1 files changed, 23 insertions, 235 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMaxHeap.java
index 93a4e75a..036a9520 100644
--- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMaxHeap.java
+++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMaxHeap.java
@@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap;
  */
 
 import java.util.Arrays;
-import java.util.ConcurrentModificationException;
 
 import de.lmu.ifi.dbs.elki.math.MathUtil;
 
 /**
- * Advanced priority queue class, based on a binary heap (for small sizes),
- * which will for larger heaps be accompanied by a 4-ary heap (attached below
- * the root of the two-ary heap, making the root actually 3-ary).
- * 
- * This code was automatically instantiated for the types: Integer and Object
- * 
- * This combination was found to work quite well in benchmarks, but YMMV.
- * 
- * Some other observations from benchmarking:
- * <ul>
- * <li>Bulk loading did not improve things</li>
- * <li>Primitive heaps are substantially faster.</li>
- * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and
- * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li>
- * <li>Workload makes a huge difference. A load-once, poll-until-empty priority
- * queue is something different than e.g. a top-k heap, which will see a lot of
- * top element replacements.</li>
- * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for
- * top-k make a difference.</li>
- * <li>Different day, different benchmark results ...</li>
- * </ul>
+ * Binary heap for primitive types.
  * 
  * @author Erich Schubert
  * 
@@ -68,49 +47,16 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
   protected Object[] twovals;
 
   /**
-   * Extension heap.
-   */
-  protected int[] fourheap;
-
-  /**
-   * Extension heapvalues.
-   */
-  protected Object[] fourvals;
-
-  /**
    * Current size of heap.
    */
   protected int size;
 
   /**
-   * (Structural) modification counter. Used to invalidate iterators.
-   */
-  protected int modCount = 0;
-
-  /**
-   * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements.
-   */
-  private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1;
-
-  /**
    * Initial size of the 2-ary heap.
    */
   private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1;
 
   /**
-   * Initial size of 4-ary heap when initialized.
-   * 
-   * 21 = 4-ary heap of height 2: 1 + 4 + 4*4
-   * 
-   * 85 = 4-ary heap of height 3: 21 + 4*4*4
-   * 
-   * 341 = 4-ary heap of height 4: 85 + 4*4*4*4
-   * 
-   * Since we last grew by 255 (to 511), let's use 341.
-   */
-  private final static int FOUR_HEAP_INITIAL_SIZE = 341;
-
-  /**
    * Constructor, with default size.
    */
   public IntegerObjectMaxHeap() {
@@ -120,10 +66,6 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
 
     this.twoheap = twoheap;
     this.twovals = twovals;
-    this.fourheap = null;
-    this.fourvals = null;
-    this.size = 0;
-    this.modCount = 0;
   }
 
   /**
@@ -133,35 +75,17 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
    */
   public IntegerObjectMaxHeap(int minsize) {
     super();
-    if (minsize < TWO_HEAP_MAX_SIZE) {
-      final int size = MathUtil.nextPow2Int(minsize + 1) - 1;
-      int[] twoheap = new int[size];
-      Object[] twovals = new Object[size];
+    final int size = MathUtil.nextPow2Int(minsize + 1) - 1;
+    int[] twoheap = new int[size];
+    Object[] twovals = new Object[size];
       
-      this.twoheap = twoheap;
-      this.twovals = twovals;
-      this.fourheap = null;
-      this.fourvals = null;
-    } else {
-      int[] twoheap = new int[TWO_HEAP_INITIAL_SIZE];
-      Object[] twovals = new Object[TWO_HEAP_INITIAL_SIZE];
-      int[] fourheap = new int[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)];
-      Object[] fourvals = new Object[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)];
-      this.twoheap = twoheap;
-      this.twovals = twovals;
-      this.fourheap = fourheap;
-      this.fourvals = fourvals;
-    }
-    this.size = 0;
-    this.modCount = 0;
+    this.twoheap = twoheap;
+    this.twovals = twovals;
   }
 
   @Override
   public void clear() {
     size = 0;
-    ++modCount;
-    fourheap = null;
-    fourvals = null;
     Arrays.fill(twoheap, 0);
     Arrays.fill(twovals, null);
   }
@@ -181,34 +105,16 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
     final int co = o;
     final Object cv = (Object)v;
     // System.err.println("Add: " + o);
-    if (size < TWO_HEAP_MAX_SIZE) {
-      if (size >= twoheap.length) {
-        // Grow by one layer.
-        twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1);
-        twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1);
-      }
-      final int twopos = size;
-      twoheap[twopos] = co;
-      twovals[twopos] = cv;
-      ++size;
-      heapifyUp2(twopos, co, cv);
-      ++modCount;
-    } else {
-      final int fourpos = size - TWO_HEAP_MAX_SIZE;
-      if (fourheap == null) {
-        fourheap = new int[FOUR_HEAP_INITIAL_SIZE];
-        fourvals = new Object[FOUR_HEAP_INITIAL_SIZE];
-      } else if (fourpos >= fourheap.length) {
-        // Grow extension heap by half.
-        fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1));
-        fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1));
-      }
-      fourheap[fourpos] = co;
-      fourvals[fourpos] = cv;
-      ++size;
-      heapifyUp4(fourpos, co, cv);
-      ++modCount;
+    if (size >= twoheap.length) {
+      // Grow by one layer.
+      twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1);
+      twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1);
     }
+    final int twopos = size;
+    twoheap[twopos] = co;
+    twovals[twopos] = cv;
+    ++size;
+    heapifyUp(twopos, co, cv);
   }
 
   @Override
@@ -223,7 +129,6 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
   @Override
   public void replaceTopElement(int reinsert, V val) {
     heapifyDown(reinsert, (Object)val);
-    ++modCount;
   }
 
   /**
@@ -233,7 +138,7 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
    * @param cur Current object
    * @param val Current value
    */
-  private void heapifyUp2(int twopos, int cur, Object val) {
+  private void heapifyUp(int twopos, int cur, Object val) {
     while (twopos > 0) {
       final int parent = (twopos - 1) >>> 1;
       int par = twoheap[parent];
@@ -248,47 +153,11 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
     twovals[twopos] = val;
   }
 
-  /**
-   * Heapify-Up method for 4-ary heap.
-   * 
-   * @param fourpos Position in 4-ary heap.
-   * @param cur Current object
-   * @param val Current value
-   */
-  private void heapifyUp4(int fourpos, int cur, Object val) {
-    while (fourpos > 0) {
-      final int parent = (fourpos - 1) >> 2;
-      int par = fourheap[parent];
-      if (cur <= par) {
-        break;
-      }
-      fourheap[fourpos] = par;
-      fourvals[fourpos] = fourvals[parent];
-      fourpos = parent;
-    }
-    if (fourpos == 0 && twoheap[0] < cur) {
-      fourheap[0] = twoheap[0];
-      fourvals[0] = twovals[0];
-      twoheap[0] = cur;
-      twovals[0] = val;
-    } else {
-      fourheap[fourpos] = cur;
-      fourvals[fourpos] = val;
-    }
-  }
-
   @Override
   public void poll() {
     --size;
     // Replacement object:
-    if (size >= TWO_HEAP_MAX_SIZE) {
-      final int last = size - TWO_HEAP_MAX_SIZE;
-      final int reinsert = fourheap[last];
-      final Object reinsertv = fourvals[last];
-      fourheap[last] = 0;
-      fourvals[last] = null;
-      heapifyDown(reinsert, reinsertv);
-    } else if (size > 0) {
+    if (size > 0) {
       final int reinsert = twoheap[size];
       final Object reinsertv = twovals[size];
       twoheap[size] = 0;
@@ -298,42 +167,17 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
       twoheap[0] = 0;
       twovals[0] = null;
     }
-    ++modCount;
   }
 
   /**
    * Invoke heapify-down for the root object.
    * 
-   * @param reinsert Object to insert.
-   * @param val Value to reinsert.
-   */
-  private void heapifyDown(int reinsert, Object val) {
-    if (size > TWO_HEAP_MAX_SIZE) {
-      // Special case: 3-ary situation.
-      final int best = (twoheap[1] >= twoheap[2]) ? 1 : 2;
-      if (fourheap[0] > twoheap[best]) {
-        twoheap[0] = fourheap[0];
-        twovals[0] = fourvals[0];
-        heapifyDown4(0, reinsert, val);
-      } else {
-        twoheap[0] = twoheap[best];
-        twovals[0] = twovals[best];
-        heapifyDown2(best, reinsert, val);
-      }
-      return;
-    }
-    heapifyDown2(0, reinsert, val);
-  }
-
-  /**
-   * Heapify-Down for 2-ary heap.
-   * 
-   * @param twopos Position in 2-ary heap.
-   * @param cur Current object
+   * @param cur Object to insert.
    * @param val Value to reinsert.
    */
-  private void heapifyDown2(int twopos, int cur, Object val) {
-    final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1;
+  private void heapifyDown(int cur, Object val) {
+    final int stop = size >>> 1;
+    int twopos = 0;
     while (twopos < stop) {
       int bestchild = (twopos << 1) + 1;
       int best = twoheap[bestchild];
@@ -353,54 +197,6 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
     twovals[twopos] = val;
   }
 
-  /**
-   * Heapify-Down for 4-ary heap.
-   * 
-   * @param fourpos Position in 4-ary heap.
-   * @param cur Current object
-   * @param val Value to reinsert.
-   */
-  private void heapifyDown4(int fourpos, int cur, Object val) {
-    final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2;
-    while (fourpos < stop) {
-      final int child = (fourpos << 2) + 1;
-      int best = fourheap[child];
-      int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE;
-      if (size > minsize) {
-        int nextchild = fourheap[candidate];
-        if (best < nextchild) {
-          bestchild = candidate;
-          best = nextchild;
-        }
-
-        minsize += 2;
-        if (size >= minsize) {
-          nextchild = fourheap[++candidate];
-          if (best < nextchild) {
-            bestchild = candidate;
-            best = nextchild;
-          }
-
-          if (size > minsize) {
-            nextchild = fourheap[++candidate];
-            if (best < nextchild) {
-              bestchild = candidate;
-              best = nextchild;
-            }
-          }
-        }
-      }
-      if (cur >= best) {
-        break;
-      }
-      fourheap[fourpos] = best;
-      fourvals[fourpos] = fourvals[bestchild];
-      fourpos = bestchild;
-    }
-    fourheap[fourpos] = cur;
-    fourvals[fourpos] = val;
-  }
-
   @Override
   public int peekKey() {
     return twoheap[0];
@@ -449,16 +245,8 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
      */
     protected int pos = 0;
 
-    /**
-     * Modification counter we were initialized at.
-     */
-    protected final int myModCount = modCount;
-
     @Override
     public boolean valid() {
-      if (modCount != myModCount) {
-        throw new ConcurrentModificationException();
-      }
       return pos < size;
     }
 
@@ -469,14 +257,14 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> {
 
     @Override
     public int getKey() {
-      return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]);
+      return twoheap[pos];
     }
 
     @SuppressWarnings("unchecked")
 
     @Override
     public V getValue() {
-      return (V)((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]);
+      return (V)twovals[pos];
     }
   }
 }