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