# HG changeset patch # User revcompgeek # Date 1206815420 21600 # Node ID 5dd9f598bcd8aa1ba971163e74a3d7066e837e16 # Parent 4b2e8e8a633e2a230bc01fa8b98ac460e4957d4c Update diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/aid/astar.d --- a/trunk/aid/astar.d Mon Mar 03 19:28:10 2008 -0700 +++ b/trunk/aid/astar.d Sat Mar 29 12:30:20 2008 -0600 @@ -6,12 +6,14 @@ module aid.astar; import mintl.arrayheap; +import mintl.arraylist; class Node(DATA) { int xloc; int yloc; int fitness; - private int fitg; + private int g; + private int h; Node* parent = null; DATA data; @@ -35,7 +37,7 @@ alias Node!(DATA) Node; alias DATA[] delegate(DATA) getChildren; ArrayHeap!(Node) openList; - ArrayHeap!(Node) closedList; + ArrayList!(Node) closedList; DATA[] run(DATA start){ } diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/ChangeLog --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/ChangeLog Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,106 @@ +2.7.2 + * all: update to dmd.1.014 + +2.7.1 + * all: update to dmd.129 + * share, set, multiaa: add static make() that calls add(...) + * hashaa, sortedaa: add block allocated nodes and recycling. add trim() + +2.7 + * arraylist/deque: mixin RandomAccessSort + * list/hashaa: mixin SequentialSort + * sorting: new templates for sorting algorithms + * hashaa: fix insertion bug with rehashing + +2.6.2 + * hashaa/sortedaa: remove enum from 2.6.1 and make get() and put(). + * multiaa: re-enable and uncomment unittests + * set: clean up mixins were for builtin AA support + * all: shorten opApply code by relying on opApplyIter + * arraylist, deque: fix len wrapping code and next() bug + * all.d: added "no warrenty" clause + +2.6.1 + * deque/arraylist: switched to start/len instead of head/tail to + make wrapping easier + * hashaa/sortedaa: redo indexing api to allow NullOnMiss, ThrowOnMiss + and InsertOnMiss for get(). Replace opIn with contains. Remove lookup. + Add 'missing' property for lookups that miss. + +2.6 + * all: simplify mixins by adding type aliases ContainerType, ValueType + IndexType, IterType + * lists: add value getter/setter for one-item slices + * all: add opCmp + * all: add ReadOnly parameter and readonly/readwrite property + * lists: add opIn, count, swap, find, fill, copy algorithms + * hashaa: for consistency with other containers rename LinkedAA + to HashAA and make the default for adapters + * all: update to dmd.126 + +2.5 + * list.d: CList to CircularList and CSList to CircularSList + * all: change move(), moveHead(), moveTail() to next() + * all: added take() and takeHead/Tail to return value if any + * concurrent/aa.d: ConcurrentAA changes to implement Collection + * arraylist.d: grow ArrayList capacity geometrically + * all: remove toArray and replace with values + * all: remove toSeq since instantiating CFoo is equivalent + * linked/sortedaa.d: change fromHead, fromTail to head/tail + * lists: add head/tail properties to get one-item slices of head/tail + * list.d: remove length setter and make length==0 mean unknown length + that gets computed only when required + * list.d: make head null indicate empty list, tail hold cache + * sortedaa.d: add from(key) and to(key) + * deque.d: simplify code by not resizing block size and making it cyclic + * arraylist.d: fix copyBlock bug copying between arrays of different size + * adapter.d: mixins for adapters + * stack.d: adapter for stack + * queue.d: adapter for queue + * set.d: adapter for sets and multi-sets + * multiaa.d: adapter for multi-aa + * index.html: update for above and add class.html. + * mintl.cls: new package containing interfaces and classes - + separate download + * mem.d: new module for customer allocators + * all: add clear() to support custom allocators + +2.2 + * all: replaced length sizes with size_t instead of uint and be careful + about overflows + * arraylist.d: change ArrayList to dynamically grow instead of error + * util.d: removed and moved aliases to target's module + * seq.d: removed and moved contents to share.d + * all: unify bounds checking code into a shared fcn for each module + * opIn: return a pointer to the element or null. + * index.html: update for above and document MinTLNoIndexChecking. + +2.1.1 + * list.d: moved mixin in list.d and slist.d to match new dmd + behavior dmd.119 + * array.d: removed obsolete AA helper functions + * arraylist.d: added capacity, length setter and array to ArrayList + to let it + act more like an array-with-capacity. The only overhead is an extra + head value that is always 0. + * arraylist.d: fixed bug in ArrayList moveBlock when copying to end + of array + +2.1 + * concurrent: split out concurrent containers into a different + distribution + +2.02 + * libmintl_debug.a and mintl_debug.lib debug builds of library + +2.01 + * array.d: remove AA utilities by default since the new implementation + breaks the old routines. old code is available with version AllowAAUtils + * arraylist.d: update for int/uint implicit conversion rules + * win32.mak: update to build unittest with SRC instead of mintl.lib + * linux.mak: same + * concurrent/*.d: add volatile statements back in + * concurrent/dualstack.d: removeTail gets result from t not next + * concurrent/aa.d: add debug print statements + * concurrent/priorityqueue.d: add slower yields to unittest + * concurrent/linkedqueue.d: add slower yields to unittest diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/adapter.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/adapter.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,47 @@ +/** \file adapter.d + * \brief Mixins for adapter containers like stack, queue, set. + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 1.1 + */ + +module mintl.adapter; + +template MAdaptBuiltin(alias impl, Container) { + size_t length() { return impl.length; } + int opEquals(Container c) { return impl == c.impl; } +} + +template MAdaptBasic(alias impl, Container) { + bool isEmpty() { return impl.isEmpty; } + Container.ValueType opIndex(Container.IndexType n) { return impl[n]; } + static if (!Container.isReadOnly) { + void opIndexAssign(Container.ValueType v, Container.IndexType n) { impl[n] = v; } + } + int opApply(int delegate(inout Container.ValueType x) dg){return impl.opApply(dg);} + int opApply(int delegate(inout Container.IndexType, inout Container.ValueType x) dg){return impl.opApply(dg);} + Container dup() { + Container res; + res.impl = impl.dup; + return res; + } +} + +template MAdaptList(alias impl, Container) { + static if (!Container.isReadOnly) { + void addHead(Container.ValueType v) {impl.addHead(v);} + void addHead(Container v) {impl.addHead(v.impl);} + void addTail(Container.ValueType v) {impl.addTail(v);} + void addTail(Container v) {impl.addTail(v.impl);} + Container.ValueType takeTail() {return impl.takeTail();} + void removeTail() {impl.removeTail();} + Container.ValueType takeHead() {return impl.takeHead();} + void removeHead() {impl.removeHead();} + void clear(){impl.clear();} + } + int opCmp(Container c) { return impl.opCmp(c.impl); } +} + diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/all.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/all.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,49 @@ +/** \file all.d + * \brief Minimal Template Library global import. For concurrent + * containers import mintl.concurrent.all. For class and interface + * API import mintl.cls.all. + * See index.html for documentation. + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 2.7.1 + */ + +/* The MinTL library and sub-libraries are provided 'as-is', without + * any express or implied warranty. In no event will the authors be + * held liable for any damages arising from the use of this software. + */ + +module mintl.all; + +// builtin array helper functions +import mintl.array; + +// linked lists +import mintl.list; +import mintl.slist; + +// special associative arrays +import mintl.hashaa; +import mintl.sortedaa; + +// circular buffer or array with capacity +import mintl.arraylist; + +// heap (complete binary tree) +import mintl.arrayheap; + +// deque (block allocated double-ended queue) +import mintl.deque; + +// adapter containers +import mintl.stack; +import mintl.queue; +import mintl.set; +import mintl.multiaa; + +// shared exceptions and definitions +import mintl.share; + diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/array.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/array.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,184 @@ +/** \file array.d + * \brief Utility functions for dynamic and associative arrays. + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 2.6 + */ + +module mintl.array; + +// sort with custom compare delegate +template sort(Value:Value[]) { + void sort(Value[] data, int delegate(Value* l, Value* r) cmp = null) { + void swap( Value* t1, Value* t2 ) { + Value t = *t1; *t1 = *t2; *t2 = t; + } + void insertionSort(Value[] data) { + Value* head = &data[0]; + Value* tail = head+data.length; + Value* i = head+1; + while(i < tail) { + Value* j = i; + for (; j > head && cmp(j - 1,j) > 0; j--) { + swap(j - 1,j); + } + i++; + } + } + void dosort(Value[] data) { + if (data.length < 2) { + return; + } else if (data.length < 8) { + insertionSort(data); + return; + } + Value *head = &data[0]; + Value *tail = head+data.length-1; + Value *p = head+1; + Value *q = tail; + swap(head,head+data.length/2); + if (cmp(p,q) > 0) swap(p,q); + if (cmp(head,q) > 0) swap(head,q); + if (cmp(p,head) > 0) swap(p,head); + while (1) { + do p++; while (cmp(p, head) < 0); + do q--; while (cmp(q, head) > 0); + if (p > q) break; + swap(p,q); + } + swap(head,q); + if (head < q) + dosort(head[0 .. q-head+1]); + if (p < tail) + dosort(p[0 .. tail-p+1]); + } + TypeInfo ti = typeid(Value); + if (cmp is null) { + cmp = cast(typeof(cmp))&ti.compare; + } + dosort(data); + } +} + +/** Reserve a capacity for a dynamic array. If the array already has + * more elements or if the original length is zero it does nothing. + * Compiler-dependent. + * \param x the array to modify + * \param n the requested capacity + */ +template reserve(Value : Value[]) { + void reserve(inout Value[] x, size_t n) { + size_t oldlen = x.length; + if ((oldlen < n) && (oldlen > 0)) { + x.length = n; + x.length = oldlen; + } + } +} + +/** Iterate backwards over a dynamic array. This function should be + * used on the target array in a foreach statement or + * or as the target to a call to toSeq x.backwards.toSeq + * \param x the array to iterate over. + */ +template backwards(Value : Value[]) { + DArrayReverseIter!(Value) backwards(Value[] x) { + DArrayReverseIter!(Value) y; + y.x = x; + return y; + } +} + +/* Private helper for reverse iteration */ +private struct DArrayReverseIter(Value) { + Value[] x; + int opApply(int delegate(inout Value val) dg) { + int res = 0; + for (size_t n=x.length; n > 0; ) { + res = dg(x[--n]); + if (res) break; + } + return res; + } + int opApply(int delegate(inout size_t n, inout Value val) dg) { + int res = 0; + size_t cnt = 0; + for (size_t n=x.length; n > 0; cnt++) { + res = dg(cnt,x[--n]); + if (res) break; + } + return res; + } +} + +//version = MinTLVerboseUnittest; +//version = MinTLUnittest; +version (MinTLUnittest) { + private import std.random; + unittest { + version (MinTLVerboseUnittest) + printf("starting mintl.array unittest\n"); + + int[] x; + x.length = 1; + reserve!(int[])(x,100); + int[] y = x; + x.length = 90; + assert( cast(int*)x == cast(int*)y ); + version (MinTLVerboseUnittest) + printf("pass\n"); + + int[] t1,t2; + t1.length = 4; + t2.length = 4; + for(int k=0;k<4;k++) t1[k] = k*100; + foreach(size_t n, int val; backwards!(int[])(t1)) { + t2[n] = val; + } + assert( t1.reverse == t2 ); + version (MinTLVerboseUnittest) + printf("pass\n"); + + double[int] c; + c[100] = 1.1; + c[300] = 2.2; + c[-100] = 3.3; + double v; + assert( 100 in c ); + assert( !(200 in c) ); + assert( 300 in c ); + for (int k=0;k<1000;k++) { + c[k*100] = 1; + } + + // test simple sorting + static int[] data = [40,300,-20,100,400,200]; + int[] s1 = data.dup; + sort!(int[])(s1); + static int[] s2 = [-20,40,100,200,300,400]; + assert( s1 == s2 ); + + // test a large sort with default order + double[] s3; + for (int k=0;k<1000;k++) { + s3 ~= 1.0*rand()/100000.0 - 500000.0; + } + double[] s4 = s3.dup; + sort!(double[])(s3); + for (int k=0;k<999;k++) { + assert( s3[k] <= s3[k+1] ); + } + // test a large sort with custom order + int cmp(double*x,double*y){return *x>*y?-1:*x==*y?0:1;} + sort!(double[])(s4,&cmp); + for (int k=0;k<999;k++) { + assert( s4[k] >= s4[k+1] ); + } + + version (MinTLVerboseUnittest) + printf("finished mintl.array unittest\n"); + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/arrayheap.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/arrayheap.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,333 @@ +/** \file arrayheap.d + * \brief A heap (complete binary tree) backed by an array + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 2.6 + */ + +module mintl.arrayheap; + +private { + import mintl.share; // for ~ and ~= + import mintl.mem; + //import std.string; +} + +/** \class ArrayHeap + * \brief A heap (complete binary tree) backed by an array + * + * An ArrayHeap!(Value) is a heap of data of type Value backed + * by an array. Adding to the tail and removing the head of the heap + * are O(log(n)) operations. The items in the heap are maintained + * in sorted order with the largest item at index 0 and for the nth item + * the items at index 2*n+1 and 2*n+2 are smaller (or equal to) + * item n. + * + * The optional allocator parameter ArrayHeap!(Value,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct ArrayHeap(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; + } + } + + // added by h3 + void eraseNoDelete() { + tail = 0; + } + + private CompareFcn cmpFcn; + private size_t tail; +} + +//version = MinTLVerboseUnittest; +//version = MinTLUnittest; +version (MinTLUnittest) { + private import std.string; + unittest { + version (MinTLVerboseUnittest) + printf("started mintl.arrayheap unittest\n"); + + ArrayHeap!(int) x,y,z; + x.data = new int[10]; + x.addTail(5); + x.addTail(3); + x.addTail(4); + assert( x.length == 3 ); + assert( x[0] == 5 ); + assert( x[x.length-1] == 4 ); + + y = x.dup; + + assert( x == y ); + + assert( x.takeHead == 5 ); + assert( x.takeHead == 4 ); + assert( x.takeHead == 3 ); + assert( x.length == 0 ); + + y.addTail(6); + int[10] y2; + int k=0; + foreach(int val; y) { + y2[k++] = val; + } + assert( y2[0] == 6 ); + assert( y2[1] == 5 ); + assert( y2[2] == 4 ); + assert( y2[3] == 3 ); + + k=0; + foreach(size_t n, int val; y) { + y2[n] = val; + } + assert( y2[0] == 6 ); + assert( y2[1] == 5 ); + assert( y2[2] == 4 ); + assert( y2[3] == 3 ); + + ArrayHeap!(int,MallocNoRoots) xm; + for (int k=0;k<100;k++) + xm.addTail(k); + for (int k=0;k<100;k++) + assert( xm.takeHead == 99-k ); + xm.clear(); + + version (MinTLVerboseUnittest) + printf("finished mintl.arrayheap unittest\n"); + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/arraylist.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/arraylist.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,858 @@ +/** \file arraylist.d + * \brief A list backed by an array. This container can + * also be used as an array with managed capacity by only + * inserting and removing from the tail and keeping the head fixed + * at 0. + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 2.7.1 + */ + +module mintl.arraylist; + +private import mintl.share; // for ~ and ~= +private import mintl.sorting; +import mintl.mem; + +private extern(C) void *memmove(void *, void *, uint); + +//debug = dArrayList; // can also pass at command line + +/** \class ArrayList + * \brief A bounded list backed by an array + * + * An ArrayList!(Value) is a list of data of type Value backed + * by a circular array. The performance of ArrayLists is on the same + * order as for arrays except adding an element to the head of an + * ArrayList is constant. The backing array can be dynamic or static + * arrays and should be set prior to use by assigning to the + * data property or the capacity property. The + * ArrayList will automatically grow the backing array if needed. + * + * An ArrayList can also be used as an array with managed capacity. + * To do so only insert and remove from the tail and keep the head fixed + * at 0. + * + * The optional ReadOnly parameter ArrayList!(Value,ReadOnly) forbids + * operations that modify the container. The readonly() property returns + * a ReadOnly view of the container. + * + * The optional allocator parameter ArrayList!(Value,false,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct ArrayList(Value, bit ReadOnly = false, Alloc = GCAllocator) { + + alias ArrayList ContainerType; + alias ArrayList SliceType; + alias Value ValueType; + alias size_t IndexType; + alias ReadOnly isReadOnly; + + Value[] data; ///< backing array. null by default. + + invariant { + assert( data.length == 0 || start < data.length ); + assert( len <= data.length ); + } + + /** Get a ReadOnly view of the container */ + .ArrayList!(Value, true, Alloc) readonly() { + .ArrayList!(Value, true, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get a read-write view of the container */ + .ArrayList!(Value, false, Alloc) readwrite() { + .ArrayList!(Value, false, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + static if (!ReadOnly) { + + /** Appends an item to the tail of the list. If the target list is + * a sub-list call addAfter instead of addTail to insert an item + * after a sub-list. Increases capacity if needed. + */ + void addTail(Value v) { + capacity(length+1); + data[addi(start,len)] = v; + len++; + } + + /** Appends a list to the tail of the target list. If the target + * list is a sub-list call addAfter instead of addTail to insert + * another list after a sub-list. Increases capacity if needed. + */ + void addTail(ArrayList v) { + size_t vlen = v.length; + capacity(len+vlen); + copyBlock(v,data,addi(start,len),vlen); + len += vlen; + } + + /** overload ~ and ~= */ + mixin MListCatOperators!(ArrayList); + + /** Removes and returns the tail item of the list. If the target + * list is empty an IndexOutOfBoundsException is thrown unless + * version=MinTLNoIndexChecking is set. + */ + Value takeTail() { + boundsCheck(length-1); + len--; + size_t n = addi(start,len); + Value val = data[n]; + data[n] = Value.init; + return val; + } + + /** Removes the tail item of the list. */ + void removeTail() { + boundsCheck(length-1); + len--; + data[addi(start,len)] = Value.init; + } + + /** Prepends an item to the head of the target list. If the target + * list is a sub-list call addBefore instead of addHead to insert an + * after a sub-list. Increases capacity if needed. + */ + void addHead(Value v) { + debug(dArrayList) printf(" add %d %u\n",start-1,dec(start)); + capacity(len+1); + start = dec(start); + data[start] = v; + len++; + } + + /** Prepends a list to the head of the target list. If the target + * list is a sub-list call addBefore instead of addHead to insert a + * list before a sub-list. Increases capacity if needed. + */ + void addHead(ArrayList v) { + size_t vlen = v.length; + capacity(len+vlen); + size_t newhead = subi(start,vlen); + copyBlock(v,data,newhead,vlen); + start = newhead; + len += vlen; + } + + /** Removes and returns the head item of the list. If the target + * list is empty an IndexOutOfBoundsException is thrown unless + * version=MinTLNoIndexChecking is set. + */ + Value takeHead() { + boundsCheck(length-1); + Value val = data[start]; + data[start] = Value.init; + start = inc(start); + debug(dArrayList) printf("%d %d\n",start,val); + len--; + return val; + } + + /** Removes the head item of the list. */ + void removeHead() { + boundsCheck(len-1); + data[start] = Value.init; + start = inc(start); + len--; + debug(dArrayList) printf("%d\n",start); + } + + /** Insert a list before a sub-list. Increases capacity if needed. */ + void addBefore(ArrayList subv, ArrayList v) { + size_t vlen = v.length; + if (vlen == 0) return; + capacity(length+vlen); + size_t tlen = subv.start >= start ? subv.start-start : data.length-start+subv.start; + size_t newhead = subi(start,vlen); + moveBlockLeft(start,tlen,newhead); + copyBlock(v,data,subi(subv.start,vlen),vlen); + start = newhead; + len += vlen; + } + + /** Insert a list after a sub-list. Increases capacity if needed. */ + void addAfter(ArrayList subv, ArrayList v) { + size_t vlen = v.length; + if (vlen == 0) return; + capacity(length+vlen); + size_t tail = addi(start,len); + size_t stail = addi(subv.start,subv.len); + size_t tlen = stail <= tail ? tail-stail : data.length-stail+tail; + moveBlockRight(stail,tlen,addi(stail,vlen)); + copyBlock(v,data,stail,vlen); + len += vlen; + } + + /** Set the length of list. */ + void length(size_t len) { + capacity(len); + this.len = len; + } + + /** Clear all contents. */ + void clear() { + static if (is(Alloc == GCAllocator)) { + } else { + if (data.ptr) + Alloc.gcFree(data.ptr); + } + *this = ArrayList.init; + } + + /** Set the nth item in the list from head. Indexing out of bounds + * throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + void opIndexAssign(Value val, size_t n) { + boundsCheck(n); + data[addi(start,n)] = val; + } + + /** Set the value of one-item slice (more generally the head value). */ + void value(Value newValue) { + opIndexAssign(newValue,0); + } + + /** Removes a sub-list from the list. */ + void remove(ArrayList sublist) { + size_t tail = addi(start,len); + size_t slen = sublist.len; + size_t stail = addi(sublist.start,slen); + size_t tlen = stail <= tail ? tail-stail : data.length-stail+tail; + debug(dArrayList) printf("remove %d %d\n",sublist.start, sublist.length); + moveBlockLeft(stail, tlen, sublist.start); + fillBlock(subi(tail,slen),slen,Value.init); + len -= slen; + debug(dArrayList) printf("removed %d %d\n",start, len); + } + + /** Removes an item from the list, if present. */ + void remove(size_t index) { + ArrayList item = opSlice(index, index+1); + remove(item); + } + + /** Removes an item from the list and returns the value, if present. */ + Value take(size_t index) { + ArrayList item = opSlice(index, index+1); + Value val = item[0]; + remove(item); + return val; + } + + } // !ReadOnly + + /** Move a sub-list towards the tail by n items. If n is + * negative the sub-list moves towards the head. A positive end is + * the tail, negative the head and 0 is both. By default moves to + * to the next item. + */ + void next(int n = 1, int end = 0) { + if (end) + len += n<0?-n:n; + if (end <= 0) { + if (n<0) { + start = subi(start,-n); + } else { + start = addi(start,n); + } + } + } + + /** Get the length of list. */ + size_t length() { + return len; + } + + private const double GrowthRate = 1.5; + + /** Ensure the minimum capacity of list. */ + void capacity(size_t cap) { + if (data.length < cap) { + cap = cast(size_t)(cap*GrowthRate)+1; + if (start > data.length - len) { + size_t oldlen = data.length; + size_t oldheadlen = oldlen - start; + resizeData(cap); + moveBlockRight(start,oldheadlen, cap - oldheadlen); + start = cap-oldheadlen; + } else { + resizeData(cap); + } + } + } + + // helper for capacity + private void resizeData(size_t cap) { + 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]; + } + } + + /** Get the capacity of list. */ + size_t capacity() { + return data.length; + } + + /** Test if container is empty. */ + bool isEmpty() { + return len == 0; + } + + /** Get the nth item in the list from head. Indexing out of bounds + * throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + Value opIndex(size_t n) { + boundsCheck(n); + return data[addi(start,n)]; + } + + /** Get the value of one-item slice (more generally the head value). + * Useful for expressions like x.tail.value or x.head.value. */ + Value value() { + return opIndex(0); + } + + // helper function to check if the index is legal + private void boundsCheck(size_t n) { + version (MinTLNoIndexChecking) { + } else { + if (n >= len) { + throw new IndexOutOfBoundsException(); + } + } + } + + /** Create a one-item slice of the head. */ + ArrayList head() { + return opSlice(0,1); + } + + /** Create a one-item slice of the tail. */ + ArrayList tail() { + size_t len = length; + return opSlice(len-1,len); + } + + /** Reverse a list in-place. */ + ArrayList reverse() { + size_t tlen = len / 2; + size_t a,b; + a = start; + b = dec(addi(start,len)); + TypeInfo ti = typeid(Value); + for (size_t k = 0; k < tlen; k++) { + debug(dArrayList) printf("swapping %d %d\n",data[a],data[b]); + ti.swap(&data[a],&data[b]); + a = inc(a); + b = dec(b); + } + return *this; + } + + /** Get list contents as dynamic array (a slice if possible). */ + Value[] values() { + Value[] buffer; + if (start <= data.length-len) { + buffer = data[start .. start+len]; + } else { + buffer.length = len; + buffer[0 .. data.length-start] = data[start .. data.length]; + buffer[data.length-start .. buffer.length] = + data[0 .. len - data.length - start]; + } + return buffer; + } + + /** Duplicates a list. */ + ArrayList dup() { + ArrayList 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.start = start; + res.len = len; + return res; + } + + /** Test for equality of two lists. */ + int opEquals(ArrayList c) { + if (len !is c.len) + return 0; + size_t a,b; + a = start; + b = c.start; + TypeInfo ti = typeid(Value); + for (size_t k = 0; k < len; k++) { + if (!ti.equals(&data[a],&c.data[b])) + return 0; + a = inc(a); + b = inc(b); + } + return 1; + } + + /** Compare two lists. */ + int opCmp(ArrayList c) { + size_t tlen = len; + if (tlen > c.len) + tlen = c.len; + size_t a,b; + a = start; + b = c.start; + TypeInfo ti = typeid(Value); + for (size_t k = 0; k < tlen; k++) { + int cmp = ti.compare(&data[a],&c.data[b]); + if (cmp) + return cmp; + a = inc(a); + b = inc(b); + } + return cast(int)len - cast(int)c.len; + } + + /** Create a sub-list from index a to b (exclusive). */ + ArrayList opSlice(size_t a, size_t b) { + ArrayList res; + res.data = data; + res.start = addi(start,a); + res.len = b-a; + debug(dArrayList) printf("slice %d %d\n",res.start,res.len); + return res; + } + + /** Create a sub-list from the head of a to the tail of b (inclusive). */ + ArrayList opSlice(ArrayList a, ArrayList b) { + ArrayList res; + res.data = data; + res.start = a.start; + if (b.start >= a.start) + res.len = b.start - a.start + b.len; + else + res.len = data.length - a.start + b.len + b.start; + return res; + } + + /** Iterates over the list from head to tail calling delegate to + * perform an action. The value is passed to the delegate. + */ + int opApplyNoKeyStep(int delegate(inout Value x) dg, int step = 1){ + int dg2(inout size_t n, inout Value x) { + return dg(x); + } + return opApplyWithKeyStep(&dg2,step); + } + + /** Iterates over the list from head to tail calling delegate to + * perform an action. The index from 0 and the value are passed + * to the delegate. + */ + int opApplyWithKeyStep(int delegate(inout size_t n, inout Value x) dg, int step = 1){ + if (len == 0) return 0; + int res = 0; + size_t tail = addi(start,len); + size_t istart = step>0 ? start : dec(tail); + size_t iend = step>0 ? tail : dec(start); + size_t n = step>0 ? 0 : len-1; + for (size_t k = istart; k != iend;) { + res = dg(n,data[k]); + if (res) break; + if (step < 0) + k = subi(k,-step); + else + k = addi(k,step); + n += step; + } + return res; + } + + /** Iterates over the list from head to tail calling delegate to + * perform an action. A one-item sub-list is passed to the delegate. + */ + int opApplyIterStep(int delegate(inout ArrayList n) dg, int step = 1){ + ArrayList itr; + itr.data = data; + itr.len = 1; + int dg2(inout size_t n, inout Value x) { + itr.start = addi(start,n); + return dg(itr); + } + return opApplyWithKeyStep(&dg2,step); + } + + /** Iterate backwards over the list (from tail to head). + * This should only be called as the + * iteration parameter in a foreach statement + */ + ArrayListReverseIter!(Value,ReadOnly,Alloc) backwards() { + ArrayListReverseIter!(Value,ReadOnly,Alloc) res; + res.list = this; + return res; + } + + /** Helper functions for opApply */ + mixin MOpApplyImpl!(ArrayList); + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + alias opApplyIter opApply; + + ArrayList getThis(){return *this;} + mixin MListAlgo!(ArrayList, getThis); + mixin MRandomAccessSort!(ArrayList, getThis); + + /** Get a pointer to the nth item in the list from head. Indexing + * out of bounds throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + Value* lookup(size_t n) { + boundsCheck(n); + return &data[addi(start,n)]; + } + + // Helper functions + + // helper function to copy sections of the backing buffer + private void moveBlockLeft(size_t srchead, size_t len, size_t desthead) { + size_t ns = srchead; + size_t nd = desthead; + while (len > 0) { + debug(dArrayList) printf("move left len %u\n",len); + size_t sz = len; + if (ns > data.length-sz) + sz = data.length-ns; + if (nd > data.length-sz) + sz = data.length-nd; + assert(sz != 0); + memmove(&data[nd],&data[ns],sz*Value.sizeof); + ns = addi(ns,sz); + nd = addi(nd,sz); + len -= sz; + } + } + + // helper function to copy sections of the backing buffer + private void moveBlockRight(size_t srchead, size_t len, size_t desthead) { + debug(dArrayList) printf("len %u\n",len); + size_t ns = addi(srchead,len-1)+1; + size_t nd = addi(desthead,len-1)+1; + while (len > 0) { + int sz = len; + if (ns < sz) + sz = ns; + if (nd < sz) + sz = nd; + assert(sz != 0); + memmove(&data[nd-sz],&data[ns-sz],sz*Value.sizeof); + ns = dec(subi(ns,sz))+1; + nd = dec(subi(nd,sz))+1; + len -= sz; + } + } + + // helper function to copy sections of the backing buffer + private void copyBlock(ArrayList src, + Value[] destdata,int desthead, + int len) { + Value[] srcdata = src.data; + int srchead = src.start; + int ns = srchead; + int nd = desthead; + while (len > 0) { + debug(dArrayList) printf("copy len %u %d %d len %d len %d\n", + len,ns,nd,srcdata.length,destdata.length); + int sz = len; + if (ns > srcdata.length-sz) + sz = srcdata.length-ns; + if (nd > destdata.length-sz) + sz = destdata.length-nd; + assert(sz != 0); + memmove(&destdata[nd],&srcdata[ns],sz*Value.sizeof); + ns = src.addi(ns,sz); + nd = addi(nd,sz); + len -= sz; + } + } + + // helper function to fill a section of the backing array + private void fillBlock(size_t srchead, size_t len, Value val) { + size_t ns = srchead; + while (len > 0) { + size_t sz = len; + if (ns > data.length-sz) + sz = data.length-ns; + assert(sz != 0); + data[ns .. ns+sz] = val; + ns = addi(ns,sz); + len -= sz; + } + } + + // move index n by 1 with wrapping + private size_t inc(size_t n) { + return (n == data.length-1) ? 0 : n+1; + } + + // move index n by -1 with wrapping + private size_t dec(size_t n) { + return (n == 0) ? data.length-1 : n-1; + } + + // move index n by -diff with wrapping + private size_t subi(size_t n, size_t diff) { + size_t res; + if (n < diff) + res = data.length - diff + n; + else + res = n - diff; + debug(dArrayList) printf("subi %d %d len %d got %d\n",n,diff,data.length,res); + return res; + } + + // move index n by diff with wrapping + private size_t addi(size_t n, size_t diff) { + size_t res; + if (data.length - n <= diff) + res = diff - (data.length - n); + else + res = n + diff; + debug(dArrayList) printf("addi %d %d len %d got %d\n",n,diff,data.length,res); + return res; + } + + private size_t start, len; +} + +// helper structure for backwards() +struct ArrayListReverseIter(Value,bit ReadOnly, Alloc=GCAllocator) { + mixin MReverseImpl!(ArrayList!(Value,ReadOnly,Alloc)); +} + +//version = MinTLVerboseUnittest; +//version = MinTLUnittest; +version (MinTLUnittest) { + private import std.string; + private import std.random; + unittest { + version (MinTLVerboseUnittest) + printf("started mintl.arraylist unittest\n"); + + ArrayList!(int) x,y,z; + x.data = new int[10]; + x.add(5,3,4); + assert( x[0] == 5 ); + assert( x[1] == 3 ); + assert( x[2] == 4 ); + assert( x.length == 3 ); + x.takeTail(); + x ~= 4; + assert( x[2] == 4 ); + + y = x.dup; + + assert( x == y ); + + x.addHead(-1); + x.addHead(-2); + // private bug + // assert( x.start == x.data.length - 2 ); + assert( x.head == x[0 .. 1] ); + assert( x.length == 5 ); + assert( x.tail == x[4 .. 5] ); + assert( x.data[x.data.length-1] == -1); + assert( x.data[x.data.length-2] == -2); + assert( x.takeHead == -2 ); + assert( x.takeHead == -1 ); + assert( x[0] == 5 ); + assert( x[x.length-1] == 4 ); + assert( x.takeHead == 5 ); + assert( x.takeHead == 3 ); + assert( x.takeHead == 4 ); + assert( x.length == 0 ); + + assert( y.length == 3 ); + assert( y[0] == 5 ); + assert( y[2] == 4 ); + y ~= 6; + debug(dArrayList) printf("%d %d %d %d\n",y.start,y.tail_,y[0],y[3]); + y = y.reverse; + debug(dArrayList) printf("%d %d %d %d\n",y.start,y.tail_,y[0],y[3]); + assert( y[0] == 6 ); + assert( y[1] == 4 ); + assert( y[2] == 3 ); + assert( y[3] == 5 ); + + int[10] y2; + int k=0; + foreach(int val; y) { + y2[k++] = val; + } + assert( y2[0] == 6 ); + assert( y2[1] == 4 ); + assert( y2[2] == 3 ); + assert( y2[3] == 5 ); + + k=0; + foreach(int val; y.backwards()) { + y2[k++] = val; + } + assert( y2[0] == 5 ); + assert( y2[1] == 3 ); + assert( y2[2] == 4 ); + assert( y2[3] == 6 ); + + k=0; + foreach(size_t n, int val; y) { + y2[n] = val; + } + assert( y2[0] == 6 ); + assert( y2[1] == 4 ); + assert( y2[2] == 3 ); + assert( y2[3] == 5 ); + + k=0; + foreach(ArrayList!(int) itr; y) { + y2[k++] = itr[0]; + } + assert( y2[0] == 6 ); + assert( y2[1] == 4 ); + assert( y2[2] == 3 ); + assert( y2[3] == 5 ); + + ArrayList!(int) y3 = y[2..4]; + assert( y3.length == 2 ); + assert( y3[0] == 3 ); + assert( y3[1] == 5 ); + y3[0..1].swap(y3[1..2]); + assert( y3[0] == 5 ); + assert( y3[1] == 3 ); + + y3[0] = 10; + assert( y[2] == 10 ); + + y3.next(-1); + assert( y3.length == 2 ); + assert( y3[0] == 4 ); + assert( y3[1] == 10 ); + y3.next(-1,-1); + assert( y3.length == 3 ); + assert( y3[0] == 6 ); + assert( y3[2] == 10 ); + y3.next(1,1); + assert( y3.length == 4 ); + assert( y3[0] == 6 ); + assert( y3[3] == 3 ); + + ArrayList!(char[]) c = ArrayList!(char[]).make("a","a","a","a"); + assert( c.opIn("a") == c.head ); + assert( c.count("a") == 4 ); + for (int kk=0;kk<100;kk++) { + c ~= toString(kk); + c.takeHead(); + } + + // test addAfter, addBefore and remove + ArrayList!(double) w; + w.data = new double[30]; + for (int j=0;j<20;j++) + w ~= j; + w.remove(w[10..15]); + assert( w.length == 15 ); + assert( w[10] == 15 ); + for (int j=0;j<5;j++) + w.addHead(j); + w.remove(w[2..7]); + assert( w.length == 15 ); + ArrayList!(double) w2; + w2.data = new double[30]; + for (k=0;k<20;k++) + w2 ~= k; + w.addBefore(w[5..7],w2[10..15]); + assert( w.length == 20 ); + assert( w[0] == 4 ); + foreach( double d; w) { + version (MinTLVerboseUnittest) + printf(" %g",d); + } + version (MinTLVerboseUnittest) + printf("\n"); + assert( w[5] == 10 ); + + ArrayList!(int) cda = ArrayList!(int).make(20,30); + cda.capacity = 20; + assert( cda.capacity >= 20 ); + assert( cda.length == 2 ); + assert( cda.values == cda.data[0..2] ); + cda.length = 4; + assert( cda.length == 4 ); + assert( cda[cda.length - 1] == 0 ); + cda.capacity = 40; + assert( cda.length == 4 ); + assert( cda.data.length >= 40 ); + cda.addHead(40); + cda.addHead(50); + cda.capacity = 50; + uint ss = cda.capacity; + assert( cda.length >= 6 ); + assert( cda[0] == 50 ); + assert( cda[1] == 40 ); + assert( cda[2] == 20 ); + assert( cda[3] == 30 ); + assert( cda[4] == 0 ); + + ArrayList!(int,false,Malloc) xm = + ArrayList!(int,false,Malloc).make(10,20,30); + assert( xm.takeTail == 30 ); + assert( xm.takeHead == 10 ); + for (int u;u<10000;u++) { + xm ~= u; + } + xm.clear(); + assert( xm.isEmpty ); + + // test simple sorting + ArrayList!(int) s1; + s1.add(40,300,-20,100,400,200); + s1.sort(); + ArrayList!(int) s2 = ArrayList!(int).make(-20,40,100,200,300,400); + assert( s1 == s2 ); + + // test a large sort with default order + ArrayList!(double) s3; + for (k=0;k<1000;k++) { + s3 ~= 1.0*rand()/100000.0 - 500000.0; + } + ArrayList!(double) s4 = s3.dup; + s3.sort(); + for (k=0;k<999;k++) { + assert( s3[k] <= s3[k+1] ); + } + // test a large sort with custom order + int cmp(double*x,double*y){return *x>*y?-1:*x==*y?0:1;} + s4.sort(&cmp); + for (k=0;k<999;k++) { + assert( s4[k] >= s4[k+1] ); + } + + version (MinTLVerboseUnittest) + printf("finished mintl.arraylist unittest\n"); + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/deque.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/deque.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,920 @@ +/** \file deque.d + * \brief A resizable double-ended queue stored in blocks with + * constant time insertion at the front and tail. + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 2.7.1 + */ + +module mintl.deque; + +import mintl.mem; +private import mintl.share; // for ~ and ~= +private import mintl.sorting; + +private extern(C) void *memmove(void *, void *, uint); + +//debug = dDeque; // can also pass at command line + +/** \class Deque + * \brief A resizable double-ended queue stored in blocks with + * constant time insertion at the front and tail. + * + * A Deque!(Value) is a list of data of type Value backed by a + * block-allocated array. The size of the allocation blocks varies + * with the number of elements in the deque. The performance of Deques + * is on the same order as for arrays except adding an element to the + * head of a Deque is constant. + * + * The optional ReadOnly parameter Deque!(Value,ReadOnly) forbids + * operations that modify the container. The readonly() property returns + * a ReadOnly view of the container. + * + * The optional allocator parameter Deque!(Value,false,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct Deque(Value, bit ReadOnly = false, Alloc = GCAllocator) { + + alias Deque ContainerType; + alias Deque SliceType; + alias Value ValueType; + alias size_t IndexType; + alias ReadOnly isReadOnly; + + alias Value* Block; + const size_t psize = (void*).sizeof; + + invariant { + assert( total() == 0 || start < total() ); + assert( len <= total() ); + } + + /** Get a ReadOnly view of the container */ + .Deque!(Value, true, Alloc) readonly() { + .Deque!(Value, true, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get a read-write view of the container */ + .Deque!(Value, false, Alloc) readwrite() { + .Deque!(Value, false, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + static if (ReadOnly) { + /** Duplicates a deque. */ + /* private bug + Deque dup() { + .Deque!(Value,false,Alloc) res; + size_t cap = block(len)+1; + if (len == 0) return res.readonly; + static if (is(Alloc == GCAllocator)) { + res.data = new Block[cap]; + } else { + Block* p = cast(Block*)Alloc.malloc(cap * psize); + res.data = p[0..cap]; + res.data[] = null; + } + res.addTail(this.readwrite); + return res.readonly; + } + */ + } else { + + /** Appends an item to the tail of the deque. If the target deque is + * a slice call addAfter instead of addTail to insert an item + * after a slice. + */ + void addTail(Value v) { + capacity(len+1); + *plookup(addi(start,len)) = v; + len++; + } + + /** Appends a deque to the tail of the target deque. If the target + * deque is a slice call addAfter instead of addTail to insert + * another deque after a slice. + */ + void addTail(Deque v) { + size_t vlen = v.len; + if (vlen == 0) return; + capacity(len+vlen); + copyBlock(v, data, addi(start,len), vlen); + len += vlen; + } + + /** overload ~ and ~= */ + mixin MListCatOperators!(Deque); + + /** Removes and returns the tail item of the deque. If the target + * deque is empty an IndexOutOfBoundsException is thrown unless + * version=MinTLNoIndexChecking is set. + */ + Value takeTail() { + boundsCheck(len-1); + len--; + Value* pval = plookup(addi(start,len)); + Value val = *pval; + *pval = Value.init; + return val; + } + + /** Removes the tail item of the deque. */ + void removeTail() { + boundsCheck(len-1); + len--; + *plookup(addi(start,len)) = Value.init; + } + + /** Prepends an item to the head of the target deque. If the target + * deque is a slice call addBefore instead of addHead to insert an + * item before a slice. + */ + void addHead(Value v) { + capacity(len+1); + start = dec(start); + *plookup(start) = v; + len++; + } + + /** Prepends a deque to the head of the target deque. If the target + * deque is a slice call addBefore instead of addHead to insert a + * deque before a slice. + */ + void addHead(Deque v) { + size_t vlen = v.len; + if (vlen == 0) return; + capacity(len+vlen); + size_t newhead = subi(start,vlen); + copyBlock(v, data, newhead, vlen); + start = newhead; + len += vlen; + } + + /** Removes and returns the head item of the deque. If the target + * deque is empty an IndexOutOfBoundsException is thrown unless + * version=MinTLNoIndexChecking is set. + */ + Value takeHead() { + boundsCheck(len-1); + Value* pval = plookup(start); + start = inc(start); + Value val = *pval; + *pval = Value.init; + len--; + debug(dDeque) printf("%d %d\n",start,val); + return val; + } + + /** Removes the head item of the deque. */ + void removeHead() { + boundsCheck(len-1); + Value* pval = plookup(start); + start = inc(start); + len--; + *pval = Value.init; + } + + /** Insert a deque before a slice. */ + void addBefore(Deque subv, Deque v) { + size_t vlen = v.length; + if (vlen == 0) return; + capacity(len+vlen); + size_t tlen = subv.start >= start ? subv.start-start : total-start+subv.start; + size_t newhead = subi(start,vlen); + debug(dDeque)printf("about to moveBlockLeft %d\n",tlen); + moveBlockLeft(start,tlen,newhead); + copyBlock(v,data,subi(subv.start,vlen),vlen); + start = newhead; + len += vlen; + } + + /** Insert a deque after a slice. */ + void addAfter(Deque subv, Deque v) { + size_t vlen = v.length; + if (vlen == 0) return; + capacity(len+vlen); + size_t tail = addi(start,len); + size_t subtail = addi(subv.start,subv.len); + size_t tlen = subtail <= tail ? tail-subtail : total-subtail+tail; + moveBlockRight(subtail,tlen,addi(subtail,vlen)); + copyBlock(v,data,subtail,vlen); + len += vlen; + } + + /** Clear all contents. */ + void clear() { + static if (is(Alloc == GCAllocator)) { + } else { + foreach (Block b; data) { + Alloc.gcFree(b); + } + if (data.ptr) + Alloc.free(data.ptr); + } + *this = Deque.init; + } + + /** Set the nth item in the deque from head. Indexing out of bounds + * throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + void opIndexAssign(Value val, size_t n) { + boundsCheck(n); + *plookup(addi(start,n)) = val; + } + + /** Set the value of one-item slice (more generally the head value). */ + void value(Value newValue) { + opIndexAssign(newValue,0); + } + + /** Removes a slice from the deque. */ + void remove(Deque sublist) { + size_t tail = addi(start,len); + size_t slen = sublist.len; + size_t stail = addi(sublist.start,slen); + size_t tlen = stail <= tail ? tail-stail : data.length-stail+tail; + debug(dArrayList) printf("remove %d %d\n",sublist.start, sublist.length); + moveBlockLeft(stail, tlen, sublist.start); + fillBlock(subi(tail,slen),slen,Value.init); + len -= slen; + } + + /** Removes an item from the list and returns the value, if present. */ + Value take(size_t index) { + Deque item = opSlice(index, index+1); + Value val = item[0]; + remove(item); + return val; + } + + /** Removes an item from the deque if present. */ + void remove(size_t index) { + Deque item = opSlice(index, index+1); + remove(item); + } + + /** Reverse a deque in-place. */ + Deque reverse() { + size_t tlen = len / 2; + size_t a,b; + a = start; + b = dec(addi(start,len)); + TypeInfo ti = typeid(Value); + for (size_t k = 0; k < tlen; k++) { + ti.swap(plookup(a),plookup(b)); + a = inc(a); + b = dec(b); + } + return *this; + } + + /** Duplicates a deque. */ + Deque dup() { + Deque res; + if (len == 0) return res; + size_t cap = block(len)+1; + static if (is(Alloc == GCAllocator)) { + res.data = new Block[cap]; + } else { + Block* p = cast(Block*)Alloc.malloc(cap * psize); + res.data = p[0..cap]; + res.data[] = null; + } + res.addTail(*this); + return res; + } + + } // !ReadOnly + + /** Move a slice towards the tail by n items. If n is + * negative the slice moves towards the head. A positive end is + * the tail, negative the head and 0 is both. By default moves to + * to the next item. + */ + void next(int n = 1, int end = 0) { + if (end) + len += n<0?-n:n; + if (end <= 0) { + if (n<0) { + start = subi(start,-n); + } else { + start = addi(start,n); + } + } + } + + /** Get the length of deque. */ + size_t length() { + return len; + } + + /** Test if container is empty. */ + bool isEmpty() { + return len == 0; + } + + /** Get the nth item in the deque from head. Indexing out of bounds + * throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + Value opIndex(size_t n) { + boundsCheck(n); + return *plookup(addi(start,n)); + } + + // lookup an index and return a pointer to the slot + private Value* plookup(size_t n) { + debug(dDeque) printf("plookup for %d block %d offset %d blocklen %d\n", + n,block(n),offset(n),data.length); + debug(dDeque) printf(" plookup got %p\n", data[block(n)]); + size_t bn = block(n); + // if (bn >= data.length) bn -= data.length; + Block b = data[bn]; + if (b is null) + data[bn] = b = newBlock();; + return b+offset(n); + } + + // allocate a new block + private Block newBlock() { + static if (is(Alloc == GCAllocator)) { + return (new Value[BlockSize]).ptr; + } else { + Value* p = cast(Value*)Alloc.gcMalloc(BlockSize * Value.sizeof); + Value[] q = p[0..BlockSize]; + q[] = Value.init; + return p; + } + } + + /** Get the value of one-item slice (more generally the head value). + * Useful for expressions like x.tail.value or x.head.value. */ + Value value() { + return opIndex(0); + } + + // helper function to check if the index is legal + private void boundsCheck(size_t n) { + version (MinTLNoIndexChecking) { + } else { + if (n >= len) { + throw new IndexOutOfBoundsException(); + } + } + } + + /** Get deque contents as dynamic array. */ + Value[] values() { + Value[] res = new Value[len]; + foreach(size_t k, Value val; *this) + res[k] = val; + return res; + } + + /** Test for equality of two deques. */ + int opEquals(Deque c) { + if (len !is c.len) + return 0; + size_t a,b; + a = start; + b = c.start; + TypeInfo ti = typeid(Value); + for (size_t k = 0; k < len; k++) { + Value* bn = c.data[block(b)]+offset(b); + if (!ti.equals(plookup(a),bn)) + return 0; + a = inc(a); + b = inc(b); + } + return 1; + } + + /** Compare two lists. */ + int opCmp(Deque c) { + size_t tlen = len; + if (tlen > c.len) + tlen = c.len; + size_t a,b; + a = start; + b = c.start; + TypeInfo ti = typeid(Value); + for (size_t k = 0; k < tlen; k++) { + Value* bn = c.data[block(b)]+offset(b); + int cmp = ti.compare(plookup(a),bn); + if (cmp) + return cmp; + a = inc(a); + b = inc(b); + } + return cast(int)len - cast(int)c.len; + } + + /** Create a slice from index a to b (exclusive). */ + Deque opSlice(size_t a, size_t b) { + Deque res; + res.data = data; + res.start = addi(start,a); + res.len = b-a; + return res; + } + + /** Create a slice from the head of a to the tail of b (inclusive). */ + Deque opSlice(Deque a, Deque b) { + Deque res; + res.data = data; + res.start = a.start; + if (b.start >= a.start) + res.len = b.start - a.start + b.len; + else + res.len = data.length - a.start + b.len + b.start; + return res; + } + + /** Create a one-item slice of the head. */ + Deque head() { + return opSlice(0,1); + } + + /** Create a one-item slice of the tail. */ + Deque tail() { + return opSlice(len-1,len); + } + + /** Iterates over the deque from head to tail calling delegate to + * perform an action. The value is passed to the delegate. + */ + int opApplyNoKeyStep(int delegate(inout Value x) dg,int step=1){ + int dg2(inout size_t n, inout Value x) { + return dg(x); + } + return opApplyWithKeyStep(&dg2,step); + } + + /** Iterates over the deque from head to tail calling delegate to + * perform an action. The index from 0 and the value are passed + * to the delegate. + */ + int opApplyWithKeyStep(int delegate(inout size_t n, inout Value x) dg, + int step = 1){ + if (len == 0) return 0; + int res = 0; + size_t tail = addi(start,len); + size_t istart = step>0 ? start : dec(tail); + size_t iend = step>0 ? tail : dec(start); + size_t n = step>0 ? 0 : len-1; + for (size_t k = istart; k != iend;) { + res = dg(n,data[block(k)][offset(k)]); + if (res) break; + if (step < 0) + k = subi(k,-step); + else + k = addi(k,step); + n += step; + } + return res; + } + + /** Iterates over the deque from head to tail calling delegate to + * perform an action. A one-item slice is passed to the delegate. + */ + int opApplyIterStep(int delegate(inout Deque n) dg, int step = 1){ + Deque itr; + itr.data = data; + itr.len = 1; + int dg2(inout size_t n, inout Value x) { + itr.start = addi(start,n); + return dg(itr); + } + return opApplyWithKeyStep(&dg2,step); + } + + /** Iterate backwards over the deque (from tail to head). + * This should only be called as the + * iteration parameter in a foreach statement + */ + DequeReverseIter!(Value,ReadOnly,Alloc) backwards() { + DequeReverseIter!(Value,ReadOnly,Alloc) res; + res.list = this; + return res; + } + + /** Helper functions for opApply */ + mixin MOpApplyImpl!(Deque); + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + alias opApplyIter opApply; + + Deque getThis(){return *this;} + mixin MListAlgo!(Deque, getThis); + mixin MRandomAccessSort!(Deque, getThis); + + /** Get a pointer to the nth item in the deque from head. Indexing + * out of bounds throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + Value* lookup(size_t n) { + boundsCheck(n); + return plookup(addi(start,n)); + } + + // Helper functions + + // compute the block number for an index + private size_t block(size_t n) { + return n >> BlockShift; + } + + // compute the offset within a block for an index + private size_t offset(size_t n) { + return n & BlockMask; + } + + /** Ensure the minimum capacity of list. */ + void capacity(size_t cap) { + cap = block(cap)+1; + if (data.length <= cap) { + cap = cap*2; + debug(dDeque) printf("growing capacity from %d to %d\n",data.length, cap); + if (start + len > total) { + size_t oldlen = data.length; + size_t offs = cap-oldlen; + size_t h = block(start); + resizeData(cap); + memmove(&data[h+offs],&data[h],(oldlen-h)*psize); + if (h == block(start+len)%data.length) { + static if (is(Alloc == GCAllocator)) { + data[h+offs] = data[h+offs][0..BlockSize].dup.ptr; + } else { + Block p = newBlock(); + p[0 .. BlockSize] = data[h+offs][0 .. BlockSize]; + data[h+offs] = p; + } + data[h][offset(start) .. BlockSize] = Value.init; + data[h+offs][0 .. offset(start+len)] = Value.init; + data[h+1 .. h+offs] = null; + } else { + data[h .. h+offs] = null; + } + start += offs*BlockSize; + } else { + resizeData(cap); + } + } + } + + // helper for capacity + private void resizeData(size_t cap) { + static if (is(Alloc == GCAllocator)) { + data.length = cap; + } else { + Block* p = data.ptr; + p = cast(Block*)Alloc.realloc(p,cap*psize); + p[data.length .. cap] = null; + data = p[0 .. cap]; + } + } + + /** Get the capacity of list. */ + size_t capacity() { + return total(); + } + + private const size_t BlockShift = Value.sizeof>128 ? 1 : 7; + private const size_t BlockSize = 1 << BlockShift; + private const size_t BlockMask = BlockSize - 1; + + // Helper functions + + // helper function to copy sections of the backing buffer + private void moveBlockLeft(size_t srchead, size_t len, size_t desthead) { + size_t ns = srchead; + size_t nd = desthead; + debug(dDeque)printf("moveBlockLeft %d\n",len); + while (len > 0) { + size_t sz = len; + size_t offs = offset(ns); + size_t offd = offset(nd); + size_t bn = block(ns); + Block srcblock = data[bn]; + if (srcblock == null) + data[bn] = srcblock = newBlock(); + bn = block(nd); + Block destblock = data[bn]; + if (destblock == null) + data[bn] = destblock = newBlock(); + if (offs+sz > BlockSize) + sz = BlockSize-offs; + if (offd+sz > BlockSize) + sz = BlockSize-offd; + assert(sz != 0); + memmove(&destblock[offd],&srcblock[offs],sz*Value.sizeof); + ns = addi(ns,sz); + nd = addi(nd,sz); + len -= sz; + } + } + + // helper function to copy sections of the backing buffer + private void moveBlockRight(size_t srchead, size_t len, size_t desthead) { + size_t ns = addi(srchead,len-1)+1; + size_t nd = addi(desthead,len-1)+1; + while (len > 0) { + size_t sz = len; + size_t bn = block(ns); + size_t offs = offset(ns); + size_t offd = offset(nd); + Block srcblock = data[bn]; + if (srcblock == null) + data[bn] = srcblock = newBlock(); + bn = block(nd); + Block destblock = data[bn]; + if (destblock == null) + data[bn] = destblock = newBlock(); + if (offs < sz) + sz = offs; + if (offd < sz) + sz = offd; + assert(sz != 0); + memmove(&destblock[offd],&srcblock[offs],sz*Value.sizeof); + ns = dec(subi(ns,sz))+1; + nd = dec(subi(nd,sz))+1; + len -= sz; + debug(dDeque)printf("moveBlockRight %d\n",sz); + } + } + + // helper function to copy sections of the backing buffer + private void copyBlock(Deque src, + Block[] destdata, + uint desthead, + uint len) { + Block[] srcdata = src.data; + int srchead = src.start; + int ns = srchead; + int nd = desthead; + while (len > 0) { + int sz = len; + size_t offs = offset(ns); + size_t offd = offset(nd); + size_t bn = block(ns); + Block srcblock = srcdata[bn]; + if (srcblock == null) + srcdata[bn] = srcblock = newBlock(); + if (offs+sz > BlockSize) + sz = BlockSize-offs; + bn = block(nd); + Block destblock = destdata[bn]; + if (destblock == null) + destdata[bn] = destblock = newBlock(); + if (offd+sz > BlockSize) + sz = BlockSize-offd; + assert(sz != 0); + memmove(&destblock[offd],&srcblock[offs],sz*Value.sizeof); + ns = src.addi(ns,sz); + nd = addi(nd,sz); + len -= sz; + debug(dDeque)printf("copyBlock %d\n",sz); + } + } + + // helper function to fill a section of the backing array + private void fillBlock(size_t srchead, size_t len, Value val) { + size_t ns = srchead; + while (len > 0) { + size_t sz = len; + size_t bn = block(ns); + size_t off = offset(ns); + Block block = data[bn]; + if (block == null) + data[bn] = block = newBlock(); + if (off+sz > BlockSize) + sz = BlockSize-off; + assert(sz != 0); + block[off .. off+sz] = val; + ns = addi(ns,sz); + len -= sz; + debug(dDeque)printf("fillBlock %d\n",sz); + } + } + + // move index n by 1 with wrapping + private size_t inc(size_t n) { + return (n == total()-1) ? 0 : n+1; + } + + // move index n by -1 with wrapping + private size_t dec(size_t n) { + return (n == 0) ? total()-1 : n-1; + } + + // move index n by -diff with wrapping + private size_t subi(size_t n, size_t diff) { + size_t res; + if (n < diff) + res = total() - diff + n; + else + res = n - diff; + return res; + } + + // move index n by diff with wrapping + private size_t addi(size_t n, size_t diff) { + size_t res; + if (total() - n <= diff) { + res = diff - (total() - n); + } else + res = n + diff; + return res; + } + + private size_t total(){ return data.length << BlockShift; } + + private Block[] data; // array of blocks of data + private size_t start, len; +} + +// helper structure for backwards() +struct DequeReverseIter(Value,bit ReadOnly,Alloc) { + mixin MReverseImpl!(Deque!(Value,ReadOnly,Alloc)); +} + +//version = MinTLVerboseUnittest; +//version = MinTLUnittest; +version (MinTLUnittest) { + private import std.string; + private import std.random; + unittest { + version (MinTLVerboseUnittest) + printf("started mintl.deque unittest\n"); + + Deque!(int) x,y,z; + x.addTail(22); + x.addTail(33); + assert( x[0] == 22 ); + assert( x[1] == 33 ); + x.addHead(11); + assert( x[0] == 11 ); + assert( x[2] == 33 ); + + y = x.dup; + + assert( y.length == 3 ); + assert( y[0] == 11 ); + assert( y[2] == 33 ); + z = x.dup; + z.addTail(y); + assert( z.length == 6 ); + assert( z[0] == 11 ); + assert( z[2] == 33 ); + assert( z[3] == 11 ); + assert( z[4] == 22 ); + assert( z[5] == 33 ); + + Deque!(int,false,Malloc) mx; + mx.add(30,40,50); + assert( mx.takeHead == 30 ); + assert( mx.takeTail == 50 ); + for(int u = 0;u<10000;u++) { + mx~=u; + } + mx.clear(); + assert( mx.isEmpty ); + + x = x.init; + x ~= 5; + x ~= 3; + x ~= 4; + assert( x[0] == 5 ); + assert( x[1] == 3 ); + assert( x[2] == 4 ); + assert( x.length == 3 ); + + x.reverse(); + assert( x[2] == 5 ); + assert( x[1] == 3 ); + assert( x[0] == 4 ); + + y = x.dup; + + assert( x == y ); + + y.addHead(6); + + int[10] y2; + int k=0; + foreach(int val; y) { + y2[k++] = val; + } + assert( y2[0] == 6 ); + assert( y2[1] == 4 ); + assert( y2[2] == 3 ); + assert( y2[3] == 5 ); + + int[] w2 = y.values; + assert( w2[0] == 6 ); + assert( w2[1] == 4 ); + assert( w2[2] == 3 ); + assert( w2[3] == 5 ); + assert( w2.length == 4 ); + + k=0; + foreach(int val; y.backwards()) { + y2[k++] = val; + } + assert( y2[0] == 5 ); + assert( y2[1] == 3 ); + assert( y2[2] == 4 ); + assert( y2[3] == 6 ); + k=0; + foreach(size_t n, int val; y) { + y2[n] = val; + } + assert( y2[0] == 6 ); + assert( y2[1] == 4 ); + assert( y2[2] == 3 ); + assert( y2[3] == 5 ); + k=0; + foreach(Deque!(int) itr; y) { + y2[k++] = itr[0]; + } + assert( y2[0] == 6 ); + assert( y2[1] == 4 ); + assert( y2[2] == 3 ); + assert( y2[3] == 5 ); + + Deque!(int) y3 = y[2..4]; + assert( y3.length == 2 ); + assert( y3[0] == 3 ); + assert( y3[1] == 5 ); + + y3[0] = 10; + assert( y[2] == 10 ); + + Deque!(char[]) c; + c ~= "a"; + c ~= "a"; + c ~= "a"; + c ~= "a"; + assert( c.opIn("a") == c.head ); + assert( c.count("a") == 4 ); + for (int kk=3;kk<6000;kk++) { + c ~= toString(kk); + c ~= toString(kk+1); + char[] res = c.takeHead(); + if (kk > 10) { + assert( res == toString(kk/2) ); + } + } + + // test addAfter, addBefore and remove + Deque!(double) w; + for (k=0;k<20;k++) + w ~= k; + w.remove(w[10..15]); + assert( w.length == 15 ); + assert( w[10] == 15 ); + for (k=0;k<5;k++) + w.addHead(k); + w.remove(w[2..7]); + assert( w.length == 15 ); + Deque!(double) w3; + for (k=0;k<20;k++) + w3 ~= k; + w.addBefore(w[5..7],w3[10..15]); + assert( w.length == 20 ); + assert( w[0] == 4 ); + foreach( double d; w) { + version (MinTLVerboseUnittest) + printf(" %g",d); + } + version (MinTLVerboseUnittest) + printf("\n"); + assert( w[5] == 10 ); + + // test sorting + Deque!(int) s1,s2; + s1.add(40,300,-20,100,400,200); + s1.sort(); + s2.add(-20,40,100,200,300,400); + assert( s1 == s2 ); + + Deque!(double) s3; + for (k=0;k<1000;k++) { + s3 ~= 1.0*rand()/100000.0 - 500000.0; + } + s3.sort(); + for (k=0;k<999;k++) { + assert( s3[k] <= s3[k+1] ); + } + + version (MinTLVerboseUnittest) + printf("finished mintl.deque unittest\n"); + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/hashaa.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/hashaa.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,752 @@ +/** \file hashaa.d + * \brief A hash-based associative array that maintains elements in insertion order + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 2.7.1 + */ + +module mintl.hashaa; + +//debug = dHashAA; // can also pass at command line + +private { + import mintl.share; + import mintl.sorting; + import mintl.mem; +} + +/** \class HashAA + * \brief A hash-based associative array traversed in insertion order. + * + * A HashAA!(Key,Value) represents an associative array with keys of + * type Key and values of type Value that maintains the inserted items + * in a linked list sorted by insertion order. If key1 is + * inserted into the array before key2 then key1 + * will appear before key2 in foreach statements and in + * iterator traversals. + * + * The optional ReadOnly parameter HashAA!(Key,Value,ReadOnly) forbids + * operations that modify the container. The readonly() property returns + * a ReadOnly view of the container. + * + * The optional allocator parameter ArrayList!(Value,false,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct HashAA(Key,Value, bit ReadOnly = false, Alloc = GCAllocator) { + + alias HashAA ContainerType; + alias HashAA SliceType; + alias Value ValueType; + alias Key IndexType; + alias Key SortType; + alias ReadOnly isReadOnly; + + /** Get the kays in the array. The operation is O(n) where n is the number of + * elements in the array. + */ + Key[] keys() { + Key[] res; + if (head_ is null) return res; + res.length = length; + size_t n = 0; + foreach(Key k,Value v;*this) { + res[n++] = k; + } + return res; + } + + /** Get the values in the array. The operation is O(n) where n is + * the number of elements in the array. + */ + Value[] values() { + Value[] res; + if (head_ is null) return res; + res.length = length; + size_t n = 0; + foreach(Key k,Value v;*this) { + res[n++] = v; + } + return res; + } + + /** Property for the default value of the array when a key is missing. */ + void missing(Value val) { + if (data.length == 0) + initDataArray(); + data[0].val = val; + } + Value missing() { + if (data.length == 0) + return Value.init; + return data[0].val; + } + + /** Length of array. The operation is O(n) where n is the number of + * elements in the array. + */ + size_t length() { + if (head_ is null) return 0; + if (head_.prev is null && tail_.next is null) return dlength(); + Node* t = head_; + int n = 1; + while (t !is null && t !is tail_) { + t = t.next; + ++n; + } + return n; + } + + /** Return true if array is empty. */ + bool isEmpty() { + return head_ is null; + } + + private void initDataArray() { + size_t s = prime_list[0]+1; + static if (is(Alloc == GCAllocator)) { + data.length = s; + } else { + Node** p = cast(Node**)Alloc.malloc((Node*).sizeof*s); + data = p[0 .. s]; + } + data[0] = allocNode; + data[0].len = 0; + } + + private enum {InsertOnMiss, ThrowOnMiss, NullOnMiss} + + // helper functions for indexing. + private Node** getNode(Key key, int failureAction) { + Node* t; + TypeInfo ti = typeid(Key); + uint hash = ti.getHash(&key); + if (data.length == 0) { + switch (failureAction) { + case InsertOnMiss: + initDataArray(); + break; + case ThrowOnMiss: + GetActionThrow: + throw new IndexOutOfBoundsException("Key not in container"); + case NullOnMiss: + return null; + } + } + uint i = (hash % (data.length-1))+1; + Node**p = &data[i]; + while (*p !is null) { + if ((*p).hash == hash && ti.equals(&(*p).key,&key)) { + // found key + return p; + } + p = &(*p).nextHash; + } + if (failureAction == ThrowOnMiss) { + goto GetActionThrow; + } else if (failureAction == NullOnMiss) { + return null; + } + // lookup Node + *p = t = allocNode(); + t.hash = hash; + t.key = key; + if (head_ is null) { + head_ = t; + tail_ = t; + } else { + link(tail_,t); + tail_ = t; + } + data[0].len++; + static if (!ReadOnly) { + if (data[0].len > .75*data.length) { + this.rehash(); + p = getNode(key,NullOnMiss); + } + } + return p; + } + + /** Find the element with a given key and return a pointer to the + * value. If the key is not in the array null is returned or if + * throwOnMiss is true an exception is thrown. The target array can + * be a sub-array though the key may fall outside of the sub-array + * range. + */ + Value* get(Key key, bool throwOnMiss = false) { + Node** t = getNode(key,throwOnMiss ? ThrowOnMiss : NullOnMiss); + if (t) + return &(*t).val; + else + return null; + } + + /** Create a sub-array from key a to b (exclusive). */ + HashAA opSlice(Key a, Key b) { + HashAA res; + res.head_ = *getNode(a,ThrowOnMiss); + res.tail_ = (*getNode(b,ThrowOnMiss)).prev; // will at least have a in there + res.data = data; + return res; + } + + /** Create a sub-array from the first key in a to the last key in b (inclusive). */ + HashAA opSlice(HashAA a, HashAA b) { + HashAA res; + res.head_ = a.head_; + res.tail_ = b.tail_; + res.data = data; + return res; + } + + /** Get a ReadOnly view of the container */ + .HashAA!(Key,Value,true,Alloc) readonly() { + .HashAA!(Key,Value,true,Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get a read-write view of the container */ + .HashAA!(Key,Value,false,Alloc) readwrite() { + .HashAA!(Key,Value,false,Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + static if (ReadOnly) { + /** Duplicates the array. The operation is O(n) where n is length. */ + /* private bug + HashAA dup() { + .HashAA!(Key,Value,false) res; + res.data.length = data.length; + res.data[0] = cast(res.Node*)allocNode; + res.data[0].len = 0; + res.missing = missing; + foreach(Key k,Value v;*this) + res[k] = v; + return res.readonly; + } + */ + } else { + + /** Clear all contents. */ + void clear() { + static if (is(Alloc == GCAllocator)) { + } else { + foreach ( Node* t; data) { + while (t) { + Node* next = t.nextHash; + Alloc.gcFree(t); + t = next; + } + } + Alloc.free(data.ptr); + } + *this = HashAA.init; + } + + /** Duplicates the array. The operation is O(n) where n is length. */ + HashAA dup() { + HashAA res; + res.data.length = data.length; + res.data[0] = allocNode; + res.data[0].len = 0; + res.missing = missing; + foreach(Key k,Value v;*this) { + res[k] = v; + } + return res; + } + + /** Rehash the array. */ + HashAA rehash() { + uint k; + uint len = data.length; + if (len == 0) return *this; + for (k=0;k len) + break; + } + Node* n = data[0]; + size_t s = prime_list[k]+1; + static if (is(Alloc == GCAllocator)) { + data = new Node*[s]; + } else { + Node** p = cast(Node**)Alloc.malloc((Node*).sizeof * s); + data = p[0 .. s]; + } + data[0] = n; + Node* t = head_; + while (t) { + uint i = (t.hash %(data.length-1))+1; + t.nextHash = data[i]; + data[i] = t; + t = t.next; + } + return *this; + } + + /** Find a key in the array and return a pointer to the associated value. + * Insert the key and initialize with Value.init if the key is not + * in the array. + */ + Value* put(Key key) { + debug (dHashAA) printf("put %d\n",key); + Node* t = *getNode(key, InsertOnMiss); + return &t.val; + } + + /** Store a value with a key, overwriting any previous value. The + * target array can be a sub-array though the key may fall outside of the + * sub-array range. + */ + void opIndexAssign(Value val, Key key) { + Node* t = *getNode(key, InsertOnMiss); + t.val = val; + } + + // helper for remove/take + private Node* takeHelper(Key key) { + Node** p = getNode(key,NullOnMiss); + if (!p) return null; + Node* n = *p; + if (n is head_) + head_ = n.next; + if (n is tail_) + tail_ = n.prev; + link(n.prev, n.next); + *p = n.nextHash; + return n; + } + + /** Remove a key from the array. The target array can be a sub-array though + * the key may fall outside of the sub-array range. + */ + void remove(Key key) { + Node* n = takeHelper(key); + if (n) { + static if (is(Alloc == GCAllocator)) { + static if (Node.sizeof < AllocBlockCutoff) { + n.next = data[0].next; + data[0].next = n; + n.prev = null; + n.val = Value.init; + n.key = Key.init; + } + } else { + Alloc.gcFree(n); + } + data[0].len--; + } + } + + /** Remove the value stored with the given key and return it, if present. + * If not present return the missing default. + */ + Value take(Key key) { + Node* n = takeHelper(key); + if (!n) return missing; + Value val = n.val; + static if (is(Alloc == GCAllocator)) { + static if (Node.sizeof <= AllocBlockCutoff) { + n.next = data[0].next; + data[0].next = n; + n.val = Value.init; + n.key = Key.init; + n.prev = null; + } + } else { + Alloc.gcFree(n); + } + data[0].len--; + return val; + } + + /** Remove a sub-array from the array. The operation is O(max(log(m),n)) + * where m is the size of the target array and n is the number of + * elements in the sub-array. + */ + void remove(HashAA subarray) { + if (subarray.head_ is subarray.tail_) { + remove(subarray.key); + } else { + Key[] keylist = subarray.keys; + foreach(Key key;keylist) + remove(key); + } + } + + mixin MAddAA!(HashAA); // mixin add function + + } // !ReadOnly + + private void link(Node* a, Node* b) { + if (a) a.next = b; + if (b) b.prev = a; + } + + // remove extra capacity + void trim() { + if (data.length > 0 && data[0]) + data[0].next = null; + } + + // Parameters for controlling block allocations + private const int AllocBlockSize = 10; // number of nodes in block + private const int AllocBlockCutoff = 96; // max node size to allow blocks + + private Node* allocNode() { + Node* p; + static if (is(Alloc == GCAllocator)) { + static if (Node.sizeof > AllocBlockCutoff) { + return new Node; + } else { + if (data[0] is null) return new Node; + p = data[0].next; + if (p) { + data[0].next = p.next; + p.next = null; + return p; + } + p = (new Node[AllocBlockSize]).ptr; + for (int k=1;k 0) { + if (end >= 0) + doNext(tail_,n); + if (end <= 0) + doNext(head_,n); + } else { + n = -n; + if (end >= 0) + doPrev(tail_,n); + if (end <= 0) + doPrev(head_,n); + } + } + + /** Test for equality of two arrays. The operation is O(n) where n + * is length of the array. + */ + int opEquals(HashAA c) { + Node* i = head_; + Node* j = c.head_; + Node* end = tail_; + Node* cend = c.tail_; + TypeInfo ti_k = typeid(Key); + TypeInfo ti_v = typeid(Value); + int do_test(Node*p1,Node*p2) { + if (!ti_k.equals(&p1.key,&p2.key)) + return 0; + if (!ti_v.equals(&p1.val,&p2.val)) + return 0; + return 1; + } + while (i !is null && j !is null) { + if (!do_test(i,j)) + return 0; + if (i is end || j is cend) { + return (i is end && j is cend); + } + i = i.next; + j = j.next; + } + return (i is null && j is null); + } + + /** Test if a key is in the array. The target array can be a sub-array + * but the key may fall outside of the sub-array range. + */ + bool contains(Key key) { + return get(key) !is null; + } + + /** Test if a key is in the array and set value if it is. */ + bool contains(Key key,out Value value) { + Value* node = get(key); + if (node) + value = *node; + return node !is null; + } + + /** Iterate over the array calling delegate to perform an action. A + * one-element sub-array is passed to the delegate. + */ + int opApplyNoKeyStep(int delegate(inout Value val) dg, int step = 1) { + int dg2(inout HashAA itr) { + Value value = itr.value; + return dg(value); + } + return opApplyIterStep(&dg2,step); + } + + /** Iterate over the array calling delegate to perform an action. A + * one-element sub-array is passed to the delegate. + */ + int opApplyWithKeyStep(int delegate(inout Key key, inout Value val) dg, + int step = 1) { + int dg2(inout HashAA itr) { + Key key = itr.key; + Value value = itr.value; + return dg(key,value); + } + return opApplyIterStep(&dg2,step); + } + + /** Iterate over the array calling delegate to perform an action. A + * one-element sub-array is passed to the delegate. + */ + int opApplyIterStep(int delegate(inout HashAA itr) dg,int step=1) { + int res = 0; + HashAA itr; + Node* x = step>0?head_:tail_; + Node* end = step>0?tail_:head_; + while (x !is null) { + itr.head_ = itr.tail_ = x; + res = dg(itr); + if (res || x is end) return res; + x = step>0?x.next:x.prev; + } + return res; + } + + /** Iterate backwards over the array (from last to first key). The target + * array can be a sub-array. This should only be called as the + * iteration parameter in a foreach statement + */ + LAReverseIter!(Key,Value,ReadOnly,Alloc) backwards() { + LAReverseIter!(Key,Value,ReadOnly,Alloc) res; + res.list = this; + return res; + } + + /** Helper functions for opApply */ + mixin MOpApplyImpl!(HashAA); + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + alias opApplyIter opApply; + + Node* getHead(){return head_;} + Node* getTail(){return tail_;} + mixin MSequentialSort!(HashAA, getHead,getTail); + void sort(int delegate(Key*a, Key*b) cmp = null) { + Node* newhead, newtail; + dosort(newhead,newtail,cmp); + head_ = newhead; + tail_ = newtail; + } + + private { + struct Node { + Node* next, prev, nextHash; + union { + uint len; + uint hash; + } + Key key; + Value val; + Key* sortLookup(){return &key;} + } + Node*[] data; + Node* head_, tail_; + } + + private uint dlength() { return data[0].len; } + + // size primes from aaA.d and planetmath.org + private static uint[] prime_list = + [97u, 389u, 1543u, 6151u, + 24593u, 98317u, 393241u, 1572869u, + 6291469u, 25165843u, 100663319u, 402653189u, + 1610612741u, 4294967291u + ]; +} + +// internal helper struct for backwards iteration +struct LAReverseIter(Key,Value,bit ReadOnly,Alloc) { + mixin MReverseImpl!(HashAA!(Key,Value,ReadOnly,Alloc)); +} + +//version = MinTLVerboseUnittest; +//version = MinTLUnittest; +version (MinTLUnittest) { + private import std.random; + unittest { + version (MinTLVerboseUnittest) + printf("starting mintl.hashaa unittest\n"); + + HashAA!(int,int) m; + m[4] = 100; + m[-10] = 200; + m[17] = 300; + assert( m.length == 3 ); + assert( m[-10] == 200 ); + + HashAA!(int,int) mm; + mm.add(4,100, -10,200, 17,300); + assert( m == mm ); + + // test foreach + int[] res; + res.length = 3; + int n=0; + foreach(int val; m) { + res[n++] = val; + } + assert( res[0] == 100 ); + assert( res[1] == 200 ); + assert( res[2] == 300 ); + + // test removing an item + m.remove(-10); + n = 0; + foreach(int val; m) { + res[n++] = val; + } + assert( res[0] == 100 ); + assert( res[1] == 300 ); + + // test assigning to an item already in array + m[22] = 400; + m[17] = 500; + n = 0; + foreach(int val; m) { + res[n++] = val; + } + assert( res[0] == 100 ); + assert( res[1] == 500 ); + assert( res[2] == 400 ); + + // test backwards foreach + n = 0; + foreach(int k,int val; m.backwards()) { + res[n++] = val; + } + assert( res[0] == 400 ); + assert( res[1] == 500 ); + assert( res[2] == 100 ); + + // test slicing + HashAA!(int, int) m2 = + HashAA!(int,int).make(400,4,100,1,500,5,300,3, + 200,2,600,6); + HashAA!(int, int) m3; + m3 = m2[500 .. 600]; + assert( m3.length == 3 ); + n = 0; + foreach(int k,int val; m3) { + res[n++] = val; + } + assert( res[0] == 5 ); + assert( res[1] == 3 ); + assert( res[2] == 2 ); + + // test keys + int[] keys = m3.keys; + assert( keys[0] == 500 ); + assert( keys[1] == 300 ); + assert( keys[2] == 200 ); + + // test rehash + for (int k=0; k<1000; k++) + m3[k] = k; + HashAA!(int,int) m4 = m3.rehash; + assert( m4 == m3 ); + + // test simple sorting + HashAA!(int,int) s1,s12; + s1.add(40,1,300,2,-20,3,100,4,400,5,200,6); + s12 = s1.dup; + s1.sort(); + assert( s1 == HashAA!(int,int).make(-20,3,40,1,100,4,200,6,300,2,400,5) ); + // sort a slice in-place + HashAA!(int,int) slice1 = s12[300 .. 200]; + slice1.sort(); + assert( s12 == HashAA!(int,int).make(40,1,-20,3,100,4,300,2,400,5,200,6)); + + // test a large sort with default order + HashAA!(double,int) s3; + for (int k=0;k<1000;k++) { + s3[1.0*rand()/100000.0 - 500000.0] = k; + } + HashAA!(double,int) s4 = s3.dup; + s3.sort(); + double[] keys2 = s3.keys; + for (int k=0;k<999;k++) { + assert( keys2[k] <= keys2[k+1] ); + } + // test a large sort with custom order + int cmp(double*x,double*y){return *x>*y?-1:*x==*y?0:1;} + s4.sort(&cmp); + keys2 = s4.keys; + for (int k=0;k<999;k++) { + assert( keys2[k] >= keys2[k+1] ); + } + + version (MinTLVerboseUnittest) + printf("finished mintl.hashaa unittest\n"); + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/index.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/index.html Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,1781 @@ + Minimal Template Library for D + +

