--- 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){
         
     }

--- /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

--- /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); }
+}
+

--- /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;
+

--- /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 <tt>x.backwards.toSeq</tt>
+ *  \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");
+  }
+}

--- /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");
+  }
+}

--- /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
+ * <tt>data</tt> property or the <tt>capacity</tt> 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 <tt>foreach</tt> 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");
+  }
+}

--- /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 <tt>foreach</tt> 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");
+  }
+}

--- /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 <tt>key1</tt> is
+ * inserted into the array before <tt>key2</tt> then <tt>key1</tt>
+ * will appear before <tt>key2</tt> 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<prime_list.length;k++) {
+      if (prime_list[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<AllocBlockSize-1;k++)
+	  p[k].next = &p[k+1];
+	data[0].next = &p[1];
+	return &p[0];
+      }
+    } else {
+      p = cast(Node*)Alloc.gcMalloc(Node.sizeof);
+    }
+    return p;
+  }
+
+  /** Find the element with a given key and return the value.  If the
+   * key is not in the map the default for the array is returned.  The
+   * target array can be a sub-array though the key may fall outside
+   * of the sub-array range.
+   */
+  Value opIndex(Key key) {
+    Value* t = get(key);
+    if (t)
+      return *t;
+    else
+      return missing;
+  }
+
+  /** Returns the value of a one-item array.   */
+  Value value() {
+    if (head_ is null && tail_ is null)
+      return Value.init;
+    return head_.val;
+  }
+
+  /** Returns the key of a one-item array.   */
+  Key key() {
+    if (head_ is null && tail_ is null)
+      return Key.init;
+    return head_.key;
+  }
+
+  /** Return a one-item slice of the head (oldest insertion).   */
+  HashAA head() {
+    HashAA res = *this;
+    res.tail_ = res.head_;
+    return res;
+  }
+
+  /** Return a one-item slice of the tail (more recent insertion).   */
+  HashAA tail() {
+    HashAA res = *this;
+    res.head_ = res.tail_;
+    return res;
+  }
+
+  /** Move a slice by n. 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 = node.next;
+    }
+    void doPrev(inout Node* node, int m) {
+      while (m--)
+	node = node.prev;
+    }
+    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);
+    }
+  }
+
+  /** 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 <tt>foreach</tt> 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");
+  }
+}

--- /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 @@
+<HTML> <head> <TITLE>Minimal Template Library for D</TITLE> </head>
+<body> 
+<h1>MinTL</h1>
+MinTL is a "minimal template library" of containers for the D
+programming language. For more info about D see <a
+href="http://www.digitalmars.com/d/">DigitalMars D home page</a>.  The
+downloads are the <a href="mintl.zip">Core Library</a> and
+the <a href="mintlc.zip">MinTL Concurrent Library</a>
+(<a href="conc.html">mintlc web page</a>), which includes
+a dependent <a href="locks.html">Synchronization Library</a>.
+The current version is 2.7.1.
+<p>
+This library is in the public domain.
+Written by <a href="http://home.comcast.net/~benhinkle">
+Ben Hinkle</a>, 2004.
+Email comments and bug reports to ben.hinkle@gmail.com
+<p>
+<h3> Contents </h3> 
+<a href="#Overview">Overview</a></br>
+<a href="#Lists">List Containers</a></br>
+<a href="#Assoc">Associative Containers</a></br>
+<a href="#Slicing">Slicing</a></br>
+<a href="#Foreach">Foreach traversals</a></br>
+<a href="#Sorting">Sorting</a></br>
+<a href="#Allocators">Allocators</a></br>
+<a href="#unmod">Unmodifiable Containers</a></br>
+<a href="#Examples">Examples</a></br>
+<a href="#API">API Reference by module</a></br>
+
+<a name="Overview"></a>
+<h3> Overview </h3> 
+
+The philosophy of the library is to be as simple and minimal as
+possible:
+<list>
+
+<li> 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.
+
+<li>
+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.
+
+<li> 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.
+
+</list>
+<p>
+
+MinTL has the following containers
+<p>
+<table border="1">
+<caption>List containers</caption>
+<tr>
+<th>container    <th> implementation  <th> file <th>  brief</th>
+</tr>
+<tr>
+<td> <a href="#list">List</a>
+<td> doubly linked list   
+<td> list.d     
+<td> sortable linked list with "previous" and "next" pointers
+</td>
+</tr>
+<tr>
+<td> <a href="#clist">CircularList</a>
+<td> circular doubly linked list   
+<td> list.d     
+<td> doubly linked list where the head and tail are linked
+</td>
+</tr>
+<tr>
+<td> <a href="#slist">SList</a>
+<td> singly linked list   
+<td> slist.d     
+<td> linked list with only "next" pointers
+</td>
+</tr>
+<tr>
+<td> <a href="#cslist">CircularSList</a>
+<td> circular singly linked list   
+<td> slist.d
+<td> singly linked list where the tail points to the head
+</td>
+</tr>
+<tr>
+<td> <a href="#arraylist">ArrayList</a> 
+<td> circular array     
+<td> arraylist.d  
+<td> sortable list backed by a resizable circular array
+</td>
+<tr>
+<td> <a href="#deque">Deque</a> 
+<td> circular block-allocated array
+<td> deque.d  
+<td> list backed by a resizable block-allocated circular array
+</td>
+<tr>
+<td> <a href="#arrayheap">ArrayHeap</a> 
+<td> heap 
+<td> arrayheap.d  
+<td> complete binary tree backed by an array
+</td>
+<tr>
+<td> <a href="#stack">Stack</a>
+<td> adapter
+<td> stack.d
+<td> adapts a list container to be a stack
+</td>
+<tr>
+<td> <a href="#arraystack">ArrayStack</a>
+<td> ArrayList
+<td> stack.d
+<td> wraps an ArrayList with the stack adapter
+</td>
+<tr>
+<td> <a href="#queue">Queue</a>
+<td> adapter
+<td> queue.d
+<td> adapts a list container to be a queue
+</td>
+<tr>
+<td> <a href="#arrayqueue">ArrayQueue</a>
+<td> ArrayList
+<td> queue.d
+<td> wraps an ArrayList with the queue adapter
+</td>
+<tr>
+<td> <a href="#pqueue">PriorityQueue</a> 
+<td> ArrayHeap
+<td> queue.d  
+<td> wraps an ArrayHeap with the queue adapter
+</td>
+</table>
+<p>
+<table border="1">
+<caption>Associative containers</caption>
+<tr>
+<th>container    <th> implementation  <th> file <th>  brief</th>
+<tr>
+<td> <a href="#hashaa">HashAA</a>
+<td> linked hash table
+<td> hashaa.d    
+<td> sortable associative array with nodes ordered by insertion order
+</td>
+<tr>
+<td> <a href="#sortedaa">SortedAA </a>
+<td> red-black tree 
+<td> sortedaa.d  
+<td> sorted associative array </td>
+</tr>
+<tr>
+<td> <a href="#set">Set</a> 
+<td> adapter
+<td> set.d
+<td> adapts an associative container to be a set
+</td>
+<tr>
+<td> <a href="#sortedset">SortedSet</a> 
+<td> SortedAA
+<td> set.d
+<td> wraps a SortedAA with the set adapter
+</td>
+<tr>
+<td> <a href="#multiset">MultiSet</a> 
+<td> adapter
+<td> set.d
+<td> adapts an associative container to be a set with repeats
+</td>
+<tr>
+<td> <a href="#sortedmultiset">SortedMultiSet</a> 
+<td> SortedAA
+<td> set.d
+<td> wraps a SortedAA with the multi-set adapter
+</td>
+<tr>
+<td> <a href="#multiaa">MultiAA</a> 
+<td> adapter
+<td> multiaa.d
+<td> adapts an associative container to hold repeated keys
+</td>
+<tr>
+<td> <a href="#sortedmultiaa">SortedMultiAA</a> 
+<td> SortedAA
+<td> multiaa.d
+<td> wraps a SortedAA with the multi-aa adapter
+</td>
+</table>
+<p>
+
+The module mintl.array defines helper functions for builtin dynamic 
+and associative arrays.
+
+<a name="BuildInstall">
+<h3> Build and Install</h3>
+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 <tt>add()</tt> datatype support uncomment the
+<tt>version=WithBox</tt> 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 
+<tt>make -f win32.mak</tt> or <tt>make -f linux.mak</tt>. 
+In your source code <tt>import</tt> the desired modules and compile each
+container used and the mintl static library into the application. 
+If a concurrent container is needed download the <tt>mintlc</tt>
+sub-package and link that library and
+the <a href="locks.html">Locks</a> library into the 
+application. For example on Linux to compile the program <tt>app.d</tt>
+<pre>
+import mintl.list;
+
+int main() {
+  List!(int) list = List!(int).make(10,20,30);
+  return 0;
+}
+</pre>
+run in the directory above mintl the command
+<pre>
+  dmd app.d mintl/libmintl_debug.a
+</pre>
+to build with asserts or
+<pre>
+  dmd app.d -release mintl/libmintl.a
+</pre>
+to build without asserts.
+On Windows run
+<pre>
+  dmd app.d mintl\mintl_debug.lib
+</pre>
+or
+<pre>
+  dmd app.d -release mintl\mintl.lib
+</pre>
+If the mintl directory is not in the current directory then use the -I flag 
+to add it to the search path
+<pre>
+  dmd app.d -Ipath_to_mintl path_to_mintl/mintl/libmintl.a
+</pre>
+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:
+<pre>
+LIB="%@P%\..\lib";\dm\lib;C:\d\mintl
+DFLAGS="-I%@P%\..\src\phobos";C:\d
+</pre>
+On Linux the static library can be put in a standard location like 
+/usr/lib if desired.
+
+<a name="Lists">
+<h3> List Containers </h3>
+
+The list containers <tt>List</tt>, <tt>SList</tt>, 
+<tt>CircularList</tt>, <tt>CircularSList</tt>, <tt>ArrayList</tt>,
+<tt>Deque</tt>, <tt>ArrayHeap</tt> and the concurrent queues
+and stacks share a naming convention
+for adding and removing items. The <i>head</i> is the
+first item in the container and the <i>tail</i> is the last item.
+All list containers support constant-time access to the head
+and tail.
+The speed of accessing the <tt>length</tt> 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.
+<p>
+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 <tt>trim</tt> function. 
+<p>
+The circular lists
+<tt>CircularList</tt> and <tt>CircularSList</tt> 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.
+<p>
+An <tt>ArrayList</tt> can also be used as a dynamic array with
+managed capacity. Set the <tt>capacity</tt> 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.
+
+<p> To add items to a container call <tt>add</tt> with any number of
+items. For example
+<pre>
+  List!(int) x,y,z;
+  y.add(10,20,30);
+  z.add(50,60,70);
+  x = y; x ~= 40; x ~= z; x ~= 80;
+</pre>
+results in the following linked list
+<pre>
+ x[0],y[0]           y[2]              z[0]              z[2]     x[7]
+    10  <->  20  <->  30  <->  40  <->  50  <->  60  <->  70  <->  80
+</pre>
+To add a single item or list call <tt>addTail</tt> or use
+one of the concatenation operators. Some containers also support adding
+items or lists at the head using <tt>addHead</tt> or at a position
+in the interior of the list using <tt>addBefore</tt> or <tt>addAfter</tt>.
+To create a list in an expression use the static <tt>make</tt> function
+For example,
+<pre>
+  List!(int) x;
+  x = List!(int).make(10,20,30) ~ List!(int).make(50,60,70);
+</pre>
+
+<p> To remove items call one of the <tt>take</tt> or 
+<tt>remove</tt> functions. 
+All list containers support <tt>removeHead</tt> to remove
+the head of the list and <tt>takeHead</tt> to remove and return
+the stored value, if any.
+Some containers also support <tt>takeTail</tt> and 
+<tt>removeTail</tt> to remove the tail and <tt>remove</tt>
+to remove a slice.
+
+<p>
+Stacks and queues are implemented as adapters of a list 
+container. By default they use a Deque as the backing container.
+Stacks define aliases <tt>push</tt> for <tt>add</tt>
+and <tt>pop</tt> for <tt>takeTail</tt>. Queues define an alias
+<tt>take</tt> for <tt>takeHead</tt> (the function <tt>add</tt> is used
+to add to the end of a queue). For example,
+<pre>
+  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" );
+</pre>
+A <tt>PriorityQueue</tt> is an ArrayHeap wrapped with the Queue adapter. To
+set a custom comparison function access the <tt>impl</tt> property of the
+adapter:
+<pre>
+  PriorityQueue!(char[]) x;
+  x.impl.compareFcn = &fcn;
+  x.add("first","second");
+</pre>
+<p>
+The following table outlines the advantages and disadvantages of
+each list container
+<table border="1">
+<tr>
+<th>container    <th> advantages  <th> disadvantages </th>
+</tr>
+<tr>
+<td> List 
+<td> O(1) insertion at head/tail or before/after slices
+<td> O(n) access to middle of list
+</td>
+</tr>
+<tr>
+<td> SList 
+<td> O(1) insertion at head/tail or after slices; less overhead
+than <tt>List</tt>
+<td> O(n) access to middle or near end of list
+</td>
+</tr>
+<tr>
+<td> ArrayList 
+<td> O(1) insertion at head/tail. O(1) access to any index
+<td> O(n) insertion in middle
+</td>
+</tr>
+<tr>
+<td> Deque
+<td> O(1) insertion at head/tail. O(1) access to any index.
+Block allocated.
+<td> O(n) insertion in middle; non-contiguous storage
+</td>
+</tr>
+<tr>
+<td> ArrayHeap
+<td> maintains items in semi-sorted order; O(log(n)) add/remove.
+<td> only allows <tt>addTail</tt> and <tt>takeHead</tt>
+</td>
+</tr>
+</table>
+
+<a name="Assoc">
+<h3> Associative Containers </h3>
+
+The associative containers <tt>SortedAA</tt>,<tt>HashAA</tt>, and
+<tt>ConcurrentAA</tt> are similar to builtin associative arrays but
+with extra capabilities. The <tt>SortedAA</tt> 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
+<tt>compareFcn</tt> property. The <tt>HashAA</tt> maintains the keys
+in insertion order, meaning if an indexing expression using key
+<tt>x</tt> is evaluated before an indexing expression using key
+<tt>y</tt> then <tt>x</tt> is traversed before <tt>y</tt> in
+<tt>foreach</tt> traversals. Assigning to a key already in the array
+does not change the insertion order. The other associative array
+properties <tt>dup</tt>, <tt>length</tt>, <tt>keys</tt> and
+<tt>values</tt> are also implemented.
+
+<p>
+Elements are inserted or modified using the <tt>add</tt> function or
+using indexing lvalue expressions
+and retrieved using indexing rvalue expressions. To test if a key is in
+the array use the overloaded <tt>contains</tt> 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 <tt>missing</tt> property.
+The functions <tt>get</tt> and <tt>put</tt> allow more flexibility in handling
+missing keys by allowing the user to either return null, throw or
+insert.
+To remove an item call the <tt>remove</tt> function. Both <tt>HashAA</tt>
+and <tt>SortedAA</tt> maintain a freelist of removed nodes for future
+reuse. To release the freelist for garbage collection call <tt>trim</tt>.
+<p>
+For example to define a sorted associative
+array with three entries associating "first" with 10, "second" with
+20 and "third" with 30 type
+<pre>
+  SortedAA!(int,char[]) x;
+  x.add(10,"first", 20,"second", 30,"third");
+</pre>
+or equivalently,
+<pre>
+  SortedAA!(int,char[]) x;
+  x[10] = "first";
+  x[20] = "second";
+  x[30] = "third";
+</pre>
+To create an associative array in an expression use the static <tt>make</tt> function
+For example,
+<pre>
+  foo(SortedAA!(int,char[]).make(10,"first",20,"second",30,"third"));
+</pre>
+
+<p>
+The number of elements in an associative container is computed by
+the <tt>length</tt> property.
+
+<p>
+Sets and multi-associative-arrays are implemented as adapters of an 
+associative container. 
+By default sets use a HashAA as the backing container.
+Use <tt>add</tt>
+to add items to a set and use an indexing expression
+to check if an item is in the set. For example,
+<pre>
+  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 );
+</pre>
+
+<a name="Slicing">
+<h3> Slicing </h3>
+
+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 <tt>x</tt> and <tt>y</tt> if 
+<tt>x</tt> is a list with 6 items and
+<tt>y</tt> is the slice <tt>x[2..4]</tt>.<br>
+
+<pre>
+   x[0]            y[0]    y[1]           x[5]
+    0  <->  1  <->  2  <->  3  <->  4  <->  5
+</pre>
+Executing <tt>z = y.dup</tt> would result in
+<pre>
+   z[0]    z[1]
+    2  <->  3 
+</pre>
+<p>
+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 <tt>addBefore</tt> or create a slice with the tail at the desired
+location and call <tt>addAfter</tt>. To remove a portion of a list create a
+slice and call <tt>remove</tt>. Again one should always insert and remove from
+the original list otherwise any variable referring to the original list
+will become out of sync.
+<p>
+A sub-list can be moved towards the head or tail
+of the original list by calling the <tt>next</tt> function.
+This allows a sub-list to traverse up and down the original list efficiently. 
+Continuing the example from above, executing <tt>y.next(-1)</tt> would result 
+in
+<pre>
+   x[0]    y[0]    y[1]                   x[5]
+    0  <->  1  <->  2  <->  3  <->  4  <->  5
+</pre>
+and then executing <tt>x.remove(y)</tt> would result in
+<pre>
+   x[0]                    x[3]
+    0  <->  3  <->  4  <->  5
+
+   y[0]    y[1]
+    1  <->  2 
+</pre>
+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.
+
+<p>
+The SortedAA slicing behavior is designed to chose slices without modifying
+the underlying container. The functions <tt>from</tt> and <tt>to</tt>
+can find a one-item slice starting from or up to a given key.
+For example if <tt>words</tt> is a sorted associative array indexed by 
+<tt>char[]</tt> then
+<pre>
+    words["a" .. "b"]
+</pre>
+or, equivalently,
+<pre>
+    words[words.from("a") .. words.to("b")]
+</pre>
+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.
+
+<a name="Foreach">
+<h3> Foreach </h3>
+Containers and slices of containers can be traversal in 
+<tt>foreach</tt> 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.
+<p>
+Each container also supports backwards traversals by calling 
+<tt>backwards</tt> in a foreach statement. For example,
+<pre>
+  List!(int) x;
+  ...
+  foreach( int val; x.backwards() )
+    printf("%d ",val);
+</pre>
+will print out the contents of x from tail to head. 
+Backwards traversals do not allocate any dynamic memory.
+
+<a name="Sorting">
+<h3> Sorting </h3>
+MinTL supports sorting containers in two forms. The <tt>SortedAA</tt>
+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 <tt>SortedSet</tt>
+and <tt>SortedMultiAA</tt> are derived from <tt>SortedAA</tt> and
+have the same sorting semantics.
+<p>
+The other form of sorting is through calling the <tt>sort</tt>
+methods of the containers <tt>ArrayList</tt>, <tt>Deque</tt>, <tt>List</tt>, 
+and <tt>HashAA</tt> or by using the <tt>sort</tt> template in 
+<tt>mintl.array</tt> 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 <tt>HashAA</tt> 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:
+<pre>
+    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));
+</pre>
+<p>
+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 <tt>HashAA</tt> 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.
+
+<a name="Allocators">
+<h3> Allocators </h3>
+Most containers accept an optional <tt>Allocator</tt> parameter to
+customize memory management. The default allocator is the 
+<tt>GCAllocator</tt> 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 <tt>clear</tt> when done
+with a container so that the memory can be released.
+<p>
+
+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 <tt>OutOfMemory</tt>
+exception if the allocation fails.
+<p>
+
+The two predefined allocators <tt>Malloc</tt> and <tt>MallocNoRoots</tt> 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,
+<pre>
+  ArrayList!(int,MallocNoRoots) x;
+  x.add(10,20,30);
+  ...
+  x.clear();
+</pre>
+
+<a name="unmod"></a>
+<h3> Unmodifiable Containers </h3>
+The <tt>ReadOnly</tt> 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 <tt>readonly</tt> property creates a read-only view of a container. 
+The <tt>readwrite</tt> property creates a read-write view.
+For example 
+<pre>
+  void foo(List!(int,ReadOnly) y) { ... }
+  List!(int) x;
+  x.add(10,20,30);
+  foo(x.readonly);
+</pre>
+
+<a name="Examples">
+<h3> Examples </h3>
+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
+<pre>
+  List!(int) x;
+  x.add(0,1,2,3,4,5,6,7,8,9,10);
+</pre>
+and print out the items 5 though 8
+<pre>
+  foreach(int val; x[5..9])
+    printf("%d ",val);
+</pre>
+to output
+<pre>
+  5 6 7 8
+</pre>
+Assigning <tt>x</tt> to another variable <tt>y</tt> shares
+the underlying list contents, so assigning through <tt>y</tt>
+is reflected in <tt>x</tt>:
+<pre>
+  List!(int) y = x;
+  y[0] = 100;
+  assert( x[0] == 100 );
+</pre>
+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.
+<p>
+
+<a name="API">
+<h3> API Reference</h3>
+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
+<pre> return-type fcn-name!(tmpl-param,...)(arg1, arg2,...);
+</pre>
+to mimic how it would appear in user code. The API is organized by
+module:<br>
+<dl>
+<dt><a href="#array">mintl.array</a>
+<dt><a href="#arrayheap">mintl.arrayheap</a>
+<dt><a href="#arraylist">mintl.arraylist</a>
+<dt><a href="#deque">mintl.deque</a>
+<dt><a href="#hashaa">mintl.hashaa</a>
+<dt><a href="#list">mintl.list</a>
+<dt><a href="#mem">mintl.mem</a>
+<dt><a href="#multiaa">mintl.multiaa</a>
+<dt><a href="#queue">mintl.queue</a>
+<dt><a href="#set">mintl.set</a>
+<dt><a href="#share">mintl.share</a>
+<dt><a href="#slist">mintl.slist</a>
+<dt><a href="#sortedaa">mintl.sortedaa</a>
+<dt><a href="#stack">mintl.stack</a>
+</dl>
+
+<a name="array"></a>
+<h4>mintl.array</h4>
+<dl>
+<dt>void <b>reserve</b>!(Value[])(inout Value[] x, size_t n);
+<dd>Reserve capacity for a dynamic array
+<dt>DArrayReverseIter <b>backwards</b>!(Value[])(Value[] x);
+<dd>Reverse dynamic array "foreach" traversal
+<dt>void <b>sort</b>!(Value[])(Value[] data, int delegate(Value* x, Value* y) cmp = null);
+<dd>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.
+</dl>
+
+<a name="arrayheap"></a>
+<h4>mintl.arrayheap</h4>
+<dl>
+<dt>struct <b>ArrayHeap</b>(Value, Alloc = GCAllocator)
+<dd>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 <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>Value[] <b>data</b>;
+<dd>Backing array
+<dt>size_t <b>length</b>;
+<dd>Return length of heap
+<dt>alias int delegate(Value* a, Value* b) <b>CompareFcn</b>;
+<dd>Signature of comparison functions
+<dt>void <b>compareFcn</b>(CompareFcn cmp);
+<dd>Set the comparison function
+<dt>bool <b>isEmpty</b>
+<dd>Return true if container is empty
+<dt>Value <b>opIndex</b>(size_t n);
+<dd>Return nth item where the head is item 0.
+<dt>void <b>opIndexAssign</b>(Value val, size_t n);
+<dd>Assign to the nth item
+<dt>Value[] <b>values</b>;
+<dd>Get heap contents as dynamic array slice of backing array
+<dt>void <b>add</b>(...);
+<dd>Add to heap
+<dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr);
+<dd>Add to heap using va_arg inpurs
+<dt>void <b>addTail</b>(Value v);
+<dd>Add to heap
+<dt>Value <b>takeHead</b>();
+<dd>Remove and return first item (greatest item)
+<dt>void <b>removeHead</b>();
+<dd>Remove first item (greatest item)
+<dt>Value* <b>lookup</b>(size_t n);
+<dd>Return a pointer to the nth item
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal by values
+<dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg);
+<dd>Foreach traversal by index-value pairs
+<dt>ArrayHeap <b>dup</b>;
+<dd>Duplicate array heap by duplicating backing array
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>int <b>opEquals</b>(ArrayHeap c);
+<dd>Test heap equality
+<dt>alias ArrayHeap <b>ContainerType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dd>Aliases for container types
+</dl>
+</dl>
+
+<a name="arraylist"></a>
+<h4>mintl.arraylist</h4>
+<dl>
+<dt>struct <b>ArrayList</b>(Value, bit ReadOnly = false, Alloc = GCAllocator)
+<dd>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 <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>Value[] <b>data</b>;
+<dd>Backing array
+<dt>mixin <b>MListCat</b>(ArrayList)
+<dd>Mixin <a href="#listcat">list catenation</a>.
+<dt>mixin <b>MListAlgo</b>(this,ArrayList)
+<dd>Mixin <a href="#listalgo">list algorithms</a>.
+<dt><b>MListCommon</b>(ArrayList)
+<dd>Implement common <a href="#listcomm">list members</a>.
+<dt>size_t <b>length</b>
+<dd>Read/write property to return or set the length of the list.
+<dt>size_t <b>capacity</b>
+<dd>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.
+<dt>Value[] <b>array</b>;
+<dd>Get list contents as dynamic array slice of the backing array assuming
+the list is contiguous.
+<dt>ArrayListReverseIter!(Value) <b>backwards</b>();
+<dd>Backwards traversal for "foreach"
+<dt>ArrayList!(Value,true,Alloc) <b>readonly</b>;
+<dd>Property that returns a read-only view of the container.
+<dt>ArrayList!(Value,false,Alloc) <b>readwrite</b>;
+<dd>Property that returns a read-write view of the container.
+<dt>void <b>sort</b>(int delegate(Value* x, Value* y) cmp = null);
+<dd>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.
+<dt>alias ArrayList <b>ContainerType</b>;
+<dt>alias ArrayList <b>SliceType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dt>alias ReadOnly <b>isReadOnly</b>;
+<dd>Aliases for container types
+</dl>
+</dl>
+
+<a name="deque"></a>
+<h4>mintl.deque</h4>
+<dl>
+<dt>struct <b>Deque</b>(Value, bit ReadOnly = false, Alloc = GCAllocator)
+<dd>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 <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>mixin <b>MListCat</b>(Deque)
+<dd>Mixin <a href="#listcat">list catenation</a>.
+<dt>mixin <b>MListAlgo</b>(this,Deque)
+<dd>Mixin <a href="#listalgo">list algorithms</a>.
+<dt><b>MListCommon</b>(Deque)
+<dd>Implement common <a href="#listcomm">list members</a>.
+<dt>size_t <b>length</b>;
+<dd>Return length of deque.
+<dt>DequeReverseIter!(Value) <b>backwards</b>();
+<dd>Backwards traversal for "foreach"
+<dt>Deque!(Value,true,Alloc) <b>readonly</b>;
+<dd>Property that returns a read-only view of the container.
+<dt>Deque!(Value,false,Alloc) <b>readwrite</b>;
+<dd>Property that returns a read-write view of the container.
+<dt>void <b>sort</b>(int delegate(Value* x, Value* y) cmp = null);
+<dd>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.
+<dt>alias Deque <b>ContainerType</b>;
+<dt>alias Deque <b>SliceType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dt>alias ReadOnly <b>isReadOnly</b>;
+<dd>Aliases for container types
+</dl>
+</dl>
+
+<a name="hashaa"></a>
+<h4>mintl.hashaa</h4>
+<dl>
+<dt>struct <b>HashAA</b>(Key,Value,bit ReadOnly = false, Alloc = GCAllocator)
+<dd>An associative array linked by insertion order.
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>void <b>add</b>(...);
+<dd>Add key-value pairs to array
+<dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr);
+<dd>Add using va_arg inpurs
+<dt>static HashAA <b>make</b>(...)
+<dd>Consruct a HashAA using add(...)
+<dt>size_t <b>length</b>;
+<dd>Return number of items in the array.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if array is empty
+<dt>Value* <b>get</b>(Key key, bit throwOnMiss = false);
+<dd>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.
+<dt>Value* <b>put</b>(Key key)
+<dd>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.
+<dt>bool <b>contains</b>(Key key)
+<dd>Returns true if the array contains the key
+<dt>bool <b>contains</b>(Key key, out Value value)
+<dd>Returns true if the array contains the key and sets the out value if
+present.
+<dt>Value <b>opIndex</b>(Key key);
+<dd>Return item with given key. Returns the default missing value if not present.
+<dt>void <b>opIndexAssign</b>(Value val, Key key);
+<dd>Assign a value to the given key
+<dt>Value <b>missing</b>
+<dd>Read/write property for the value to use on indexing a key not in
+the array. Defaults to Value.init
+<dt>HashAA <b>opSlice</b>(Key a, Key b);
+<dd>Slice from item a to b (exclusive)
+<dt>HashAA <b>opSlice</b>(HashAA a, HashAA b);
+<dd>Slice from first key in a to last key in b
+<dt>HashAA <b>head</b>
+<dd>Return one-item slice of the head
+<dt>HashAA <b>tail</b>
+<dd>Return one-item slice of the tail
+<dt>void <b>next</b>(int n = 1, int end = 0);
+<dd>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.
+<dt>void <b>remove</b>(Key key);
+<dd>Remove a key from array if present. The node used for key is reused in
+future insert actions.
+<dt>Value <b>take</b>(Key key);
+<dd>Remove a key from array if present and return value. Returns the
+default missing value if the key was not present.
+<dt>void <b>remove</b>(HashAA subarray);
+<dd>Remove a slice from array
+<dt>Value[] <b>values</b>;
+<dd>Get values as a dynamic array. The values are in insertion order.
+<dt>Key[] <b>keys</b>;
+<dd>Get keys as a dynamic array. The keys are in insertion order.
+<dt>void <b>reserve</b>(size_t n);
+<dd>Reserve a capacity for the array
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal by values
+<dt>int <b>opApply</b>(int delegate(inout Key key, inout Value x) dg);
+<dd>Foreach traversal by key-value pairs
+<dt>int <b>opApply</b>(int delegate(inout HashAA n) dg);
+<dd>Foreach traversal by one-item slices
+<dt>HashAA <b>dup</b>;
+<dd>Duplicate array
+<dt>void <b>clear</b>;
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>void <b>trim</b>;
+<dd>Remove references to extra nodes kept for reuse
+<dt>int <b>opEquals</b>(HashAA c);
+<dd>Test array equality
+<dt>HashAAReverseIter!(Key,Value) <b>backwards</b>();
+<dd>Backwards traversal for "foreach"
+<dt>HashAA <b>rehash</b>;
+<dd>Rehash array to be more efficient
+<dt>Value <b>value</b>
+<dd>Return value of a one-item slices
+<dt>Key <b>key</b>;
+<dd>Return key of a one-item slices
+<dt>HashAA!(Key,Value,true) <b>readonly</b>;
+<dd>Property that returns a read-only view of the container.
+<dt>HashAA!(Key,Value,false) <b>readwrite</b>;
+<dd>Property that returns a read-write view of the container.
+<dt>void <b>sort</b>(int delegate(Key* x, Key* y) cmp = null);
+<dd>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.
+<dt>alias HashAA <b>ContainerType</b>;
+<dt>alias HashAA <b>SliceType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias Key <b>IndexType</b>;
+<dt>alias ReadOnly <b>isReadOnly</b>;
+<dd>Aliases for container types
+</dl>
+
+</dl>
+<a name="list"></a>
+<h4>mintl.list</h4>
+<dl>
+<dt>struct <b>List</b>(Value, bit ReadOnly = false, Alloc = GCAllocator)
+<dd>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 <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>mixin <b>MListCat</b>(List)
+<dd>Mixin <a href="#listcat">list catenation</a>.
+<dt>mixin <b>MListAlgo</b>(this,List)
+<dd>Mixin <a href="#listalgo">list algorithms</a>.
+<dt><b>MListCommon</b>(List)
+<dd>Implement common <a href="#listcomm">list members</a>.
+<dt>size_t <b>length</b>;
+<dd>Return length of list.
+<dt>void <b>trim</b>;
+<dd>Remove references to extra nodes kept for reuse
+<dt>ListReverseIter!(Value) <b>backwards</b>();
+<dd>Backwards traversal for "foreach"
+<dt>List!(Value,true,Alloc) <b>readonly</b>;
+<dd>Property that returns a read-only view of the container.
+<dt>List!(Value,false,Alloc) <b>readwrite</b>;
+<dd>Property that returns a read-write view of the container.
+<dt>void <b>sort</b>(int delegate(Value* x, Value* y) cmp = null);
+<dd>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.
+<dt>alias List <b>ContainerType</b>;
+<dt>alias List <b>SliceType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dt>alias ReadOnly <b>isReadOnly</b>;
+<dd>Aliases for container types
+</dl>
+</dl>
+<p>
+
+<a name="clist"></a>
+<dl>
+<dt>struct <b>CircularList</b>(Value, bit ReadOnly = false, Alloc = GCAllocator)
+<dd>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 <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>mixin <b>MListCat</b>(CircularList)
+<dd>Mixin <a href="#listcat">list catenation</a>.
+<dt>mixin <b>MListAlgo</b>(this,CircularList)
+<dd>Mixin <a href="#listalgo">list algorithms</a>.
+<dt><b>MListCommon</b>(CircularList)
+<dd>Implement common <a href="#listcomm">list members</a>.
+<dt>size_t <b>length</b>;
+<dd>Return length of list.
+<dt>List <b>toList</b>;
+<dd>Return the list as a non-circular List
+<dt>void <b>rotate</b>(int n = 1);
+<dd>Rotate the list by n steps (backwards if n is negative)
+<dt>CircularListReverseIter!(Value) <b>backwards</b>();
+<dd>Backwards traversal for "foreach"
+<dt>CircularList!(Value,true,Alloc) <b>readonly</b>;
+<dd>Property that returns a read-only view of the container.
+<dt>CircularList!(Value,false,Alloc) <b>readwrite</b>;
+<dd>Property that returns a read-write view of the container.
+<dt>alias CircularList <b>ContainerType</b>;
+<dt>alias List!(Value,Alloc) <b>SliceType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dt>alias ReadOnly <b>isReadOnly</b>;
+<dd>Aliases for container types
+</dl>
+</dl>
+
+<a name="mem"></a>
+<h4>mintl.mem</h4>
+<dl>
+<dt>void* <b>mallocWithCheck</b>(size_t s)
+<dd>Call std.c.stdlib.malloc and throw OutOfMemory if fails.
+<dt>void* <b>callocWithCheck</b>(size_t n, size_t s)
+<dd>Call std.c.stdlib.calloc and throw OutOfMemory if fails.
+<dt>void* <b>reallocWithCheck</b>(void* p, size_t s)
+<dd>Call std.c.stdlib.realloc and throw OutOfMemory if fails.
+<dt>void <b>dfree</b>(void* p)
+<dd>Call free.
+<dt>void* <b>gcMalloc</b>(size_t s)
+<dd>Call mallocWithCheck and register range with GC.
+<dt>void* <b>gcCalloc</b>(size_t n, size_t s)
+<dd>Call callocWithCheck and register range with GC.
+<dt>void* <b>gcRealloc</b>(void* p, size_t s)
+<dd>Call reallocWithCheck and register range with GC.
+<dt>void <b>gcFree</b>(void* p)
+<dd>Remove range and call free.
+<p>
+
+<a name="GCAlloc">
+<dt>struct <b>GCAllocator</b></a>
+<dd>The default allocator that indicates the garbage collector
+should be used for memory management.
+<dt>struct <b>Malloc</b>
+<dd>An allocator that uses malloc for memory requests and registers 
+blocks with the GC when requested by the container.
+<dt>struct <b>MallocNoRoots</b>
+<dd>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.
+</dl>
+</dl>
+
+<a name="multiaa"></a>
+<h4>mintl.multiaa</h4>
+<dl>
+<dt>struct <b>MultiAA</b>!(Key,Value, ImplType = HashAA!(Key,Value[]))
+<dd>An associative array which allows keys to be repeated. 
+Adapted from a customizable container type mapping keys to Value[].
+<p>
+<dl>
+<dt>ImplType <b>impl</b>
+<dd>Read-write property holding the backing container
+<dt>void <b>add</b>(...);
+<dd>Add key-value pairs to the container
+<dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr);
+<dd>Add using va_arg inpurs
+<dt>static MultiAA <b>make</b>(...)
+<dd>Consruct a MultiAA using add(...)
+<dt>void <b>addItem</b>(Key key, Value item);
+<dd>Add item to container.
+<dt>size_t <b>length</b>;
+<dd>Return number of items in the container.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if container is empty.
+<dt>Value[] <b>opIndex</b>(Key key);
+<dd>Return the values for a given key.
+<dt>void <b>remove</b>(Key key, Value value);
+<dd>Remove an item from the container if present.
+<dt>void <b>remove</b>(Key key);
+<dd>Remove all the values with a given key if present.
+<dt>Key[] <b>keys</b>;
+<dd>Get keys as a dynamic array. Duplicates are removed.
+<dt>Value[][] <b>values</b>;
+<dd>Get values as a dynamic array.
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal of items in the container. If an item is repeated it
+is passed multiple times consecutively to the delegate.
+<dt>int <b>opApply</b>(int delegate(inout Key key, inout Value x) dg);
+<dd>Foreach traversal of items in the container. If an item is repeated it
+is passed multiple times consecutively to the delegate.
+<dt>MultiAA <b>dup</b>;
+<dd>Duplicate container
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>int <b>opEquals</b>(MultiAA c);
+<dd>Test container equality
+<dt>alias MultiAA <b>ContainerType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias Key <b>IndexType</b>;
+<dt>alias ImplType <b>AdaptType</b>;
+<dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly;
+<dd>Aliases for container types
+</dl>
+<p>
+<a name="sortedmultiaa"></a>
+<dt>alias <b>SortedMultiAA</b>!(Key,Value)
+<dd>An alias for MultiAA!(Key,Value,SortedAA!(Key,Value[])) to implement a 
+sorted multi-aa.
+</dl>
+
+<a name="queue"></a>
+<h4>mintl.queue</h4>
+<dl>
+<dt>struct <b>Queue</b>!(Value, ImplType = Deque!(Value))
+<dd>A queue of items adapted from a customizable list container type. The
+default backing container is a Deque.
+<p>
+<dl>
+<dt>ImplType <b>impl</b>
+<dd>Read-write property holding the backing container.
+<dt>alias addTail <b>put</b>;
+<dd>Alias to add items to the tail of the queue.
+<dt>alias takeHead <b>take</b>;
+<dd>Alias to take items to the head of the queue.
+<dt>Value <b>peek</b>
+<dd>Return the head of the queue or Value.init if empty.
+<dt>mixin <b>MListCat</b>(Queue)
+<dd>Mixin <a href="#listcat">list catenation</a>.
+<dt>size_t <b>length</b>;
+<dd>Return length of queue.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if container is empty
+<dt>Value <b>opIndex</b>(size_t n);
+<dd>Return nth item where the head is item 0.
+<dt>void <b>opIndexAssign</b>(Value val, size_t n);
+<dd>Assign to the nth item
+<dt>void <b>addTail</b>(Value v);
+<dd>Add to tail of queue
+<dt>void <b>addTail</b>(Queue v);
+<dd>Append v to tail of queue
+<dt>Value <b>takeHead</b>();
+<dd>Remove and return first item
+<dt>void <b>removeHead</b>();
+<dd>Remove first item
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal by values
+<dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg);
+<dd>Foreach traversal by index-value pairs
+<dt>Queue <b>dup</b>;
+<dd>Duplicate queue.
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>int <b>opEquals</b>(Queue c);
+<dd>Test queue equality
+<dt>int <b>opCmp</b>(Queue c);
+<dd>Compare queues
+<dt>alias Queue <b>ContainerType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dt>alias ImplType <b>AdaptType</b>;
+<dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly;
+<dd>Aliases for container types
+</dl>
+<p>
+<a name="arrayqueue"></a>
+<dt>alias <b>ArrayQueue</b>!(Value)
+<dd>An alias for Queue!(Value,ArrayList!(Value)) to adapt an ArrayList
+to the queue interface.
+<p>
+<a name="pqueue"></a>
+<dt>alias <b>PriorityQueue</b>!(Value)
+<dd>An alias for Queue!(Value,ArrayHeap!(Value)) to adapt an ArrayHeap
+to the queue interface.
+
+</dl>
+
+<a name="set"></a>
+<h4>mintl.set</h4>
+<dl>
+<dt>struct <b>Set</b>!(Value, ImplType = HashAA!(Value,uint))
+<dd>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.
+<p>
+<dl>
+<dt>ImplType <b>impl</b>
+<dd>Read-write property holding the backing container
+<dt>void <b>add</b>(...);
+<dd>Add items to set
+<dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr);
+<dd>Add using va_arg inpurs
+<dt>static Set <b>make</b>(...)
+<dd>Consruct a Set using add(...)
+<dt>void <b>addItem</b>(Value item);
+<dd>Add item to set
+<dt>size_t <b>length</b>;
+<dd>Return number of items in the set.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if set is empty
+<dt>bool <b>opIndex</b>(Value item);
+<dd>Return true if the item is in the set
+<dt>void <b>remove</b>(Value item);
+<dd>Remove an item from the set if present
+<dt>Value[] <b>values</b>;
+<dd>Get items as a dynamic set.
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal of items in the set
+<dt>Set <b>dup</b>;
+<dd>Duplicate set
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>int <b>opEquals</b>(Set c);
+<dd>Test set equality
+<dt>alias Set <b>ContainerType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias ImplType <b>AdaptType</b>;
+<dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly;
+<dd>Aliases for container types
+</dl>
+<p>
+<a name="sortedset"></a>
+<dt>alias <b>SortedSet</b>!(Value)
+<dd>An alias for Set!(Value,SortedAA!(Value,uint)) to implement a sorted set.
+<p>
+<a name="multiset"></a>
+<dt>struct <b>MultiSet</b>!(Value, ImplType = HashAA!(uint,Value))
+<dd>A set which allows items to be repeated. Adapted from a customizable
+container type mapping items to repeat counts.
+<p>
+<dl>
+<dt>ImplType <b>impl</b>
+<dd>Read-write property holding the backing container
+<dt>void <b>add</b>(...);
+<dd>Add items to set
+<dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr);
+<dd>Add using va_arg inpurs
+<dt>static MultiSet <b>make</b>(...)
+<dd>Consruct a MultiSet using add(...)
+<dt>void <b>addItem</b>(Value item);
+<dd>Add item to set
+<dt>size_t <b>length</b>;
+<dd>Return number of items in the set.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if set is empty
+<dt>bool <b>opIndex</b>(Value item);
+<dd>Return true if the item is in the set
+<dt>void <b>remove</b>(Value item);
+<dd>Remove an item from the set if present
+<dt>Value[] <b>values</b>;
+<dd>Get items as a dynamic set. Duplicates are removed.
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal of items in the set. If an item is repeated it
+is passed multiple times consecutively to the delegate.
+<dt>MultiSet <b>dup</b>;
+<dd>Duplicate set
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>int <b>opEquals</b>(MultiSet c);
+<dd>Test set equality
+<dt>alias MultiSet <b>ContainerType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias ImplType <b>AdaptType</b>;
+<dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly;
+<dd>Aliases for container types
+</dl>
+<p>
+<a name="sortedmultiset"></a>
+<dt>alias <b>SortedMultiSet</b>!(Value)
+<dd>An alias for MultiSet!(Value,SortedAA!(Value,uint)) to implement a 
+sorted multi-set.
+</dl>
+
+<a name="share"></a>
+<h4>mintl.share</h4>
+The mintl.share module is publically imported into all container modules
+and stores shared defintions.
+<dl>
+<dt>const bit <b>ReadOnly</b> = true;
+<dd>A named constant to improve the readability of code involving read-only
+containers. See the section on <a href="#unmod">unmodifiable containers</a> for examples.
+<dt>class <b>IndexOutOfBoundsException</b> : Exception
+<dd>Exception thrown when attempting to access an invalid index or key. Checks for invalid indices can be disabled using version=MinTLNoIndexChecking.
+
+<a name="listcat">
+<dt>template <b>MListCatOperators</b>(List)</a>
+<dd>Concatenation routines to be mixed into the list-like containers
+<dl>
+<dt>void <b>add</b>(...);
+<dd>Add to list
+<dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr);
+<dd>Add using va_arg inpurs
+<dt>static List <b>make</b>(...)
+<dd>Consruct a List using add(...)
+<dt>void <b>addN</b>(uint n, Value v)
+<dd>Add the value n times to the list
+<dt>void <b>addBefore</b>(List.SliceType sublist, Value[] v)
+<dd>Insert the values in the dynamic array v before sublist
+<dt>void <b>addAfter</b>(List.SliceType sublist, Value[] v)
+<dd>Insert the values in the dynamic array v after sublist
+<dt>List <b>opCatAssign</b>(Value v);
+<dd>Concatenation operator this ~= v
+<dt>List <b>opCat</b>(Value v);
+<dd>Concatenation operator this ~ v. copies this
+<dt>List <b>opCat_r</b>(Value v);
+<dd>Concatenation operator v ~ this. copies this
+<dt>List <b>opCatAssign</b>(List v);
+<dd>Concatenation operator this ~= v. copies v
+<dt>List <b>opCat</b>(List v);
+<dd>Concatenation operator this ~ v. copies both arguments
+</dl>
+<a name="listalgo">
+<dt>template <b>MListAlgo</b>(Container, alias list)</a>
+<dd>List algorithms to be mixed into the list-like containers
+<dl>
+<dt>Container.SliceType <b>opIn</b>(Value v);
+<dd>Return a one-item slice of the first occurrence of v in the list.
+<dt>Container.SliceType <b>find</b>(int delegate(inout Value v) dg);
+<dd>Return a one-item slice of the first occurrence where dg is true.
+<dt>uint <b>count</b>(Value v);
+<dd>Return the number of time v appears in the list.
+<dt>void <b>swap</b>(Container v);
+<dd>Swap the contents of the list with v (assumes non-overlapping). Extra
+elements are ignored.
+<dt>void <b>fill</b>(Value v);
+<dd>Fill the container with v
+<dt>void <b>copy</b>(Container v);
+<dd>Copy the contents of v to this container. Extra elements are ignored.
+</dl>
+<a name="listcomm">
+<dt><b>MListCommon</b>(Container)</a>
+<dd>Common list routines
+<dl>
+<dt>bool <b>isEmpty</b>
+<dd>Return true if container is empty
+<dt>Value <b>opIndex</b>(size_t n);
+<dd>Return nth item where the head is item 0.
+<dt>void <b>opIndexAssign</b>(Value val, size_t n);
+<dd>Assign to the nth item
+<dt>Container.SliceType <b>opSlice</b>(size_t a, size_t b);
+<dd>Slice from item a to b (exclusive)
+<dt>Container.SliceType <b>opSlice</b>(Container.SliceType a, Container.SliceType b);
+<dd>Slice from head of a to tail of b
+<dt>Container.SliceType <b>head</b>
+<dd>Read-only property to get a one-item slice of the head.
+<dt>Container.SliceType <b>tail</b>
+<dd>Read-only property to get a one-item slice of the tail.
+<dt>Value[] <b>values</b>;
+<dd>Get list contents as dynamic array.
+<dt>Value <b>value</b>;
+<dd>Read/write property for the value of a one-item slice.
+<dt>void <b>addTail</b>(Value v);
+<dd>Add to tail of list
+<dt>void <b>addTail</b>(Container v);
+<dd>Copy v to tail of list
+<dt>void <b>addHead</b>(Value v);
+<dd>Add to head of list
+<dt>void <b>addHead</b>(Container v);
+<dd>Copy v to head of list
+<dt>Value <b>takeTail</b>();
+<dd>Remove and return last item
+<dt>Value <b>takeHead</b>();
+<dd>Remove and return first item
+<dt>void <b>removeTail</b>();
+<dd>Remove last item
+<dt>void <b>removeHead</b>();
+<dd>Remove first item
+<dt>void <b>remove</b>(Container.SliceType sublist);
+<dd>Remove sublist from list
+<dt>void <b>addBefore</b>(Container.SliceType subv, Container.SliceType v);
+<dd>Insert v before subv.
+<dt>void <b>addAfter</b>(Container.SliceType subv, Container.SliceType v);
+<dd>Insert v after subv.
+<dt>void <b>next</b>(int n = 1, int end = 0);
+<dd>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.
+<dt>Value* <b>lookup</b>(size_t n);
+<dd>Return a pointer to the nth item
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal by values
+<dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg);
+<dd>Foreach traversal by index-value pairs
+<dt>int <b>opApply</b>(int delegate(inout Container.SliceType n) dg);
+<dd>Foreach traversal by one-item slices
+<dt>Container <b>reverse</b>;
+<dd>Reverse list in-place.
+<dt>Container <b>dup</b>;
+<dd>Duplicate array list by duplicating backing array
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>int <b>opEquals</b>(Container c);
+<dd>Test list equality
+<dt>int <b>opCmp</b>(Container c);
+<dd>Compare lists
+</dl>
+</dl>
+
+<a name="slist"></a>
+<h4>mintl.slist</h4>
+<dl>
+<dt>struct <b>SList</b>(Value, bit ReadOnly = false, Alloc = GCAllocator)
+<dd>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 <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>mixin <b>MListCat</b>(SList)
+<dd>Mixin <a href="#listcat">list catenation</a>.
+<dt>size_t <b>length</b>;
+<dd>Return length of list.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if container is empty
+<dt>SList <b>tailList</b>;
+<dd>Return the tail of the list as a slice
+<dt>Value <b>opIndex</b>(size_t n);
+<dd>Return nth item where the head is item 0.
+<dt>void <b>opIndexAssign</b>(Value val, size_t n);
+<dd>Assign to the nth item
+<dt>SList <b>opSlice</b>(size_t a, size_t b);
+<dd>Slice from item a to b (exclusive)
+<dt>SList <b>opSlice</b>(SList a, SList b);
+<dd>Slice from head of a to tail of b
+<dt>SList <b>head</b>
+<dd>Read-only property to get a one-item slice of the head.
+<dt>SList <b>tail</b>
+<dd>Read-only property to get a one-item slice of the tail.
+<dt>Value <b>value</b>
+<dd>Read/write property for the value of a one-item slice.
+<dt>Value[] <b>values</b>;
+<dd>Get list contents as dynamic array.
+<dt>void <b>addTail</b>(Value v);
+<dd>Add to tail of list
+<dt>void <b>addTail</b>(SList v);
+<dd>Append v to tail of list
+<dt>void <b>addHead</b>(Value v);
+<dd>Add to head of list
+<dt>void <b>addHead</b>(SList v);
+<dd>Prepend v to head of list
+<dt>Value <b>takeHead</b>();
+<dd>Remove and return first item
+<dt>void <b>removeHead</b>();
+<dd>Remove first item
+<dt>void <b>addAfter</b>(SList subv, SList v);
+<dd>Insert v after subv.
+<dt>void <b>removeAfter</b>(SList sublist, size_t n=1);
+<dd>Remove n items following sublist
+<dt>void <b>removeBetween</b>(SList a, SList b);
+<dd>Remove items after the tail of a to the head of b (exclusive)
+<dt>void <b>next</b>(int n = 1, int end = 0);
+<dd>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.
+<dt>Value* <b>lookup</b>(size_t n);
+<dd>Return a pointer to the nth item
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal by values
+<dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg);
+<dd>Foreach traversal by index-value pairs
+<dt>int <b>opApply</b>(int delegate(inout SList n) dg);
+<dd>Foreach traversal by one-item slices
+<dt>SList <b>dup</b>;
+<dd>Duplicate list
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>void <b>trim</b>;
+<dd>Remove references to extra nodes kept for reuse
+<dt>int <b>opEquals</b>(SList c);
+<dd>Test list equality
+<dt>int <b>opCmp</b>(SList c);
+<dd>Compare lists
+<dt>mixin <b>MListAlgo</b>(this,SList)
+<dd>Mixin <a href="#listalgo">list algorithms</a>.
+<dt>SList!(Value,true,Alloc) <b>readonly</b>;
+<dd>Property that returns a read-only view of the container.
+<dt>SList!(Value,false,Alloc) <b>readwrite</b>;
+<dd>Property that returns a read-write view of the container.
+<dt>alias SList <b>ContainerType</b>;
+<dt>alias SList <b>SliceType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dt>alias ReadOnly <b>isReadOnly</b>;
+<dd>Aliases for container types
+</dl>
+</dl>
+<p>
+<a name="cslist"></a>
+<dl>
+<dt>struct <b>CircularSList</b>(Value, bit ReadOnly = false, Alloc = GCAllocator)
+<dd>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 <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>mixin <b>MListCat</b>(CircularSList)
+<dd>Mixin <a href="#listcat">list catenation</a>.
+<dt>size_t <b>length</b>;
+<dd>Return length of list.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if container is empty
+<dt>SList <b>toSList</b>;
+<dd>Return the list as a non-circular SList
+<dt>Value <b>opIndex</b>(size_t n);
+<dd>Return nth item where the head is item 0.
+<dt>void <b>opIndexAssign</b>(Value val, size_t n);
+<dd>Assign to the nth item
+<dt>SList <b>opSlice</b>(size_t a, size_t b);
+<dd>Slice from item a to b (exclusive)
+<dt>SList <b>opSlice</b>(SList a, SList b);
+<dd>Slice from head of a to tail of b
+<dt>SList <b>head</b>
+<dd>Read-only property to get a one-item slice of the head.
+<dt>SList <b>tail</b>
+<dd>Read-only property to get a one-item slice of the tail.
+<dt>Value <b>value</b>
+<dd>Read/write property for the value of a one-item slice.
+<dt>void <b>addTail</b>(Value v);
+<dd>Add to tail of list
+<dt>void <b>addTail</b>(CircularSList v);
+<dd>Append v to tail of list
+<dt>void <b>addHead</b>(Value v);
+<dd>Add to head of list
+<dt>void <b>addHead</b>(CircularSList v);
+<dd>Prepend v to head of list
+<dt>Value <b>takeHead</b>();
+<dd>Remove and return first item
+<dt>void <b>removeHead</b>();
+<dd>Remove first item
+<dt>void <b>addAfter</b>(SList subv, SList v);
+<dd>Insert v after subv.
+<dt>void <b>removeAfter</b>(SList sublist, size_t n=1);
+<dd>Remove n items following sublist
+<dt>void <b>removeBetween</b>(SList a, SList b);
+<dd>Remove items after the tail of a to the head of b (exclusive)
+<dt>void <b>rotate</b>(int n = 1);
+<dd>Rotate the list by n steps
+<dt>Value* <b>lookup</b>(size_t n);
+<dd>Return a pointer to the nth item
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal by values
+<dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg);
+<dd>Foreach traversal by index-value pairs
+<dt>int <b>opApply</b>(int delegate(inout SList n) dg);
+<dd>Foreach traversal by one-item slices
+<dt>CircularSList <b>dup</b>;
+<dd>Duplicate list
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>int <b>opEquals</b>(CircularSList c);
+<dd>Test list equality
+<dt>int <b>opCmp</b>(CircularSList c);
+<dd>Compare lists
+<dt>mixin <b>MListAlgo</b>(this,CircularSList)
+<dd>Mixin <a href="#listalgo">list algorithms</a>.
+<dt>CircularSList!(Value,true,Alloc) <b>readonly</b>;
+<dd>Property that returns a read-only view of the container.
+<dt>CircularSList!(Value,false,Alloc) <b>readwrite</b>;
+<dd>Property that returns a read-write view of the container.
+<dt>alias CircularAList <b>ContainerType</b>;
+<dt>alias SList!(Value,Alloc) <b>SliceType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dt>alias ReadOnly <b>isReadOnly</b>;
+<dd>Aliases for container types
+</dl>
+</dl>
+
+<a name="sortedaa"></a>
+<h4>mintl.sortedaa</h4>
+<dl>
+<dt>class <b>CompareFcnSetException</b>: Exception;
+<dd>Exception thrown when trying to set the comparison function of
+a non-empty array or an array that already had the comparison function
+set.
+</dl>
+<p>
+<dl>
+<dt>struct <b>SortedAA</b>(Key, Value, bit ReadOnly = false, Alloc = GCAllocator)
+<dd>A sorted associative array
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is <a href="#GCAlloc">GCAllocator</a>.
+<p>
+<dl>
+<dt>alias int delegate(Key* a, Key* b) <b>CompareFcn</b>;
+<dd>Signature of comparison functions
+<dt>void <b>compareFcn</b>(CompareFcn cmp);
+<dd>Set the comparison function
+<dt>void <b>add</b>(...);
+<dd>Add key-value pairs to array
+<dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr);
+<dd>Add using va_arg inpurs
+<dt>static SortedAA <b>make</b>(...)
+<dd>Consruct a SortedAA using add(...)
+<dt>size_t <b>length</b>;
+<dd>Return number of items in the array.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if array is empty
+<dt>Value* <b>get</b>(Key key, bit throwOnMiss = false);
+<dd>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.
+<dt>Value* <b>put</b>(Key key)
+<dd>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.
+<dt>bool <b>contains</b>(Key key)
+<dd>Returns true if the array contains the key
+<dt>bool <b>contains</b>(Key key, out Value value)
+<dd>Returns true if the array contains the key and sets the out value if
+present.
+<dt>Value <b>opIndex</b>(Key key);
+<dd>Return item with given key. Returns the default missing value if not present.
+<dt>void <b>opIndexAssign</b>(Value val, Key key);
+<dd>Assign a value to the given key
+<dt>Value <b>missing</b>
+<dd>Read/write property for the value to use on indexing a key not in
+the array. Defaults to Value.init
+<dt>SortedAA <b>head</b>()
+<dd>Return one-item slice of the smallest item
+<dt>SortedAA <b>tail</b>()
+<dd>Return one-item slice of the greatest item
+<dt>void <b>next</b>(int n = 1, int end = 0);
+<dd>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.
+<dt>SortedAA <b>from</b>(Key a);
+<dd>Return a one-item slice of the smallest item greater than or equal to a.
+<dt>SortedAA <b>to</b>(Key b);
+<dd>Return a one-item slice of the greatest item smaller than b.
+<dt>SortedAA <b>opSlice</b>(Key a, Key b);
+<dd>Slice from item a to b (exclusive).
+<dt>SortedAA <b>opSlice</b>(SortedAA a, SortedAA b);
+<dd>Slice from first key in a to last key in b.
+<dt>Value <b>take</b>(Key key);
+<dd>Remove a key from array if present and return value. Returns the
+default missing value if the key was not present.
+<dt>void <b>remove</b>(Key key);
+<dd>Remove a key from array if present.
+<dt>void <b>remove</b>(SortedAA subarray);
+<dd>Remove a slice from array.
+<dt>void <b>trim</b>;
+<dd>Remove references to extra nodes kept for reuse
+<dt>Value[] <b>values</b>;
+<dd>Get values as a dynamic array. The values are in order.
+<dt>Key[] <b>keys</b>;
+<dd>Get keys as a dynamic array. The keys are in order.
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal by values
+<dt>int <b>opApply</b>(int delegate(inout Key key, inout Value x) dg);
+<dd>Foreach traversal by key-value pairs
+<dt>int <b>opApply</b>(int delegate(inout SortedAA n) dg);
+<dd>Foreach traversal by one-item slices
+<dt>SortedAA <b>dup</b>;
+<dd>Duplicate array
+<dt>void <b>clear</b>()
+<dd>Clear contents. Only needed if a non-GCAllocator is used.
+<dt>int <b>opEquals</b>(SortedAA c);
+<dd>Test array equality
+<dt>SortedAAReverseIter!(Key,Value) <b>backwards</b>();
+<dd>Backwards traversal for "foreach"
+<dt>Value <b>value</b>;
+<dd>Return value of a one-item slices
+<dt>Key <b>key</b>;
+<dd>Return key of a one-item slices
+<dt>SortedAA!(Key,Value,true,Alloc) <b>readonly</b>;
+<dd>Property that returns a read-only view of the container.
+<dt>SortedAA!(Key,Value,false,Alloc) <b>readwrite</b>;
+<dd>Property that returns a read-write view of the container.
+<dt>alias SortedAA <b>ContainerType</b>;
+<dt>alias SortedAA <b>SliceType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias Key <b>IndexType</b>;
+<dd>Aliases for container types
+</dl>
+</dl>
+
+<a name="stack"></a>
+<h4>mintl.stack</h4>
+<dl>
+<dt>struct <b>Stack</b>!(Value, ImplType = Deque!(Value))
+<dd>A stack of items adapted from a customizable list container type. The
+default backing container is a Deque.
+<p>
+<dl>
+<dt>ImplType <b>impl</b>
+<dd>Read-write property holding the backing container.
+<dt>alias addTail <b>push</b>;
+<dd>Alias to add items to the tail of the stack.
+<dt>alias takeTail <b>pop</b>;
+<dd>Alias to take items from the tail of the stack.
+<dt>Value <b>peek</b>
+<dd>Return the top of the stack or Value.init if empty.
+<dt>mixin <b>MListCat</b>(Stack)
+<dd>Mixin <a href="#listcat">list catenation</a>.
+<dt>size_t <b>length</b>;
+<dd>Return length of stack.
+<dt>bool <b>isEmpty</b>
+<dd>Return true if container is empty
+<dt>Value <b>opIndex</b>(size_t n);
+<dd>Return nth item where the head is item 0.
+<dt>void <b>opIndexAssign</b>(Value val, size_t n);
+<dd>Assign to the nth item
+<dt>void <b>addTail</b>(Value v);
+<dd>Add to tail of stack
+<dt>void <b>addTail</b>(Stack v);
+<dd>Append v to tail of stack
+<dt>Value <b>takeHead</b>();
+<dd>Remove and return first item
+<dt>void <b>removeHead</b>();
+<dd>Remove first item
+<dt>int <b>opApply</b>(int delegate(inout Value x) dg);
+<dd>Foreach traversal by values
+<dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg);
+<dd>Foreach traversal by index-value pairs
+<dt>Stack <b>dup</b>;
+<dd>Duplicate stack.
+<dt>int <b>opEquals</b>(Stack c);
+<dd>Test stack equality
+<dt>int <b>opCmp</b>(Stack c);
+<dd>Compare stacks
+<dt>alias Stack <b>ContainerType</b>;
+<dt>alias Value <b>ValueType</b>;
+<dt>alias size_t <b>IndexType</b>;
+<dt>alias ImplType <b>AdaptType</b>;
+<dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly;
+<dd>Aliases for container types
+</dl>
+<p>
+<a name="arraystack"></a>
+<dt>alias <b>ArrayStack</b>!(Value)
+<dd>An alias for Stack!(Value,ArrayList!(Value)) to adapt an ArrayList
+to the stack interface.
+</dl>
+
+</BODY>
+</HTML>