net.sourceforge.phpeclipse/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 }