MinTL

MinTL is a "minimal template library" of containers for the D programming language. For more info about D see DigitalMars D home page. The downloads are the Core Library and the MinTL Concurrent Library (mintlc web page), which includes a dependent Synchronization Library. The current version is 2.7.1.

This library is in the public domain. Written by Ben Hinkle, 2004. Email comments and bug reports to ben.hinkle@gmail.com

Contents

Overview
List Containers
Associative Containers
Slicing
Foreach traversals
Sorting
Allocators
Unmodifiable Containers
Examples
API Reference by module

Overview

The philosophy of the library is to be as simple and minimal as possible:
  • The design is simple by keeping the number of classes to a minimum and reusing concepts from builtin dynamic and associative arrays. For example a slice of a container has the same type as the container, just as the slice of a dynamic array is another dynamic array.
  • The memory footprint and the garbage generation is kept to a minimum by relying on structs instead of classes and by implementing slicing and traversals without allocating dynamic memory. Some containers also recycle nodes. For example when the head or tail of a list is removed the node is retained and reused the next time an item is added to the head or tail. Optional Allocator parameters allow custom memory management.
  • Closely related data structures share common naming conventions and adapters reuse fundamental data structures like arrays, linked-lists and sorted associative arrays for stacks, queues and sets. Performance can be tuned for different uses by either choose between several variations (eg. a linked list, a circular array or a deque) or by supplying optional constructor arguments.

    MinTL has the following containers

    List containers
    container implementation file brief
    List doubly linked list list.d sortable linked list with "previous" and "next" pointers
    CircularList circular doubly linked list list.d doubly linked list where the head and tail are linked
    SList singly linked list slist.d linked list with only "next" pointers
    CircularSList circular singly linked list slist.d singly linked list where the tail points to the head
    ArrayList circular array arraylist.d sortable list backed by a resizable circular array
    Deque circular block-allocated array deque.d list backed by a resizable block-allocated circular array
    ArrayHeap heap arrayheap.d complete binary tree backed by an array
    Stack adapter stack.d adapts a list container to be a stack
    ArrayStack ArrayList stack.d wraps an ArrayList with the stack adapter
    Queue adapter queue.d adapts a list container to be a queue
    ArrayQueue ArrayList queue.d wraps an ArrayList with the queue adapter
    PriorityQueue ArrayHeap queue.d wraps an ArrayHeap with the queue adapter

    Associative containers
    container implementation file brief
    HashAA linked hash table hashaa.d sortable associative array with nodes ordered by insertion order
    SortedAA red-black tree sortedaa.d sorted associative array
    Set adapter set.d adapts an associative container to be a set
    SortedSet SortedAA set.d wraps a SortedAA with the set adapter
    MultiSet adapter set.d adapts an associative container to be a set with repeats
    SortedMultiSet SortedAA set.d wraps a SortedAA with the multi-set adapter
    MultiAA adapter multiaa.d adapts an associative container to hold repeated keys
    SortedMultiAA SortedAA multiaa.d wraps a SortedAA with the multi-aa adapter

    The module mintl.array defines helper functions for builtin dynamic and associative arrays.

    Build and Install

    To use MinTL first unpack the library in a directory on the D compiler search path. There are pre-built debug and non-debug versions of the library. To enable flexible add() datatype support uncomment the version=WithBox statement in mintl.share and recompile MinTL. To use std.boxer in a debug build you must also rebuild phobos with debugging. If you wish to rebuild MinTL enter the mintl directory and type make -f win32.mak or make -f linux.mak. In your source code import the desired modules and compile each container used and the mintl static library into the application. If a concurrent container is needed download the mintlc sub-package and link that library and the Locks library into the application. For example on Linux to compile the program app.d
    import mintl.list;
    
    int main() {
      List!(int) list = List!(int).make(10,20,30);
      return 0;
    }
    
    run in the directory above mintl the command
      dmd app.d mintl/libmintl_debug.a
    
    to build with asserts or
      dmd app.d -release mintl/libmintl.a
    
    to build without asserts. On Windows run
      dmd app.d mintl\mintl_debug.lib
    
    or
      dmd app.d -release mintl\mintl.lib
    
    If the mintl directory is not in the current directory then use the -I flag to add it to the search path
      dmd app.d -Ipath_to_mintl path_to_mintl/mintl/libmintl.a
    
    or modify the dmd\bin\sc.ini file (on Windows) or dmd.conf (on Linux) to include the paths to mintl. For example if MinTL is unpacked in the directory C:\d on Windows then sc.ini should be modified to include C:\d in the include path and C:\d\mintl on the library search path:
    LIB="%@P%\..\lib";\dm\lib;C:\d\mintl
    DFLAGS="-I%@P%\..\src\phobos";C:\d
    
    On Linux the static library can be put in a standard location like /usr/lib if desired.

    List Containers

    The list containers List, SList, CircularList, CircularSList, ArrayList, Deque, ArrayHeap and the concurrent queues and stacks share a naming convention for adding and removing items. The head is the first item in the container and the tail is the last item. All list containers support constant-time access to the head and tail. The speed of accessing the length property depends on the container. Array-based containers have constant-time access to length, the linked-list containers have constant-time unless an operation modifies the list to have unknown length, in which case the next time the length is computed it is cached again. The singly-linked lists have linear-time length access and it is not cached.

    Some containers maintain nodes past the head and tail of the list as extra capacity. To trim off any extra capacity most containers support a trim function.

    The circular lists CircularList and CircularSList are the same as the non-circular versions except that slicing a circular list returns a non-circular list and node are not reused when adding or removing items. However circular lists are useful when the objects being modeled do not have a natural unique definition of a head or tail.

    An ArrayList can also be used as a dynamic array with managed capacity. Set the capacity property or allocate an array with the desired capacity and leave the head of the arraylist at 0. The arraylist will automatically grow the capacity as required.

    To add items to a container call add with any number of items. For example

      List!(int) x,y,z;
      y.add(10,20,30);
      z.add(50,60,70);
      x = y; x ~= 40; x ~= z; x ~= 80;
    
    results in the following linked list
     x[0],y[0]           y[2]              z[0]              z[2]     x[7]
        10  <->  20  <->  30  <->  40  <->  50  <->  60  <->  70  <->  80
    
    To add a single item or list call addTail or use one of the concatenation operators. Some containers also support adding items or lists at the head using addHead or at a position in the interior of the list using addBefore or addAfter. To create a list in an expression use the static make function For example,
      List!(int) x;
      x = List!(int).make(10,20,30) ~ List!(int).make(50,60,70);
    

    To remove items call one of the take or remove functions. All list containers support removeHead to remove the head of the list and takeHead to remove and return the stored value, if any. Some containers also support takeTail and removeTail to remove the tail and remove to remove a slice.

    Stacks and queues are implemented as adapters of a list container. By default they use a Deque as the backing container. Stacks define aliases push for add and pop for takeTail. Queues define an alias take for takeHead (the function add is used to add to the end of a queue). For example,

      Stack!(char[]) x;
      x.push("first","second");
      assert( x.pop == "second" );
      assert( x.pop == "first" );
    
      Queue!(char[]) x;
      x.add("first","second");
      assert( x.take == "first" );
      assert( x.take == "second" );
    
    A PriorityQueue is an ArrayHeap wrapped with the Queue adapter. To set a custom comparison function access the impl property of the adapter:
      PriorityQueue!(char[]) x;
      x.impl.compareFcn = &fcn;
      x.add("first","second");
    

    The following table outlines the advantages and disadvantages of each list container
    container advantages disadvantages
    List O(1) insertion at head/tail or before/after slices O(n) access to middle of list
    SList O(1) insertion at head/tail or after slices; less overhead than List O(n) access to middle or near end of list
    ArrayList O(1) insertion at head/tail. O(1) access to any index O(n) insertion in middle
    Deque O(1) insertion at head/tail. O(1) access to any index. Block allocated. O(n) insertion in middle; non-contiguous storage
    ArrayHeap maintains items in semi-sorted order; O(log(n)) add/remove. only allows addTail and takeHead

    Associative Containers

    The associative containers SortedAA,HashAA, and ConcurrentAA are similar to builtin associative arrays but with extra capabilities. The SortedAA maintains the keys in some specific order as determined by a comparison function. By default the keys are ordered by the type's default comparison function. To specify a custom comparison function assign to the compareFcn property. The HashAA maintains the keys in insertion order, meaning if an indexing expression using key x is evaluated before an indexing expression using key y then x is traversed before y in foreach traversals. Assigning to a key already in the array does not change the insertion order. The other associative array properties dup, length, keys and values are also implemented.

    Elements are inserted or modified using the add function or using indexing lvalue expressions and retrieved using indexing rvalue expressions. To test if a key is in the array use the overloaded contains functions. An indexing expression that is not an assignment will return a default missing value. The missing value defaults to Value.init but can be set by assigning to the missing property. The functions get and put allow more flexibility in handling missing keys by allowing the user to either return null, throw or insert. To remove an item call the remove function. Both HashAA and SortedAA maintain a freelist of removed nodes for future reuse. To release the freelist for garbage collection call trim.

    For example to define a sorted associative array with three entries associating "first" with 10, "second" with 20 and "third" with 30 type

      SortedAA!(int,char[]) x;
      x.add(10,"first", 20,"second", 30,"third");
    
    or equivalently,
      SortedAA!(int,char[]) x;
      x[10] = "first";
      x[20] = "second";
      x[30] = "third";
    
    To create an associative array in an expression use the static make function For example,
      foo(SortedAA!(int,char[]).make(10,"first",20,"second",30,"third"));
    

    The number of elements in an associative container is computed by the length property.

    Sets and multi-associative-arrays are implemented as adapters of an associative container. By default sets use a HashAA as the backing container. Use add to add items to a set and use an indexing expression to check if an item is in the set. For example,

      Set!(char[]) x;
      x.add("first","second","third");
      assert( x["first"] );
      assert( x["second"] );
      assert( x["third"] );
      assert( !x["fourth"] );
    
      MultiSet!(char[]) mx;
      xm.add("first","second","first","third","second");
      xm.remove("first");
      assert( x["first"] );
    
      MultiAA!(int,char[]) y;
      y.add(10,"first",20,"second",10,"third");
      assert( y[10].length == 2 );
    

    Slicing

    In general slicing a container behaves like slicing a dynamic array. For example, slicing between two indices in a List creates another List with the head at the first index and the tail at the element before the second index. The contents of the slice is shared with the original list so assigning new values to elements in the list will be visible in the oringal list. The resulting slice, or sub-list, can be traversed using "foreach", duplicated, indexed into, etc just like a slice of a dynamic array can be treated as a "first-class" dyamic array. The following diagram illustrates the relationships for x and y if x is a list with 6 items and y is the slice x[2..4].
       x[0]            y[0]    y[1]           x[5]
        0  <->  1  <->  2  <->  3  <->  4  <->  5
    
    Executing z = y.dup would result in
       z[0]    z[1]
        2  <->  3 
    

    One should be careful when resizing or writing to a slice. For example do not (in general) append or prepend item to a sub-list using the addTail or addHead functions or remove items using removeTail and removeHead unless the original list is no longer needed. To insert an item or list at a certain location create a slice with the head at the desired location and call addBefore or create a slice with the tail at the desired location and call addAfter. To remove a portion of a list create a slice and call remove. Again one should always insert and remove from the original list otherwise any variable referring to the original list will become out of sync.

    A sub-list can be moved towards the head or tail of the original list by calling the next function. This allows a sub-list to traverse up and down the original list efficiently. Continuing the example from above, executing y.next(-1) would result in

       x[0]    y[0]    y[1]                   x[5]
        0  <->  1  <->  2  <->  3  <->  4  <->  5
    
    and then executing x.remove(y) would result in
       x[0]                    x[3]
        0  <->  3  <->  4  <->  5
    
       y[0]    y[1]
        1  <->  2 
    
    The performance of inserting and removing from the interior of an ArrayList or Deque can be significantly worse than that of a List if the slices are near the middle of the container.

    The SortedAA slicing behavior is designed to chose slices without modifying the underlying container. The functions from and to can find a one-item slice starting from or up to a given key. For example if words is a sorted associative array indexed by char[] then

        words["a" .. "b"]
    
    or, equivalently,
        words[words.from("a") .. words.to("b")]
    
    is a slice containing all the items with keys that start with the character "a" even if the strings "a" and "b" aren't in the container.

    Foreach

    Containers and slices of containers can be traversal in foreach statements by value, key-value pairs and one-element slices. Some containers support moving a slice up and down the container. For these containers a slice can be used for the same purposes as an iterator in C++ or Java.

    Each container also supports backwards traversals by calling backwards in a foreach statement. For example,

      List!(int) x;
      ...
      foreach( int val; x.backwards() )
        printf("%d ",val);
    
    will print out the contents of x from tail to head. Backwards traversals do not allocate any dynamic memory.

    Sorting

    MinTL supports sorting containers in two forms. The SortedAA is a sorted associative container that maintains its elements in a given sorted order at all times. The comparison delegate used to determine the element order must be specified before the first element is insert or the key's default comparison function will be used and it cannot be changed during the lifetime of the container. The SortedSet and SortedMultiAA are derived from SortedAA and have the same sorting semantics.

    The other form of sorting is through calling the sort methods of the containers ArrayList, Deque, List, and HashAA or by using the sort template in mintl.array to sort a dynamic array. These sort methods take an optional comparison delegate. The default comparison delegate is the sorting type's default comparison function. For the list-like containers the sorting type is the value type of the container. For HashAA the sorting type is the key type. Sorting is done in-place and slices are preserved relative to their surrounding container. For example, the following code creates a short linked list, sorts and slice and compares it with the expected end result:

        List!(int) list;
        list.add(40,300,-20,100,400,200);
        list[1 .. 5].sort();    // sort a slice in-place
        assert( list == List!(int).make(40,-20,100,300,400,200));
    

    Sorting a container does not change the behavior of adding new elements. The sorting operation is performed once and the comparison function is not remembered by the container or used in any other way. For example sorting a HashAA which was previously maintained in insertion order will sort the elements but adding any new elements will add them to the end of the traversal order in insertion order again.

    Allocators

    Most containers accept an optional Allocator parameter to customize memory management. The default allocator is the GCAllocator which indicates to the container that the garbage collector should be used for all allocations. If a custom allocator is supplied the container will call the memory management functions in the allocator to allocate and free memory. Users who supply a non-garbage-collecting allocator need to call clear when done with a container so that the memory can be released.

    An allocator is a type containing 8 symbols malloc, calloc, realloc, free and the corresponding GC-aware versions gcMalloc, gcCalloc, gcRealloc and gcFree. Containers will call the GC-aware functions on blocks that may hold roots and otherwise will call the regular functions. Allocators are expected to throw an OutOfMemory exception if the allocation fails.

    The two predefined allocators Malloc and MallocNoRoots use std.c.stdlib.malloc to perform allocations. The MallocNoRoots ignores any requests by the container to register roots with the GC. The MallocNoRoots allocator should only be used with containers that the user knows will never contain any roots. For example,

      ArrayList!(int,MallocNoRoots) x;
      x.add(10,20,30);
      ...
      x.clear();
    

    Unmodifiable Containers

    The ReadOnly template parameter makes a container unmodifiable. A read-only container does not have operations that add or remove or change elements. However the underlying data is shared with the original modifiable container so a read-only container only guarantees that the elements will not be modified by that particular view of the container. A slice of a read-only container is also read-only. The readonly property creates a read-only view of a container. The readwrite property creates a read-write view. For example
      void foo(List!(int,ReadOnly) y) { ... }
      List!(int) x;
      x.add(10,20,30);
      foo(x.readonly);
    

    Examples

    The source files have examples and unittests that one can use to get a feel for the behavior. The following example walks through some uses of MinTL: Create a list of the integers 0 through 10
      List!(int) x;
      x.add(0,1,2,3,4,5,6,7,8,9,10);
    
    and print out the items 5 though 8
      foreach(int val; x[5..9])
        printf("%d ",val);
    
    to output
      5 6 7 8
    
    Assigning x to another variable y shares the underlying list contents, so assigning through y is reflected in x:
      List!(int) y = x;
      y[0] = 100;
      assert( x[0] == 100 );
    
    When passing a container to a function that could add or remove elements from the container be sure to use "inout" parameters to be sure the original variable in the calling frame is properly updated.

    API Reference

    This section lists the public structs and functions in MinTL without detailed explanation. For more information see the documentation before the function or struct in the source file. Template functions are written as
     return-type fcn-name!(tmpl-param,...)(arg1, arg2,...);
    
    to mimic how it would appear in user code. The API is organized by module:
    mintl.array
    mintl.arrayheap
    mintl.arraylist
    mintl.deque
    mintl.hashaa
    mintl.list
    mintl.mem
    mintl.multiaa
    mintl.queue
    mintl.set
    mintl.share
    mintl.slist
    mintl.sortedaa
    mintl.stack

    mintl.array

    void reserve!(Value[])(inout Value[] x, size_t n);
    Reserve capacity for a dynamic array
    DArrayReverseIter backwards!(Value[])(Value[] x);
    Reverse dynamic array "foreach" traversal
    void sort!(Value[])(Value[] data, int delegate(Value* x, Value* y) cmp = null);
    Sort the array in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Value type is used.

    mintl.arrayheap

    struct ArrayHeap(Value, Alloc = GCAllocator)
    A heap (complete binary tree) backed by an array. x[n] is greater than or equal to x[2*n+1] and x[2*n+2]. x[0] is the greatest item. An optional allocator can customize memory management. The default allocator is GCAllocator.

    Value[] data;
    Backing array
    size_t length;
    Return length of heap
    alias int delegate(Value* a, Value* b) CompareFcn;
    Signature of comparison functions
    void compareFcn(CompareFcn cmp);
    Set the comparison function
    bool isEmpty
    Return true if container is empty
    Value opIndex(size_t n);
    Return nth item where the head is item 0.
    void opIndexAssign(Value val, size_t n);
    Assign to the nth item
    Value[] values;
    Get heap contents as dynamic array slice of backing array
    void add(...);
    Add to heap
    void vadd(TypeInfo[] ti, void* argptr);
    Add to heap using va_arg inpurs
    void addTail(Value v);
    Add to heap
    Value takeHead();
    Remove and return first item (greatest item)
    void removeHead();
    Remove first item (greatest item)
    Value* lookup(size_t n);
    Return a pointer to the nth item
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal by values
    int opApply(int delegate(inout size_t n, inout Value x) dg);
    Foreach traversal by index-value pairs
    ArrayHeap dup;
    Duplicate array heap by duplicating backing array
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    int opEquals(ArrayHeap c);
    Test heap equality
    alias ArrayHeap ContainerType;
    alias Value ValueType;
    alias size_t IndexType;
    Aliases for container types

    mintl.arraylist

    struct ArrayList(Value, bit ReadOnly = false, Alloc = GCAllocator)
    A list backed by an array. An ArrayList can also be used as a dynamic array with managed capacity. The backing array is resized when more space is required. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is GCAllocator.

    Value[] data;
    Backing array
    mixin MListCat(ArrayList)
    Mixin list catenation.
    mixin MListAlgo(this,ArrayList)
    Mixin list algorithms.
    MListCommon(ArrayList)
    Implement common list members.
    size_t length
    Read/write property to return or set the length of the list.
    size_t capacity
    Read/write property for the minimum capacity of the backing array. The capacity is the maximum number of elements the array can hold without requiring a reallocation of the backing array.
    Value[] array;
    Get list contents as dynamic array slice of the backing array assuming the list is contiguous.
    ArrayListReverseIter!(Value) backwards();
    Backwards traversal for "foreach"
    ArrayList!(Value,true,Alloc) readonly;
    Property that returns a read-only view of the container.
    ArrayList!(Value,false,Alloc) readwrite;
    Property that returns a read-write view of the container.
    void sort(int delegate(Value* x, Value* y) cmp = null);
    Sort the list in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Value type is used.
    alias ArrayList ContainerType;
    alias ArrayList SliceType;
    alias Value ValueType;
    alias size_t IndexType;
    alias ReadOnly isReadOnly;
    Aliases for container types

    mintl.deque

    struct Deque(Value, bit ReadOnly = false, Alloc = GCAllocator)
    A double-ended queue backed by a circular block-allocated array Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is GCAllocator.

    mixin MListCat(Deque)
    Mixin list catenation.
    mixin MListAlgo(this,Deque)
    Mixin list algorithms.
    MListCommon(Deque)
    Implement common list members.
    size_t length;
    Return length of deque.
    DequeReverseIter!(Value) backwards();
    Backwards traversal for "foreach"
    Deque!(Value,true,Alloc) readonly;
    Property that returns a read-only view of the container.
    Deque!(Value,false,Alloc) readwrite;
    Property that returns a read-write view of the container.
    void sort(int delegate(Value* x, Value* y) cmp = null);
    Sort the list in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Value type is used.
    alias Deque ContainerType;
    alias Deque SliceType;
    alias Value ValueType;
    alias size_t IndexType;
    alias ReadOnly isReadOnly;
    Aliases for container types

    mintl.hashaa

    struct HashAA(Key,Value,bit ReadOnly = false, Alloc = GCAllocator)
    An associative array linked by insertion order. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is GCAllocator.

    void add(...);
    Add key-value pairs to array
    void vadd(TypeInfo[] ti, void* argptr);
    Add using va_arg inpurs
    static HashAA make(...)
    Consruct a HashAA using add(...)
    size_t length;
    Return number of items in the array.
    bool isEmpty
    Return true if array is empty
    Value* get(Key key, bit throwOnMiss = false);
    Return a pointer to the value stored at the key. If the key is not in the array then null is returned or if throwOnMiss is true an exception is thrown.
    Value* put(Key key)
    Return a pointer to the value stored at the key and insert the key with value Value.init if the key is not in the array.
    bool contains(Key key)
    Returns true if the array contains the key
    bool contains(Key key, out Value value)
    Returns true if the array contains the key and sets the out value if present.
    Value opIndex(Key key);
    Return item with given key. Returns the default missing value if not present.
    void opIndexAssign(Value val, Key key);
    Assign a value to the given key
    Value missing
    Read/write property for the value to use on indexing a key not in the array. Defaults to Value.init
    HashAA opSlice(Key a, Key b);
    Slice from item a to b (exclusive)
    HashAA opSlice(HashAA a, HashAA b);
    Slice from first key in a to last key in b
    HashAA head
    Return one-item slice of the head
    HashAA tail
    Return one-item slice of the tail
    void next(int n = 1, int end = 0);
    Move the head and tail to the next item. If n is negative move to the previous item. If end <= 0 move the head of the slice and if end >= 0 move the tail of the slice.
    void remove(Key key);
    Remove a key from array if present. The node used for key is reused in future insert actions.
    Value take(Key key);
    Remove a key from array if present and return value. Returns the default missing value if the key was not present.
    void remove(HashAA subarray);
    Remove a slice from array
    Value[] values;
    Get values as a dynamic array. The values are in insertion order.
    Key[] keys;
    Get keys as a dynamic array. The keys are in insertion order.
    void reserve(size_t n);
    Reserve a capacity for the array
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal by values
    int opApply(int delegate(inout Key key, inout Value x) dg);
    Foreach traversal by key-value pairs
    int opApply(int delegate(inout HashAA n) dg);
    Foreach traversal by one-item slices
    HashAA dup;
    Duplicate array
    void clear;
    Clear contents. Only needed if a non-GCAllocator is used.
    void trim;
    Remove references to extra nodes kept for reuse
    int opEquals(HashAA c);
    Test array equality
    HashAAReverseIter!(Key,Value) backwards();
    Backwards traversal for "foreach"
    HashAA rehash;
    Rehash array to be more efficient
    Value value
    Return value of a one-item slices
    Key key;
    Return key of a one-item slices
    HashAA!(Key,Value,true) readonly;
    Property that returns a read-only view of the container.
    HashAA!(Key,Value,false) readwrite;
    Property that returns a read-write view of the container.
    void sort(int delegate(Key* x, Key* y) cmp = null);
    Sort the HashAA in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Key type is used. Future insertions are added in insertion order at the end of the traversal order.
    alias HashAA ContainerType;
    alias HashAA SliceType;
    alias Value ValueType;
    alias Key IndexType;
    alias ReadOnly isReadOnly;
    Aliases for container types

    mintl.list

    struct List(Value, bit ReadOnly = false, Alloc = GCAllocator)
    A doubly-linked list. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is GCAllocator.

    mixin MListCat(List)
    Mixin list catenation.
    mixin MListAlgo(this,List)
    Mixin list algorithms.
    MListCommon(List)
    Implement common list members.
    size_t length;
    Return length of list.
    void trim;
    Remove references to extra nodes kept for reuse
    ListReverseIter!(Value) backwards();
    Backwards traversal for "foreach"
    List!(Value,true,Alloc) readonly;
    Property that returns a read-only view of the container.
    List!(Value,false,Alloc) readwrite;
    Property that returns a read-write view of the container.
    void sort(int delegate(Value* x, Value* y) cmp = null);
    Sort the list in increasing order as defined by the given comparison delegate. If no delegate is supplied the default comparison function of the Value type is used.
    alias List ContainerType;
    alias List SliceType;
    alias Value ValueType;
    alias size_t IndexType;
    alias ReadOnly isReadOnly;
    Aliases for container types

    struct CircularList(Value, bit ReadOnly = false, Alloc = GCAllocator)
    A circular doubly-linked list. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is GCAllocator.

    mixin MListCat(CircularList)
    Mixin list catenation.
    mixin MListAlgo(this,CircularList)
    Mixin list algorithms.
    MListCommon(CircularList)
    Implement common list members.
    size_t length;
    Return length of list.
    List toList;
    Return the list as a non-circular List
    void rotate(int n = 1);
    Rotate the list by n steps (backwards if n is negative)
    CircularListReverseIter!(Value) backwards();
    Backwards traversal for "foreach"
    CircularList!(Value,true,Alloc) readonly;
    Property that returns a read-only view of the container.
    CircularList!(Value,false,Alloc) readwrite;
    Property that returns a read-write view of the container.
    alias CircularList ContainerType;
    alias List!(Value,Alloc) SliceType;
    alias Value ValueType;
    alias size_t IndexType;
    alias ReadOnly isReadOnly;
    Aliases for container types

    mintl.mem

    void* mallocWithCheck(size_t s)
    Call std.c.stdlib.malloc and throw OutOfMemory if fails.
    void* callocWithCheck(size_t n, size_t s)
    Call std.c.stdlib.calloc and throw OutOfMemory if fails.
    void* reallocWithCheck(void* p, size_t s)
    Call std.c.stdlib.realloc and throw OutOfMemory if fails.
    void dfree(void* p)
    Call free.
    void* gcMalloc(size_t s)
    Call mallocWithCheck and register range with GC.
    void* gcCalloc(size_t n, size_t s)
    Call callocWithCheck and register range with GC.
    void* gcRealloc(void* p, size_t s)
    Call reallocWithCheck and register range with GC.
    void gcFree(void* p)
    Remove range and call free.

    struct GCAllocator
    The default allocator that indicates the garbage collector should be used for memory management.
    struct Malloc
    An allocator that uses malloc for memory requests and registers blocks with the GC when requested by the container.
    struct MallocNoRoots
    An allocator that uses malloc for memory requests and ignores requests to register blocks with the GC. Use this allocator only when you know the container will not contain any roots.

    mintl.multiaa

    struct MultiAA!(Key,Value, ImplType = HashAA!(Key,Value[]))
    An associative array which allows keys to be repeated. Adapted from a customizable container type mapping keys to Value[].

    ImplType impl
    Read-write property holding the backing container
    void add(...);
    Add key-value pairs to the container
    void vadd(TypeInfo[] ti, void* argptr);
    Add using va_arg inpurs
    static MultiAA make(...)
    Consruct a MultiAA using add(...)
    void addItem(Key key, Value item);
    Add item to container.
    size_t length;
    Return number of items in the container.
    bool isEmpty
    Return true if container is empty.
    Value[] opIndex(Key key);
    Return the values for a given key.
    void remove(Key key, Value value);
    Remove an item from the container if present.
    void remove(Key key);
    Remove all the values with a given key if present.
    Key[] keys;
    Get keys as a dynamic array. Duplicates are removed.
    Value[][] values;
    Get values as a dynamic array.
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal of items in the container. If an item is repeated it is passed multiple times consecutively to the delegate.
    int opApply(int delegate(inout Key key, inout Value x) dg);
    Foreach traversal of items in the container. If an item is repeated it is passed multiple times consecutively to the delegate.
    MultiAA dup;
    Duplicate container
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    int opEquals(MultiAA c);
    Test container equality
    alias MultiAA ContainerType;
    alias Value ValueType;
    alias Key IndexType;
    alias ImplType AdaptType;
    const bit isReadOnly = ImplType.isReadOnly;
    Aliases for container types

    alias SortedMultiAA!(Key,Value)
    An alias for MultiAA!(Key,Value,SortedAA!(Key,Value[])) to implement a sorted multi-aa.

    mintl.queue

    struct Queue!(Value, ImplType = Deque!(Value))
    A queue of items adapted from a customizable list container type. The default backing container is a Deque.

    ImplType impl
    Read-write property holding the backing container.
    alias addTail put;
    Alias to add items to the tail of the queue.
    alias takeHead take;
    Alias to take items to the head of the queue.
    Value peek
    Return the head of the queue or Value.init if empty.
    mixin MListCat(Queue)
    Mixin list catenation.
    size_t length;
    Return length of queue.
    bool isEmpty
    Return true if container is empty
    Value opIndex(size_t n);
    Return nth item where the head is item 0.
    void opIndexAssign(Value val, size_t n);
    Assign to the nth item
    void addTail(Value v);
    Add to tail of queue
    void addTail(Queue v);
    Append v to tail of queue
    Value takeHead();
    Remove and return first item
    void removeHead();
    Remove first item
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal by values
    int opApply(int delegate(inout size_t n, inout Value x) dg);
    Foreach traversal by index-value pairs
    Queue dup;
    Duplicate queue.
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    int opEquals(Queue c);
    Test queue equality
    int opCmp(Queue c);
    Compare queues
    alias Queue ContainerType;
    alias Value ValueType;
    alias size_t IndexType;
    alias ImplType AdaptType;
    const bit isReadOnly = ImplType.isReadOnly;
    Aliases for container types

    alias ArrayQueue!(Value)
    An alias for Queue!(Value,ArrayList!(Value)) to adapt an ArrayList to the queue interface.

    alias PriorityQueue!(Value)
    An alias for Queue!(Value,ArrayHeap!(Value)) to adapt an ArrayHeap to the queue interface.

    mintl.set

    struct Set!(Value, ImplType = HashAA!(Value,uint))
    A set of unique items adapted from a customizable container type mapping items to 0 or 1. The default backing container type is a builtin associative array.

    ImplType impl
    Read-write property holding the backing container
    void add(...);
    Add items to set
    void vadd(TypeInfo[] ti, void* argptr);
    Add using va_arg inpurs
    static Set make(...)
    Consruct a Set using add(...)
    void addItem(Value item);
    Add item to set
    size_t length;
    Return number of items in the set.
    bool isEmpty
    Return true if set is empty
    bool opIndex(Value item);
    Return true if the item is in the set
    void remove(Value item);
    Remove an item from the set if present
    Value[] values;
    Get items as a dynamic set.
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal of items in the set
    Set dup;
    Duplicate set
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    int opEquals(Set c);
    Test set equality
    alias Set ContainerType;
    alias Value ValueType;
    alias ImplType AdaptType;
    const bit isReadOnly = ImplType.isReadOnly;
    Aliases for container types

    alias SortedSet!(Value)
    An alias for Set!(Value,SortedAA!(Value,uint)) to implement a sorted set.

    struct MultiSet!(Value, ImplType = HashAA!(uint,Value))
    A set which allows items to be repeated. Adapted from a customizable container type mapping items to repeat counts.

    ImplType impl
    Read-write property holding the backing container
    void add(...);
    Add items to set
    void vadd(TypeInfo[] ti, void* argptr);
    Add using va_arg inpurs
    static MultiSet make(...)
    Consruct a MultiSet using add(...)
    void addItem(Value item);
    Add item to set
    size_t length;
    Return number of items in the set.
    bool isEmpty
    Return true if set is empty
    bool opIndex(Value item);
    Return true if the item is in the set
    void remove(Value item);
    Remove an item from the set if present
    Value[] values;
    Get items as a dynamic set. Duplicates are removed.
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal of items in the set. If an item is repeated it is passed multiple times consecutively to the delegate.
    MultiSet dup;
    Duplicate set
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    int opEquals(MultiSet c);
    Test set equality
    alias MultiSet ContainerType;
    alias Value ValueType;
    alias ImplType AdaptType;
    const bit isReadOnly = ImplType.isReadOnly;
    Aliases for container types

    alias SortedMultiSet!(Value)
    An alias for MultiSet!(Value,SortedAA!(Value,uint)) to implement a sorted multi-set.

    mintl.share

    The mintl.share module is publically imported into all container modules and stores shared defintions.
    const bit ReadOnly = true;
    A named constant to improve the readability of code involving read-only containers. See the section on unmodifiable containers for examples.
    class IndexOutOfBoundsException : Exception
    Exception thrown when attempting to access an invalid index or key. Checks for invalid indices can be disabled using version=MinTLNoIndexChecking.
    template MListCatOperators(List)
    Concatenation routines to be mixed into the list-like containers
    void add(...);
    Add to list
    void vadd(TypeInfo[] ti, void* argptr);
    Add using va_arg inpurs
    static List make(...)
    Consruct a List using add(...)
    void addN(uint n, Value v)
    Add the value n times to the list
    void addBefore(List.SliceType sublist, Value[] v)
    Insert the values in the dynamic array v before sublist
    void addAfter(List.SliceType sublist, Value[] v)
    Insert the values in the dynamic array v after sublist
    List opCatAssign(Value v);
    Concatenation operator this ~= v
    List opCat(Value v);
    Concatenation operator this ~ v. copies this
    List opCat_r(Value v);
    Concatenation operator v ~ this. copies this
    List opCatAssign(List v);
    Concatenation operator this ~= v. copies v
    List opCat(List v);
    Concatenation operator this ~ v. copies both arguments
    template MListAlgo(Container, alias list)
    List algorithms to be mixed into the list-like containers
    Container.SliceType opIn(Value v);
    Return a one-item slice of the first occurrence of v in the list.
    Container.SliceType find(int delegate(inout Value v) dg);
    Return a one-item slice of the first occurrence where dg is true.
    uint count(Value v);
    Return the number of time v appears in the list.
    void swap(Container v);
    Swap the contents of the list with v (assumes non-overlapping). Extra elements are ignored.
    void fill(Value v);
    Fill the container with v
    void copy(Container v);
    Copy the contents of v to this container. Extra elements are ignored.
    MListCommon(Container)
    Common list routines
    bool isEmpty
    Return true if container is empty
    Value opIndex(size_t n);
    Return nth item where the head is item 0.
    void opIndexAssign(Value val, size_t n);
    Assign to the nth item
    Container.SliceType opSlice(size_t a, size_t b);
    Slice from item a to b (exclusive)
    Container.SliceType opSlice(Container.SliceType a, Container.SliceType b);
    Slice from head of a to tail of b
    Container.SliceType head
    Read-only property to get a one-item slice of the head.
    Container.SliceType tail
    Read-only property to get a one-item slice of the tail.
    Value[] values;
    Get list contents as dynamic array.
    Value value;
    Read/write property for the value of a one-item slice.
    void addTail(Value v);
    Add to tail of list
    void addTail(Container v);
    Copy v to tail of list
    void addHead(Value v);
    Add to head of list
    void addHead(Container v);
    Copy v to head of list
    Value takeTail();
    Remove and return last item
    Value takeHead();
    Remove and return first item
    void removeTail();
    Remove last item
    void removeHead();
    Remove first item
    void remove(Container.SliceType sublist);
    Remove sublist from list
    void addBefore(Container.SliceType subv, Container.SliceType v);
    Insert v before subv.
    void addAfter(Container.SliceType subv, Container.SliceType v);
    Insert v after subv.
    void next(int n = 1, int end = 0);
    Move the head and tail to the next item. If n is negative move to the previous item. If end <= 0 move the head of the slice and if end >= 0 move the tail of the slice.
    Value* lookup(size_t n);
    Return a pointer to the nth item
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal by values
    int opApply(int delegate(inout size_t n, inout Value x) dg);
    Foreach traversal by index-value pairs
    int opApply(int delegate(inout Container.SliceType n) dg);
    Foreach traversal by one-item slices
    Container reverse;
    Reverse list in-place.
    Container dup;
    Duplicate array list by duplicating backing array
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    int opEquals(Container c);
    Test list equality
    int opCmp(Container c);
    Compare lists

    mintl.slist

    struct SList(Value, bit ReadOnly = false, Alloc = GCAllocator)
    A singly-linked list. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is GCAllocator.

    mixin MListCat(SList)
    Mixin list catenation.
    size_t length;
    Return length of list.
    bool isEmpty
    Return true if container is empty
    SList tailList;
    Return the tail of the list as a slice
    Value opIndex(size_t n);
    Return nth item where the head is item 0.
    void opIndexAssign(Value val, size_t n);
    Assign to the nth item
    SList opSlice(size_t a, size_t b);
    Slice from item a to b (exclusive)
    SList opSlice(SList a, SList b);
    Slice from head of a to tail of b
    SList head
    Read-only property to get a one-item slice of the head.
    SList tail
    Read-only property to get a one-item slice of the tail.
    Value value
    Read/write property for the value of a one-item slice.
    Value[] values;
    Get list contents as dynamic array.
    void addTail(Value v);
    Add to tail of list
    void addTail(SList v);
    Append v to tail of list
    void addHead(Value v);
    Add to head of list
    void addHead(SList v);
    Prepend v to head of list
    Value takeHead();
    Remove and return first item
    void removeHead();
    Remove first item
    void addAfter(SList subv, SList v);
    Insert v after subv.
    void removeAfter(SList sublist, size_t n=1);
    Remove n items following sublist
    void removeBetween(SList a, SList b);
    Remove items after the tail of a to the head of b (exclusive)
    void next(int n = 1, int end = 0);
    Move the head and tail to the next item. If n is negative move to the previous item. If end <= 0 move the head of the slice and if end >= 0 move the tail of the slice.
    Value* lookup(size_t n);
    Return a pointer to the nth item
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal by values
    int opApply(int delegate(inout size_t n, inout Value x) dg);
    Foreach traversal by index-value pairs
    int opApply(int delegate(inout SList n) dg);
    Foreach traversal by one-item slices
    SList dup;
    Duplicate list
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    void trim;
    Remove references to extra nodes kept for reuse
    int opEquals(SList c);
    Test list equality
    int opCmp(SList c);
    Compare lists
    mixin MListAlgo(this,SList)
    Mixin list algorithms.
    SList!(Value,true,Alloc) readonly;
    Property that returns a read-only view of the container.
    SList!(Value,false,Alloc) readwrite;
    Property that returns a read-write view of the container.
    alias SList ContainerType;
    alias SList SliceType;
    alias Value ValueType;
    alias size_t IndexType;
    alias ReadOnly isReadOnly;
    Aliases for container types

    struct CircularSList(Value, bit ReadOnly = false, Alloc = GCAllocator)
    A circular singly-linked list. Compile with version=MinTLNoIndexChecking to disable bounds checking. The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is GCAllocator.

    mixin MListCat(CircularSList)
    Mixin list catenation.
    size_t length;
    Return length of list.
    bool isEmpty
    Return true if container is empty
    SList toSList;
    Return the list as a non-circular SList
    Value opIndex(size_t n);
    Return nth item where the head is item 0.
    void opIndexAssign(Value val, size_t n);
    Assign to the nth item
    SList opSlice(size_t a, size_t b);
    Slice from item a to b (exclusive)
    SList opSlice(SList a, SList b);
    Slice from head of a to tail of b
    SList head
    Read-only property to get a one-item slice of the head.
    SList tail
    Read-only property to get a one-item slice of the tail.
    Value value
    Read/write property for the value of a one-item slice.
    void addTail(Value v);
    Add to tail of list
    void addTail(CircularSList v);
    Append v to tail of list
    void addHead(Value v);
    Add to head of list
    void addHead(CircularSList v);
    Prepend v to head of list
    Value takeHead();
    Remove and return first item
    void removeHead();
    Remove first item
    void addAfter(SList subv, SList v);
    Insert v after subv.
    void removeAfter(SList sublist, size_t n=1);
    Remove n items following sublist
    void removeBetween(SList a, SList b);
    Remove items after the tail of a to the head of b (exclusive)
    void rotate(int n = 1);
    Rotate the list by n steps
    Value* lookup(size_t n);
    Return a pointer to the nth item
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal by values
    int opApply(int delegate(inout size_t n, inout Value x) dg);
    Foreach traversal by index-value pairs
    int opApply(int delegate(inout SList n) dg);
    Foreach traversal by one-item slices
    CircularSList dup;
    Duplicate list
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    int opEquals(CircularSList c);
    Test list equality
    int opCmp(CircularSList c);
    Compare lists
    mixin MListAlgo(this,CircularSList)
    Mixin list algorithms.
    CircularSList!(Value,true,Alloc) readonly;
    Property that returns a read-only view of the container.
    CircularSList!(Value,false,Alloc) readwrite;
    Property that returns a read-write view of the container.
    alias CircularAList ContainerType;
    alias SList!(Value,Alloc) SliceType;
    alias Value ValueType;
    alias size_t IndexType;
    alias ReadOnly isReadOnly;
    Aliases for container types

    mintl.sortedaa

    class CompareFcnSetException: Exception;
    Exception thrown when trying to set the comparison function of a non-empty array or an array that already had the comparison function set.

    struct SortedAA(Key, Value, bit ReadOnly = false, Alloc = GCAllocator)
    A sorted associative array The optional ReadOnly parameter disallows container modifications. The optional allocator customizes memory management. The default allocator is GCAllocator.

    alias int delegate(Key* a, Key* b) CompareFcn;
    Signature of comparison functions
    void compareFcn(CompareFcn cmp);
    Set the comparison function
    void add(...);
    Add key-value pairs to array
    void vadd(TypeInfo[] ti, void* argptr);
    Add using va_arg inpurs
    static SortedAA make(...)
    Consruct a SortedAA using add(...)
    size_t length;
    Return number of items in the array.
    bool isEmpty
    Return true if array is empty
    Value* get(Key key, bit throwOnMiss = false);
    Return a pointer to the value stored at the key. If the key is not in the array then null is returned or if throwOnMiss is true an exception is thrown.
    Value* put(Key key)
    Return a pointer to the value stored at the key and insert the key with value Value.init if the key is not in the array.
    bool contains(Key key)
    Returns true if the array contains the key
    bool contains(Key key, out Value value)
    Returns true if the array contains the key and sets the out value if present.
    Value opIndex(Key key);
    Return item with given key. Returns the default missing value if not present.
    void opIndexAssign(Value val, Key key);
    Assign a value to the given key
    Value missing
    Read/write property for the value to use on indexing a key not in the array. Defaults to Value.init
    SortedAA head()
    Return one-item slice of the smallest item
    SortedAA tail()
    Return one-item slice of the greatest item
    void next(int n = 1, int end = 0);
    Move the head and tail to the next item. If n is negative move to the previous item. If end <= 0 move the head of the slice and if end >= 0 move the tail of the slice.
    SortedAA from(Key a);
    Return a one-item slice of the smallest item greater than or equal to a.
    SortedAA to(Key b);
    Return a one-item slice of the greatest item smaller than b.
    SortedAA opSlice(Key a, Key b);
    Slice from item a to b (exclusive).
    SortedAA opSlice(SortedAA a, SortedAA b);
    Slice from first key in a to last key in b.
    Value take(Key key);
    Remove a key from array if present and return value. Returns the default missing value if the key was not present.
    void remove(Key key);
    Remove a key from array if present.
    void remove(SortedAA subarray);
    Remove a slice from array.
    void trim;
    Remove references to extra nodes kept for reuse
    Value[] values;
    Get values as a dynamic array. The values are in order.
    Key[] keys;
    Get keys as a dynamic array. The keys are in order.
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal by values
    int opApply(int delegate(inout Key key, inout Value x) dg);
    Foreach traversal by key-value pairs
    int opApply(int delegate(inout SortedAA n) dg);
    Foreach traversal by one-item slices
    SortedAA dup;
    Duplicate array
    void clear()
    Clear contents. Only needed if a non-GCAllocator is used.
    int opEquals(SortedAA c);
    Test array equality
    SortedAAReverseIter!(Key,Value) backwards();
    Backwards traversal for "foreach"
    Value value;
    Return value of a one-item slices
    Key key;
    Return key of a one-item slices
    SortedAA!(Key,Value,true,Alloc) readonly;
    Property that returns a read-only view of the container.
    SortedAA!(Key,Value,false,Alloc) readwrite;
    Property that returns a read-write view of the container.
    alias SortedAA ContainerType;
    alias SortedAA SliceType;
    alias Value ValueType;
    alias Key IndexType;
    Aliases for container types

    mintl.stack

    struct Stack!(Value, ImplType = Deque!(Value))
    A stack of items adapted from a customizable list container type. The default backing container is a Deque.

    ImplType impl
    Read-write property holding the backing container.
    alias addTail push;
    Alias to add items to the tail of the stack.
    alias takeTail pop;
    Alias to take items from the tail of the stack.
    Value peek
    Return the top of the stack or Value.init if empty.
    mixin MListCat(Stack)
    Mixin list catenation.
    size_t length;
    Return length of stack.
    bool isEmpty
    Return true if container is empty
    Value opIndex(size_t n);
    Return nth item where the head is item 0.
    void opIndexAssign(Value val, size_t n);
    Assign to the nth item
    void addTail(Value v);
    Add to tail of stack
    void addTail(Stack v);
    Append v to tail of stack
    Value takeHead();
    Remove and return first item
    void removeHead();
    Remove first item
    int opApply(int delegate(inout Value x) dg);
    Foreach traversal by values
    int opApply(int delegate(inout size_t n, inout Value x) dg);
    Foreach traversal by index-value pairs
    Stack dup;
    Duplicate stack.
    int opEquals(Stack c);
    Test stack equality
    int opCmp(Stack c);
    Compare stacks
    alias Stack ContainerType;
    alias Value ValueType;
    alias size_t IndexType;
    alias ImplType AdaptType;
    const bit isReadOnly = ImplType.isReadOnly;
    Aliases for container types

    alias ArrayStack!(Value)
    An alias for Stack!(Value,ArrayList!(Value)) to adapt an ArrayList to the stack interface.