Mercurial > projects > aid
view trunk/mintl/index.html @ 1:5dd9f598bcd8
Update
author | revcompgeek |
---|---|
date | Sat, 29 Mar 2008 12:30:20 -0600 |
parents | |
children |
line wrap: on
line source
<HTML> <head> <TITLE>Minimal Template Library for D</TITLE> </head> <body> <h1>MinTL</h1> MinTL is a "minimal template library" of containers for the D programming language. For more info about D see <a href="http://www.digitalmars.com/d/">DigitalMars D home page</a>. The downloads are the <a href="mintl.zip">Core Library</a> and the <a href="mintlc.zip">MinTL Concurrent Library</a> (<a href="conc.html">mintlc web page</a>), which includes a dependent <a href="locks.html">Synchronization Library</a>. The current version is 2.7.1. <p> This library is in the public domain. Written by <a href="http://home.comcast.net/~benhinkle"> Ben Hinkle</a>, 2004. Email comments and bug reports to ben.hinkle@gmail.com <p> <h3> Contents </h3> <a href="#Overview">Overview</a></br> <a href="#Lists">List Containers</a></br> <a href="#Assoc">Associative Containers</a></br> <a href="#Slicing">Slicing</a></br> <a href="#Foreach">Foreach traversals</a></br> <a href="#Sorting">Sorting</a></br> <a href="#Allocators">Allocators</a></br> <a href="#unmod">Unmodifiable Containers</a></br> <a href="#Examples">Examples</a></br> <a href="#API">API Reference by module</a></br> <a name="Overview"></a> <h3> Overview </h3> The philosophy of the library is to be as simple and minimal as possible: <list> <li> The design is simple by keeping the number of classes to a minimum and reusing concepts from builtin dynamic and associative arrays. For example a slice of a container has the same type as the container, just as the slice of a dynamic array is another dynamic array. <li> The memory footprint and the garbage generation is kept to a minimum by relying on structs instead of classes and by implementing slicing and traversals without allocating dynamic memory. Some containers also recycle nodes. For example when the head or tail of a list is removed the node is retained and reused the next time an item is added to the head or tail. Optional Allocator parameters allow custom memory management. <li> Closely related data structures share common naming conventions and adapters reuse fundamental data structures like arrays, linked-lists and sorted associative arrays for stacks, queues and sets. Performance can be tuned for different uses by either choose between several variations (eg. a linked list, a circular array or a deque) or by supplying optional constructor arguments. </list> <p> MinTL has the following containers <p> <table border="1"> <caption>List containers</caption> <tr> <th>container <th> implementation <th> file <th> brief</th> </tr> <tr> <td> <a href="#list">List</a> <td> doubly linked list <td> list.d <td> sortable linked list with "previous" and "next" pointers </td> </tr> <tr> <td> <a href="#clist">CircularList</a> <td> circular doubly linked list <td> list.d <td> doubly linked list where the head and tail are linked </td> </tr> <tr> <td> <a href="#slist">SList</a> <td> singly linked list <td> slist.d <td> linked list with only "next" pointers </td> </tr> <tr> <td> <a href="#cslist">CircularSList</a> <td> circular singly linked list <td> slist.d <td> singly linked list where the tail points to the head </td> </tr> <tr> <td> <a href="#arraylist">ArrayList</a> <td> circular array <td> arraylist.d <td> sortable list backed by a resizable circular array </td> <tr> <td> <a href="#deque">Deque</a> <td> circular block-allocated array <td> deque.d <td> list backed by a resizable block-allocated circular array </td> <tr> <td> <a href="#arrayheap">ArrayHeap</a> <td> heap <td> arrayheap.d <td> complete binary tree backed by an array </td> <tr> <td> <a href="#stack">Stack</a> <td> adapter <td> stack.d <td> adapts a list container to be a stack </td> <tr> <td> <a href="#arraystack">ArrayStack</a> <td> ArrayList <td> stack.d <td> wraps an ArrayList with the stack adapter </td> <tr> <td> <a href="#queue">Queue</a> <td> adapter <td> queue.d <td> adapts a list container to be a queue </td> <tr> <td> <a href="#arrayqueue">ArrayQueue</a> <td> ArrayList <td> queue.d <td> wraps an ArrayList with the queue adapter </td> <tr> <td> <a href="#pqueue">PriorityQueue</a> <td> ArrayHeap <td> queue.d <td> wraps an ArrayHeap with the queue adapter </td> </table> <p> <table border="1"> <caption>Associative containers</caption> <tr> <th>container <th> implementation <th> file <th> brief</th> <tr> <td> <a href="#hashaa">HashAA</a> <td> linked hash table <td> hashaa.d <td> sortable associative array with nodes ordered by insertion order </td> <tr> <td> <a href="#sortedaa">SortedAA </a> <td> red-black tree <td> sortedaa.d <td> sorted associative array </td> </tr> <tr> <td> <a href="#set">Set</a> <td> adapter <td> set.d <td> adapts an associative container to be a set </td> <tr> <td> <a href="#sortedset">SortedSet</a> <td> SortedAA <td> set.d <td> wraps a SortedAA with the set adapter </td> <tr> <td> <a href="#multiset">MultiSet</a> <td> adapter <td> set.d <td> adapts an associative container to be a set with repeats </td> <tr> <td> <a href="#sortedmultiset">SortedMultiSet</a> <td> SortedAA <td> set.d <td> wraps a SortedAA with the multi-set adapter </td> <tr> <td> <a href="#multiaa">MultiAA</a> <td> adapter <td> multiaa.d <td> adapts an associative container to hold repeated keys </td> <tr> <td> <a href="#sortedmultiaa">SortedMultiAA</a> <td> SortedAA <td> multiaa.d <td> wraps a SortedAA with the multi-aa adapter </td> </table> <p> The module mintl.array defines helper functions for builtin dynamic and associative arrays. <a name="BuildInstall"> <h3> Build and Install</h3> To use MinTL first unpack the library in a directory on the D compiler search path. There are pre-built debug and non-debug versions of the library. To enable flexible <tt>add()</tt> datatype support uncomment the <tt>version=WithBox</tt> statement in mintl.share and recompile MinTL. To use std.boxer in a debug build you must also rebuild phobos with debugging. If you wish to rebuild MinTL enter the mintl directory and type <tt>make -f win32.mak</tt> or <tt>make -f linux.mak</tt>. In your source code <tt>import</tt> the desired modules and compile each container used and the mintl static library into the application. If a concurrent container is needed download the <tt>mintlc</tt> sub-package and link that library and the <a href="locks.html">Locks</a> library into the application. For example on Linux to compile the program <tt>app.d</tt> <pre> import mintl.list; int main() { List!(int) list = List!(int).make(10,20,30); return 0; } </pre> run in the directory above mintl the command <pre> dmd app.d mintl/libmintl_debug.a </pre> to build with asserts or <pre> dmd app.d -release mintl/libmintl.a </pre> to build without asserts. On Windows run <pre> dmd app.d mintl\mintl_debug.lib </pre> or <pre> dmd app.d -release mintl\mintl.lib </pre> If the mintl directory is not in the current directory then use the -I flag to add it to the search path <pre> dmd app.d -Ipath_to_mintl path_to_mintl/mintl/libmintl.a </pre> or modify the dmd\bin\sc.ini file (on Windows) or dmd.conf (on Linux) to include the paths to mintl. For example if MinTL is unpacked in the directory C:\d on Windows then sc.ini should be modified to include C:\d in the include path and C:\d\mintl on the library search path: <pre> LIB="%@P%\..\lib";\dm\lib;C:\d\mintl DFLAGS="-I%@P%\..\src\phobos";C:\d </pre> On Linux the static library can be put in a standard location like /usr/lib if desired. <a name="Lists"> <h3> List Containers </h3> The list containers <tt>List</tt>, <tt>SList</tt>, <tt>CircularList</tt>, <tt>CircularSList</tt>, <tt>ArrayList</tt>, <tt>Deque</tt>, <tt>ArrayHeap</tt> and the concurrent queues and stacks share a naming convention for adding and removing items. The <i>head</i> is the first item in the container and the <i>tail</i> is the last item. All list containers support constant-time access to the head and tail. The speed of accessing the <tt>length</tt> property depends on the container. Array-based containers have constant-time access to length, the linked-list containers have constant-time unless an operation modifies the list to have unknown length, in which case the next time the length is computed it is cached again. The singly-linked lists have linear-time length access and it is not cached. <p> Some containers maintain nodes past the head and tail of the list as extra capacity. To trim off any extra capacity most containers support a <tt>trim</tt> function. <p> The circular lists <tt>CircularList</tt> and <tt>CircularSList</tt> are the same as the non-circular versions except that slicing a circular list returns a non-circular list and node are not reused when adding or removing items. However circular lists are useful when the objects being modeled do not have a natural unique definition of a head or tail. <p> An <tt>ArrayList</tt> can also be used as a dynamic array with managed capacity. Set the <tt>capacity</tt> property or allocate an array with the desired capacity and leave the head of the arraylist at 0. The arraylist will automatically grow the capacity as required. <p> To add items to a container call <tt>add</tt> with any number of items. For example <pre> List!(int) x,y,z; y.add(10,20,30); z.add(50,60,70); x = y; x ~= 40; x ~= z; x ~= 80; </pre> results in the following linked list <pre> x[0],y[0] y[2] z[0] z[2] x[7] 10 <-> 20 <-> 30 <-> 40 <-> 50 <-> 60 <-> 70 <-> 80 </pre> To add a single item or list call <tt>addTail</tt> or use one of the concatenation operators. Some containers also support adding items or lists at the head using <tt>addHead</tt> or at a position in the interior of the list using <tt>addBefore</tt> or <tt>addAfter</tt>. To create a list in an expression use the static <tt>make</tt> function For example, <pre> List!(int) x; x = List!(int).make(10,20,30) ~ List!(int).make(50,60,70); </pre> <p> To remove items call one of the <tt>take</tt> or <tt>remove</tt> functions. All list containers support <tt>removeHead</tt> to remove the head of the list and <tt>takeHead</tt> to remove and return the stored value, if any. Some containers also support <tt>takeTail</tt> and <tt>removeTail</tt> to remove the tail and <tt>remove</tt> to remove a slice. <p> Stacks and queues are implemented as adapters of a list container. By default they use a Deque as the backing container. Stacks define aliases <tt>push</tt> for <tt>add</tt> and <tt>pop</tt> for <tt>takeTail</tt>. Queues define an alias <tt>take</tt> for <tt>takeHead</tt> (the function <tt>add</tt> is used to add to the end of a queue). For example, <pre> Stack!(char[]) x; x.push("first","second"); assert( x.pop == "second" ); assert( x.pop == "first" ); Queue!(char[]) x; x.add("first","second"); assert( x.take == "first" ); assert( x.take == "second" ); </pre> A <tt>PriorityQueue</tt> is an ArrayHeap wrapped with the Queue adapter. To set a custom comparison function access the <tt>impl</tt> property of the adapter: <pre> PriorityQueue!(char[]) x; x.impl.compareFcn = &fcn; x.add("first","second"); </pre> <p> The following table outlines the advantages and disadvantages of each list container <table border="1"> <tr> <th>container <th> advantages <th> disadvantages </th> </tr> <tr> <td> List <td> O(1) insertion at head/tail or before/after slices <td> O(n) access to middle of list </td> </tr> <tr> <td> SList <td> O(1) insertion at head/tail or after slices; less overhead than <tt>List</tt> <td> O(n) access to middle or near end of list </td> </tr> <tr> <td> ArrayList <td> O(1) insertion at head/tail. O(1) access to any index <td> O(n) insertion in middle </td> </tr> <tr> <td> Deque <td> O(1) insertion at head/tail. O(1) access to any index. Block allocated. <td> O(n) insertion in middle; non-contiguous storage </td> </tr> <tr> <td> ArrayHeap <td> maintains items in semi-sorted order; O(log(n)) add/remove. <td> only allows <tt>addTail</tt> and <tt>takeHead</tt> </td> </tr> </table> <a name="Assoc"> <h3> Associative Containers </h3> The associative containers <tt>SortedAA</tt>,<tt>HashAA</tt>, and <tt>ConcurrentAA</tt> are similar to builtin associative arrays but with extra capabilities. The <tt>SortedAA</tt> maintains the keys in some specific order as determined by a comparison function. By default the keys are ordered by the type's default comparison function. To specify a custom comparison function assign to the <tt>compareFcn</tt> property. The <tt>HashAA</tt> maintains the keys in insertion order, meaning if an indexing expression using key <tt>x</tt> is evaluated before an indexing expression using key <tt>y</tt> then <tt>x</tt> is traversed before <tt>y</tt> in <tt>foreach</tt> traversals. Assigning to a key already in the array does not change the insertion order. The other associative array properties <tt>dup</tt>, <tt>length</tt>, <tt>keys</tt> and <tt>values</tt> are also implemented. <p> Elements are inserted or modified using the <tt>add</tt> function or using indexing lvalue expressions and retrieved using indexing rvalue expressions. To test if a key is in the array use the overloaded <tt>contains</tt> functions. An indexing expression that is not an assignment will return a default missing value. The missing value defaults to Value.init but can be set by assigning to the <tt>missing</tt> property. The functions <tt>get</tt> and <tt>put</tt> allow more flexibility in handling missing keys by allowing the user to either return null, throw or insert. To remove an item call the <tt>remove</tt> function. Both <tt>HashAA</tt> and <tt>SortedAA</tt> maintain a freelist of removed nodes for future reuse. To release the freelist for garbage collection call <tt>trim</tt>. <p> For example to define a sorted associative array with three entries associating "first" with 10, "second" with 20 and "third" with 30 type <pre> SortedAA!(int,char[]) x; x.add(10,"first", 20,"second", 30,"third"); </pre> or equivalently, <pre> SortedAA!(int,char[]) x; x[10] = "first"; x[20] = "second"; x[30] = "third"; </pre> To create an associative array in an expression use the static <tt>make</tt> function For example, <pre> foo(SortedAA!(int,char[]).make(10,"first",20,"second",30,"third")); </pre> <p> The number of elements in an associative container is computed by the <tt>length</tt> property. <p> Sets and multi-associative-arrays are implemented as adapters of an associative container. By default sets use a HashAA as the backing container. Use <tt>add</tt> to add items to a set and use an indexing expression to check if an item is in the set. For example, <pre> Set!(char[]) x; x.add("first","second","third"); assert( x["first"] ); assert( x["second"] ); assert( x["third"] ); assert( !x["fourth"] ); MultiSet!(char[]) mx; xm.add("first","second","first","third","second"); xm.remove("first"); assert( x["first"] ); MultiAA!(int,char[]) y; y.add(10,"first",20,"second",10,"third"); assert( y[10].length == 2 ); </pre> <a name="Slicing"> <h3> Slicing </h3> In general slicing a container behaves like slicing a dynamic array. For example, slicing between two indices in a List creates another List with the head at the first index and the tail at the element before the second index. The contents of the slice is shared with the original list so assigning new values to elements in the list will be visible in the oringal list. The resulting slice, or sub-list, can be traversed using "foreach", duplicated, indexed into, etc just like a slice of a dynamic array can be treated as a "first-class" dyamic array. The following diagram illustrates the relationships for <tt>x</tt> and <tt>y</tt> if <tt>x</tt> is a list with 6 items and <tt>y</tt> is the slice <tt>x[2..4]</tt>.<br> <pre> x[0] y[0] y[1] x[5] 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 </pre> Executing <tt>z = y.dup</tt> would result in <pre> z[0] z[1] 2 <-> 3 </pre> <p> One should be careful when resizing or writing to a slice. For example do not (in general) append or prepend item to a sub-list using the addTail or addHead functions or remove items using removeTail and removeHead unless the original list is no longer needed. To insert an item or list at a certain location create a slice with the head at the desired location and call <tt>addBefore</tt> or create a slice with the tail at the desired location and call <tt>addAfter</tt>. To remove a portion of a list create a slice and call <tt>remove</tt>. Again one should always insert and remove from the original list otherwise any variable referring to the original list will become out of sync. <p> A sub-list can be moved towards the head or tail of the original list by calling the <tt>next</tt> function. This allows a sub-list to traverse up and down the original list efficiently. Continuing the example from above, executing <tt>y.next(-1)</tt> would result in <pre> x[0] y[0] y[1] x[5] 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 </pre> and then executing <tt>x.remove(y)</tt> would result in <pre> x[0] x[3] 0 <-> 3 <-> 4 <-> 5 y[0] y[1] 1 <-> 2 </pre> The performance of inserting and removing from the interior of an ArrayList or Deque can be significantly worse than that of a List if the slices are near the middle of the container. <p> The SortedAA slicing behavior is designed to chose slices without modifying the underlying container. The functions <tt>from</tt> and <tt>to</tt> can find a one-item slice starting from or up to a given key. For example if <tt>words</tt> is a sorted associative array indexed by <tt>char[]</tt> then <pre> words["a" .. "b"] </pre> or, equivalently, <pre> words[words.from("a") .. words.to("b")] </pre> is a slice containing all the items with keys that start with the character "a" even if the strings "a" and "b" aren't in the container. <a name="Foreach"> <h3> Foreach </h3> Containers and slices of containers can be traversal in <tt>foreach</tt> statements by value, key-value pairs and one-element slices. Some containers support moving a slice up and down the container. For these containers a slice can be used for the same purposes as an iterator in C++ or Java. <p> Each container also supports backwards traversals by calling <tt>backwards</tt> in a foreach statement. For example, <pre> List!(int) x; ... foreach( int val; x.backwards() ) printf("%d ",val); </pre> will print out the contents of x from tail to head. Backwards traversals do not allocate any dynamic memory. <a name="Sorting"> <h3> Sorting </h3> MinTL supports sorting containers in two forms. The <tt>SortedAA</tt> is a sorted associative container that maintains its elements in a given sorted order at all times. The comparison delegate used to determine the element order must be specified before the first element is insert or the key's default comparison function will be used and it cannot be changed during the lifetime of the container. The <tt>SortedSet</tt> and <tt>SortedMultiAA</tt> are derived from <tt>SortedAA</tt> and have the same sorting semantics. <p> The other form of sorting is through calling the <tt>sort</tt> methods of the containers <tt>ArrayList</tt>, <tt>Deque</tt>, <tt>List</tt>, and <tt>HashAA</tt> or by using the <tt>sort</tt> template in <tt>mintl.array</tt> to sort a dynamic array. These sort methods take an optional comparison delegate. The default comparison delegate is the sorting type's default comparison function. For the list-like containers the sorting type is the value type of the container. For <tt>HashAA</tt> the sorting type is the key type. Sorting is done in-place and slices are preserved relative to their surrounding container. For example, the following code creates a short linked list, sorts and slice and compares it with the expected end result: <pre> List!(int) list; list.add(40,300,-20,100,400,200); list[1 .. 5].sort(); // sort a slice in-place assert( list == List!(int).make(40,-20,100,300,400,200)); </pre> <p> Sorting a container does not change the behavior of adding new elements. The sorting operation is performed once and the comparison function is not remembered by the container or used in any other way. For example sorting a <tt>HashAA</tt> which was previously maintained in insertion order will sort the elements but adding any new elements will add them to the end of the traversal order in insertion order again. <a name="Allocators"> <h3> Allocators </h3> Most containers accept an optional <tt>Allocator</tt> parameter to customize memory management. The default allocator is the <tt>GCAllocator</tt> which indicates to the container that the garbage collector should be used for all allocations. If a custom allocator is supplied the container will call the memory management functions in the allocator to allocate and free memory. Users who supply a non-garbage-collecting allocator need to call <tt>clear</tt> when done with a container so that the memory can be released. <p> An allocator is a type containing 8 symbols malloc, calloc, realloc, free and the corresponding GC-aware versions gcMalloc, gcCalloc, gcRealloc and gcFree. Containers will call the GC-aware functions on blocks that may hold roots and otherwise will call the regular functions. Allocators are expected to throw an <tt>OutOfMemory</tt> exception if the allocation fails. <p> The two predefined allocators <tt>Malloc</tt> and <tt>MallocNoRoots</tt> use std.c.stdlib.malloc to perform allocations. The MallocNoRoots ignores any requests by the container to register roots with the GC. The MallocNoRoots allocator should only be used with containers that the user knows will never contain any roots. For example, <pre> ArrayList!(int,MallocNoRoots) x; x.add(10,20,30); ... x.clear(); </pre> <a name="unmod"></a> <h3> Unmodifiable Containers </h3> The <tt>ReadOnly</tt> template parameter makes a container unmodifiable. A read-only container does not have operations that add or remove or change elements. However the underlying data is shared with the original modifiable container so a read-only container only guarantees that the elements will not be modified by that particular view of the container. A slice of a read-only container is also read-only. The <tt>readonly</tt> property creates a read-only view of a container. The <tt>readwrite</tt> property creates a read-write view. For example <pre> void foo(List!(int,ReadOnly) y) { ... } List!(int) x; x.add(10,20,30); foo(x.readonly); </pre> <a name="Examples"> <h3> Examples </h3> The source files have examples and unittests that one can use to get a feel for the behavior. The following example walks through some uses of MinTL: Create a list of the integers 0 through 10 <pre> List!(int) x; x.add(0,1,2,3,4,5,6,7,8,9,10); </pre> and print out the items 5 though 8 <pre> foreach(int val; x[5..9]) printf("%d ",val); </pre> to output <pre> 5 6 7 8 </pre> Assigning <tt>x</tt> to another variable <tt>y</tt> shares the underlying list contents, so assigning through <tt>y</tt> is reflected in <tt>x</tt>: <pre> List!(int) y = x; y[0] = 100; assert( x[0] == 100 ); </pre> When passing a container to a function that could add or remove elements from the container be sure to use "inout" parameters to be sure the original variable in the calling frame is properly updated. <p> <a name="API"> <h3> API Reference</h3> This section lists the public structs and functions in MinTL without detailed explanation. For more information see the documentation before the function or struct in the source file. Template functions are written as <pre> return-type fcn-name!(tmpl-param,...)(arg1, arg2,...); </pre> to mimic how it would appear in user code. The API is organized by module:<br> <dl> <dt><a href="#array">mintl.array</a> <dt><a href="#arrayheap">mintl.arrayheap</a> <dt><a href="#arraylist">mintl.arraylist</a> <dt><a href="#deque">mintl.deque</a> <dt><a href="#hashaa">mintl.hashaa</a> <dt><a href="#list">mintl.list</a> <dt><a href="#mem">mintl.mem</a> <dt><a href="#multiaa">mintl.multiaa</a> <dt><a href="#queue">mintl.queue</a> <dt><a href="#set">mintl.set</a> <dt><a href="#share">mintl.share</a> <dt><a href="#slist">mintl.slist</a> <dt><a href="#sortedaa">mintl.sortedaa</a> <dt><a href="#stack">mintl.stack</a> </dl> <a name="array"></a> <h4>mintl.array</h4> <dl> <dt>void <b>reserve</b>!(Value[])(inout Value[] x, size_t n); <dd>Reserve capacity for a dynamic array <dt>DArrayReverseIter <b>backwards</b>!(Value[])(Value[] x); <dd>Reverse dynamic array "foreach" traversal <dt>void <b>sort</b>!(Value[])(Value[] data, int delegate(Value* x, Value* y) cmp = null); <dd>Sort the array in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Value type is used. </dl> <a name="arrayheap"></a> <h4>mintl.arrayheap</h4> <dl> <dt>struct <b>ArrayHeap</b>(Value, Alloc = GCAllocator) <dd>A heap (complete binary tree) backed by an array. x[n] is greater than or equal to x[2*n+1] and x[2*n+2]. x[0] is the greatest item. An optional allocator can customize memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>Value[] <b>data</b>; <dd>Backing array <dt>size_t <b>length</b>; <dd>Return length of heap <dt>alias int delegate(Value* a, Value* b) <b>CompareFcn</b>; <dd>Signature of comparison functions <dt>void <b>compareFcn</b>(CompareFcn cmp); <dd>Set the comparison function <dt>bool <b>isEmpty</b> <dd>Return true if container is empty <dt>Value <b>opIndex</b>(size_t n); <dd>Return nth item where the head is item 0. <dt>void <b>opIndexAssign</b>(Value val, size_t n); <dd>Assign to the nth item <dt>Value[] <b>values</b>; <dd>Get heap contents as dynamic array slice of backing array <dt>void <b>add</b>(...); <dd>Add to heap <dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr); <dd>Add to heap using va_arg inpurs <dt>void <b>addTail</b>(Value v); <dd>Add to heap <dt>Value <b>takeHead</b>(); <dd>Remove and return first item (greatest item) <dt>void <b>removeHead</b>(); <dd>Remove first item (greatest item) <dt>Value* <b>lookup</b>(size_t n); <dd>Return a pointer to the nth item <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal by values <dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg); <dd>Foreach traversal by index-value pairs <dt>ArrayHeap <b>dup</b>; <dd>Duplicate array heap by duplicating backing array <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>int <b>opEquals</b>(ArrayHeap c); <dd>Test heap equality <dt>alias ArrayHeap <b>ContainerType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dd>Aliases for container types </dl> </dl> <a name="arraylist"></a> <h4>mintl.arraylist</h4> <dl> <dt>struct <b>ArrayList</b>(Value, bit ReadOnly = false, Alloc = GCAllocator) <dd>A list backed by an array. An ArrayList can also be used as a dynamic array with managed capacity. The backing array is resized when more space is required. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>Value[] <b>data</b>; <dd>Backing array <dt>mixin <b>MListCat</b>(ArrayList) <dd>Mixin <a href="#listcat">list catenation</a>. <dt>mixin <b>MListAlgo</b>(this,ArrayList) <dd>Mixin <a href="#listalgo">list algorithms</a>. <dt><b>MListCommon</b>(ArrayList) <dd>Implement common <a href="#listcomm">list members</a>. <dt>size_t <b>length</b> <dd>Read/write property to return or set the length of the list. <dt>size_t <b>capacity</b> <dd>Read/write property for the minimum capacity of the backing array. The capacity is the maximum number of elements the array can hold without requiring a reallocation of the backing array. <dt>Value[] <b>array</b>; <dd>Get list contents as dynamic array slice of the backing array assuming the list is contiguous. <dt>ArrayListReverseIter!(Value) <b>backwards</b>(); <dd>Backwards traversal for "foreach" <dt>ArrayList!(Value,true,Alloc) <b>readonly</b>; <dd>Property that returns a read-only view of the container. <dt>ArrayList!(Value,false,Alloc) <b>readwrite</b>; <dd>Property that returns a read-write view of the container. <dt>void <b>sort</b>(int delegate(Value* x, Value* y) cmp = null); <dd>Sort the list in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Value type is used. <dt>alias ArrayList <b>ContainerType</b>; <dt>alias ArrayList <b>SliceType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dt>alias ReadOnly <b>isReadOnly</b>; <dd>Aliases for container types </dl> </dl> <a name="deque"></a> <h4>mintl.deque</h4> <dl> <dt>struct <b>Deque</b>(Value, bit ReadOnly = false, Alloc = GCAllocator) <dd>A double-ended queue backed by a circular block-allocated array Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>mixin <b>MListCat</b>(Deque) <dd>Mixin <a href="#listcat">list catenation</a>. <dt>mixin <b>MListAlgo</b>(this,Deque) <dd>Mixin <a href="#listalgo">list algorithms</a>. <dt><b>MListCommon</b>(Deque) <dd>Implement common <a href="#listcomm">list members</a>. <dt>size_t <b>length</b>; <dd>Return length of deque. <dt>DequeReverseIter!(Value) <b>backwards</b>(); <dd>Backwards traversal for "foreach" <dt>Deque!(Value,true,Alloc) <b>readonly</b>; <dd>Property that returns a read-only view of the container. <dt>Deque!(Value,false,Alloc) <b>readwrite</b>; <dd>Property that returns a read-write view of the container. <dt>void <b>sort</b>(int delegate(Value* x, Value* y) cmp = null); <dd>Sort the list in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Value type is used. <dt>alias Deque <b>ContainerType</b>; <dt>alias Deque <b>SliceType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dt>alias ReadOnly <b>isReadOnly</b>; <dd>Aliases for container types </dl> </dl> <a name="hashaa"></a> <h4>mintl.hashaa</h4> <dl> <dt>struct <b>HashAA</b>(Key,Value,bit ReadOnly = false, Alloc = GCAllocator) <dd>An associative array linked by insertion order. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>void <b>add</b>(...); <dd>Add key-value pairs to array <dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr); <dd>Add using va_arg inpurs <dt>static HashAA <b>make</b>(...) <dd>Consruct a HashAA using add(...) <dt>size_t <b>length</b>; <dd>Return number of items in the array. <dt>bool <b>isEmpty</b> <dd>Return true if array is empty <dt>Value* <b>get</b>(Key key, bit throwOnMiss = false); <dd>Return a pointer to the value stored at the key. If the key is not in the array then null is returned or if throwOnMiss is true an exception is thrown. <dt>Value* <b>put</b>(Key key) <dd>Return a pointer to the value stored at the key and insert the key with value Value.init if the key is not in the array. <dt>bool <b>contains</b>(Key key) <dd>Returns true if the array contains the key <dt>bool <b>contains</b>(Key key, out Value value) <dd>Returns true if the array contains the key and sets the out value if present. <dt>Value <b>opIndex</b>(Key key); <dd>Return item with given key. Returns the default missing value if not present. <dt>void <b>opIndexAssign</b>(Value val, Key key); <dd>Assign a value to the given key <dt>Value <b>missing</b> <dd>Read/write property for the value to use on indexing a key not in the array. Defaults to Value.init <dt>HashAA <b>opSlice</b>(Key a, Key b); <dd>Slice from item a to b (exclusive) <dt>HashAA <b>opSlice</b>(HashAA a, HashAA b); <dd>Slice from first key in a to last key in b <dt>HashAA <b>head</b> <dd>Return one-item slice of the head <dt>HashAA <b>tail</b> <dd>Return one-item slice of the tail <dt>void <b>next</b>(int n = 1, int end = 0); <dd>Move the head and tail to the next item. If n is negative move to the previous item. If end <= 0 move the head of the slice and if end >= 0 move the tail of the slice. <dt>void <b>remove</b>(Key key); <dd>Remove a key from array if present. The node used for key is reused in future insert actions. <dt>Value <b>take</b>(Key key); <dd>Remove a key from array if present and return value. Returns the default missing value if the key was not present. <dt>void <b>remove</b>(HashAA subarray); <dd>Remove a slice from array <dt>Value[] <b>values</b>; <dd>Get values as a dynamic array. The values are in insertion order. <dt>Key[] <b>keys</b>; <dd>Get keys as a dynamic array. The keys are in insertion order. <dt>void <b>reserve</b>(size_t n); <dd>Reserve a capacity for the array <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal by values <dt>int <b>opApply</b>(int delegate(inout Key key, inout Value x) dg); <dd>Foreach traversal by key-value pairs <dt>int <b>opApply</b>(int delegate(inout HashAA n) dg); <dd>Foreach traversal by one-item slices <dt>HashAA <b>dup</b>; <dd>Duplicate array <dt>void <b>clear</b>; <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>void <b>trim</b>; <dd>Remove references to extra nodes kept for reuse <dt>int <b>opEquals</b>(HashAA c); <dd>Test array equality <dt>HashAAReverseIter!(Key,Value) <b>backwards</b>(); <dd>Backwards traversal for "foreach" <dt>HashAA <b>rehash</b>; <dd>Rehash array to be more efficient <dt>Value <b>value</b> <dd>Return value of a one-item slices <dt>Key <b>key</b>; <dd>Return key of a one-item slices <dt>HashAA!(Key,Value,true) <b>readonly</b>; <dd>Property that returns a read-only view of the container. <dt>HashAA!(Key,Value,false) <b>readwrite</b>; <dd>Property that returns a read-write view of the container. <dt>void <b>sort</b>(int delegate(Key* x, Key* y) cmp = null); <dd>Sort the HashAA in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Key type is used. Future insertions are added in insertion order at the end of the traversal order. <dt>alias HashAA <b>ContainerType</b>; <dt>alias HashAA <b>SliceType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias Key <b>IndexType</b>; <dt>alias ReadOnly <b>isReadOnly</b>; <dd>Aliases for container types </dl> </dl> <a name="list"></a> <h4>mintl.list</h4> <dl> <dt>struct <b>List</b>(Value, bit ReadOnly = false, Alloc = GCAllocator) <dd>A doubly-linked list. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>mixin <b>MListCat</b>(List) <dd>Mixin <a href="#listcat">list catenation</a>. <dt>mixin <b>MListAlgo</b>(this,List) <dd>Mixin <a href="#listalgo">list algorithms</a>. <dt><b>MListCommon</b>(List) <dd>Implement common <a href="#listcomm">list members</a>. <dt>size_t <b>length</b>; <dd>Return length of list. <dt>void <b>trim</b>; <dd>Remove references to extra nodes kept for reuse <dt>ListReverseIter!(Value) <b>backwards</b>(); <dd>Backwards traversal for "foreach" <dt>List!(Value,true,Alloc) <b>readonly</b>; <dd>Property that returns a read-only view of the container. <dt>List!(Value,false,Alloc) <b>readwrite</b>; <dd>Property that returns a read-write view of the container. <dt>void <b>sort</b>(int delegate(Value* x, Value* y) cmp = null); <dd>Sort the list in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Value type is used. <dt>alias List <b>ContainerType</b>; <dt>alias List <b>SliceType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dt>alias ReadOnly <b>isReadOnly</b>; <dd>Aliases for container types </dl> </dl> <p> <a name="clist"></a> <dl> <dt>struct <b>CircularList</b>(Value, bit ReadOnly = false, Alloc = GCAllocator) <dd>A circular doubly-linked list. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>mixin <b>MListCat</b>(CircularList) <dd>Mixin <a href="#listcat">list catenation</a>. <dt>mixin <b>MListAlgo</b>(this,CircularList) <dd>Mixin <a href="#listalgo">list algorithms</a>. <dt><b>MListCommon</b>(CircularList) <dd>Implement common <a href="#listcomm">list members</a>. <dt>size_t <b>length</b>; <dd>Return length of list. <dt>List <b>toList</b>; <dd>Return the list as a non-circular List <dt>void <b>rotate</b>(int n = 1); <dd>Rotate the list by n steps (backwards if n is negative) <dt>CircularListReverseIter!(Value) <b>backwards</b>(); <dd>Backwards traversal for "foreach" <dt>CircularList!(Value,true,Alloc) <b>readonly</b>; <dd>Property that returns a read-only view of the container. <dt>CircularList!(Value,false,Alloc) <b>readwrite</b>; <dd>Property that returns a read-write view of the container. <dt>alias CircularList <b>ContainerType</b>; <dt>alias List!(Value,Alloc) <b>SliceType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dt>alias ReadOnly <b>isReadOnly</b>; <dd>Aliases for container types </dl> </dl> <a name="mem"></a> <h4>mintl.mem</h4> <dl> <dt>void* <b>mallocWithCheck</b>(size_t s) <dd>Call std.c.stdlib.malloc and throw OutOfMemory if fails. <dt>void* <b>callocWithCheck</b>(size_t n, size_t s) <dd>Call std.c.stdlib.calloc and throw OutOfMemory if fails. <dt>void* <b>reallocWithCheck</b>(void* p, size_t s) <dd>Call std.c.stdlib.realloc and throw OutOfMemory if fails. <dt>void <b>dfree</b>(void* p) <dd>Call free. <dt>void* <b>gcMalloc</b>(size_t s) <dd>Call mallocWithCheck and register range with GC. <dt>void* <b>gcCalloc</b>(size_t n, size_t s) <dd>Call callocWithCheck and register range with GC. <dt>void* <b>gcRealloc</b>(void* p, size_t s) <dd>Call reallocWithCheck and register range with GC. <dt>void <b>gcFree</b>(void* p) <dd>Remove range and call free. <p> <a name="GCAlloc"> <dt>struct <b>GCAllocator</b></a> <dd>The default allocator that indicates the garbage collector should be used for memory management. <dt>struct <b>Malloc</b> <dd>An allocator that uses malloc for memory requests and registers blocks with the GC when requested by the container. <dt>struct <b>MallocNoRoots</b> <dd>An allocator that uses malloc for memory requests and ignores requests to register blocks with the GC. Use this allocator only when you know the container will not contain any roots. </dl> </dl> <a name="multiaa"></a> <h4>mintl.multiaa</h4> <dl> <dt>struct <b>MultiAA</b>!(Key,Value, ImplType = HashAA!(Key,Value[])) <dd>An associative array which allows keys to be repeated. Adapted from a customizable container type mapping keys to Value[]. <p> <dl> <dt>ImplType <b>impl</b> <dd>Read-write property holding the backing container <dt>void <b>add</b>(...); <dd>Add key-value pairs to the container <dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr); <dd>Add using va_arg inpurs <dt>static MultiAA <b>make</b>(...) <dd>Consruct a MultiAA using add(...) <dt>void <b>addItem</b>(Key key, Value item); <dd>Add item to container. <dt>size_t <b>length</b>; <dd>Return number of items in the container. <dt>bool <b>isEmpty</b> <dd>Return true if container is empty. <dt>Value[] <b>opIndex</b>(Key key); <dd>Return the values for a given key. <dt>void <b>remove</b>(Key key, Value value); <dd>Remove an item from the container if present. <dt>void <b>remove</b>(Key key); <dd>Remove all the values with a given key if present. <dt>Key[] <b>keys</b>; <dd>Get keys as a dynamic array. Duplicates are removed. <dt>Value[][] <b>values</b>; <dd>Get values as a dynamic array. <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal of items in the container. If an item is repeated it is passed multiple times consecutively to the delegate. <dt>int <b>opApply</b>(int delegate(inout Key key, inout Value x) dg); <dd>Foreach traversal of items in the container. If an item is repeated it is passed multiple times consecutively to the delegate. <dt>MultiAA <b>dup</b>; <dd>Duplicate container <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>int <b>opEquals</b>(MultiAA c); <dd>Test container equality <dt>alias MultiAA <b>ContainerType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias Key <b>IndexType</b>; <dt>alias ImplType <b>AdaptType</b>; <dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly; <dd>Aliases for container types </dl> <p> <a name="sortedmultiaa"></a> <dt>alias <b>SortedMultiAA</b>!(Key,Value) <dd>An alias for MultiAA!(Key,Value,SortedAA!(Key,Value[])) to implement a sorted multi-aa. </dl> <a name="queue"></a> <h4>mintl.queue</h4> <dl> <dt>struct <b>Queue</b>!(Value, ImplType = Deque!(Value)) <dd>A queue of items adapted from a customizable list container type. The default backing container is a Deque. <p> <dl> <dt>ImplType <b>impl</b> <dd>Read-write property holding the backing container. <dt>alias addTail <b>put</b>; <dd>Alias to add items to the tail of the queue. <dt>alias takeHead <b>take</b>; <dd>Alias to take items to the head of the queue. <dt>Value <b>peek</b> <dd>Return the head of the queue or Value.init if empty. <dt>mixin <b>MListCat</b>(Queue) <dd>Mixin <a href="#listcat">list catenation</a>. <dt>size_t <b>length</b>; <dd>Return length of queue. <dt>bool <b>isEmpty</b> <dd>Return true if container is empty <dt>Value <b>opIndex</b>(size_t n); <dd>Return nth item where the head is item 0. <dt>void <b>opIndexAssign</b>(Value val, size_t n); <dd>Assign to the nth item <dt>void <b>addTail</b>(Value v); <dd>Add to tail of queue <dt>void <b>addTail</b>(Queue v); <dd>Append v to tail of queue <dt>Value <b>takeHead</b>(); <dd>Remove and return first item <dt>void <b>removeHead</b>(); <dd>Remove first item <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal by values <dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg); <dd>Foreach traversal by index-value pairs <dt>Queue <b>dup</b>; <dd>Duplicate queue. <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>int <b>opEquals</b>(Queue c); <dd>Test queue equality <dt>int <b>opCmp</b>(Queue c); <dd>Compare queues <dt>alias Queue <b>ContainerType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dt>alias ImplType <b>AdaptType</b>; <dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly; <dd>Aliases for container types </dl> <p> <a name="arrayqueue"></a> <dt>alias <b>ArrayQueue</b>!(Value) <dd>An alias for Queue!(Value,ArrayList!(Value)) to adapt an ArrayList to the queue interface. <p> <a name="pqueue"></a> <dt>alias <b>PriorityQueue</b>!(Value) <dd>An alias for Queue!(Value,ArrayHeap!(Value)) to adapt an ArrayHeap to the queue interface. </dl> <a name="set"></a> <h4>mintl.set</h4> <dl> <dt>struct <b>Set</b>!(Value, ImplType = HashAA!(Value,uint)) <dd>A set of unique items adapted from a customizable container type mapping items to 0 or 1. The default backing container type is a builtin associative array. <p> <dl> <dt>ImplType <b>impl</b> <dd>Read-write property holding the backing container <dt>void <b>add</b>(...); <dd>Add items to set <dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr); <dd>Add using va_arg inpurs <dt>static Set <b>make</b>(...) <dd>Consruct a Set using add(...) <dt>void <b>addItem</b>(Value item); <dd>Add item to set <dt>size_t <b>length</b>; <dd>Return number of items in the set. <dt>bool <b>isEmpty</b> <dd>Return true if set is empty <dt>bool <b>opIndex</b>(Value item); <dd>Return true if the item is in the set <dt>void <b>remove</b>(Value item); <dd>Remove an item from the set if present <dt>Value[] <b>values</b>; <dd>Get items as a dynamic set. <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal of items in the set <dt>Set <b>dup</b>; <dd>Duplicate set <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>int <b>opEquals</b>(Set c); <dd>Test set equality <dt>alias Set <b>ContainerType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias ImplType <b>AdaptType</b>; <dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly; <dd>Aliases for container types </dl> <p> <a name="sortedset"></a> <dt>alias <b>SortedSet</b>!(Value) <dd>An alias for Set!(Value,SortedAA!(Value,uint)) to implement a sorted set. <p> <a name="multiset"></a> <dt>struct <b>MultiSet</b>!(Value, ImplType = HashAA!(uint,Value)) <dd>A set which allows items to be repeated. Adapted from a customizable container type mapping items to repeat counts. <p> <dl> <dt>ImplType <b>impl</b> <dd>Read-write property holding the backing container <dt>void <b>add</b>(...); <dd>Add items to set <dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr); <dd>Add using va_arg inpurs <dt>static MultiSet <b>make</b>(...) <dd>Consruct a MultiSet using add(...) <dt>void <b>addItem</b>(Value item); <dd>Add item to set <dt>size_t <b>length</b>; <dd>Return number of items in the set. <dt>bool <b>isEmpty</b> <dd>Return true if set is empty <dt>bool <b>opIndex</b>(Value item); <dd>Return true if the item is in the set <dt>void <b>remove</b>(Value item); <dd>Remove an item from the set if present <dt>Value[] <b>values</b>; <dd>Get items as a dynamic set. Duplicates are removed. <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal of items in the set. If an item is repeated it is passed multiple times consecutively to the delegate. <dt>MultiSet <b>dup</b>; <dd>Duplicate set <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>int <b>opEquals</b>(MultiSet c); <dd>Test set equality <dt>alias MultiSet <b>ContainerType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias ImplType <b>AdaptType</b>; <dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly; <dd>Aliases for container types </dl> <p> <a name="sortedmultiset"></a> <dt>alias <b>SortedMultiSet</b>!(Value) <dd>An alias for MultiSet!(Value,SortedAA!(Value,uint)) to implement a sorted multi-set. </dl> <a name="share"></a> <h4>mintl.share</h4> The mintl.share module is publically imported into all container modules and stores shared defintions. <dl> <dt>const bit <b>ReadOnly</b> = true; <dd>A named constant to improve the readability of code involving read-only containers. See the section on <a href="#unmod">unmodifiable containers</a> for examples. <dt>class <b>IndexOutOfBoundsException</b> : Exception <dd>Exception thrown when attempting to access an invalid index or key. Checks for invalid indices can be disabled using version=MinTLNoIndexChecking. <a name="listcat"> <dt>template <b>MListCatOperators</b>(List)</a> <dd>Concatenation routines to be mixed into the list-like containers <dl> <dt>void <b>add</b>(...); <dd>Add to list <dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr); <dd>Add using va_arg inpurs <dt>static List <b>make</b>(...) <dd>Consruct a List using add(...) <dt>void <b>addN</b>(uint n, Value v) <dd>Add the value n times to the list <dt>void <b>addBefore</b>(List.SliceType sublist, Value[] v) <dd>Insert the values in the dynamic array v before sublist <dt>void <b>addAfter</b>(List.SliceType sublist, Value[] v) <dd>Insert the values in the dynamic array v after sublist <dt>List <b>opCatAssign</b>(Value v); <dd>Concatenation operator this ~= v <dt>List <b>opCat</b>(Value v); <dd>Concatenation operator this ~ v. copies this <dt>List <b>opCat_r</b>(Value v); <dd>Concatenation operator v ~ this. copies this <dt>List <b>opCatAssign</b>(List v); <dd>Concatenation operator this ~= v. copies v <dt>List <b>opCat</b>(List v); <dd>Concatenation operator this ~ v. copies both arguments </dl> <a name="listalgo"> <dt>template <b>MListAlgo</b>(Container, alias list)</a> <dd>List algorithms to be mixed into the list-like containers <dl> <dt>Container.SliceType <b>opIn</b>(Value v); <dd>Return a one-item slice of the first occurrence of v in the list. <dt>Container.SliceType <b>find</b>(int delegate(inout Value v) dg); <dd>Return a one-item slice of the first occurrence where dg is true. <dt>uint <b>count</b>(Value v); <dd>Return the number of time v appears in the list. <dt>void <b>swap</b>(Container v); <dd>Swap the contents of the list with v (assumes non-overlapping). Extra elements are ignored. <dt>void <b>fill</b>(Value v); <dd>Fill the container with v <dt>void <b>copy</b>(Container v); <dd>Copy the contents of v to this container. Extra elements are ignored. </dl> <a name="listcomm"> <dt><b>MListCommon</b>(Container)</a> <dd>Common list routines <dl> <dt>bool <b>isEmpty</b> <dd>Return true if container is empty <dt>Value <b>opIndex</b>(size_t n); <dd>Return nth item where the head is item 0. <dt>void <b>opIndexAssign</b>(Value val, size_t n); <dd>Assign to the nth item <dt>Container.SliceType <b>opSlice</b>(size_t a, size_t b); <dd>Slice from item a to b (exclusive) <dt>Container.SliceType <b>opSlice</b>(Container.SliceType a, Container.SliceType b); <dd>Slice from head of a to tail of b <dt>Container.SliceType <b>head</b> <dd>Read-only property to get a one-item slice of the head. <dt>Container.SliceType <b>tail</b> <dd>Read-only property to get a one-item slice of the tail. <dt>Value[] <b>values</b>; <dd>Get list contents as dynamic array. <dt>Value <b>value</b>; <dd>Read/write property for the value of a one-item slice. <dt>void <b>addTail</b>(Value v); <dd>Add to tail of list <dt>void <b>addTail</b>(Container v); <dd>Copy v to tail of list <dt>void <b>addHead</b>(Value v); <dd>Add to head of list <dt>void <b>addHead</b>(Container v); <dd>Copy v to head of list <dt>Value <b>takeTail</b>(); <dd>Remove and return last item <dt>Value <b>takeHead</b>(); <dd>Remove and return first item <dt>void <b>removeTail</b>(); <dd>Remove last item <dt>void <b>removeHead</b>(); <dd>Remove first item <dt>void <b>remove</b>(Container.SliceType sublist); <dd>Remove sublist from list <dt>void <b>addBefore</b>(Container.SliceType subv, Container.SliceType v); <dd>Insert v before subv. <dt>void <b>addAfter</b>(Container.SliceType subv, Container.SliceType v); <dd>Insert v after subv. <dt>void <b>next</b>(int n = 1, int end = 0); <dd>Move the head and tail to the next item. If n is negative move to the previous item. If end <= 0 move the head of the slice and if end >= 0 move the tail of the slice. <dt>Value* <b>lookup</b>(size_t n); <dd>Return a pointer to the nth item <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal by values <dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg); <dd>Foreach traversal by index-value pairs <dt>int <b>opApply</b>(int delegate(inout Container.SliceType n) dg); <dd>Foreach traversal by one-item slices <dt>Container <b>reverse</b>; <dd>Reverse list in-place. <dt>Container <b>dup</b>; <dd>Duplicate array list by duplicating backing array <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>int <b>opEquals</b>(Container c); <dd>Test list equality <dt>int <b>opCmp</b>(Container c); <dd>Compare lists </dl> </dl> <a name="slist"></a> <h4>mintl.slist</h4> <dl> <dt>struct <b>SList</b>(Value, bit ReadOnly = false, Alloc = GCAllocator) <dd>A singly-linked list. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>mixin <b>MListCat</b>(SList) <dd>Mixin <a href="#listcat">list catenation</a>. <dt>size_t <b>length</b>; <dd>Return length of list. <dt>bool <b>isEmpty</b> <dd>Return true if container is empty <dt>SList <b>tailList</b>; <dd>Return the tail of the list as a slice <dt>Value <b>opIndex</b>(size_t n); <dd>Return nth item where the head is item 0. <dt>void <b>opIndexAssign</b>(Value val, size_t n); <dd>Assign to the nth item <dt>SList <b>opSlice</b>(size_t a, size_t b); <dd>Slice from item a to b (exclusive) <dt>SList <b>opSlice</b>(SList a, SList b); <dd>Slice from head of a to tail of b <dt>SList <b>head</b> <dd>Read-only property to get a one-item slice of the head. <dt>SList <b>tail</b> <dd>Read-only property to get a one-item slice of the tail. <dt>Value <b>value</b> <dd>Read/write property for the value of a one-item slice. <dt>Value[] <b>values</b>; <dd>Get list contents as dynamic array. <dt>void <b>addTail</b>(Value v); <dd>Add to tail of list <dt>void <b>addTail</b>(SList v); <dd>Append v to tail of list <dt>void <b>addHead</b>(Value v); <dd>Add to head of list <dt>void <b>addHead</b>(SList v); <dd>Prepend v to head of list <dt>Value <b>takeHead</b>(); <dd>Remove and return first item <dt>void <b>removeHead</b>(); <dd>Remove first item <dt>void <b>addAfter</b>(SList subv, SList v); <dd>Insert v after subv. <dt>void <b>removeAfter</b>(SList sublist, size_t n=1); <dd>Remove n items following sublist <dt>void <b>removeBetween</b>(SList a, SList b); <dd>Remove items after the tail of a to the head of b (exclusive) <dt>void <b>next</b>(int n = 1, int end = 0); <dd>Move the head and tail to the next item. If n is negative move to the previous item. If end <= 0 move the head of the slice and if end >= 0 move the tail of the slice. <dt>Value* <b>lookup</b>(size_t n); <dd>Return a pointer to the nth item <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal by values <dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg); <dd>Foreach traversal by index-value pairs <dt>int <b>opApply</b>(int delegate(inout SList n) dg); <dd>Foreach traversal by one-item slices <dt>SList <b>dup</b>; <dd>Duplicate list <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>void <b>trim</b>; <dd>Remove references to extra nodes kept for reuse <dt>int <b>opEquals</b>(SList c); <dd>Test list equality <dt>int <b>opCmp</b>(SList c); <dd>Compare lists <dt>mixin <b>MListAlgo</b>(this,SList) <dd>Mixin <a href="#listalgo">list algorithms</a>. <dt>SList!(Value,true,Alloc) <b>readonly</b>; <dd>Property that returns a read-only view of the container. <dt>SList!(Value,false,Alloc) <b>readwrite</b>; <dd>Property that returns a read-write view of the container. <dt>alias SList <b>ContainerType</b>; <dt>alias SList <b>SliceType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dt>alias ReadOnly <b>isReadOnly</b>; <dd>Aliases for container types </dl> </dl> <p> <a name="cslist"></a> <dl> <dt>struct <b>CircularSList</b>(Value, bit ReadOnly = false, Alloc = GCAllocator) <dd>A circular singly-linked list. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>mixin <b>MListCat</b>(CircularSList) <dd>Mixin <a href="#listcat">list catenation</a>. <dt>size_t <b>length</b>; <dd>Return length of list. <dt>bool <b>isEmpty</b> <dd>Return true if container is empty <dt>SList <b>toSList</b>; <dd>Return the list as a non-circular SList <dt>Value <b>opIndex</b>(size_t n); <dd>Return nth item where the head is item 0. <dt>void <b>opIndexAssign</b>(Value val, size_t n); <dd>Assign to the nth item <dt>SList <b>opSlice</b>(size_t a, size_t b); <dd>Slice from item a to b (exclusive) <dt>SList <b>opSlice</b>(SList a, SList b); <dd>Slice from head of a to tail of b <dt>SList <b>head</b> <dd>Read-only property to get a one-item slice of the head. <dt>SList <b>tail</b> <dd>Read-only property to get a one-item slice of the tail. <dt>Value <b>value</b> <dd>Read/write property for the value of a one-item slice. <dt>void <b>addTail</b>(Value v); <dd>Add to tail of list <dt>void <b>addTail</b>(CircularSList v); <dd>Append v to tail of list <dt>void <b>addHead</b>(Value v); <dd>Add to head of list <dt>void <b>addHead</b>(CircularSList v); <dd>Prepend v to head of list <dt>Value <b>takeHead</b>(); <dd>Remove and return first item <dt>void <b>removeHead</b>(); <dd>Remove first item <dt>void <b>addAfter</b>(SList subv, SList v); <dd>Insert v after subv. <dt>void <b>removeAfter</b>(SList sublist, size_t n=1); <dd>Remove n items following sublist <dt>void <b>removeBetween</b>(SList a, SList b); <dd>Remove items after the tail of a to the head of b (exclusive) <dt>void <b>rotate</b>(int n = 1); <dd>Rotate the list by n steps <dt>Value* <b>lookup</b>(size_t n); <dd>Return a pointer to the nth item <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal by values <dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg); <dd>Foreach traversal by index-value pairs <dt>int <b>opApply</b>(int delegate(inout SList n) dg); <dd>Foreach traversal by one-item slices <dt>CircularSList <b>dup</b>; <dd>Duplicate list <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>int <b>opEquals</b>(CircularSList c); <dd>Test list equality <dt>int <b>opCmp</b>(CircularSList c); <dd>Compare lists <dt>mixin <b>MListAlgo</b>(this,CircularSList) <dd>Mixin <a href="#listalgo">list algorithms</a>. <dt>CircularSList!(Value,true,Alloc) <b>readonly</b>; <dd>Property that returns a read-only view of the container. <dt>CircularSList!(Value,false,Alloc) <b>readwrite</b>; <dd>Property that returns a read-write view of the container. <dt>alias CircularAList <b>ContainerType</b>; <dt>alias SList!(Value,Alloc) <b>SliceType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dt>alias ReadOnly <b>isReadOnly</b>; <dd>Aliases for container types </dl> </dl> <a name="sortedaa"></a> <h4>mintl.sortedaa</h4> <dl> <dt>class <b>CompareFcnSetException</b>: Exception; <dd>Exception thrown when trying to set the comparison function of a non-empty array or an array that already had the comparison function set. </dl> <p> <dl> <dt>struct <b>SortedAA</b>(Key, Value, bit ReadOnly = false, Alloc = GCAllocator) <dd>A sorted associative array The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is <a href="#GCAlloc">GCAllocator</a>. <p> <dl> <dt>alias int delegate(Key* a, Key* b) <b>CompareFcn</b>; <dd>Signature of comparison functions <dt>void <b>compareFcn</b>(CompareFcn cmp); <dd>Set the comparison function <dt>void <b>add</b>(...); <dd>Add key-value pairs to array <dt>void <b>vadd</b>(TypeInfo[] ti, void* argptr); <dd>Add using va_arg inpurs <dt>static SortedAA <b>make</b>(...) <dd>Consruct a SortedAA using add(...) <dt>size_t <b>length</b>; <dd>Return number of items in the array. <dt>bool <b>isEmpty</b> <dd>Return true if array is empty <dt>Value* <b>get</b>(Key key, bit throwOnMiss = false); <dd>Return a pointer to the value stored at the key. If the key is not in the array then null is returned or if throwOnMiss is true an exception is thrown. <dt>Value* <b>put</b>(Key key) <dd>Return a pointer to the value stored at the key and insert the key with value Value.init if the key is not in the array. <dt>bool <b>contains</b>(Key key) <dd>Returns true if the array contains the key <dt>bool <b>contains</b>(Key key, out Value value) <dd>Returns true if the array contains the key and sets the out value if present. <dt>Value <b>opIndex</b>(Key key); <dd>Return item with given key. Returns the default missing value if not present. <dt>void <b>opIndexAssign</b>(Value val, Key key); <dd>Assign a value to the given key <dt>Value <b>missing</b> <dd>Read/write property for the value to use on indexing a key not in the array. Defaults to Value.init <dt>SortedAA <b>head</b>() <dd>Return one-item slice of the smallest item <dt>SortedAA <b>tail</b>() <dd>Return one-item slice of the greatest item <dt>void <b>next</b>(int n = 1, int end = 0); <dd>Move the head and tail to the next item. If n is negative move to the previous item. If end <= 0 move the head of the slice and if end >= 0 move the tail of the slice. <dt>SortedAA <b>from</b>(Key a); <dd>Return a one-item slice of the smallest item greater than or equal to a. <dt>SortedAA <b>to</b>(Key b); <dd>Return a one-item slice of the greatest item smaller than b. <dt>SortedAA <b>opSlice</b>(Key a, Key b); <dd>Slice from item a to b (exclusive). <dt>SortedAA <b>opSlice</b>(SortedAA a, SortedAA b); <dd>Slice from first key in a to last key in b. <dt>Value <b>take</b>(Key key); <dd>Remove a key from array if present and return value. Returns the default missing value if the key was not present. <dt>void <b>remove</b>(Key key); <dd>Remove a key from array if present. <dt>void <b>remove</b>(SortedAA subarray); <dd>Remove a slice from array. <dt>void <b>trim</b>; <dd>Remove references to extra nodes kept for reuse <dt>Value[] <b>values</b>; <dd>Get values as a dynamic array. The values are in order. <dt>Key[] <b>keys</b>; <dd>Get keys as a dynamic array. The keys are in order. <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal by values <dt>int <b>opApply</b>(int delegate(inout Key key, inout Value x) dg); <dd>Foreach traversal by key-value pairs <dt>int <b>opApply</b>(int delegate(inout SortedAA n) dg); <dd>Foreach traversal by one-item slices <dt>SortedAA <b>dup</b>; <dd>Duplicate array <dt>void <b>clear</b>() <dd>Clear contents. Only needed if a non-GCAllocator is used. <dt>int <b>opEquals</b>(SortedAA c); <dd>Test array equality <dt>SortedAAReverseIter!(Key,Value) <b>backwards</b>(); <dd>Backwards traversal for "foreach" <dt>Value <b>value</b>; <dd>Return value of a one-item slices <dt>Key <b>key</b>; <dd>Return key of a one-item slices <dt>SortedAA!(Key,Value,true,Alloc) <b>readonly</b>; <dd>Property that returns a read-only view of the container. <dt>SortedAA!(Key,Value,false,Alloc) <b>readwrite</b>; <dd>Property that returns a read-write view of the container. <dt>alias SortedAA <b>ContainerType</b>; <dt>alias SortedAA <b>SliceType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias Key <b>IndexType</b>; <dd>Aliases for container types </dl> </dl> <a name="stack"></a> <h4>mintl.stack</h4> <dl> <dt>struct <b>Stack</b>!(Value, ImplType = Deque!(Value)) <dd>A stack of items adapted from a customizable list container type. The default backing container is a Deque. <p> <dl> <dt>ImplType <b>impl</b> <dd>Read-write property holding the backing container. <dt>alias addTail <b>push</b>; <dd>Alias to add items to the tail of the stack. <dt>alias takeTail <b>pop</b>; <dd>Alias to take items from the tail of the stack. <dt>Value <b>peek</b> <dd>Return the top of the stack or Value.init if empty. <dt>mixin <b>MListCat</b>(Stack) <dd>Mixin <a href="#listcat">list catenation</a>. <dt>size_t <b>length</b>; <dd>Return length of stack. <dt>bool <b>isEmpty</b> <dd>Return true if container is empty <dt>Value <b>opIndex</b>(size_t n); <dd>Return nth item where the head is item 0. <dt>void <b>opIndexAssign</b>(Value val, size_t n); <dd>Assign to the nth item <dt>void <b>addTail</b>(Value v); <dd>Add to tail of stack <dt>void <b>addTail</b>(Stack v); <dd>Append v to tail of stack <dt>Value <b>takeHead</b>(); <dd>Remove and return first item <dt>void <b>removeHead</b>(); <dd>Remove first item <dt>int <b>opApply</b>(int delegate(inout Value x) dg); <dd>Foreach traversal by values <dt>int <b>opApply</b>(int delegate(inout size_t n, inout Value x) dg); <dd>Foreach traversal by index-value pairs <dt>Stack <b>dup</b>; <dd>Duplicate stack. <dt>int <b>opEquals</b>(Stack c); <dd>Test stack equality <dt>int <b>opCmp</b>(Stack c); <dd>Compare stacks <dt>alias Stack <b>ContainerType</b>; <dt>alias Value <b>ValueType</b>; <dt>alias size_t <b>IndexType</b>; <dt>alias ImplType <b>AdaptType</b>; <dt>const bit <b>isReadOnly</b> = ImplType.isReadOnly; <dd>Aliases for container types </dl> <p> <a name="arraystack"></a> <dt>alias <b>ArrayStack</b>!(Value) <dd>An alias for Stack!(Value,ArrayList!(Value)) to adapt an ArrayList to the stack interface. </dl> </BODY> </HTML>