1 /*
   2  * Copyright (c) 1997, 2015, 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 jdk.test.lib.hprof.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 }