src/org/ibex/classgen/util/Sort.java

   1 package org.ibex.classgen.util;
   2
   3 // FIXME: Share this with nestedvm somehow
   4 public final class Sort {
   5     private Sort() { }
   6
   7     public interface Comparable { public int compareTo(Object o); }
   8     public interface CompareFunc { public int compare(Object a, Object b); }
   9
  10     private static final CompareFunc comparableCompareFunc = new CompareFunc() {
  11         public int compare(Object a,Object b) { return ((Comparable)a).compareTo(b); }
  12     };
  13
  14     public static void sort(Comparable[] a) { sort(a,comparableCompareFunc); }
  15     public static void sort(Object[] a, CompareFunc c) { sort(a,c,0,a.length-1); }
  16
  17     private static void sort(Object[] a, CompareFunc c, int start, int end) {
  18         Object tmp;
  19         if(start >= end) return;
  20         if(end-start <= 6) {
  21             for(int i=start+1;i<=end;i++) {
  22                 tmp = a[i];
  23                 int j;
  24                 for(j=i-1;j>=start;j--) {
  25                     if(c.compare(a[j],tmp) <= 0) break;
  26                     a[j+1] = a[j];
  27                 }
  28                 a[j+1] = tmp;
  29             }
  30             return;
  31         }
  32
  33         Object pivot = a[end];
  34         int lo = start - 1;
  35         int hi = end;
  36
  37         do {
  38             while((lo < hi) && c.compare(a[++lo],pivot) < 0) { }
  39             while((hi > lo) && c.compare(a[--hi],pivot) > 0) { }
  40             tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
  41         } while(lo < hi);
  42
  43         tmp = a[lo]; a[lo] = a[end]; a[end] = tmp;
  44
  45         sort(a, c, start, lo-1);
  46         sort(a, c, lo+1, end);
  47     }
  48 }