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 an array of objects. 38 * <p> 39 * Use: 40 * <pre> 41 * 42 * Stuff[] arr = ...; 43 * ArraySorter.sort(arr, 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 public class ArraySorter { 54 55 /** 56 * Sort the given array, using c for comparison 57 **/ 58 static public void sort(Object[] arr, Comparer c) { 59 quickSort(arr, c, 0, arr.length-1); 60 } 61 62 63 /** 64 * Sort an array of strings, using String.compareTo() 65 **/ 66 static public void sortArrayOfStrings(Object[] arr) { 67 sort(arr, new Comparer() { 68 public int compare(Object lhs, Object rhs) { 69 return ((String) lhs).compareTo((String) rhs); 70 } 71 }); 72 } 73 74 75 static private void swap(Object[] arr, int a, int b) { 76 Object tmp = arr[a]; 77 arr[a] = arr[b]; 78 arr[b] = tmp; 79 } 80 81 // 82 // Sorts arr between from and to, inclusive. This is a quick, off-the-top- 83 // of-my-head quicksort: I haven't put any thought into optimizing it. 84 // I _did_ put thought into making sure it's safe (it will always 85 // terminate). Worst-case it's O(n^2), but it will usually run in 86 // in O(n log n). It's well-behaved if the list is already sorted, 87 // or nearly so. 88 // 89 static private void quickSort(Object[] arr, Comparer c, int from, int to) { 90 if (to <= from) 91 return; 92 int mid = (from + to) / 2; 93 if (mid != from) 94 swap(arr, mid, from); 95 Object pivot = arr[from]; // Simple-minded, but reasonable 96 int highestBelowPivot = from - 1; 97 int low = from+1; 98 int high = to; 99 // We now move low and high toward each other, maintaining the 100 // invariants: 101 // arr[i] <= pivot for all i < low 102 // arr[i] > pivot for all i > high 103 // As long as these invariants hold, and every iteration makes 104 // progress, we are safe. 105 while (low <= high) { 106 int cmp = c.compare(arr[low], pivot); 107 if (cmp <= 0) { // arr[low] <= pivot 108 if (cmp < 0) { 109 highestBelowPivot = low; 110 } 111 low++; 112 } else { 113 int c2; 114 for (;;) { 115 // arr[high] > pivot: 116 c2 = c.compare(arr[high], pivot); 117 if (c2 > 0) { 118 high--; 119 if (low > high) { 120 break; 121 } 122 } else { 123 break; 124 } 125 } 126 // At this point, low is never == high, BTW 127 if (low <= high) { 128 swap(arr, low, high); 129 if (c2 < 0) { 130 highestBelowPivot = low; 131 } 132 low++; 133 high--; 134 } 135 } 136 } 137 // At this point, low == high+1 138 // Now we just need to sort from from..highestBelowPivot 139 // and from high+1..to 140 if (highestBelowPivot > from) { 141 // pivot == pivot, so ensure algorithm terminates 142 swap(arr, from, highestBelowPivot); 143 quickSort(arr, c, from, highestBelowPivot-1); 144 } 145 quickSort(arr, c, high+1, to); 146 } 147 }