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

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

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

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

  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

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.