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.