Sort


1   // HTMLParser Library $Name: v1_5_20050313 $ - A java-based parser for HTML
2   // http://sourceforge.org/projects/htmlparser
3   // Copyright (C) 2004 Derrick Oswald
4   //
5   // Revision Control Information
6   //
7   // $Source: /cvsroot/htmlparser/htmlparser/src/org/htmlparser/util/sort/Sort.java,v $
8   // $Author: derrickoswald $
9   // $Date: 2004/01/14 02:53:47 $
10  // $Revision: 1.12 $
11  //
12  // This library is free software; you can redistribute it and/or
13  // modify it under the terms of the GNU Lesser General Public
14  // License as published by the Free Software Foundation; either
15  // version 2.1 of the License, or (at your option) any later version.
16  //
17  // This library is distributed in the hope that it will be useful,
18  // but WITHOUT ANY WARRANTY; without even the implied warranty of
19  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20  // Lesser General Public License for more details.
21  //
22  // You should have received a copy of the GNU Lesser General Public
23  // License along with this library; if not, write to the Free Software
24  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25  //
26  
27  package org.htmlparser.util.sort;
28  
29  import java.util.*;
30  
31  /**
32   * A quick sort algorithm to sort Vectors or arrays.
33   * Provides sort and binary search capabilities.
34   *<p>
35   * This all goes away in JDK 1.2.
36   * <p>
37   * @author James Gosling
38   * @author Kevin A. Smith
39   * @author Derrick Oswald
40   * @version 1.4, 11 June, 1997
41   */
42  public class Sort
43  {
44      /**
45       * No object of this class need ever be instantiated.
46       * All methods are static.
47       */
48      private Sort ()
49      {
50      }
51  
52      /**
53       * This is a generic version of C.A.R Hoare's Quick Sort algorithm.
54       * This will handle vectors that are already
55       * sorted, and vectors with duplicate keys.
56       * Equivalent to:
57       * <pre>
58       * QuickSort (v, 0, v.size () - 1);
59       * </pre>
60       * @param v A <code>Vector</code> of <code>Ordered</code> items.
61       * @exception ClassCastException If the vector contains objects that
62       * are not <code>Ordered</code>.
63       */
64      public static void QuickSort (Vector v) throws ClassCastException  
65      {
66          QuickSort (v, 0, v.size () - 1);
67      }
68  
69      /**
70       * This is a generic version of C.A.R Hoare's Quick Sort algorithm.
71       * This will handle vectors that are already
72       * sorted, and vectors with duplicate keys.
73       * <p>
74       * If you think of a one dimensional vector as going from
75       * the lowest index on the left to the highest index on the right
76       * then the parameters to this function are lowest index or
77       * left and highest index or right.
78       * @param v A <code>Vector</code> of <code>Ordered</code> items.
79       * @param lo0 Left boundary of vector partition.
80       * @param hi0 Right boundary of vector partition.
81       * @exception ClassCastException If the vector contains objects that
82       * are not <code>Ordered</code>.
83       */
84      public static void QuickSort (Vector v, int lo0, int hi0) throws ClassCastException  
85      {
86          int lo = lo0;
87          int hi = hi0;
88          Ordered mid;
89  
90          if ( hi0 > lo0)
91          {   // arbitrarily establish partition element as the midpoint of the vector
92              mid = (Ordered)v.elementAt((lo0 + hi0) / 2);
93  
94              // loop through the vector until indices cross
95              while (lo <= hi)
96              {
97                  // find the first element that is greater than or equal to
98                  // the partition element starting from the left index
99                  while ((lo < hi0) && (0 > ((Ordered)v.elementAt (lo)).compare (mid)))
100                     ++lo;
101 
102                 // find an element that is smaller than or equal to
103                 // the partition element starting from the right index
104                 while ((hi > lo0) && (0 < ((Ordered)v.elementAt (hi)).compare (mid)))
105                     --hi;
106 
107                 // if the indexes have not crossed, swap
108                 if (lo <= hi)
109                     swap (v, lo++, hi--);
110             }
111 
112             // if the right index has not reached the left side of array
113             // must now sort the left partition
114             if (lo0 < hi)
115                 QuickSort (v, lo0, hi);
116 
117             // if the left index has not reached the right side of array
118             // must now sort the right partition
119             if (lo < hi0)
120                 QuickSort (v, lo, hi0);
121         }
122     }
123 
124     private static void swap (Vector v, int i, int j)
125     {
126         Object   o;
127 
128         o = v.elementAt (i);
129         v.setElementAt (v.elementAt (j), i);
130         v.setElementAt (o, j);
131     }
132 
133     /**
134      * This is a generic version of C.A.R Hoare's Quick Sort algorithm.
135      * This will handle arrays that are already sorted,
136      * and arrays with duplicate keys.
137      * <p>
138      * Equivalent to:
139      * <pre>
140      * QuickSort (a, 0, a.length - 1);
141      * </pre>
142      * @param a An array of <code>Ordered</code> items.
143      */
144     public static void QuickSort (Ordered[] a)
145     {
146         QuickSort (a, 0, a.length - 1);
147     }
148 
149     /**
150      * This is a generic version of C.A.R Hoare's Quick Sort algorithm.
151      * This will handle arrays that are already sorted,
152      * and arrays with duplicate keys.
153      * <p>
154      * If you think of a one dimensional array as going from
155      * the lowest index on the left to the highest index on the right
156      * then the parameters to this function are lowest index or
157      * left and highest index or right.
158      * @param a An array of <code>Ordered</code> items.
159      * @param lo0 Left boundary of array partition.
160      * @param hi0 Right boundary of array partition.
161      */
162     public static void QuickSort (Ordered[] a, int lo0, int hi0)
163     {
164         int lo = lo0;
165         int hi = hi0;
166         Ordered mid;
167 
168         if ( hi0 > lo0)
169         {
170             // arbitrarily establish partition element as the midpoint of the array
171             mid = a[(lo0 + hi0) / 2];
172 
173             // loop through the vector until indices cross
174             while (lo <= hi)
175             {
176                 // find the first element that is greater than or equal to
177                 // the partition element starting from the left index
178                 while ((lo < hi0) && (0 > a[lo].compare (mid)))
179                     ++lo;
180 
181                 // find an element that is smaller than or equal to
182                 // the partition element starting from the right Index.
183                 while ((hi > lo0) && (0 < a[hi].compare (mid)))
184                     --hi;
185 
186                 // if the indexes have not crossed, swap
187                 if (lo <= hi)
188                     swap (a, lo++, hi--);
189             }
190 
191             // if the right index has not reached the left side of array
192             // must now sort the left partition
193             if (lo0 < hi)
194                 QuickSort (a, lo0, hi);
195 
196             // if the left index has not reached the right side of array
197             // must now sort the right partition
198             if (lo < hi0)
199                 QuickSort (a, lo, hi0);
200         }
201     }
202 
203     /**
204      * Swaps two elements of an array.
205      * @param a The array of elements.
206      * @param i The index of one item to swap.
207      * @param j The index of the other item to swap.
208      */
209     private static void swap (Object  [] a, int i, int j)
210     {
211         Object   o;
212         o = a[i];
213         a[i] = a[j];
214         a[j] = o;
215     }
216 
217     /**
218      * This is a string version of C.A.R Hoare's Quick Sort algorithm.
219      * This will handle arrays that are already sorted,
220      * and arrays with duplicate keys.
221      * <p>
222      * Equivalent to:
223      * <pre>
224      * QuickSort (a, 0, a.length - 1);
225      * </pre>
226      * @param a An array of <code>String</code> items.
227      */
228     public static void QuickSort (String  [] a)
229     {
230         QuickSort (a, 0, a.length - 1);
231     }
232 
233     /**
234      * This is a string version of C.A.R Hoare's Quick Sort algorithm.
235      * This will handle arrays that are already sorted,
236      * and arrays with duplicate keys.
237      * <p>
238      * If you think of a one dimensional array as going from
239      * the lowest index on the left to the highest index on the right
240      * then the parameters to this function are lowest index or
241      * left and highest index or right.
242      * @param a An array of <code>String</code> items.
243      * @param lo0 Left boundary of array partition.
244      * @param hi0 Right boundary of array partition.
245      */
246     public static void QuickSort (String  [] a, int lo0, int hi0)
247     {
248         int lo = lo0;
249         int hi = hi0;
250         String   mid;
251 
252         if ( hi0 > lo0)
253         {
254             // arbitrarily establish partition element as the midpoint of the array
255             mid = a[(lo0 + hi0) / 2];
256 
257             // loop through the vector until indices cross
258             while (lo <= hi)
259             {
260                 // find the first element that is greater than or equal to
261                 // the partition element starting from the left index
262                 while ((lo < hi0) && (0 > a[lo].compareTo (mid)))
263                     ++lo;
264 
265                 // find an element that is smaller than or equal to
266                 // the partition element starting from the right Index.
267                 while ((hi > lo0) && (0 < a[hi].compareTo (mid)))
268                     --hi;
269 
270                 // if the indexes have not crossed, swap
271                 if (lo <= hi)
272                     swap (a, lo++, hi--);
273             }
274 
275             // if the right index has not reached the left side of array
276             // must now sort the left partition
277             if (lo0 < hi)
278                 QuickSort (a, lo0, hi);
279 
280             // if the left index has not reached the right side of array
281             // must now sort the right partition
282             if (lo < hi0)
283                 QuickSort (a, lo, hi0);
284         }
285     }
286 
287     /**
288      * This is a generic version of C.A.R Hoare's Quick Sort algorithm.
289      * This will handle Sortable objects that are already
290      * sorted, and Sortable objects with duplicate keys.
291      * <p>
292      * @param sortable A <code>Sortable</code> object.
293      * @param lo0 Left boundary of partition.
294      * @param hi0 Right boundary of partition.
295      */
296     public static void QuickSort (Sortable sortable, int lo0, int hi0)
297     {
298         int lo = lo0;
299         int hi = hi0;
300         Ordered mid;
301         Ordered test;
302 
303         if ( hi0 > lo0)
304         {   // arbitrarily establish partition element as the midpoint of the vector
305             mid = sortable.fetch ((lo0 + hi0) / 2, null);
306             test = null;
307 
308             // loop through the vector until indices cross
309             while (lo <= hi)
310             {
311                 // find the first element that is greater than or equal to
312                 // the partition element starting from the left index
313                 while ((lo < hi0) && (0 > (test = sortable.fetch (lo, test)).compare (mid)))
314                     ++lo;
315 
316                 // find an element that is smaller than or equal to
317                 // the partition element starting from the right index
318                 while ((hi > lo0) && (0 < (test = sortable.fetch (hi, test)).compare (mid)))
319                     --hi;
320 
321                 // if the indexes have not crossed, swap
322                 if (lo <= hi)
323                     sortable.swap (lo++, hi--);
324             }
325 
326             // if the right index has not reached the left side of array
327             // must now sort the left partition
328             if (lo0 < hi)
329                 QuickSort (sortable, lo0, hi);
330 
331             // if the left index has not reached the right side of array
332             // must now sort the right partition
333             if (lo < hi0)
334                 QuickSort (sortable, lo, hi0);
335         }
336     }
337 
338     /**
339      * This is a generic version of C.A.R Hoare's Quick Sort algorithm.
340      * This will handle Sortable objects that are already
341      * sorted, and Sortable objects with duplicate keys.
342      * <p>
343      * Equivalent to:
344      * <pre>
345      * QuickSort (sortable, sortable.first (), sortable.last ());
346      * </pre>
347      * @param sortable A <code>Sortable</code> object.
348      */
349     public static void QuickSort (Sortable sortable)
350     {
351         QuickSort (sortable, sortable.first (), sortable.last ());
352     }
353 
354     /**
355      * Sort a Hashtable.
356      * @param h A Hashtable with String or Ordered keys.
357      * @return A sorted array of the keys.
358      * @exception ClassCastException If the keys of the hashtable
359      * are not <code>Ordered</code>.
360      */
361     public static Object  [] QuickSort (Hashtable h) throws ClassCastException  
362     {
363         Enumeration e;
364         boolean are_strings;
365         Object  [] ret;
366 
367         // make the array
368         ret = new Ordered[h.size ()];
369         e = h.keys ();
370         are_strings = true; // until proven otherwise
371         for (int i = 0; i < ret.length; i++)
372         {
373             ret[i] = e.nextElement ();
374             if (are_strings && !(ret[i] instanceof String  ))
375                 are_strings = false;
376         }
377 
378         // sort it
379         if (are_strings)
380             QuickSort ((String  [])ret);
381         else
382             QuickSort ((Ordered[])ret);
383 
384         return (ret);
385     }
386 
387     /**
388      * Binary search for an object
389      * @param set The collection of <code>Ordered</code> objects.
390      * @param ref The name to search for.
391      * @param lo The lower index within which to look.
392      * @param hi The upper index within which to look.
393      * @return The index at which reference was found or is to be inserted.
394      */
395     public static int bsearch (Sortable set, Ordered ref, int lo, int hi)
396     {   int num;
397         int mid;
398         Ordered ordered;
399         int half;
400         int result;
401         int ret;
402 
403         ret = -1;
404 
405         num = (hi - lo) + 1;
406         ordered = null;
407         while ((-1 == ret) && (lo <= hi))
408         {
409             half = num / 2;
410             mid = lo + ((0 != (num & 1)) ? half : half - 1);
411             ordered = set.fetch (mid, ordered);
412             result = ref.compare (ordered);
413             if (0 == result)
414                 ret = mid;
415             else if (0 > result)
416             {
417                 hi = mid - 1;
418                 num = ((0 != (num & 1)) ? half : half - 1);
419             }
420             else
421             {
422                 lo = mid + 1;
423                 num = half;
424             }
425         }
426         if (-1 == ret)
427             ret = lo;
428 
429         return (ret);
430     }
431 
432     /**
433      * Binary search for an object
434      * @param set The collection of <code>Ordered</code> objects.
435      * @param ref The name to search for.
436      * @return The index at which reference was found or is to be inserted.
437      */
438     public static int bsearch (Sortable set, Ordered ref)
439     {
440         return (bsearch (set, ref, set.first (), set.last ()));
441     }
442 
443     /**
444      * Binary search for an object
445      * @param vector The vector of <code>Ordered</code> objects.
446      * @param ref The name to search for.
447      * @param lo The lower index within which to look.
448      * @param hi The upper index within which to look.
449      * @return The index at which reference was found or is to be inserted.
450      */
451     public static int bsearch (Vector vector, Ordered ref, int lo, int hi)
452     {   int num;
453         int mid;
454         int half;
455         int result;
456         int ret;
457 
458         ret = -1;
459 
460         num = (hi - lo) + 1;
461         while ((-1 == ret) && (lo <= hi))
462         {
463             half = num / 2;
464             mid = lo + ((0 != (num & 1)) ? half : half - 1);
465             result = ref.compare (vector.elementAt (mid));
466             if (0 == result)
467                 ret = mid;
468             else if (0 > result)
469             {
470                 hi = mid - 1;
471                 num = ((0 != (num & 1)) ? half : half - 1);
472             }
473             else
474             {
475                 lo = mid + 1;
476                 num = half;
477             }
478         }
479         if (-1 == ret)
480             ret = lo;
481 
482         return (ret);
483     }
484 
485     /**
486      * Binary search for an object
487      * @param vector The vector of <code>Ordered</code> objects.
488      * @param ref The name to search for.
489      * @return The index at which reference was found or is to be inserted.
490      */
491     public static int bsearch (Vector vector, Ordered ref)
492     {
493         return (bsearch (vector, ref, 0, vector.size () - 1));
494     }
495 
496     /**
497      * Binary search for an object
498      * @param array The array of <code>Ordered</code> objects.
499      * @param ref The name to search for.
500      * @param lo The lower index within which to look.
501      * @param hi The upper index within which to look.
502      * @return The index at which reference was found or is to be inserted.
503      */
504     public static int bsearch (Ordered[] array, Ordered ref, int lo, int hi)
505     {   int num;
506         int mid;
507         int half;
508         int result;
509         int ret;
510 
511         ret = -1;
512 
513         num = (hi - lo) + 1;
514         while ((-1 == ret) && (lo <= hi))
515         {
516             half = num / 2;
517             mid = lo + ((0 != (num & 1)) ? half : half - 1);
518             result = ref.compare (array[mid]);
519             if (0 == result)
520                 ret = mid;
521             else if (0 > result)
522             {
523                 hi = mid - 1;
524                 num = ((0 != (num & 1)) ? half : half - 1);
525             }
526             else
527             {
528                 lo = mid + 1;
529                 num = half;
530             }
531         }
532         if (-1 == ret)
533             ret = lo;
534 
535         return (ret);
536     }
537 
538     /**
539      * Binary search for an object
540      * @param array The array of <code>Ordered</code> objects.
541      * @param ref The name to search for.
542      * @return The index at which reference was found or is to be inserted.
543      */
544     public static int bsearch (Ordered[] array, Ordered ref)
545     {
546         return (bsearch (array, ref, 0, array.length - 1));
547     }
548 }
549 
550
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags