Commits

Michael Ludwig committed c3e3a93

Refactor and expose flexible quick sort implementation

Comments (0)

Files changed (4)

ferox-util/src/main/java/com/ferox/util/Bag.java

 import java.lang.reflect.Array;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.Collections;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
-import java.util.Random;
 import java.util.RandomAccess;
 
 /**
     public static final float DEFAULT_FACTOR = 2f;
     public static final int DEFAULT_GROWTH = 0;
 
-    private static final Random shuffler = new Random();
-
-    @SuppressWarnings("rawtypes")
-    private static final HashFunction NATURAL_HASHER = new HashFunction() {
-        @Override
-        public int hashCode(Object o) {
-            return o.hashCode();
-        }
-    };
-
     private E[] elements;
     private int size;
     private int maxFastClearSize;
      * <p>
      * However, this sort is often much faster than the above code (orders of
      * magnitude depending on the complexity of the Comparator). This is best
-     * used when there's not a precise definition of order. If <tt>hasher</tt>
-     * is null, the "natural" hashing function is used (e.g. each element's
-     * {@link Object#hashCode() hashCode()}).
+     * used when there's not a precise definition of order.
      * </p>
      * 
      * @param hasher The HashFunction that determines the integer hash codes
      *            which impose an ordering on the elements within this Bag
      */
-    @SuppressWarnings("unchecked")
-    public void sort(HashFunction<E> hasher) {
-        if (hasher == null) {
-            hasher = NATURAL_HASHER;
-        }
+    public void sort(final HashFunction<? super E> hasher) {
+        QuickSort.sort(new ItemView() {
+            @Override
+            public void swap(int srcIndex, int dstIndex) {
+                E t = elements[srcIndex];
+                elements[srcIndex] = elements[dstIndex];
+                elements[dstIndex] = t;
+            }
 
-        int[] keys = new int[size];
-        for (int i = 0; i < size; i++) {
-            keys[i] = hasher.hashCode(elements[i]);
-        }
-        quickSort(keys, 0, size);
-    }
+            @Override
+            public int length() {
+                return size;
+            }
 
-    /**
-     * Shuffle the elements within this bag randomly. This performs equivalently
-     * to {@link Collections#shuffle(java.util.List)} except that it operates on
-     * the Bag instead of a List.
-     */
-    public void shuffle() {
-        for (int i = size; i >= 1; i--) {
-            swap(i - 1, shuffler.nextInt(i));
-        }
+            @Override
+            public int hash(int index) {
+                return hasher.hashCode(elements[index]);
+            }
+        });
     }
 
     @Override
         return builder.toString();
     }
 
