00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 package org.openmobileis.common.util.collection;
00030
00031 import java.util.Arrays;
00032
00033 import org.openmobileis.common.util.OpenMISSerializable;
00034
00043 public final class LongArray implements OpenMISSerializable {
00044
00045 protected static final long serialVersionUID = 5521257935120563452L;
00046
00051 private long elementData[];
00052
00056 private int size;
00057
00066 public LongArray(int initialCapacity) {
00067 super();
00068 if (initialCapacity < 0)
00069 throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
00070 this.elementData = new long[initialCapacity];
00071 }
00072
00076 public LongArray() {
00077 this(10);
00078 }
00079
00080 public void clear() {
00081 this.elementData = new long[this.elementData.length];
00082 size = 0;
00083 }
00084
00085 protected long[] getArrayElements() {
00086 return elementData;
00087 }
00088
00089 protected void setArrayElements(long[] array) {
00090 elementData = array;
00091 }
00092
00101 public void ensureCapacity(int minCapacity) {
00102 int oldCapacity = elementData.length;
00103 if (minCapacity > oldCapacity) {
00104 long oldData[] = elementData;
00105 int newCapacity = (oldCapacity * 3) / 2 + 1;
00106 if (newCapacity < minCapacity)
00107 newCapacity = minCapacity;
00108 elementData = new long[newCapacity];
00109 System.arraycopy(oldData, 0, elementData, 0, size);
00110 }
00111 }
00112
00118 public int size() {
00119 return size;
00120 }
00121
00128 public boolean contains(long o) {
00129 for (int i=0; i<size; i++) {
00130 if (elementData[i] == o) {
00131 return true;
00132 }
00133 }
00134 return false;
00135 }
00136
00143 public boolean isEmpty() {
00144 return size == 0;
00145 }
00146
00154 public long[] toArray() {
00155 long[] result = new long[size];
00156 System.arraycopy(elementData, 0, result, 0, size);
00157 return result;
00158 }
00159
00160
00161
00172 public long get(int index) {
00173 RangeCheck(index);
00174
00175 return elementData[index];
00176 }
00177
00185 public boolean add(long o) {
00186 ensureCapacity(size + 1);
00187 elementData[size++] = o;
00188 return true;
00189 }
00190
00198 public boolean add(LongArray array) {
00199 ensureCapacity(size + array.size());
00200 System.arraycopy(array.getArrayElements(), 0, elementData, size, array.size());
00201 size += array.size();
00202 return true;
00203 }
00204
00212 public boolean add(long[] array) {
00213 ensureCapacity(size + array.length);
00214 System.arraycopy(array, 0, elementData, size, array.length);
00215 size += array.length;
00216 return true;
00217 }
00218
00229 public boolean replace(int index, long o) {
00230 if (index >= size) {
00231 return this.add(o);
00232 }
00233 elementData[index] = o;
00234 return true;
00235 }
00236
00244 public boolean add(int index, long o) {
00245 ensureCapacity(index);
00246 elementData[index] = o;
00247 if (index >= size)
00248 size = index + 1;
00249 return true;
00250 }
00251
00263 public long remove(int index) {
00264 RangeCheck(index);
00265 long oldValue = elementData[index];
00266
00267 int numMoved = size - index - 1;
00268 if (numMoved > 0)
00269 System.arraycopy(elementData, index + 1, elementData, index, numMoved);
00270 elementData[--size] = 0;
00271
00272 return oldValue;
00273 }
00274
00275 public void addIntersect(long[] array) {
00276 long[] thisarray = this.toArray();
00277 long[] newArray = LongArray.intersectLongArray(thisarray, array);
00278 this.elementData = newArray;
00279 this.size = this.elementData.length;
00280 }
00281
00282 public void addUnion(long[] array) {
00283 long[] thisarray = this.toArray();
00284 long[] newArray = LongArray.unionLongArray(thisarray, array);
00285 this.elementData = newArray;
00286 this.size = this.elementData.length;
00287 }
00288
00293 private void RangeCheck(int index) {
00294 if (index >= size || index < 0)
00295 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
00296 }
00297
00298 public static synchronized void shellsort(long[] data) {
00299 Arrays.sort(data);
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338 }
00339
00340 public static long[] intersectLongArray(long[] array1, long[] array2) {
00341 if (array1.length == 0)
00342 return array1;
00343 if (array2.length == 0)
00344 return array2;
00345 if (array1.length > 1)
00346 LongArray.shellsort(array1);
00347 if (array2.length > 1)
00348 LongArray.shellsort(array2);
00349
00350 LongArray retArray = new LongArray(array1.length);
00351 long ret = 0;
00352 int i = 0, j = 0;
00353 while ((i < array1.length) && (j < array2.length)) {
00354 ret = array1[i] - array2[j];
00355 if (ret == 0) {
00356 retArray.add(array1[i]);
00357 i++;
00358 j++;
00359 } else if (ret > 0) {
00360 j++;
00361 } else {
00362 i++;
00363 }
00364 }
00365 return retArray.toArray();
00366 }
00367
00368 public static long[] unionLongArray(long[] array1, long[] array2) {
00369 if (array1.length == 0)
00370 return array2;
00371 if (array2.length == 0)
00372 return array1;
00373 if (array1.length > 1)
00374 LongArray.shellsort(array1);
00375 if (array2.length > 1)
00376 LongArray.shellsort(array2);
00377 LongArray retArray = new LongArray(array1.length + array2.length);
00378 long ret = 0;
00379 int i = 0, j = 0;
00380 while ((i < array1.length) && (j < array2.length)) {
00381 ret = array1[i] - array2[j];
00382 if (ret == 0) {
00383 retArray.add(array1[i]);
00384 i++;
00385 j++;
00386 } else if (ret > 0) {
00387 retArray.add(array2[j]);
00388 j++;
00389 } else {
00390 retArray.add(array1[i]);
00391 i++;
00392 }
00393 }
00394 if (i < array1.length) {
00395 long[] newArray = new long[array1.length - i];
00396 System.arraycopy(array1, i, newArray, 0, newArray.length);
00397 retArray.add(newArray);
00398 }
00399 if (j < array2.length) {
00400 long[] newArray = new long[array2.length - j];
00401 System.arraycopy(array2, j, newArray, 0, newArray.length);
00402 retArray.add(newArray);
00403 }
00404
00405 return retArray.toArray();
00406 }
00407
00419 public static long[] diffLongArray(long[] array1, long[] array2) {
00420 if (array1.length == 0)
00421 return array2;
00422 if (array2.length == 0)
00423 return array2;
00424 if (array1.length > 1)
00425 LongArray.shellsort(array1);
00426 if (array2.length > 1)
00427 LongArray.shellsort(array2);
00428
00429 LongArray retArray = new LongArray(array2.length);
00430 long ret = 0;
00431 int i = 0, j = 0;
00432 while ((i < array1.length) && (j < array2.length)) {
00433 ret = array1[i] - array2[j];
00434 if (ret == 0) {
00435 i++;
00436 j++;
00437 } else if (ret > 0) {
00438 retArray.add(array2[j]);
00439 j++;
00440 } else {
00441 i++;
00442 }
00443 }
00444
00445 for (i = j; i < array2.length; i++) {
00446 retArray.add(array2[i]);
00447 }
00448 return retArray.toArray();
00449 }
00450
00451 public static void main(String[] args) {
00452 long[] array = new long[]{64503,98492,125925,92863,216997,220236,60096,50894,46147,200767,250096,149978,196629,295896,74650,379255,167916,242275,421185,423220,282319,467503,276760,278447,471319,396347,416000,391491,462370,398735,425386,412277,460000};
00453
00454 LongArray.shellsort(array);
00455 }
00456 }