1 /*
2 * $Source$
3 * $Revision$
4 *
5 * Copyright (C) 2000 William Chesters
6 *
7 * Part of Melati (http://melati.org), a framework for the rapid
8 * development of clean, maintainable web applications.
9 *
10 * Melati is free software; Permission is granted to copy, distribute
11 * and/or modify this software under the terms either:
12 *
13 * a) the GNU General Public License as published by the Free Software
14 * Foundation; either version 2 of the License, or (at your option)
15 * any later version,
16 *
17 * or
18 *
19 * b) any version of the Melati Software License, as published
20 * at http://melati.org
21 *
22 * You should have received a copy of the GNU General Public License and
23 * the Melati Software License along with this program;
24 * if not, write to the Free Software Foundation, Inc.,
25 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA to obtain the
26 * GNU General Public License and visit http://melati.org to obtain the
27 * Melati Software License.
28 *
29 * Feel free to contact the Developers of Melati (http://melati.org),
30 * if you would like to work out a different arrangement than the options
31 * outlined here. It is our intention to allow Melati to be used by as
32 * wide an audience as possible.
33 *
34 * This program is distributed in the hope that it will be useful,
35 * but WITHOUT ANY WARRANTY; without even the implied warranty of
36 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
37 * GNU General Public License for more details.
38 *
39 * Contact details for copyright holder:
40 *
41 * William Chesters <williamc At paneris.org>
42 * http://paneris.org/~williamc
43 * Obrechtstraat 114, 2517VX Den Haag, The Netherlands
44 */
45
46 package org.melati.poem.util;
47
48 import java.util.Vector;
49 import java.util.Enumeration;
50
51 /**
52 * An assortment of useful sorting operations.
53 */
54 public final class SortUtils {
55
56 private SortUtils() {}
57
58 /**
59 * Swap two elements of an Array.
60 * @param arr the Array
61 * @param i will become j
62 * @param j will become i
63 */
64 public static void swap(Object[] arr, int i, int j) {
65 Object t = arr[i];
66 arr[i] = arr[j];
67 arr[j] = t;
68 }
69
70 /**
71 * Sort an Array by a supplied ordering.
72 * @param cmp an ordering
73 * @param arr the Array to sort
74 */
75 public static void insertionSort(Order cmp, Object[] arr) {
76 for (int i = 1; i < arr.length; ++i) {
77 Object val_i = arr[i];
78 if (!cmp.lessOrEqual(arr[i-1], val_i)) {
79 int j = i - 1;
80 arr[i] = arr[j];
81 while (j >= 1 && !cmp.lessOrEqual(arr[j-1], val_i)) {
82 arr[j] = arr[j-1];
83 --j;
84 }
85 arr[j] = val_i;
86 }
87 }
88 }
89
90 /**
91 * This is nicked from ocaml 2.03's Sort.array, in turn derived from
92 * Sedgewick. ocaml is a superb object/functional language from INRIA:
93 * see http://caml.inria.fr/ .
94 */
95 private static void partlyQSort(Order cmp, Object[] arr, int lo, int hi) {
96 if (hi - lo >= 6) {
97 int mid = (lo + hi) >> 1;
98
99 /* Select median value from among LO, MID, and HI. Rearrange
100 LO and HI so the three values are sorted. This lowers the
101 probability of picking a pathological pivot. It also
102 avoids extra comparisons on i and j in the two tight "while"
103 loops below. */
104
105 if (cmp.lessOrEqual(arr[mid], arr[lo]))
106 swap(arr, mid, lo);
107 if (cmp.lessOrEqual(arr[hi], arr[mid])) {
108 swap(arr, mid, hi);
109 if (cmp.lessOrEqual(arr[mid], arr[lo]))
110 swap(arr, mid, lo);
111 }
112
113 Object pivot = arr[mid];
114 int i = lo + 1;
115 int j = hi - 1;
116 while (i < j) {
117 while (!cmp.lessOrEqual(pivot, arr[i])) ++i;
118 while (!cmp.lessOrEqual(arr[j], pivot)) --j;
119 if (i < j)
120 swap(arr, i, j);
121 ++i;
122 --j;
123 }
124
125 /* Recursion on smaller half, tail-call on larger half */
126
127 if (j - lo <= hi - i) {
128 partlyQSort(cmp, arr, lo, j);
129 partlyQSort(cmp, arr, i, hi);
130 }
131 else {
132 partlyQSort(cmp, arr, i, hi);
133 partlyQSort(cmp, arr, lo, j);
134 }
135 }
136 }
137
138 /**
139 * Quick sort an array.
140 * @param cmp ordering to use
141 * @param arr Array to sort
142 */
143 public static void qsort(Order cmp, Object[] arr) {
144 partlyQSort(cmp, arr, 0, arr.length - 1);
145 /* Finish sorting by insertion sort */
146 insertionSort(cmp, arr);
147 }
148
149 /**
150 * Return a new sorted Array.
151 * @param cmp the ordering
152 * @param arr the Array to sort
153 * @return the sorted Array
154 */
155 public static Object[] sorted(Order cmp, Object[] arr) {
156 Object[] arr2 = (Object[])arr.clone();
157 qsort(cmp, arr2);
158 return arr2;
159 }
160
161 /**
162 * Sort a Vector into a new Array.
163 * @param cmp the ordering
164 * @param v Vector to sort
165 * @return an Array of the sorted Vector's Elements
166 */
167 public static <O> O[] sorted(Order cmp, Vector<O> v) {
168 O[] arr = ArrayUtils.arrayOf(v);
169 qsort(cmp, arr);
170 return arr;
171 }
172
173 /**
174 * Sort an Enumeration into an Array.
175 * @param cmp the ordering
176 * @param e the Enumeration to sort
177 * @return an Array of the sorted Enumeration's Elements
178 */
179 public static <O> O[] sorted(Order cmp, Enumeration<O> e) {
180 return sorted(cmp, EnumUtils.vectorOf(e));
181 }
182
183 }