001: // Sorter.java
002: // $Id: Sorter.java,v 1.8 2007/02/09 22:23:34 ylafon Exp $
003: // (c) COPYRIGHT MIT and INRIA, 1996.
004: // Please first read the full copyright statement in file COPYRIGHT.html
005:
006: package org.w3c.tools.sorter;
007:
008: import java.util.Enumeration;
009: import java.util.Hashtable;
010: import java.util.Vector;
011:
012: import java.io.File;
013:
014: /**
015: * This class implements a bunch of different ways of sorting things.
016: */
017:
018: public class Sorter {
019:
020: private static int compare(File file1, File file2) {
021: if (file1.isDirectory() && file2.isFile())
022: return -1;
023: else if (file1.isFile() && file2.isDirectory())
024: return 1;
025: else
026: return file1.compareTo(file2);
027: }
028:
029: /**
030: * Insert a File into a vector, maintaing the order:<p>
031: * Directory then files in alphabetical order.
032: * @param file The File used to sort.
033: * @param into The target sorted vector.
034: */
035: public static void orderedFileInsert(File file, Vector into) {
036: int lo = 0;
037: int hi = into.size() - 1;
038: int idx = -1;
039: File item = null;
040: int cmp = 0;
041:
042: if (hi >= lo) {
043: while ((hi - lo) > 1) {
044: idx = (hi - lo) / 2 + lo;
045: item = (File) into.elementAt(idx);
046: cmp = compare(item, file);
047: if (cmp == 0) {
048: return;
049: } else if (cmp < 0) {
050: lo = idx;
051: } else if (cmp > 0) {
052: hi = idx;
053: }
054: }
055: switch (hi - lo) {
056: case 0:
057: item = (File) into.elementAt(hi);
058: if (item.equals(file))
059: return;
060: idx = (compare(item, file) < 0) ? hi + 1 : hi;
061: break;
062: case 1:
063: File loitem = (File) into.elementAt(lo);
064: File hiitem = (File) into.elementAt(hi);
065: if (loitem.equals(file))
066: return;
067: if (hiitem.equals(file))
068: return;
069: if (compare(file, loitem) < 0) {
070: idx = lo;
071: } else if (compare(file, hiitem) < 0) {
072: idx = hi;
073: } else {
074: idx = hi + 1;
075: }
076: break;
077: default:
078: throw new RuntimeException("implementation bug.");
079: }
080: }
081: // Add this file to the vector:
082: if (idx < 0)
083: idx = 0;
084: into.insertElementAt(file, idx);
085: return;
086: }
087:
088: /**
089: * Insert a String into a vector, maintaing the order.
090: * @param key The string to insert.
091: * @param into The target sorted vector.
092: */
093:
094: static void orderedStringInsert(String key, Vector into) {
095: int lo = 0;
096: int hi = into.size() - 1;
097: int idx = -1;
098: String item = null;
099: int cmp = 0;
100:
101: if (hi >= lo) {
102: while ((hi - lo) > 1) {
103: idx = (hi - lo) / 2 + lo;
104: item = (String) into.elementAt(idx);
105: cmp = item.compareTo(key);
106: if (cmp == 0) {
107: return;
108: } else if (cmp < 0) {
109: lo = idx;
110: } else if (cmp > 0) {
111: hi = idx;
112: }
113: }
114: switch (hi - lo) {
115: case 0:
116: item = (String) into.elementAt(hi);
117: if (item.equals(key))
118: return;
119: idx = (item.compareTo(key) < 0) ? hi + 1 : hi;
120: break;
121: case 1:
122: String loitem = (String) into.elementAt(lo);
123: String hiitem = (String) into.elementAt(hi);
124: if (loitem.equals(key))
125: return;
126: if (hiitem.equals(key))
127: return;
128: if (key.compareTo(loitem) < 0) {
129: idx = lo;
130: } else if (key.compareTo(hiitem) < 0) {
131: idx = hi;
132: } else {
133: idx = hi + 1;
134: }
135: break;
136: default:
137: throw new RuntimeException("implementation bug.");
138: }
139: }
140: // Add this key to the vector:
141: if (idx < 0)
142: idx = 0;
143: into.insertElementAt(key, idx);
144: return;
145: }
146:
147: /**
148: * Quick sort the given chunk of the array in place.
149: * @param array The array to sort.
150: * @param lo0 The low bound of the chunk of the array to sort.
151: * @param hi0 The high bound of the array to sort.
152: */
153:
154: static void quickSortStringArray(String array[], int lo0, int hi0) {
155: int lo = lo0;
156: int hi = hi0;
157: String mid = null;
158:
159: if (hi0 > lo0) {
160: mid = array[(lo0 + hi0) / 2];
161: while (lo <= hi) {
162: while ((lo < hi0) && (array[lo].compareTo(mid) < 0))
163: ++lo;
164: while ((hi > lo0) && (array[hi].compareTo(mid) > 0))
165: --hi;
166: if (lo <= hi) {
167: String tmp = array[lo];
168: array[lo] = array[hi];
169: array[hi] = tmp;
170: ++lo;
171: --hi;
172: }
173: }
174: if (lo0 < hi)
175: quickSortStringArray(array, lo0, hi);
176: if (lo < hi0)
177: quickSortStringArray(array, lo, hi0);
178: }
179: }
180:
181: /**
182: * Get the keys of this hashtable, sorted.
183: * @param h The hashtable whose String keys are wanted.
184: */
185:
186: public static Vector sortStringKeys(Hashtable h) {
187: return sortStringEnumeration(h.keys());
188: }
189:
190: /**
191: * Sort the given String enumeration.
192: * @return A sorted vector of String.
193: */
194:
195: public static Vector sortStringEnumeration(Enumeration e) {
196: Vector sorted = new Vector();
197: while (e.hasMoreElements()) {
198: orderedStringInsert((String) e.nextElement(), sorted);
199: }
200: sorted.trimToSize();
201: return sorted;
202: }
203:
204: /**
205: * Insert a Comparable into a vector, maintaing the order.
206: * @param key The string to insert.
207: * @param into The target sorted vector.
208: */
209:
210: static void orderedComparableInsert(Comparable key, Vector into) {
211: int lo = 0;
212: int hi = into.size() - 1;
213: int idx = -1;
214: Comparable item = null;
215: int cmp = 0;
216:
217: if (hi >= lo) {
218: while ((hi - lo) > 1) {
219: idx = (hi - lo) / 2 + lo;
220: item = (Comparable) into.elementAt(idx);
221: if (item.greaterThan(key)) {
222: hi = idx;
223: } else {
224: lo = idx;
225: }
226: }
227: switch (hi - lo) {
228: case 0:
229: item = (Comparable) into.elementAt(hi);
230: idx = (item.greaterThan(key)) ? hi : hi + 1;
231: break;
232: case 1:
233: Comparable loitem = (Comparable) into.elementAt(lo);
234: Comparable hiitem = (Comparable) into.elementAt(hi);
235: if (loitem.greaterThan(key)) {
236: idx = lo;
237: } else if (hiitem.greaterThan(key)) {
238: idx = hi;
239: } else {
240: idx = hi + 1;
241: }
242: break;
243: default:
244: throw new RuntimeException("implementation bug.");
245: }
246: }
247: // Add this key to the vector:
248: if (idx < 0)
249: idx = 0;
250: into.insertElementAt(key, idx);
251: return;
252: }
253:
254: /**
255: * Get the keys of this hashtable, sorted.
256: * @param h The hashtable whose Comparable keys are wanted.
257: */
258:
259: public static Vector sortComparableKeys(Hashtable h) {
260: return sortComparableEnumeration(h.keys());
261: }
262:
263: /**
264: * Sort the given Comparable enumeration.
265: * @return A sorted vector of Comparable instance.
266: */
267:
268: public static Vector sortComparableEnumeration(Enumeration e) {
269: Vector sorted = new Vector();
270: while (e.hasMoreElements()) {
271: orderedComparableInsert((Comparable) e.nextElement(),
272: sorted);
273: }
274: sorted.trimToSize();
275: return sorted;
276: }
277:
278: /**
279: * Sort the given String array in place.
280: * @param array The array of String to sort.
281: * @param inplace Sort the array in place if <strong>true</strong>,
282: * allocate a fresh array for the result otherwise.
283: * @return The same array, with string sorted.
284: */
285:
286: public static String[] sortStringArray(String array[],
287: boolean inplace) {
288: String tosort[] = array;
289: if (!inplace) {
290: tosort = new String[array.length];
291: System.arraycopy(array, 0, tosort, 0, array.length);
292: }
293: quickSortStringArray(tosort, 0, tosort.length - 1);
294: return tosort;
295: }
296:
297: /**
298: * Quick sort the given chunk of the array in place.
299: * @param array The array to sort.
300: * @param lo0 The low bound of the chunk of the array to sort.
301: * @param hi0 The high bound of the array to sort.
302: */
303:
304: static void quickSortCompArray(Comparable array[], int lo0, int hi0) {
305: int lo = lo0;
306: int hi = hi0;
307: Comparable mid = null;
308:
309: if (hi0 > lo0) {
310: mid = array[(lo0 + hi0) / 2];
311: while (lo <= hi) {
312: while ((lo < hi0) && (mid.greaterThan(array[lo])))
313: ++lo;
314: while ((hi > lo0) && (array[hi].greaterThan(mid)))
315: --hi;
316: if (lo <= hi) {
317: Comparable tmp = array[lo];
318: array[lo] = array[hi];
319: array[hi] = tmp;
320: ++lo;
321: --hi;
322: }
323: }
324: if (lo0 < hi)
325: quickSortCompArray(array, lo0, hi);
326: if (lo < hi0)
327: quickSortCompArray(array, lo, hi0);
328: }
329: }
330:
331: public static Comparable[] sortComparableArray(Comparable array[],
332: boolean inplace) {
333: Comparable tosort[] = array;
334: if (!inplace) {
335: tosort = new Comparable[array.length];
336: System.arraycopy(array, 0, tosort, 0, array.length);
337: }
338: quickSortCompArray(tosort, 0, tosort.length - 1);
339: return tosort;
340: }
341:
342: }
|