View Javadoc
1   /*
2    * Copyright (c) 1997, 2008, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  
27  /*
28   * The Original Code is HAT. The Initial Developer of the
29   * Original Code is Bill Foote, with contributions from others
30   * at JavaSoft/Sun.
31   */
32  
33  package com.sun.tools.hat.internal.util;
34  import java.util.*;
35  
36  /**
37   * A singleton utility class that sorts a vector.
38   * <p>
39   * Use:
40   * <pre>
41   *
42   *  Vector v =   <a vector of, say, String objects>;
43   *  VectorSorter.sort(v, new Comparer() {
44   *      public int compare(Object lhs, Object rhs) {
45   *          return ((String) lhs).compareTo((String) rhs);
46   *      }
47   *  });
48   * </pre>
49   *
50   * @author      Bill Foote
51   */
52  
53  
54  public class VectorSorter {
55  
56      /**
57       * Sort the given vector, using c for comparison
58      **/
59      static public void sort(Vector<Object> v, Comparer c)  {
60          quickSort(v, c, 0, v.size()-1);
61      }
62  
63  
64      /**
65       * Sort a vector of strings, using String.compareTo()
66      **/
67      static public void sortVectorOfStrings(Vector<Object> v) {
68          sort(v, new Comparer() {
69              public int compare(Object lhs, Object rhs) {
70                  return ((String) lhs).compareTo((String) rhs);
71              }
72          });
73      }
74  
75  
76      static private void swap(Vector<Object> v, int a, int b) {
77          Object tmp = v.elementAt(a);
78          v.setElementAt(v.elementAt(b), a);
79          v.setElementAt(tmp, b);
80      }
81  
82      //
83      // Sorts v between from and to, inclusive.  This is a quick, off-the-top-
84      // of-my-head quicksort:  I haven't put any thought into optimizing it.
85      // I _did_ put thought into making sure it's safe (it will always
86      // terminate).  Worst-case it's O(n^2), but it will usually run in
87      // in O(n log n).  It's well-behaved if the list is already sorted,
88      // or nearly so.
89      //
90      static private void quickSort(Vector<Object> v, Comparer c, int from, int to) {
91          if (to <= from)
92              return;
93          int mid = (from + to) / 2;
94          if (mid != from)
95              swap(v, mid, from);
96          Object pivot = v.elementAt(from);
97                          // Simple-minded, but reasonable
98          int highestBelowPivot = from - 1;
99          int low = from+1;
100         int high = to;
101             // We now move low and high toward eachother, maintaining the
102             // invariants:
103             //      v[i] <= pivot    for all i < low
104             //      v[i] > pivot     for all i > high
105             // As long as these invariants hold, and every iteration makes
106             // progress, we are safe.
107         while (low <= high) {
108             int cmp = c.compare(v.elementAt(low), pivot);
109             if (cmp <= 0) {    // v[low] <= pivot
110                 if (cmp < 0) {
111                     highestBelowPivot = low;
112                 }
113                 low++;
114             } else {
115                 int c2;
116                 for (;;) {
117                     c2 = c.compare(v.elementAt(high), pivot);
118                         // v[high] > pivot:
119                     if (c2 > 0) {
120                         high--;
121                         if (low > high) {
122                             break;
123                         }
124                     } else {
125                         break;
126                     }
127                 }
128                 // At this point, low is never == high
129                 if (low <= high) {
130                     swap(v, low, high);
131                     if (c2 < 0) {
132                         highestBelowPivot = low;
133                     }
134                     low++;
135                     high--;
136                 }
137             }
138         }
139         // Now we just need to sort from from..highestBelowPivot
140         // and from high+1..to
141         if (highestBelowPivot > from) {
142             // pivot == pivot, so ensure algorithm terminates
143             swap(v, from, highestBelowPivot);
144             quickSort(v, c, from, highestBelowPivot-1);
145         }
146         quickSort(v, c, high+1, to);
147     }
148 }