01: /*******************************************************************************
02: * Copyright (c) 2002, 2006 IBM Corporation and others.
03: * All rights reserved. This program and the accompanying materials
04: * are made available under the terms of the Eclipse Public License v1.0
05: * which accompanies this distribution, and is available at
06: * http://www.eclipse.org/legal/epl-v10.html
07: *
08: * Contributors:
09: * IBM Corporation - initial API and implementation
10: *******************************************************************************/package org.eclipse.ui.internal.cheatsheets.registry;
11:
12: /**
13: * The SortOperation takes a collection of objects and returns
14: * a sorted collection of these objects. Concrete instances of this
15: * class provide the criteria for the sorting of the objects based on
16: * the type of the objects.
17: */
18: public abstract class Sorter {
19: /**
20: * Returns true if elementTwo is 'greater than' elementOne
21: * This is the 'ordering' method of the sort operation.
22: * Each subclass overides this method with the particular
23: * implementation of the 'greater than' concept for the
24: * objects being sorted.
25: */
26: /*package*/abstract boolean compare(Object elementOne,
27: Object elementTwo);
28:
29: /**
30: * Sort the objects in sorted collection and return that collection.
31: */
32: private Object[] quickSort(Object[] sortedCollection, int left,
33: int right) {
34: int originalLeft = left;
35: int originalRight = right;
36: Object mid = sortedCollection[(left + right) / 2];
37:
38: do {
39: while (compare(sortedCollection[left], mid))
40: left++;
41: while (compare(mid, sortedCollection[right]))
42: right--;
43: if (left <= right) {
44: Object tmp = sortedCollection[left];
45: sortedCollection[left] = sortedCollection[right];
46: sortedCollection[right] = tmp;
47: left++;
48: right--;
49: }
50: } while (left <= right);
51:
52: if (originalLeft < right)
53: sortedCollection = quickSort(sortedCollection,
54: originalLeft, right);
55: if (left < originalRight)
56: sortedCollection = quickSort(sortedCollection, left,
57: originalRight);
58:
59: return sortedCollection;
60: }
61:
62: /**
63: * Return a new sorted collection from this unsorted collection.
64: * Sort using quick sort.
65: */
66: /*package*/Object[] sort(Object[] unSortedCollection) {
67: int size = unSortedCollection.length;
68: Object[] sortedCollection = new Object[size];
69:
70: //copy the array so can return a new sorted collection
71: System.arraycopy(unSortedCollection, 0, sortedCollection, 0,
72: size);
73: if (size > 1)
74: quickSort(sortedCollection, 0, size - 1);
75:
76: return sortedCollection;
77: }
78: }
|