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