LongArray.java

00001 /*
00002  * OpenMobileIS - a free Java(TM) Framework for mobile applications Java(TM)
00003  * Copyright (C) 2004-2006 Philippe Delrieu
00004  * All rights reserved.
00005  * Contact: pdelrieu@openmobileis.org
00006  *
00007  * This library is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Lesser General Public
00009  * License as published by the Free Software Foundation; either
00010  * version 2.1 of the License, or any later version.
00011  *
00012  * This library is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  * Lesser General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Lesser General Public
00018  * License along with this library; if not, write to the Free Software
00019  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
00020  * USA
00021  *
00022  *  Author : Philippe Delrieu
00023  *  
00024  *  Modifications :
00025  *  2004 Creation P.Delrieu
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   // Positional Access Operations
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); // Increments modCount!!
00170     elementData[size++] = o;
00171     return true;
00172   }
00173 
00181   public boolean add(LongArray array) {
00182     ensureCapacity(size + array.size()); // Increments modCount!!
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); // Increments modCount!!
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); // Increments modCount!!
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; // Let gc do its work
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     // sort using Shellsort
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     // add end of second array
00427     for (i = j; i < array2.length; i++) {
00428       retArray.add(array2[i]);
00429     }
00430     return retArray.toArray();
00431   }
00432 }

Generated on Mon Dec 4 11:03:27 2006 for OpenMobileIS by  doxygen 1.5.1-p1