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 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   // Positional Access Operations
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); // Increments modCount!!
00185     elementData[size++] = o;
00186     return true;
00187   }
00188 
00196   public boolean add(LongArray array) {
00197     ensureCapacity(size + array.size()); // Increments modCount!!
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); // Increments modCount!!
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); // Increments modCount!!
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; // Let gc do its work
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     // sort using Shellsort
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     // add end of second array
00442     for (i = j; i < array2.length; i++) {
00443       retArray.add(array2[i]);
00444     }
00445     return retArray.toArray();
00446   }
00447 }

Generated on Tue May 22 23:01:10 2007 for OpenMobileIS by  doxygen 1.5.1-p1