Mercurial > projects > aid
view trunk/aid/containers/heap.d @ 7:b9fe92a2d8ad default tip
Removed old code.
author | revcompgeek |
---|---|
date | Tue, 06 May 2008 22:20:26 -0600 |
parents | 4b2e8e8a633e |
children |
line wrap: on
line source
/*++++++++++++++++++++++++++++++++++++++++++++ + 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; }