From 8f20cbd09cb3b11fe8bd65e66d02f3453940c996 Mon Sep 17 00:00:00 2001
From: David Crawshaw <david@zentus.com>
Date: Sun, 19 Nov 2006 22:44:32 -0800
Subject: [PATCH] import classgen's Sort utility class, better to replicate 20
 lines of quicksort than make a mess of the build process

darcs-hash:20061120064432-0c629-34144a892c2e6e1c0619953e31c6bc063831e1ae.gz
---
 src/org/ibex/nestedvm/UnixRuntime.java |    2 --
 src/org/ibex/nestedvm/util/Sort.java   |   47 ++++++++++++++++++++++++++++++++
 2 files changed, 47 insertions(+), 2 deletions(-)
 create mode 100644 src/org/ibex/nestedvm/util/Sort.java

diff --git a/src/org/ibex/nestedvm/UnixRuntime.java b/src/org/ibex/nestedvm/UnixRuntime.java
index 2852f35..8031f58 100644
--- a/src/org/ibex/nestedvm/UnixRuntime.java
+++ b/src/org/ibex/nestedvm/UnixRuntime.java
@@ -5,8 +5,6 @@
 package org.ibex.nestedvm;
 
 import org.ibex.nestedvm.util.*;
-// HACK: This is ugly, this stuff needs to be in org.ibex.util or something
-import org.ibex.classgen.util.Sort;
 import java.io.*;
 import java.util.*;
 import java.net.*;
diff --git a/src/org/ibex/nestedvm/util/Sort.java b/src/org/ibex/nestedvm/util/Sort.java
new file mode 100644
index 0000000..79fe029
--- /dev/null
+++ b/src/org/ibex/nestedvm/util/Sort.java
@@ -0,0 +1,47 @@
+package org.ibex.nestedvm.util;
+
+public final class Sort {
+    private Sort() { }
+
+    public interface Comparable { public int compareTo(Object o); }
+    public interface CompareFunc { public int compare(Object a, Object b); }
+
+    private static final CompareFunc comparableCompareFunc = new CompareFunc() {
+        public int compare(Object a,Object b) { return ((Comparable)a).compareTo(b); }
+    };
+
+    public static void sort(Comparable[] a) { sort(a,comparableCompareFunc); }
+    public static void sort(Object[] a, CompareFunc c) { sort(a,c,0,a.length-1); }
+
+    private static void sort(Object[] a, CompareFunc c, int start, int end) {
+        Object tmp;
+        if(start >= end) return;
+        if(end-start <= 6) {
+            for(int i=start+1;i<=end;i++) {
+                tmp = a[i];
+                int j;
+                for(j=i-1;j>=start;j--) {
+                    if(c.compare(a[j],tmp) <= 0) break;
+                    a[j+1] = a[j];
+                }
+                a[j+1] = tmp;
+            }
+            return;
+        }
+
+        Object pivot = a[end];
+        int lo = start - 1;
+        int hi = end;
+
+        do {
+            while((lo < hi) && c.compare(a[++lo],pivot) < 0) { }
+            while((hi > lo) && c.compare(a[--hi],pivot) > 0) { }
+            tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
+        } while(lo < hi);
+
+        tmp = a[lo]; a[lo] = a[end]; a[end] = tmp;
+
+        sort(a, c, start, lo-1);
+        sort(a, c, lo+1, end);
+    }
+}
-- 
1.7.10.4