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
00030 package org.openmobileis.common.util.collection;
00031
00032 import org.openmobileis.common.util.OpenMISSerializable;
00033
00041 public final class LongArray implements OpenMISSerializable {
00042 protected static final long serialVersionUID = 5521257935120563452L;
00043
00048 private long elementData[];
00049
00053 private int size;
00054
00062 public LongArray(int initialCapacity) {
00063 super();
00064 if (initialCapacity < 0)
00065 throw new IllegalArgumentException("Illegal Capacity: "
00066 + initialCapacity);
00067 this.elementData = new long[initialCapacity];
00068 }
00069
00073 public LongArray() {
00074 this(10);
00075 }
00076
00077 public void clear() {
00078 this.elementData = new long[this.elementData.length];
00079 size = 0;
00080 }
00081
00082 protected long[] getArrayElements() {
00083 return elementData;
00084 }
00085
00086 protected void setArrayElements(long[] array) {
00087 elementData = array;
00088 }
00089
00097 public void ensureCapacity(int minCapacity) {
00098 int oldCapacity = elementData.length;
00099 if (minCapacity > oldCapacity) {
00100 long oldData[] = elementData;
00101 int newCapacity = (oldCapacity * 3) / 2 + 1;
00102 if (newCapacity < minCapacity)
00103 newCapacity = minCapacity;
00104 elementData = new long[newCapacity];
00105 System.arraycopy(oldData, 0, elementData, 0, size);
00106 }
00107 }
00108
00114 public int size() {
00115 return size;
00116 }
00117
00124 public boolean isEmpty() {
00125 return size == 0;
00126 }
00127
00135 public long[] toArray() {
00136 long[] result = new long[size];
00137 System.arraycopy(elementData, 0, result, 0, size);
00138 return result;
00139 }
00140
00141
00142
00151 public long get(int index) {
00152 RangeCheck(index);
00153
00154 return elementData[index];
00155 }
00156
00163 public boolean add(long o) {
00164 ensureCapacity(size + 1);
00165 elementData[size++] = o;
00166 return true;
00167 }
00168
00175 public boolean add(LongArray array) {
00176 ensureCapacity(size + array.size());
00177 System.arraycopy(array.getArrayElements(), 0, elementData, size, array
00178 .size());
00179 size += array.size();
00180 return true;
00181 }
00182
00189 public boolean add(long[] array) {
00190 ensureCapacity(size + array.length);
00191 System.arraycopy(array, 0, elementData, size, array.length);
00192 size += array.length;
00193 return true;
00194 }
00195
00204 public boolean replace(int index, long o) {
00205 if (index >= size) {
00206 return this.add(o);
00207 }
00208 elementData[index] = o;
00209 return true;
00210 }
00211
00218 public boolean add(int index, long o) {
00219 ensureCapacity(index);
00220 elementData[index] = o;
00221 if (index >= size)
00222 size = index + 1;
00223 return true;
00224 }
00225
00236 public long remove(int index) {
00237 RangeCheck(index);
00238 long oldValue = elementData[index];
00239
00240 int numMoved = size - index - 1;
00241 if (numMoved > 0)
00242 System.arraycopy(elementData, index + 1, elementData, index,
00243 numMoved);
00244 elementData[--size] = 0;
00245
00246 return oldValue;
00247 }
00248
00249 public void addIntersect(long[] array) {
00250 long[] thisarray = this.toArray();
00251 long[] newArray = LongArray.intersectLongArray(thisarray, array);
00252 this.elementData = newArray;
00253 this.size = this.elementData.length;
00254 }
00255
00256 public void addUnion(long[] array) {
00257 long[] thisarray = this.toArray();
00258 long[] newArray = LongArray.unionLongArray(thisarray, array);
00259 this.elementData = newArray;
00260 this.size = this.elementData.length;
00261 }
00262
00267 private void RangeCheck(int index) {
00268 if (index >= size || index < 0)
00269 throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
00270 + size);
00271 }
00272
00273 public static void shellsort(long[] data) {
00274
00275 int h = 1;
00276 int i = 0;
00277 int n = data.length;
00278
00279 while (h <= n)
00280 h = h * 3 + 1;
00281 while (h > 1) {
00282 h /= 3;
00283 long v;
00284 for (i = h + 1; i <= n; i++) {
00285 v = data[i - 1];
00286 int j = i;
00287 while ((data[j - h - 1] - v) > 0) {
00288 data[j - 1] = data[j - h - 1];
00289 j -= h;
00290 if (j <= h)
00291 break;
00292 }
00293 data[j - 1] = v;
00294 }
00295 }
00296 }
00297
00298 public static long[] intersectLongArray(long[] array1, long[] array2) {
00299 if (array1.length == 0)
00300 return array1;
00301 if (array2.length == 0)
00302 return array2;
00303 if (array1.length > 1)
00304 LongArray.shellsort(array1);
00305 if (array2.length > 1)
00306 LongArray.shellsort(array2);
00307
00308 LongArray retArray = new LongArray(array1.length);
00309 long ret = 0;
00310 int i = 0, j = 0;
00311 while ((i < array1.length) && (j < array2.length)) {
00312 ret = array1[i] - array2[j];
00313 if (ret == 0) {
00314 retArray.add(array1[i]);
00315 i++;
00316 j++;
00317 } else if (ret > 0) {
00318 j++;
00319 } else {
00320 i++;
00321 }
00322 }
00323 return retArray.toArray();
00324 }
00325
00326 public static long[] unionLongArray(long[] array1, long[] array2) {
00327 if (array1.length == 0)
00328 return array2;
00329 if (array2.length == 0)
00330 return array1;
00331 if (array1.length > 1)
00332 LongArray.shellsort(array1);
00333 if (array2.length > 1)
00334 LongArray.shellsort(array2);
00335 LongArray retArray = new LongArray(array1.length + array2.length);
00336 long ret = 0;
00337 int i = 0, j = 0;
00338 while ((i < array1.length) && (j < array2.length)) {
00339 ret = array1[i] - array2[j];
00340 if (ret == 0) {
00341 retArray.add(array1[i]);
00342 i++;
00343 j++;
00344 } else if (ret > 0) {
00345 retArray.add(array2[j]);
00346 j++;
00347 } else {
00348 retArray.add(array1[i]);
00349 i++;
00350 }
00351 }
00352 if (i < array1.length) {
00353 long[] newArray = new long[array1.length - i];
00354 System.arraycopy(array1, i, newArray, 0, newArray.length);
00355 retArray.add(newArray);
00356 }
00357 if (j < array2.length) {
00358 long[] newArray = new long[array2.length - j];
00359 System.arraycopy(array2, j, newArray, 0, newArray.length);
00360 retArray.add(newArray);
00361 }
00362
00363 return retArray.toArray();
00364 }
00365
00372 public static long[] diffLongArray(long[] array1, long[] array2) {
00373 if (array1.length == 0)
00374 return array2;
00375 if (array2.length == 0)
00376 return array2;
00377 if (array1.length > 1)
00378 LongArray.shellsort(array1);
00379 if (array2.length > 1)
00380 LongArray.shellsort(array2);
00381
00382 LongArray retArray = new LongArray(array2.length);
00383 long ret = 0;
00384 int i = 0, j = 0;
00385 while ((i < array1.length) && (j < array2.length)) {
00386 ret = array1[i] - array2[j];
00387 if (ret == 0) {
00388 i++;
00389 j++;
00390 } else if (ret > 0) {
00391 retArray.add(array2[j]);
00392 j++;
00393 } else {
00394 i++;
00395 }
00396 }
00397
00398 for (i = j; i < array2.length; i++) {
00399 retArray.add(array2[i]);
00400 }
00401 return retArray.toArray();
00402 }
00403 }