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 org.openmobileis.common.util.OpenMISSerializable;
00032 import org.openmobileis.common.util.log.LogManager;
00033
00042 public final class LongArray implements OpenMISSerializable {
00043 protected static final long serialVersionUID = 5521257935120563452L;
00044
00049 private long elementData[];
00050
00054 private int size;
00055
00064 public LongArray(int initialCapacity) {
00065 super();
00066 if (initialCapacity < 0)
00067 throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
00068 this.elementData = new long[initialCapacity];
00069 }
00070
00074 public LongArray() {
00075 this(10);
00076 }
00077
00078 public void clear() {
00079 this.elementData = new long[this.elementData.length];
00080 size = 0;
00081 }
00082
00083 protected long[] getArrayElements() {
00084 return elementData;
00085 }
00086
00087 protected void setArrayElements(long[] array) {
00088 elementData = array;
00089 }
00090
00099 public void ensureCapacity(int minCapacity) {
00100 int oldCapacity = elementData.length;
00101 if (minCapacity > oldCapacity) {
00102 long oldData[] = elementData;
00103 int newCapacity = (oldCapacity * 3) / 2 + 1;
00104 if (newCapacity < minCapacity)
00105 newCapacity = minCapacity;
00106 elementData = new long[newCapacity];
00107 System.arraycopy(oldData, 0, elementData, 0, size);
00108 }
00109 }
00110
00116 public int size() {
00117 return size;
00118 }
00119
00126 public boolean contains(long o) {
00127 for (int i=0; i<size; i++) {
00128 if (elementData[i] == o) {
00129 return true;
00130 }
00131 }
00132 return false;
00133 }
00134
00141 public boolean isEmpty() {
00142 return size == 0;
00143 }
00144
00152 public long[] toArray() {
00153 long[] result = new long[size];
00154 System.arraycopy(elementData, 0, result, 0, size);
00155 return result;
00156 }
00157
00158
00159
00170 public long get(int index) {
00171 RangeCheck(index);
00172
00173 return elementData[index];
00174 }
00175
00183 public boolean add(long o) {
00184 ensureCapacity(size + 1);
00185 elementData[size++] = o;
00186 return true;
00187 }
00188
00196 public boolean add(LongArray array) {
00197 ensureCapacity(size + array.size());
00198 System.arraycopy(array.getArrayElements(), 0, elementData, size, array.size());
00199 size += array.size();
00200 return true;
00201 }
00202
00210 public boolean add(long[] array) {
00211 ensureCapacity(size + array.length);
00212 System.arraycopy(array, 0, elementData, size, array.length);
00213 size += array.length;
00214 return true;
00215 }
00216
00227 public boolean replace(int index, long o) {
00228 if (index >= size) {
00229 return this.add(o);
00230 }
00231 elementData[index] = o;
00232 return true;
00233 }
00234
00242 public boolean add(int index, long o) {
00243 ensureCapacity(index);
00244 elementData[index] = o;
00245 if (index >= size)
00246 size = index + 1;
00247 return true;
00248 }
00249
00261 public long remove(int index) {
00262 RangeCheck(index);
00263 long oldValue = elementData[index];
00264
00265 int numMoved = size - index - 1;
00266 if (numMoved > 0)
00267 System.arraycopy(elementData, index + 1, elementData, index, numMoved);
00268 elementData[--size] = 0;
00269
00270 return oldValue;
00271 }
00272
00273 public void addIntersect(long[] array) {
00274 long[] thisarray = this.toArray();
00275 long[] newArray = LongArray.intersectLongArray(thisarray, array);
00276 this.elementData = newArray;
00277 this.size = this.elementData.length;
00278 }
00279
00280 public void addUnion(long[] array) {
00281 long[] thisarray = this.toArray();
00282 long[] newArray = LongArray.unionLongArray(thisarray, array);
00283 this.elementData = newArray;
00284 this.size = this.elementData.length;
00285 }
00286
00291 private void RangeCheck(int index) {
00292 if (index >= size || index < 0)
00293 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
00294 }
00295
00296 public static void shellsort(long[] data) {
00297
00298 int h = 1;
00299 int i = 0;
00300 if (data == null) {
00301 LogManager.traceError(0, "ERROR LogArray shellsort specified data null");
00302 throw new NullPointerException("ERROR LogArray shellsort specified data null");
00303 }
00304 int n = data.length;
00305 try {
00306
00307 while (h <= n)
00308 h = h * 3 + 1;
00309 while (h > 1) {
00310 h /= 3;
00311 long v;
00312 for (i = h + 1; i <= n; i++) {
00313 v = data[i - 1];
00314 int j = i;
00315 while ((data[j - h - 1] - v) > 0) {
00316 data[j - 1] = data[j - h - 1];
00317 j -= h;
00318 if (j <= h)
00319 break;
00320 }
00321 data[j - 1] = v;
00322 }
00323 }
00324 } catch (IndexOutOfBoundsException ex) {
00325 if (data != null) {
00326 LogManager.traceError(0, "ERROR :LongArray shellsort error : data.length:" + data.length + " n:" + n + " h:" + h + "i:" + i);
00327 StringBuffer buff = new StringBuffer("array_data :");
00328 for (int j = 0; i < data.length; j++) {
00329 buff.append(data[i]).append('/');
00330 }
00331 LogManager.traceError(0, "LongArray shellsort error data list:" + buff.toString());
00332 }
00333 throw ex;
00334 }
00335 }
00336
00337 public static long[] intersectLongArray(long[] array1, long[] array2) {
00338 if (array1.length == 0)
00339 return array1;
00340 if (array2.length == 0)
00341 return array2;
00342 if (array1.length > 1)
00343 LongArray.shellsort(array1);
00344 if (array2.length > 1)
00345 LongArray.shellsort(array2);
00346
00347 LongArray retArray = new LongArray(array1.length);
00348 long ret = 0;
00349 int i = 0, j = 0;
00350 while ((i < array1.length) && (j < array2.length)) {
00351 ret = array1[i] - array2[j];
00352 if (ret == 0) {
00353 retArray.add(array1[i]);
00354 i++;
00355 j++;
00356 } else if (ret > 0) {
00357 j++;
00358 } else {
00359 i++;
00360 }
00361 }
00362 return retArray.toArray();
00363 }
00364
00365 public static long[] unionLongArray(long[] array1, long[] array2) {
00366 if (array1.length == 0)
00367 return array2;
00368 if (array2.length == 0)
00369 return array1;
00370 if (array1.length > 1)
00371 LongArray.shellsort(array1);
00372 if (array2.length > 1)
00373 LongArray.shellsort(array2);
00374 LongArray retArray = new LongArray(array1.length + array2.length);
00375 long ret = 0;
00376 int i = 0, j = 0;
00377 while ((i < array1.length) && (j < array2.length)) {
00378 ret = array1[i] - array2[j];
00379 if (ret == 0) {
00380 retArray.add(array1[i]);
00381 i++;
00382 j++;
00383 } else if (ret > 0) {
00384 retArray.add(array2[j]);
00385 j++;
00386 } else {
00387 retArray.add(array1[i]);
00388 i++;
00389 }
00390 }
00391 if (i < array1.length) {
00392 long[] newArray = new long[array1.length - i];
00393 System.arraycopy(array1, i, newArray, 0, newArray.length);
00394 retArray.add(newArray);
00395 }
00396 if (j < array2.length) {
00397 long[] newArray = new long[array2.length - j];
00398 System.arraycopy(array2, j, newArray, 0, newArray.length);
00399 retArray.add(newArray);
00400 }
00401
00402 return retArray.toArray();
00403 }
00404
00416 public static long[] diffLongArray(long[] array1, long[] array2) {
00417 if (array1.length == 0)
00418 return array2;
00419 if (array2.length == 0)
00420 return array2;
00421 if (array1.length > 1)
00422 LongArray.shellsort(array1);
00423 if (array2.length > 1)
00424 LongArray.shellsort(array2);
00425
00426 LongArray retArray = new LongArray(array2.length);
00427 long ret = 0;
00428 int i = 0, j = 0;
00429 while ((i < array1.length) && (j < array2.length)) {
00430 ret = array1[i] - array2[j];
00431 if (ret == 0) {
00432 i++;
00433 j++;
00434 } else if (ret > 0) {
00435 retArray.add(array2[j]);
00436 j++;
00437 } else {
00438 i++;
00439 }
00440 }
00441
00442 for (i = j; i < array2.length; i++) {
00443 retArray.add(array2[i]);
00444 }
00445 return retArray.toArray();
00446 }
00447 }