86db922454028b771e93904e4288a51c4af2b2ff
[phpeclipse.git] / net.sourceforge.phpeclipse.ui / src / net / sourceforge / phpdt / internal / ui / util / TwoArrayQuickSorter.java
1 package net.sourceforge.phpdt.internal.ui.util;
2
3 import java.util.Comparator;
4
5 import org.eclipse.jface.util.Assert;
6
7 /**
8  * Quick sort to sort key-value pairs. The keys and arrays are specified in
9  * separate arrays.
10  */
11 public class TwoArrayQuickSorter {
12
13         private Comparator fComparator;
14
15         /**
16          * Default comparator.
17          */
18         public static final class StringComparator implements Comparator {
19                 private boolean fIgnoreCase;
20
21                 StringComparator(boolean ignoreCase) {
22                         fIgnoreCase = ignoreCase;
23                 }
24
25                 public int compare(Object left, Object right) {
26                         return fIgnoreCase ? ((String) left)
27                                         .compareToIgnoreCase((String) right) : ((String) left)
28                                         .compareTo((String) right);
29                 }
30         }
31
32         /**
33          * Creates a sorter with default string comparator. The keys are assumed to
34          * be strings.
35          * 
36          * @param ignoreCase
37          *            specifies whether sorting is case sensitive or not.
38          */
39         public TwoArrayQuickSorter(boolean ignoreCase) {
40                 fComparator = new StringComparator(ignoreCase);
41         }
42
43         /**
44          * Creates a sorter with a comparator.
45          * 
46          * @param comparator
47          *            the comparator to order the elements. The comparator must not
48          *            be <code>null</code>.
49          */
50         public TwoArrayQuickSorter(Comparator comparator) {
51                 fComparator = comparator;
52         }
53
54         /**
55          * Sorts keys and values in parallel.
56          * 
57          * @param keys
58          *            the keys to use for sorting.
59          * @param values
60          *            the values associated with the keys.
61          */
62         public void sort(Object[] keys, Object[] values) {
63                 if ((keys == null) || (values == null)) {
64                         Assert.isTrue(false, "Either keys or values in null"); //$NON-NLS-1$
65                         return;
66                 }
67
68                 if (keys.length <= 1)
69                         return;
70
71                 internalSort(keys, values, 0, keys.length - 1);
72         }
73
74         private void internalSort(Object[] keys, Object[] values, int left,
75                         int right) {
76                 int original_left = left;
77                 int original_right = right;
78
79                 Object mid = keys[(left + right) / 2];
80                 do {
81                         while (fComparator.compare(keys[left], mid) < 0)
82                                 left++;
83
84                         while (fComparator.compare(mid, keys[right]) < 0)
85                                 right--;
86
87                         if (left <= right) {
88                                 swap(keys, left, right);
89                                 swap(values, left, right);
90                                 left++;
91                                 right--;
92                         }
93                 } while (left <= right);
94
95                 if (original_left < right)
96                         internalSort(keys, values, original_left, right);
97
98                 if (left < original_right)
99                         internalSort(keys, values, left, original_right);
100         }
101
102         /*
103          * Swaps x[a] with x[b].
104          */
105         private static final void swap(Object x[], int a, int b) {
106                 Object t = x[a];
107                 x[a] = x[b];
108                 x[b] = t;
109         }
110
111 }