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