0) {
+ if (end >= 0)
+ doNext(tail_,n);
+ if (end <= 0)
+ doNext(head_,n);
+ } else {
+ n = -n;
+ if (end >= 0)
+ doPrev(tail_,n);
+ if (end <= 0)
+ doPrev(head_,n);
+ }
+ }
+
+ /** Test for equality of two arrays. The operation is O(n) where n
+ * is length of the array.
+ */
+ int opEquals(HashAA c) {
+ Node* i = head_;
+ Node* j = c.head_;
+ Node* end = tail_;
+ Node* cend = c.tail_;
+ TypeInfo ti_k = typeid(Key);
+ TypeInfo ti_v = typeid(Value);
+ int do_test(Node*p1,Node*p2) {
+ if (!ti_k.equals(&p1.key,&p2.key))
+ return 0;
+ if (!ti_v.equals(&p1.val,&p2.val))
+ return 0;
+ return 1;
+ }
+ while (i !is null && j !is null) {
+ if (!do_test(i,j))
+ return 0;
+ if (i is end || j is cend) {
+ return (i is end && j is cend);
+ }
+ i = i.next;
+ j = j.next;
+ }
+ return (i is null && j is null);
+ }
+
+ /** Test if a key is in the array. The target array can be a sub-array
+ * but the key may fall outside of the sub-array range.
+ */
+ bool contains(Key key) {
+ return get(key) !is null;
+ }
+
+ /** Test if a key is in the array and set value if it is. */
+ bool contains(Key key,out Value value) {
+ Value* node = get(key);
+ if (node)
+ value = *node;
+ return node !is null;
+ }
+
+ /** Iterate over the array calling delegate to perform an action. A
+ * one-element sub-array is passed to the delegate.
+ */
+ int opApplyNoKeyStep(int delegate(inout Value val) dg, int step = 1) {
+ int dg2(inout HashAA itr) {
+ Value value = itr.value;
+ return dg(value);
+ }
+ return opApplyIterStep(&dg2,step);
+ }
+
+ /** Iterate over the array calling delegate to perform an action. A
+ * one-element sub-array is passed to the delegate.
+ */
+ int opApplyWithKeyStep(int delegate(inout Key key, inout Value val) dg,
+ int step = 1) {
+ int dg2(inout HashAA itr) {
+ Key key = itr.key;
+ Value value = itr.value;
+ return dg(key,value);
+ }
+ return opApplyIterStep(&dg2,step);
+ }
+
+ /** Iterate over the array calling delegate to perform an action. A
+ * one-element sub-array is passed to the delegate.
+ */
+ int opApplyIterStep(int delegate(inout HashAA itr) dg,int step=1) {
+ int res = 0;
+ HashAA itr;
+ Node* x = step>0?head_:tail_;
+ Node* end = step>0?tail_:head_;
+ while (x !is null) {
+ itr.head_ = itr.tail_ = x;
+ res = dg(itr);
+ if (res || x is end) return res;
+ x = step>0?x.next:x.prev;
+ }
+ return res;
+ }
+
+ /** Iterate backwards over the array (from last to first key). The target
+ * array can be a sub-array. This should only be called as the
+ * iteration parameter in a foreach statement
+ */
+ LAReverseIter!(Key,Value,ReadOnly,Alloc) backwards() {
+ LAReverseIter!(Key,Value,ReadOnly,Alloc) res;
+ res.list = this;
+ return res;
+ }
+
+ /** Helper functions for opApply */
+ mixin MOpApplyImpl!(HashAA);
+ alias opApplyNoKey opApply;
+ alias opApplyWithKey opApply;
+ alias opApplyIter opApply;
+
+ Node* getHead(){return head_;}
+ Node* getTail(){return tail_;}
+ mixin MSequentialSort!(HashAA, getHead,getTail);
+ void sort(int delegate(Key*a, Key*b) cmp = null) {
+ Node* newhead, newtail;
+ dosort(newhead,newtail,cmp);
+ head_ = newhead;
+ tail_ = newtail;
+ }
+
+ private {
+ struct Node {
+ Node* next, prev, nextHash;
+ union {
+ uint len;
+ uint hash;
+ }
+ Key key;
+ Value val;
+ Key* sortLookup(){return &key;}
+ }
+ Node*[] data;
+ Node* head_, tail_;
+ }
+
+ private uint dlength() { return data[0].len; }
+
+ // size primes from aaA.d and planetmath.org
+ private static uint[] prime_list =
+ [97u, 389u, 1543u, 6151u,
+ 24593u, 98317u, 393241u, 1572869u,
+ 6291469u, 25165843u, 100663319u, 402653189u,
+ 1610612741u, 4294967291u
+ ];
+}
+
+// internal helper struct for backwards iteration
+struct LAReverseIter(Key,Value,bit ReadOnly,Alloc) {
+ mixin MReverseImpl!(HashAA!(Key,Value,ReadOnly,Alloc));
+}
+
+//version = MinTLVerboseUnittest;
+//version = MinTLUnittest;
+version (MinTLUnittest) {
+ private import std.random;
+ unittest {
+ version (MinTLVerboseUnittest)
+ printf("starting mintl.hashaa unittest\n");
+
+ HashAA!(int,int) m;
+ m[4] = 100;
+ m[-10] = 200;
+ m[17] = 300;
+ assert( m.length == 3 );
+ assert( m[-10] == 200 );
+
+ HashAA!(int,int) mm;
+ mm.add(4,100, -10,200, 17,300);
+ assert( m == mm );
+
+ // test foreach
+ int[] res;
+ res.length = 3;
+ int n=0;
+ foreach(int val; m) {
+ res[n++] = val;
+ }
+ assert( res[0] == 100 );
+ assert( res[1] == 200 );
+ assert( res[2] == 300 );
+
+ // test removing an item
+ m.remove(-10);
+ n = 0;
+ foreach(int val; m) {
+ res[n++] = val;
+ }
+ assert( res[0] == 100 );
+ assert( res[1] == 300 );
+
+ // test assigning to an item already in array
+ m[22] = 400;
+ m[17] = 500;
+ n = 0;
+ foreach(int val; m) {
+ res[n++] = val;
+ }
+ assert( res[0] == 100 );
+ assert( res[1] == 500 );
+ assert( res[2] == 400 );
+
+ // test backwards foreach
+ n = 0;
+ foreach(int k,int val; m.backwards()) {
+ res[n++] = val;
+ }
+ assert( res[0] == 400 );
+ assert( res[1] == 500 );
+ assert( res[2] == 100 );
+
+ // test slicing
+ HashAA!(int, int) m2 =
+ HashAA!(int,int).make(400,4,100,1,500,5,300,3,
+ 200,2,600,6);
+ HashAA!(int, int) m3;
+ m3 = m2[500 .. 600];
+ assert( m3.length == 3 );
+ n = 0;
+ foreach(int k,int val; m3) {
+ res[n++] = val;
+ }
+ assert( res[0] == 5 );
+ assert( res[1] == 3 );
+ assert( res[2] == 2 );
+
+ // test keys
+ int[] keys = m3.keys;
+ assert( keys[0] == 500 );
+ assert( keys[1] == 300 );
+ assert( keys[2] == 200 );
+
+ // test rehash
+ for (int k=0; k<1000; k++)
+ m3[k] = k;
+ HashAA!(int,int) m4 = m3.rehash;
+ assert( m4 == m3 );
+
+ // test simple sorting
+ HashAA!(int,int) s1,s12;
+ s1.add(40,1,300,2,-20,3,100,4,400,5,200,6);
+ s12 = s1.dup;
+ s1.sort();
+ assert( s1 == HashAA!(int,int).make(-20,3,40,1,100,4,200,6,300,2,400,5) );
+ // sort a slice in-place
+ HashAA!(int,int) slice1 = s12[300 .. 200];
+ slice1.sort();
+ assert( s12 == HashAA!(int,int).make(40,1,-20,3,100,4,300,2,400,5,200,6));
+
+ // test a large sort with default order
+ HashAA!(double,int) s3;
+ for (int k=0;k<1000;k++) {
+ s3[1.0*rand()/100000.0 - 500000.0] = k;
+ }
+ HashAA!(double,int) s4 = s3.dup;
+ s3.sort();
+ double[] keys2 = s3.keys;
+ for (int k=0;k<999;k++) {
+ assert( keys2[k] <= keys2[k+1] );
+ }
+ // test a large sort with custom order
+ int cmp(double*x,double*y){return *x>*y?-1:*x==*y?0:1;}
+ s4.sort(&cmp);
+ keys2 = s4.keys;
+ for (int k=0;k<999;k++) {
+ assert( keys2[k] >= keys2[k+1] );
+ }
+
+ version (MinTLVerboseUnittest)
+ printf("finished mintl.hashaa unittest\n");
+ }
+}
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/index.html
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/index.html Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,1781 @@
+ Minimal Template Library for D
+
+MinTL
+MinTL is a "minimal template library" of containers for the D
+programming language. For more info about D see DigitalMars D home page. The
+downloads are the Core Library and
+the MinTL Concurrent Library
+(mintlc web page), which includes
+a dependent Synchronization Library.
+The current version is 2.7.1.
+
+This library is in the public domain.
+Written by
+Ben Hinkle, 2004.
+Email comments and bug reports to ben.hinkle@gmail.com
+
+
Contents
+Overview
+List Containers
+Associative Containers
+Slicing
+Foreach traversals
+Sorting
+Allocators
+Unmodifiable Containers
+Examples
+API Reference by module
+
+
+ Overview
+
+The philosophy of the library is to be as simple and minimal as
+possible:
+
+
+ The design is simple by keeping the number of classes to a
+minimum and reusing concepts from builtin dynamic and associative
+arrays. For example a slice of a container has the same type as the
+container, just as the slice of a dynamic array is another dynamic
+array.
+
+
+The memory footprint and the garbage generation is kept to a minimum
+by relying on structs instead of classes and by implementing slicing
+and traversals without allocating dynamic memory. Some containers
+also recycle nodes. For example when the head or tail of a list is removed
+the node is retained and reused the next time an item is added
+to the head or tail. Optional Allocator parameters allow custom memory
+management.
+
+ Closely related data structures share common naming conventions
+and adapters reuse fundamental data structures like arrays, linked-lists
+and sorted associative arrays for stacks, queues and sets.
+Performance can be tuned for different uses by either choose
+between several variations (eg. a linked list, a circular array or a
+deque) or by supplying optional constructor arguments.
+
+
+
+
+MinTL has the following containers
+
+
+List containers
+
+| container | implementation | file | brief |
+
+
+| List
+ | doubly linked list
+ | list.d
+ | sortable linked list with "previous" and "next" pointers
+ |
+
+
+| CircularList
+ | circular doubly linked list
+ | list.d
+ | doubly linked list where the head and tail are linked
+ |
+
+
+| SList
+ | singly linked list
+ | slist.d
+ | linked list with only "next" pointers
+ |
+
+
+| CircularSList
+ | circular singly linked list
+ | slist.d
+ | singly linked list where the tail points to the head
+ |
+
+
+| ArrayList
+ | circular array
+ | arraylist.d
+ | sortable list backed by a resizable circular array
+ |
+
+| Deque
+ | circular block-allocated array
+ | deque.d
+ | list backed by a resizable block-allocated circular array
+ |
+
+| ArrayHeap
+ | heap
+ | arrayheap.d
+ | complete binary tree backed by an array
+ |
+
+| Stack
+ | adapter
+ | stack.d
+ | adapts a list container to be a stack
+ |
+
+| ArrayStack
+ | ArrayList
+ | stack.d
+ | wraps an ArrayList with the stack adapter
+ |
+
+| Queue
+ | adapter
+ | queue.d
+ | adapts a list container to be a queue
+ |
+
+| ArrayQueue
+ | ArrayList
+ | queue.d
+ | wraps an ArrayList with the queue adapter
+ |
+
+| PriorityQueue
+ | ArrayHeap
+ | queue.d
+ | wraps an ArrayHeap with the queue adapter
+ |
+
+
+
+Associative containers
+
+| container | implementation | file | brief |
+
+| HashAA
+ | linked hash table
+ | hashaa.d
+ | sortable associative array with nodes ordered by insertion order
+ |
+
+| SortedAA
+ | red-black tree
+ | sortedaa.d
+ | sorted associative array |
+
+
+| Set
+ | adapter
+ | set.d
+ | adapts an associative container to be a set
+ |
+
+| SortedSet
+ | SortedAA
+ | set.d
+ | wraps a SortedAA with the set adapter
+ |
+
+| MultiSet
+ | adapter
+ | set.d
+ | adapts an associative container to be a set with repeats
+ |
+
+| SortedMultiSet
+ | SortedAA
+ | set.d
+ | wraps a SortedAA with the multi-set adapter
+ |
+
+| MultiAA
+ | adapter
+ | multiaa.d
+ | adapts an associative container to hold repeated keys
+ |
+
+| SortedMultiAA
+ | SortedAA
+ | multiaa.d
+ | wraps a SortedAA with the multi-aa adapter
+ |
+
+
+
+The module mintl.array defines helper functions for builtin dynamic
+and associative arrays.
+
+
+ Build and Install
+To use MinTL first unpack the library in a directory on the D compiler
+search path. There are pre-built debug and non-debug versions of the library.
+To enable flexible add() datatype support uncomment the
+version=WithBox statement in mintl.share and recompile MinTL.
+To use std.boxer in a debug build you must also rebuild phobos with
+debugging.
+If you wish to rebuild MinTL enter the mintl directory and type
+make -f win32.mak or make -f linux.mak.
+In your source code import the desired modules and compile each
+container used and the mintl static library into the application.
+If a concurrent container is needed download the mintlc
+sub-package and link that library and
+the Locks library into the
+application. For example on Linux to compile the program app.d
+
+import mintl.list;
+
+int main() {
+ List!(int) list = List!(int).make(10,20,30);
+ return 0;
+}
+
+run in the directory above mintl the command
+
+ dmd app.d mintl/libmintl_debug.a
+
+to build with asserts or
+
+ dmd app.d -release mintl/libmintl.a
+
+to build without asserts.
+On Windows run
+
+ dmd app.d mintl\mintl_debug.lib
+
+or
+
+ dmd app.d -release mintl\mintl.lib
+
+If the mintl directory is not in the current directory then use the -I flag
+to add it to the search path
+
+ dmd app.d -Ipath_to_mintl path_to_mintl/mintl/libmintl.a
+
+or modify the dmd\bin\sc.ini file (on Windows) or dmd.conf (on Linux)
+to include the paths to mintl. For example if MinTL is unpacked in the
+directory C:\d on Windows then sc.ini should be modified to include C:\d
+in the include path and C:\d\mintl on the library search path:
+
+LIB="%@P%\..\lib";\dm\lib;C:\d\mintl
+DFLAGS="-I%@P%\..\src\phobos";C:\d
+
+On Linux the static library can be put in a standard location like
+/usr/lib if desired.
+
+
+ List Containers
+
+The list containers List, SList,
+CircularList, CircularSList, ArrayList,
+Deque, ArrayHeap and the concurrent queues
+and stacks share a naming convention
+for adding and removing items. The head is the
+first item in the container and the tail is the last item.
+All list containers support constant-time access to the head
+and tail.
+The speed of accessing the length property depends on the
+container. Array-based containers have constant-time access to length,
+the linked-list containers have constant-time unless an operation
+modifies the list to have unknown length, in which case the next
+time the length is computed it is cached again. The singly-linked
+lists have linear-time length access and it is not cached.
+
+Some containers maintain nodes past the head and tail
+of the list as extra capacity. To trim off any extra capacity
+most containers support a trim function.
+
+The circular lists
+CircularList and CircularSList are the same as the non-circular
+versions except that slicing a circular list returns a non-circular
+list and node are not reused when adding or removing items. However
+circular lists are useful when the objects being modeled do not have a
+natural unique definition of a head or tail.
+
+An ArrayList can also be used as a dynamic array with
+managed capacity. Set the capacity property or allocate an array
+with the desired capacity
+and leave the head of the arraylist at 0. The arraylist will
+automatically grow the capacity as required.
+
+
To add items to a container call add with any number of
+items. For example
+
+ List!(int) x,y,z;
+ y.add(10,20,30);
+ z.add(50,60,70);
+ x = y; x ~= 40; x ~= z; x ~= 80;
+
+results in the following linked list
+
+ x[0],y[0] y[2] z[0] z[2] x[7]
+ 10 <-> 20 <-> 30 <-> 40 <-> 50 <-> 60 <-> 70 <-> 80
+
+To add a single item or list call addTail or use
+one of the concatenation operators. Some containers also support adding
+items or lists at the head using addHead or at a position
+in the interior of the list using addBefore or addAfter.
+To create a list in an expression use the static make function
+For example,
+
+ List!(int) x;
+ x = List!(int).make(10,20,30) ~ List!(int).make(50,60,70);
+
+
+ To remove items call one of the take or
+remove functions.
+All list containers support removeHead to remove
+the head of the list and takeHead to remove and return
+the stored value, if any.
+Some containers also support takeTail and
+removeTail to remove the tail and remove
+to remove a slice.
+
+
+Stacks and queues are implemented as adapters of a list
+container. By default they use a Deque as the backing container.
+Stacks define aliases push for add
+and pop for takeTail. Queues define an alias
+take for takeHead (the function add is used
+to add to the end of a queue). For example,
+
+ Stack!(char[]) x;
+ x.push("first","second");
+ assert( x.pop == "second" );
+ assert( x.pop == "first" );
+
+ Queue!(char[]) x;
+ x.add("first","second");
+ assert( x.take == "first" );
+ assert( x.take == "second" );
+
+A PriorityQueue is an ArrayHeap wrapped with the Queue adapter. To
+set a custom comparison function access the impl property of the
+adapter:
+
+ PriorityQueue!(char[]) x;
+ x.impl.compareFcn = &fcn;
+ x.add("first","second");
+
+
+The following table outlines the advantages and disadvantages of
+each list container
+
+
+| container | advantages | disadvantages |
+
+
+| List
+ | O(1) insertion at head/tail or before/after slices
+ | O(n) access to middle of list
+ |
+
+
+| SList
+ | O(1) insertion at head/tail or after slices; less overhead
+than List
+ | O(n) access to middle or near end of list
+ |
+
+
+| ArrayList
+ | O(1) insertion at head/tail. O(1) access to any index
+ | O(n) insertion in middle
+ |
+
+
+| Deque
+ | O(1) insertion at head/tail. O(1) access to any index.
+Block allocated.
+ | O(n) insertion in middle; non-contiguous storage
+ |
+
+
+| ArrayHeap
+ | maintains items in semi-sorted order; O(log(n)) add/remove.
+ | only allows addTail and takeHead
+ |
+
+
+
+
+ Associative Containers
+
+The associative containers SortedAA,HashAA, and
+ConcurrentAA are similar to builtin associative arrays but
+with extra capabilities. The SortedAA maintains the keys in
+some specific order as determined by a comparison function. By
+default the keys are ordered by the type's default comparison
+function. To specify a custom comparison function assign to the
+compareFcn property. The HashAA maintains the keys
+in insertion order, meaning if an indexing expression using key
+x is evaluated before an indexing expression using key
+y then x is traversed before y in
+foreach traversals. Assigning to a key already in the array
+does not change the insertion order. The other associative array
+properties dup, length, keys and
+values are also implemented.
+
+
+Elements are inserted or modified using the add function or
+using indexing lvalue expressions
+and retrieved using indexing rvalue expressions. To test if a key is in
+the array use the overloaded contains functions.
+An indexing expression that is not an assignment will return a
+default missing value. The missing value defaults to Value.init
+but can be set by assigning to the missing property.
+The functions get and put allow more flexibility in handling
+missing keys by allowing the user to either return null, throw or
+insert.
+To remove an item call the remove function. Both HashAA
+and SortedAA maintain a freelist of removed nodes for future
+reuse. To release the freelist for garbage collection call trim.
+
+For example to define a sorted associative
+array with three entries associating "first" with 10, "second" with
+20 and "third" with 30 type
+
+ SortedAA!(int,char[]) x;
+ x.add(10,"first", 20,"second", 30,"third");
+
+or equivalently,
+
+ SortedAA!(int,char[]) x;
+ x[10] = "first";
+ x[20] = "second";
+ x[30] = "third";
+
+To create an associative array in an expression use the static make function
+For example,
+
+ foo(SortedAA!(int,char[]).make(10,"first",20,"second",30,"third"));
+
+
+
+The number of elements in an associative container is computed by
+the length property.
+
+
+Sets and multi-associative-arrays are implemented as adapters of an
+associative container.
+By default sets use a HashAA as the backing container.
+Use add
+to add items to a set and use an indexing expression
+to check if an item is in the set. For example,
+
+ Set!(char[]) x;
+ x.add("first","second","third");
+ assert( x["first"] );
+ assert( x["second"] );
+ assert( x["third"] );
+ assert( !x["fourth"] );
+
+ MultiSet!(char[]) mx;
+ xm.add("first","second","first","third","second");
+ xm.remove("first");
+ assert( x["first"] );
+
+ MultiAA!(int,char[]) y;
+ y.add(10,"first",20,"second",10,"third");
+ assert( y[10].length == 2 );
+
+
+
+ Slicing
+
+In general slicing a container behaves like slicing a dynamic
+array. For example, slicing between two indices in a List creates
+another List with the head at the first index and the tail at the
+element before the second index. The contents of the slice is shared
+with the original list so assigning new values to elements in the list
+will be visible in the oringal list. The resulting slice, or
+sub-list, can be traversed using "foreach", duplicated, indexed into,
+etc just like a slice of a dynamic array can be treated as a
+"first-class" dyamic array. The following diagram illustrates the
+relationships for x and y if
+x is a list with 6 items and
+y is the slice x[2..4].
+
+
+ x[0] y[0] y[1] x[5]
+ 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5
+
+Executing z = y.dup would result in
+
+ z[0] z[1]
+ 2 <-> 3
+
+
+One should be careful when resizing or writing to a slice. For example
+do not (in general) append or prepend item to a sub-list using the addTail or addHead
+functions or remove items using removeTail and removeHead unless the
+original list is no longer needed. To insert an item or list at a
+certain location create a slice with the head at the desired location
+and call addBefore or create a slice with the tail at the desired
+location and call addAfter. To remove a portion of a list create a
+slice and call remove. Again one should always insert and remove from
+the original list otherwise any variable referring to the original list
+will become out of sync.
+
+A sub-list can be moved towards the head or tail
+of the original list by calling the next function.
+This allows a sub-list to traverse up and down the original list efficiently.
+Continuing the example from above, executing y.next(-1) would result
+in
+
+ x[0] y[0] y[1] x[5]
+ 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5
+
+and then executing x.remove(y) would result in
+
+ x[0] x[3]
+ 0 <-> 3 <-> 4 <-> 5
+
+ y[0] y[1]
+ 1 <-> 2
+
+The performance of inserting and removing from the interior
+of an ArrayList or Deque can be significantly worse than that of a List
+if the slices are near the middle of the container.
+
+
+The SortedAA slicing behavior is designed to chose slices without modifying
+the underlying container. The functions from and to
+can find a one-item slice starting from or up to a given key.
+For example if words is a sorted associative array indexed by
+char[] then
+
+ words["a" .. "b"]
+
+or, equivalently,
+
+ words[words.from("a") .. words.to("b")]
+
+is a slice containing all the items with keys that start with the character "a"
+even if the strings "a" and "b" aren't in the container.
+
+
+ Foreach
+Containers and slices of containers can be traversal in
+foreach statements
+by value, key-value pairs and one-element slices. Some containers
+support moving a slice up and down the container. For these containers
+a slice can be used for the same purposes as an iterator in C++ or
+Java.
+
+Each container also supports backwards traversals by calling
+backwards in a foreach statement. For example,
+
+ List!(int) x;
+ ...
+ foreach( int val; x.backwards() )
+ printf("%d ",val);
+
+will print out the contents of x from tail to head.
+Backwards traversals do not allocate any dynamic memory.
+
+
+ Sorting
+MinTL supports sorting containers in two forms. The SortedAA
+is a sorted associative container that maintains its elements in a
+given sorted order at all times. The comparison delegate
+used to determine the element order must be specified
+before the first element is insert or the key's default comparison
+function will be used and it cannot be changed during the lifetime
+of the container. The SortedSet
+and SortedMultiAA are derived from SortedAA and
+have the same sorting semantics.
+
+The other form of sorting is through calling the sort
+methods of the containers ArrayList, Deque, List,
+and HashAA or by using the sort template in
+mintl.array to sort a dynamic array. These sort methods
+take an optional comparison delegate. The default comparison
+delegate is the sorting type's default comparison function. For
+the list-like containers the sorting type is the value type of
+the container. For HashAA the sorting type is the key
+type. Sorting is done in-place and slices are preserved relative
+to their surrounding container. For example, the following code
+creates a short linked list, sorts and slice and compares it
+with the expected end result:
+
+ List!(int) list;
+ list.add(40,300,-20,100,400,200);
+ list[1 .. 5].sort(); // sort a slice in-place
+ assert( list == List!(int).make(40,-20,100,300,400,200));
+
+
+Sorting a container does not change the behavior of adding new elements.
+The sorting operation is performed once and the comparison function
+is not remembered by the container or used in any other way. For example
+sorting a HashAA which was previously maintained in insertion
+order will sort the elements but adding any new elements will add them
+to the end of the traversal order in insertion order again.
+
+
+ Allocators
+Most containers accept an optional Allocator parameter to
+customize memory management. The default allocator is the
+GCAllocator which indicates to the container that the garbage
+collector should be used for all allocations. If a custom allocator
+is supplied the container will call the memory management functions in
+the allocator to allocate and free memory. Users who supply a
+non-garbage-collecting allocator need to call clear when done
+with a container so that the memory can be released.
+
+
+An allocator is a type containing 8 symbols malloc, calloc, realloc,
+free and the corresponding GC-aware versions gcMalloc, gcCalloc,
+gcRealloc and gcFree. Containers will call the GC-aware functions on
+blocks that may hold roots and otherwise will call the regular
+functions. Allocators are expected to throw an OutOfMemory
+exception if the allocation fails.
+
+
+The two predefined allocators Malloc and MallocNoRoots use
+std.c.stdlib.malloc to perform allocations. The MallocNoRoots ignores
+any requests by the container to register roots with the GC. The
+MallocNoRoots allocator should only be used with containers that the
+user knows will never contain any roots. For example,
+
+ ArrayList!(int,MallocNoRoots) x;
+ x.add(10,20,30);
+ ...
+ x.clear();
+
+
+
+
Unmodifiable Containers
+The ReadOnly template parameter makes a container
+unmodifiable. A read-only container does not have operations that add or
+remove or change elements. However the underlying data is shared with
+the original modifiable container so a read-only container only
+guarantees that the elements will not be modified by that particular
+view of the container.
+A slice of a read-only container is also read-only.
+The readonly property creates a read-only view of a container.
+The readwrite property creates a read-write view.
+For example
+
+ void foo(List!(int,ReadOnly) y) { ... }
+ List!(int) x;
+ x.add(10,20,30);
+ foo(x.readonly);
+
+
+
+ Examples
+The source files have examples and unittests
+that one can use to get a feel for the behavior. The following example
+walks through some uses of MinTL:
+Create a list of the integers 0 through 10
+
+ List!(int) x;
+ x.add(0,1,2,3,4,5,6,7,8,9,10);
+
+and print out the items 5 though 8
+
+ foreach(int val; x[5..9])
+ printf("%d ",val);
+
+to output
+
+ 5 6 7 8
+
+Assigning x to another variable y shares
+the underlying list contents, so assigning through y
+is reflected in x:
+
+ List!(int) y = x;
+ y[0] = 100;
+ assert( x[0] == 100 );
+
+When passing a container to a function that could add or remove
+elements from the container be sure to use "inout" parameters
+to be sure the original variable in the calling frame is
+properly updated.
+
+
+
+ API Reference
+This section lists the public structs and functions in MinTL without
+detailed explanation. For more information see the documentation before
+the function or struct in the source file. Template functions are
+written as
+ return-type fcn-name!(tmpl-param,...)(arg1, arg2,...);
+
+to mimic how it would appear in user code. The API is organized by
+module:
+
+- mintl.array
+
- mintl.arrayheap
+
- mintl.arraylist
+
- mintl.deque
+
- mintl.hashaa
+
- mintl.list
+
- mintl.mem
+
- mintl.multiaa
+
- mintl.queue
+
- mintl.set
+
- mintl.share
+
- mintl.slist
+
- mintl.sortedaa
+
- mintl.stack
+
+
+
+
mintl.array
+
+- void reserve!(Value[])(inout Value[] x, size_t n);
+
- Reserve capacity for a dynamic array
+
- DArrayReverseIter backwards!(Value[])(Value[] x);
+
- Reverse dynamic array "foreach" traversal
+
- void sort!(Value[])(Value[] data, int delegate(Value* x, Value* y) cmp = null);
+
- Sort the array in increasing order as defined by the given comparison
+delegate. If no delegate is supplied the default comparison function of the
+Value type is used.
+
+
+
+mintl.arrayheap
+
+- struct ArrayHeap(Value, Alloc = GCAllocator)
+
- A heap (complete binary tree) backed by an array. x[n] is greater than
+or equal to x[2*n+1] and x[2*n+2]. x[0] is the greatest item.
+An optional allocator can customize memory management. The default allocator
+is GCAllocator.
+
+
+- Value[] data;
+
- Backing array
+
- size_t length;
+
- Return length of heap
+
- alias int delegate(Value* a, Value* b) CompareFcn;
+
- Signature of comparison functions
+
- void compareFcn(CompareFcn cmp);
+
- Set the comparison function
+
- bool isEmpty
+
- Return true if container is empty
+
- Value opIndex(size_t n);
+
- Return nth item where the head is item 0.
+
- void opIndexAssign(Value val, size_t n);
+
- Assign to the nth item
+
- Value[] values;
+
- Get heap contents as dynamic array slice of backing array
+
- void add(...);
+
- Add to heap
+
- void vadd(TypeInfo[] ti, void* argptr);
+
- Add to heap using va_arg inpurs
+
- void addTail(Value v);
+
- Add to heap
+
- Value takeHead();
+
- Remove and return first item (greatest item)
+
- void removeHead();
+
- Remove first item (greatest item)
+
- Value* lookup(size_t n);
+
- Return a pointer to the nth item
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal by values
+
- int opApply(int delegate(inout size_t n, inout Value x) dg);
+
- Foreach traversal by index-value pairs
+
- ArrayHeap dup;
+
- Duplicate array heap by duplicating backing array
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- int opEquals(ArrayHeap c);
+
- Test heap equality
+
- alias ArrayHeap ContainerType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- Aliases for container types
+
+
+
+
+mintl.arraylist
+
+- struct ArrayList(Value, bit ReadOnly = false, Alloc = GCAllocator)
+
- A list backed by an array. An ArrayList can also be used as
+a dynamic array with managed capacity. The backing array is resized
+when more space is required.
+Compile with version=MinTLNoIndexChecking to disable bounds checking.
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is GCAllocator.
+
+
+- Value[] data;
+
- Backing array
+
- mixin MListCat(ArrayList)
+
- Mixin list catenation.
+
- mixin MListAlgo(this,ArrayList)
+
- Mixin list algorithms.
+
- MListCommon(ArrayList)
+
- Implement common list members.
+
- size_t length
+
- Read/write property to return or set the length of the list.
+
- size_t capacity
+
- Read/write property for the minimum capacity of the backing array. The
+capacity is the maximum number of elements the array can hold without
+requiring a reallocation of the backing array.
+
- Value[] array;
+
- Get list contents as dynamic array slice of the backing array assuming
+the list is contiguous.
+
- ArrayListReverseIter!(Value) backwards();
+
- Backwards traversal for "foreach"
+
- ArrayList!(Value,true,Alloc) readonly;
+
- Property that returns a read-only view of the container.
+
- ArrayList!(Value,false,Alloc) readwrite;
+
- Property that returns a read-write view of the container.
+
- void sort(int delegate(Value* x, Value* y) cmp = null);
+
- Sort the list in increasing order as defined by the given comparison
+delegate. If no delegate is supplied the default comparison function of the
+Value type is used.
+
- alias ArrayList ContainerType;
+
- alias ArrayList SliceType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- alias ReadOnly isReadOnly;
+
- Aliases for container types
+
+
+
+
+mintl.deque
+
+- struct Deque(Value, bit ReadOnly = false, Alloc = GCAllocator)
+
- A double-ended queue backed by a circular block-allocated array
+Compile with version=MinTLNoIndexChecking to disable bounds checking.
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is GCAllocator.
+
+
+- mixin MListCat(Deque)
+
- Mixin list catenation.
+
- mixin MListAlgo(this,Deque)
+
- Mixin list algorithms.
+
- MListCommon(Deque)
+
- Implement common list members.
+
- size_t length;
+
- Return length of deque.
+
- DequeReverseIter!(Value) backwards();
+
- Backwards traversal for "foreach"
+
- Deque!(Value,true,Alloc) readonly;
+
- Property that returns a read-only view of the container.
+
- Deque!(Value,false,Alloc) readwrite;
+
- Property that returns a read-write view of the container.
+
- void sort(int delegate(Value* x, Value* y) cmp = null);
+
- Sort the list in increasing order as defined by the given comparison
+delegate. If no delegate is supplied the default comparison function of the
+Value type is used.
+
- alias Deque ContainerType;
+
- alias Deque SliceType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- alias ReadOnly isReadOnly;
+
- Aliases for container types
+
+
+
+
+mintl.hashaa
+
+- struct HashAA(Key,Value,bit ReadOnly = false, Alloc = GCAllocator)
+
- An associative array linked by insertion order.
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is GCAllocator.
+
+
+- void add(...);
+
- Add key-value pairs to array
+
- void vadd(TypeInfo[] ti, void* argptr);
+
- Add using va_arg inpurs
+
- static HashAA make(...)
+
- Consruct a HashAA using add(...)
+
- size_t length;
+
- Return number of items in the array.
+
- bool isEmpty
+
- Return true if array is empty
+
- Value* get(Key key, bit throwOnMiss = false);
+
- Return a pointer to the value stored at the key. If the key is not
+in the array then null is returned or if throwOnMiss is true an
+exception is thrown.
+
- Value* put(Key key)
+
- Return a pointer to the value stored at the key and insert the
+key with value Value.init if the key is not in the array.
+
- bool contains(Key key)
+
- Returns true if the array contains the key
+
- bool contains(Key key, out Value value)
+
- Returns true if the array contains the key and sets the out value if
+present.
+
- Value opIndex(Key key);
+
- Return item with given key. Returns the default missing value if not present.
+
- void opIndexAssign(Value val, Key key);
+
- Assign a value to the given key
+
- Value missing
+
- Read/write property for the value to use on indexing a key not in
+the array. Defaults to Value.init
+
- HashAA opSlice(Key a, Key b);
+
- Slice from item a to b (exclusive)
+
- HashAA opSlice(HashAA a, HashAA b);
+
- Slice from first key in a to last key in b
+
- HashAA head
+
- Return one-item slice of the head
+
- HashAA tail
+
- Return one-item slice of the tail
+
- void next(int n = 1, int end = 0);
+
- Move the head and tail to the next item. If n is negative move to
+the previous item. If end <= 0 move the head of the slice and if
+end >= 0 move the tail of the slice.
+
- void remove(Key key);
+
- Remove a key from array if present. The node used for key is reused in
+future insert actions.
+
- Value take(Key key);
+
- Remove a key from array if present and return value. Returns the
+default missing value if the key was not present.
+
- void remove(HashAA subarray);
+
- Remove a slice from array
+
- Value[] values;
+
- Get values as a dynamic array. The values are in insertion order.
+
- Key[] keys;
+
- Get keys as a dynamic array. The keys are in insertion order.
+
- void reserve(size_t n);
+
- Reserve a capacity for the array
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal by values
+
- int opApply(int delegate(inout Key key, inout Value x) dg);
+
- Foreach traversal by key-value pairs
+
- int opApply(int delegate(inout HashAA n) dg);
+
- Foreach traversal by one-item slices
+
- HashAA dup;
+
- Duplicate array
+
- void clear;
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- void trim;
+
- Remove references to extra nodes kept for reuse
+
- int opEquals(HashAA c);
+
- Test array equality
+
- HashAAReverseIter!(Key,Value) backwards();
+
- Backwards traversal for "foreach"
+
- HashAA rehash;
+
- Rehash array to be more efficient
+
- Value value
+
- Return value of a one-item slices
+
- Key key;
+
- Return key of a one-item slices
+
- HashAA!(Key,Value,true) readonly;
+
- Property that returns a read-only view of the container.
+
- HashAA!(Key,Value,false) readwrite;
+
- Property that returns a read-write view of the container.
+
- void sort(int delegate(Key* x, Key* y) cmp = null);
+
- Sort the HashAA in increasing order as defined by the given comparison
+delegate. If no delegate is supplied the default comparison function of the
+Key type is used. Future insertions are added in insertion order at
+the end of the traversal order.
+
- alias HashAA ContainerType;
+
- alias HashAA SliceType;
+
- alias Value ValueType;
+
- alias Key IndexType;
+
- alias ReadOnly isReadOnly;
+
- Aliases for container types
+
+
+
+
+mintl.list
+
+- struct List(Value, bit ReadOnly = false, Alloc = GCAllocator)
+
- A doubly-linked list.
+Compile with version=MinTLNoIndexChecking to disable bounds checking.
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is GCAllocator.
+
+
+- mixin MListCat(List)
+
- Mixin list catenation.
+
- mixin MListAlgo(this,List)
+
- Mixin list algorithms.
+
- MListCommon(List)
+
- Implement common list members.
+
- size_t length;
+
- Return length of list.
+
- void trim;
+
- Remove references to extra nodes kept for reuse
+
- ListReverseIter!(Value) backwards();
+
- Backwards traversal for "foreach"
+
- List!(Value,true,Alloc) readonly;
+
- Property that returns a read-only view of the container.
+
- List!(Value,false,Alloc) readwrite;
+
- Property that returns a read-write view of the container.
+
- void sort(int delegate(Value* x, Value* y) cmp = null);
+
- Sort the list in increasing order as defined by the given comparison
+delegate. If no delegate is supplied the default comparison function of the
+Value type is used.
+
- alias List ContainerType;
+
- alias List SliceType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- alias ReadOnly isReadOnly;
+
- Aliases for container types
+
+
+
+
+
+
+- struct CircularList(Value, bit ReadOnly = false, Alloc = GCAllocator)
+
- A circular doubly-linked list.
+Compile with version=MinTLNoIndexChecking to disable bounds checking.
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is GCAllocator.
+
+
+- mixin MListCat(CircularList)
+
- Mixin list catenation.
+
- mixin MListAlgo(this,CircularList)
+
- Mixin list algorithms.
+
- MListCommon(CircularList)
+
- Implement common list members.
+
- size_t length;
+
- Return length of list.
+
- List toList;
+
- Return the list as a non-circular List
+
- void rotate(int n = 1);
+
- Rotate the list by n steps (backwards if n is negative)
+
- CircularListReverseIter!(Value) backwards();
+
- Backwards traversal for "foreach"
+
- CircularList!(Value,true,Alloc) readonly;
+
- Property that returns a read-only view of the container.
+
- CircularList!(Value,false,Alloc) readwrite;
+
- Property that returns a read-write view of the container.
+
- alias CircularList ContainerType;
+
- alias List!(Value,Alloc) SliceType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- alias ReadOnly isReadOnly;
+
- Aliases for container types
+
+
+
+
+mintl.mem
+
+- void* mallocWithCheck(size_t s)
+
- Call std.c.stdlib.malloc and throw OutOfMemory if fails.
+
- void* callocWithCheck(size_t n, size_t s)
+
- Call std.c.stdlib.calloc and throw OutOfMemory if fails.
+
- void* reallocWithCheck(void* p, size_t s)
+
- Call std.c.stdlib.realloc and throw OutOfMemory if fails.
+
- void dfree(void* p)
+
- Call free.
+
- void* gcMalloc(size_t s)
+
- Call mallocWithCheck and register range with GC.
+
- void* gcCalloc(size_t n, size_t s)
+
- Call callocWithCheck and register range with GC.
+
- void* gcRealloc(void* p, size_t s)
+
- Call reallocWithCheck and register range with GC.
+
- void gcFree(void* p)
+
- Remove range and call free.
+
+
+
+- struct GCAllocator
+
- The default allocator that indicates the garbage collector
+should be used for memory management.
+
- struct Malloc
+
- An allocator that uses malloc for memory requests and registers
+blocks with the GC when requested by the container.
+
- struct MallocNoRoots
+
- An allocator that uses malloc for memory requests and ignores requests
+to register blocks with the GC. Use this allocator only when you know the
+container will not contain any roots.
+
+
+
+
+mintl.multiaa
+
+- struct MultiAA!(Key,Value, ImplType = HashAA!(Key,Value[]))
+
- An associative array which allows keys to be repeated.
+Adapted from a customizable container type mapping keys to Value[].
+
+
+- ImplType impl
+
- Read-write property holding the backing container
+
- void add(...);
+
- Add key-value pairs to the container
+
- void vadd(TypeInfo[] ti, void* argptr);
+
- Add using va_arg inpurs
+
- static MultiAA make(...)
+
- Consruct a MultiAA using add(...)
+
- void addItem(Key key, Value item);
+
- Add item to container.
+
- size_t length;
+
- Return number of items in the container.
+
- bool isEmpty
+
- Return true if container is empty.
+
- Value[] opIndex(Key key);
+
- Return the values for a given key.
+
- void remove(Key key, Value value);
+
- Remove an item from the container if present.
+
- void remove(Key key);
+
- Remove all the values with a given key if present.
+
- Key[] keys;
+
- Get keys as a dynamic array. Duplicates are removed.
+
- Value[][] values;
+
- Get values as a dynamic array.
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal of items in the container. If an item is repeated it
+is passed multiple times consecutively to the delegate.
+
- int opApply(int delegate(inout Key key, inout Value x) dg);
+
- Foreach traversal of items in the container. If an item is repeated it
+is passed multiple times consecutively to the delegate.
+
- MultiAA dup;
+
- Duplicate container
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- int opEquals(MultiAA c);
+
- Test container equality
+
- alias MultiAA ContainerType;
+
- alias Value ValueType;
+
- alias Key IndexType;
+
- alias ImplType AdaptType;
+
- const bit isReadOnly = ImplType.isReadOnly;
+
- Aliases for container types
+
+
+
+
- alias SortedMultiAA!(Key,Value)
+
- An alias for MultiAA!(Key,Value,SortedAA!(Key,Value[])) to implement a
+sorted multi-aa.
+
+
+
+mintl.queue
+
+- struct Queue!(Value, ImplType = Deque!(Value))
+
- A queue of items adapted from a customizable list container type. The
+default backing container is a Deque.
+
+
+- ImplType impl
+
- Read-write property holding the backing container.
+
- alias addTail put;
+
- Alias to add items to the tail of the queue.
+
- alias takeHead take;
+
- Alias to take items to the head of the queue.
+
- Value peek
+
- Return the head of the queue or Value.init if empty.
+
- mixin MListCat(Queue)
+
- Mixin list catenation.
+
- size_t length;
+
- Return length of queue.
+
- bool isEmpty
+
- Return true if container is empty
+
- Value opIndex(size_t n);
+
- Return nth item where the head is item 0.
+
- void opIndexAssign(Value val, size_t n);
+
- Assign to the nth item
+
- void addTail(Value v);
+
- Add to tail of queue
+
- void addTail(Queue v);
+
- Append v to tail of queue
+
- Value takeHead();
+
- Remove and return first item
+
- void removeHead();
+
- Remove first item
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal by values
+
- int opApply(int delegate(inout size_t n, inout Value x) dg);
+
- Foreach traversal by index-value pairs
+
- Queue dup;
+
- Duplicate queue.
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- int opEquals(Queue c);
+
- Test queue equality
+
- int opCmp(Queue c);
+
- Compare queues
+
- alias Queue ContainerType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- alias ImplType AdaptType;
+
- const bit isReadOnly = ImplType.isReadOnly;
+
- Aliases for container types
+
+
+
+
- alias ArrayQueue!(Value)
+
- An alias for Queue!(Value,ArrayList!(Value)) to adapt an ArrayList
+to the queue interface.
+
+
+
- alias PriorityQueue!(Value)
+
- An alias for Queue!(Value,ArrayHeap!(Value)) to adapt an ArrayHeap
+to the queue interface.
+
+
+
+
+mintl.set
+
+- struct Set!(Value, ImplType = HashAA!(Value,uint))
+
- A set of unique items adapted from a customizable container type
+mapping items to 0 or 1. The default backing container type is a
+builtin associative array.
+
+
+- ImplType impl
+
- Read-write property holding the backing container
+
- void add(...);
+
- Add items to set
+
- void vadd(TypeInfo[] ti, void* argptr);
+
- Add using va_arg inpurs
+
- static Set make(...)
+
- Consruct a Set using add(...)
+
- void addItem(Value item);
+
- Add item to set
+
- size_t length;
+
- Return number of items in the set.
+
- bool isEmpty
+
- Return true if set is empty
+
- bool opIndex(Value item);
+
- Return true if the item is in the set
+
- void remove(Value item);
+
- Remove an item from the set if present
+
- Value[] values;
+
- Get items as a dynamic set.
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal of items in the set
+
- Set dup;
+
- Duplicate set
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- int opEquals(Set c);
+
- Test set equality
+
- alias Set ContainerType;
+
- alias Value ValueType;
+
- alias ImplType AdaptType;
+
- const bit isReadOnly = ImplType.isReadOnly;
+
- Aliases for container types
+
+
+
+
- alias SortedSet!(Value)
+
- An alias for Set!(Value,SortedAA!(Value,uint)) to implement a sorted set.
+
+
+
- struct MultiSet!(Value, ImplType = HashAA!(uint,Value))
+
- A set which allows items to be repeated. Adapted from a customizable
+container type mapping items to repeat counts.
+
+
+- ImplType impl
+
- Read-write property holding the backing container
+
- void add(...);
+
- Add items to set
+
- void vadd(TypeInfo[] ti, void* argptr);
+
- Add using va_arg inpurs
+
- static MultiSet make(...)
+
- Consruct a MultiSet using add(...)
+
- void addItem(Value item);
+
- Add item to set
+
- size_t length;
+
- Return number of items in the set.
+
- bool isEmpty
+
- Return true if set is empty
+
- bool opIndex(Value item);
+
- Return true if the item is in the set
+
- void remove(Value item);
+
- Remove an item from the set if present
+
- Value[] values;
+
- Get items as a dynamic set. Duplicates are removed.
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal of items in the set. If an item is repeated it
+is passed multiple times consecutively to the delegate.
+
- MultiSet dup;
+
- Duplicate set
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- int opEquals(MultiSet c);
+
- Test set equality
+
- alias MultiSet ContainerType;
+
- alias Value ValueType;
+
- alias ImplType AdaptType;
+
- const bit isReadOnly = ImplType.isReadOnly;
+
- Aliases for container types
+
+
+
+
- alias SortedMultiSet!(Value)
+
- An alias for MultiSet!(Value,SortedAA!(Value,uint)) to implement a
+sorted multi-set.
+
+
+
+mintl.share
+The mintl.share module is publically imported into all container modules
+and stores shared defintions.
+
+- const bit ReadOnly = true;
+
- A named constant to improve the readability of code involving read-only
+containers. See the section on unmodifiable containers for examples.
+
- class IndexOutOfBoundsException : Exception
+
- Exception thrown when attempting to access an invalid index or key. Checks for invalid indices can be disabled using version=MinTLNoIndexChecking.
+
+
+
- template MListCatOperators(List)
+- Concatenation routines to be mixed into the list-like containers
+
+- void add(...);
+
- Add to list
+
- void vadd(TypeInfo[] ti, void* argptr);
+
- Add using va_arg inpurs
+
- static List make(...)
+
- Consruct a List using add(...)
+
- void addN(uint n, Value v)
+
- Add the value n times to the list
+
- void addBefore(List.SliceType sublist, Value[] v)
+
- Insert the values in the dynamic array v before sublist
+
- void addAfter(List.SliceType sublist, Value[] v)
+
- Insert the values in the dynamic array v after sublist
+
- List opCatAssign(Value v);
+
- Concatenation operator this ~= v
+
- List opCat(Value v);
+
- Concatenation operator this ~ v. copies this
+
- List opCat_r(Value v);
+
- Concatenation operator v ~ this. copies this
+
- List opCatAssign(List v);
+
- Concatenation operator this ~= v. copies v
+
- List opCat(List v);
+
- Concatenation operator this ~ v. copies both arguments
+
+
+- template MListAlgo(Container, alias list)
+- List algorithms to be mixed into the list-like containers
+
+- Container.SliceType opIn(Value v);
+
- Return a one-item slice of the first occurrence of v in the list.
+
- Container.SliceType find(int delegate(inout Value v) dg);
+
- Return a one-item slice of the first occurrence where dg is true.
+
- uint count(Value v);
+
- Return the number of time v appears in the list.
+
- void swap(Container v);
+
- Swap the contents of the list with v (assumes non-overlapping). Extra
+elements are ignored.
+
- void fill(Value v);
+
- Fill the container with v
+
- void copy(Container v);
+
- Copy the contents of v to this container. Extra elements are ignored.
+
+
+- MListCommon(Container)
+- Common list routines
+
+- bool isEmpty
+
- Return true if container is empty
+
- Value opIndex(size_t n);
+
- Return nth item where the head is item 0.
+
- void opIndexAssign(Value val, size_t n);
+
- Assign to the nth item
+
- Container.SliceType opSlice(size_t a, size_t b);
+
- Slice from item a to b (exclusive)
+
- Container.SliceType opSlice(Container.SliceType a, Container.SliceType b);
+
- Slice from head of a to tail of b
+
- Container.SliceType head
+
- Read-only property to get a one-item slice of the head.
+
- Container.SliceType tail
+
- Read-only property to get a one-item slice of the tail.
+
- Value[] values;
+
- Get list contents as dynamic array.
+
- Value value;
+
- Read/write property for the value of a one-item slice.
+
- void addTail(Value v);
+
- Add to tail of list
+
- void addTail(Container v);
+
- Copy v to tail of list
+
- void addHead(Value v);
+
- Add to head of list
+
- void addHead(Container v);
+
- Copy v to head of list
+
- Value takeTail();
+
- Remove and return last item
+
- Value takeHead();
+
- Remove and return first item
+
- void removeTail();
+
- Remove last item
+
- void removeHead();
+
- Remove first item
+
- void remove(Container.SliceType sublist);
+
- Remove sublist from list
+
- void addBefore(Container.SliceType subv, Container.SliceType v);
+
- Insert v before subv.
+
- void addAfter(Container.SliceType subv, Container.SliceType v);
+
- Insert v after subv.
+
- void next(int n = 1, int end = 0);
+
- Move the head and tail to the next item. If n is negative move to
+the previous item. If end <= 0 move the head of the slice and if
+end >= 0 move the tail of the slice.
+
- Value* lookup(size_t n);
+
- Return a pointer to the nth item
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal by values
+
- int opApply(int delegate(inout size_t n, inout Value x) dg);
+
- Foreach traversal by index-value pairs
+
- int opApply(int delegate(inout Container.SliceType n) dg);
+
- Foreach traversal by one-item slices
+
- Container reverse;
+
- Reverse list in-place.
+
- Container dup;
+
- Duplicate array list by duplicating backing array
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- int opEquals(Container c);
+
- Test list equality
+
- int opCmp(Container c);
+
- Compare lists
+
+
+
+
+mintl.slist
+
+- struct SList(Value, bit ReadOnly = false, Alloc = GCAllocator)
+
- A singly-linked list.
+Compile with version=MinTLNoIndexChecking to disable bounds checking.
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is GCAllocator.
+
+
+- mixin MListCat(SList)
+
- Mixin list catenation.
+
- size_t length;
+
- Return length of list.
+
- bool isEmpty
+
- Return true if container is empty
+
- SList tailList;
+
- Return the tail of the list as a slice
+
- Value opIndex(size_t n);
+
- Return nth item where the head is item 0.
+
- void opIndexAssign(Value val, size_t n);
+
- Assign to the nth item
+
- SList opSlice(size_t a, size_t b);
+
- Slice from item a to b (exclusive)
+
- SList opSlice(SList a, SList b);
+
- Slice from head of a to tail of b
+
- SList head
+
- Read-only property to get a one-item slice of the head.
+
- SList tail
+
- Read-only property to get a one-item slice of the tail.
+
- Value value
+
- Read/write property for the value of a one-item slice.
+
- Value[] values;
+
- Get list contents as dynamic array.
+
- void addTail(Value v);
+
- Add to tail of list
+
- void addTail(SList v);
+
- Append v to tail of list
+
- void addHead(Value v);
+
- Add to head of list
+
- void addHead(SList v);
+
- Prepend v to head of list
+
- Value takeHead();
+
- Remove and return first item
+
- void removeHead();
+
- Remove first item
+
- void addAfter(SList subv, SList v);
+
- Insert v after subv.
+
- void removeAfter(SList sublist, size_t n=1);
+
- Remove n items following sublist
+
- void removeBetween(SList a, SList b);
+
- Remove items after the tail of a to the head of b (exclusive)
+
- void next(int n = 1, int end = 0);
+
- Move the head and tail to the next item. If n is negative move to
+the previous item. If end <= 0 move the head of the slice and if
+end >= 0 move the tail of the slice.
+
- Value* lookup(size_t n);
+
- Return a pointer to the nth item
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal by values
+
- int opApply(int delegate(inout size_t n, inout Value x) dg);
+
- Foreach traversal by index-value pairs
+
- int opApply(int delegate(inout SList n) dg);
+
- Foreach traversal by one-item slices
+
- SList dup;
+
- Duplicate list
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- void trim;
+
- Remove references to extra nodes kept for reuse
+
- int opEquals(SList c);
+
- Test list equality
+
- int opCmp(SList c);
+
- Compare lists
+
- mixin MListAlgo(this,SList)
+
- Mixin list algorithms.
+
- SList!(Value,true,Alloc) readonly;
+
- Property that returns a read-only view of the container.
+
- SList!(Value,false,Alloc) readwrite;
+
- Property that returns a read-write view of the container.
+
- alias SList ContainerType;
+
- alias SList SliceType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- alias ReadOnly isReadOnly;
+
- Aliases for container types
+
+
+
+
+
+- struct CircularSList(Value, bit ReadOnly = false, Alloc = GCAllocator)
+
- A circular singly-linked list.
+Compile with version=MinTLNoIndexChecking to disable bounds checking.
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is GCAllocator.
+
+
+- mixin MListCat(CircularSList)
+
- Mixin list catenation.
+
- size_t length;
+
- Return length of list.
+
- bool isEmpty
+
- Return true if container is empty
+
- SList toSList;
+
- Return the list as a non-circular SList
+
- Value opIndex(size_t n);
+
- Return nth item where the head is item 0.
+
- void opIndexAssign(Value val, size_t n);
+
- Assign to the nth item
+
- SList opSlice(size_t a, size_t b);
+
- Slice from item a to b (exclusive)
+
- SList opSlice(SList a, SList b);
+
- Slice from head of a to tail of b
+
- SList head
+
- Read-only property to get a one-item slice of the head.
+
- SList tail
+
- Read-only property to get a one-item slice of the tail.
+
- Value value
+
- Read/write property for the value of a one-item slice.
+
- void addTail(Value v);
+
- Add to tail of list
+
- void addTail(CircularSList v);
+
- Append v to tail of list
+
- void addHead(Value v);
+
- Add to head of list
+
- void addHead(CircularSList v);
+
- Prepend v to head of list
+
- Value takeHead();
+
- Remove and return first item
+
- void removeHead();
+
- Remove first item
+
- void addAfter(SList subv, SList v);
+
- Insert v after subv.
+
- void removeAfter(SList sublist, size_t n=1);
+
- Remove n items following sublist
+
- void removeBetween(SList a, SList b);
+
- Remove items after the tail of a to the head of b (exclusive)
+
- void rotate(int n = 1);
+
- Rotate the list by n steps
+
- Value* lookup(size_t n);
+
- Return a pointer to the nth item
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal by values
+
- int opApply(int delegate(inout size_t n, inout Value x) dg);
+
- Foreach traversal by index-value pairs
+
- int opApply(int delegate(inout SList n) dg);
+
- Foreach traversal by one-item slices
+
- CircularSList dup;
+
- Duplicate list
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- int opEquals(CircularSList c);
+
- Test list equality
+
- int opCmp(CircularSList c);
+
- Compare lists
+
- mixin MListAlgo(this,CircularSList)
+
- Mixin list algorithms.
+
- CircularSList!(Value,true,Alloc) readonly;
+
- Property that returns a read-only view of the container.
+
- CircularSList!(Value,false,Alloc) readwrite;
+
- Property that returns a read-write view of the container.
+
- alias CircularAList ContainerType;
+
- alias SList!(Value,Alloc) SliceType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- alias ReadOnly isReadOnly;
+
- Aliases for container types
+
+
+
+
+mintl.sortedaa
+
+- class CompareFcnSetException: Exception;
+
- Exception thrown when trying to set the comparison function of
+a non-empty array or an array that already had the comparison function
+set.
+
+
+
+- struct SortedAA(Key, Value, bit ReadOnly = false, Alloc = GCAllocator)
+
- A sorted associative array
+The optional ReadOnly parameter disallows container modifications.
+The optional allocator customizes memory management. The default allocator
+is GCAllocator.
+
+
+- alias int delegate(Key* a, Key* b) CompareFcn;
+
- Signature of comparison functions
+
- void compareFcn(CompareFcn cmp);
+
- Set the comparison function
+
- void add(...);
+
- Add key-value pairs to array
+
- void vadd(TypeInfo[] ti, void* argptr);
+
- Add using va_arg inpurs
+
- static SortedAA make(...)
+
- Consruct a SortedAA using add(...)
+
- size_t length;
+
- Return number of items in the array.
+
- bool isEmpty
+
- Return true if array is empty
+
- Value* get(Key key, bit throwOnMiss = false);
+
- Return a pointer to the value stored at the key. If the key is not
+in the array then null is returned or if throwOnMiss is true an
+exception is thrown.
+
- Value* put(Key key)
+
- Return a pointer to the value stored at the key and insert the
+key with value Value.init if the key is not in the array.
+
- bool contains(Key key)
+
- Returns true if the array contains the key
+
- bool contains(Key key, out Value value)
+
- Returns true if the array contains the key and sets the out value if
+present.
+
- Value opIndex(Key key);
+
- Return item with given key. Returns the default missing value if not present.
+
- void opIndexAssign(Value val, Key key);
+
- Assign a value to the given key
+
- Value missing
+
- Read/write property for the value to use on indexing a key not in
+the array. Defaults to Value.init
+
- SortedAA head()
+
- Return one-item slice of the smallest item
+
- SortedAA tail()
+
- Return one-item slice of the greatest item
+
- void next(int n = 1, int end = 0);
+
- Move the head and tail to the next item. If n is negative move to
+the previous item. If end <= 0 move the head of the slice and if
+end >= 0 move the tail of the slice.
+
- SortedAA from(Key a);
+
- Return a one-item slice of the smallest item greater than or equal to a.
+
- SortedAA to(Key b);
+
- Return a one-item slice of the greatest item smaller than b.
+
- SortedAA opSlice(Key a, Key b);
+
- Slice from item a to b (exclusive).
+
- SortedAA opSlice(SortedAA a, SortedAA b);
+
- Slice from first key in a to last key in b.
+
- Value take(Key key);
+
- Remove a key from array if present and return value. Returns the
+default missing value if the key was not present.
+
- void remove(Key key);
+
- Remove a key from array if present.
+
- void remove(SortedAA subarray);
+
- Remove a slice from array.
+
- void trim;
+
- Remove references to extra nodes kept for reuse
+
- Value[] values;
+
- Get values as a dynamic array. The values are in order.
+
- Key[] keys;
+
- Get keys as a dynamic array. The keys are in order.
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal by values
+
- int opApply(int delegate(inout Key key, inout Value x) dg);
+
- Foreach traversal by key-value pairs
+
- int opApply(int delegate(inout SortedAA n) dg);
+
- Foreach traversal by one-item slices
+
- SortedAA dup;
+
- Duplicate array
+
- void clear()
+
- Clear contents. Only needed if a non-GCAllocator is used.
+
- int opEquals(SortedAA c);
+
- Test array equality
+
- SortedAAReverseIter!(Key,Value) backwards();
+
- Backwards traversal for "foreach"
+
- Value value;
+
- Return value of a one-item slices
+
- Key key;
+
- Return key of a one-item slices
+
- SortedAA!(Key,Value,true,Alloc) readonly;
+
- Property that returns a read-only view of the container.
+
- SortedAA!(Key,Value,false,Alloc) readwrite;
+
- Property that returns a read-write view of the container.
+
- alias SortedAA ContainerType;
+
- alias SortedAA SliceType;
+
- alias Value ValueType;
+
- alias Key IndexType;
+
- Aliases for container types
+
+
+
+
+mintl.stack
+
+- struct Stack!(Value, ImplType = Deque!(Value))
+
- A stack of items adapted from a customizable list container type. The
+default backing container is a Deque.
+
+
+- ImplType impl
+
- Read-write property holding the backing container.
+
- alias addTail push;
+
- Alias to add items to the tail of the stack.
+
- alias takeTail pop;
+
- Alias to take items from the tail of the stack.
+
- Value peek
+
- Return the top of the stack or Value.init if empty.
+
- mixin MListCat(Stack)
+
- Mixin list catenation.
+
- size_t length;
+
- Return length of stack.
+
- bool isEmpty
+
- Return true if container is empty
+
- Value opIndex(size_t n);
+
- Return nth item where the head is item 0.
+
- void opIndexAssign(Value val, size_t n);
+
- Assign to the nth item
+
- void addTail(Value v);
+
- Add to tail of stack
+
- void addTail(Stack v);
+
- Append v to tail of stack
+
- Value takeHead();
+
- Remove and return first item
+
- void removeHead();
+
- Remove first item
+
- int opApply(int delegate(inout Value x) dg);
+
- Foreach traversal by values
+
- int opApply(int delegate(inout size_t n, inout Value x) dg);
+
- Foreach traversal by index-value pairs
+
- Stack dup;
+
- Duplicate stack.
+
- int opEquals(Stack c);
+
- Test stack equality
+
- int opCmp(Stack c);
+
- Compare stacks
+
- alias Stack ContainerType;
+
- alias Value ValueType;
+
- alias size_t IndexType;
+
- alias ImplType AdaptType;
+
- const bit isReadOnly = ImplType.isReadOnly;
+
- Aliases for container types
+
+
+
+
- alias ArrayStack!(Value)
+
- An alias for Stack!(Value,ArrayList!(Value)) to adapt an ArrayList
+to the stack interface.
+
+
+
+
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/linux.mak
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/linux.mak Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,72 @@
+
+# To build libmintl.a type
+# make -f linux.mak DFLAGS=-g LIBNAME=libmintl_debug.a
+# or
+# make -f linux.mak DFLAGS=-release LIBNAME=libmintl.a
+# The libmintl.a and object files will be created in the source directory.
+
+# flags to use building unittest.exe
+DUNITFLAGS=-g -unittest -I.. -version=MinTLUnittest -version=MinTLVerboseUnittest
+
+# flags to use when building the mintl.lib library
+DLIBFLAGS=$(DFLAGS) -I..
+#DLIBFLAGS=-g -I..
+
+DMD=dmd
+
+#LIBNAME = libmintl.a
+
+targets : unittest
+
+mintl : $(LIBNAME)
+
+SRC = all.d \
+ array.d \
+ arraylist.d \
+ arrayheap.d \
+ deque.d \
+ hashaa.d \
+ list.d \
+ slist.d \
+ share.d \
+ adapter.d \
+ stack.d \
+ queue.d \
+ set.d \
+ multiaa.d \
+ mem.d \
+ sorting.d \
+ sortedaa.d
+
+OBJS = all.o \
+ array.o \
+ arraylist.o \
+ arrayheap.o \
+ deque.o \
+ hashaa.o \
+ list.o \
+ slist.o \
+ share.o \
+ adapter.o \
+ stack.o \
+ queue.o \
+ set.o \
+ multiaa.o \
+ mem.o \
+ sorting.o \
+ sortedaa.o
+
+$(LIBNAME) : $(OBJS) $(SRC)
+ ar -r $@ $(OBJS)
+
+clean:
+ rm *.o
+ rm $(LIBNAME)
+ rm unittest
+
+%.o : %.d
+ $(DMD) -c $(DLIBFLAGS) $< -of$@
+
+unittest : $(LIBNAME) $(OBJS) $(SRC)
+ $(DMD) $(DUNITFLAGS) unittest.d -ofunittest $(SRC)
+
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/list.d
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/list.d Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,1420 @@
+/** \file list.d
+ * \brief A doubly-linked list and a circular doubly-linked list.
+ *
+ * Written by Ben Hinkle and released to the public domain, as
+ * explained at http://creativecommons.org/licenses/publicdomain
+ * Email comments and bug reports to ben.hinkle@gmail.com
+ *
+ * revision 2.7.1
+ */
+
+module mintl.list;
+
+private import mintl.share; // for ~ and ~=
+private import mintl.sorting;
+import mintl.mem;
+
+// shared data structure between List and CircularList
+private struct DNode(Value) {
+ DNode* next, prev;
+ Value data;
+ Value* sortLookup(){return &data;}
+}
+
+/** Template for member functions common to List and CircularList */
+template MCommonList(alias tail_, Container ) {
+
+ /** Test if a container is empty. */
+ bool isEmpty() {
+ return head_ is null;
+ }
+
+ /** Get the length of list. The computation can be O(n) but the
+ * result is cached and the actively updated until another list
+ * of unknown length is concatenated or removed.
+ */
+ size_t length() {
+ if (length_ == 0 && head_) {
+ Container.Node* n = head_;
+ length_ = 1;
+ Container.Node* end = tail_;
+ while (n !is end) {
+ length_++;
+ n = n.next;
+ }
+ }
+ return length_;
+ }
+
+ // helper function to check if the index is legal
+ void boundsCheck(size_t n) {
+ version (MinTLNoIndexChecking) {
+ } else {
+ if (!(n == 0 && this.head_) &&
+ (n >= length_ && n >= this.length)) {
+ throw new IndexOutOfBoundsException();
+ }
+ }
+ }
+
+ // Internal function to get the nth item of the list.
+ package Container.Node* getNode(size_t n) {
+ boundsCheck(n);
+ Container.Node* v;
+ if (n <= length_/2) {
+ v = head_;
+ while (n--) {
+ v = v.next;
+ }
+ } else {
+ n = length_-n-1;
+ v = tail_;
+ while (n--) {
+ v = v.prev;
+ }
+ }
+ return v;
+ }
+
+ /** Get the nth item in the list from head. The operation is O(N(n))
+ * where N(x) is the distance from x to either end of list.
+ * Indexing out of bounds throws an IndexOutOfBoundsException unless
+ * version=MinTLNoIndexChecking is set.
+ */
+ Container.ValueType opIndex(size_t n) {
+ return getNode(n).data;
+ }
+
+ static if (!Container.isReadOnly) {
+
+ /** Get a pointer to the nth item in the list from head. The
+ * operation is O(N(n)) where N(x) is the distance from x to either
+ * end of list. Indexing out of bounds throws an
+ * IndexOutOfBoundsException unless version=MinTLNoIndexChecking is
+ * set.
+ */
+ Container.ValueType* lookup(size_t n) {
+ return &getNode(n).data;
+ }
+
+ /** Set the nth item in the list from head. The operation is O(N(n))
+ * where N(x) is the distance from x to either end of list.
+ * Indexing out of bounds throws an IndexOutOfBoundsException unless
+ * version=MinTLNoIndexChecking is set.
+ */
+ void opIndexAssign(Container.ValueType val, size_t n) {
+ getNode(n).data = val;
+ }
+
+ /** Reverse a list in-place. The operation is O(n) where n is
+ * length of the list.
+ */
+ Container reverse() {
+ if (this.isEmpty)
+ return *this;
+ Node* i = head_;
+ Node* j = tail_;
+ TypeInfo ti = typeid(Container.ValueType);
+ while (i !is j && i.next !is j) {
+ ti.swap(&i.data,&j.data);
+ i = i.next;
+ j = j.prev;
+ }
+ ti.swap(&i.data,&j.data);
+ return *this;
+ }
+
+ } // !isReadOnly
+
+ /** Copies the list contents to an array */
+ Container.ValueType[] values() {
+ Container.ValueType[] buffer = new Container.ValueType[this.length];
+ foreach(size_t n, Container.ValueType val; *this) {
+ buffer[n] = val;
+ }
+ return buffer;
+ }
+
+ /** Test for equality of two lists. The operation is O(n) where n
+ * is length of the list.
+ */
+ int opEquals(Container c) {
+ if (length_ && c.length_ && length_ != c.length_)
+ return 0;
+ Container.Node* i = head_;
+ Container.Node* j = c.head_;
+ Container.Node* t = tail_;
+ Container.Node* ct = c.tail_;
+ TypeInfo ti = typeid(Container.ValueType);
+ while (i !is null && j !is null) {
+ if (!ti.equals(&i.data,&j.data))
+ return 0;
+ if (i !is t && j !is ct)
+ return 1;
+ i = i.next;
+ j = j.next;
+ }
+ return (i is null && j is null);
+ }
+
+ /** Compare two lists. */
+ int opCmp(Container c) {
+ Container.Node* i = head_;
+ Container.Node* j = c.head_;
+ Container.Node* t = tail_;
+ Container.Node* ct = c.tail_;
+ TypeInfo ti = typeid(Container.ValueType);
+ while (i !is null && j !is null) {
+ int cmp = ti.compare(&i.data,&j.data);
+ if (cmp)
+ return cmp;
+ if (i !is t && j !is ct)
+ return 0;
+ i = i.next;
+ j = j.next;
+ }
+ if (i is null && j is null)
+ return 0;
+ else
+ return (i is null) ? -1 : 1;
+ }
+
+ /** Create a sub-list from index a to b (exclusive). The operation is
+ * O(max(N(a),N(b))) where N(x) is distance from x to either end of
+ * the target list.
+ */
+ Container.SliceType opSlice(size_t a, size_t b) {
+ Container.SliceType res;
+ res.length_ = b-a;
+ if (res.length_ > 0) {
+ res.head_ = getNode(a);
+ if (this.length_ - b > b-a){
+ Container.Node* v = res.head_;
+ b = b-a-1;
+ while (b--)
+ v = v.next;
+ res.tail_ = v;
+ } else {
+ res.tail_ = getNode(b-1);
+ }
+ }
+ return res;
+ }
+
+ /** Create a sub-list from the head of a to the tail of b (inclusive). */
+ Container.SliceType opSlice(Container.SliceType a, Container.SliceType b) {
+ if (a.isEmpty)
+ return b;
+ if (b.isEmpty)
+ return a;
+ Container.SliceType res;
+ Container.Node* i = a.head_;
+ res.head_ = i;
+ res.tail_ = b.tail_;
+ res.length_ = 0; // flag indicating unknown length
+ return res;
+ }
+
+ /** Iterates over the list from head to tail calling delegate to
+ * perform an action. The value is passed to the delegate.
+ */
+ int opApplyNoKeyStep(int delegate(inout Container.ValueType x) dg, int step = 1){
+ int dg2(inout size_t count, inout Container.ValueType val) {
+ return dg(val);
+ }
+ return opApplyWithKeyStep(&dg2,step);
+ }
+
+ /** Iterates over the list from head to tail calling delegate to
+ * perform an action. The index from 0 and the value are passed
+ * to the delegate.
+ */
+ int opApplyWithKeyStep(int delegate(inout size_t n, inout Container.ValueType x) dg,
+ int step = 1){
+ Container.Node* i = step>0 ? head_ : tail_;
+ Container.Node* end = step>0 ? tail_ : head_;
+ int res = 0;
+ size_t n = step>0 ? 0 : this.length-1;
+ while (i !is null) {
+ res = dg(n, i.data);
+ if (res || i is end) break;
+ n += step;
+ i = step>0 ? i.next : i.prev;
+ }
+ return res;
+ }
+
+ /** Iterates over the list from head to tail calling delegate to
+ * perform an action. A one-item sub-list is passed to the delegate.
+ */
+ int opApplyIterStep(int delegate(inout Container.SliceType n) dg, int step = 1){
+ Container.Node* i = step>0 ? head_ : tail_;
+ Container.Node* end = step>0 ? tail_ : head_;
+ int res = 0;
+ Container.SliceType n;
+ n.length_ = 1;
+ while (i !is null) {
+ n.head_ = n.tail_ = i;
+ res = dg(n);
+ if (res || i is end) break;
+ i = step>0 ? i.next : i.prev;
+ }
+ return res;
+ }
+
+}
+
+/** \class List
+ * \brief A doubly-linked list.
+ *
+ * A List!(Value) is a linked list of data of type Value. A list is
+ * similar to a dynamic array except accessing an element in the
+ * middle of the list is O(n) and appending to the front or back is
+ * O(1). Any operation that is not constant-time will explicitly have
+ * the performance behavior documented.
+ *
+ * The optional ReadOnly parameter List!(Value,ReadOnly) forbids
+ * operations that modify the container. The readonly() property returns
+ * a ReadOnly view of the container.
+ *
+ * The optional allocator parameter List!(Value,false,Allocator) is used
+ * to allocate and free memory. The GC is the default allocator.
+ */
+struct List(Value, bit ReadOnly = false, Alloc = GCAllocator) {
+
+ alias List ContainerType;
+ alias List SliceType;
+ alias Value ValueType;
+ alias size_t IndexType;
+ alias Value SortType;
+ alias DNode!(Value) Node;
+ alias ReadOnly isReadOnly;
+
+ const int NodeAllocationBlockSize = 10; // allocate 10 nodes at a time
+
+ /* length 0 means length is unknown. An empty list is indicated by
+ * a null head. The tail can be non-null in order to maintain the
+ * cached nodes.
+ */
+ invariant {
+ assert( length_ == 0 || head_ !is null );
+ }
+
+ // private bug private {
+ size_t length_;
+ Node* head_;
+ Node* tail_;
+ // }
+
+ /** Get a ReadOnly view of the container */
+ .List!(Value, true, Alloc) readonly() {
+ .List!(Value, true, Alloc) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ /** Get a read-write view of the container */
+ .List!(Value, false, Alloc) readwrite() {
+ .List!(Value, false, Alloc) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ static if (!ReadOnly) {
+
+ /** Appends an item to the tail of the list. If the target list is
+ * a sub-list call addAfter instead of addTail to insert an item
+ * after a sub-list.
+ */
+ void addTail(Value v) {
+ if (head_ is null && tail_ !is null) {
+ // empty list but with cache available
+ head_ = tail_;
+ tail_.data = v;
+ length_ = 1;
+ } else if (tail_ is null || tail_.next is null) {
+ if (head_ is null || head_.prev is null) {
+ // no available nodes so allocate a new one
+ List val;
+ val.head_ = val.tail_ = newNode();
+ val.length_ = 1;
+ val.head_.data = v;
+ addTail(val);
+ } else {
+ // grab available node from front
+ Node* t = head_.prev;
+ if (t.prev !is null) t.prev.next = head_;
+ head_.prev = t.prev;
+ t.prev = tail_;
+ t.next = null;
+ tail_.next = t;
+ tail_ = t;
+ tail_.data = v;
+ if (length_) length_++;
+ }
+ } else {
+ // grab available node from end
+ tail_.next.prev = tail_;
+ tail_ = tail_.next;
+ tail_.data = v;
+ if (length_) length_++;
+ }
+ }
+
+ /** Appends a list to the tail of the target list. If the target
+ * list is a sub-list call addAfter instead of addTail to insert
+ * another list after a sub-list.
+ */
+ void addTail(List v) {
+ if (v.isEmpty)
+ return;
+ if (tail_ !is null)
+ tail_.next = v.head_;
+ v.head_.prev = tail_;
+ if (this.isEmpty)
+ length_ = v.length_;
+ else
+ length_ = increaseLength(length_, v.length_);
+ tail_ = v.tail_;
+ if (head_ is null)
+ head_ = v.head_;
+ }
+
+ mixin MListCatOperators!(List);
+
+ /** Clear all contents. */
+ void clear() {
+ static if (is(Alloc == GCAllocator)) {
+ } else {
+ trim();
+ Node* i = head_;
+ while (i !is null) {
+ Node* next = i.next;
+ Alloc.gcFree(i);
+ i = next;
+ }
+ }
+ *this = List.init;
+ }
+
+ /** Set the value of one-item slice (more generally the head value). */
+ void value(Value newValue) {
+ head_.data = newValue;
+ }
+
+ // Helper function for take and remove
+ private Node* takeTailHelper() {
+ if (this.isEmpty)
+ throw new IndexOutOfBoundsException();
+ Node* v = tail_;
+ if (head_ && head_ is tail_) {
+ head_ = null;
+ } else {
+ tail_ = tail_.prev;
+ }
+ return v;
+ }
+
+ /** Removes and returns the tail item of the list. The node that
+ * contained the item may be reused in future additions to the
+ * list. To prevent the node from being reused call trim or
+ * call remove with a sublist containing the last item. If
+ * the target list is empty an IndexOutOfBoundsException is thrown
+ * unless version=MinTLNoIndexChecking is set.
+ */
+ Value takeTail() {
+ Node* v = takeTailHelper();
+ Value data = v.data;
+ v.data = Value.init;
+ if (length_) length_--;
+ return data;
+ }
+
+ /** Removes the tail item of the list. */
+ void removeTail() {
+ Node* v = takeTailHelper();
+ v.data = Value.init;
+ if (length_) length_--;
+ }
+
+ /** Prepends an item to the head of the target list. If the target
+ * list is a sub-list call addBefore instead of addHead to insert an
+ * item before a sub-list.
+ */
+ void addHead(Value v) {
+ if (head_ is null && tail_ !is null) {
+ // empty list but with cache available
+ head_ = tail_;
+ tail_.data = v;
+ length_ = 1;
+ } else if (head_ is null || head_.prev is null) {
+ if (tail_ is null || tail_.next is null) {
+ // no available nodes so allocate a new one
+ List val;
+ val.head_ = val.tail_ = newNode();
+ val.length_ = 1;
+ val.head_.data = v;
+ addHead(val);
+ } else {
+ // grab available node from end
+ Node* t = tail_.next;
+ if (t.next !is null) t.next.prev = tail_;
+ tail_.next = t.next;
+ t.next = head_;
+ t.prev = null;
+ head_.prev = t;
+ head_ = t;
+ head_.data = v;
+ if (length_) length_++;
+ }
+ } else {
+ // grab available node from front
+ head_.prev.next = head_;
+ head_ = head_.prev;
+ head_.data = v;
+ if (length_) length_++;
+ }
+ }
+
+ /** Prepends a list to the head of the target list. If the target
+ * list is a sub-list call addBefore instead of addHead to insert a
+ * list before a sub-list.
+ */
+ void addHead(List v) {
+ if (v.isEmpty)
+ return;
+ if (head_ !is null)
+ head_.prev = v.tail_;
+ v.tail_.next = head_;
+ if (this.isEmpty)
+ length_ = v.length_;
+ else
+ length_ = increaseLength(length_, v.length_);
+ head_ = v.head_;
+ if (tail_ is null)
+ tail_ = v.tail_;
+ }
+
+ // Helper function for take and remove
+ private Node* takeHeadHelper() {
+ if (this.isEmpty)
+ throw new IndexOutOfBoundsException();
+ Node* v = head_;
+ if (head_ && head_ is tail_) {
+ head_ = null;
+ } else {
+ head_ = head_.next;
+ }
+ return v;
+ }
+
+ /** Removes and returns the head item of the list. The node that
+ * contained the item may be reused in future additions to the
+ * list. If the target list is empty an IndexOutOfBoundsException is
+ * thrown unless version=MinTLNoIndexChecking is set.
+ */
+ Value takeHead() {
+ Node* v = takeHeadHelper();
+ Value data = v.data;
+ v.data = Value.init;
+ if (length_) length_--;
+ return data;
+ }
+
+ /** Removes the head item of the list. */
+ void removeHead() {
+ Node* v = takeHeadHelper();
+ v.data = Value.init;
+ if (length_) length_--;
+ }
+
+ /** Insert a list before a sub-list. */
+ void addBefore(List subv, List v) {
+ if (v.isEmpty)
+ return;
+ if (subv.isEmpty)
+ throw new IndexOutOfBoundsException();
+ Node* t = subv.head_;
+ if (t.prev !is null) {
+ t.prev.next = v.head_;
+ }
+ v.head_.prev = t.prev;
+ v.tail_.next = t;
+ t.prev = v.tail_;
+ if (t is head_)
+ head_ = v.head_;
+ length_ = increaseLength(length_, v.length_);
+ }
+
+ /** Insert a list after a sub-list. */
+ void addAfter(List subv, List v) {
+ if (v.isEmpty)
+ return;
+ if (subv.isEmpty)
+ throw new IndexOutOfBoundsException();
+ Node* t = subv.tail_;
+ if (t.next !is null) {
+ t.next.prev = v.tail_;
+ }
+ v.tail_.next = t.next;
+ v.head_.prev = t;
+ t.next = v.head_;
+ if (t is tail_)
+ tail_ = v.tail_;
+ length_ = increaseLength(length_, v.length_);
+ }
+
+
+ /** Removes a sub-list from the list entirely. */
+ void remove(List sublist) {
+ if (sublist.isEmpty)
+ return;
+ Node* h = sublist.head_;
+ Node* t = sublist.tail_;
+ if (h is head_ && t is tail_) {
+ head_ = tail_ = null;
+ length_ = 0;
+ return;
+ }
+ Node* hp = h.prev;
+ Node* tn = t.next;
+ if (hp !is null)
+ hp.next = tn;
+ if (tn !is null)
+ tn.prev = hp;
+ if (h is head_)
+ head_ = tn;
+ if (t is tail_)
+ tail_ = hp;
+ length_ = decreaseLength(length_, sublist.length_);
+ }
+
+ /** Removes an item from the list if present. */
+ void remove(size_t index) {
+ List item = opSlice(index, index+1);
+ remove(item);
+ }
+
+ /** Removes an item and return the value if any. */
+ Value take(size_t index) {
+ List item = opSlice(index, index+1);
+ remove(item);
+ Value val = item[0];
+ item.clear();
+ return val;
+ }
+
+ /** Trims off extra nodes that are not actively being used by the
+ * list but are available for recyling for future add operations.
+ * This function should be called after calling remove and
+ * there are other list or pointer references to the removed item.
+ */
+ void trim() {
+ if (!this.isEmpty) {
+ Node* i;
+ if (tail_.next) {
+ i = tail_.next;
+ i.prev = null;
+ tail_.next = null;
+ static if (is(Alloc == GCAllocator)) {
+ } else {
+ while (i !is null) {
+ Node* next = i.next;
+ Alloc.gcFree(i);
+ i = next;
+ }
+ }
+ }
+ if (head_.prev) {
+ i = head_.prev;
+ i.next = null;
+ head_.prev = null;
+ static if (is(Alloc == GCAllocator)) {
+ } else {
+ while (i !is null) {
+ Node* prev = i.prev;
+ Alloc.gcFree(i);
+ i = prev;
+ }
+ }
+ }
+ }
+ }
+
+ } // !ReadOnly
+
+ /** Duplicates a list. The operation is O(n) where n is length of
+ * the list.
+ */
+ List dup() {
+ .List!(Value,false,Alloc) res;
+ foreach(ValueType val; *this) {
+ res ~= val;
+ }
+ static if (ReadOnly) {
+ return res.readonly;
+ } else {
+ return res;
+ }
+ }
+
+ /** Move a sub-list towards the head or tail by n items. If n is
+ * negative the sub-list moves towards the head. A positive end is
+ * the tail, negative the head and 0 is both. By default moves to
+ * the next item.
+ */
+ void next(int n = 1, int end = 0) {
+ if (length_)
+ length_ -= n*end;
+ while (n-- > 0) {
+ if (end <= 0)
+ head_ = head_.next;
+ if (end >= 0)
+ tail_ = tail_.next;
+ }
+ while (++n < 0) {
+ if (end <= 0)
+ head_ = head_.prev;
+ if (end >= 0)
+ tail_ = tail_.prev;
+ }
+ }
+
+ /** Get the length of list. The computation can be O(n) but the
+ * result is cached and the actively updated until another list
+ * of unknown length is concatenated.
+ */
+ size_t length() {
+ if (length_ == 0 && !this.isEmpty) {
+ Node* n = head_;
+ length_ = 1;
+ while (n !is tail_) {
+ length_++;
+ n = n.next;
+ }
+ }
+ return length_;
+ }
+
+ /** Create a one-item slice of the head. */
+ List head() {
+ List res;
+ res.length_ = head_? 1 : 0;
+ res.head_ = res.tail_ = head_;
+ return res;
+ }
+
+ /** Create a one-item slice of the tail. */
+ List tail() {
+ List res;
+ res.length_ = tail_? 1 : 0;
+ res.head_ = res.tail_ = tail_;
+ return res;
+ }
+
+ /** Get the value of one-item slice (more generally the head value).
+ * Useful for expressions like x.tail.value or x.head.value. */
+ Value value() {
+ return head_.data;
+ }
+
+ /** Iterate backwards over the list (from tail to head). This
+ * should be called as the iteration parameter in a
+ * foreach statement
+ */
+ ListReverseIter!(Value,ReadOnly,Alloc) backwards() {
+ ListReverseIter!(Value,ReadOnly,Alloc) res;
+ res.list = this;
+ return res;
+ }
+
+ /** Helper functions for opApply */
+ mixin MOpApplyImpl!(ContainerType);
+ alias opApplyNoKey opApply;
+ alias opApplyWithKey opApply;
+ alias opApplyIter opApply;
+
+ private Node* newNode() {
+ static if (is(Alloc == GCAllocator)) {
+ // allocate a block of nodes and return pointer to first one
+ Node[] block = new Node[NodeAllocationBlockSize];
+ for (int k=1; kadd and remove functions and
+ * slices can be moved forward around the list indefinitely. A CircularList
+ * also has a smaller memory footprint since it requires only one
+ * pointer for the head instead of two pointers for a tail and head.
+ *
+ * The optional ReadOnly parameter CircularList!(Value,ReadOnly) forbids
+ * operations that modify the container. The readonly() property returns
+ * a ReadOnly view of the container.
+ *
+ * The optional allocator parameter CircularList!(Value,false,Allocator) is used
+ * to allocate and free memory. The GC is the default allocator.
+ */
+struct CircularList(Value, bit ReadOnly = false, Alloc = GCAllocator) {
+
+ alias CircularList ContainerType;
+ alias List!(Value,ReadOnly,Alloc) SliceType;
+ alias Value ValueType;
+ alias size_t IndexType;
+ alias DNode!(Value) Node;
+ alias ReadOnly isReadOnly;
+
+ private {
+ size_t length_;
+ Node* head_;
+ }
+
+ /* length 0 means length is unknown. */
+ invariant {
+ assert( length_ == 0 || head_ !is null );
+ }
+
+ /** Return the circular list as a non-circular List.
+ * \return the list as a List
+ */
+ SliceType toList() {
+ SliceType res;
+ if (this.isEmpty)
+ return res;
+ res.privateMake(head_,head_.prev,length_);
+ // res.tail_ =
+ // res.head_ = head_;
+ // res.length_ = length_;
+ return res;
+ }
+
+ /** Get a ReadOnly view of the container */
+ .CircularList!(Value, true, Alloc) readonly() {
+ .CircularList!(Value, true, Alloc) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ /** Get a read-write view of the container */
+ .CircularList!(Value, false, Alloc) readwrite() {
+ .CircularList!(Value, false, Alloc) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ private Node* tail_() {
+ if (this.isEmpty) return null;
+ return head_.prev;
+ }
+
+ static if (!ReadOnly) {
+
+ /** Rotate the list by n items. If n is negative the rotation is
+ * reversed.
+ */
+ void rotate(int n = 1) {
+ if (n >= 0) {
+ while (n-- > 0)
+ head_ = head_.next;
+ } else {
+ while (++n < 0)
+ head_ = head_.prev;
+ }
+ }
+
+ /** Clear all contents. */
+ void clear() {
+ static if (is(Alloc == GCAllocator)) {
+ } else {
+ Node* i = head_;
+ if (i !is null)
+ i.prev.next = null;
+ while (i !is null) {
+ Node* next = i.next;
+ Alloc.gcFree(i);
+ i = next;
+ }
+ }
+ *this = CircularList.init;
+ }
+ /** Appends an item to the tail of the list. If the target list is
+ * a sub-list call addAfter instead of addTail to insert an item
+ * after a sub-list.
+ */
+ void addTail(Value v) {
+ Node* n = newNode();
+ n.data = v;
+ addNode(n);
+ }
+
+ private void link(Node* a, Node* b) {
+ a.next = b;
+ b.prev = a;
+ }
+
+ /** Adds a node before head. */
+ private void addNode(Node* n) {
+ if (this.isEmpty) {
+ link(n,n);
+ head_ = n;
+ length_ = 1;
+ } else {
+ link(tail_,n);
+ link(n,head_);
+ if (length_) length_++;
+ }
+ }
+
+ /** Appends a list to the tail of the target list. If the target
+ * list is a sub-list call addAfter instead of addTail to insert
+ * another list after a sub-list.
+ */
+ void addTail(CircularList v) {
+ addHead(v);
+ }
+
+ mixin MListCatOperators!(CircularList);
+
+ // Helper function for take and remove
+ private Node* takeTailHelper() {
+ if (this.isEmpty)
+ throw new IndexOutOfBoundsException();
+ Node* v = tail_;
+ if (head_ && head_ is tail_) {
+ head_ = null;
+ } else {
+ link(v.prev,v.next);
+ }
+ return v;
+ }
+
+ /** Removes and returns the tail item of the list. The node that
+ * contained the item may be reused in future additions to the
+ * list. To prevent the node from being reused call trim or
+ * call remove with a sublist containing the last item. If
+ * the target list is empty an IndexOutOfBoundsException is thrown
+ * unless version=MinTLNoIndexChecking is set.
+ */
+ Value takeTail() {
+ Node* v = takeTailHelper();
+ Value data = v.data;
+ freeNode(v);
+ if (length_) length_--;
+ return data;
+ }
+
+ /** Removes the tail item of the list. */
+ void removeTail() {
+ Node* v = takeTailHelper();
+ if (length_) length_--;
+ freeNode(v);
+ }
+
+ /** Prepends an item to the head of the target list. If the target
+ * list is a sub-list call addBefore instead of addHead to insert an
+ * item before a sub-list.
+ */
+ void addHead(Value v) {
+ Node* n = new Node;
+ n.data = v;
+ addNode(n);
+ head_ = n;
+ }
+
+ /** Prepends a list to the head of the target list. If the target
+ * list is a sub-list call addBefore instead of addHead to insert a
+ * list before a sub-list.
+ */
+ void addHead(CircularList v) {
+ if (v.isEmpty)
+ return;
+ if (this.isEmpty) {
+ *this = v;
+ return;
+ }
+ Node* vt = v.tail_;
+ link(tail_,v.head_);
+ link(vt,head_);
+ head_ = v.head_;
+ length_ = increaseLength(length_, v.length_);
+ }
+
+ // Helper function for take and remove
+ private Node* takeHeadHelper() {
+ if (this.isEmpty)
+ throw new IndexOutOfBoundsException();
+ Node* v = head_;
+ if (head_ && head_ is tail_) {
+ head_ = null;
+ } else {
+ link(v.prev,v.next);
+ }
+ return v;
+ }
+
+ /** Removes and returns the head item of the list. The node that
+ * contained the item may be reused in future additions to the
+ * list. To prevent the node from being reused call trim or
+ * call remove with a sublist containing the last item. If
+ * the target list is empty an IndexOutOfBoundsException is thrown
+ * unless version=MinTLNoIndexChecking is set.
+ */
+ Value takeHead() {
+ Node* v = takeHeadHelper();
+ Value data = v.data;
+ if (length_) length_--;
+ freeNode(v);
+ return data;
+ }
+
+ /** Removes the head item of the list. */
+ void removeHead() {
+ Node* v = takeHeadHelper();
+ if (length_) length_--;
+ freeNode(v);
+ }
+
+ /** Insert a list before a sub-list. */
+ void addBefore(SliceType subv, SliceType v) {
+ if (v.isEmpty)
+ return;
+ if (subv.isEmpty)
+ throw new IndexOutOfBoundsException();
+ Node* t = subv.head_;
+ link(t.prev,v.head_);
+ link(v.tail_,t);
+ if (t is head_)
+ head_ = v.head_;
+ length_ = increaseLength(length_, v.length_);
+ }
+
+ /** Insert a list after a sub-list. */
+ void addAfter(SliceType subv, SliceType v) {
+ if (v.isEmpty)
+ return;
+ if (subv.isEmpty)
+ throw new IndexOutOfBoundsException();
+ Node* t = subv.tail_;
+ link(v.tail_,t.next);
+ link(t,v.head_);
+ length_ = increaseLength(length_, v.length_);
+ }
+
+
+ /** Removes a sub-list from the list entirely. */
+ void remove(SliceType sublist) {
+ if (sublist.isEmpty)
+ return;
+ Node* h = sublist.head_;
+ Node* t = sublist.tail_;
+ if (h is head_ && t is tail_) {
+ head_ = null;
+ length_ = 0;
+ return;
+ }
+ if (h is head_)
+ head_ = t.next;
+ link(h.prev,t.next);
+ h.prev = null;
+ t.next = null;
+ length_ = decreaseLength(length_, sublist.length_);
+ }
+
+ /** Removes an item if present. */
+ void remove(size_t index) {
+ remove(opSlice(index, index+1));
+ }
+
+ /** Removes an item from the list and return its value, if present. */
+ Value take(size_t index) {
+ SliceType item = opSlice(index, index+1);
+ remove(item);
+ Value val = item[0];
+ item.clear();
+ return val;
+ }
+
+ } // !ReadOnly
+
+ /** Duplicates a list. The operation is O(n) where n is length of
+ * the list.
+ */
+ CircularList dup() {
+ .CircularList!(Value,false,Alloc) res;
+ foreach(ValueType val; *this) {
+ res ~= val;
+ }
+ static if (ReadOnly) {
+ return res.readonly;
+ } else {
+ return res;
+ }
+ }
+
+ /** Create a one-item slice of the head. */
+ SliceType head() {
+ SliceType res;
+ if (this.isEmpty) return res;
+ res.head_ = res.tail_ = head_;
+ res.length_ = 1;
+ return res;
+ }
+
+ /** Create a one-item slice of the tail. */
+ SliceType tail() {
+ SliceType res;
+ if (this.isEmpty) return res;
+ res.head_ = res.tail_ = head_.prev;
+ res.length_ = 1;
+ return res;
+ }
+
+ /** Move a sub-list towards the tail by n items. */
+ void next(int n = 1, int end = 0) {
+ if (length_)
+ length_ -= n*end;
+ while (n-- > 0) {
+ if (end <= 0)
+ head_ = head_.next;
+ }
+ }
+
+ /** Iterate backwards over the list (from tail to head). This
+ * should be called as the iteration parameter in a
+ * foreach statement
+ */
+ CircularListReverseIter!(Value,ReadOnly,Alloc) backwards() {
+ CircularListReverseIter!(Value,ReadOnly,Alloc) res;
+ res.list = this;
+ return res;
+ }
+
+ /**
+ * Helper functions for opApply with/without keys and
+ * forward/backward order
+ */
+ mixin MOpApplyImpl!(ContainerType);
+ alias opApplyNoKey opApply;
+ alias opApplyWithKey opApply;
+ alias opApplyIter opApply;
+
+ private Node* newNode() {
+ static if (is(Alloc == GCAllocator)) {
+ return new Node;
+ } else {
+ Node* p = cast(Node*)Alloc.gcMalloc(Node.sizeof);
+ *p = Node.init;
+ return p;
+ }
+ }
+
+ private void freeNode(Node* n) {
+ static if (is(Alloc == GCAllocator)) {
+ } else {
+ Alloc.gcFree(n);
+ }
+ }
+
+ CircularList getThis(){return *this;}
+ mixin MListAlgo!(CircularList, getThis);
+
+ mixin MCommonList!(tail_, CircularList );
+}
+
+// helper functions for adjusting length cache
+private size_t increaseLength(size_t len, size_t x) {
+ return x ? (len? len+x : 0) : 0;
+}
+private size_t decreaseLength(size_t len, size_t x) {
+ return x ? (len? len-x : 0) : 0;
+}
+
+// helper structure for backwards()
+struct CircularListReverseIter(Value,bit ReadOnly,Alloc) {
+ mixin MReverseImpl!(List!(Value,ReadOnly,Alloc),
+ CircularList!(Value,ReadOnly,Alloc));
+}
+
+//version = MinTLVerboseUnittest;
+//version = MinTLUnittest;
+
+version (MinTLUnittest) {
+ private import std.random;
+ unittest {
+ version (MinTLVerboseUnittest)
+ printf("starting mintl.list unittest\n");
+
+ List!(int) x;
+ x ~= 3;
+ x ~= 4;
+ assert( x[0] == 3 );
+ assert( x[1] == 4 );
+ assert( x.length == 2 );
+ List!(int) x2 = List!(int).make(3,4);
+ assert( x == x2 );
+
+ List!(int) catt;
+ catt = List!(int).make(1,2,3) ~ List!(int).make(4,5,6);
+ assert( catt == List!(int).make(1,2,3,4,5,6) );
+
+ List!(int,false,MallocNoRoots) xm;
+ xm ~= 3;
+ xm ~= 4;
+ assert( xm[0] == 3 );
+ assert( xm[1] == 4 );
+ assert( xm.length == 2 );
+ xm.clear();
+ assert( xm.isEmpty );
+
+ List!(real) x2s;
+ x2s.add(cast(real)3,cast(real)4);
+ assert( x2s[0] == 3 );
+ assert( x2s[1] == 4 );
+
+ // test addHead
+ List!(int) y;
+ y.addHead(4);
+ y.addHead(3);
+
+ // test ==
+ assert( x == y );
+ List!(int) w = x.dup;
+ w ~= 5;
+ assert( x != w);
+
+ // test remove/take
+ assert( w.takeTail() == 5 );
+ size_t wlen = w.length;
+ w.addTail(6);
+ w.removeTail();
+ assert( w.length() == wlen );
+ assert( w == x );
+ w.trim();
+ w ~= 5;
+
+ // test reverse lists
+ List!(int) z = y.dup;
+ z.reverse();
+ assert( z[0] == 4 );
+ assert( z[1] == 3 );
+
+ // test foreach iteration
+ foreach(size_t n, inout int val; z) {
+ val = n*10;
+ }
+ assert( z[0] == 0 );
+ assert( z[1] == 10 );
+ foreach(size_t n, int val; y.backwards()) {
+ assert(x[n] == val);
+ }
+ int n = 0;
+ foreach(List!(int) itr; y) {
+ assert(itr[0] == y[n++]);
+ }
+
+ // test slicing
+ List!(int) v = w[1..3];
+ assert( v.length == 2 );
+ assert( v[0] == 4 );
+ assert( v[1] == 5 );
+
+ // test readonly
+ List!(int,ReadOnly) rv = v.readonly;
+ assert( rv.length == 2 );
+ assert( rv[0] == 4 );
+ assert( rv[1] == 5 );
+ assert( rv.head == rv[0 .. 1] );
+ assert( rv.tail == rv[1 .. 2] );
+
+ // test algorithms
+ assert( v.opIn(5) == v.tail );
+ assert( v.count(5) == 1 );
+ assert( v.find(delegate int(inout int v){return v == 5;}) == v.tail );
+ v[0 .. 1].swap(v[1..2]);
+ assert( v[0] == 5 );
+ assert( v[1] == 4 );
+ v.fill(10);
+ assert( v[0] == 10 );
+ assert( v[1] == 10 );
+ List!(int) vsub;
+ vsub.add(4,5);
+ v.copy(vsub);
+ assert( v[0] == 4 );
+ assert( v[1] == 5 );
+
+ // test another node type
+ List!(char[]) str;
+ str.add("hello","world");
+ assert( str[str.length-1] == "world" );
+
+ // test sub-list spanning
+ List!(int) tmp;
+ int[10] tmp2;
+ tmp2[3] = 100;
+ tmp2[8] = 200;
+ foreach(int xx;tmp2)
+ tmp ~= xx;
+ List!(int) a,b,c;
+ a = tmp[3..5];
+ b = tmp[7..9];
+ c = tmp[a..b];
+ assert( c.length == 6 );
+ assert( c[0] == 100 );
+ assert( c[5] == 200 );
+
+ // CircularList testing
+
+ CircularList!(int) cx;
+ cx ~= 3;
+ cx ~= 4;
+ assert( cx[0] == 3 );
+ assert( cx[1] == 4 );
+ assert( cx.length == 2 );
+
+ CircularList!(int) cx2;
+ cx2.add(3,4);
+ assert( cx == cx2 );
+
+ // test addHead
+ CircularList!(int) cy;
+ cy.addHead(4);
+ cy.addHead(3);
+
+ // test ==
+ assert( cx == cy );
+ CircularList!(int) cw = cx.dup;
+ cw ~= 5;
+ assert( cx != cw);
+
+ // test remove
+ assert( cw.takeTail() == 5 );
+ wlen = cw.length;
+ cw.addTail(6);
+ cw.removeTail();
+ assert( cw.length() == wlen );
+ assert( cw == cx );
+ cw ~= 5;
+
+ // test reverse lists
+ CircularList!(int) cz = cy.dup;
+ cz.reverse();
+ assert( cz[0] == 4 );
+ assert( cz[1] == 3 );
+
+ // test foreach iteration
+ foreach(size_t n, inout int val; cz) {
+ val = n*10;
+ }
+ assert( cz[0] == 0 );
+ assert( cz[1] == 10 );
+ foreach(size_t n, int val; cy.backwards()) {
+ assert(cx[n] == val);
+ }
+ n = 0;
+ foreach(List!(int) itr; cy) {
+ assert(itr[0] == cy[n++]);
+ }
+
+ // test slicing
+ List!(int) cv = w[1..3];
+ assert( cv.length == 2 );
+ assert( cv[0] == 4 );
+ assert( cv[1] == 5 );
+
+ // test algorithms
+ assert( cv.opIn(5) == v.tail );
+ assert( cv.count(5) == 1 );
+
+ // test another node type
+ CircularList!(char[]) cstr;
+ cstr.add("hello","world");
+ assert( cstr[cstr.length-1] == "world" );
+
+ // test sub-list spanning
+ CircularList!(int,false,MallocNoRoots) ctmp;
+ tmp2[3] = 100;
+ tmp2[8] = 200;
+ foreach(int xx;tmp2)
+ ctmp ~= xx;
+ List!(int,false,MallocNoRoots) ca,cb,cc;
+ ca = ctmp[3..5];
+ cb = ctmp[7..9];
+ cc = ctmp[ca..cb];
+ assert( cc.length == 6 );
+ assert( cc[0] == 100 );
+ assert( cc[5] == 200 );
+ ctmp.clear();
+ assert( ctmp.isEmpty );
+
+ // test simple sorting
+ List!(int) s1,s12;
+ s1.add(40,300,-20,100,400,200);
+ s12 = s1.dup;
+ s1.sort();
+ List!(int) s2 = List!(int).make(-20,40,100,200,300,400);
+ //List!(int) s2 = s2.make(-20,40,100,200,300,400);
+ assert( s1 == s2 );
+ // sort a slice in-place
+ s12[1..4].sort();
+ s2.clear();
+ s2.add(40,-20,100,300,400,200);
+ assert( s12 == s2 );
+
+ // test a large sort with default order
+ List!(double) s3;
+ for (int k=0;k<1000;k++) {
+ s3 ~= 1.0*rand()/100000.0 - 500000.0;
+ }
+ List!(double) s4 = s3.dup;
+ s3.sort();
+ for (int k=0;k<999;k++) {
+ assert( s3[k] <= s3[k+1] );
+ }
+ // test a large sort with custom order
+ int cmp(double*x,double*y){return *x>*y?-1:*x==*y?0:1;}
+ s4.sort(&cmp);
+ for (int k=0;k<999;k++) {
+ assert( s4[k] >= s4[k+1] );
+ }
+
+ version (MinTLVerboseUnittest)
+ printf("finished mintl.list unittest\n");
+ }
+}
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/locks.html
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/locks.html Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,490 @@
+ Synchronization Locks Library for D
+
+Synchronization Locks for D
+Locks is a library of synchronization constructs for the D
+programming language based on the concurrent locks library
+by Doug Lea.
+For more info about D see DigitalMars D home page. The
+library can be downloaded
+here
+or as part of
+MinTL.
+For more information about the Java library see
+
+JSR-166. For an initial port see
+ dsource.
+
+
+This library is in the public domain.
+Portions written by Ben Hinkle, 2004, portions ported from code
+written by Doug Lea.
+Email comments and bug reports to ben.hinkle@gmail.com
+
+
+
Overview
+
+The D language has builtin support for defining critical sections
+using the synchronized statement but does not include
+POSIX synchronization constructs like locks and condition variables.
+The purpose of the Locks library is to extend the builtin D
+capabilities to support not only POSIX constructs but also support
+latches, barriers and exchangers. Concurrent containers like queues,
+stacks and associative arrays are in the MinTL library in the
+package mintl.concurrent. When using concurrent algorithms
+be careful to use the volatile statement to ensure data
+is properly updated in all the threads.
+
+
+The primary interface of the Locks library is the Lock interface. It
+defines two methods, lock and unlock, that aquire
+and release the lock. In general the Lock interface makes no
+guarentee that a thread can lock a lock that it already
+owns. The ReentrantLock class, which implements
+Lock, does guarantee that the thread that hold the lock can
+call lock without blocking. If a thread calls lock
+and the lock is held by another thread then the calling thread is
+parked until the lock is released. The tryLock functions
+attempts to acquire the lock immediately or within a specified time interval.
+For example a typical
+class X that uses a ReentrantLock to control access
+to function m uses try-finally blocks to insure the lock is
+released before the function returns:
+
+
+ class X {
+ private ReentrantLock lock;
+ // ...
+ this() {
+ lock = new ReentrantLock;
+ }
+ void m() {
+ lock.lock(); // block until lock is available
+ try {
+ // ... method body
+ } finally {
+ lock.unlock()
+ }
+ }
+ }
+
+A ScopedLock can simplify the code around managing locks.
+The class X could instead use a ScopedLock
+in m:
+
+ class X {
+ private ReentrantLock lock;
+ // ...
+ this() {
+ lock = new ReentrantLock;
+ }
+ void m() {
+ auto ScopedLock slock = new ScopedLock(lock);
+ // ... method body
+ }
+ }
+
+
+The only difference between the two implementations is that the
+ScopedLock, as written, will allocate memory from the GC each
+time it is called.
+
+
+The Condition interface defines a condition variable for a given lock.
+A condition variable allows two or more threads to hand-off ownership
+of the lock atomically by calling wait and notify.
+If a thread owns the lock and calls wait
+on a condition variable then the thread releases the lock and
+blocks until notified by the condition variable.
+Once notified the thread attempts to acquire the lock and once successful
+continues execution. The wait function accepts timeout values to stop
+blocking after a certain amount of time. A thread that fails the timeout
+still must reacquire the lock before proceeding. A typical use of condition
+variables is to signal when an event has happened.
+The function Lock.newCondition creates and returns a Condition
+instance.
+For example, the
+condition below signals when the data variable has been set:
+
+ int data;
+ Thread getter, setter;
+ ReentrantLock lock = new ReentrantLock;
+ Condition is_ready = lock.newCondition;
+ setter = new Thread(
+ delegate int() {
+ lock.lock();
+ try {
+ data = 10;
+ is_ready.notify();
+ } finally {
+ lock.unlock();
+ }
+ return 0;
+ });
+ getter = new Thread(
+ delegate int() {
+ lock.lock();
+ try {
+ is_ready.wait();
+ printf("%d\n",data);
+ } finally {
+ lock.unlock();
+ }
+ return 0;
+ });
+ getter.start();
+ setter.start();
+
+
+
+To start several threads and have them wait until a signal from a
+coordinating thread use a CountDownLatch with a count of
+1. For example,
+
+ CountDownLatch go = new CountDownLatch(1);
+ Thread[4] t;
+ for (int i=0; i < 4; i++) {
+ t[i] = new Thread(
+ delegate int() {
+ go.wait(); // wait for signal from main thread
+ // ... do something interesting ...
+ return 0;
+ });
+ t[i].start();
+ }
+ go.countDown(); // let worker threads go
+
+Conversely to signal a coordinating thread that the worker threads
+are finished have each worker thread decrement another
+CountDownLatch:
+
+ CountDownLatch go = new CountDownLatch(1);
+ CountDownLatch allDone = new CountDownLatch(4);
+ Thread[4] t;
+ for (int i=0; i < 4; i++) {
+ t[i] = new Thread(
+ delegate int() {
+ go.wait(); // wait for signal from main thread
+ // ... do something interesting ...
+ allDone.countDown();
+ return 0;
+ });
+ t[i].start();
+ }
+ go.countDown(); // let worker threads go
+ allDone.wait(); // wait for all workers to finish
+
+
+
+A CyclicBarrier is similar to a CountDownLatch
+except the cyclic barrier is used without a controlling thread.
+A thread that reaches the barrier waits until the barrier count
+is exhausted before continuing. Once the barrier is tripped it
+optionally runs a function and resets to zero. Continuing the
+example from the previous paragraph the worker threads might need
+to rendezvous at a certain point mid-way through their task:
+
+ CountDownLatch go = new CountDownLatch(1);
+ CountDownLatch allDone = new CountDownLatch(4);
+ CyclicBarrier barrier = new CyclicBarrier(4);
+ Thread[4] t;
+ for (int i=0; i < 4; i++) {
+ t[i] = new Thread(
+ delegate int() {
+ go.wait(); // wait for signal from main thread
+ // ... do something interesting ...
+ barrier.wait(); // wait for all workers to get to barrier
+ // ... do something else interesting ...
+ allDone.countDown();
+ return 0;
+ });
+ t[i].start();
+ }
+ go.countDown(); // let worker threads go
+ allDone.wait(); // wait for all workers to finish
+
+
+
+A Semaphore maintains a given number of permits. When a
+thread acquires a permit the semaphore decremements the number of
+available permits and when a thread releases the permit (any thread
+can release the permit) the semaphore increments the number of
+available permits. Semaphores don't have a concept of threads
+owning permits - it only gives out and recieves permits atomically.
+A typical use case for semaphores is to manage access by multiple
+threads to a fixed collection of objects.
+
+
API Reference
+This section lists the public structs and functions in the library without
+detailed explanation. For more information see the documentation before
+the function or class in the source file.
+The API is organized by module:
+
+- locks.condition
+
- locks.countdown
+
- locks.exchanger
+
- locks.lock
+
- locks.platformutils
+
- locks.readwritelock
+
- locks.reentrantlock
+
- locks.semaphore
+
- locks.timeunit
+
+
+
+
+locks.condition
+
+- interface Condition
+
- A condition variable
+
+
+- void wait()
+
- Cause current thread to wait until notified
+
- long waitNanos(long nanosTimeout)
+
- Cause current thread to wait until notified or time expires
+
- bool wait(long time, TimeUnit unit)
+
- Cause current thread to wait until notified or time expires
+
- void notify()
+
- Wake up one waiting thread
+
- void notifyAll()
+
- Wake up all waiting threads
+
+
+
+
+locks.countdown
+
+- class CountDownLatch
+
- Allow one or more threads to wait for a set of other threads.
+
+
+- this(int count)
+
- Construct the latch with the given count before releasing
+
- void wait()
+
- Causes the current thread to wait until the count reaches zero
+
- void wait(long timeout, TimeUnit unit)
+
- Causes the current thread to wait until the count reaches zero or time expires
+
- void countDown()
+
- Decrement count
+
- long count
+
- Get the current count
+
- char[] toString
+
- Return a string summary of the latch
+
+
+
+
+locks.cyclicbarrier
+
+- class CyclicBarrier
+
- Allow a fixed group of threads to wait for each other
+
+
+- this(int parties, int delegate() barrierAction = null)
+
- Construct the barrier with given number of parties and concluding action
+
- int parties
+
- Return number of parties for this barrier
+
- int wait()
+
- Causes the current thread to wait for all parties to reach the barrier
+
- int wait(long timeout, TimeUnit unit)
+
- Causes the current thread to wait only for the specified time
+
- bool isBroken()
+
- Returns true if the barrier has been broken
+
- void reset()
+
- Break the barrier for waiting parties and reset to initial state
+
- int getNumberWaiting
+
- Get the current number of waiting parties
+
+
+
+
+locks.exchanger
+
+- class Exchanger(Value)
+
- Allow two threads to safely exchange values.
+
+
+- this()
+
- Construct the exchanger
+
- Value exchange(Value v)
+
- Offer v for exchange and wait for response
+
- Value exchange(Value v, long timeout, TimeUnit unit)
+
- Offer v for exchange and wait for response with possible timeout
+
+
+
+
+locks.lock
+
+- interface Lock
+
- The interface for all lock implementations.
+
+
+- void lock()
+
- Acquires the lock
+
- bool tryLock()
+
- Acquires the lock only if it is free at the time of invocation
+
- bool tryLock(long time, TimeUnit unit)
+
- Acquires the lock if it is free within the given waiting time
+
- void unlock()
+
- Releases the lock
+
- Condition newCondition
+
- Returns a new Condition instance that is bound to this lock instance
+
+
+
+- auto final class ScopedLock
+
- An auto class for aquiring and releasing a lock in a scope
+
+
+- this(Lock lock)
+
- Initializes the ScopedLock and acquires the supplied lock
+
- ~this()
+
- Release the lock
+
+
+
+
+locks.platformutils
+
+- bit compareAndSet32(void* mem, void* expect, void* update)
+
- Compare the 32 bit value expect with the value at *mem and if equal
+set to update and return true. This assumes a pointer is 32 bits.
+
- bit compareAndSet32(void* mem, int expect, int update)
+
- Convenience overload for compareAndSet32 when the data are integers
+instead of pointers
+
- bit compareAndSet64(void* mem, void* expect, void* update)
+
- Compare the 64 bit value at *expect with the value at *mem and if equal
+set to *update and return true.
+
- int atomicAdd32(int* val, int x);
+
- Atomically add x to *val and return previous value of *val
+
- int atomicExchange32(int* val, int x);
+
- Atomically store x to *val and return previous value of *val
+
- void atomicInc32(int* val);
+
- Atomically increment *val
+
- void atomicDec32(int* val);
+
- Atomically decrement *val
+
- long currentTimeMillis()
+
- Return the current system time in milliseconds
+
- long currentTimeNanos()
+
- Return the current system time in nanoseconds
+
- void sleepNanos(long duration)
+
- Sleep the current thread for the specified duration in nanoseconds
+
+
+
+locks.readwritelock
+
+- interface ReadWriteLock
+
- A pair of read-write locks
+
+
+- Lock readLock()
+
- Return the read lock
+
- Lock writeLock()
+
- Return the write lock
+
+
+
+
+- class ReentrantReadWriteLock : ReadWriteLock
+
- A pair of reentrant read-write locks
+
+
+- this(bool fair = false)
+
- Construct the lock with specified fairness policy
+
- Lock readLock()
+
- Return the read lock
+
- Lock writeLock()
+
- Return the write lock
+
+
+
+
+
+locks.reentrantlock
+
+- class ReentrantLock : Lock
+
- A reentrant mutual exclusive lock with condition variables
+
+
+- this(bool fair = false)
+
- Construct the lock with specified fairness policy
+
- void lock()
+
- Acquires the lock
+
- bool tryLock()
+
- Acquires the lock only if it is free at the time of invocation
+
- bool tryLock(long time, TimeUnit unit)
+
- Acquires the lock if it is free within the given waiting time
+
- void unlock()
+
- Releases the lock
+
- Condition newCondition
+
- Returns a new Condition instance that is bound to this lock instance
+
- int getHoldCount()
+
- Get the number of holds on this lock by the current thread
+
- bool isHeldByCurrentThread()
+
- Query if the lock is held by the current thread
+
- bool isLocked()
+
- Query if the lock is held by any thread
+
- bool isFair()
+
- Query if the lock is fair
+
- char[] toString()
+
- return a string representation of the lock
+
+
+
+
+
+locks.semaphore
+
+- class Semaphore
+
- A counting semaphore for maintaining a set of permits
+
+
+- this(int permits, bool fair = false)
+
- Construct the semaphore with the given number of permits and fairness policy
+
- void acquire(int permits = 1)
+
- Acquires n permits, blocking until all are available
+
- bool tryAcquire(int permits = 1)
+
- Acquires n permit from this semaphore only if they are immediately available
+
- bool tryAcquire(long timeout, TimeUnit unit, int permits = 1)
+
- Attempt acquiring n permits within the specified time interval
+
- void release(int permits = 1)
+
- Release n permits
+
- int availablePermits
+
- Get the current number of available permits
+
- bool isFair()
+
- return true if the semaphore is fair
+
- char[] toString
+
- Return a string summary of the semaphore
+
+
+
+
+
+locks.timeunit
+
+ - enum TimeUnit
+
- Time units common in synchronization
+
+ - NanoSeconds = 0
+
- MicroSeconds
+
- MilliSeconds
+
- Seconds
+
+
+
- long convert(long duration, TimeUnit fromUnit, TimeUnit toUnit);
+
- Convert the given time duration in the given unit to this unit.
+
- long toNanos(long duration, TimeUnit fromUnit);
+
- Convert to nanoseconds.
+
- long toMicros(long duration, TimeUnit fromUnit);
+
- Convert to microseconds.
+
- long toMillis(long duration, TimeUnit fromUnit);
+
- Convert to milliseconds.
+
- long toSeconds(long duration, TimeUnit fromUnit);
+
- Convert to seconds.
+
+
+
+
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/mem.d
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/mem.d Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,129 @@
+/** \file mem.d
+ * \brief Allocators for custom container memory management
+ *
+ * Written by Ben Hinkle and released to the public domain, as
+ * explained at http://creativecommons.org/licenses/publicdomain
+ * Email comments and bug reports to ben.hinkle@gmail.com
+ *
+ * version 1.0
+ */
+
+module mintl.mem;
+
+private {
+ import tango.stdc.stdlib;
+ import tango.core.Memory : GC;
+ import tango.core.Exception : onOutOfMemoryError;
+}
+
+/** An Allocator is a type containing 8 symbols malloc, calloc,
+ * realloc, free and the corresponding GC-aware versions gcMalloc,
+ * gcCalloc, gcRealloc and gcFree. Containers will call the GC-aware
+ * functions on blocks that may hold roots and otherwise will call the
+ * regular functions. Allocators are expected to throw OutOfMemory if
+ * the allocation fails. Be aware than when using an allocator with
+ * a container one must call the container clear() function
+ * to free the memory.
+ *
+ * The two predefined allocators Malloc and MallocNoRoots use
+ * std.c.stdlib.malloc to perform allocations. The MallocNoRoots
+ * ignores any requests by the container to register roots with the
+ * GC. The MallocNoRoots allocator should only be used with containers
+ * that the user knows will never contain any roots (e.g. ArrayList!(int))
+ */
+
+/** Malloc and throw OutOfMemory if fails. */
+void* mallocWithCheck(size_t s) {
+ void* p = malloc(s);
+ if (!p)
+ onOutOfMemoryError();
+ return p;
+}
+
+/** Calloc and throw OutOfMemory if fails. */
+void* callocWithCheck(size_t n, size_t s) {
+ void* p = calloc(n,s);
+ if (!p)
+ onOutOfMemoryError();
+ return p;
+}
+
+/** Realloc and throw OutOfMemory if fails. */
+void* reallocWithCheck(void*p, size_t s) {
+ p = realloc(p,s);
+ if (!p)
+ onOutOfMemoryError();
+ return p;
+}
+
+/** Free pointer. */
+void dfree(void*p) {
+ free(p);
+}
+
+/** Malloc and register the range with GC. */
+void* gcMalloc(size_t s) {
+ void* p = mallocWithCheck(s);
+ GC.addRange(p,s);
+ return p;
+}
+
+/** Calloc and register the range with GC. */
+void* gcCalloc(size_t n, size_t s) {
+ void* p = callocWithCheck(n,s);
+ GC.addRange(p,n*s);
+ return p;
+}
+
+/** Realloc and register the range with GC. */
+void* gcRealloc(void* p, size_t s) {
+ if (p)
+ GC.removeRange(p);
+ p = reallocWithCheck(p,s);
+ GC.addRange(p,s);
+ return p;
+}
+
+/** Deregister the range with GC and free. */
+void gcFree(void* p) {
+ if (p)
+ GC.removeRange(p);
+ free(p);
+}
+
+// Default Allocator
+struct GCAllocator{
+ alias void malloc;
+ alias void calloc;
+ alias void realloc;
+ alias void free;
+ alias void gcMalloc;
+ alias void gcCalloc;
+ alias void gcRealloc;
+ alias void gcFree;
+}
+
+// An allocator that uses malloc
+struct Malloc {
+ alias mallocWithCheck malloc;
+ alias callocWithCheck calloc;
+ alias reallocWithCheck realloc;
+ alias dfree free;
+ alias .gcMalloc gcMalloc;
+ alias .gcCalloc gcCalloc;
+ alias .gcRealloc gcRealloc;
+ alias .gcFree gcFree;
+}
+
+// An allocator that uses malloc and assumes allocations have no roots
+struct MallocNoRoots {
+ alias mallocWithCheck malloc;
+ alias callocWithCheck calloc;
+ alias reallocWithCheck realloc;
+ alias dfree free;
+ alias mallocWithCheck gcMalloc;
+ alias callocWithCheck gcCalloc;
+ alias reallocWithCheck gcRealloc;
+ alias dfree gcFree;
+}
+
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/multiaa.d
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/multiaa.d Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,191 @@
+/** \file multiaa.d
+ * \brief An associative array that allows multiple values per key.
+ *
+ * Written by Ben Hinkle and released to the public domain, as
+ * explained at http://creativecommons.org/licenses/publicdomain
+ * The red-black tree code is by Thomas Niemann.
+ * Email comments and bug reports to ben.hinkle@gmail.com
+ *
+ * revision 1.2
+ */
+
+module mintl.multiaa;
+
+private import mintl.share;
+private import mintl.adapter;
+private import mintl.sortedaa;
+private import mintl.hashaa;
+private import std.stdarg;
+private import std.boxer;
+
+//version = WithBox;
+
+/** An associative array of items with duplicate keys.
+ * By default the backing container is a builtin associative array.
+ */
+struct MultiAA(Key, Value, ImplType = HashAA!(Key,Value[])) {
+
+ alias MultiAA ContainerType;
+ alias Value ValueType;
+ alias Key IndexType;
+ alias ImplType AdaptType;
+ const bit isReadOnly = ImplType.isReadOnly;
+
+ ImplType impl;
+
+ size_t length() {
+ size_t total = 0;
+ foreach(Value[] val; impl) {
+ total += val.length;
+ }
+ return total;
+ }
+ int opEquals(MultiAA c) { return impl == c.impl; }
+ static if (!ImplType.isReadOnly) {
+ void remove(Key key) {
+ impl.remove(key);
+ }
+ void remove(Key key, Value val) {
+ Value[]* vals = impl.get(key);
+ if (vals) {
+ size_t k;
+ Value[] x = *vals;
+ for(k = 0; kaddTail repeatedly.
+ */
+ void add(...) {
+ vadd(_arguments,_argptr);
+ }
+ void vadd(TypeInfo[] arguments, void* argptr) {
+ for (int k=0;ktail
+ * property.
+ * Indexing out of bounds throws an IndexOutOfBoundsException unless
+ * version=MinTLNoIndexChecking is set.
+ */
+ Container.ValueType opIndex(size_t n) {
+ return getNode(n).data;
+ }
+
+ static if (!Container.isReadOnly) {
+
+ /** Get a pointer to the nth item in the list from head. The
+ * operation is O(n). To efficiently access the tail of the list
+ * use the tail property. Indexing out of bounds throws an
+ * IndexOutOfBoundsException unless version=MinTLNoIndexChecking is
+ * set.
+ */
+ Container.ValueType* lookup(size_t n) {
+ return &getNode(n).data;
+ }
+
+ /** Set the nth item in the list from head. The operation is O(n).
+ * To efficiently access the tail of the list use the tail
+ * property.
+ * Indexing out of bounds throws an IndexOutOfBoundsException unless
+ * version=MinTLNoIndexChecking is set.
+ */
+ void opIndexAssign(Container.ValueType val, size_t n) {
+ getNode(n).data = val;
+ }
+
+ } // !ReadOnly
+
+ /** Iterates over the list from head to tail calling delegate to
+ * perform an action. The value is passed to the delegate.
+ */
+ int opApplyNoKey(int delegate(inout Container.ValueType x) dg){
+ int dg2(inout size_t count, inout Container.ValueType val) {
+ return dg(val);
+ }
+ return opApplyWithKey(&dg2);
+ }
+
+ /** Iterates over the list from head to tail calling delegate to
+ * perform an action. The index from 0 and the value are passed
+ * to the delegate.
+ */
+ int opApplyWithKey(int delegate(inout size_t n, inout Container.ValueType x) dg){
+ Container.Node* i = head_;
+ Container.Node* end = tail_;
+ int res = 0;
+ size_t n = 0;
+ while (i !is null) {
+ res = dg(n, i.data);
+ if (res || i is end) break;
+ n++;
+ i = i.next;
+ }
+ return res;
+ }
+
+ /** Iterates over the list from head to tail calling delegate to
+ * perform an action. A one-item sub-list is passed to the delegate.
+ */
+ int opApplyIter(int delegate(inout Container.SliceType n) dg){
+ Container.Node* i = head_;
+ Container.Node* end = tail_;
+ int res = 0;
+ Container.SliceType n;
+ while (i !is null) {
+ n.head_ = n.tail_ = i;
+ res = dg(n);
+ if (res || i is end) break;
+ i = i.next;
+ }
+ return res;
+ }
+
+ /** Test for equality of two lists. The operation is O(n) where n
+ * is length of the list.
+ */
+ int opEquals(Container c) {
+ Container.Node* i = head_;
+ Container.Node* j = c.head_;
+ Container.Node* t = tail_;
+ Container.Node* ct = c.tail_;
+ TypeInfo ti = typeid(Container.ValueType);
+ while (i !is null && j !is null) {
+ if (!ti.equals(&i.data,&j.data))
+ return 0;
+ if (i is t && j is ct)
+ return 1;
+ i = i.next;
+ j = j.next;
+ }
+ return (i is null && j is null);
+ }
+
+ /** Compare two lists. */
+ int opCmp(Container c) {
+ Container.Node* i = head_;
+ Container.Node* j = c.head_;
+ Container.Node* t = tail_;
+ Container.Node* ct = c.tail_;
+ TypeInfo ti = typeid(Container.ValueType);
+ while (i !is null && j !is null) {
+ int cmp = ti.compare(&i.data,&j.data);
+ if (cmp)
+ return cmp;
+ if (i is t && j is ct)
+ return 0;
+ i = i.next;
+ j = j.next;
+ }
+ if (i is null && j is null)
+ return 0;
+ else
+ return (i is null) ? -1 : 1;
+ }
+
+ /** Create a one-item slice of the head. */
+ Container.SliceType head() {
+ return opSlice(0,1);
+ }
+
+ /** Return a one-item slice at the tail. */
+ Container.SliceType tail() {
+ Container.SliceType res;
+ res.head_ = res.tail_ = tail_;
+ return res;
+ }
+
+ /** Create a sub-list from index a to b (exclusive). The operation is
+ * O(max(a,b)). */
+ Container.SliceType opSlice(size_t a, size_t b) {
+ Container.SliceType res;
+ if (a != b) {
+ res.head_ = getNode(a);
+ Container.Node *v = res.head_;
+ b = b-a-1;
+ while (b--)
+ v = v.next;
+ res.tail_ = v;
+ }
+ return res;
+ }
+
+ /** Create a sub-list from the head of a to the tail of b (inclusive). */
+ Container.SliceType opSlice(Container.SliceType a, Container.SliceType b) {
+ if (a.head_ is null)
+ return b;
+ if (b.head_ is null)
+ return a;
+ Container.SliceType res;
+ res.head_ = a.head_;
+ res.tail_ = b.tail_;
+ return res;
+ }
+
+ /** Copies the list contents to an array. */
+ Container.ValueType[] values() {
+ Container.ValueType[] buffer = new Container.ValueType[length()];
+ foreach(size_t n, Container.ValueType val; *this) {
+ buffer[n] = val;
+ }
+ return buffer;
+ }
+}
+
+/** \class SList
+ * \brief A singly-linked list.
+ *
+ * A SList!(Value) is a singly linked list of data of type Value. A
+ * list is similar to a dynamic array except accessing an element in
+ * the middle or near the end of the list is O(n) and appending to the
+ * front or back is O(1). Any operation that is not constant-time will
+ * explicitly have the performance behavior documented.
+ *
+ * A singly-linked list differs from a doubly-linked list in the speed
+ * of accessing elements near the end of the list and the ability to
+ * reverse, addBefore iterate backwards and
+ * remove a sublist. The only operations supported in the
+ * middle of a singly-linked list are operations that modify the items
+ * that follow the sublist. This prevents manipulations in one sublist
+ * from invalidating an adjacent sublist.
+ *
+ * The optional ReadOnly parameter SList!(Value,ReadOnly) forbids
+ * operations that modify the container. The readonly() property returns
+ * a ReadOnly view of the container.
+ *
+ * The optional allocator parameter SList!(Value,false,Allocator) is used
+ * to allocate and free memory. The GC is the default allocator.
+ */
+struct SList(Value, bit ReadOnly = false, Alloc = GCAllocator) {
+
+ alias SList ContainerType;
+ alias SList SliceType;
+ alias Value ValueType;
+ alias size_t IndexType;
+ alias SNode!(Value) Node;
+ alias ReadOnly isReadOnly;
+
+ const int NodeAllocationBlockSize = 10; // allocate 10 nodes at a time
+
+ // private bug private {
+ Node* head_; // head_ is first item
+ Node* tail_; // tail_ is last item
+ // }
+
+ mixin MCommonSList!(head_, SList );
+
+ SList getThis(){return *this;}
+ mixin MListAlgo!(SList, getThis);
+
+ /** Get a ReadOnly view of the container */
+ .SList!(Value, true, Alloc) readonly() {
+ .SList!(Value, true, Alloc) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ /** Get a read-write view of the container */
+ .SList!(Value, false, Alloc) readwrite() {
+ .SList!(Value, false, Alloc) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ static if (!ReadOnly) {
+
+ /** Appends an item to the tail of the list. If the target list is
+ * a sub-list call addAfter instead of addTail to insert an item
+ * after a sub-list.
+ */
+ void addTail(Value v) {
+ if (tail_ is null) {
+ // no available nodes so allocate a new one
+ tail_ = newNode();
+ } else {
+ tail_ = tail_.next;
+ }
+ tail_.data = v;
+ if (head_ is null)
+ head_ = tail_;
+ }
+
+ /** Appends a list to the tail of the target list. If the target
+ * list is a sub-list call addAfter instead of addTail to insert
+ * another list after a sub-list.
+ */
+ void addTail(SList v) {
+ if (v.head_ is null)
+ return;
+ tail_.next = v.head_;
+ tail_ = v.tail_;
+ if (head_ is null)
+ head_ = v.head_;
+ }
+
+ mixin MListCatOperators!(SList);
+
+ /** Prepends an item to the head of the target list. */
+ void addHead(Value v) {
+ if (head_ is null) {
+ addTail(v);
+ } else if (tail_.next is null) {
+ // no available nodes so allocate a new one
+ Node* t = head_;
+ head_ = new Node();
+ head_.data = v;
+ head_.next = t;
+ } else {
+ // grab available node from end
+ Node* t = tail_.next;
+ tail_.next = t.next;
+ t.next = head_;
+ head_ = t;
+ t.data = v;
+ }
+ }
+
+ /** Prepends a list to the head of the target list. */
+ void addHead(SList v) {
+ if (v.head_ is null)
+ return;
+ Node* t = head_;
+ head_ = v.head_;
+ v.tail_.next = t;
+ if (tail_ is null)
+ tail_ = v.tail_;
+ }
+
+ /** Removes and returns the head item of the list. The node that
+ * contained the item may be reused in future additions to the
+ * list. To prevent the node from being reused call trim.
+ * If the target list is empty an IndexOutOfBoundsException is thrown
+ * unless version=MinTLNoIndexChecking is set.
+ */
+ Value takeHead() {
+ boundsCheck(head_);
+ Node* v = head_;
+ head_ = v.next;
+ // save node for future reuse
+ v.next = tail_.next;
+ tail_.next = v;
+ Value data = v.data;
+ v.data = Value.init;
+ return data;
+ }
+
+ /** Removes the head item of the list. */
+ void removeHead() {
+ boundsCheck(head_);
+ Node* v = head_;
+ head_ = v.next;
+ // save node for future reuse
+ v.next = tail_.next;
+ tail_.next = v;
+ v.data = Value.init;
+ }
+
+ /** Insert a list after a sub-list. */
+ void addAfter(SList subv, SList v) {
+ if (v.tail_ is null)
+ return;
+ Node* t = subv.tail_;
+ if (t is null) {
+ *this = v;
+ return;
+ }
+ v.tail_.next = t.next;
+ t.next = v.head_;
+ if (t is tail_)
+ tail_ = v.tail_;
+ }
+
+ /** Trims off extra nodes that are not actively being used by the
+ * list but are available for recyling for future add operations.
+ */
+ void trim() {
+ if (tail_ !is null)
+ tail_.next = null;
+ }
+
+ /** Removes n items after a sublist. */
+ void removeAfter(SList sublist, size_t n = 1) {
+ if (sublist.head_ is null)
+ return;
+ boundsCheck(head_);
+ Node* t = sublist.tail_;
+ Node* newt = t.next;
+ while (n--)
+ newt = newt.next;
+ t.next = newt;
+ if (newt is tail_)
+ tail_ = t;
+ }
+
+ /** Removes items between the tail of a to the head to b (exclusive). */
+ void removeBetween(SList a, SList b) {
+ // what to do if a or b is null?
+ boundsCheck(head_);
+ a.tail_.next = b.head_;
+ }
+
+ /** Set the value of one-item slice (more generally the head value). */
+ void value(Value newValue) {
+ head_.data = newValue;
+ }
+
+ } // !ReadOnly
+
+ /** Move a sub-list towards the tail by n items. By default moves
+ * to the next item.
+ */
+ void next(int n = 1, int end = 0) {
+ while (n-- > 0) {
+ if (end <= 0)
+ head_ = head_.next;
+ if (end >= 0)
+ tail_ = tail_.next;
+ }
+ }
+
+ /** Duplicates a list. */
+ .SList!(Value,ReadOnly,Alloc) dup() {
+ .SList!(Value,false,Alloc) res;
+ foreach(ValueType val; *this) {
+ res ~= val;
+ }
+ static if (ReadOnly) {
+ return res.readonly;
+ } else {
+ return res;
+ }
+ }
+
+ /** Get the value of one-item slice (more generally the head value).
+ * Useful for expressions like x.tail.value or x.head.value. */
+ Value value() {
+ return head_.data;
+ }
+
+ alias opApplyNoKey opApply;
+ alias opApplyWithKey opApply;
+ alias opApplyIter opApply;
+
+ private Node* newNode() {
+ static if (is(Alloc == GCAllocator)) {
+ // allocate a block of nodes and return pointer to first one
+ Node[] block = new Node[NodeAllocationBlockSize];
+ for (int k=1; kadd and remove functions and
+ * slices can be moved forward around the list indefinitely. A CircularSList
+ * also has a smaller memory footprint since it requires only one
+ * pointer for the tail instead of two pointers for a tail and head.
+ *
+ * The optional ReadOnly parameter CircularSList!(Value,ReadOnly) forbids
+ * operations that modify the container. The readonly() property returns
+ * a ReadOnly view of the container.
+ *
+ * The optional allocator parameter CircularSList!(Value,false,Allocator) is used
+ * to allocate and free memory. The GC is the default allocator.
+ */
+struct CircularSList(Value, bit ReadOnly = false, Alloc = GCAllocator) {
+
+ alias CircularSList ContainerType;
+ alias SList!(Value,ReadOnly,Alloc) SliceType;
+ alias Value ValueType;
+ alias size_t IndexType;
+ alias SNode!(Value) Node;
+ alias ReadOnly isReadOnly;
+
+ private {
+ Node* tail_; // tail_ is last item
+ }
+
+ /** Return the circular list as a non-circular SList. */
+ SliceType toSList() {
+ SliceType res;
+ if (tail_ is null)
+ return res;
+ res.head_ = tail_.next;
+ res.tail_ = tail_;
+ return res;
+ }
+
+ /** Get a ReadOnly view of the container */
+ .CircularSList!(Value, true, Alloc) readonly() {
+ .CircularSList!(Value, true, Alloc) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ /** Get a read-write view of the container */
+ .CircularSList!(Value, false, Alloc) readwrite() {
+ .CircularSList!(Value, false, Alloc) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ static if (!ReadOnly) {
+
+ /** Appends an item to the tail of the list. If the target list is
+ * a sub-list call addAfter instead of addTail to insert an item
+ * after a sub-list.
+ */
+ void addTail(Value v) {
+ Node* n = new Node;
+ n.data = v;
+ addNode(n);
+ tail_ = n;
+ }
+
+ /** Adds a node after tail. */
+ private void addNode(Node* n) {
+ if (tail_ is null) {
+ n.next = n;
+ tail_ = n;
+ } else {
+ n.next = tail_.next;
+ tail_.next = n;
+ }
+ }
+
+ /** Appends a list to the tail of the target list. If the target
+ * list is a sub-list call addAfter instead of addTail to insert
+ * another list after a sub-list.
+ */
+ void addTail(CircularSList v) {
+ addHead(v);
+ tail_ = v.tail_;
+ }
+
+ mixin MListCatOperators!(CircularSList);
+
+ /** Appends an item to the tail of the list. If the target list is
+ * a sub-list call addAfter instead of addTail to insert an item
+ * after a sub-list.
+ */
+ void addHead(Value v) {
+ Node* n = newNode();
+ n.data = v;
+ addNode(n);
+ }
+
+ /** Appends a list to the tail of the target list. If the target
+ * list is a sub-list call addAfter instead of addTail to insert
+ * another list after a sub-list.
+ */
+ void addHead(CircularSList v) {
+ if (v.tail_ is null)
+ return;
+ if (tail_ is null) {
+ tail_ = v.tail_;
+ return;
+ }
+ v.tail_.next = tail_.next;
+ tail_.next = v.tail_;
+ }
+
+ /** Removes and returns the head item of the list. */
+ Value takeHead() {
+ boundsCheck(tail_);
+ Node* v = tail_.next;
+ tail_.next = v.next;
+ Value val = v.data;
+ freeNode(v);
+ return val;
+ }
+
+ /** Removes the head item of the list. */
+ void removeHead() {
+ boundsCheck(tail_);
+ Node* v = tail_.next;
+ tail_.next = v.next;
+ freeNode(v);
+ }
+
+ /** Clear all contents. */
+ void clear() {
+ static if (is(Alloc == GCAllocator)) {
+ } else {
+ Node* i = head_;
+ if (i !is null)
+ tail_.next = null;
+ while (i !is null) {
+ Node* next = i.next;
+ Alloc.gcFree(i);
+ i = next;
+ }
+ }
+ *this = CircularSList.init;
+ }
+
+ /** Insert a list after a sub-list. */
+ void addAfter(SliceType subv, SliceType v) {
+ if (v.tail_ is null)
+ return;
+ Node* t = subv.tail_;
+ if (t is null) {
+ tail_ = v.tail_;
+ return;
+ }
+ v.tail_.next = t.next;
+ t.next = v.head_;
+ if (t is tail_)
+ tail_ = v.tail_;
+ }
+
+ /** Removes n items after a sublist. */
+ void removeAfter(SliceType sublist, size_t n = 1) {
+ if (sublist.head_ is null)
+ return;
+ boundsCheck(tail_);
+ Node* t = sublist.tail_;
+ Node* newt = t.next;
+ while (n--) {
+ Node* i = newt;
+ newt = newt.next;
+ freeNode(i);
+ }
+ t.next = newt;
+ if (newt is tail_)
+ tail_ = t;
+ }
+
+ /** Removes items between the tail of a to the head to b (exclusive).
+ * If a custom allocator is used the memory is not freed automatically.
+ */
+ void removeBetween(SliceType a, SliceType b) {
+ // what to do if a or b is null?
+ boundsCheck(tail_);
+ a.tail_.next = b.head_;
+ }
+
+ } // !ReadOnly
+
+ /** Duplicates a list. */
+ .CircularSList!(Value,ReadOnly,Alloc) dup() {
+ .CircularSList!(Value,false,Alloc) res;
+ foreach(ValueType val; *this) {
+ res ~= val;
+ }
+ static if (ReadOnly) {
+ return res.readonly;
+ } else {
+ return res;
+ }
+ }
+
+ /** Rotate the list. */
+ void rotate(int n = 1) {
+ while (n-- > 0)
+ tail_ = tail_.next;
+ }
+
+ private Node* head_() {
+ if (tail_ is null) return null;
+ return tail_.next;
+ }
+
+ CircularSList getThis(){return *this;}
+ mixin MListAlgo!(CircularSList, getThis);
+
+ mixin MCommonSList!(head_, CircularSList );
+
+ alias opApplyNoKey opApply;
+ alias opApplyWithKey opApply;
+ alias opApplyIter opApply;
+
+ private Node* newNode() {
+ static if (is(Alloc == GCAllocator)) {
+ return new Node;
+ } else {
+ Node* p = cast(Node*)Alloc.gcMalloc(Node.sizeof);
+ *p = Node.init;
+ return p;
+ }
+ }
+
+ private void freeNode(Node* n) {
+ static if (is(Alloc == GCAllocator)) {
+ } else {
+ Alloc.gcFree(n);
+ }
+ }
+}
+
+//version = MinTLVerboseUnittest;
+//version = MinTLUnittest;
+
+version (MinTLUnittest) {
+ unittest {
+ version (MinTLVerboseUnittest)
+ printf("starting mintl.slist unittest\n");
+ SList!(int) x;
+ x.add(3,4);
+ assert( x[0] == 3 );
+ assert( x[1] == 4 );
+ assert( x.length == 2 );
+
+ // test addHead
+ SList!(int) y;
+ y.addHead(4);
+ y.addHead(3);
+
+ // test ==
+ assert( x == y );
+ SList!(int) w = x.dup;
+ w ~= 5;
+ assert( x != w);
+
+ // test remove
+ assert( w.takeHead() == 3 );
+ w.trim();
+ w.addHead(3);
+
+ SList!(int) z = x.dup;
+ // test foreach iteration
+ foreach(size_t n, inout int val; z) {
+ val = n*10;
+ }
+ assert( z[0] == 0 );
+ assert( z[1] == 10 );
+ int n = 0;
+ foreach(SList!(int) itr; z) {
+ assert(itr[0] == z[n++]);
+ }
+
+ // test slicing
+ SList!(int) v = w[1..3];
+ assert( v.length == 2 );
+ assert( v[0] == 4 );
+ assert( v[1] == 5 );
+
+ // test algorithms
+ assert( v.opIn(5) == v.tail );
+ assert( v.count(5) == 1 );
+
+ // test another node type
+ SList!(char[]) str;
+ str ~= "hello";
+ str ~= "world";
+ assert( str[str.length-1] == "world" );
+
+ // test sub-list spanning
+ SList!(int) tmp;
+ int[10] tmp2;
+ tmp2[3] = 100;
+ tmp2[8] = 200;
+ foreach(int xx;tmp2)
+ tmp ~= xx;
+ SList!(int) a,b,c;
+ a = tmp[3..5];
+ b = tmp[7..9];
+ c = tmp[a..b];
+ assert( c.length == 6 );
+ assert( c[0] == 100 );
+ assert( c[5] == 200 );
+
+ // CircularSList
+
+ CircularSList!(int) cx;
+ cx.add(3,4);
+ assert( cx[0] == 3 );
+ assert( cx[1] == 4 );
+ assert( cx.length == 2 );
+
+ // test addHead
+ CircularSList!(int) cy;
+ cy.addHead(4);
+ cy.addHead(3);
+
+ // test ==
+ assert( cx == cy );
+ CircularSList!(int) cw = cx.dup;
+ cw ~= 5;
+ assert( cx != cw);
+
+ // test remove
+ assert( cw.takeHead() == 3 );
+ cw.addHead(3);
+
+ CircularSList!(int) cz = cx.dup;
+ // test foreach iteration
+ foreach(size_t n, inout int val; cz) {
+ val = n*10;
+ }
+ assert( cz[0] == 0 );
+ assert( cz[1] == 10 );
+ n = 0;
+ foreach(SList!(int) itr; cz) {
+ assert(itr[0] == cz[n++]);
+ }
+
+ // test slicing
+ SList!(int) cv = cw[1..3];
+ assert( cv.length == 2 );
+ assert( cv[0] == 4 );
+ assert( cv[1] == 5 );
+
+ // test algorithms
+ assert( cv.opIn(5) == cv.tail );
+ assert( cv.count(5) == 1 );
+
+ // test another node type
+ CircularSList!(char[]) cstr;
+ cstr ~= "hello";
+ cstr ~= "world";
+ assert( cstr[cstr.length-1] == "world" );
+
+ // test sub-list spanning
+ CircularSList!(int) ctmp;
+ int[10] ctmp2;
+ ctmp2[3] = 100;
+ ctmp2[8] = 200;
+ foreach(int xx; ctmp2)
+ ctmp ~= xx;
+ SList!(int) ca,cb,cc;
+ ca = ctmp[3..5];
+ cb = ctmp[7..9];
+ cc = ctmp[a..b];
+ assert( cc.length == 6 );
+ assert( cc[0] == 100 );
+ assert( cc[5] == 200 );
+
+ version (MinTLVerboseUnittest)
+ printf("finished mintl.slist unittest\n");
+ }
+}
+
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/sortedaa.d
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/sortedaa.d Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,1033 @@
+/** \file sortedaa.d
+ * \brief A sorted associative array.
+ *
+ * Written by Ben Hinkle and released to the public domain, as
+ * explained at http://creativecommons.org/licenses/publicdomain
+ * The red-black tree code is by Thomas Niemann.
+ * Email comments and bug reports to ben.hinkle@gmail.com
+ *
+ * revision 2.7.1
+ */
+
+module mintl.sortedaa;
+
+private import mintl.share; // for mixins
+import mintl.mem;
+
+// debug = dSortedAA; // can also pass at command line
+//debug(dSortedAA) {
+// private import std.stdio;
+//}
+
+/** \class CompareFcnSetException
+ * \brief An exception thrown when attempting to set the compare
+ * function twice. In particular it cannot be set on a non-empty
+ * SortedAA.
+ */
+class CompareFcnSetException: Exception {
+ this(char[] str) { super(str); }
+ this() { super("Cannot set the comparison function twice"); }
+}
+
+/** \class SortedAA
+ * \brief A sorted associative array.
+ *
+ * A SortedAA!(Key,Value) represents a sorted associative array with
+ * keys of type Key and values of type Value. A sorted associative
+ * array is similar to a builtin associative array except accessing an
+ * elements is O(log(n)), where n is the number of elements in the
+ * array, instead of O(1) and the elements are sorted by key. Any
+ * operation that is not O(log(n)) will explicitly have the
+ * performance behavior documented.
+ *
+ * The array is sorted by default according to the key's TypeInfo compare
+ * function. To use a custom key order call the CompareFcn property setter
+ * with a delegate of the form int delegate(Key* a, Key* b). The comparison
+ * function cannot be set after any elements are inserted.
+ *
+ * The optional ReadOnly parameter SortedAA!(Key,Value,ReadOnly) forbids
+ * operations that modify the container. The readonly() property returns
+ * a ReadOnly view of the container.
+ *
+ * The optional allocator parameter SortedAA!(Key,Value,false,Allocator) is used
+ * to allocate and free memory. The GC is the default allocator.
+ */
+struct SortedAA(Key,Value, bit ReadOnly = false, Alloc = GCAllocator) {
+
+ alias SortedAA ContainerType;
+ alias SortedAA SliceType;
+ alias Value ValueType;
+ alias Key IndexType;
+ alias ReadOnly isReadOnly;
+
+ /** Get a ReadOnly view of the container */
+ .SortedAA!(Key,Value,true) readonly() {
+ .SortedAA!(Key,Value,true) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ /** Get a read-write view of the container */
+ .SortedAA!(Key,Value,false) readwrite() {
+ .SortedAA!(Key,Value,false) res;
+ res = *cast(typeof(&res))this;
+ return res;
+ }
+
+ /** Get the kays in the array. The operation is O(n) where n is the number of
+ * elements in the array.
+ */
+ Key[] keys() {
+ Key[] res;
+ foreach(Key k,Value v;*this)
+ res ~= k;
+ return res;
+ }
+
+ /** Get the values in the array. The operation is O(n) where n is the number of
+ * elements in the array.
+ */
+ Value[] values() {
+ Value[] res;
+ foreach(Key k,Value v;*this)
+ res ~= v;
+ return res;
+ }
+
+ /** Property for the default value of the array when a key is missing. */
+ void missing(Value val) {
+ fixupShared();
+ shared.missing = val;
+ }
+ Value missing() {
+ if (!shared)
+ return Value.init;
+ return shared.missing;
+ }
+
+ /** Length of array. The operation is O(n) where n is the number of
+ * elements in the array.
+ */
+ size_t length() {
+ size_t len = 0;
+ foreach(Value val; *this)
+ len++;
+ return len;
+ }
+
+ /** Test if array is empty. */
+ bool isEmpty() {
+ return shared is null || shared.root is null;
+ }
+
+ static if (ReadOnly) {
+
+ /** Duplicates an array. */
+ SortedAA dup() {
+ .SortedAA!(Key,Value,false) res;
+ if (shared) {
+ if (shared.cmpFcn)
+ res.compareFcn = shared.cmpFcn;
+ res.missing = missing;
+ }
+ foreach(Key k,Value v;*this)
+ res[k] = v;
+ return res.readonly;
+ }
+
+ } else {
+
+ /** Clear all contents. */
+ void clear() {
+ static if (is(Alloc == GCAllocator)) {
+ } else {
+ if (shared) {
+ void freeNode(Node*p) {
+ if(p) {
+ freeNode(p.left);
+ freeNode(p.right);
+ Alloc.gcFree(p);
+ }
+ }
+ freeNode(shared.root);
+ Alloc.gcFree(shared);
+ }
+ }
+ *this = SortedAA.init;
+ }
+
+ /** Remove a key from the array. The target array can be a sub-array though
+ * the key may fall outside of the sub-array range. The value stored for
+ * the key is returned, if present.
+ */
+ Value take(Key key) {
+ // debug(dSortedAA) writefln("getAndRemove: %s",key);
+ Node* node = getNode(key,NullOnMiss);
+ if (!node) return missing;
+ Value value = node.val;
+ deleteNode(node);
+ return value;
+ }
+
+ /** Remove a key from the array. The target array can be a sub-array though
+ * the key may fall outside of the sub-array range.
+ */
+ void remove(Key key) {
+ // debug(dSortedAA) writefln("remove: %s",key);
+ deleteNode(getNode(key,NullOnMiss));
+ }
+
+ /** Remove a sub-array from the array. The operation is O(max(log(m),n))
+ * where m is the size of the target array and n is the number of
+ * elements in the sub-array.
+ */
+ void remove(SortedAA subarray) {
+ if (subarray.head_ is subarray.tail_) {
+ deleteNode(subarray.head_);
+ } else {
+ Key[] keylist = subarray.keys;
+ foreach(Key key;keylist)
+ remove(key);
+ }
+ }
+
+ /** Duplicates an array. */
+ SortedAA dup() {
+ SortedAA res;
+ if (shared) {
+ if (shared.cmpFcn)
+ res.compareFcn = shared.cmpFcn;
+ res.missing = missing;
+ }
+ foreach(Key k,Value v;*this)
+ res[k] = v;
+ return res;
+ }
+
+ } // !ReadOnly
+
+ /** signature for a custom comparison function */
+ alias int delegate(Key* a, Key* b) CompareFcn;
+
+ /** Set custom comparison function. If the array is non-empty or the
+ * comparison function has already been set a CompareFcnSetException
+ * is thrown.
+ */
+ void compareFcn(CompareFcn cmp) {
+ allocShared();
+ if (shared.cmpFcn !is null)
+ throw new CompareFcnSetException();
+ else
+ shared.cmpFcn = cmp;
+ }
+
+ /** Find (and insert if not present) the element with a given key
+ * and return the value. The target array can be a sub-array though
+ * the key may fall outside of the sub-array range.
+ */
+ Value opIndex(Key key) {
+ Node* t = getNode(key,NullOnMiss);
+ if (t)
+ return t.val;
+ else
+ return missing;
+ }
+
+ /** Store a value with a key, overwriting any previous value. The
+ * target array can be a sub-array though the key may fall outside of the
+ * sub-array range.
+ */
+ void opIndexAssign(Value val, Key key) {
+ Node* t = getNode(key,InsertOnMiss);
+ t.val = val;
+ }
+
+ /** Returns the value of the first item of a slice. In particular gets
+ * the value of a one-item slice.
+ */
+ Value value() {
+ if (head_ is null && tail_ is null)
+ return Value.init;
+ return head_.val;
+ }
+
+ /** Returns the key of the first item of a slice. In particular gets
+ * the key of a one-item slice.
+ */
+ Key key() {
+ if (head_ is null && tail_ is null)
+ return Key.init;
+ return head_.key;
+ }
+
+ /** Return the start of the sorted items (the min). */
+ SortedAA head() {
+ Node* node = head_ is null ? minNode() : head_;
+ SortedAA res;
+ res.shared = shared;
+ res.head_ = res.tail_ = node;
+ return res;
+ }
+
+ /** Return the end of the sorted items (the max). */
+ SortedAA tail() {
+ Node* node = tail_ is null ? maxNode() : tail_;
+ SortedAA res;
+ res.shared = shared;
+ res.head_ = res.tail_ = node;
+ return res;
+ }
+
+ /** Return a one-item slice of the item less than key */
+ SortedAA to(Key key) {
+ SortedAA res;
+ res.shared = shared;
+ res.head_ = res.tail_ = lookupSide(key,false);
+ return res;
+ }
+
+ /** Return a one-item slice of the item greater than or equal to key */
+ SortedAA from(Key key) {
+ SortedAA res;
+ res.shared = shared;
+ res.head_ = res.tail_ = lookupSide(key,true);
+ return res;
+ }
+
+ /** Move a slice towards the head or tail by n items. If n is
+ * negative the slice moves towards the head. A positive end is
+ * the tail, negative the head and 0 is both. By default moves to
+ * the next item.
+ */
+ void next(int n = 1, int end = 0) {
+ void doNext(inout Node* node, int m) {
+ while (m--)
+ node = nextNode(node);
+ }
+ void doPrev(inout Node* node, int m) {
+ while (m--)
+ node = prevNode(node);
+ }
+ if (n > 0) {
+ if (end >= 0)
+ doNext(tail_,n);
+ if (end <= 0)
+ doNext(head_,n);
+ } else {
+ n = -n;
+ if (end >= 0)
+ doPrev(tail_,n);
+ if (end <= 0)
+ doPrev(head_,n);
+ }
+ }
+
+ /** Find the element with a given key and return a pointer to the
+ * value. If the key is not in the array null is returned or if
+ * throwOnMiss is true an exception is thrown. The target array can
+ * be a sub-array though the key may fall outside of the sub-array
+ * range.
+ */
+ Value* get(Key key, bool throwOnMiss = false) {
+ Node* t = getNode(key,throwOnMiss ? ThrowOnMiss : NullOnMiss);
+ if (t)
+ return &t.val;
+ else
+ return null;
+ }
+
+ /** Find a key in the array and return a pointer to the associated value.
+ * Insert the key and initialize with Value.init if the key is not
+ * in the array.
+ */
+ Value* put(Key key) {
+ Node* t = getNode(key, InsertOnMiss);
+ return &t.val;
+ }
+
+ /** Create a slice from the head of a to the tail in b (inclusive). */
+ SortedAA opSlice(SortedAA a, SortedAA b) {
+ SortedAA res;
+ res.head_ = a.head_ is null ? minNode() : a.head_;
+ res.tail_ = b.tail_ is null ? maxNode() : b.tail_;
+ res.shared = shared;
+ return res;
+ }
+
+ /** Create a sub-array from key a to b (exclusive). */
+ SortedAA opSlice(Key a, Key b) {
+ return (*this)[from(a) .. to(b)];
+ }
+
+ /** Create a sub-array from slice a to key b (exclusive). */
+ SortedAA opSlice(SortedAA a, Key b) {
+ return (*this)[a .. to(b)];
+ }
+ /** Create a sub-array from key a to slice b (inclusive). */
+ SortedAA opSlice(Key a, SortedAA b) {
+ return (*this)[from(a) .. b];
+ }
+
+ /** Test for equality of two arrays. The operation is O(n) where n
+ * is length of the array.
+ */
+ int opEquals(SortedAA c) {
+ fixupShared();
+ c.fixupShared();
+ Node* i = head_ ? head_ : minNode();
+ Node* j = c.head_ ? c.head_ : c.minNode();
+ Node* end = tail_ ? tail_ : maxNode();
+ Node* cend = c.tail_ ? c.tail_ : c.maxNode();
+ TypeInfo ti_k = typeid(Key);
+ TypeInfo ti_v = typeid(Value);
+ int do_test(Node*p1,Node*p2) {
+ if (p1 is null && p2 is null)
+ return 1;
+ if ((p1 is null && p2 !is null) ||
+ (p1 !is null && p2 is null))
+ return 0;
+ if (!ti_k.equals(&p1.key,&p2.key))
+ return 0;
+ if (!ti_v.equals(&p1.val,&p2.val))
+ return 0;
+ return 1;
+ }
+ while (i !is end && j !is cend) {
+ if (!do_test(i,j))
+ return 0;
+ i = nextNode(i);
+ j = c.nextNode(j);
+ }
+ return do_test(i,j);
+ }
+
+ /** Test if a key is in the array. The target array can be a sub-array
+ * but the key may fall outside of the sub-array range.
+ */
+ bool contains(Key key) {
+ Value* node = get(key);
+ return node !is null;
+ }
+
+ /** Test if a key is in the array and set value if it is. */
+ bool contains(Key key,out Value value) {
+ Value* node = get(key);
+ if (node)
+ value = *node;
+ return node !is null;
+ }
+
+ /** Iterate over the array calling delegate to perform an action.
+ * The value is passed to the delegate.
+ */
+ int opApplyNoKeyStep(int delegate(inout Value val) dg, int step=1) {
+ int dg2(inout SortedAA itr) {
+ Value value = itr.value;
+ return dg(value);
+ }
+ return opApplyIterStep(&dg2,step);
+ }
+
+ /** Iterate over the array calling delegate to perform an action.
+ * The key and value are passed to the delegate.
+ */
+ int opApplyWithKeyStep(int delegate(inout Key key, inout Value val) dg,
+ int step = 1) {
+ int dg2(inout SortedAA itr) {
+ Key key = itr.key;
+ Value value = itr.value;
+ return dg(key,value);
+ }
+ return opApplyIterStep(&dg2,step);
+ }
+
+ /** Iterate over the array calling delegate to perform an action. A
+ * one-element sub-array is passed to the delegate.
+ */
+ int opApplyIterStep(int delegate(inout SortedAA itr) dg,int step=1) {
+ SortedAA itr;
+ itr = *this;
+ int res;
+ if (shared is null) return 0;
+ Node* i = head_ ? head_ : minNode();
+ Node* j = tail_ ? tail_ : maxNode();
+ Node* x = step>0?i:j;
+ Node* end = step>0?j:i;
+ while (x !is null) {
+ itr.head_ = itr.tail_ = x;
+ res = dg(itr);
+ if (res || x is end) return res;
+ x = step>0?nextNode(x):prevNode(x);
+ }
+ return res;
+ }
+
+ /** Iterate backwards over the array (from last to first key). This
+ * should only be called as the iteration parameter in a
+ * foreach statement
+ */
+ SortedAAReverseIter!(Key,Value,ReadOnly,Alloc) backwards() {
+ SortedAAReverseIter!(Key,Value,ReadOnly,Alloc) res;
+ res.list = this;
+ return res;
+ }
+
+ /** Helper functions for opApply */
+ mixin MOpApplyImpl!(SortedAA);
+ alias opApplyNoKey opApply;
+ alias opApplyWithKey opApply;
+ alias opApplyIter opApply;
+ mixin MAddAA!(SortedAA); // mixin add function
+
+ // End of public interface
+
+ private {
+ enum Color:int { Red, Black }
+ // share some data between array and sub-arrays to make updating
+ // easier and shrink the SortedAA footprint.
+ struct SharedArrayData {
+ Node* root;
+ CompareFcn cmpFcn;
+ Value missing;
+ Node* freelist;
+ }
+ struct Node {
+ Node* left, right, parent;
+ Color color;
+ Key key;
+ Value val;
+ }
+ SharedArrayData *shared;
+ Node* head_, tail_;
+ }
+
+ debug(dSortedAA) {
+ private void dumpTree(Node* x, char[] str,int indent) {
+ if (x !is null) {
+ int n = indent;
+ while (n--) printf(" ");
+ printf("%.*s %p: %d %.*s\n",str,x,x.color,x.key);
+ dumpTree(x.left,"left",indent+1);
+ dumpTree(x.right,"right",indent+1);
+ }
+ }
+ }
+
+ // lookup the smallest item greater than or equal to key (from)
+ // or lookup the largest item less than key
+ Node* lookupSide(Key key, bool from) {
+ Node* current;
+ Node* parent;
+ fixupShared();
+ current = shared.root;
+ parent = current;
+ int cmpVal = 0;
+ CompareFcn cmp = shared.cmpFcn;
+ while (current !is null) {
+ cmpVal = cmp(&key,¤t.key);
+ if (cmpVal == 0) {
+ return from?current:prevNode(current);
+ }
+ parent = current;
+ current = cmpVal < 0 ? current.left : current.right;
+ }
+ if (!parent) throw new Exception("Invalid Index");
+ if (from)
+ return cmpVal<0?prevNode(parent):parent;
+ else
+ return cmpVal>0?nextNode(parent):parent;
+ }
+
+ // initialize shared data if null
+ private void allocShared() {
+ if (shared is null) {
+ static if (is(Alloc == GCAllocator)) {
+ shared = new SharedArrayData;
+ } else {
+ shared = cast(SharedArrayData*)Alloc.gcMalloc(SharedArrayData.sizeof);
+ *shared = SharedArrayData.init;
+ }
+ }
+ }
+
+ // initialize shared data if null and initialize cmpFcn
+ private void fixupShared() {
+ allocShared();
+ if (shared.cmpFcn is null) {
+ TypeInfo ti = typeid(Key);
+ shared.cmpFcn = cast(CompareFcn)&ti.compare;
+ }
+ }
+
+ // return the next largest node or null if none
+ // used when we can't traverse the whole tree
+ private Node* nextNode(Node* x) {
+ if (x.right !is null) {
+ x = x.right;
+ while (x.left != null) x = x.left;
+ } else {
+ while (x.parent !is null && x.parent.right == x)
+ x = x.parent;
+ if (x.parent !is null && x.parent.left == x)
+ x = x.parent;
+ else
+ x = null;
+ }
+ return x;
+ }
+
+ // return the previous node or null if none
+ // used when we can't traverse the whole tree
+ private Node* prevNode(Node* x) {
+ if (x.left !is null) {
+ x = x.left;
+ while (x.right != null) x = x.right;
+ } else {
+ while (x.parent !is null && x.parent.left == x)
+ x = x.parent;
+ if (x.parent !is null && x.parent.right == x)
+ x = x.parent;
+ else
+ x = null;
+ }
+ return x;
+ }
+
+ // fixup Red-Black invariant
+ private void rotateLeft(Node* x) {
+ Node* y = x.right;
+ assert( y !is null );
+ x.right = y.left;
+ if (y.left !is null)
+ y.left.parent = x;
+ y.parent = x.parent;
+ if (x.parent !is null) {
+ if (x is x.parent.left)
+ x.parent.left = y;
+ else
+ x.parent.right = y;
+ } else {
+ shared.root = y;
+ }
+ y.left = x;
+ if (x !is null) x.parent = y;
+ }
+
+ // fixup Red-Black invariant
+ private void rotateRight(Node* x) {
+ Node* y = x.left;
+ assert( y !is null );
+ x.left = y.right;
+ if (y.right !is null)
+ y.right.parent = x;
+ y.parent = x.parent;
+ if (x.parent !is null) {
+ if (x is x.parent.right)
+ x.parent.right = y;
+ else
+ x.parent.left = y;
+ } else {
+ shared.root = y;
+ }
+ y.right = x;
+ if (x !is null) x.parent = y;
+ }
+
+ // fixup Red-Black invariant after an insert
+ private void insertFixup(Node* x) {
+ Node* root = shared.root;
+ while (x !is root && x.parent.color == Color.Red) {
+ debug(dSortedAA) printf("fixing up parent %p\n",x.parent);
+ if (x.parent is x.parent.parent.left) {
+ Node* y = x.parent.parent.right;
+ if (y !is null && y.color == Color.Red) {
+ x.parent.color = Color.Black;
+ y.color = Color.Black;
+ x.parent.parent.color = Color.Red;
+ x = x.parent.parent;
+ } else {
+ if (x is x.parent.right) {
+ x = x.parent;
+ debug(dSortedAA) printf("rotating left %p\n",x);
+ rotateLeft(x);
+ }
+ x.parent.color = Color.Black;
+ x.parent.parent.color = Color.Red;
+ debug(dSortedAA) printf("rotating right1 %s\n",x.parent.parent);
+ rotateRight(x.parent.parent);
+ }
+ } else {
+ Node* y = x.parent.parent.left;
+ if (y !is null && y.color == Color.Red) {
+ x.parent.color = Color.Black;
+ y.color = Color.Black;
+ x.parent.parent.color = Color.Red;
+ x = x.parent.parent;
+ } else {
+ if (x is x.parent.left) {
+ x = x.parent;
+ debug(dSortedAA) printf("rotating right %p\n",x);
+ rotateRight(x);
+ }
+ x.parent.color = Color.Black;
+ x.parent.parent.color = Color.Red;
+ debug(dSortedAA) printf("rotating left1 %p\n",x.parent.parent);
+ rotateLeft(x.parent.parent);
+ }
+ }
+ }
+ while (x.parent !is null)
+ x = x.parent;
+ x.color = Color.Black;
+ }
+
+ private enum {InsertOnMiss, ThrowOnMiss, NullOnMiss}
+
+ // returns node for a given key - even if the key is ouside the
+ // sub-array.
+ private Node* getNode(Key key, int failureAction) {
+ // debug(dSortedAA) writefln("lookup %s",key);
+ Node* current;
+ fixupShared();
+ current = shared.root;
+ Node* parent = null;
+ int cmpVal = 0;
+ CompareFcn cmp = shared.cmpFcn;
+ while (current !is null) {
+ cmpVal = cmp(&key,¤t.key);
+ // debug(dSortedAA) writefln("comparing %s %s got %s",key,current.key,cmpVal);
+ if (cmpVal == 0) return current;
+ parent = current;
+ current = cmpVal < 0 ? current.left : current.right;
+ }
+ switch (failureAction) {
+ case NullOnMiss: return null;
+ case ThrowOnMiss: throw new IndexOutOfBoundsException("Key not in container");
+ case InsertOnMiss: return insertNode(key, Value.init, parent, cmpVal);
+ }
+ }
+
+ // remove extra capacity
+ void trim() {
+ if (shared)
+ shared.freelist = null;
+ }
+
+ // Parameters for controlling block allocations
+ private const int NodeAllocBlockSize = 10; // number of nodes in block
+ private const int AllocBlockCutoff = 96; // max node size to allow blocks
+
+ // helper function to allocate a node
+ private Node* newNode() {
+ static if (is(Alloc == GCAllocator)) {
+ static if (Node.sizeof > AllocBlockCutoff) {
+ return new Node;
+ } else {
+ if (shared.freelist) {
+ Node* t = shared.freelist;
+ shared.freelist = t.left;
+ t.left = null;
+ return t;
+ }
+ Node[] block = new Node[NodeAllocBlockSize];
+ for(int k=1;k prev );
+ prev = val;
+ }
+ /* private bug
+ SortedAA!(char[],char[]) m5 = m2;
+ m5.head_ = m5.minNode();
+ m5.tail_ = m5.maxNode();
+ prev = "";
+ foreach(char[] val; m5) {
+ assert( val > prev );
+ prev = val;
+ }
+ prev = m5.maxNode().val;
+ foreach(char[] val; m5.backwards()) {
+ assert( val <= prev );
+ prev = val;
+ }
+ */
+ SortedAA!(int,int) m3;
+ m3.compareFcn = delegate int(int* a, int* b) {
+ return *a-*b;
+ };
+ m3[10] = -100;
+ m3[7] = 100;
+ m3[-10] = 200;
+ assert( m3.length == 3);
+ assert( m3[7] == 100 );
+ assert( m3[-10] == 200 );
+ assert( m3[10] == -100 );
+
+ SortedAA!(int,int) mm;
+ mm.add(10,-100, 7,100, -10,200);
+ assert( m3 == mm );
+
+ SortedAA!(int,int) m3a = m3.dup;
+ assert( m3a == m3 );
+ assert( m3a !is m3 );
+ assert( m3a.length == 3);
+ assert( m3a[7] == 100 );
+ assert( m3a[-10] == 200 );
+ assert( m3a[10] == -100 );
+
+ m3.remove(7);
+ m3.remove(10);
+ m3.remove(-10);
+ // assert( m3.shared.root is null );
+
+ int[] keys = m3a.keys;
+ assert( keys[0] == -10 );
+ assert( keys[1] == 7 );
+ assert( keys[2] == 10 );
+
+ // test slicing
+ SortedAA!(char[],int) m8 =
+ SortedAA!(char[],int).make("a",100,"c",300,"d",400,"b",200,
+ "f",600,"e",500);
+ SortedAA!(char[],int) msl,msl2,msl3;
+ // debug(dSortedAA) m8.dumpTree(m8.shared.root,"",0);
+ msl = m8["b".."d"];
+ msl2 = m8[m8.from("b123") .. m8.to("e")];
+ assert( msl.length == 2 );
+ // assert( msl.head_.key == "b" );
+ // assert( msl.tail_.key == "c" );
+ msl2 = m8["c".."f"];
+ assert( msl2.length == 3 );
+ // assert( msl2.head_.key == "c" );
+ // assert( msl2.tail_.key == "e" );
+ msl3 = m8[msl..msl2];
+ assert( msl3.length == 4 );
+ // assert( msl3.head_.key == "b" );
+ // assert( msl3.tail_.key == "e" );
+ m8.remove(msl2);
+ assert( m8.length == 3 );
+ debug(dSortedAA) printf("\nsize %d\n",m8.sizeof);
+
+ SortedAA!(int,int,false,MallocNoRoots) mal;
+ mal[10] = 20;
+ mal[30] = 50;
+ assert( mal[10] == 20 );
+ assert( mal[30] == 50 );
+ mal.clear();
+ assert( mal.isEmpty );
+
+ version (MinTLVerboseUnittest)
+ printf("starting mintl.sortedaa unittest\n");
+ }
+}
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/sorting.d
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/sorting.d Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,139 @@
+/** \file sorting.d
+ * \brief Mixins for sorting random-access and sequential-access containers
+ *
+ * Written by Ben Hinkle and released to the public domain, as
+ * explained at http://creativecommons.org/licenses/publicdomain
+ * Email comments and bug reports to ben.hinkle@gmail.com
+ *
+ * revision 1.0
+ */
+
+module mintl.sorting;
+
+// mixin for sorting random-access containers
+// quicksort with insertion sort for short lists
+template MRandomAccessSort(Container, alias list) {
+ void sort(int delegate(Container.ValueType* l, Container.ValueType* r) cmp = null) {
+ void swap(Container.ValueType* t1, Container.ValueType* t2 ) {
+ Container.ValueType t = *t1; *t1 = *t2; *t2 = t;
+ }
+ void insertionSort(Container data) {
+ size_t i = 1;
+ while(i < data.length) {
+ size_t j = i;
+ Container.ValueType* jp = data.lookup(j);
+ Container.ValueType* j1p;
+ while (j > 0 && cmp((j1p=data.lookup(j-1)),jp) > 0) {
+ swap(j1p,jp);
+ --j;
+ jp = j1p;
+ }
+ i++;
+ }
+ }
+ void dosort(Container data) {
+ if (data.length < 2) {
+ return;
+ } else if (data.length < 8) {
+ insertionSort(data);
+ return;
+ }
+ size_t tail = data.length-1;
+ size_t p = 1;
+ size_t q = tail;
+ Container.ValueType* headptr = data.lookup(0);
+ Container.ValueType* pptr = data.lookup(p);
+ Container.ValueType* qptr = data.lookup(q);
+ swap(headptr,data.lookup(data.length/2));
+ if (cmp(pptr,qptr) > 0) swap(pptr,qptr);
+ if (cmp(headptr,qptr) > 0) swap(headptr,qptr);
+ if (cmp(pptr,headptr) > 0) swap(pptr,headptr);
+ while (1) {
+ do p++; while (cmp(data.lookup(p), headptr) < 0);
+ do q--; while (cmp(data.lookup(q), headptr) > 0);
+ if (p > q) break;
+ swap(data.lookup(p),data.lookup(q));
+ }
+ swap(headptr,data.lookup(q));
+ if (0 < q)
+ dosort(data[0 .. q+1]);
+ if (p < tail)
+ dosort(data[p .. tail+1]);
+ }
+ TypeInfo ti = typeid(Container.ValueType);
+ if (cmp is null) {
+ cmp = cast(typeof(cmp))&ti.compare;
+ }
+ dosort(list);
+ }
+}
+
+// mixin for sorting sequential-access containers
+// using mergesort customized for doublly-linked lists
+// TODO: allow singly-linked lists, too
+template MSequentialSort(Container, alias head_, alias tail_) {
+ void dosort(out Container.Node* newhead,
+ out Container.Node* newtail,
+ int delegate(Container.SortType* l, Container.SortType* r) cmp = null) {
+ void link(Container.Node* a, Container.Node* b) {
+ if (a) a.next = b;
+ if (b) b.prev = a;
+ }
+ if (cmp is null) {
+ TypeInfo ti = typeid(Container.SortType);
+ cmp = cast(typeof(cmp))&ti.compare;
+ }
+ Container.Node* head = head_;
+ Container.Node* tail = tail_;
+ Container.Node* headprev = head.prev;
+ Container.Node* i,j,e,itail;
+ i = tail;
+ tail = tail.next; // one past tail
+ i.next = null;
+ int depth;
+ size_t ilen, jlen, len = 1;
+ while (1) {
+ i = head;
+ depth = 0;
+ itail = null;
+ head = null;
+ while (i) {
+ depth++;
+ j = i;
+ ilen = 0;
+ for (size_t k = 0; k < len; k++) {
+ ilen++;
+ j = j.next;
+ if (!j) break;
+ }
+ jlen = len;
+ while (ilen > 0 || (jlen > 0 && j)) {
+ if (ilen == 0) {
+ e = j; j = j.next; jlen--;
+ } else if (jlen == 0 || !j ||
+ cmp(i.sortLookup(),j.sortLookup()) <= 0) {
+ e = i; i = i.next; ilen--;
+ } else {
+ e = j; j = j.next; jlen--;
+ }
+ if (itail) {
+ link(itail,e);
+ } else {
+ head = e;
+ }
+ itail = e;
+ }
+ i = j;
+ }
+ itail.next = null;
+ if (depth <= 1) {
+ link(itail,tail);
+ newtail = itail;
+ link(headprev,head);
+ newhead = head;
+ return;
+ }
+ len *= 2;
+ }
+ }
+}
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/stack.d
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/stack.d Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,91 @@
+/** \file stack.d
+ * \brief A stack container
+ *
+ * Written by Ben Hinkle and released to the public domain, as
+ * explained at http://creativecommons.org/licenses/publicdomain
+ * Email comments and bug reports to ben.hinkle@gmail.com
+ *
+ * revision 1.1
+ */
+
+module mintl.stack;
+
+private import mintl.deque;
+private import mintl.arraylist;
+import mintl.adapter;
+import mintl.share;
+import mintl.mem;
+
+/** A stack of items of stype Value backed by a container of type ImplType.
+ * Aliases push and pop allow stack operations. By default the stack is
+ * backed by a Deque.
+ */
+struct Stack(Value, ImplType = Deque!(Value)) {
+
+ alias Stack ContainerType;
+ alias Value ValueType;
+ alias size_t IndexType;
+ alias ImplType AdaptType;
+ const bit isReadOnly = ImplType.isReadOnly;
+
+ ImplType impl;
+
+ mixin MAdaptBuiltin!(impl,Stack);
+ mixin MAdaptBasic!(impl,Stack);
+ mixin MAdaptList!(impl,Stack);
+ mixin MListCatOperators!(Stack);
+
+ // Stack specific
+ static if (!ImplType.isReadOnly) {
+ alias add push;
+ alias takeTail pop;
+ }
+ Value peek() {
+ ImplType last = impl.tail;
+ return last.isEmpty ? Value.init : last[0];
+ }
+}
+
+/** Convenience alias for a stack backed by an array */
+template ArrayStack(Value) {
+ alias Stack!(Value,ArrayList!(Value)) ArrayStack;
+}
+
+//version = MinTLVerboseUnittest;
+//version = MinTLUnittest;
+
+version (MinTLUnittest) {
+ import mintl.list;
+ unittest {
+ version (MinTLVerboseUnittest)
+ printf("starting mintl.stack unittest\n");
+ Stack!(int) st;
+ st.push(10, 20);
+ assert( st.peek == 20 );
+ assert( st.pop == 20 );
+ assert( st[st.length - 1] == 10 );
+ assert( st.pop == 10 );
+ assert( st.length == 0 );
+
+ ArrayStack!(int) st2;
+ st2.push(10);
+ st2 ~= 20;
+ assert( st2.peek == 20 );
+ assert( st2.pop == 20 );
+ assert( st2[st2.length - 1] == 10 );
+ assert( st2.pop == 10 );
+ assert( st2.length == 0 );
+
+ Stack!(int,List!(int)) st3;
+ st3.push(10);
+ st3 ~= 20;
+ assert( st3.peek == 20 );
+ assert( st3.pop == 20 );
+ assert( st3[st3.length - 1] == 10 );
+ assert( st3.pop == 10 );
+ assert( st3.length == 0 );
+
+ version (MinTLVerboseUnittest)
+ printf("finished mintl.stack unittest\n");
+ }
+}
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/unittest.d
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/unittest.d Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,6 @@
+
+import mintl.all;
+
+int main() {
+ return 0;
+}
diff -r 4b2e8e8a633e -r 5dd9f598bcd8 trunk/mintl/win32.mak
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mintl/win32.mak Sat Mar 29 12:30:20 2008 -0600
@@ -0,0 +1,74 @@
+
+# To build mintl.lib type
+# make -f win32.mak DFLAGS=-g LIBNAME=mintl_debug.lib
+# or
+# make -f win32.mak DFLAGS=-release LIBNAME=mintl.lib
+# The mintl.lib and object files will be created in the source directory.
+
+# flags to use building unittest.exe
+DUNITFLAGS=-g -v -unittest -I.. -version=MinTLUnittest -version=MinTLVerboseUnittest
+
+# flags to use when building the mintl.lib library
+DLIBFLAGS=$(DFLAGS) -release -I..
+
+DMD = dmd
+LIB = lib
+
+targets : unittest
+
+unittest : unittest.exe
+
+LIBNAME = mintl.lib
+
+#mintl : $(LIBNAME)
+
+SRC = all.d \
+ array.d \
+ arraylist.d \
+ arrayheap.d \
+ deque.d \
+ hashaa.d \
+ list.d \
+ slist.d \
+ share.d \
+ adapter.d \
+ stack.d \
+ queue.d \
+ set.d \
+ multiaa.d \
+ mem.d \
+ sorting.d \
+ sortedaa.d
+
+OBJS = all.obj \
+ array.obj \
+ arraylist.obj \
+ arrayheap.obj \
+ deque.obj \
+ hashaa.obj \
+ list.obj \
+ slist.obj \
+ share.obj \
+ adapter.obj \
+ stack.obj \
+ queue.obj \
+ set.obj \
+ multiaa.obj \
+ mem.obj \
+ sorting.obj \
+ sortedaa.obj
+
+.d.obj :
+ $(DMD) -c $(DLIBFLAGS) -of$@ $<
+
+$(LIBNAME) : $(OBJS) $(SRC)
+ $(LIB) -c $@ $(OBJS)
+
+
+unittest.exe : $(LIBNAME) $(SRC)
+ $(DMD) $(DUNITFLAGS) unittest.d -ofunittest.exe $(SRC)
+
+clean:
+ del *.obj
+ del $(LIBNAME)
+ IF EXIST unittest.exe del unittest.exe