MinTL

+MinTL is a "minimal template library" of containers for the D +programming language. For more info about D see DigitalMars D home page. The +downloads are the Core Library and +the MinTL Concurrent Library +(mintlc web page), which includes +a dependent Synchronization Library. +The current version is 2.7.1. +

+This library is in the public domain. +Written by +Ben Hinkle, 2004. +Email comments and bug reports to ben.hinkle@gmail.com +

+

Contents

+Overview
+List Containers
+Associative Containers
+Slicing
+Foreach traversals
+Sorting
+Allocators
+Unmodifiable Containers
+Examples
+API Reference by module
+ + +

Overview

+ +The philosophy of the library is to be as simple and minimal as +possible: + + +
  • The design is simple by keeping the number of classes to a +minimum and reusing concepts from builtin dynamic and associative +arrays. For example a slice of a container has the same type as the +container, just as the slice of a dynamic array is another dynamic +array. + +
  • +The memory footprint and the garbage generation is kept to a minimum +by relying on structs instead of classes and by implementing slicing +and traversals without allocating dynamic memory. Some containers +also recycle nodes. For example when the head or tail of a list is removed +the node is retained and reused the next time an item is added +to the head or tail. Optional Allocator parameters allow custom memory +management. + +
  • Closely related data structures share common naming conventions +and adapters reuse fundamental data structures like arrays, linked-lists +and sorted associative arrays for stacks, queues and sets. +Performance can be tuned for different uses by either choose +between several variations (eg. a linked list, a circular array or a +deque) or by supplying optional constructor arguments. + + +

    + +MinTL has the following containers +

    + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
    List containers
    container implementation file brief
    List + doubly linked list + list.d + sortable linked list with "previous" and "next" pointers +
    CircularList + circular doubly linked list + list.d + doubly linked list where the head and tail are linked +
    SList + singly linked list + slist.d + linked list with only "next" pointers +
    CircularSList + circular singly linked list + slist.d + singly linked list where the tail points to the head +
    ArrayList + circular array + arraylist.d + sortable list backed by a resizable circular array +
    Deque + circular block-allocated array + deque.d + list backed by a resizable block-allocated circular array +
    ArrayHeap + heap + arrayheap.d + complete binary tree backed by an array +
    Stack + adapter + stack.d + adapts a list container to be a stack +
    ArrayStack + ArrayList + stack.d + wraps an ArrayList with the stack adapter +
    Queue + adapter + queue.d + adapts a list container to be a queue +
    ArrayQueue + ArrayList + queue.d + wraps an ArrayList with the queue adapter +
    PriorityQueue + ArrayHeap + queue.d + wraps an ArrayHeap with the queue adapter +
    +

    + + + + + + + + + + + + + + + + + + + + + +
    Associative containers
    container implementation file brief
    HashAA + linked hash table + hashaa.d + sortable associative array with nodes ordered by insertion order +
    SortedAA + red-black tree + sortedaa.d + sorted associative array
    Set + adapter + set.d + adapts an associative container to be a set +
    SortedSet + SortedAA + set.d + wraps a SortedAA with the set adapter +
    MultiSet + adapter + set.d + adapts an associative container to be a set with repeats +
    SortedMultiSet + SortedAA + set.d + wraps a SortedAA with the multi-set adapter +
    MultiAA + adapter + multiaa.d + adapts an associative container to hold repeated keys +
    SortedMultiAA + SortedAA + multiaa.d + wraps a SortedAA with the multi-aa adapter +
    +

    + +The module mintl.array defines helper functions for builtin dynamic +and associative arrays. + + +

    Build and Install

    +To use MinTL first unpack the library in a directory on the D compiler +search path. There are pre-built debug and non-debug versions of the library. +To enable flexible add() datatype support uncomment the +version=WithBox statement in mintl.share and recompile MinTL. +To use std.boxer in a debug build you must also rebuild phobos with +debugging. +If you wish to rebuild MinTL enter the mintl directory and type +make -f win32.mak or make -f linux.mak. +In your source code import the desired modules and compile each +container used and the mintl static library into the application. +If a concurrent container is needed download the mintlc +sub-package and link that library and +the Locks library into the +application. For example on Linux to compile the program app.d +
    +import mintl.list;
    +
    +int main() {
    +  List!(int) list = List!(int).make(10,20,30);
    +  return 0;
    +}
    +
    +run in the directory above mintl the command +
    +  dmd app.d mintl/libmintl_debug.a
    +
    +to build with asserts or +
    +  dmd app.d -release mintl/libmintl.a
    +
    +to build without asserts. +On Windows run +
    +  dmd app.d mintl\mintl_debug.lib
    +
    +or +
    +  dmd app.d -release mintl\mintl.lib
    +
    +If the mintl directory is not in the current directory then use the -I flag +to add it to the search path +
    +  dmd app.d -Ipath_to_mintl path_to_mintl/mintl/libmintl.a
    +
    +or modify the dmd\bin\sc.ini file (on Windows) or dmd.conf (on Linux) +to include the paths to mintl. For example if MinTL is unpacked in the +directory C:\d on Windows then sc.ini should be modified to include C:\d +in the include path and C:\d\mintl on the library search path: +
    +LIB="%@P%\..\lib";\dm\lib;C:\d\mintl
    +DFLAGS="-I%@P%\..\src\phobos";C:\d
    +
    +On Linux the static library can be put in a standard location like +/usr/lib if desired. + + +

    List Containers

    + +The list containers List, SList, +CircularList, CircularSList, ArrayList, +Deque, ArrayHeap and the concurrent queues +and stacks share a naming convention +for adding and removing items. The head is the +first item in the container and the tail is the last item. +All list containers support constant-time access to the head +and tail. +The speed of accessing the length property depends on the +container. Array-based containers have constant-time access to length, +the linked-list containers have constant-time unless an operation +modifies the list to have unknown length, in which case the next +time the length is computed it is cached again. The singly-linked +lists have linear-time length access and it is not cached. +

    +Some containers maintain nodes past the head and tail +of the list as extra capacity. To trim off any extra capacity +most containers support a trim function. +

    +The circular lists +CircularList and CircularSList are the same as the non-circular +versions except that slicing a circular list returns a non-circular +list and node are not reused when adding or removing items. However +circular lists are useful when the objects being modeled do not have a +natural unique definition of a head or tail. +

    +An ArrayList can also be used as a dynamic array with +managed capacity. Set the capacity property or allocate an array +with the desired capacity +and leave the head of the arraylist at 0. The arraylist will +automatically grow the capacity as required. + +

    To add items to a container call add with any number of +items. For example +

    +  List!(int) x,y,z;
    +  y.add(10,20,30);
    +  z.add(50,60,70);
    +  x = y; x ~= 40; x ~= z; x ~= 80;
    +
    +results in the following linked list +
    + x[0],y[0]           y[2]              z[0]              z[2]     x[7]
    +    10  <->  20  <->  30  <->  40  <->  50  <->  60  <->  70  <->  80
    +
    +To add a single item or list call addTail or use +one of the concatenation operators. Some containers also support adding +items or lists at the head using addHead or at a position +in the interior of the list using addBefore or addAfter. +To create a list in an expression use the static make function +For example, +
    +  List!(int) x;
    +  x = List!(int).make(10,20,30) ~ List!(int).make(50,60,70);
    +
    + +

    To remove items call one of the take or +remove functions. +All list containers support removeHead to remove +the head of the list and takeHead to remove and return +the stored value, if any. +Some containers also support takeTail and +removeTail to remove the tail and remove +to remove a slice. + +

    +Stacks and queues are implemented as adapters of a list +container. By default they use a Deque as the backing container. +Stacks define aliases push for add +and pop for takeTail. Queues define an alias +take for takeHead (the function add is used +to add to the end of a queue). For example, +

    +  Stack!(char[]) x;
    +  x.push("first","second");
    +  assert( x.pop == "second" );
    +  assert( x.pop == "first" );
    +
    +  Queue!(char[]) x;
    +  x.add("first","second");
    +  assert( x.take == "first" );
    +  assert( x.take == "second" );
    +
    +A PriorityQueue is an ArrayHeap wrapped with the Queue adapter. To +set a custom comparison function access the impl property of the +adapter: +
    +  PriorityQueue!(char[]) x;
    +  x.impl.compareFcn = &fcn;
    +  x.add("first","second");
    +
    +

    +The following table outlines the advantages and disadvantages of +each list container + + + + + + + + + + + + + + + + + + + +
    container advantages disadvantages
    List + O(1) insertion at head/tail or before/after slices + O(n) access to middle of list +
    SList + O(1) insertion at head/tail or after slices; less overhead +than List + O(n) access to middle or near end of list +
    ArrayList + O(1) insertion at head/tail. O(1) access to any index + O(n) insertion in middle +
    Deque + O(1) insertion at head/tail. O(1) access to any index. +Block allocated. + O(n) insertion in middle; non-contiguous storage +
    ArrayHeap + maintains items in semi-sorted order; O(log(n)) add/remove. + only allows addTail and takeHead +
    + +
    +

    Associative Containers

    + +The associative containers SortedAA,HashAA, and +ConcurrentAA are similar to builtin associative arrays but +with extra capabilities. The SortedAA maintains the keys in +some specific order as determined by a comparison function. By +default the keys are ordered by the type's default comparison +function. To specify a custom comparison function assign to the +compareFcn property. The HashAA maintains the keys +in insertion order, meaning if an indexing expression using key +x is evaluated before an indexing expression using key +y then x is traversed before y in +foreach traversals. Assigning to a key already in the array +does not change the insertion order. The other associative array +properties dup, length, keys and +values are also implemented. + +

    +Elements are inserted or modified using the add function or +using indexing lvalue expressions +and retrieved using indexing rvalue expressions. To test if a key is in +the array use the overloaded contains functions. +An indexing expression that is not an assignment will return a +default missing value. The missing value defaults to Value.init +but can be set by assigning to the missing property. +The functions get and put allow more flexibility in handling +missing keys by allowing the user to either return null, throw or +insert. +To remove an item call the remove function. Both HashAA +and SortedAA maintain a freelist of removed nodes for future +reuse. To release the freelist for garbage collection call trim. +

    +For example to define a sorted associative +array with three entries associating "first" with 10, "second" with +20 and "third" with 30 type +

    +  SortedAA!(int,char[]) x;
    +  x.add(10,"first", 20,"second", 30,"third");
    +
    +or equivalently, +
    +  SortedAA!(int,char[]) x;
    +  x[10] = "first";
    +  x[20] = "second";
    +  x[30] = "third";
    +
    +To create an associative array in an expression use the static make function +For example, +
    +  foo(SortedAA!(int,char[]).make(10,"first",20,"second",30,"third"));
    +
    + +

    +The number of elements in an associative container is computed by +the length property. + +

    +Sets and multi-associative-arrays are implemented as adapters of an +associative container. +By default sets use a HashAA as the backing container. +Use add +to add items to a set and use an indexing expression +to check if an item is in the set. For example, +

    +  Set!(char[]) x;
    +  x.add("first","second","third");
    +  assert( x["first"] );
    +  assert( x["second"] );
    +  assert( x["third"] );
    +  assert( !x["fourth"] );
    +
    +  MultiSet!(char[]) mx;
    +  xm.add("first","second","first","third","second");
    +  xm.remove("first");
    +  assert( x["first"] );
    +
    +  MultiAA!(int,char[]) y;
    +  y.add(10,"first",20,"second",10,"third");
    +  assert( y[10].length == 2 );
    +
    + +
    +

    Slicing

    + +In general slicing a container behaves like slicing a dynamic +array. For example, slicing between two indices in a List creates +another List with the head at the first index and the tail at the +element before the second index. The contents of the slice is shared +with the original list so assigning new values to elements in the list +will be visible in the oringal list. The resulting slice, or +sub-list, can be traversed using "foreach", duplicated, indexed into, +etc just like a slice of a dynamic array can be treated as a +"first-class" dyamic array. The following diagram illustrates the +relationships for x and y if +x is a list with 6 items and +y is the slice x[2..4].
    + +
    +   x[0]            y[0]    y[1]           x[5]
    +    0  <->  1  <->  2  <->  3  <->  4  <->  5
    +
    +Executing z = y.dup would result in +
    +   z[0]    z[1]
    +    2  <->  3 
    +
    +

    +One should be careful when resizing or writing to a slice. For example +do not (in general) append or prepend item to a sub-list using the addTail or addHead +functions or remove items using removeTail and removeHead unless the +original list is no longer needed. To insert an item or list at a +certain location create a slice with the head at the desired location +and call addBefore or create a slice with the tail at the desired +location and call addAfter. To remove a portion of a list create a +slice and call remove. Again one should always insert and remove from +the original list otherwise any variable referring to the original list +will become out of sync. +

    +A sub-list can be moved towards the head or tail +of the original list by calling the next function. +This allows a sub-list to traverse up and down the original list efficiently. +Continuing the example from above, executing y.next(-1) would result +in +

    +   x[0]    y[0]    y[1]                   x[5]
    +    0  <->  1  <->  2  <->  3  <->  4  <->  5
    +
    +and then executing x.remove(y) would result in +
    +   x[0]                    x[3]
    +    0  <->  3  <->  4  <->  5
    +
    +   y[0]    y[1]
    +    1  <->  2 
    +
    +The performance of inserting and removing from the interior +of an ArrayList or Deque can be significantly worse than that of a List +if the slices are near the middle of the container. + +

    +The SortedAA slicing behavior is designed to chose slices without modifying +the underlying container. The functions from and to +can find a one-item slice starting from or up to a given key. +For example if words is a sorted associative array indexed by +char[] then +

    +    words["a" .. "b"]
    +
    +or, equivalently, +
    +    words[words.from("a") .. words.to("b")]
    +
    +is a slice containing all the items with keys that start with the character "a" +even if the strings "a" and "b" aren't in the container. + +
    +

    Foreach

    +Containers and slices of containers can be traversal in +foreach statements +by value, key-value pairs and one-element slices. Some containers +support moving a slice up and down the container. For these containers +a slice can be used for the same purposes as an iterator in C++ or +Java. +

    +Each container also supports backwards traversals by calling +backwards in a foreach statement. For example, +

    +  List!(int) x;
    +  ...
    +  foreach( int val; x.backwards() )
    +    printf("%d ",val);
    +
    +will print out the contents of x from tail to head. +Backwards traversals do not allocate any dynamic memory. + +
    +

    Sorting

    +MinTL supports sorting containers in two forms. The SortedAA +is a sorted associative container that maintains its elements in a +given sorted order at all times. The comparison delegate +used to determine the element order must be specified +before the first element is insert or the key's default comparison +function will be used and it cannot be changed during the lifetime +of the container. The SortedSet +and SortedMultiAA are derived from SortedAA and +have the same sorting semantics. +

    +The other form of sorting is through calling the sort +methods of the containers ArrayList, Deque, List, +and HashAA or by using the sort template in +mintl.array to sort a dynamic array. These sort methods +take an optional comparison delegate. The default comparison +delegate is the sorting type's default comparison function. For +the list-like containers the sorting type is the value type of +the container. For HashAA the sorting type is the key +type. Sorting is done in-place and slices are preserved relative +to their surrounding container. For example, the following code +creates a short linked list, sorts and slice and compares it +with the expected end result: +

    +    List!(int) list;
    +    list.add(40,300,-20,100,400,200);
    +    list[1 .. 5].sort();    // sort a slice in-place
    +    assert( list == List!(int).make(40,-20,100,300,400,200));
    +
    +

    +Sorting a container does not change the behavior of adding new elements. +The sorting operation is performed once and the comparison function +is not remembered by the container or used in any other way. For example +sorting a HashAA which was previously maintained in insertion +order will sort the elements but adding any new elements will add them +to the end of the traversal order in insertion order again. + + +

    Allocators

    +Most containers accept an optional Allocator parameter to +customize memory management. The default allocator is the +GCAllocator which indicates to the container that the garbage +collector should be used for all allocations. If a custom allocator +is supplied the container will call the memory management functions in +the allocator to allocate and free memory. Users who supply a +non-garbage-collecting allocator need to call clear when done +with a container so that the memory can be released. +

    + +An allocator is a type containing 8 symbols malloc, calloc, realloc, +free and the corresponding GC-aware versions gcMalloc, gcCalloc, +gcRealloc and gcFree. Containers will call the GC-aware functions on +blocks that may hold roots and otherwise will call the regular +functions. Allocators are expected to throw an OutOfMemory +exception if the allocation fails. +

    + +The two predefined allocators Malloc and MallocNoRoots use +std.c.stdlib.malloc to perform allocations. The MallocNoRoots ignores +any requests by the container to register roots with the GC. The +MallocNoRoots allocator should only be used with containers that the +user knows will never contain any roots. For example, +

    +  ArrayList!(int,MallocNoRoots) x;
    +  x.add(10,20,30);
    +  ...
    +  x.clear();
    +
    + +
    +

    Unmodifiable Containers

    +The ReadOnly template parameter makes a container +unmodifiable. A read-only container does not have operations that add or +remove or change elements. However the underlying data is shared with +the original modifiable container so a read-only container only +guarantees that the elements will not be modified by that particular +view of the container. +A slice of a read-only container is also read-only. +The readonly property creates a read-only view of a container. +The readwrite property creates a read-write view. +For example +
    +  void foo(List!(int,ReadOnly) y) { ... }
    +  List!(int) x;
    +  x.add(10,20,30);
    +  foo(x.readonly);
    +
    + + +

    Examples

    +The source files have examples and unittests +that one can use to get a feel for the behavior. The following example +walks through some uses of MinTL: +Create a list of the integers 0 through 10 +
    +  List!(int) x;
    +  x.add(0,1,2,3,4,5,6,7,8,9,10);
    +
    +and print out the items 5 though 8 +
    +  foreach(int val; x[5..9])
    +    printf("%d ",val);
    +
    +to output +
    +  5 6 7 8
    +
    +Assigning x to another variable y shares +the underlying list contents, so assigning through y +is reflected in x: +
    +  List!(int) y = x;
    +  y[0] = 100;
    +  assert( x[0] == 100 );
    +
    +When passing a container to a function that could add or remove +elements from the container be sure to use "inout" parameters +to be sure the original variable in the calling frame is +properly updated. +

    + + +

    API Reference

    +This section lists the public structs and functions in MinTL without +detailed explanation. For more information see the documentation before +the function or struct in the source file. Template functions are +written as +
     return-type fcn-name!(tmpl-param,...)(arg1, arg2,...);
    +
    +to mimic how it would appear in user code. The API is organized by +module:
    +
    +
    mintl.array +
    mintl.arrayheap +
    mintl.arraylist +
    mintl.deque +
    mintl.hashaa +
    mintl.list +
    mintl.mem +
    mintl.multiaa +
    mintl.queue +
    mintl.set +
    mintl.share +
    mintl.slist +
    mintl.sortedaa +
    mintl.stack +
    + + +

    mintl.array

    +
    +
    void reserve!(Value[])(inout Value[] x, size_t n); +
    Reserve capacity for a dynamic array +
    DArrayReverseIter backwards!(Value[])(Value[] x); +
    Reverse dynamic array "foreach" traversal +
    void sort!(Value[])(Value[] data, int delegate(Value* x, Value* y) cmp = null); +
    Sort the array in increasing order as defined by the given comparison +delegate. If no delegate is supplied the default comparison function of the +Value type is used. +
    + + +

    mintl.arrayheap

    +
    +
    struct ArrayHeap(Value, Alloc = GCAllocator) +
    A heap (complete binary tree) backed by an array. x[n] is greater than +or equal to x[2*n+1] and x[2*n+2]. x[0] is the greatest item. +An optional allocator can customize memory management. The default allocator +is GCAllocator. +

    +

    +
    Value[] data; +
    Backing array +
    size_t length; +
    Return length of heap +
    alias int delegate(Value* a, Value* b) CompareFcn; +
    Signature of comparison functions +
    void compareFcn(CompareFcn cmp); +
    Set the comparison function +
    bool isEmpty +
    Return true if container is empty +
    Value opIndex(size_t n); +
    Return nth item where the head is item 0. +
    void opIndexAssign(Value val, size_t n); +
    Assign to the nth item +
    Value[] values; +
    Get heap contents as dynamic array slice of backing array +
    void add(...); +
    Add to heap +
    void vadd(TypeInfo[] ti, void* argptr); +
    Add to heap using va_arg inpurs +
    void addTail(Value v); +
    Add to heap +
    Value takeHead(); +
    Remove and return first item (greatest item) +
    void removeHead(); +
    Remove first item (greatest item) +
    Value* lookup(size_t n); +
    Return a pointer to the nth item +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal by values +
    int opApply(int delegate(inout size_t n, inout Value x) dg); +
    Foreach traversal by index-value pairs +
    ArrayHeap dup; +
    Duplicate array heap by duplicating backing array +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    int opEquals(ArrayHeap c); +
    Test heap equality +
    alias ArrayHeap ContainerType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    Aliases for container types +
    +
    + + +

    mintl.arraylist

    +
    +
    struct ArrayList(Value, bit ReadOnly = false, Alloc = GCAllocator) +
    A list backed by an array. An ArrayList can also be used as +a dynamic array with managed capacity. The backing array is resized +when more space is required. +Compile with version=MinTLNoIndexChecking to disable bounds checking. +The optional ReadOnly parameter disallows container modifications. +The optional allocator customizes memory management. The default allocator +is GCAllocator. +

    +

    +
    Value[] data; +
    Backing array +
    mixin MListCat(ArrayList) +
    Mixin list catenation. +
    mixin MListAlgo(this,ArrayList) +
    Mixin list algorithms. +
    MListCommon(ArrayList) +
    Implement common list members. +
    size_t length +
    Read/write property to return or set the length of the list. +
    size_t capacity +
    Read/write property for the minimum capacity of the backing array. The +capacity is the maximum number of elements the array can hold without +requiring a reallocation of the backing array. +
    Value[] array; +
    Get list contents as dynamic array slice of the backing array assuming +the list is contiguous. +
    ArrayListReverseIter!(Value) backwards(); +
    Backwards traversal for "foreach" +
    ArrayList!(Value,true,Alloc) readonly; +
    Property that returns a read-only view of the container. +
    ArrayList!(Value,false,Alloc) readwrite; +
    Property that returns a read-write view of the container. +
    void sort(int delegate(Value* x, Value* y) cmp = null); +
    Sort the list in increasing order as defined by the given comparison +delegate. If no delegate is supplied the default comparison function of the +Value type is used. +
    alias ArrayList ContainerType; +
    alias ArrayList SliceType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    alias ReadOnly isReadOnly; +
    Aliases for container types +
    +
    + + +

    mintl.deque

    +
    +
    struct Deque(Value, bit ReadOnly = false, Alloc = GCAllocator) +
    A double-ended queue backed by a circular block-allocated array +Compile with version=MinTLNoIndexChecking to disable bounds checking. +The optional ReadOnly parameter disallows container modifications. +The optional allocator customizes memory management. The default allocator +is GCAllocator. +

    +

    +
    mixin MListCat(Deque) +
    Mixin list catenation. +
    mixin MListAlgo(this,Deque) +
    Mixin list algorithms. +
    MListCommon(Deque) +
    Implement common list members. +
    size_t length; +
    Return length of deque. +
    DequeReverseIter!(Value) backwards(); +
    Backwards traversal for "foreach" +
    Deque!(Value,true,Alloc) readonly; +
    Property that returns a read-only view of the container. +
    Deque!(Value,false,Alloc) readwrite; +
    Property that returns a read-write view of the container. +
    void sort(int delegate(Value* x, Value* y) cmp = null); +
    Sort the list in increasing order as defined by the given comparison +delegate. If no delegate is supplied the default comparison function of the +Value type is used. +
    alias Deque ContainerType; +
    alias Deque SliceType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    alias ReadOnly isReadOnly; +
    Aliases for container types +
    +
    + + +

    mintl.hashaa

    +
    +
    struct HashAA(Key,Value,bit ReadOnly = false, Alloc = GCAllocator) +
    An associative array linked by insertion order. +The optional ReadOnly parameter disallows container modifications. +The optional allocator customizes memory management. The default allocator +is GCAllocator. +

    +

    +
    void add(...); +
    Add key-value pairs to array +
    void vadd(TypeInfo[] ti, void* argptr); +
    Add using va_arg inpurs +
    static HashAA make(...) +
    Consruct a HashAA using add(...) +
    size_t length; +
    Return number of items in the array. +
    bool isEmpty +
    Return true if array is empty +
    Value* get(Key key, bit throwOnMiss = false); +
    Return a pointer to the value stored at the key. If the key is not +in the array then null is returned or if throwOnMiss is true an +exception is thrown. +
    Value* put(Key key) +
    Return a pointer to the value stored at the key and insert the +key with value Value.init if the key is not in the array. +
    bool contains(Key key) +
    Returns true if the array contains the key +
    bool contains(Key key, out Value value) +
    Returns true if the array contains the key and sets the out value if +present. +
    Value opIndex(Key key); +
    Return item with given key. Returns the default missing value if not present. +
    void opIndexAssign(Value val, Key key); +
    Assign a value to the given key +
    Value missing +
    Read/write property for the value to use on indexing a key not in +the array. Defaults to Value.init +
    HashAA opSlice(Key a, Key b); +
    Slice from item a to b (exclusive) +
    HashAA opSlice(HashAA a, HashAA b); +
    Slice from first key in a to last key in b +
    HashAA head +
    Return one-item slice of the head +
    HashAA tail +
    Return one-item slice of the tail +
    void next(int n = 1, int end = 0); +
    Move the head and tail to the next item. If n is negative move to +the previous item. If end <= 0 move the head of the slice and if +end >= 0 move the tail of the slice. +
    void remove(Key key); +
    Remove a key from array if present. The node used for key is reused in +future insert actions. +
    Value take(Key key); +
    Remove a key from array if present and return value. Returns the +default missing value if the key was not present. +
    void remove(HashAA subarray); +
    Remove a slice from array +
    Value[] values; +
    Get values as a dynamic array. The values are in insertion order. +
    Key[] keys; +
    Get keys as a dynamic array. The keys are in insertion order. +
    void reserve(size_t n); +
    Reserve a capacity for the array +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal by values +
    int opApply(int delegate(inout Key key, inout Value x) dg); +
    Foreach traversal by key-value pairs +
    int opApply(int delegate(inout HashAA n) dg); +
    Foreach traversal by one-item slices +
    HashAA dup; +
    Duplicate array +
    void clear; +
    Clear contents. Only needed if a non-GCAllocator is used. +
    void trim; +
    Remove references to extra nodes kept for reuse +
    int opEquals(HashAA c); +
    Test array equality +
    HashAAReverseIter!(Key,Value) backwards(); +
    Backwards traversal for "foreach" +
    HashAA rehash; +
    Rehash array to be more efficient +
    Value value +
    Return value of a one-item slices +
    Key key; +
    Return key of a one-item slices +
    HashAA!(Key,Value,true) readonly; +
    Property that returns a read-only view of the container. +
    HashAA!(Key,Value,false) readwrite; +
    Property that returns a read-write view of the container. +
    void sort(int delegate(Key* x, Key* y) cmp = null); +
    Sort the HashAA in increasing order as defined by the given comparison +delegate. If no delegate is supplied the default comparison function of the +Key type is used. Future insertions are added in insertion order at +the end of the traversal order. +
    alias HashAA ContainerType; +
    alias HashAA SliceType; +
    alias Value ValueType; +
    alias Key IndexType; +
    alias ReadOnly isReadOnly; +
    Aliases for container types +
    + +
    + +

    mintl.list

    +
    +
    struct List(Value, bit ReadOnly = false, Alloc = GCAllocator) +
    A doubly-linked list. +Compile with version=MinTLNoIndexChecking to disable bounds checking. +The optional ReadOnly parameter disallows container modifications. +The optional allocator customizes memory management. The default allocator +is GCAllocator. +

    +

    +
    mixin MListCat(List) +
    Mixin list catenation. +
    mixin MListAlgo(this,List) +
    Mixin list algorithms. +
    MListCommon(List) +
    Implement common list members. +
    size_t length; +
    Return length of list. +
    void trim; +
    Remove references to extra nodes kept for reuse +
    ListReverseIter!(Value) backwards(); +
    Backwards traversal for "foreach" +
    List!(Value,true,Alloc) readonly; +
    Property that returns a read-only view of the container. +
    List!(Value,false,Alloc) readwrite; +
    Property that returns a read-write view of the container. +
    void sort(int delegate(Value* x, Value* y) cmp = null); +
    Sort the list in increasing order as defined by the given comparison +delegate. If no delegate is supplied the default comparison function of the +Value type is used. +
    alias List ContainerType; +
    alias List SliceType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    alias ReadOnly isReadOnly; +
    Aliases for container types +
    +
    +

    + + +

    +
    struct CircularList(Value, bit ReadOnly = false, Alloc = GCAllocator) +
    A circular doubly-linked list. +Compile with version=MinTLNoIndexChecking to disable bounds checking. +The optional ReadOnly parameter disallows container modifications. +The optional allocator customizes memory management. The default allocator +is GCAllocator. +

    +

    +
    mixin MListCat(CircularList) +
    Mixin list catenation. +
    mixin MListAlgo(this,CircularList) +
    Mixin list algorithms. +
    MListCommon(CircularList) +
    Implement common list members. +
    size_t length; +
    Return length of list. +
    List toList; +
    Return the list as a non-circular List +
    void rotate(int n = 1); +
    Rotate the list by n steps (backwards if n is negative) +
    CircularListReverseIter!(Value) backwards(); +
    Backwards traversal for "foreach" +
    CircularList!(Value,true,Alloc) readonly; +
    Property that returns a read-only view of the container. +
    CircularList!(Value,false,Alloc) readwrite; +
    Property that returns a read-write view of the container. +
    alias CircularList ContainerType; +
    alias List!(Value,Alloc) SliceType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    alias ReadOnly isReadOnly; +
    Aliases for container types +
    +
    + + +

    mintl.mem

    +
    +
    void* mallocWithCheck(size_t s) +
    Call std.c.stdlib.malloc and throw OutOfMemory if fails. +
    void* callocWithCheck(size_t n, size_t s) +
    Call std.c.stdlib.calloc and throw OutOfMemory if fails. +
    void* reallocWithCheck(void* p, size_t s) +
    Call std.c.stdlib.realloc and throw OutOfMemory if fails. +
    void dfree(void* p) +
    Call free. +
    void* gcMalloc(size_t s) +
    Call mallocWithCheck and register range with GC. +
    void* gcCalloc(size_t n, size_t s) +
    Call callocWithCheck and register range with GC. +
    void* gcRealloc(void* p, size_t s) +
    Call reallocWithCheck and register range with GC. +
    void gcFree(void* p) +
    Remove range and call free. +

    + + +

    struct GCAllocator +
    The default allocator that indicates the garbage collector +should be used for memory management. +
    struct Malloc +
    An allocator that uses malloc for memory requests and registers +blocks with the GC when requested by the container. +
    struct MallocNoRoots +
    An allocator that uses malloc for memory requests and ignores requests +to register blocks with the GC. Use this allocator only when you know the +container will not contain any roots. +
    + + + +

    mintl.multiaa

    +
    +
    struct MultiAA!(Key,Value, ImplType = HashAA!(Key,Value[])) +
    An associative array which allows keys to be repeated. +Adapted from a customizable container type mapping keys to Value[]. +

    +

    +
    ImplType impl +
    Read-write property holding the backing container +
    void add(...); +
    Add key-value pairs to the container +
    void vadd(TypeInfo[] ti, void* argptr); +
    Add using va_arg inpurs +
    static MultiAA make(...) +
    Consruct a MultiAA using add(...) +
    void addItem(Key key, Value item); +
    Add item to container. +
    size_t length; +
    Return number of items in the container. +
    bool isEmpty +
    Return true if container is empty. +
    Value[] opIndex(Key key); +
    Return the values for a given key. +
    void remove(Key key, Value value); +
    Remove an item from the container if present. +
    void remove(Key key); +
    Remove all the values with a given key if present. +
    Key[] keys; +
    Get keys as a dynamic array. Duplicates are removed. +
    Value[][] values; +
    Get values as a dynamic array. +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal of items in the container. If an item is repeated it +is passed multiple times consecutively to the delegate. +
    int opApply(int delegate(inout Key key, inout Value x) dg); +
    Foreach traversal of items in the container. If an item is repeated it +is passed multiple times consecutively to the delegate. +
    MultiAA dup; +
    Duplicate container +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    int opEquals(MultiAA c); +
    Test container equality +
    alias MultiAA ContainerType; +
    alias Value ValueType; +
    alias Key IndexType; +
    alias ImplType AdaptType; +
    const bit isReadOnly = ImplType.isReadOnly; +
    Aliases for container types +
    +

    + +

    alias SortedMultiAA!(Key,Value) +
    An alias for MultiAA!(Key,Value,SortedAA!(Key,Value[])) to implement a +sorted multi-aa. +
    + + +

    mintl.queue

    +
    +
    struct Queue!(Value, ImplType = Deque!(Value)) +
    A queue of items adapted from a customizable list container type. The +default backing container is a Deque. +

    +

    +
    ImplType impl +
    Read-write property holding the backing container. +
    alias addTail put; +
    Alias to add items to the tail of the queue. +
    alias takeHead take; +
    Alias to take items to the head of the queue. +
    Value peek +
    Return the head of the queue or Value.init if empty. +
    mixin MListCat(Queue) +
    Mixin list catenation. +
    size_t length; +
    Return length of queue. +
    bool isEmpty +
    Return true if container is empty +
    Value opIndex(size_t n); +
    Return nth item where the head is item 0. +
    void opIndexAssign(Value val, size_t n); +
    Assign to the nth item +
    void addTail(Value v); +
    Add to tail of queue +
    void addTail(Queue v); +
    Append v to tail of queue +
    Value takeHead(); +
    Remove and return first item +
    void removeHead(); +
    Remove first item +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal by values +
    int opApply(int delegate(inout size_t n, inout Value x) dg); +
    Foreach traversal by index-value pairs +
    Queue dup; +
    Duplicate queue. +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    int opEquals(Queue c); +
    Test queue equality +
    int opCmp(Queue c); +
    Compare queues +
    alias Queue ContainerType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    alias ImplType AdaptType; +
    const bit isReadOnly = ImplType.isReadOnly; +
    Aliases for container types +
    +

    + +

    alias ArrayQueue!(Value) +
    An alias for Queue!(Value,ArrayList!(Value)) to adapt an ArrayList +to the queue interface. +

    + +

    alias PriorityQueue!(Value) +
    An alias for Queue!(Value,ArrayHeap!(Value)) to adapt an ArrayHeap +to the queue interface. + +
    + + +

    mintl.set

    +
    +
    struct Set!(Value, ImplType = HashAA!(Value,uint)) +
    A set of unique items adapted from a customizable container type +mapping items to 0 or 1. The default backing container type is a +builtin associative array. +

    +

    +
    ImplType impl +
    Read-write property holding the backing container +
    void add(...); +
    Add items to set +
    void vadd(TypeInfo[] ti, void* argptr); +
    Add using va_arg inpurs +
    static Set make(...) +
    Consruct a Set using add(...) +
    void addItem(Value item); +
    Add item to set +
    size_t length; +
    Return number of items in the set. +
    bool isEmpty +
    Return true if set is empty +
    bool opIndex(Value item); +
    Return true if the item is in the set +
    void remove(Value item); +
    Remove an item from the set if present +
    Value[] values; +
    Get items as a dynamic set. +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal of items in the set +
    Set dup; +
    Duplicate set +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    int opEquals(Set c); +
    Test set equality +
    alias Set ContainerType; +
    alias Value ValueType; +
    alias ImplType AdaptType; +
    const bit isReadOnly = ImplType.isReadOnly; +
    Aliases for container types +
    +

    + +

    alias SortedSet!(Value) +
    An alias for Set!(Value,SortedAA!(Value,uint)) to implement a sorted set. +

    + +

    struct MultiSet!(Value, ImplType = HashAA!(uint,Value)) +
    A set which allows items to be repeated. Adapted from a customizable +container type mapping items to repeat counts. +

    +

    +
    ImplType impl +
    Read-write property holding the backing container +
    void add(...); +
    Add items to set +
    void vadd(TypeInfo[] ti, void* argptr); +
    Add using va_arg inpurs +
    static MultiSet make(...) +
    Consruct a MultiSet using add(...) +
    void addItem(Value item); +
    Add item to set +
    size_t length; +
    Return number of items in the set. +
    bool isEmpty +
    Return true if set is empty +
    bool opIndex(Value item); +
    Return true if the item is in the set +
    void remove(Value item); +
    Remove an item from the set if present +
    Value[] values; +
    Get items as a dynamic set. Duplicates are removed. +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal of items in the set. If an item is repeated it +is passed multiple times consecutively to the delegate. +
    MultiSet dup; +
    Duplicate set +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    int opEquals(MultiSet c); +
    Test set equality +
    alias MultiSet ContainerType; +
    alias Value ValueType; +
    alias ImplType AdaptType; +
    const bit isReadOnly = ImplType.isReadOnly; +
    Aliases for container types +
    +

    + +

    alias SortedMultiSet!(Value) +
    An alias for MultiSet!(Value,SortedAA!(Value,uint)) to implement a +sorted multi-set. +
    + + +

    mintl.share

    +The mintl.share module is publically imported into all container modules +and stores shared defintions. +
    +
    const bit ReadOnly = true; +
    A named constant to improve the readability of code involving read-only +containers. See the section on unmodifiable containers for examples. +
    class IndexOutOfBoundsException : Exception +
    Exception thrown when attempting to access an invalid index or key. Checks for invalid indices can be disabled using version=MinTLNoIndexChecking. + + +
    template MListCatOperators(List) +
    Concatenation routines to be mixed into the list-like containers +
    +
    void add(...); +
    Add to list +
    void vadd(TypeInfo[] ti, void* argptr); +
    Add using va_arg inpurs +
    static List make(...) +
    Consruct a List using add(...) +
    void addN(uint n, Value v) +
    Add the value n times to the list +
    void addBefore(List.SliceType sublist, Value[] v) +
    Insert the values in the dynamic array v before sublist +
    void addAfter(List.SliceType sublist, Value[] v) +
    Insert the values in the dynamic array v after sublist +
    List opCatAssign(Value v); +
    Concatenation operator this ~= v +
    List opCat(Value v); +
    Concatenation operator this ~ v. copies this +
    List opCat_r(Value v); +
    Concatenation operator v ~ this. copies this +
    List opCatAssign(List v); +
    Concatenation operator this ~= v. copies v +
    List opCat(List v); +
    Concatenation operator this ~ v. copies both arguments +
    + +
    template MListAlgo(Container, alias list) +
    List algorithms to be mixed into the list-like containers +
    +
    Container.SliceType opIn(Value v); +
    Return a one-item slice of the first occurrence of v in the list. +
    Container.SliceType find(int delegate(inout Value v) dg); +
    Return a one-item slice of the first occurrence where dg is true. +
    uint count(Value v); +
    Return the number of time v appears in the list. +
    void swap(Container v); +
    Swap the contents of the list with v (assumes non-overlapping). Extra +elements are ignored. +
    void fill(Value v); +
    Fill the container with v +
    void copy(Container v); +
    Copy the contents of v to this container. Extra elements are ignored. +
    + +
    MListCommon(Container) +
    Common list routines +
    +
    bool isEmpty +
    Return true if container is empty +
    Value opIndex(size_t n); +
    Return nth item where the head is item 0. +
    void opIndexAssign(Value val, size_t n); +
    Assign to the nth item +
    Container.SliceType opSlice(size_t a, size_t b); +
    Slice from item a to b (exclusive) +
    Container.SliceType opSlice(Container.SliceType a, Container.SliceType b); +
    Slice from head of a to tail of b +
    Container.SliceType head +
    Read-only property to get a one-item slice of the head. +
    Container.SliceType tail +
    Read-only property to get a one-item slice of the tail. +
    Value[] values; +
    Get list contents as dynamic array. +
    Value value; +
    Read/write property for the value of a one-item slice. +
    void addTail(Value v); +
    Add to tail of list +
    void addTail(Container v); +
    Copy v to tail of list +
    void addHead(Value v); +
    Add to head of list +
    void addHead(Container v); +
    Copy v to head of list +
    Value takeTail(); +
    Remove and return last item +
    Value takeHead(); +
    Remove and return first item +
    void removeTail(); +
    Remove last item +
    void removeHead(); +
    Remove first item +
    void remove(Container.SliceType sublist); +
    Remove sublist from list +
    void addBefore(Container.SliceType subv, Container.SliceType v); +
    Insert v before subv. +
    void addAfter(Container.SliceType subv, Container.SliceType v); +
    Insert v after subv. +
    void next(int n = 1, int end = 0); +
    Move the head and tail to the next item. If n is negative move to +the previous item. If end <= 0 move the head of the slice and if +end >= 0 move the tail of the slice. +
    Value* lookup(size_t n); +
    Return a pointer to the nth item +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal by values +
    int opApply(int delegate(inout size_t n, inout Value x) dg); +
    Foreach traversal by index-value pairs +
    int opApply(int delegate(inout Container.SliceType n) dg); +
    Foreach traversal by one-item slices +
    Container reverse; +
    Reverse list in-place. +
    Container dup; +
    Duplicate array list by duplicating backing array +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    int opEquals(Container c); +
    Test list equality +
    int opCmp(Container c); +
    Compare lists +
    +
    + + +

    mintl.slist

    +
    +
    struct SList(Value, bit ReadOnly = false, Alloc = GCAllocator) +
    A singly-linked list. +Compile with version=MinTLNoIndexChecking to disable bounds checking. +The optional ReadOnly parameter disallows container modifications. +The optional allocator customizes memory management. The default allocator +is GCAllocator. +

    +

    +
    mixin MListCat(SList) +
    Mixin list catenation. +
    size_t length; +
    Return length of list. +
    bool isEmpty +
    Return true if container is empty +
    SList tailList; +
    Return the tail of the list as a slice +
    Value opIndex(size_t n); +
    Return nth item where the head is item 0. +
    void opIndexAssign(Value val, size_t n); +
    Assign to the nth item +
    SList opSlice(size_t a, size_t b); +
    Slice from item a to b (exclusive) +
    SList opSlice(SList a, SList b); +
    Slice from head of a to tail of b +
    SList head +
    Read-only property to get a one-item slice of the head. +
    SList tail +
    Read-only property to get a one-item slice of the tail. +
    Value value +
    Read/write property for the value of a one-item slice. +
    Value[] values; +
    Get list contents as dynamic array. +
    void addTail(Value v); +
    Add to tail of list +
    void addTail(SList v); +
    Append v to tail of list +
    void addHead(Value v); +
    Add to head of list +
    void addHead(SList v); +
    Prepend v to head of list +
    Value takeHead(); +
    Remove and return first item +
    void removeHead(); +
    Remove first item +
    void addAfter(SList subv, SList v); +
    Insert v after subv. +
    void removeAfter(SList sublist, size_t n=1); +
    Remove n items following sublist +
    void removeBetween(SList a, SList b); +
    Remove items after the tail of a to the head of b (exclusive) +
    void next(int n = 1, int end = 0); +
    Move the head and tail to the next item. If n is negative move to +the previous item. If end <= 0 move the head of the slice and if +end >= 0 move the tail of the slice. +
    Value* lookup(size_t n); +
    Return a pointer to the nth item +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal by values +
    int opApply(int delegate(inout size_t n, inout Value x) dg); +
    Foreach traversal by index-value pairs +
    int opApply(int delegate(inout SList n) dg); +
    Foreach traversal by one-item slices +
    SList dup; +
    Duplicate list +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    void trim; +
    Remove references to extra nodes kept for reuse +
    int opEquals(SList c); +
    Test list equality +
    int opCmp(SList c); +
    Compare lists +
    mixin MListAlgo(this,SList) +
    Mixin list algorithms. +
    SList!(Value,true,Alloc) readonly; +
    Property that returns a read-only view of the container. +
    SList!(Value,false,Alloc) readwrite; +
    Property that returns a read-write view of the container. +
    alias SList ContainerType; +
    alias SList SliceType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    alias ReadOnly isReadOnly; +
    Aliases for container types +
    +
    +

    + +

    +
    struct CircularSList(Value, bit ReadOnly = false, Alloc = GCAllocator) +
    A circular singly-linked list. +Compile with version=MinTLNoIndexChecking to disable bounds checking. +The optional ReadOnly parameter disallows container modifications. +The optional allocator customizes memory management. The default allocator +is GCAllocator. +

    +

    +
    mixin MListCat(CircularSList) +
    Mixin list catenation. +
    size_t length; +
    Return length of list. +
    bool isEmpty +
    Return true if container is empty +
    SList toSList; +
    Return the list as a non-circular SList +
    Value opIndex(size_t n); +
    Return nth item where the head is item 0. +
    void opIndexAssign(Value val, size_t n); +
    Assign to the nth item +
    SList opSlice(size_t a, size_t b); +
    Slice from item a to b (exclusive) +
    SList opSlice(SList a, SList b); +
    Slice from head of a to tail of b +
    SList head +
    Read-only property to get a one-item slice of the head. +
    SList tail +
    Read-only property to get a one-item slice of the tail. +
    Value value +
    Read/write property for the value of a one-item slice. +
    void addTail(Value v); +
    Add to tail of list +
    void addTail(CircularSList v); +
    Append v to tail of list +
    void addHead(Value v); +
    Add to head of list +
    void addHead(CircularSList v); +
    Prepend v to head of list +
    Value takeHead(); +
    Remove and return first item +
    void removeHead(); +
    Remove first item +
    void addAfter(SList subv, SList v); +
    Insert v after subv. +
    void removeAfter(SList sublist, size_t n=1); +
    Remove n items following sublist +
    void removeBetween(SList a, SList b); +
    Remove items after the tail of a to the head of b (exclusive) +
    void rotate(int n = 1); +
    Rotate the list by n steps +
    Value* lookup(size_t n); +
    Return a pointer to the nth item +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal by values +
    int opApply(int delegate(inout size_t n, inout Value x) dg); +
    Foreach traversal by index-value pairs +
    int opApply(int delegate(inout SList n) dg); +
    Foreach traversal by one-item slices +
    CircularSList dup; +
    Duplicate list +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    int opEquals(CircularSList c); +
    Test list equality +
    int opCmp(CircularSList c); +
    Compare lists +
    mixin MListAlgo(this,CircularSList) +
    Mixin list algorithms. +
    CircularSList!(Value,true,Alloc) readonly; +
    Property that returns a read-only view of the container. +
    CircularSList!(Value,false,Alloc) readwrite; +
    Property that returns a read-write view of the container. +
    alias CircularAList ContainerType; +
    alias SList!(Value,Alloc) SliceType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    alias ReadOnly isReadOnly; +
    Aliases for container types +
    +
    + + +

    mintl.sortedaa

    +
    +
    class CompareFcnSetException: Exception; +
    Exception thrown when trying to set the comparison function of +a non-empty array or an array that already had the comparison function +set. +
    +

    +

    +
    struct SortedAA(Key, Value, bit ReadOnly = false, Alloc = GCAllocator) +
    A sorted associative array +The optional ReadOnly parameter disallows container modifications. +The optional allocator customizes memory management. The default allocator +is GCAllocator. +

    +

    +
    alias int delegate(Key* a, Key* b) CompareFcn; +
    Signature of comparison functions +
    void compareFcn(CompareFcn cmp); +
    Set the comparison function +
    void add(...); +
    Add key-value pairs to array +
    void vadd(TypeInfo[] ti, void* argptr); +
    Add using va_arg inpurs +
    static SortedAA make(...) +
    Consruct a SortedAA using add(...) +
    size_t length; +
    Return number of items in the array. +
    bool isEmpty +
    Return true if array is empty +
    Value* get(Key key, bit throwOnMiss = false); +
    Return a pointer to the value stored at the key. If the key is not +in the array then null is returned or if throwOnMiss is true an +exception is thrown. +
    Value* put(Key key) +
    Return a pointer to the value stored at the key and insert the +key with value Value.init if the key is not in the array. +
    bool contains(Key key) +
    Returns true if the array contains the key +
    bool contains(Key key, out Value value) +
    Returns true if the array contains the key and sets the out value if +present. +
    Value opIndex(Key key); +
    Return item with given key. Returns the default missing value if not present. +
    void opIndexAssign(Value val, Key key); +
    Assign a value to the given key +
    Value missing +
    Read/write property for the value to use on indexing a key not in +the array. Defaults to Value.init +
    SortedAA head() +
    Return one-item slice of the smallest item +
    SortedAA tail() +
    Return one-item slice of the greatest item +
    void next(int n = 1, int end = 0); +
    Move the head and tail to the next item. If n is negative move to +the previous item. If end <= 0 move the head of the slice and if +end >= 0 move the tail of the slice. +
    SortedAA from(Key a); +
    Return a one-item slice of the smallest item greater than or equal to a. +
    SortedAA to(Key b); +
    Return a one-item slice of the greatest item smaller than b. +
    SortedAA opSlice(Key a, Key b); +
    Slice from item a to b (exclusive). +
    SortedAA opSlice(SortedAA a, SortedAA b); +
    Slice from first key in a to last key in b. +
    Value take(Key key); +
    Remove a key from array if present and return value. Returns the +default missing value if the key was not present. +
    void remove(Key key); +
    Remove a key from array if present. +
    void remove(SortedAA subarray); +
    Remove a slice from array. +
    void trim; +
    Remove references to extra nodes kept for reuse +
    Value[] values; +
    Get values as a dynamic array. The values are in order. +
    Key[] keys; +
    Get keys as a dynamic array. The keys are in order. +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal by values +
    int opApply(int delegate(inout Key key, inout Value x) dg); +
    Foreach traversal by key-value pairs +
    int opApply(int delegate(inout SortedAA n) dg); +
    Foreach traversal by one-item slices +
    SortedAA dup; +
    Duplicate array +
    void clear() +
    Clear contents. Only needed if a non-GCAllocator is used. +
    int opEquals(SortedAA c); +
    Test array equality +
    SortedAAReverseIter!(Key,Value) backwards(); +
    Backwards traversal for "foreach" +
    Value value; +
    Return value of a one-item slices +
    Key key; +
    Return key of a one-item slices +
    SortedAA!(Key,Value,true,Alloc) readonly; +
    Property that returns a read-only view of the container. +
    SortedAA!(Key,Value,false,Alloc) readwrite; +
    Property that returns a read-write view of the container. +
    alias SortedAA ContainerType; +
    alias SortedAA SliceType; +
    alias Value ValueType; +
    alias Key IndexType; +
    Aliases for container types +
    +
    + + +

    mintl.stack

    +
    +
    struct Stack!(Value, ImplType = Deque!(Value)) +
    A stack of items adapted from a customizable list container type. The +default backing container is a Deque. +

    +

    +
    ImplType impl +
    Read-write property holding the backing container. +
    alias addTail push; +
    Alias to add items to the tail of the stack. +
    alias takeTail pop; +
    Alias to take items from the tail of the stack. +
    Value peek +
    Return the top of the stack or Value.init if empty. +
    mixin MListCat(Stack) +
    Mixin list catenation. +
    size_t length; +
    Return length of stack. +
    bool isEmpty +
    Return true if container is empty +
    Value opIndex(size_t n); +
    Return nth item where the head is item 0. +
    void opIndexAssign(Value val, size_t n); +
    Assign to the nth item +
    void addTail(Value v); +
    Add to tail of stack +
    void addTail(Stack v); +
    Append v to tail of stack +
    Value takeHead(); +
    Remove and return first item +
    void removeHead(); +
    Remove first item +
    int opApply(int delegate(inout Value x) dg); +
    Foreach traversal by values +
    int opApply(int delegate(inout size_t n, inout Value x) dg); +
    Foreach traversal by index-value pairs +
    Stack dup; +
    Duplicate stack. +
    int opEquals(Stack c); +
    Test stack equality +
    int opCmp(Stack c); +
    Compare stacks +
    alias Stack ContainerType; +
    alias Value ValueType; +
    alias size_t IndexType; +
    alias ImplType AdaptType; +
    const bit isReadOnly = ImplType.isReadOnly; +
    Aliases for container types +
    +

    + +

    alias ArrayStack!(Value) +
    An alias for Stack!(Value,ArrayList!(Value)) to adapt an ArrayList +to the stack interface. +
    + + + diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/linux.mak --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/linux.mak Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,72 @@ + +# To build libmintl.a type +# make -f linux.mak DFLAGS=-g LIBNAME=libmintl_debug.a +# or +# make -f linux.mak DFLAGS=-release LIBNAME=libmintl.a +# The libmintl.a and object files will be created in the source directory. + +# flags to use building unittest.exe +DUNITFLAGS=-g -unittest -I.. -version=MinTLUnittest -version=MinTLVerboseUnittest + +# flags to use when building the mintl.lib library +DLIBFLAGS=$(DFLAGS) -I.. +#DLIBFLAGS=-g -I.. + +DMD=dmd + +#LIBNAME = libmintl.a + +targets : unittest + +mintl : $(LIBNAME) + +SRC = all.d \ + array.d \ + arraylist.d \ + arrayheap.d \ + deque.d \ + hashaa.d \ + list.d \ + slist.d \ + share.d \ + adapter.d \ + stack.d \ + queue.d \ + set.d \ + multiaa.d \ + mem.d \ + sorting.d \ + sortedaa.d + +OBJS = all.o \ + array.o \ + arraylist.o \ + arrayheap.o \ + deque.o \ + hashaa.o \ + list.o \ + slist.o \ + share.o \ + adapter.o \ + stack.o \ + queue.o \ + set.o \ + multiaa.o \ + mem.o \ + sorting.o \ + sortedaa.o + +$(LIBNAME) : $(OBJS) $(SRC) + ar -r $@ $(OBJS) + +clean: + rm *.o + rm $(LIBNAME) + rm unittest + +%.o : %.d + $(DMD) -c $(DLIBFLAGS) $< -of$@ + +unittest : $(LIBNAME) $(OBJS) $(SRC) + $(DMD) $(DUNITFLAGS) unittest.d -ofunittest $(SRC) + diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/list.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/list.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,1420 @@ +/** \file list.d + * \brief A doubly-linked list and a circular doubly-linked list. + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 2.7.1 + */ + +module mintl.list; + +private import mintl.share; // for ~ and ~= +private import mintl.sorting; +import mintl.mem; + +// shared data structure between List and CircularList +private struct DNode(Value) { + DNode* next, prev; + Value data; + Value* sortLookup(){return &data;} +} + +/** Template for member functions common to List and CircularList */ +template MCommonList(alias tail_, Container ) { + + /** Test if a container is empty. */ + bool isEmpty() { + return head_ is null; + } + + /** Get the length of list. The computation can be O(n) but the + * result is cached and the actively updated until another list + * of unknown length is concatenated or removed. + */ + size_t length() { + if (length_ == 0 && head_) { + Container.Node* n = head_; + length_ = 1; + Container.Node* end = tail_; + while (n !is end) { + length_++; + n = n.next; + } + } + return length_; + } + + // helper function to check if the index is legal + void boundsCheck(size_t n) { + version (MinTLNoIndexChecking) { + } else { + if (!(n == 0 && this.head_) && + (n >= length_ && n >= this.length)) { + throw new IndexOutOfBoundsException(); + } + } + } + + // Internal function to get the nth item of the list. + package Container.Node* getNode(size_t n) { + boundsCheck(n); + Container.Node* v; + if (n <= length_/2) { + v = head_; + while (n--) { + v = v.next; + } + } else { + n = length_-n-1; + v = tail_; + while (n--) { + v = v.prev; + } + } + return v; + } + + /** Get the nth item in the list from head. The operation is O(N(n)) + * where N(x) is the distance from x to either end of list. + * Indexing out of bounds throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + Container.ValueType opIndex(size_t n) { + return getNode(n).data; + } + + static if (!Container.isReadOnly) { + + /** Get a pointer to the nth item in the list from head. The + * operation is O(N(n)) where N(x) is the distance from x to either + * end of list. Indexing out of bounds throws an + * IndexOutOfBoundsException unless version=MinTLNoIndexChecking is + * set. + */ + Container.ValueType* lookup(size_t n) { + return &getNode(n).data; + } + + /** Set the nth item in the list from head. The operation is O(N(n)) + * where N(x) is the distance from x to either end of list. + * Indexing out of bounds throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + void opIndexAssign(Container.ValueType val, size_t n) { + getNode(n).data = val; + } + + /** Reverse a list in-place. The operation is O(n) where n is + * length of the list. + */ + Container reverse() { + if (this.isEmpty) + return *this; + Node* i = head_; + Node* j = tail_; + TypeInfo ti = typeid(Container.ValueType); + while (i !is j && i.next !is j) { + ti.swap(&i.data,&j.data); + i = i.next; + j = j.prev; + } + ti.swap(&i.data,&j.data); + return *this; + } + + } // !isReadOnly + + /** Copies the list contents to an array */ + Container.ValueType[] values() { + Container.ValueType[] buffer = new Container.ValueType[this.length]; + foreach(size_t n, Container.ValueType val; *this) { + buffer[n] = val; + } + return buffer; + } + + /** Test for equality of two lists. The operation is O(n) where n + * is length of the list. + */ + int opEquals(Container c) { + if (length_ && c.length_ && length_ != c.length_) + return 0; + Container.Node* i = head_; + Container.Node* j = c.head_; + Container.Node* t = tail_; + Container.Node* ct = c.tail_; + TypeInfo ti = typeid(Container.ValueType); + while (i !is null && j !is null) { + if (!ti.equals(&i.data,&j.data)) + return 0; + if (i !is t && j !is ct) + return 1; + i = i.next; + j = j.next; + } + return (i is null && j is null); + } + + /** Compare two lists. */ + int opCmp(Container c) { + Container.Node* i = head_; + Container.Node* j = c.head_; + Container.Node* t = tail_; + Container.Node* ct = c.tail_; + TypeInfo ti = typeid(Container.ValueType); + while (i !is null && j !is null) { + int cmp = ti.compare(&i.data,&j.data); + if (cmp) + return cmp; + if (i !is t && j !is ct) + return 0; + i = i.next; + j = j.next; + } + if (i is null && j is null) + return 0; + else + return (i is null) ? -1 : 1; + } + + /** Create a sub-list from index a to b (exclusive). The operation is + * O(max(N(a),N(b))) where N(x) is distance from x to either end of + * the target list. + */ + Container.SliceType opSlice(size_t a, size_t b) { + Container.SliceType res; + res.length_ = b-a; + if (res.length_ > 0) { + res.head_ = getNode(a); + if (this.length_ - b > b-a){ + Container.Node* v = res.head_; + b = b-a-1; + while (b--) + v = v.next; + res.tail_ = v; + } else { + res.tail_ = getNode(b-1); + } + } + return res; + } + + /** Create a sub-list from the head of a to the tail of b (inclusive). */ + Container.SliceType opSlice(Container.SliceType a, Container.SliceType b) { + if (a.isEmpty) + return b; + if (b.isEmpty) + return a; + Container.SliceType res; + Container.Node* i = a.head_; + res.head_ = i; + res.tail_ = b.tail_; + res.length_ = 0; // flag indicating unknown length + return res; + } + + /** Iterates over the list from head to tail calling delegate to + * perform an action. The value is passed to the delegate. + */ + int opApplyNoKeyStep(int delegate(inout Container.ValueType x) dg, int step = 1){ + int dg2(inout size_t count, inout Container.ValueType val) { + return dg(val); + } + return opApplyWithKeyStep(&dg2,step); + } + + /** Iterates over the list from head to tail calling delegate to + * perform an action. The index from 0 and the value are passed + * to the delegate. + */ + int opApplyWithKeyStep(int delegate(inout size_t n, inout Container.ValueType x) dg, + int step = 1){ + Container.Node* i = step>0 ? head_ : tail_; + Container.Node* end = step>0 ? tail_ : head_; + int res = 0; + size_t n = step>0 ? 0 : this.length-1; + while (i !is null) { + res = dg(n, i.data); + if (res || i is end) break; + n += step; + i = step>0 ? i.next : i.prev; + } + return res; + } + + /** Iterates over the list from head to tail calling delegate to + * perform an action. A one-item sub-list is passed to the delegate. + */ + int opApplyIterStep(int delegate(inout Container.SliceType n) dg, int step = 1){ + Container.Node* i = step>0 ? head_ : tail_; + Container.Node* end = step>0 ? tail_ : head_; + int res = 0; + Container.SliceType n; + n.length_ = 1; + while (i !is null) { + n.head_ = n.tail_ = i; + res = dg(n); + if (res || i is end) break; + i = step>0 ? i.next : i.prev; + } + return res; + } + +} + +/** \class List + * \brief A doubly-linked list. + * + * A List!(Value) is a linked list of data of type Value. A list is + * similar to a dynamic array except accessing an element in the + * middle of the list is O(n) and appending to the front or back is + * O(1). Any operation that is not constant-time will explicitly have + * the performance behavior documented. + * + * The optional ReadOnly parameter List!(Value,ReadOnly) forbids + * operations that modify the container. The readonly() property returns + * a ReadOnly view of the container. + * + * The optional allocator parameter List!(Value,false,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct List(Value, bit ReadOnly = false, Alloc = GCAllocator) { + + alias List ContainerType; + alias List SliceType; + alias Value ValueType; + alias size_t IndexType; + alias Value SortType; + alias DNode!(Value) Node; + alias ReadOnly isReadOnly; + + const int NodeAllocationBlockSize = 10; // allocate 10 nodes at a time + + /* length 0 means length is unknown. An empty list is indicated by + * a null head. The tail can be non-null in order to maintain the + * cached nodes. + */ + invariant { + assert( length_ == 0 || head_ !is null ); + } + + // private bug private { + size_t length_; + Node* head_; + Node* tail_; + // } + + /** Get a ReadOnly view of the container */ + .List!(Value, true, Alloc) readonly() { + .List!(Value, true, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get a read-write view of the container */ + .List!(Value, false, Alloc) readwrite() { + .List!(Value, false, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + static if (!ReadOnly) { + + /** Appends an item to the tail of the list. If the target list is + * a sub-list call addAfter instead of addTail to insert an item + * after a sub-list. + */ + void addTail(Value v) { + if (head_ is null && tail_ !is null) { + // empty list but with cache available + head_ = tail_; + tail_.data = v; + length_ = 1; + } else if (tail_ is null || tail_.next is null) { + if (head_ is null || head_.prev is null) { + // no available nodes so allocate a new one + List val; + val.head_ = val.tail_ = newNode(); + val.length_ = 1; + val.head_.data = v; + addTail(val); + } else { + // grab available node from front + Node* t = head_.prev; + if (t.prev !is null) t.prev.next = head_; + head_.prev = t.prev; + t.prev = tail_; + t.next = null; + tail_.next = t; + tail_ = t; + tail_.data = v; + if (length_) length_++; + } + } else { + // grab available node from end + tail_.next.prev = tail_; + tail_ = tail_.next; + tail_.data = v; + if (length_) length_++; + } + } + + /** Appends a list to the tail of the target list. If the target + * list is a sub-list call addAfter instead of addTail to insert + * another list after a sub-list. + */ + void addTail(List v) { + if (v.isEmpty) + return; + if (tail_ !is null) + tail_.next = v.head_; + v.head_.prev = tail_; + if (this.isEmpty) + length_ = v.length_; + else + length_ = increaseLength(length_, v.length_); + tail_ = v.tail_; + if (head_ is null) + head_ = v.head_; + } + + mixin MListCatOperators!(List); + + /** Clear all contents. */ + void clear() { + static if (is(Alloc == GCAllocator)) { + } else { + trim(); + Node* i = head_; + while (i !is null) { + Node* next = i.next; + Alloc.gcFree(i); + i = next; + } + } + *this = List.init; + } + + /** Set the value of one-item slice (more generally the head value). */ + void value(Value newValue) { + head_.data = newValue; + } + + // Helper function for take and remove + private Node* takeTailHelper() { + if (this.isEmpty) + throw new IndexOutOfBoundsException(); + Node* v = tail_; + if (head_ && head_ is tail_) { + head_ = null; + } else { + tail_ = tail_.prev; + } + return v; + } + + /** Removes and returns the tail item of the list. The node that + * contained the item may be reused in future additions to the + * list. To prevent the node from being reused call trim or + * call remove with a sublist containing the last item. If + * the target list is empty an IndexOutOfBoundsException is thrown + * unless version=MinTLNoIndexChecking is set. + */ + Value takeTail() { + Node* v = takeTailHelper(); + Value data = v.data; + v.data = Value.init; + if (length_) length_--; + return data; + } + + /** Removes the tail item of the list. */ + void removeTail() { + Node* v = takeTailHelper(); + v.data = Value.init; + if (length_) length_--; + } + + /** Prepends an item to the head of the target list. If the target + * list is a sub-list call addBefore instead of addHead to insert an + * item before a sub-list. + */ + void addHead(Value v) { + if (head_ is null && tail_ !is null) { + // empty list but with cache available + head_ = tail_; + tail_.data = v; + length_ = 1; + } else if (head_ is null || head_.prev is null) { + if (tail_ is null || tail_.next is null) { + // no available nodes so allocate a new one + List val; + val.head_ = val.tail_ = newNode(); + val.length_ = 1; + val.head_.data = v; + addHead(val); + } else { + // grab available node from end + Node* t = tail_.next; + if (t.next !is null) t.next.prev = tail_; + tail_.next = t.next; + t.next = head_; + t.prev = null; + head_.prev = t; + head_ = t; + head_.data = v; + if (length_) length_++; + } + } else { + // grab available node from front + head_.prev.next = head_; + head_ = head_.prev; + head_.data = v; + if (length_) length_++; + } + } + + /** Prepends a list to the head of the target list. If the target + * list is a sub-list call addBefore instead of addHead to insert a + * list before a sub-list. + */ + void addHead(List v) { + if (v.isEmpty) + return; + if (head_ !is null) + head_.prev = v.tail_; + v.tail_.next = head_; + if (this.isEmpty) + length_ = v.length_; + else + length_ = increaseLength(length_, v.length_); + head_ = v.head_; + if (tail_ is null) + tail_ = v.tail_; + } + + // Helper function for take and remove + private Node* takeHeadHelper() { + if (this.isEmpty) + throw new IndexOutOfBoundsException(); + Node* v = head_; + if (head_ && head_ is tail_) { + head_ = null; + } else { + head_ = head_.next; + } + return v; + } + + /** Removes and returns the head item of the list. The node that + * contained the item may be reused in future additions to the + * list. If the target list is empty an IndexOutOfBoundsException is + * thrown unless version=MinTLNoIndexChecking is set. + */ + Value takeHead() { + Node* v = takeHeadHelper(); + Value data = v.data; + v.data = Value.init; + if (length_) length_--; + return data; + } + + /** Removes the head item of the list. */ + void removeHead() { + Node* v = takeHeadHelper(); + v.data = Value.init; + if (length_) length_--; + } + + /** Insert a list before a sub-list. */ + void addBefore(List subv, List v) { + if (v.isEmpty) + return; + if (subv.isEmpty) + throw new IndexOutOfBoundsException(); + Node* t = subv.head_; + if (t.prev !is null) { + t.prev.next = v.head_; + } + v.head_.prev = t.prev; + v.tail_.next = t; + t.prev = v.tail_; + if (t is head_) + head_ = v.head_; + length_ = increaseLength(length_, v.length_); + } + + /** Insert a list after a sub-list. */ + void addAfter(List subv, List v) { + if (v.isEmpty) + return; + if (subv.isEmpty) + throw new IndexOutOfBoundsException(); + Node* t = subv.tail_; + if (t.next !is null) { + t.next.prev = v.tail_; + } + v.tail_.next = t.next; + v.head_.prev = t; + t.next = v.head_; + if (t is tail_) + tail_ = v.tail_; + length_ = increaseLength(length_, v.length_); + } + + + /** Removes a sub-list from the list entirely. */ + void remove(List sublist) { + if (sublist.isEmpty) + return; + Node* h = sublist.head_; + Node* t = sublist.tail_; + if (h is head_ && t is tail_) { + head_ = tail_ = null; + length_ = 0; + return; + } + Node* hp = h.prev; + Node* tn = t.next; + if (hp !is null) + hp.next = tn; + if (tn !is null) + tn.prev = hp; + if (h is head_) + head_ = tn; + if (t is tail_) + tail_ = hp; + length_ = decreaseLength(length_, sublist.length_); + } + + /** Removes an item from the list if present. */ + void remove(size_t index) { + List item = opSlice(index, index+1); + remove(item); + } + + /** Removes an item and return the value if any. */ + Value take(size_t index) { + List item = opSlice(index, index+1); + remove(item); + Value val = item[0]; + item.clear(); + return val; + } + + /** Trims off extra nodes that are not actively being used by the + * list but are available for recyling for future add operations. + * This function should be called after calling remove and + * there are other list or pointer references to the removed item. + */ + void trim() { + if (!this.isEmpty) { + Node* i; + if (tail_.next) { + i = tail_.next; + i.prev = null; + tail_.next = null; + static if (is(Alloc == GCAllocator)) { + } else { + while (i !is null) { + Node* next = i.next; + Alloc.gcFree(i); + i = next; + } + } + } + if (head_.prev) { + i = head_.prev; + i.next = null; + head_.prev = null; + static if (is(Alloc == GCAllocator)) { + } else { + while (i !is null) { + Node* prev = i.prev; + Alloc.gcFree(i); + i = prev; + } + } + } + } + } + + } // !ReadOnly + + /** Duplicates a list. The operation is O(n) where n is length of + * the list. + */ + List dup() { + .List!(Value,false,Alloc) res; + foreach(ValueType val; *this) { + res ~= val; + } + static if (ReadOnly) { + return res.readonly; + } else { + return res; + } + } + + /** Move a sub-list towards the head or tail by n items. If n is + * negative the sub-list moves towards the head. A positive end is + * the tail, negative the head and 0 is both. By default moves to + * the next item. + */ + void next(int n = 1, int end = 0) { + if (length_) + length_ -= n*end; + while (n-- > 0) { + if (end <= 0) + head_ = head_.next; + if (end >= 0) + tail_ = tail_.next; + } + while (++n < 0) { + if (end <= 0) + head_ = head_.prev; + if (end >= 0) + tail_ = tail_.prev; + } + } + + /** Get the length of list. The computation can be O(n) but the + * result is cached and the actively updated until another list + * of unknown length is concatenated. + */ + size_t length() { + if (length_ == 0 && !this.isEmpty) { + Node* n = head_; + length_ = 1; + while (n !is tail_) { + length_++; + n = n.next; + } + } + return length_; + } + + /** Create a one-item slice of the head. */ + List head() { + List res; + res.length_ = head_? 1 : 0; + res.head_ = res.tail_ = head_; + return res; + } + + /** Create a one-item slice of the tail. */ + List tail() { + List res; + res.length_ = tail_? 1 : 0; + res.head_ = res.tail_ = tail_; + return res; + } + + /** Get the value of one-item slice (more generally the head value). + * Useful for expressions like x.tail.value or x.head.value. */ + Value value() { + return head_.data; + } + + /** Iterate backwards over the list (from tail to head). This + * should be called as the iteration parameter in a + * foreach statement + */ + ListReverseIter!(Value,ReadOnly,Alloc) backwards() { + ListReverseIter!(Value,ReadOnly,Alloc) res; + res.list = this; + return res; + } + + /** Helper functions for opApply */ + mixin MOpApplyImpl!(ContainerType); + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + alias opApplyIter opApply; + + private Node* newNode() { + static if (is(Alloc == GCAllocator)) { + // allocate a block of nodes and return pointer to first one + Node[] block = new Node[NodeAllocationBlockSize]; + for (int k=1; kadd and remove functions and + * slices can be moved forward around the list indefinitely. A CircularList + * also has a smaller memory footprint since it requires only one + * pointer for the head instead of two pointers for a tail and head. + * + * The optional ReadOnly parameter CircularList!(Value,ReadOnly) forbids + * operations that modify the container. The readonly() property returns + * a ReadOnly view of the container. + * + * The optional allocator parameter CircularList!(Value,false,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct CircularList(Value, bit ReadOnly = false, Alloc = GCAllocator) { + + alias CircularList ContainerType; + alias List!(Value,ReadOnly,Alloc) SliceType; + alias Value ValueType; + alias size_t IndexType; + alias DNode!(Value) Node; + alias ReadOnly isReadOnly; + + private { + size_t length_; + Node* head_; + } + + /* length 0 means length is unknown. */ + invariant { + assert( length_ == 0 || head_ !is null ); + } + + /** Return the circular list as a non-circular List. + * \return the list as a List + */ + SliceType toList() { + SliceType res; + if (this.isEmpty) + return res; + res.privateMake(head_,head_.prev,length_); + // res.tail_ = + // res.head_ = head_; + // res.length_ = length_; + return res; + } + + /** Get a ReadOnly view of the container */ + .CircularList!(Value, true, Alloc) readonly() { + .CircularList!(Value, true, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get a read-write view of the container */ + .CircularList!(Value, false, Alloc) readwrite() { + .CircularList!(Value, false, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + private Node* tail_() { + if (this.isEmpty) return null; + return head_.prev; + } + + static if (!ReadOnly) { + + /** Rotate the list by n items. If n is negative the rotation is + * reversed. + */ + void rotate(int n = 1) { + if (n >= 0) { + while (n-- > 0) + head_ = head_.next; + } else { + while (++n < 0) + head_ = head_.prev; + } + } + + /** Clear all contents. */ + void clear() { + static if (is(Alloc == GCAllocator)) { + } else { + Node* i = head_; + if (i !is null) + i.prev.next = null; + while (i !is null) { + Node* next = i.next; + Alloc.gcFree(i); + i = next; + } + } + *this = CircularList.init; + } + /** Appends an item to the tail of the list. If the target list is + * a sub-list call addAfter instead of addTail to insert an item + * after a sub-list. + */ + void addTail(Value v) { + Node* n = newNode(); + n.data = v; + addNode(n); + } + + private void link(Node* a, Node* b) { + a.next = b; + b.prev = a; + } + + /** Adds a node before head. */ + private void addNode(Node* n) { + if (this.isEmpty) { + link(n,n); + head_ = n; + length_ = 1; + } else { + link(tail_,n); + link(n,head_); + if (length_) length_++; + } + } + + /** Appends a list to the tail of the target list. If the target + * list is a sub-list call addAfter instead of addTail to insert + * another list after a sub-list. + */ + void addTail(CircularList v) { + addHead(v); + } + + mixin MListCatOperators!(CircularList); + + // Helper function for take and remove + private Node* takeTailHelper() { + if (this.isEmpty) + throw new IndexOutOfBoundsException(); + Node* v = tail_; + if (head_ && head_ is tail_) { + head_ = null; + } else { + link(v.prev,v.next); + } + return v; + } + + /** Removes and returns the tail item of the list. The node that + * contained the item may be reused in future additions to the + * list. To prevent the node from being reused call trim or + * call remove with a sublist containing the last item. If + * the target list is empty an IndexOutOfBoundsException is thrown + * unless version=MinTLNoIndexChecking is set. + */ + Value takeTail() { + Node* v = takeTailHelper(); + Value data = v.data; + freeNode(v); + if (length_) length_--; + return data; + } + + /** Removes the tail item of the list. */ + void removeTail() { + Node* v = takeTailHelper(); + if (length_) length_--; + freeNode(v); + } + + /** Prepends an item to the head of the target list. If the target + * list is a sub-list call addBefore instead of addHead to insert an + * item before a sub-list. + */ + void addHead(Value v) { + Node* n = new Node; + n.data = v; + addNode(n); + head_ = n; + } + + /** Prepends a list to the head of the target list. If the target + * list is a sub-list call addBefore instead of addHead to insert a + * list before a sub-list. + */ + void addHead(CircularList v) { + if (v.isEmpty) + return; + if (this.isEmpty) { + *this = v; + return; + } + Node* vt = v.tail_; + link(tail_,v.head_); + link(vt,head_); + head_ = v.head_; + length_ = increaseLength(length_, v.length_); + } + + // Helper function for take and remove + private Node* takeHeadHelper() { + if (this.isEmpty) + throw new IndexOutOfBoundsException(); + Node* v = head_; + if (head_ && head_ is tail_) { + head_ = null; + } else { + link(v.prev,v.next); + } + return v; + } + + /** Removes and returns the head item of the list. The node that + * contained the item may be reused in future additions to the + * list. To prevent the node from being reused call trim or + * call remove with a sublist containing the last item. If + * the target list is empty an IndexOutOfBoundsException is thrown + * unless version=MinTLNoIndexChecking is set. + */ + Value takeHead() { + Node* v = takeHeadHelper(); + Value data = v.data; + if (length_) length_--; + freeNode(v); + return data; + } + + /** Removes the head item of the list. */ + void removeHead() { + Node* v = takeHeadHelper(); + if (length_) length_--; + freeNode(v); + } + + /** Insert a list before a sub-list. */ + void addBefore(SliceType subv, SliceType v) { + if (v.isEmpty) + return; + if (subv.isEmpty) + throw new IndexOutOfBoundsException(); + Node* t = subv.head_; + link(t.prev,v.head_); + link(v.tail_,t); + if (t is head_) + head_ = v.head_; + length_ = increaseLength(length_, v.length_); + } + + /** Insert a list after a sub-list. */ + void addAfter(SliceType subv, SliceType v) { + if (v.isEmpty) + return; + if (subv.isEmpty) + throw new IndexOutOfBoundsException(); + Node* t = subv.tail_; + link(v.tail_,t.next); + link(t,v.head_); + length_ = increaseLength(length_, v.length_); + } + + + /** Removes a sub-list from the list entirely. */ + void remove(SliceType sublist) { + if (sublist.isEmpty) + return; + Node* h = sublist.head_; + Node* t = sublist.tail_; + if (h is head_ && t is tail_) { + head_ = null; + length_ = 0; + return; + } + if (h is head_) + head_ = t.next; + link(h.prev,t.next); + h.prev = null; + t.next = null; + length_ = decreaseLength(length_, sublist.length_); + } + + /** Removes an item if present. */ + void remove(size_t index) { + remove(opSlice(index, index+1)); + } + + /** Removes an item from the list and return its value, if present. */ + Value take(size_t index) { + SliceType item = opSlice(index, index+1); + remove(item); + Value val = item[0]; + item.clear(); + return val; + } + + } // !ReadOnly + + /** Duplicates a list. The operation is O(n) where n is length of + * the list. + */ + CircularList dup() { + .CircularList!(Value,false,Alloc) res; + foreach(ValueType val; *this) { + res ~= val; + } + static if (ReadOnly) { + return res.readonly; + } else { + return res; + } + } + + /** Create a one-item slice of the head. */ + SliceType head() { + SliceType res; + if (this.isEmpty) return res; + res.head_ = res.tail_ = head_; + res.length_ = 1; + return res; + } + + /** Create a one-item slice of the tail. */ + SliceType tail() { + SliceType res; + if (this.isEmpty) return res; + res.head_ = res.tail_ = head_.prev; + res.length_ = 1; + return res; + } + + /** Move a sub-list towards the tail by n items. */ + void next(int n = 1, int end = 0) { + if (length_) + length_ -= n*end; + while (n-- > 0) { + if (end <= 0) + head_ = head_.next; + } + } + + /** Iterate backwards over the list (from tail to head). This + * should be called as the iteration parameter in a + * foreach statement + */ + CircularListReverseIter!(Value,ReadOnly,Alloc) backwards() { + CircularListReverseIter!(Value,ReadOnly,Alloc) res; + res.list = this; + return res; + } + + /** + * Helper functions for opApply with/without keys and + * forward/backward order + */ + mixin MOpApplyImpl!(ContainerType); + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + alias opApplyIter opApply; + + private Node* newNode() { + static if (is(Alloc == GCAllocator)) { + return new Node; + } else { + Node* p = cast(Node*)Alloc.gcMalloc(Node.sizeof); + *p = Node.init; + return p; + } + } + + private void freeNode(Node* n) { + static if (is(Alloc == GCAllocator)) { + } else { + Alloc.gcFree(n); + } + } + + CircularList getThis(){return *this;} + mixin MListAlgo!(CircularList, getThis); + + mixin MCommonList!(tail_, CircularList ); +} + +// helper functions for adjusting length cache +private size_t increaseLength(size_t len, size_t x) { + return x ? (len? len+x : 0) : 0; +} +private size_t decreaseLength(size_t len, size_t x) { + return x ? (len? len-x : 0) : 0; +} + +// helper structure for backwards() +struct CircularListReverseIter(Value,bit ReadOnly,Alloc) { + mixin MReverseImpl!(List!(Value,ReadOnly,Alloc), + CircularList!(Value,ReadOnly,Alloc)); +} + +//version = MinTLVerboseUnittest; +//version = MinTLUnittest; + +version (MinTLUnittest) { + private import std.random; + unittest { + version (MinTLVerboseUnittest) + printf("starting mintl.list unittest\n"); + + List!(int) x; + x ~= 3; + x ~= 4; + assert( x[0] == 3 ); + assert( x[1] == 4 ); + assert( x.length == 2 ); + List!(int) x2 = List!(int).make(3,4); + assert( x == x2 ); + + List!(int) catt; + catt = List!(int).make(1,2,3) ~ List!(int).make(4,5,6); + assert( catt == List!(int).make(1,2,3,4,5,6) ); + + List!(int,false,MallocNoRoots) xm; + xm ~= 3; + xm ~= 4; + assert( xm[0] == 3 ); + assert( xm[1] == 4 ); + assert( xm.length == 2 ); + xm.clear(); + assert( xm.isEmpty ); + + List!(real) x2s; + x2s.add(cast(real)3,cast(real)4); + assert( x2s[0] == 3 ); + assert( x2s[1] == 4 ); + + // test addHead + List!(int) y; + y.addHead(4); + y.addHead(3); + + // test == + assert( x == y ); + List!(int) w = x.dup; + w ~= 5; + assert( x != w); + + // test remove/take + assert( w.takeTail() == 5 ); + size_t wlen = w.length; + w.addTail(6); + w.removeTail(); + assert( w.length() == wlen ); + assert( w == x ); + w.trim(); + w ~= 5; + + // test reverse lists + List!(int) z = y.dup; + z.reverse(); + assert( z[0] == 4 ); + assert( z[1] == 3 ); + + // test foreach iteration + foreach(size_t n, inout int val; z) { + val = n*10; + } + assert( z[0] == 0 ); + assert( z[1] == 10 ); + foreach(size_t n, int val; y.backwards()) { + assert(x[n] == val); + } + int n = 0; + foreach(List!(int) itr; y) { + assert(itr[0] == y[n++]); + } + + // test slicing + List!(int) v = w[1..3]; + assert( v.length == 2 ); + assert( v[0] == 4 ); + assert( v[1] == 5 ); + + // test readonly + List!(int,ReadOnly) rv = v.readonly; + assert( rv.length == 2 ); + assert( rv[0] == 4 ); + assert( rv[1] == 5 ); + assert( rv.head == rv[0 .. 1] ); + assert( rv.tail == rv[1 .. 2] ); + + // test algorithms + assert( v.opIn(5) == v.tail ); + assert( v.count(5) == 1 ); + assert( v.find(delegate int(inout int v){return v == 5;}) == v.tail ); + v[0 .. 1].swap(v[1..2]); + assert( v[0] == 5 ); + assert( v[1] == 4 ); + v.fill(10); + assert( v[0] == 10 ); + assert( v[1] == 10 ); + List!(int) vsub; + vsub.add(4,5); + v.copy(vsub); + assert( v[0] == 4 ); + assert( v[1] == 5 ); + + // test another node type + List!(char[]) str; + str.add("hello","world"); + assert( str[str.length-1] == "world" ); + + // test sub-list spanning + List!(int) tmp; + int[10] tmp2; + tmp2[3] = 100; + tmp2[8] = 200; + foreach(int xx;tmp2) + tmp ~= xx; + List!(int) a,b,c; + a = tmp[3..5]; + b = tmp[7..9]; + c = tmp[a..b]; + assert( c.length == 6 ); + assert( c[0] == 100 ); + assert( c[5] == 200 ); + + // CircularList testing + + CircularList!(int) cx; + cx ~= 3; + cx ~= 4; + assert( cx[0] == 3 ); + assert( cx[1] == 4 ); + assert( cx.length == 2 ); + + CircularList!(int) cx2; + cx2.add(3,4); + assert( cx == cx2 ); + + // test addHead + CircularList!(int) cy; + cy.addHead(4); + cy.addHead(3); + + // test == + assert( cx == cy ); + CircularList!(int) cw = cx.dup; + cw ~= 5; + assert( cx != cw); + + // test remove + assert( cw.takeTail() == 5 ); + wlen = cw.length; + cw.addTail(6); + cw.removeTail(); + assert( cw.length() == wlen ); + assert( cw == cx ); + cw ~= 5; + + // test reverse lists + CircularList!(int) cz = cy.dup; + cz.reverse(); + assert( cz[0] == 4 ); + assert( cz[1] == 3 ); + + // test foreach iteration + foreach(size_t n, inout int val; cz) { + val = n*10; + } + assert( cz[0] == 0 ); + assert( cz[1] == 10 ); + foreach(size_t n, int val; cy.backwards()) { + assert(cx[n] == val); + } + n = 0; + foreach(List!(int) itr; cy) { + assert(itr[0] == cy[n++]); + } + + // test slicing + List!(int) cv = w[1..3]; + assert( cv.length == 2 ); + assert( cv[0] == 4 ); + assert( cv[1] == 5 ); + + // test algorithms + assert( cv.opIn(5) == v.tail ); + assert( cv.count(5) == 1 ); + + // test another node type + CircularList!(char[]) cstr; + cstr.add("hello","world"); + assert( cstr[cstr.length-1] == "world" ); + + // test sub-list spanning + CircularList!(int,false,MallocNoRoots) ctmp; + tmp2[3] = 100; + tmp2[8] = 200; + foreach(int xx;tmp2) + ctmp ~= xx; + List!(int,false,MallocNoRoots) ca,cb,cc; + ca = ctmp[3..5]; + cb = ctmp[7..9]; + cc = ctmp[ca..cb]; + assert( cc.length == 6 ); + assert( cc[0] == 100 ); + assert( cc[5] == 200 ); + ctmp.clear(); + assert( ctmp.isEmpty ); + + // test simple sorting + List!(int) s1,s12; + s1.add(40,300,-20,100,400,200); + s12 = s1.dup; + s1.sort(); + List!(int) s2 = List!(int).make(-20,40,100,200,300,400); + //List!(int) s2 = s2.make(-20,40,100,200,300,400); + assert( s1 == s2 ); + // sort a slice in-place + s12[1..4].sort(); + s2.clear(); + s2.add(40,-20,100,300,400,200); + assert( s12 == s2 ); + + // test a large sort with default order + List!(double) s3; + for (int k=0;k<1000;k++) { + s3 ~= 1.0*rand()/100000.0 - 500000.0; + } + List!(double) s4 = s3.dup; + s3.sort(); + for (int k=0;k<999;k++) { + assert( s3[k] <= s3[k+1] ); + } + // test a large sort with custom order + int cmp(double*x,double*y){return *x>*y?-1:*x==*y?0:1;} + s4.sort(&cmp); + for (int k=0;k<999;k++) { + assert( s4[k] >= s4[k+1] ); + } + + version (MinTLVerboseUnittest) + printf("finished mintl.list unittest\n"); + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/locks.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/locks.html Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,490 @@ + Synchronization Locks Library for D + +

    Synchronization Locks for D

    +Locks is a library of synchronization constructs for the D +programming language based on the concurrent locks library +by Doug Lea. +For more info about D see DigitalMars D home page. The +library can be downloaded +here +or as part of +MinTL. +For more information about the Java library see + +JSR-166. For an initial port see + dsource. + +

    +This library is in the public domain. +Portions written by Ben Hinkle, 2004, portions ported from code +written by Doug Lea. +Email comments and bug reports to ben.hinkle@gmail.com +

    + +

    Overview

    + +The D language has builtin support for defining critical sections +using the synchronized statement but does not include +POSIX synchronization constructs like locks and condition variables. +The purpose of the Locks library is to extend the builtin D +capabilities to support not only POSIX constructs but also support +latches, barriers and exchangers. Concurrent containers like queues, +stacks and associative arrays are in the MinTL library in the +package mintl.concurrent. When using concurrent algorithms +be careful to use the volatile statement to ensure data +is properly updated in all the threads. + +

    +The primary interface of the Locks library is the Lock interface. It +defines two methods, lock and unlock, that aquire +and release the lock. In general the Lock interface makes no +guarentee that a thread can lock a lock that it already +owns. The ReentrantLock class, which implements +Lock, does guarantee that the thread that hold the lock can +call lock without blocking. If a thread calls lock +and the lock is held by another thread then the calling thread is +parked until the lock is released. The tryLock functions +attempts to acquire the lock immediately or within a specified time interval. +For example a typical +class X that uses a ReentrantLock to control access +to function m uses try-finally blocks to insure the lock is +released before the function returns: + +

    +  class X {
    +    private ReentrantLock lock;
    +    // ...
    +    this() { 
    +      lock = new ReentrantLock; 
    +    }
    +    void m() { 
    +      lock.lock();  // block until lock is available
    +      try {
    +        // ... method body
    +      } finally {
    +        lock.unlock()
    +      }
    +    }
    +  }
    +
    +A ScopedLock can simplify the code around managing locks. +The class X could instead use a ScopedLock +in m: +
    +  class X {
    +    private ReentrantLock lock;
    +    // ...
    +    this() { 
    +      lock = new ReentrantLock; 
    +    }
    +    void m() { 
    +        auto ScopedLock slock = new ScopedLock(lock);
    +        // ... method body
    +    }
    +  }
    +
    + +The only difference between the two implementations is that the +ScopedLock, as written, will allocate memory from the GC each +time it is called. + +

    +The Condition interface defines a condition variable for a given lock. +A condition variable allows two or more threads to hand-off ownership +of the lock atomically by calling wait and notify. +If a thread owns the lock and calls wait +on a condition variable then the thread releases the lock and +blocks until notified by the condition variable. +Once notified the thread attempts to acquire the lock and once successful +continues execution. The wait function accepts timeout values to stop +blocking after a certain amount of time. A thread that fails the timeout +still must reacquire the lock before proceeding. A typical use of condition +variables is to signal when an event has happened. +The function Lock.newCondition creates and returns a Condition +instance. +For example, the +condition below signals when the data variable has been set: +

    +  int data;
    +  Thread getter, setter;
    +  ReentrantLock lock = new ReentrantLock;
    +  Condition is_ready = lock.newCondition;
    +  setter = new Thread(
    +    delegate int() {
    +      lock.lock();
    +      try {
    +        data = 10;
    +        is_ready.notify();
    +      } finally {
    +        lock.unlock();
    +      }
    +      return 0;
    +    });
    +  getter = new Thread(
    +    delegate int() {
    +      lock.lock();
    +      try {
    +        is_ready.wait();
    +        printf("%d\n",data);
    +      } finally {
    +        lock.unlock();
    +      }
    +      return 0;
    +    });
    +  getter.start();
    +  setter.start();
    +
    + +

    +To start several threads and have them wait until a signal from a +coordinating thread use a CountDownLatch with a count of +1. For example, +

    +  CountDownLatch go = new CountDownLatch(1);
    +  Thread[4] t;
    +  for (int i=0; i < 4; i++) {
    +    t[i] = new Thread(
    +      delegate int() {
    +        go.wait(); // wait for signal from main thread
    +        // ... do something interesting ...
    +        return 0;
    +      });
    +    t[i].start();
    +  }
    +  go.countDown(); // let worker threads go
    +
    +Conversely to signal a coordinating thread that the worker threads +are finished have each worker thread decrement another +CountDownLatch: +
    +  CountDownLatch go = new CountDownLatch(1);
    +  CountDownLatch allDone = new CountDownLatch(4);
    +  Thread[4] t;
    +  for (int i=0; i < 4; i++) {
    +    t[i] = new Thread(
    +      delegate int() {
    +        go.wait(); // wait for signal from main thread
    +        // ... do something interesting ...
    +        allDone.countDown();
    +        return 0;
    +      });
    +    t[i].start();
    +  }
    +  go.countDown(); // let worker threads go
    +  allDone.wait(); // wait for all workers to finish
    +
    + +

    +A CyclicBarrier is similar to a CountDownLatch +except the cyclic barrier is used without a controlling thread. +A thread that reaches the barrier waits until the barrier count +is exhausted before continuing. Once the barrier is tripped it +optionally runs a function and resets to zero. Continuing the +example from the previous paragraph the worker threads might need +to rendezvous at a certain point mid-way through their task: +

    +  CountDownLatch go = new CountDownLatch(1);
    +  CountDownLatch allDone = new CountDownLatch(4);
    +  CyclicBarrier barrier = new CyclicBarrier(4);
    +  Thread[4] t;
    +  for (int i=0; i < 4; i++) {
    +    t[i] = new Thread(
    +      delegate int() {
    +        go.wait(); // wait for signal from main thread
    +        // ... do something interesting ...
    +        barrier.wait(); // wait for all workers to get to barrier
    +        // ... do something else interesting ...
    +        allDone.countDown();
    +        return 0;
    +      });
    +    t[i].start();
    +  }
    +  go.countDown(); // let worker threads go
    +  allDone.wait(); // wait for all workers to finish
    +
    + +

    +A Semaphore maintains a given number of permits. When a +thread acquires a permit the semaphore decremements the number of +available permits and when a thread releases the permit (any thread +can release the permit) the semaphore increments the number of +available permits. Semaphores don't have a concept of threads +owning permits - it only gives out and recieves permits atomically. +A typical use case for semaphores is to manage access by multiple +threads to a fixed collection of objects. + +

    API Reference

    +This section lists the public structs and functions in the library without +detailed explanation. For more information see the documentation before +the function or class in the source file. +The API is organized by module:
    +
    +
    locks.condition +
    locks.countdown +
    locks.exchanger +
    locks.lock +
    locks.platformutils +
    locks.readwritelock +
    locks.reentrantlock +
    locks.semaphore +
    locks.timeunit +
    + + + +

    locks.condition

    +
    +
    interface Condition +
    A condition variable +

    +

    +
    void wait() +
    Cause current thread to wait until notified +
    long waitNanos(long nanosTimeout) +
    Cause current thread to wait until notified or time expires +
    bool wait(long time, TimeUnit unit) +
    Cause current thread to wait until notified or time expires +
    void notify() +
    Wake up one waiting thread +
    void notifyAll() +
    Wake up all waiting threads +
    +
    + +
    +

    locks.countdown

    +
    +
    class CountDownLatch +
    Allow one or more threads to wait for a set of other threads. +

    +

    +
    this(int count) +
    Construct the latch with the given count before releasing +
    void wait() +
    Causes the current thread to wait until the count reaches zero +
    void wait(long timeout, TimeUnit unit) +
    Causes the current thread to wait until the count reaches zero or time expires +
    void countDown() +
    Decrement count +
    long count +
    Get the current count +
    char[] toString +
    Return a string summary of the latch +
    +
    + +
    +

    locks.cyclicbarrier

    +
    +
    class CyclicBarrier +
    Allow a fixed group of threads to wait for each other +

    +

    +
    this(int parties, int delegate() barrierAction = null) +
    Construct the barrier with given number of parties and concluding action +
    int parties +
    Return number of parties for this barrier +
    int wait() +
    Causes the current thread to wait for all parties to reach the barrier +
    int wait(long timeout, TimeUnit unit) +
    Causes the current thread to wait only for the specified time +
    bool isBroken() +
    Returns true if the barrier has been broken +
    void reset() +
    Break the barrier for waiting parties and reset to initial state +
    int getNumberWaiting +
    Get the current number of waiting parties +
    +
    + +
    +

    locks.exchanger

    +
    +
    class Exchanger(Value) +
    Allow two threads to safely exchange values. +

    +

    +
    this() +
    Construct the exchanger +
    Value exchange(Value v) +
    Offer v for exchange and wait for response +
    Value exchange(Value v, long timeout, TimeUnit unit) +
    Offer v for exchange and wait for response with possible timeout +
    +
    + +
    +

    locks.lock

    +
    +
    interface Lock +
    The interface for all lock implementations. +

    +

    +
    void lock() +
    Acquires the lock +
    bool tryLock() +
    Acquires the lock only if it is free at the time of invocation +
    bool tryLock(long time, TimeUnit unit) +
    Acquires the lock if it is free within the given waiting time +
    void unlock() +
    Releases the lock +
    Condition newCondition +
    Returns a new Condition instance that is bound to this lock instance +
    +
    +
    +
    auto final class ScopedLock +
    An auto class for aquiring and releasing a lock in a scope +

    +

    +
    this(Lock lock) +
    Initializes the ScopedLock and acquires the supplied lock +
    ~this() +
    Release the lock +
    +
    + +
    +

    locks.platformutils

    +
    +
    bit compareAndSet32(void* mem, void* expect, void* update) +
    Compare the 32 bit value expect with the value at *mem and if equal +set to update and return true. This assumes a pointer is 32 bits. +
    bit compareAndSet32(void* mem, int expect, int update) +
    Convenience overload for compareAndSet32 when the data are integers +instead of pointers +
    bit compareAndSet64(void* mem, void* expect, void* update) +
    Compare the 64 bit value at *expect with the value at *mem and if equal +set to *update and return true. +
    int atomicAdd32(int* val, int x); +
    Atomically add x to *val and return previous value of *val +
    int atomicExchange32(int* val, int x); +
    Atomically store x to *val and return previous value of *val +
    void atomicInc32(int* val); +
    Atomically increment *val +
    void atomicDec32(int* val); +
    Atomically decrement *val +
    long currentTimeMillis() +
    Return the current system time in milliseconds +
    long currentTimeNanos() +
    Return the current system time in nanoseconds +
    void sleepNanos(long duration) +
    Sleep the current thread for the specified duration in nanoseconds +
    + +
    +

    locks.readwritelock

    +
    +
    interface ReadWriteLock +
    A pair of read-write locks +

    +

    +
    Lock readLock() +
    Return the read lock +
    Lock writeLock() +
    Return the write lock +
    +
    +

    +

    +
    class ReentrantReadWriteLock : ReadWriteLock +
    A pair of reentrant read-write locks +

    +

    +
    this(bool fair = false) +
    Construct the lock with specified fairness policy +
    Lock readLock() +
    Return the read lock +
    Lock writeLock() +
    Return the write lock +
    + +
    + +
    +

    locks.reentrantlock

    +
    +
    class ReentrantLock : Lock +
    A reentrant mutual exclusive lock with condition variables +

    +

    +
    this(bool fair = false) +
    Construct the lock with specified fairness policy +
    void lock() +
    Acquires the lock +
    bool tryLock() +
    Acquires the lock only if it is free at the time of invocation +
    bool tryLock(long time, TimeUnit unit) +
    Acquires the lock if it is free within the given waiting time +
    void unlock() +
    Releases the lock +
    Condition newCondition +
    Returns a new Condition instance that is bound to this lock instance +
    int getHoldCount() +
    Get the number of holds on this lock by the current thread +
    bool isHeldByCurrentThread() +
    Query if the lock is held by the current thread +
    bool isLocked() +
    Query if the lock is held by any thread +
    bool isFair() +
    Query if the lock is fair +
    char[] toString() +
    return a string representation of the lock +
    + +
    + +
    +

    locks.semaphore

    +
    +
    class Semaphore +
    A counting semaphore for maintaining a set of permits +

    +

    +
    this(int permits, bool fair = false) +
    Construct the semaphore with the given number of permits and fairness policy +
    void acquire(int permits = 1) +
    Acquires n permits, blocking until all are available +
    bool tryAcquire(int permits = 1) +
    Acquires n permit from this semaphore only if they are immediately available +
    bool tryAcquire(long timeout, TimeUnit unit, int permits = 1) +
    Attempt acquiring n permits within the specified time interval +
    void release(int permits = 1) +
    Release n permits +
    int availablePermits +
    Get the current number of available permits +
    bool isFair() +
    return true if the semaphore is fair +
    char[] toString +
    Return a string summary of the semaphore +
    + +
    + +
    +

    locks.timeunit

    +
    +
    enum TimeUnit +
    Time units common in synchronization +
    +
    NanoSeconds = 0 +
    MicroSeconds +
    MilliSeconds +
    Seconds +
    +

    +

    long convert(long duration, TimeUnit fromUnit, TimeUnit toUnit); +
    Convert the given time duration in the given unit to this unit. +
    long toNanos(long duration, TimeUnit fromUnit); +
    Convert to nanoseconds. +
    long toMicros(long duration, TimeUnit fromUnit); +
    Convert to microseconds. +
    long toMillis(long duration, TimeUnit fromUnit); +
    Convert to milliseconds. +
    long toSeconds(long duration, TimeUnit fromUnit); +
    Convert to seconds. +
    + + + diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/mem.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/mem.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,129 @@ +/** \file mem.d + * \brief Allocators for custom container memory management + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * version 1.0 + */ + +module mintl.mem; + +private { + import tango.stdc.stdlib; + import tango.core.Memory : GC; + import tango.core.Exception : onOutOfMemoryError; +} + +/** An Allocator is a type containing 8 symbols malloc, calloc, + * realloc, free and the corresponding GC-aware versions gcMalloc, + * gcCalloc, gcRealloc and gcFree. Containers will call the GC-aware + * functions on blocks that may hold roots and otherwise will call the + * regular functions. Allocators are expected to throw OutOfMemory if + * the allocation fails. Be aware than when using an allocator with + * a container one must call the container clear() function + * to free the memory. + * + * The two predefined allocators Malloc and MallocNoRoots use + * std.c.stdlib.malloc to perform allocations. The MallocNoRoots + * ignores any requests by the container to register roots with the + * GC. The MallocNoRoots allocator should only be used with containers + * that the user knows will never contain any roots (e.g. ArrayList!(int)) + */ + +/** Malloc and throw OutOfMemory if fails. */ +void* mallocWithCheck(size_t s) { + void* p = malloc(s); + if (!p) + onOutOfMemoryError(); + return p; +} + +/** Calloc and throw OutOfMemory if fails. */ +void* callocWithCheck(size_t n, size_t s) { + void* p = calloc(n,s); + if (!p) + onOutOfMemoryError(); + return p; +} + +/** Realloc and throw OutOfMemory if fails. */ +void* reallocWithCheck(void*p, size_t s) { + p = realloc(p,s); + if (!p) + onOutOfMemoryError(); + return p; +} + +/** Free pointer. */ +void dfree(void*p) { + free(p); +} + +/** Malloc and register the range with GC. */ +void* gcMalloc(size_t s) { + void* p = mallocWithCheck(s); + GC.addRange(p,s); + return p; +} + +/** Calloc and register the range with GC. */ +void* gcCalloc(size_t n, size_t s) { + void* p = callocWithCheck(n,s); + GC.addRange(p,n*s); + return p; +} + +/** Realloc and register the range with GC. */ +void* gcRealloc(void* p, size_t s) { + if (p) + GC.removeRange(p); + p = reallocWithCheck(p,s); + GC.addRange(p,s); + return p; +} + +/** Deregister the range with GC and free. */ +void gcFree(void* p) { + if (p) + GC.removeRange(p); + free(p); +} + +// Default Allocator +struct GCAllocator{ + alias void malloc; + alias void calloc; + alias void realloc; + alias void free; + alias void gcMalloc; + alias void gcCalloc; + alias void gcRealloc; + alias void gcFree; +} + +// An allocator that uses malloc +struct Malloc { + alias mallocWithCheck malloc; + alias callocWithCheck calloc; + alias reallocWithCheck realloc; + alias dfree free; + alias .gcMalloc gcMalloc; + alias .gcCalloc gcCalloc; + alias .gcRealloc gcRealloc; + alias .gcFree gcFree; +} + +// An allocator that uses malloc and assumes allocations have no roots +struct MallocNoRoots { + alias mallocWithCheck malloc; + alias callocWithCheck calloc; + alias reallocWithCheck realloc; + alias dfree free; + alias mallocWithCheck gcMalloc; + alias callocWithCheck gcCalloc; + alias reallocWithCheck gcRealloc; + alias dfree gcFree; +} + diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/multiaa.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/multiaa.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,191 @@ +/** \file multiaa.d + * \brief An associative array that allows multiple values per key. + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * The red-black tree code is by Thomas Niemann. + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 1.2 + */ + +module mintl.multiaa; + +private import mintl.share; +private import mintl.adapter; +private import mintl.sortedaa; +private import mintl.hashaa; +private import std.stdarg; +private import std.boxer; + +//version = WithBox; + +/** An associative array of items with duplicate keys. + * By default the backing container is a builtin associative array. + */ +struct MultiAA(Key, Value, ImplType = HashAA!(Key,Value[])) { + + alias MultiAA ContainerType; + alias Value ValueType; + alias Key IndexType; + alias ImplType AdaptType; + const bit isReadOnly = ImplType.isReadOnly; + + ImplType impl; + + size_t length() { + size_t total = 0; + foreach(Value[] val; impl) { + total += val.length; + } + return total; + } + int opEquals(MultiAA c) { return impl == c.impl; } + static if (!ImplType.isReadOnly) { + void remove(Key key) { + impl.remove(key); + } + void remove(Key key, Value val) { + Value[]* vals = impl.get(key); + if (vals) { + size_t k; + Value[] x = *vals; + for(k = 0; kaddTail repeatedly. + */ + void add(...) { + vadd(_arguments,_argptr); + } + void vadd(TypeInfo[] arguments, void* argptr) { + for (int k=0;ktail + * property. + * Indexing out of bounds throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + Container.ValueType opIndex(size_t n) { + return getNode(n).data; + } + + static if (!Container.isReadOnly) { + + /** Get a pointer to the nth item in the list from head. The + * operation is O(n). To efficiently access the tail of the list + * use the tail property. Indexing out of bounds throws an + * IndexOutOfBoundsException unless version=MinTLNoIndexChecking is + * set. + */ + Container.ValueType* lookup(size_t n) { + return &getNode(n).data; + } + + /** Set the nth item in the list from head. The operation is O(n). + * To efficiently access the tail of the list use the tail + * property. + * Indexing out of bounds throws an IndexOutOfBoundsException unless + * version=MinTLNoIndexChecking is set. + */ + void opIndexAssign(Container.ValueType val, size_t n) { + getNode(n).data = val; + } + + } // !ReadOnly + + /** Iterates over the list from head to tail calling delegate to + * perform an action. The value is passed to the delegate. + */ + int opApplyNoKey(int delegate(inout Container.ValueType x) dg){ + int dg2(inout size_t count, inout Container.ValueType val) { + return dg(val); + } + return opApplyWithKey(&dg2); + } + + /** Iterates over the list 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 Container.ValueType x) dg){ + Container.Node* i = head_; + Container.Node* end = tail_; + int res = 0; + size_t n = 0; + while (i !is null) { + res = dg(n, i.data); + if (res || i is end) break; + n++; + i = i.next; + } + return res; + } + + /** Iterates over the list from head to tail calling delegate to + * perform an action. A one-item sub-list is passed to the delegate. + */ + int opApplyIter(int delegate(inout Container.SliceType n) dg){ + Container.Node* i = head_; + Container.Node* end = tail_; + int res = 0; + Container.SliceType n; + while (i !is null) { + n.head_ = n.tail_ = i; + res = dg(n); + if (res || i is end) break; + i = i.next; + } + return res; + } + + /** Test for equality of two lists. The operation is O(n) where n + * is length of the list. + */ + int opEquals(Container c) { + Container.Node* i = head_; + Container.Node* j = c.head_; + Container.Node* t = tail_; + Container.Node* ct = c.tail_; + TypeInfo ti = typeid(Container.ValueType); + while (i !is null && j !is null) { + if (!ti.equals(&i.data,&j.data)) + return 0; + if (i is t && j is ct) + return 1; + i = i.next; + j = j.next; + } + return (i is null && j is null); + } + + /** Compare two lists. */ + int opCmp(Container c) { + Container.Node* i = head_; + Container.Node* j = c.head_; + Container.Node* t = tail_; + Container.Node* ct = c.tail_; + TypeInfo ti = typeid(Container.ValueType); + while (i !is null && j !is null) { + int cmp = ti.compare(&i.data,&j.data); + if (cmp) + return cmp; + if (i is t && j is ct) + return 0; + i = i.next; + j = j.next; + } + if (i is null && j is null) + return 0; + else + return (i is null) ? -1 : 1; + } + + /** Create a one-item slice of the head. */ + Container.SliceType head() { + return opSlice(0,1); + } + + /** Return a one-item slice at the tail. */ + Container.SliceType tail() { + Container.SliceType res; + res.head_ = res.tail_ = tail_; + return res; + } + + /** Create a sub-list from index a to b (exclusive). The operation is + * O(max(a,b)). */ + Container.SliceType opSlice(size_t a, size_t b) { + Container.SliceType res; + if (a != b) { + res.head_ = getNode(a); + Container.Node *v = res.head_; + b = b-a-1; + while (b--) + v = v.next; + res.tail_ = v; + } + return res; + } + + /** Create a sub-list from the head of a to the tail of b (inclusive). */ + Container.SliceType opSlice(Container.SliceType a, Container.SliceType b) { + if (a.head_ is null) + return b; + if (b.head_ is null) + return a; + Container.SliceType res; + res.head_ = a.head_; + res.tail_ = b.tail_; + return res; + } + + /** Copies the list contents to an array. */ + Container.ValueType[] values() { + Container.ValueType[] buffer = new Container.ValueType[length()]; + foreach(size_t n, Container.ValueType val; *this) { + buffer[n] = val; + } + return buffer; + } +} + +/** \class SList + * \brief A singly-linked list. + * + * A SList!(Value) is a singly linked list of data of type Value. A + * list is similar to a dynamic array except accessing an element in + * the middle or near the end of the list is O(n) and appending to the + * front or back is O(1). Any operation that is not constant-time will + * explicitly have the performance behavior documented. + * + * A singly-linked list differs from a doubly-linked list in the speed + * of accessing elements near the end of the list and the ability to + * reverse, addBefore iterate backwards and + * remove a sublist. The only operations supported in the + * middle of a singly-linked list are operations that modify the items + * that follow the sublist. This prevents manipulations in one sublist + * from invalidating an adjacent sublist. + * + * The optional ReadOnly parameter SList!(Value,ReadOnly) forbids + * operations that modify the container. The readonly() property returns + * a ReadOnly view of the container. + * + * The optional allocator parameter SList!(Value,false,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct SList(Value, bit ReadOnly = false, Alloc = GCAllocator) { + + alias SList ContainerType; + alias SList SliceType; + alias Value ValueType; + alias size_t IndexType; + alias SNode!(Value) Node; + alias ReadOnly isReadOnly; + + const int NodeAllocationBlockSize = 10; // allocate 10 nodes at a time + + // private bug private { + Node* head_; // head_ is first item + Node* tail_; // tail_ is last item + // } + + mixin MCommonSList!(head_, SList ); + + SList getThis(){return *this;} + mixin MListAlgo!(SList, getThis); + + /** Get a ReadOnly view of the container */ + .SList!(Value, true, Alloc) readonly() { + .SList!(Value, true, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get a read-write view of the container */ + .SList!(Value, false, Alloc) readwrite() { + .SList!(Value, false, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + static if (!ReadOnly) { + + /** Appends an item to the tail of the list. If the target list is + * a sub-list call addAfter instead of addTail to insert an item + * after a sub-list. + */ + void addTail(Value v) { + if (tail_ is null) { + // no available nodes so allocate a new one + tail_ = newNode(); + } else { + tail_ = tail_.next; + } + tail_.data = v; + if (head_ is null) + head_ = tail_; + } + + /** Appends a list to the tail of the target list. If the target + * list is a sub-list call addAfter instead of addTail to insert + * another list after a sub-list. + */ + void addTail(SList v) { + if (v.head_ is null) + return; + tail_.next = v.head_; + tail_ = v.tail_; + if (head_ is null) + head_ = v.head_; + } + + mixin MListCatOperators!(SList); + + /** Prepends an item to the head of the target list. */ + void addHead(Value v) { + if (head_ is null) { + addTail(v); + } else if (tail_.next is null) { + // no available nodes so allocate a new one + Node* t = head_; + head_ = new Node(); + head_.data = v; + head_.next = t; + } else { + // grab available node from end + Node* t = tail_.next; + tail_.next = t.next; + t.next = head_; + head_ = t; + t.data = v; + } + } + + /** Prepends a list to the head of the target list. */ + void addHead(SList v) { + if (v.head_ is null) + return; + Node* t = head_; + head_ = v.head_; + v.tail_.next = t; + if (tail_ is null) + tail_ = v.tail_; + } + + /** Removes and returns the head item of the list. The node that + * contained the item may be reused in future additions to the + * list. To prevent the node from being reused call trim. + * If the target list is empty an IndexOutOfBoundsException is thrown + * unless version=MinTLNoIndexChecking is set. + */ + Value takeHead() { + boundsCheck(head_); + Node* v = head_; + head_ = v.next; + // save node for future reuse + v.next = tail_.next; + tail_.next = v; + Value data = v.data; + v.data = Value.init; + return data; + } + + /** Removes the head item of the list. */ + void removeHead() { + boundsCheck(head_); + Node* v = head_; + head_ = v.next; + // save node for future reuse + v.next = tail_.next; + tail_.next = v; + v.data = Value.init; + } + + /** Insert a list after a sub-list. */ + void addAfter(SList subv, SList v) { + if (v.tail_ is null) + return; + Node* t = subv.tail_; + if (t is null) { + *this = v; + return; + } + v.tail_.next = t.next; + t.next = v.head_; + if (t is tail_) + tail_ = v.tail_; + } + + /** Trims off extra nodes that are not actively being used by the + * list but are available for recyling for future add operations. + */ + void trim() { + if (tail_ !is null) + tail_.next = null; + } + + /** Removes n items after a sublist. */ + void removeAfter(SList sublist, size_t n = 1) { + if (sublist.head_ is null) + return; + boundsCheck(head_); + Node* t = sublist.tail_; + Node* newt = t.next; + while (n--) + newt = newt.next; + t.next = newt; + if (newt is tail_) + tail_ = t; + } + + /** Removes items between the tail of a to the head to b (exclusive). */ + void removeBetween(SList a, SList b) { + // what to do if a or b is null? + boundsCheck(head_); + a.tail_.next = b.head_; + } + + /** Set the value of one-item slice (more generally the head value). */ + void value(Value newValue) { + head_.data = newValue; + } + + } // !ReadOnly + + /** Move a sub-list towards the tail by n items. By default moves + * to the next item. + */ + void next(int n = 1, int end = 0) { + while (n-- > 0) { + if (end <= 0) + head_ = head_.next; + if (end >= 0) + tail_ = tail_.next; + } + } + + /** Duplicates a list. */ + .SList!(Value,ReadOnly,Alloc) dup() { + .SList!(Value,false,Alloc) res; + foreach(ValueType val; *this) { + res ~= val; + } + static if (ReadOnly) { + return res.readonly; + } else { + return res; + } + } + + /** Get the value of one-item slice (more generally the head value). + * Useful for expressions like x.tail.value or x.head.value. */ + Value value() { + return head_.data; + } + + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + alias opApplyIter opApply; + + private Node* newNode() { + static if (is(Alloc == GCAllocator)) { + // allocate a block of nodes and return pointer to first one + Node[] block = new Node[NodeAllocationBlockSize]; + for (int k=1; kadd and remove functions and + * slices can be moved forward around the list indefinitely. A CircularSList + * also has a smaller memory footprint since it requires only one + * pointer for the tail instead of two pointers for a tail and head. + * + * The optional ReadOnly parameter CircularSList!(Value,ReadOnly) forbids + * operations that modify the container. The readonly() property returns + * a ReadOnly view of the container. + * + * The optional allocator parameter CircularSList!(Value,false,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct CircularSList(Value, bit ReadOnly = false, Alloc = GCAllocator) { + + alias CircularSList ContainerType; + alias SList!(Value,ReadOnly,Alloc) SliceType; + alias Value ValueType; + alias size_t IndexType; + alias SNode!(Value) Node; + alias ReadOnly isReadOnly; + + private { + Node* tail_; // tail_ is last item + } + + /** Return the circular list as a non-circular SList. */ + SliceType toSList() { + SliceType res; + if (tail_ is null) + return res; + res.head_ = tail_.next; + res.tail_ = tail_; + return res; + } + + /** Get a ReadOnly view of the container */ + .CircularSList!(Value, true, Alloc) readonly() { + .CircularSList!(Value, true, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get a read-write view of the container */ + .CircularSList!(Value, false, Alloc) readwrite() { + .CircularSList!(Value, false, Alloc) res; + res = *cast(typeof(&res))this; + return res; + } + + static if (!ReadOnly) { + + /** Appends an item to the tail of the list. If the target list is + * a sub-list call addAfter instead of addTail to insert an item + * after a sub-list. + */ + void addTail(Value v) { + Node* n = new Node; + n.data = v; + addNode(n); + tail_ = n; + } + + /** Adds a node after tail. */ + private void addNode(Node* n) { + if (tail_ is null) { + n.next = n; + tail_ = n; + } else { + n.next = tail_.next; + tail_.next = n; + } + } + + /** Appends a list to the tail of the target list. If the target + * list is a sub-list call addAfter instead of addTail to insert + * another list after a sub-list. + */ + void addTail(CircularSList v) { + addHead(v); + tail_ = v.tail_; + } + + mixin MListCatOperators!(CircularSList); + + /** Appends an item to the tail of the list. If the target list is + * a sub-list call addAfter instead of addTail to insert an item + * after a sub-list. + */ + void addHead(Value v) { + Node* n = newNode(); + n.data = v; + addNode(n); + } + + /** Appends a list to the tail of the target list. If the target + * list is a sub-list call addAfter instead of addTail to insert + * another list after a sub-list. + */ + void addHead(CircularSList v) { + if (v.tail_ is null) + return; + if (tail_ is null) { + tail_ = v.tail_; + return; + } + v.tail_.next = tail_.next; + tail_.next = v.tail_; + } + + /** Removes and returns the head item of the list. */ + Value takeHead() { + boundsCheck(tail_); + Node* v = tail_.next; + tail_.next = v.next; + Value val = v.data; + freeNode(v); + return val; + } + + /** Removes the head item of the list. */ + void removeHead() { + boundsCheck(tail_); + Node* v = tail_.next; + tail_.next = v.next; + freeNode(v); + } + + /** Clear all contents. */ + void clear() { + static if (is(Alloc == GCAllocator)) { + } else { + Node* i = head_; + if (i !is null) + tail_.next = null; + while (i !is null) { + Node* next = i.next; + Alloc.gcFree(i); + i = next; + } + } + *this = CircularSList.init; + } + + /** Insert a list after a sub-list. */ + void addAfter(SliceType subv, SliceType v) { + if (v.tail_ is null) + return; + Node* t = subv.tail_; + if (t is null) { + tail_ = v.tail_; + return; + } + v.tail_.next = t.next; + t.next = v.head_; + if (t is tail_) + tail_ = v.tail_; + } + + /** Removes n items after a sublist. */ + void removeAfter(SliceType sublist, size_t n = 1) { + if (sublist.head_ is null) + return; + boundsCheck(tail_); + Node* t = sublist.tail_; + Node* newt = t.next; + while (n--) { + Node* i = newt; + newt = newt.next; + freeNode(i); + } + t.next = newt; + if (newt is tail_) + tail_ = t; + } + + /** Removes items between the tail of a to the head to b (exclusive). + * If a custom allocator is used the memory is not freed automatically. + */ + void removeBetween(SliceType a, SliceType b) { + // what to do if a or b is null? + boundsCheck(tail_); + a.tail_.next = b.head_; + } + + } // !ReadOnly + + /** Duplicates a list. */ + .CircularSList!(Value,ReadOnly,Alloc) dup() { + .CircularSList!(Value,false,Alloc) res; + foreach(ValueType val; *this) { + res ~= val; + } + static if (ReadOnly) { + return res.readonly; + } else { + return res; + } + } + + /** Rotate the list. */ + void rotate(int n = 1) { + while (n-- > 0) + tail_ = tail_.next; + } + + private Node* head_() { + if (tail_ is null) return null; + return tail_.next; + } + + CircularSList getThis(){return *this;} + mixin MListAlgo!(CircularSList, getThis); + + mixin MCommonSList!(head_, CircularSList ); + + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + alias opApplyIter opApply; + + private Node* newNode() { + static if (is(Alloc == GCAllocator)) { + return new Node; + } else { + Node* p = cast(Node*)Alloc.gcMalloc(Node.sizeof); + *p = Node.init; + return p; + } + } + + private void freeNode(Node* n) { + static if (is(Alloc == GCAllocator)) { + } else { + Alloc.gcFree(n); + } + } +} + +//version = MinTLVerboseUnittest; +//version = MinTLUnittest; + +version (MinTLUnittest) { + unittest { + version (MinTLVerboseUnittest) + printf("starting mintl.slist unittest\n"); + SList!(int) x; + x.add(3,4); + assert( x[0] == 3 ); + assert( x[1] == 4 ); + assert( x.length == 2 ); + + // test addHead + SList!(int) y; + y.addHead(4); + y.addHead(3); + + // test == + assert( x == y ); + SList!(int) w = x.dup; + w ~= 5; + assert( x != w); + + // test remove + assert( w.takeHead() == 3 ); + w.trim(); + w.addHead(3); + + SList!(int) z = x.dup; + // test foreach iteration + foreach(size_t n, inout int val; z) { + val = n*10; + } + assert( z[0] == 0 ); + assert( z[1] == 10 ); + int n = 0; + foreach(SList!(int) itr; z) { + assert(itr[0] == z[n++]); + } + + // test slicing + SList!(int) v = w[1..3]; + assert( v.length == 2 ); + assert( v[0] == 4 ); + assert( v[1] == 5 ); + + // test algorithms + assert( v.opIn(5) == v.tail ); + assert( v.count(5) == 1 ); + + // test another node type + SList!(char[]) str; + str ~= "hello"; + str ~= "world"; + assert( str[str.length-1] == "world" ); + + // test sub-list spanning + SList!(int) tmp; + int[10] tmp2; + tmp2[3] = 100; + tmp2[8] = 200; + foreach(int xx;tmp2) + tmp ~= xx; + SList!(int) a,b,c; + a = tmp[3..5]; + b = tmp[7..9]; + c = tmp[a..b]; + assert( c.length == 6 ); + assert( c[0] == 100 ); + assert( c[5] == 200 ); + + // CircularSList + + CircularSList!(int) cx; + cx.add(3,4); + assert( cx[0] == 3 ); + assert( cx[1] == 4 ); + assert( cx.length == 2 ); + + // test addHead + CircularSList!(int) cy; + cy.addHead(4); + cy.addHead(3); + + // test == + assert( cx == cy ); + CircularSList!(int) cw = cx.dup; + cw ~= 5; + assert( cx != cw); + + // test remove + assert( cw.takeHead() == 3 ); + cw.addHead(3); + + CircularSList!(int) cz = cx.dup; + // test foreach iteration + foreach(size_t n, inout int val; cz) { + val = n*10; + } + assert( cz[0] == 0 ); + assert( cz[1] == 10 ); + n = 0; + foreach(SList!(int) itr; cz) { + assert(itr[0] == cz[n++]); + } + + // test slicing + SList!(int) cv = cw[1..3]; + assert( cv.length == 2 ); + assert( cv[0] == 4 ); + assert( cv[1] == 5 ); + + // test algorithms + assert( cv.opIn(5) == cv.tail ); + assert( cv.count(5) == 1 ); + + // test another node type + CircularSList!(char[]) cstr; + cstr ~= "hello"; + cstr ~= "world"; + assert( cstr[cstr.length-1] == "world" ); + + // test sub-list spanning + CircularSList!(int) ctmp; + int[10] ctmp2; + ctmp2[3] = 100; + ctmp2[8] = 200; + foreach(int xx; ctmp2) + ctmp ~= xx; + SList!(int) ca,cb,cc; + ca = ctmp[3..5]; + cb = ctmp[7..9]; + cc = ctmp[a..b]; + assert( cc.length == 6 ); + assert( cc[0] == 100 ); + assert( cc[5] == 200 ); + + version (MinTLVerboseUnittest) + printf("finished mintl.slist unittest\n"); + } +} + diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/sortedaa.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/sortedaa.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,1033 @@ +/** \file sortedaa.d + * \brief A sorted associative array. + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * The red-black tree code is by Thomas Niemann. + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 2.7.1 + */ + +module mintl.sortedaa; + +private import mintl.share; // for mixins +import mintl.mem; + +// debug = dSortedAA; // can also pass at command line +//debug(dSortedAA) { +// private import std.stdio; +//} + +/** \class CompareFcnSetException + * \brief An exception thrown when attempting to set the compare + * function twice. In particular it cannot be set on a non-empty + * SortedAA. + */ +class CompareFcnSetException: Exception { + this(char[] str) { super(str); } + this() { super("Cannot set the comparison function twice"); } +} + +/** \class SortedAA + * \brief A sorted associative array. + * + * A SortedAA!(Key,Value) represents a sorted associative array with + * keys of type Key and values of type Value. A sorted associative + * array is similar to a builtin associative array except accessing an + * elements is O(log(n)), where n is the number of elements in the + * array, instead of O(1) and the elements are sorted by key. Any + * operation that is not O(log(n)) will explicitly have the + * performance behavior documented. + * + * The array is sorted by default according to the key's TypeInfo compare + * function. To use a custom key order call the CompareFcn property setter + * with a delegate of the form int delegate(Key* a, Key* b). The comparison + * function cannot be set after any elements are inserted. + * + * The optional ReadOnly parameter SortedAA!(Key,Value,ReadOnly) forbids + * operations that modify the container. The readonly() property returns + * a ReadOnly view of the container. + * + * The optional allocator parameter SortedAA!(Key,Value,false,Allocator) is used + * to allocate and free memory. The GC is the default allocator. + */ +struct SortedAA(Key,Value, bit ReadOnly = false, Alloc = GCAllocator) { + + alias SortedAA ContainerType; + alias SortedAA SliceType; + alias Value ValueType; + alias Key IndexType; + alias ReadOnly isReadOnly; + + /** Get a ReadOnly view of the container */ + .SortedAA!(Key,Value,true) readonly() { + .SortedAA!(Key,Value,true) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get a read-write view of the container */ + .SortedAA!(Key,Value,false) readwrite() { + .SortedAA!(Key,Value,false) res; + res = *cast(typeof(&res))this; + return res; + } + + /** Get the kays in the array. The operation is O(n) where n is the number of + * elements in the array. + */ + Key[] keys() { + Key[] res; + foreach(Key k,Value v;*this) + res ~= k; + return res; + } + + /** Get the values in the array. The operation is O(n) where n is the number of + * elements in the array. + */ + Value[] values() { + Value[] res; + foreach(Key k,Value v;*this) + res ~= v; + return res; + } + + /** Property for the default value of the array when a key is missing. */ + void missing(Value val) { + fixupShared(); + shared.missing = val; + } + Value missing() { + if (!shared) + return Value.init; + return shared.missing; + } + + /** Length of array. The operation is O(n) where n is the number of + * elements in the array. + */ + size_t length() { + size_t len = 0; + foreach(Value val; *this) + len++; + return len; + } + + /** Test if array is empty. */ + bool isEmpty() { + return shared is null || shared.root is null; + } + + static if (ReadOnly) { + + /** Duplicates an array. */ + SortedAA dup() { + .SortedAA!(Key,Value,false) res; + if (shared) { + if (shared.cmpFcn) + res.compareFcn = shared.cmpFcn; + res.missing = missing; + } + foreach(Key k,Value v;*this) + res[k] = v; + return res.readonly; + } + + } else { + + /** Clear all contents. */ + void clear() { + static if (is(Alloc == GCAllocator)) { + } else { + if (shared) { + void freeNode(Node*p) { + if(p) { + freeNode(p.left); + freeNode(p.right); + Alloc.gcFree(p); + } + } + freeNode(shared.root); + Alloc.gcFree(shared); + } + } + *this = SortedAA.init; + } + + /** Remove a key from the array. The target array can be a sub-array though + * the key may fall outside of the sub-array range. The value stored for + * the key is returned, if present. + */ + Value take(Key key) { + // debug(dSortedAA) writefln("getAndRemove: %s",key); + Node* node = getNode(key,NullOnMiss); + if (!node) return missing; + Value value = node.val; + deleteNode(node); + return value; + } + + /** Remove a key from the array. The target array can be a sub-array though + * the key may fall outside of the sub-array range. + */ + void remove(Key key) { + // debug(dSortedAA) writefln("remove: %s",key); + deleteNode(getNode(key,NullOnMiss)); + } + + /** Remove a sub-array from the array. The operation is O(max(log(m),n)) + * where m is the size of the target array and n is the number of + * elements in the sub-array. + */ + void remove(SortedAA subarray) { + if (subarray.head_ is subarray.tail_) { + deleteNode(subarray.head_); + } else { + Key[] keylist = subarray.keys; + foreach(Key key;keylist) + remove(key); + } + } + + /** Duplicates an array. */ + SortedAA dup() { + SortedAA res; + if (shared) { + if (shared.cmpFcn) + res.compareFcn = shared.cmpFcn; + res.missing = missing; + } + foreach(Key k,Value v;*this) + res[k] = v; + return res; + } + + } // !ReadOnly + + /** signature for a custom comparison function */ + alias int delegate(Key* a, Key* b) CompareFcn; + + /** Set custom comparison function. If the array is non-empty or the + * comparison function has already been set a CompareFcnSetException + * is thrown. + */ + void compareFcn(CompareFcn cmp) { + allocShared(); + if (shared.cmpFcn !is null) + throw new CompareFcnSetException(); + else + shared.cmpFcn = cmp; + } + + /** Find (and insert if not present) the element with a given key + * and return the value. The target array can be a sub-array though + * the key may fall outside of the sub-array range. + */ + Value opIndex(Key key) { + Node* t = getNode(key,NullOnMiss); + if (t) + return t.val; + else + return missing; + } + + /** Store a value with a key, overwriting any previous value. The + * target array can be a sub-array though the key may fall outside of the + * sub-array range. + */ + void opIndexAssign(Value val, Key key) { + Node* t = getNode(key,InsertOnMiss); + t.val = val; + } + + /** Returns the value of the first item of a slice. In particular gets + * the value of a one-item slice. + */ + Value value() { + if (head_ is null && tail_ is null) + return Value.init; + return head_.val; + } + + /** Returns the key of the first item of a slice. In particular gets + * the key of a one-item slice. + */ + Key key() { + if (head_ is null && tail_ is null) + return Key.init; + return head_.key; + } + + /** Return the start of the sorted items (the min). */ + SortedAA head() { + Node* node = head_ is null ? minNode() : head_; + SortedAA res; + res.shared = shared; + res.head_ = res.tail_ = node; + return res; + } + + /** Return the end of the sorted items (the max). */ + SortedAA tail() { + Node* node = tail_ is null ? maxNode() : tail_; + SortedAA res; + res.shared = shared; + res.head_ = res.tail_ = node; + return res; + } + + /** Return a one-item slice of the item less than key */ + SortedAA to(Key key) { + SortedAA res; + res.shared = shared; + res.head_ = res.tail_ = lookupSide(key,false); + return res; + } + + /** Return a one-item slice of the item greater than or equal to key */ + SortedAA from(Key key) { + SortedAA res; + res.shared = shared; + res.head_ = res.tail_ = lookupSide(key,true); + return res; + } + + /** Move a slice towards the head or tail by n items. If n is + * negative the slice moves towards the head. A positive end is + * the tail, negative the head and 0 is both. By default moves to + * the next item. + */ + void next(int n = 1, int end = 0) { + void doNext(inout Node* node, int m) { + while (m--) + node = nextNode(node); + } + void doPrev(inout Node* node, int m) { + while (m--) + node = prevNode(node); + } + if (n > 0) { + if (end >= 0) + doNext(tail_,n); + if (end <= 0) + doNext(head_,n); + } else { + n = -n; + if (end >= 0) + doPrev(tail_,n); + if (end <= 0) + doPrev(head_,n); + } + } + + /** Find the element with a given key and return a pointer to the + * value. If the key is not in the array null is returned or if + * throwOnMiss is true an exception is thrown. The target array can + * be a sub-array though the key may fall outside of the sub-array + * range. + */ + Value* get(Key key, bool throwOnMiss = false) { + Node* t = getNode(key,throwOnMiss ? ThrowOnMiss : NullOnMiss); + if (t) + return &t.val; + else + return null; + } + + /** Find a key in the array and return a pointer to the associated value. + * Insert the key and initialize with Value.init if the key is not + * in the array. + */ + Value* put(Key key) { + Node* t = getNode(key, InsertOnMiss); + return &t.val; + } + + /** Create a slice from the head of a to the tail in b (inclusive). */ + SortedAA opSlice(SortedAA a, SortedAA b) { + SortedAA res; + res.head_ = a.head_ is null ? minNode() : a.head_; + res.tail_ = b.tail_ is null ? maxNode() : b.tail_; + res.shared = shared; + return res; + } + + /** Create a sub-array from key a to b (exclusive). */ + SortedAA opSlice(Key a, Key b) { + return (*this)[from(a) .. to(b)]; + } + + /** Create a sub-array from slice a to key b (exclusive). */ + SortedAA opSlice(SortedAA a, Key b) { + return (*this)[a .. to(b)]; + } + /** Create a sub-array from key a to slice b (inclusive). */ + SortedAA opSlice(Key a, SortedAA b) { + return (*this)[from(a) .. b]; + } + + /** Test for equality of two arrays. The operation is O(n) where n + * is length of the array. + */ + int opEquals(SortedAA c) { + fixupShared(); + c.fixupShared(); + Node* i = head_ ? head_ : minNode(); + Node* j = c.head_ ? c.head_ : c.minNode(); + Node* end = tail_ ? tail_ : maxNode(); + Node* cend = c.tail_ ? c.tail_ : c.maxNode(); + TypeInfo ti_k = typeid(Key); + TypeInfo ti_v = typeid(Value); + int do_test(Node*p1,Node*p2) { + if (p1 is null && p2 is null) + return 1; + if ((p1 is null && p2 !is null) || + (p1 !is null && p2 is null)) + return 0; + if (!ti_k.equals(&p1.key,&p2.key)) + return 0; + if (!ti_v.equals(&p1.val,&p2.val)) + return 0; + return 1; + } + while (i !is end && j !is cend) { + if (!do_test(i,j)) + return 0; + i = nextNode(i); + j = c.nextNode(j); + } + return do_test(i,j); + } + + /** Test if a key is in the array. The target array can be a sub-array + * but the key may fall outside of the sub-array range. + */ + bool contains(Key key) { + Value* node = get(key); + return node !is null; + } + + /** Test if a key is in the array and set value if it is. */ + bool contains(Key key,out Value value) { + Value* node = get(key); + if (node) + value = *node; + return node !is null; + } + + /** Iterate over the array calling delegate to perform an action. + * The value is passed to the delegate. + */ + int opApplyNoKeyStep(int delegate(inout Value val) dg, int step=1) { + int dg2(inout SortedAA itr) { + Value value = itr.value; + return dg(value); + } + return opApplyIterStep(&dg2,step); + } + + /** Iterate over the array calling delegate to perform an action. + * The key and value are passed to the delegate. + */ + int opApplyWithKeyStep(int delegate(inout Key key, inout Value val) dg, + int step = 1) { + int dg2(inout SortedAA itr) { + Key key = itr.key; + Value value = itr.value; + return dg(key,value); + } + return opApplyIterStep(&dg2,step); + } + + /** Iterate over the array calling delegate to perform an action. A + * one-element sub-array is passed to the delegate. + */ + int opApplyIterStep(int delegate(inout SortedAA itr) dg,int step=1) { + SortedAA itr; + itr = *this; + int res; + if (shared is null) return 0; + Node* i = head_ ? head_ : minNode(); + Node* j = tail_ ? tail_ : maxNode(); + Node* x = step>0?i:j; + Node* end = step>0?j:i; + while (x !is null) { + itr.head_ = itr.tail_ = x; + res = dg(itr); + if (res || x is end) return res; + x = step>0?nextNode(x):prevNode(x); + } + return res; + } + + /** Iterate backwards over the array (from last to first key). This + * should only be called as the iteration parameter in a + * foreach statement + */ + SortedAAReverseIter!(Key,Value,ReadOnly,Alloc) backwards() { + SortedAAReverseIter!(Key,Value,ReadOnly,Alloc) res; + res.list = this; + return res; + } + + /** Helper functions for opApply */ + mixin MOpApplyImpl!(SortedAA); + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + alias opApplyIter opApply; + mixin MAddAA!(SortedAA); // mixin add function + + // End of public interface + + private { + enum Color:int { Red, Black } + // share some data between array and sub-arrays to make updating + // easier and shrink the SortedAA footprint. + struct SharedArrayData { + Node* root; + CompareFcn cmpFcn; + Value missing; + Node* freelist; + } + struct Node { + Node* left, right, parent; + Color color; + Key key; + Value val; + } + SharedArrayData *shared; + Node* head_, tail_; + } + + debug(dSortedAA) { + private void dumpTree(Node* x, char[] str,int indent) { + if (x !is null) { + int n = indent; + while (n--) printf(" "); + printf("%.*s %p: %d %.*s\n",str,x,x.color,x.key); + dumpTree(x.left,"left",indent+1); + dumpTree(x.right,"right",indent+1); + } + } + } + + // lookup the smallest item greater than or equal to key (from) + // or lookup the largest item less than key + Node* lookupSide(Key key, bool from) { + Node* current; + Node* parent; + fixupShared(); + current = shared.root; + parent = current; + int cmpVal = 0; + CompareFcn cmp = shared.cmpFcn; + while (current !is null) { + cmpVal = cmp(&key,¤t.key); + if (cmpVal == 0) { + return from?current:prevNode(current); + } + parent = current; + current = cmpVal < 0 ? current.left : current.right; + } + if (!parent) throw new Exception("Invalid Index"); + if (from) + return cmpVal<0?prevNode(parent):parent; + else + return cmpVal>0?nextNode(parent):parent; + } + + // initialize shared data if null + private void allocShared() { + if (shared is null) { + static if (is(Alloc == GCAllocator)) { + shared = new SharedArrayData; + } else { + shared = cast(SharedArrayData*)Alloc.gcMalloc(SharedArrayData.sizeof); + *shared = SharedArrayData.init; + } + } + } + + // initialize shared data if null and initialize cmpFcn + private void fixupShared() { + allocShared(); + if (shared.cmpFcn is null) { + TypeInfo ti = typeid(Key); + shared.cmpFcn = cast(CompareFcn)&ti.compare; + } + } + + // return the next largest node or null if none + // used when we can't traverse the whole tree + private Node* nextNode(Node* x) { + if (x.right !is null) { + x = x.right; + while (x.left != null) x = x.left; + } else { + while (x.parent !is null && x.parent.right == x) + x = x.parent; + if (x.parent !is null && x.parent.left == x) + x = x.parent; + else + x = null; + } + return x; + } + + // return the previous node or null if none + // used when we can't traverse the whole tree + private Node* prevNode(Node* x) { + if (x.left !is null) { + x = x.left; + while (x.right != null) x = x.right; + } else { + while (x.parent !is null && x.parent.left == x) + x = x.parent; + if (x.parent !is null && x.parent.right == x) + x = x.parent; + else + x = null; + } + return x; + } + + // fixup Red-Black invariant + private void rotateLeft(Node* x) { + Node* y = x.right; + assert( y !is null ); + x.right = y.left; + if (y.left !is null) + y.left.parent = x; + y.parent = x.parent; + if (x.parent !is null) { + if (x is x.parent.left) + x.parent.left = y; + else + x.parent.right = y; + } else { + shared.root = y; + } + y.left = x; + if (x !is null) x.parent = y; + } + + // fixup Red-Black invariant + private void rotateRight(Node* x) { + Node* y = x.left; + assert( y !is null ); + x.left = y.right; + if (y.right !is null) + y.right.parent = x; + y.parent = x.parent; + if (x.parent !is null) { + if (x is x.parent.right) + x.parent.right = y; + else + x.parent.left = y; + } else { + shared.root = y; + } + y.right = x; + if (x !is null) x.parent = y; + } + + // fixup Red-Black invariant after an insert + private void insertFixup(Node* x) { + Node* root = shared.root; + while (x !is root && x.parent.color == Color.Red) { + debug(dSortedAA) printf("fixing up parent %p\n",x.parent); + if (x.parent is x.parent.parent.left) { + Node* y = x.parent.parent.right; + if (y !is null && y.color == Color.Red) { + x.parent.color = Color.Black; + y.color = Color.Black; + x.parent.parent.color = Color.Red; + x = x.parent.parent; + } else { + if (x is x.parent.right) { + x = x.parent; + debug(dSortedAA) printf("rotating left %p\n",x); + rotateLeft(x); + } + x.parent.color = Color.Black; + x.parent.parent.color = Color.Red; + debug(dSortedAA) printf("rotating right1 %s\n",x.parent.parent); + rotateRight(x.parent.parent); + } + } else { + Node* y = x.parent.parent.left; + if (y !is null && y.color == Color.Red) { + x.parent.color = Color.Black; + y.color = Color.Black; + x.parent.parent.color = Color.Red; + x = x.parent.parent; + } else { + if (x is x.parent.left) { + x = x.parent; + debug(dSortedAA) printf("rotating right %p\n",x); + rotateRight(x); + } + x.parent.color = Color.Black; + x.parent.parent.color = Color.Red; + debug(dSortedAA) printf("rotating left1 %p\n",x.parent.parent); + rotateLeft(x.parent.parent); + } + } + } + while (x.parent !is null) + x = x.parent; + x.color = Color.Black; + } + + private enum {InsertOnMiss, ThrowOnMiss, NullOnMiss} + + // returns node for a given key - even if the key is ouside the + // sub-array. + private Node* getNode(Key key, int failureAction) { + // debug(dSortedAA) writefln("lookup %s",key); + Node* current; + fixupShared(); + current = shared.root; + Node* parent = null; + int cmpVal = 0; + CompareFcn cmp = shared.cmpFcn; + while (current !is null) { + cmpVal = cmp(&key,¤t.key); + // debug(dSortedAA) writefln("comparing %s %s got %s",key,current.key,cmpVal); + if (cmpVal == 0) return current; + parent = current; + current = cmpVal < 0 ? current.left : current.right; + } + switch (failureAction) { + case NullOnMiss: return null; + case ThrowOnMiss: throw new IndexOutOfBoundsException("Key not in container"); + case InsertOnMiss: return insertNode(key, Value.init, parent, cmpVal); + } + } + + // remove extra capacity + void trim() { + if (shared) + shared.freelist = null; + } + + // Parameters for controlling block allocations + private const int NodeAllocBlockSize = 10; // number of nodes in block + private const int AllocBlockCutoff = 96; // max node size to allow blocks + + // helper function to allocate a node + private Node* newNode() { + static if (is(Alloc == GCAllocator)) { + static if (Node.sizeof > AllocBlockCutoff) { + return new Node; + } else { + if (shared.freelist) { + Node* t = shared.freelist; + shared.freelist = t.left; + t.left = null; + return t; + } + Node[] block = new Node[NodeAllocBlockSize]; + for(int k=1;k prev ); + prev = val; + } + /* private bug + SortedAA!(char[],char[]) m5 = m2; + m5.head_ = m5.minNode(); + m5.tail_ = m5.maxNode(); + prev = ""; + foreach(char[] val; m5) { + assert( val > prev ); + prev = val; + } + prev = m5.maxNode().val; + foreach(char[] val; m5.backwards()) { + assert( val <= prev ); + prev = val; + } + */ + SortedAA!(int,int) m3; + m3.compareFcn = delegate int(int* a, int* b) { + return *a-*b; + }; + m3[10] = -100; + m3[7] = 100; + m3[-10] = 200; + assert( m3.length == 3); + assert( m3[7] == 100 ); + assert( m3[-10] == 200 ); + assert( m3[10] == -100 ); + + SortedAA!(int,int) mm; + mm.add(10,-100, 7,100, -10,200); + assert( m3 == mm ); + + SortedAA!(int,int) m3a = m3.dup; + assert( m3a == m3 ); + assert( m3a !is m3 ); + assert( m3a.length == 3); + assert( m3a[7] == 100 ); + assert( m3a[-10] == 200 ); + assert( m3a[10] == -100 ); + + m3.remove(7); + m3.remove(10); + m3.remove(-10); + // assert( m3.shared.root is null ); + + int[] keys = m3a.keys; + assert( keys[0] == -10 ); + assert( keys[1] == 7 ); + assert( keys[2] == 10 ); + + // test slicing + SortedAA!(char[],int) m8 = + SortedAA!(char[],int).make("a",100,"c",300,"d",400,"b",200, + "f",600,"e",500); + SortedAA!(char[],int) msl,msl2,msl3; + // debug(dSortedAA) m8.dumpTree(m8.shared.root,"",0); + msl = m8["b".."d"]; + msl2 = m8[m8.from("b123") .. m8.to("e")]; + assert( msl.length == 2 ); + // assert( msl.head_.key == "b" ); + // assert( msl.tail_.key == "c" ); + msl2 = m8["c".."f"]; + assert( msl2.length == 3 ); + // assert( msl2.head_.key == "c" ); + // assert( msl2.tail_.key == "e" ); + msl3 = m8[msl..msl2]; + assert( msl3.length == 4 ); + // assert( msl3.head_.key == "b" ); + // assert( msl3.tail_.key == "e" ); + m8.remove(msl2); + assert( m8.length == 3 ); + debug(dSortedAA) printf("\nsize %d\n",m8.sizeof); + + SortedAA!(int,int,false,MallocNoRoots) mal; + mal[10] = 20; + mal[30] = 50; + assert( mal[10] == 20 ); + assert( mal[30] == 50 ); + mal.clear(); + assert( mal.isEmpty ); + + version (MinTLVerboseUnittest) + printf("starting mintl.sortedaa unittest\n"); + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/sorting.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/sorting.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,139 @@ +/** \file sorting.d + * \brief Mixins for sorting random-access and sequential-access containers + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 1.0 + */ + +module mintl.sorting; + +// mixin for sorting random-access containers +// quicksort with insertion sort for short lists +template MRandomAccessSort(Container, alias list) { + void sort(int delegate(Container.ValueType* l, Container.ValueType* r) cmp = null) { + void swap(Container.ValueType* t1, Container.ValueType* t2 ) { + Container.ValueType t = *t1; *t1 = *t2; *t2 = t; + } + void insertionSort(Container data) { + size_t i = 1; + while(i < data.length) { + size_t j = i; + Container.ValueType* jp = data.lookup(j); + Container.ValueType* j1p; + while (j > 0 && cmp((j1p=data.lookup(j-1)),jp) > 0) { + swap(j1p,jp); + --j; + jp = j1p; + } + i++; + } + } + void dosort(Container data) { + if (data.length < 2) { + return; + } else if (data.length < 8) { + insertionSort(data); + return; + } + size_t tail = data.length-1; + size_t p = 1; + size_t q = tail; + Container.ValueType* headptr = data.lookup(0); + Container.ValueType* pptr = data.lookup(p); + Container.ValueType* qptr = data.lookup(q); + swap(headptr,data.lookup(data.length/2)); + if (cmp(pptr,qptr) > 0) swap(pptr,qptr); + if (cmp(headptr,qptr) > 0) swap(headptr,qptr); + if (cmp(pptr,headptr) > 0) swap(pptr,headptr); + while (1) { + do p++; while (cmp(data.lookup(p), headptr) < 0); + do q--; while (cmp(data.lookup(q), headptr) > 0); + if (p > q) break; + swap(data.lookup(p),data.lookup(q)); + } + swap(headptr,data.lookup(q)); + if (0 < q) + dosort(data[0 .. q+1]); + if (p < tail) + dosort(data[p .. tail+1]); + } + TypeInfo ti = typeid(Container.ValueType); + if (cmp is null) { + cmp = cast(typeof(cmp))&ti.compare; + } + dosort(list); + } +} + +// mixin for sorting sequential-access containers +// using mergesort customized for doublly-linked lists +// TODO: allow singly-linked lists, too +template MSequentialSort(Container, alias head_, alias tail_) { + void dosort(out Container.Node* newhead, + out Container.Node* newtail, + int delegate(Container.SortType* l, Container.SortType* r) cmp = null) { + void link(Container.Node* a, Container.Node* b) { + if (a) a.next = b; + if (b) b.prev = a; + } + if (cmp is null) { + TypeInfo ti = typeid(Container.SortType); + cmp = cast(typeof(cmp))&ti.compare; + } + Container.Node* head = head_; + Container.Node* tail = tail_; + Container.Node* headprev = head.prev; + Container.Node* i,j,e,itail; + i = tail; + tail = tail.next; // one past tail + i.next = null; + int depth; + size_t ilen, jlen, len = 1; + while (1) { + i = head; + depth = 0; + itail = null; + head = null; + while (i) { + depth++; + j = i; + ilen = 0; + for (size_t k = 0; k < len; k++) { + ilen++; + j = j.next; + if (!j) break; + } + jlen = len; + while (ilen > 0 || (jlen > 0 && j)) { + if (ilen == 0) { + e = j; j = j.next; jlen--; + } else if (jlen == 0 || !j || + cmp(i.sortLookup(),j.sortLookup()) <= 0) { + e = i; i = i.next; ilen--; + } else { + e = j; j = j.next; jlen--; + } + if (itail) { + link(itail,e); + } else { + head = e; + } + itail = e; + } + i = j; + } + itail.next = null; + if (depth <= 1) { + link(itail,tail); + newtail = itail; + link(headprev,head); + newhead = head; + return; + } + len *= 2; + } + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/stack.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/stack.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,91 @@ +/** \file stack.d + * \brief A stack container + * + * Written by Ben Hinkle and released to the public domain, as + * explained at http://creativecommons.org/licenses/publicdomain + * Email comments and bug reports to ben.hinkle@gmail.com + * + * revision 1.1 + */ + +module mintl.stack; + +private import mintl.deque; +private import mintl.arraylist; +import mintl.adapter; +import mintl.share; +import mintl.mem; + +/** A stack of items of stype Value backed by a container of type ImplType. + * Aliases push and pop allow stack operations. By default the stack is + * backed by a Deque. + */ +struct Stack(Value, ImplType = Deque!(Value)) { + + alias Stack ContainerType; + alias Value ValueType; + alias size_t IndexType; + alias ImplType AdaptType; + const bit isReadOnly = ImplType.isReadOnly; + + ImplType impl; + + mixin MAdaptBuiltin!(impl,Stack); + mixin MAdaptBasic!(impl,Stack); + mixin MAdaptList!(impl,Stack); + mixin MListCatOperators!(Stack); + + // Stack specific + static if (!ImplType.isReadOnly) { + alias add push; + alias takeTail pop; + } + Value peek() { + ImplType last = impl.tail; + return last.isEmpty ? Value.init : last[0]; + } +} + +/** Convenience alias for a stack backed by an array */ +template ArrayStack(Value) { + alias Stack!(Value,ArrayList!(Value)) ArrayStack; +} + +//version = MinTLVerboseUnittest; +//version = MinTLUnittest; + +version (MinTLUnittest) { + import mintl.list; + unittest { + version (MinTLVerboseUnittest) + printf("starting mintl.stack unittest\n"); + Stack!(int) st; + st.push(10, 20); + assert( st.peek == 20 ); + assert( st.pop == 20 ); + assert( st[st.length - 1] == 10 ); + assert( st.pop == 10 ); + assert( st.length == 0 ); + + ArrayStack!(int) st2; + st2.push(10); + st2 ~= 20; + assert( st2.peek == 20 ); + assert( st2.pop == 20 ); + assert( st2[st2.length - 1] == 10 ); + assert( st2.pop == 10 ); + assert( st2.length == 0 ); + + Stack!(int,List!(int)) st3; + st3.push(10); + st3 ~= 20; + assert( st3.peek == 20 ); + assert( st3.pop == 20 ); + assert( st3[st3.length - 1] == 10 ); + assert( st3.pop == 10 ); + assert( st3.length == 0 ); + + version (MinTLVerboseUnittest) + printf("finished mintl.stack unittest\n"); + } +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/unittest.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/unittest.d Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,6 @@ + +import mintl.all; + +int main() { + return 0; +} diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/win32.mak --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mintl/win32.mak Sat Mar 29 12:30:20 2008 -0600 @@ -0,0 +1,74 @@ + +# To build mintl.lib type +# make -f win32.mak DFLAGS=-g LIBNAME=mintl_debug.lib +# or +# make -f win32.mak DFLAGS=-release LIBNAME=mintl.lib +# The mintl.lib and object files will be created in the source directory. + +# flags to use building unittest.exe +DUNITFLAGS=-g -v -unittest -I.. -version=MinTLUnittest -version=MinTLVerboseUnittest + +# flags to use when building the mintl.lib library +DLIBFLAGS=$(DFLAGS) -release -I.. + +DMD = dmd +LIB = lib + +targets : unittest + +unittest : unittest.exe + +LIBNAME = mintl.lib + +#mintl : $(LIBNAME) + +SRC = all.d \ + array.d \ + arraylist.d \ + arrayheap.d \ + deque.d \ + hashaa.d \ + list.d \ + slist.d \ + share.d \ + adapter.d \ + stack.d \ + queue.d \ + set.d \ + multiaa.d \ + mem.d \ + sorting.d \ + sortedaa.d + +OBJS = all.obj \ + array.obj \ + arraylist.obj \ + arrayheap.obj \ + deque.obj \ + hashaa.obj \ + list.obj \ + slist.obj \ + share.obj \ + adapter.obj \ + stack.obj \ + queue.obj \ + set.obj \ + multiaa.obj \ + mem.obj \ + sorting.obj \ + sortedaa.obj + +.d.obj : + $(DMD) -c $(DLIBFLAGS) -of$@ $< + +$(LIBNAME) : $(OBJS) $(SRC) + $(LIB) -c $@ $(OBJS) + + +unittest.exe : $(LIBNAME) $(SRC) + $(DMD) $(DUNITFLAGS) unittest.d -ofunittest.exe $(SRC) + +clean: + del *.obj + del $(LIBNAME) + IF EXIST unittest.exe del unittest.exe