Sort.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.Vector;
00032 
00040 public class Sort {
00041 
00042         // no one should instantiate this class
00043 
00044         private Sort() {}
00045 
00056         public synchronized static void shellsort(Vector vec, Orderable op)
00057         {
00058                 if (vec == null || op == null)
00059                         throw new IllegalArgumentException("null argument");
00060 
00061                 int n = vec.size();
00062                 if (n < 2)
00063                         return;
00064 
00065                 // copy out Vector slots to speed things up
00066     int i = 0;
00067                 Object new_vec[] = new Object[n];
00068                 for (i = 0; i < n; i++)
00069                         new_vec[i] = vec.elementAt(i);
00070 
00071     shellsort(new_vec, op);
00072 
00073                 // copy back to Vector
00074 
00075                 for (i = 0; i < n; i++)
00076                         vec.setElementAt(new_vec[i], i);
00077         }
00078 
00079 
00091         public synchronized static void shellsort(Array array, Orderable op)    {
00092                 if (array == null || op == null)
00093                         throw new IllegalArgumentException("null argument");
00094 
00095                 int n = array.size();
00096                 if (n < 2)
00097                         return;
00098 
00099                 // copy out Vector slots to speed things up
00100                 Object new_vec[] = new Object[n];
00101                 System.arraycopy(array.getArrayElements(),0, new_vec, 0, n);
00102 
00103     shellsort(new_vec, op);
00104 
00105                 // copy back to Vector
00106     array.setArrayElements(new_vec);
00107         }
00108 
00109   public static void shellsort(Object[] data, Orderable op)  {
00110                 // sort using Shellsort
00111                 int h = 1;
00112                 int i = 0;
00113                 int n = data.length;
00114 
00115 
00116                 while (h <= n)
00117                         h = h * 3 + 1;
00118                 while (h > 1) {
00119                         h /= 3;
00120                         for (i = h + 1; i <= n; i++) {
00121                                 Object v = data[i - 1];
00122                                 int j = i;
00123                                 while (op.compareTo(data[j - h - 1], v) > 0) {
00124                                         data[j - 1] = data[j - h - 1];
00125                                         j -= h;
00126                                         if (j <= h)
00127                                                 break;
00128                                 }
00129                                 data[j - 1] = v;
00130                         }
00131                 }
00132   }
00133   
00143   public static Object[] returnANotInB(Object[] A, Object[] B, Orderable order) {
00144         if (A == null) return null;
00145         Sort.shellsort(A, order);
00146         if (B == null) return A;
00147         Sort.shellsort(B, order);
00148         
00149         Array ret = new Array(A.length);
00150                 int comptA = 0;
00151                 int comptB = 0;
00152                 Object inA = null;
00153                 Object inB = null;
00154                 
00155                 int compare = 0;
00156                 
00157                 while (comptA < A.length && comptB < B.length) {
00158                         
00159                         inA = A[comptA];
00160                         inB = B[comptB];
00161                         
00162                         compare = order.compareTo(inA, inB);
00163                  
00164                         if (compare <0){
00165                                 ret.add(A[comptA]);
00166                                 comptA++;
00167       } else if (compare > 0) {
00168         comptB ++;
00169       } else    {
00170                                 comptA++;
00171         comptB ++;
00172       }
00173                 }
00174                 Object[] toreturn = null;
00175                 if (comptA < A.length)  { //add remaining.
00176                         toreturn = new Object[ret.size+(A.length-comptA)];
00177                         ret.toArray(toreturn);
00178                         System.arraycopy(A, comptA, toreturn, ret.size(), (A.length-comptA));
00179                 } else  {
00180                         toreturn = ret.toArray();
00181                 }
00182         return toreturn;
00183   }
00184 
00185 }

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