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 java.util.Arrays;
00032 
00033 import org.openmobileis.common.util.OpenMISSerializable;
00034 
00043 public final class LongArray implements OpenMISSerializable {
00044         
00045   protected static final long serialVersionUID = 5521257935120563452L;
00046 
00051   private long elementData[];
00052 
00056   private int size;
00057 
00066   public LongArray(int initialCapacity) {
00067     super();
00068     if (initialCapacity < 0)
00069       throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
00070     this.elementData = new long[initialCapacity];
00071   }
00072 
00076   public LongArray() {
00077     this(10);
00078   }
00079 
00080   public void clear() {
00081     this.elementData = new long[this.elementData.length];
00082     size = 0;
00083   }
00084 
00085   protected long[] getArrayElements() {
00086     return elementData;
00087   }
00088 
00089   protected void setArrayElements(long[] array) {
00090     elementData = array;
00091   }
00092 
00101   public void ensureCapacity(int minCapacity) {
00102     int oldCapacity = elementData.length;
00103     if (minCapacity > oldCapacity) {
00104       long oldData[] = elementData;
00105       int newCapacity = (oldCapacity * 3) / 2 + 1;
00106       if (newCapacity < minCapacity)
00107         newCapacity = minCapacity;
00108       elementData = new long[newCapacity];
00109       System.arraycopy(oldData, 0, elementData, 0, size);
00110     }
00111   }
00112 
00118   public int size() {
00119     return size;
00120   }
00121 
00128         public boolean contains(long o) {
00129                 for (int i=0; i<size; i++)      {
00130                         if (elementData[i] == o)        {
00131                                 return true;
00132                         }
00133                 }
00134                 return false;
00135         }
00136 
00143   public boolean isEmpty() {
00144     return size == 0;
00145   }
00146 
00154   public long[] toArray() {
00155     long[] result = new long[size];
00156     System.arraycopy(elementData, 0, result, 0, size);
00157     return result;
00158   }
00159 
00160   // Positional Access Operations
00161 
00172   public long get(int index) {
00173     RangeCheck(index);
00174 
00175     return elementData[index];
00176   }
00177 
00185   public boolean add(long o) {
00186     ensureCapacity(size + 1); // Increments modCount!!
00187     elementData[size++] = o;
00188     return true;
00189   }
00190 
00198   public boolean add(LongArray array) {
00199     ensureCapacity(size + array.size()); // Increments modCount!!
00200     System.arraycopy(array.getArrayElements(), 0, elementData, size, array.size());
00201     size += array.size();
00202     return true;
00203   }
00204 
00212   public boolean add(long[] array) {
00213     ensureCapacity(size + array.length); // Increments modCount!!
00214     System.arraycopy(array, 0, elementData, size, array.length);
00215     size += array.length;
00216     return true;
00217   }
00218 
00229   public boolean replace(int index, long o) {
00230     if (index >= size) {
00231       return this.add(o);
00232     }
00233     elementData[index] = o;
00234     return true;
00235   }
00236 
00244   public boolean add(int index, long o) {
00245     ensureCapacity(index); // Increments modCount!!
00246     elementData[index] = o;
00247     if (index >= size)
00248       size = index + 1;
00249     return true;
00250   }
00251 
00263   public long remove(int index) {
00264     RangeCheck(index);
00265     long oldValue = elementData[index];
00266 
00267     int numMoved = size - index - 1;
00268     if (numMoved > 0)
00269       System.arraycopy(elementData, index + 1, elementData, index, numMoved);
00270     elementData[--size] = 0; // Let gc do its work
00271 
00272     return oldValue;
00273   }
00274 
00275   public void addIntersect(long[] array) {
00276     long[] thisarray = this.toArray();
00277     long[] newArray = LongArray.intersectLongArray(thisarray, array);
00278     this.elementData = newArray;
00279     this.size = this.elementData.length;
00280   }
00281 
00282   public void addUnion(long[] array) {
00283     long[] thisarray = this.toArray();
00284     long[] newArray = LongArray.unionLongArray(thisarray, array);
00285     this.elementData = newArray;
00286     this.size = this.elementData.length;
00287   }
00288 
00293   private void RangeCheck(int index) {
00294     if (index >= size || index < 0)
00295       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
00296   }
00297 
00298   public static synchronized void shellsort(long[] data) {
00299         Arrays.sort(data);
00300     // sort using Shellsort
00301  /*   int h = 1;
00302     int i = 0;
00303     if (data == null) {
00304       LogManager.traceError(0, "ERROR LogArray shellsort specified data null");
00305       throw new NullPointerException("ERROR LogArray shellsort specified data null");
00306     }
00307     int n = data.length;
00308     try {
00309 
00310       while (h <= n)
00311         h = h * 3 + 1;
00312       while (h > 1) {
00313         h /= 3;
00314         long v;
00315         for (i = h + 1; i <= n; i++) {
00316           v = data[i - 1];
00317           int j = i;
00318           while ((data[j - h - 1] - v) > 0) {
00319             data[j - 1] = data[j - h - 1];
00320             j -= h;
00321             if (j <= h)
00322               break;
00323           }
00324           data[j - 1] = v;
00325         }
00326       }
00327     } catch (IndexOutOfBoundsException ex) {
00328       if (data != null) {
00329         LogManager.traceError(0, "ERROR :LongArray shellsort error : data.length:" + data.length + " n:" + n + " h:" + h + "i:" + i);
00330         StringBuffer buff = new StringBuffer("array_data :");
00331         for (int kk = 0; kk < data.length; kk++) {
00332           buff.append(data[kk]).append('/');
00333         }
00334         LogManager.traceError(0, "LongArray shellsort error data list:" + buff.toString());
00335       }
00336       throw ex;
00337     } */
00338   }
00339 
00340   public static long[] intersectLongArray(long[] array1, long[] array2) {
00341     if (array1.length == 0)
00342       return array1;
00343     if (array2.length == 0)
00344       return array2;
00345     if (array1.length > 1)
00346       LongArray.shellsort(array1);
00347     if (array2.length > 1)
00348       LongArray.shellsort(array2);
00349 
00350     LongArray retArray = new LongArray(array1.length);
00351     long ret = 0;
00352     int i = 0, j = 0;
00353     while ((i < array1.length) && (j < array2.length)) {
00354       ret = array1[i] - array2[j];
00355       if (ret == 0) {
00356         retArray.add(array1[i]);
00357         i++;
00358         j++;
00359       } else if (ret > 0) {
00360         j++;
00361       } else {
00362         i++;
00363       }
00364     }
00365     return retArray.toArray();
00366   }
00367 
00368   public static long[] unionLongArray(long[] array1, long[] array2) {
00369     if (array1.length == 0)
00370       return array2;
00371     if (array2.length == 0)
00372       return array1;
00373     if (array1.length > 1)
00374       LongArray.shellsort(array1);
00375     if (array2.length > 1)
00376       LongArray.shellsort(array2);
00377     LongArray retArray = new LongArray(array1.length + array2.length);
00378     long ret = 0;
00379     int i = 0, j = 0;
00380     while ((i < array1.length) && (j < array2.length)) {
00381       ret = array1[i] - array2[j];
00382       if (ret == 0) {
00383         retArray.add(array1[i]);
00384         i++;
00385         j++;
00386       } else if (ret > 0) {
00387         retArray.add(array2[j]);
00388         j++;
00389       } else {
00390         retArray.add(array1[i]);
00391         i++;
00392       }
00393     }
00394     if (i < array1.length) {
00395       long[] newArray = new long[array1.length - i];
00396       System.arraycopy(array1, i, newArray, 0, newArray.length);
00397       retArray.add(newArray);
00398     }
00399     if (j < array2.length) {
00400       long[] newArray = new long[array2.length - j];
00401       System.arraycopy(array2, j, newArray, 0, newArray.length);
00402       retArray.add(newArray);
00403     }
00404 
00405     return retArray.toArray();
00406   }
00407 
00419   public static long[] diffLongArray(long[] array1, long[] array2) {
00420     if (array1.length == 0)
00421       return array2;
00422     if (array2.length == 0)
00423       return array2;
00424     if (array1.length > 1)
00425       LongArray.shellsort(array1);
00426     if (array2.length > 1)
00427       LongArray.shellsort(array2);
00428 
00429     LongArray retArray = new LongArray(array2.length);
00430     long ret = 0;
00431     int i = 0, j = 0;
00432     while ((i < array1.length) && (j < array2.length)) {
00433       ret = array1[i] - array2[j];
00434       if (ret == 0) {
00435         i++;
00436         j++;
00437       } else if (ret > 0) {
00438         retArray.add(array2[j]);
00439         j++;
00440       } else {
00441         i++;
00442       }
00443     }
00444     // add end of second array
00445     for (i = j; i < array2.length; i++) {
00446       retArray.add(array2[i]);
00447     }
00448     return retArray.toArray();
00449   }
00450   
00451   public static void main(String[] args)        {
00452         long[] array = new long[]{64503,98492,125925,92863,216997,220236,60096,50894,46147,200767,250096,149978,196629,295896,74650,379255,167916,242275,421185,423220,282319,467503,276760,278447,471319,396347,416000,391491,462370,398735,425386,412277,460000};
00453         
00454         LongArray.shellsort(array);
00455   }
00456 }

Generated on Mon Jan 11 21:19:15 2010 for OpenMobileIS by  doxygen 1.5.4