Mercurial > projects > aid

view trunk/mintl/index.html @ 1:5dd9f598bcd8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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>