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