-    // use quick sort to sort the elements of the Bag, based off of paired keys stored in x
-    private void quickSort(int[] x, int off, int len) {
-        // insertion sort on smallest arrays
-        if (len < 7) {
-            for (int i = off; i < len + off; i++) {
-                for (int j = i; j > off && x[j - 1] > x[j]; j--) {
-                    swap(x, j, j - 1);
-                }
-            }
-            return;
-        }
-
-        // choose a partition element, v
-        int m = off + (len >> 1); // small arrays, middle element
-        if (len > 7) {
-            int l = off;
-            int n = off + len - 1;
-            if (len > 40) { // big arrays, pseudomedian of 9
-                int s = len / 8;
-                l = med3(x, l, l + s, l + 2 * s);
-                m = med3(x, m - s, m, m + s);
-                n = med3(x, n - 2 * s, n - s, n);
-            }
-            m = med3(x, l, m, n); // mid-size, med of 3
-        }
-        int v = x[m];
-
-        int a = off, b = a, c = off + len - 1, d = c;
-        while (true) {
-            while (b <= c && x[b] <= v) {
-                if (v == x[b]) {
-                    swap(x, a++, b);
-                }
-                b++;
-            }
-            while (c >= b && x[c] >= v) {
-                if (v == x[c]) {
-                    swap(x, c, d--);
-                }
-                c--;
-            }
-            if (b > c) {
-                break;
-            }
-            swap(x, b++, c--);
-        }
-
-        // swap partition elements back to middle
-        int s, n = off + len;
-        s = Math.min(a - off, b - a);
-        vecswap(x, off, b - s, s);
-        s = Math.min(d - c, n - d - 1);
-        vecswap(x, b, n - s, s);
-
-        // recursively sort non-partition-elements
-        if ((s = b - a) > 1) {
-            quickSort(x, off, s);
-        }
-        if ((s = d - c) > 1) {
-            quickSort(x, n - s, s);
-        }
-    }
-
-    // swaps the elements at indices a and b, along with the hashes in x
-    private void swap(int[] x, int a, int b) {
-        int k = x[a];
-        x[a] = x[b];
-        x[b] = k;
-        swap(a, b);
-    }
-
-    private void swap(int a, int b) {
-        E t = elements[a];
-        elements[a] = elements[b];
-        elements[b] = t;
-    }
-
-    // swaps n elements starting at a and b, such that (a,b), (a+1, b+1), etc. are swapped
-    private void vecswap(int[] x, int a, int b, int n) {
-        for (int i = 0; i < n; i++, a++, b++) {
-            swap(x, a, b);
-        }
-    }
-
-    // returns the index of the median of the three indexed elements
-    private static int med3(int x[], int a, int b, int c) {
-        return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
-    }
-
     private class BagIterator implements Iterator<E> {
         private int index;
         private E element;

ferox-util/src/main/java/com/ferox/util/HashFunction.java

  * @param <E> The Object type that will be hashed
  */
 public interface HashFunction<E> {
+    public static final HashFunction<Object> NATURAL_HASHER = new HashFunction<Object>() {
+        @Override
+        public int hashCode(Object o) {
+            return o.hashCode();
+        }
+    };
 
     /**
      * Compute and return the hash code for the given <tt>value</tt>. If

ferox-util/src/main/java/com/ferox/util/ItemView.java

+package com.ferox.util;
+
+public interface ItemView {
+
+    public int hash(int index);
+
+    public void swap(int srcIndex, int dstIndex);
+
+    public int length();
+}

ferox-util/src/main/java/com/ferox/util/QuickSort.java

+package com.ferox.util;
+
+import java.util.List;
+
+public class QuickSort {
+    public static void sort(ItemView view) {
+        int[] hashes = new int[view.length()];
+        for (int i = 0; i < hashes.length; i++) {
+            hashes[i] = view.hash(i);
+        }
+        quickSort(hashes, view, 0, hashes.length);
+    }
+
+    public static <T> void sort(final T[] array, final HashFunction<? super T> hash) {
+        sort(new ItemView() {
+            @Override
+            public void swap(int srcIndex, int dstIndex) {
+                T tmp = array[srcIndex];
+                array[srcIndex] = array[dstIndex];
+                array[dstIndex] = tmp;
+            }
+
+            @Override
+            public int length() {
+                return array.length;
+            }
+
+            @Override
+            public int hash(int index) {
+                return (array[index] == null ? 0 : hash.hashCode(array[index]));
+            }
+        });
+    }
+
+    public static <T> void sort(final List<T> list, final HashFunction<? super T> hash) {
+        sort(new ItemView() {
+            @Override
+            public void swap(int srcIndex, int dstIndex) {
+                T tmp = list.get(srcIndex);
+                list.set(srcIndex, list.get(dstIndex));
+                list.set(dstIndex, tmp);
+            }
+
+            @Override
+            public int length() {
+                return list.size();
+            }
+
+            @Override
+            public int hash(int index) {
+                return (list.get(index) == null ? 0 : hash.hashCode(list.get(index)));
+            }
+        });
+    }
+
+    public static <T> void sort(T[] array) {
+        sort(array, HashFunction.NATURAL_HASHER);
+    }
+
+    public static <T> void sort(List<T> list) {
+        sort(list, HashFunction.NATURAL_HASHER);
+    }
+
+    // use quick sort to sort the elements of the Bag, based off of paired keys stored in x
+    private static void quickSort(int[] x, ItemView view, int off, int len) {
+        // insertion sort on smallest arrays
+        if (len < 7) {
+            for (int i = off; i < len + off; i++) {
+                for (int j = i; j > off && x[j - 1] > x[j]; j--) {
+                    swap(x, view, j, j - 1);
+                }
+            }
+            return;
+        }
+
+        // choose a partition element, v
+        int m = off + (len >> 1); // small arrays, middle element
+        if (len > 7) {
+            int l = off;
+            int n = off + len - 1;
+            if (len > 40) { // big arrays, pseudomedian of 9
+                int s = len / 8;
+                l = med3(x, l, l + s, l + 2 * s);
+                m = med3(x, m - s, m, m + s);
+                n = med3(x, n - 2 * s, n - s, n);
+            }
+            m = med3(x, l, m, n); // mid-size, med of 3
+        }
+        int v = x[m];
+
+        int a = off, b = a, c = off + len - 1, d = c;
+        while (true) {
+            while (b <= c && x[b] <= v) {
+                if (v == x[b]) {
+                    swap(x, view, a++, b);
+                }
+                b++;
+            }
+            while (c >= b && x[c] >= v) {
+                if (v == x[c]) {
+                    swap(x, view, c, d--);
+                }
+                c--;
+            }
+            if (b > c) {
+                break;
+            }
+            swap(x, view, b++, c--);
+        }
+
+        // swap partition elements back to middle
+        int s, n = off + len;
+        s = Math.min(a - off, b - a);
+        vecswap(x, view, off, b - s, s);
+        s = Math.min(d - c, n - d - 1);
+        vecswap(x, view, b, n - s, s);
+
+        // recursively sort non-partition-elements
+        if ((s = b - a) > 1) {
+            quickSort(x, view, off, s);
+        }
+        if ((s = d - c) > 1) {
+            quickSort(x, view, n - s, s);
+        }
+    }
+
+    // swaps the elements at indices a and b, along with the hashes in x
+    private static void swap(int[] x, ItemView view, int a, int b) {
+        int k = x[a];
+        x[a] = x[b];
+        x[b] = k;
+        view.swap(a, b);
+    }
+
+    // swaps n elements starting at a and b, such that (a,b), (a+1, b+1), etc. are swapped
+    private static void vecswap(int[] x, ItemView view, int a, int b, int n) {
+        for (int i = 0; i < n; i++, a++, b++) {
+            swap(x, view, a, b);
+        }
+    }
+
+    // returns the index of the median of the three indexed elements
+    private static int med3(int x[], int a, int b, int c) {
+        return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
+    }
+}