SortedVector


1   /*
2   
3   This software is OSI Certified Open Source Software.
4   OSI Certified is a certification mark of the Open Source Initiative.
5   
6   The license (Mozilla version 1.0) can be read at the MMBase site.
7   See http://www.MMBase.org/license
8   
9   */
10  package org.mmbase.util;
11  
12  import java.util.Vector  ;
13  import java.util.Enumeration  ;
14  import org.mmbase.util.logging.*;
15  
16  /**
17   * Class to store Objects in, in a Sorted manner
18   *
19   * @see org.mmbase.util.Sortable
20   * @see org.mmbase.util.CompareInterface
21   *
22   *
23   * Todo: Remove duplicate code for the binary search
24   * @deprecated You can use java.util.SortedSet (implementations of that), or Collections.sort(), if duplicate entries are essential (but how should they be sorted then?)
25   * @author Rico Jansen
26   * @version $Id: SortedVector.java,v 1.10 2004/09/30 16:08:39 pierre Exp $
27   */
28  public class SortedVector extends java.util.Vector   {
29  
30      // logger
31      private static Logger log = Logging.getLoggerInstance(SortedVector.class.getName());
32  
33      CompareInterface cmp=null;
34      CompareInterface sortcmp=new SortableCompare();
35      CompareInterface stringcmp=new StringCompare();
36  
37      /**
38       * Create a SortedVector
39       */
40      public SortedVector() {
41          super();
42      }
43  
44      /**
45       * Create a SortedVector, specifying which compare function to use.
46       * @see org.mmbase.util.CompareInterface
47       */
48      public SortedVector(CompareInterface cmp) {
49          super();
50          this.cmp=cmp;
51      }
52  
53      /**
54       * Store an object in its right location.
55       * This will do a linear insert until 16 elements and
56       * than switch over to binary insert.
57       */
58      public void addSorted(Object   newObject) {
59          // No compare set at creation so it must be strings
60          if (cmp==null) cmp=stringcmp;
61          if (size()>16) { // Turnaround in code is around 16 elements
62              addBinSorted(newObject);
63          } else {
64              addLinSorted(newObject);
65          }
66      }
67  
68      /**
69       * Store an object in its right location.
70       * This will do a linear insert until 16 elements and
71       * than switch over to binary insert.
72       */
73      public void addSorted(Sortable newObject) {
74          if (cmp==null) cmp=sortcmp;
75          if (size()>16) { // Turnaround in code is around 16 elements
76              addBinSorted(newObject);
77          } else {
78              addLinSorted(newObject);
79          }
80      }
81  
82      /**
83       * Store an object in its right location, search for the location
84       * the binary (smart) way and only insert it if it's not in the Vector yet.
85       */
86      public void addUniqueSorted(Object   newObject) {
87          int low,med,high,which=0;
88          boolean done;
89  
90          med=0;
91          done=false;
92          Object   other;
93  
94          for (low=0,high=size()-1;low<=high && !done; ) {
95              med=(low+high)/2;
96              other=elementAt(med);
97              which=cmp.compare(newObject,other);
98              if (which<0) {
99                  high=med-1;
100             } else if (which>0) {
101                 low=med+1;
102                 med=low;
103             } else {
104                 done=true;
105             }
106         }
107         if (!done)
108             insertElementAt(newObject,med);
109     }
110 
111     /**
112      * Store an object in its right location, search for the location
113      * the linear (stupid) way.
114      */
115     public void addLinSorted(Object   newObject) {
116         Enumeration   e = elements();
117         boolean done = false;
118         int i = 0;
119 
120         Object   other;
121 
122         while (e.hasMoreElements() && !done) { // While more elements and not done
123             other = e.nextElement();
124             if (cmp.compare(newObject,other)<0) {    //insert newObject before other
125                 insertElementAt(newObject,i);
126                 done = true;
127             }
128             i++;
129         }
130         if (!done) {
131             addElement(newObject);
132         }
133     }
134 
135     /**
136      * Store an object in its right location, search for the location
137      * the binary (smart) way.
138      */
139     public void addBinSorted(Object   newObject) {
140         int low,med,high,which=0;
141         boolean done;
142 
143         med=0;
144         done=false;
145         Object   other;
146 
147         for (low=0,high=size()-1;low<=high && !done; ) {
148             med=(low+high)/2;
149             other=elementAt(med);
150             which=cmp.compare(newObject,other);
151             if (which<0) {
152                 high=med-1;
153             } else if (which>0) {
154                 low=med+1;
155                 med=low;
156             } else {
157                 done=true;
158             }
159         }
160         insertElementAt(newObject,med);
161     }
162 
163     /**
164      * See if an object is in the SortedVector
165      * This should be contains(Object) but that one is final.
166      * @see java.util.Vector
167      */
168     public boolean has(Object   newObject) {
169         return find(newObject)>=0;
170     }
171 
172     /**
173      * Find an object in the SortedVector.
174      * This uses binary search. As usual this should be a overide
175      * of an existing method but that one is final.
176      * In this case indexOf(Object,int) in Vector.
177      * @see java.util.Vector
178      */
179     public int find(Object   newObject) {
180         int low,med,high,which=0;
181         boolean done;
182 
183         med=0;
184         done=false;
185         Object   other;
186 
187         for (low=0,high=size()-1;low<=high && !done; ) {
188             med=(low+high)/2;
189             other=elementAt(med);
190             which=cmp.compare(newObject,other);
191             if (which<0) {
192                 high=med-1;
193             } else if (which>0) {
194                 low=med+1;
195                 med=low;
196             } else {
197                 done=true;
198             }
199         }
200         if (done) return med;
201         else return -1;
202     }
203 
204     /**
205      * Change the compare function the SortedVector should use.
206      * This forces a (re)sort of the data.
207      */
208     public void setCompare(CompareInterface cmp) {
209         this.cmp=cmp;
210         Sort();
211     }
212 
213     /**
214      * Sort the SortedVector
215      */
216     public void Sort() {
217         if (size()>1) {
218             if (cmp==null) {
219                 if (firstElement() instanceof String  ) {
220                     cmp=stringcmp;
221                 } else {
222                     cmp=sortcmp;
223                 }
224             }
225             qsortCompare(0,size()-1);
226         }
227     }
228 
229     /**
230      * The actual sort routine, this is just plain old qsort.
231      */
232     private void qsortCompare(int first,int last ) {
233         Object   x;
234         int left=first+1;
235         int right=last;
236 
237 
238         if (last-first+1<2) return;
239         loop:
240         while(left<right) {
241             while(cmp.compare(elementAt(left),elementAt(first))<=0) {
242                 left++;
243                 if (left>=right) break loop;
244             }
245             while(cmp.compare(elementAt(right),elementAt(first))>0) {
246                 right--;
247                 if (left>=right) break loop;
248             }
249             /* Swap */
250             x=elementAt(left);
251             setElementAt(elementAt(right),left);
252             setElementAt(x,right);
253             left++;
254         }
255         if (cmp.compare(elementAt(first),elementAt(left))<0) {
256             left--;
257         }
258         x=elementAt(left);
259         setElementAt(elementAt(first),left);
260         setElementAt(x,first);
261         qsortCompare(first,left-1);
262         qsortCompare(left+1,last);
263     }
264 
265     /**
266      * Sort a Vector and return a SortedVector.
267      * Note: You should make sure it are Strings or Sortables,
268      * otherwise use SortVector(Vector,CompareInterface) to specify
269      * the interface
270      */
271     public static SortedVector SortVector(Vector   vec) {
272         SortedVector newvec=new SortedVector();
273 
274         for (Enumeration   e=vec.elements();e.hasMoreElements();) {
275             newvec.addElement(e.nextElement());
276         }
277         newvec.Sort();
278         return newvec;
279     }
280 
281     /**
282      * Sort a Vector and return a SortedVector using the specified compare
283      * function.
284      */
285     public static SortedVector SortVector(Vector   vec,CompareInterface cmpI) {
286         SortedVector newvec=new SortedVector(cmpI);
287 
288         for (Enumeration   e=vec.elements();e.hasMoreElements();) {
289             newvec.addElement(e.nextElement());
290         }
291         newvec.Sort();
292         return newvec;
293     }
294 
295     /**
296      * Test the class
297      */
298     public static void main(String   args[]) {
299         SortedVector v;
300         Vector   vec=new Vector  ();
301         StringCompare strc=new StringCompare();
302 
303         /* Binary insert test */
304         v=new SortedVector(strc);
305         for (int i=0;i<args.length;i++) {
306             v.addBinSorted(args[i]);
307             log.info("V "+v);
308         }
309         /* See if find works */
310         log.info("Element "+args[0]+" at "+v.find(args[0])+" : "+v.has(args[0]));
311 
312         /* Normal String Qsort test */
313         for (int i=0;i<args.length;i++) {
314             vec.addElement(args[i]);
315         }
316         log.info("V1 "+vec);
317         log.info("V2 "+SortVector(vec));
318 
319 
320         /* Qsort test through compare function */
321         v=new SortedVector(strc);
322         for (int i=0;i<args.length;i++) {
323             v.addElement(args[i]);
324         }
325         log.info("V1 "+vec);
326         log.info("V2 "+SortVector(vec));
327     }
328 
329 }
330
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags