--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/aid/containers/heap.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,282 @@
+/*++++++++++++++++++++++++++++++++++++++++++++
+ +              Heap sorted array            +
+ +               By Matt Peterson            +
+ ++++++++++++++++++++++++++++++++++++++++++++*/
+
+/*class Heap(Value) {
+    Value[] array;
+    int tail;
+    public int capacity(){
+        // This returns the current capacity of the heap.
+        return array.length;
+    }
+    public int size(){
+        // This returns the number of items in the heap.
+        return tail;
+    }
+    
+    void capacity(int c){
+        // This sets the capacity to c.
+        if(c < tail) c = tail;
+        array.length = c;
+    }
+    void insert(Value v){
+        // Inserts a value and sorts it to it's correct position.
+        if(tail >= size()) capacity(size()+10);
+        array[++tail] = v;
+        int i = tail;
+        while(i > 0 && array[i/2] > array[i]){
+            array[i] = array[i/2];
+            array[i/2] = v;
+            i /= 2;
+        }
+    }
+    Value removeHead(){
+        Value ret = array[0];
+        array[0] = array[tail];
+        tail--;
+        i = 0;
+        while(
+    }
+    
+}*/
+
+struct Heap(Value, Alloc = GCAllocator) {
+
+  alias ArrayHeap   ContainerType;
+  alias Value       ValueType;
+  alias size_t      IndexType;
+
+  Value[] data;   ///< backing array. null by default, grows as needed
+
+  invariant {
+    assert( tail <= data.length );
+  }
+
+  /** signature for a custom comparison function */
+  alias int delegate(Value* a, Value* b) CompareFcn;
+
+  /** Set custom comparison function.   */
+  void compareFcn(CompareFcn cmp) {
+    cmpFcn = cmp;
+  }
+
+  /** Get heap contents as dynamic array slice of backing array.   */
+  Value[] values() {
+    return data[0..tail];
+  }
+
+  /** Adds an item to the heap. Increases capacity if needed.   */
+  void addTail(Value v) {
+    capacity(tail+1);
+    data[tail++] = v;
+    fixupTail();
+  }
+
+  /** Removes and returns the head item of the heap. If the target
+   * heap is empty an IndexOutOfBoundsException is thrown unless
+   * version=MinTLNoIndexChecking is set.
+   */
+  Value takeHead() {
+    version (MinTLNoIndexChecking) {
+      // no error checking
+    } else {
+      if (tail == 0)
+	throw new IndexOutOfBoundsException();
+    }
+    Value val = data[0];
+    data[0] = data[--tail];
+    data[tail] = Value.init;
+    fixupHead();
+    return val;
+  }
+
+  /** Removes the head item of the heap.   */
+  void removeHead() {
+    version (MinTLNoIndexChecking) {
+      // no error checking
+    } else {
+      if (tail == 0)
+	throw new IndexOutOfBoundsException();
+    }
+    data[0] = data[--tail];
+    data[tail] = Value.init;
+    fixupHead();
+  }
+
+  /** Get the length of heap.   */
+  size_t length() {
+     return tail;
+  }
+
+  /** Test if container is empty.   */
+  bool isEmpty() { 
+    return tail == 0;
+  }
+
+  /** Clear all contents. */
+  void clear() {
+    static if (is(Alloc == GCAllocator)) {
+    } else {
+      if (data.ptr)
+	Alloc.gcFree(data.ptr);
+    }
+    *this = ArrayHeap.init;
+  }
+
+  /** Get the nth item in the heap from head.   */
+  Value opIndex(size_t n) {
+    return data[n];
+  }
+
+  /** Get a pointer to the nth item in the heap   */
+  Value* lookup(size_t n) {
+    return &data[n];
+  }
+
+  /** Set the nth item in the heap.   */
+  void opIndexAssign(Value val, size_t n) {
+    data[n] = val;
+  }
+
+  /** Duplicates a heap.   */
+  ArrayHeap dup() {
+    ArrayHeap res;
+    static if (is(Alloc == GCAllocator)) {
+      res.data = data.dup;
+    } else {
+      Value* p = cast(Value*)Alloc.malloc(data.length * Value.sizeof);
+      res.data = p[0 .. data.length];
+      res.data[] = data[];
+    }
+    res.tail = tail;
+    res.cmpFcn = cmpFcn;
+    return res;
+  }
+
+  /** Test for equality of two heaps.   */
+  int opEquals(ArrayHeap c) {
+    size_t len = length;
+    if (len !is c.length)
+      return 0;
+    size_t a,b;
+    a = 0;
+    b = 0;
+    TypeInfo ti = typeid(Value);
+    for (size_t k = 0; k < len; k++) {
+      if (!ti.equals(&data[a],&c.data[b]))
+	return 0;
+      a++;
+      b++;
+    }
+    return 1;
+  }
+
+  /** Compare two heaps.   */
+  int opCmp(ArrayHeap c) {
+    size_t len = length;
+    if (len > c.length)
+      len = c.length;
+    size_t a,b;
+    a = 0;
+    b = 0;
+    TypeInfo ti = typeid(Value);
+    for (size_t k = 0; k < len; k++) {
+      int cmp = ti.compare(&data[a],&c.data[b]);
+      if (cmp)
+	return cmp;
+      a++;
+      b++;
+    }
+    return cast(int)length - cast(int)c.length;
+  }
+
+  /** Returns a short string representation of the heap. */
+  char[] toString() {
+    return "[ArrayHeap length " ~ std.string.toString(tail) ~ "]";
+  }
+
+  /** Iterates over the heap from head to tail calling delegate to
+   * perform an action. The value is passed to the delegate.
+   */
+  int opApplyNoKey(int delegate(inout Value x) dg){
+    int res = 0;
+    for (size_t k=0; k < tail; k++) {
+      res = dg(data[k]);
+      if (res) break;
+    }
+    return res;
+  }
+
+  /** Iterates over the heap from head to tail calling delegate to
+   * perform an action. The index from 0 and the value are passed
+   * to the delegate.
+   */
+  int opApplyWithKey(int delegate(inout size_t n, inout Value x) dg){
+    int res = 0;
+    for (size_t k=0; k < tail; k++) {
+      res = dg(k,data[k]);
+      if (res) break;
+    }
+    return res;
+  }
+
+  alias opApplyNoKey opApply;
+  alias opApplyWithKey opApply;
+
+  /** Ensure the minimum capacity of heap.   */
+  void capacity(size_t cap) {
+    if (cap > data.length) {
+      cap = (cap+1)*2;
+      static if (is(Alloc == GCAllocator)) {
+	data.length = cap;
+      } else {
+	Value* p = data.ptr;
+	p = cast(Value*)Alloc.gcRealloc(p,cap*Value.sizeof);
+	p[data.length .. cap] = Value.init;
+	data = p[0 .. cap];
+      }
+    }
+  }
+
+  // Helper functions
+
+  // enforce heap invariant after a new head
+  private void fixupHead() {
+    size_t n = 0;
+    TypeInfo ti = typeid(Value);
+    if (cmpFcn is null) {
+      cmpFcn = cast(CompareFcn)&ti.compare;
+    }
+    for (;;) {
+      size_t n1 = 2*n+1;
+      if (n1 >= tail) break;
+      if ((n1 != tail-1) && (cmpFcn(&data[n1],&data[n1+1]) < 0))
+	n1++;
+      if (cmpFcn(&data[n],&data[n1]) < 0) {
+	ti.swap(&data[n],&data[n1]);
+	n = n1;
+      } else {
+	break;
+      }
+    }
+  }
+
+  // enforce heap invariant after a new tail
+  private void fixupTail() {
+    size_t n = tail-1;
+    TypeInfo ti = typeid(Value);
+    if (cmpFcn is null) {
+      cmpFcn = cast(CompareFcn)&ti.compare;
+    }
+    size_t n1 = (n-1)>>1;
+    while ((n > 0) && (cmpFcn(&data[n],&data[n1]) > 0)) {
+      ti.swap(&data[n],&data[n1]);
+      n = n1;
+      n1 = (n-1)>>1;
+    }
+  }
+
+  private CompareFcn cmpFcn;
+  private size_t tail;
+}
\ No newline at end of file