VectorSorter.java revision 2224:2a8815d86b93 
1/*
2 * Copyright (c) 1997, 2016, 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
33package jdk.test.lib.hprof.util;
34import 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
54public 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}
149