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 isEmpty() {
00127 return size == 0;
00128 }
00129
00137 public long[] toArray() {
00138 long[] result = new long[size];
00139 System.arraycopy(elementData, 0, result, 0, size);
00140 return result;
00141 }
00142
00143
00144
00155 public long get(int index) {
00156 RangeCheck(index);
00157
00158 return elementData[index];
00159 }
00160
00168 public boolean add(long o) {
00169 ensureCapacity(size + 1);
00170 elementData[size++] = o;
00171 return true;
00172 }
00173
00181 public boolean add(LongArray array) {
00182 ensureCapacity(size + array.size());
00183 System.arraycopy(array.getArrayElements(), 0, elementData, size, array.size());
00184 size += array.size();
00185 return true;
00186 }
00187
00195 public boolean add(long[] array) {
00196 ensureCapacity(size + array.length);
00197 System.arraycopy(array, 0, elementData, size, array.length);
00198 size += array.length;
00199 return true;
00200 }
00201
00212 public boolean replace(int index, long o) {
00213 if (index >= size) {
00214 return this.add(o);
00215 }
00216 elementData[index] = o;
00217 return true;
00218 }
00219
00227 public boolean add(int index, long o) {
00228 ensureCapacity(index);
00229 elementData[index] = o;
00230 if (index >= size)
00231 size = index + 1;
00232 return true;
00233 }
00234
00246 public long remove(int index) {
00247 RangeCheck(index);
00248 long oldValue = elementData[index];
00249
00250 int numMoved = size - index - 1;
00251 if (numMoved > 0)
00252 System.arraycopy(elementData, index + 1, elementData, index, numMoved);
00253 elementData[--size] = 0;
00254
00255 return oldValue;
00256 }
00257
00258 public void addIntersect(long[] array) {
00259 long[] thisarray = this.toArray();
00260 long[] newArray = LongArray.intersectLongArray(thisarray, array);
00261 this.elementData = newArray;
00262 this.size = this.elementData.length;
00263 }
00264
00265 public void addUnion(long[] array) {
00266 long[] thisarray = this.toArray();
00267 long[] newArray = LongArray.unionLongArray(thisarray, array);
00268 this.elementData = newArray;
00269 this.size = this.elementData.length;
00270 }
00271
00276 private void RangeCheck(int index) {
00277 if (index >= size || index < 0)
00278 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
00279 }
00280
00281 public static void shellsort(long[] data) {
00282
00283 int h = 1;
00284 int i = 0;
00285 if (data == null) {
00286 LogManager.traceError(0, "ERROR LogArray shellsort specified data null");
00287 throw new NullPointerException("ERROR LogArray shellsort specified data null");
00288 }
00289 int n = data.length;
00290 try {
00291
00292 while (h <= n)
00293 h = h * 3 + 1;
00294 while (h > 1) {
00295 h /= 3;
00296 long v;
00297 for (i = h + 1; i <= n; i++) {
00298 v = data[i - 1];
00299 int j = i;
00300 while ((data[j - h - 1] - v) > 0) {
00301 data[j - 1] = data[j - h - 1];
00302 j -= h;
00303 if (j <= h)
00304 break;
00305 }
00306 data[j - 1] = v;
00307 }
00308 }
00309 } catch (IndexOutOfBoundsException ex) {
00310 if (data != null) {
00311 LogManager.traceError(0, "ERROR :LongArray shellsort error : data.length:" + data.length + " n:" + n + " h:" + h + "i:" + i);
00312 StringBuffer buff = new StringBuffer("array_data :");
00313 for (int j = 0; i < data.length; j++) {
00314 buff.append(data[i]).append('/');
00315 }
00316 LogManager.traceError(0, "LongArray shellsort error data list:" + buff.toString());
00317 }
00318 throw ex;
00319 }
00320 }
00321
00322 public static long[] intersectLongArray(long[] array1, long[] array2) {
00323 if (array1.length == 0)
00324 return array1;
00325 if (array2.length == 0)
00326 return array2;
00327 if (array1.length > 1)
00328 LongArray.shellsort(array1);
00329 if (array2.length > 1)
00330 LongArray.shellsort(array2);
00331
00332 LongArray retArray = new LongArray(array1.length);
00333 long ret = 0;
00334 int i = 0, j = 0;
00335 while ((i < array1.length) && (j < array2.length)) {
00336 ret = array1[i] - array2[j];
00337 if (ret == 0) {
00338 retArray.add(array1[i]);
00339 i++;
00340 j++;
00341 } else if (ret > 0) {
00342 j++;
00343 } else {
00344 i++;
00345 }
00346 }
00347 return retArray.toArray();
00348 }
00349
00350 public static long[] unionLongArray(long[] array1, long[] array2) {
00351 if (array1.length == 0)
00352 return array2;
00353 if (array2.length == 0)
00354 return array1;
00355 if (array1.length > 1)
00356 LongArray.shellsort(array1);
00357 if (array2.length > 1)
00358 LongArray.shellsort(array2);
00359 LongArray retArray = new LongArray(array1.length + array2.length);
00360 long ret = 0;
00361 int i = 0, j = 0;
00362 while ((i < array1.length) && (j < array2.length)) {
00363 ret = array1[i] - array2[j];
00364 if (ret == 0) {
00365 retArray.add(array1[i]);
00366 i++;
00367 j++;
00368 } else if (ret > 0) {
00369 retArray.add(array2[j]);
00370 j++;
00371 } else {
00372 retArray.add(array1[i]);
00373 i++;
00374 }
00375 }
00376 if (i < array1.length) {
00377 long[] newArray = new long[array1.length - i];
00378 System.arraycopy(array1, i, newArray, 0, newArray.length);
00379 retArray.add(newArray);
00380 }
00381 if (j < array2.length) {
00382 long[] newArray = new long[array2.length - j];
00383 System.arraycopy(array2, j, newArray, 0, newArray.length);
00384 retArray.add(newArray);
00385 }
00386
00387 return retArray.toArray();
00388 }
00389
00401 public static long[] diffLongArray(long[] array1, long[] array2) {
00402 if (array1.length == 0)
00403 return array2;
00404 if (array2.length == 0)
00405 return array2;
00406 if (array1.length > 1)
00407 LongArray.shellsort(array1);
00408 if (array2.length > 1)
00409 LongArray.shellsort(array2);
00410
00411 LongArray retArray = new LongArray(array2.length);
00412 long ret = 0;
00413 int i = 0, j = 0;
00414 while ((i < array1.length) && (j < array2.length)) {
00415 ret = array1[i] - array2[j];
00416 if (ret == 0) {
00417 i++;
00418 j++;
00419 } else if (ret > 0) {
00420 retArray.add(array2[j]);
00421 j++;
00422 } else {
00423 i++;
00424 }
00425 }
00426
00427 for (i = j; i < array2.length; i++) {
00428 retArray.add(array2[i]);
00429 }
00430 return retArray.toArray();
00431 }
00432 }