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 }