multi_index

alias MultiIndexContainer!(int, IndexedBy!(Sequenced!())) MyContainer;

MyContainer c = new MyContainer;

alias MultiIndexContainer!(int, IndexedBy!(Sequenced!(),"seq")) MyContainer;

MyContainer c = new MyContainer;

auto seq_index = c.get_index!0;

auto seq_index = c.seq;

alias MultiIndexContainer!(int, IndexedBy!(
            Sequenced!(), "a",
            Sequenced!(), "b")) DualList;

DualList list = new DualList();

// Sequenced defaults to insert to back
list.a.insert([1,2,3,4]);
assert(equals(list.a[], [1,2,3,4]));
assert(equals(list.b[], [1,2,3,4]));

list.a.insertFront(5);
assert(equals(list.a[], [5,1,2,3,4]));
assert(equals(list.b[], [1,2,3,4,5]));

class Value{
    int i;
    string s;
    this(int _i, string _s){
        i = _i;
        s = _s;
    }
}
alias MultiIndexContainer!(Value,
        IndexedBy!(RandomAccess!(), OrderedUnique!("a.s"))) C;

C c = new C;
auto i = c.get_index!0;

i.insert(new Value(1,"a"));
i.insert(new Value(2,"b"));
i[1].s = "a"; // bad! index 1 now contains duplicates and is in invalid state!

import std.container;
alias RedBlackTree!(Tuple!(int,int), "a[0] < b[0]") T1;
alias RedBlackTree!(Tuple!(int,int)*, "(*a)[1] < (*b)[1]") T2;

T1 tree1 = new T1;
T2 tree2 = new T2;

tree1.insert(item);
tree2.insert(&item);

tree1.remove(item);
tree2.remove(&item); // requires a log(n) search, followed by a potential log(n) rebalancing

alias MultiIndexContainer!(Tuple!(int,int),
        IndexedBy!(OrderedUnique!("a[0]"),
            OrderedUnique!("a[1]"))) T;

T t = new T;

t.insert(item);
t.remove(item);

import multi_index;
import std.algorithm: moveAll;

class MyRecord{
    int _i;

    @property int i()const{ return _i; }
    @property void i(int i1){
        _i = i1;
        emit(); // MultiIndexContainer is notified that this record's
                // position in indeces may need to be fixed
    }

    // signal impl - MultiIndexContainer will use these
    // to connect. In this example, we actually only need
    // a single slot. For a value type with M signals
    // (differentiated with mixin aliases), there will be
    // M slots connected.
    mixin Signals!();
}

alias MultiIndexContainer!(MyRecord,
    IndexedBy!(OrderedUnique!("a.i")),
    ValueChangedSlots!(ValueSignal!(0)), // this tells MultiIndexContainer that you want
                                      // it to use the signal defined in MyRecord.
                                      // you just need to pass in the index number.
    MutableView,
) MyContainer;

MyContainer c = new MyContainer;

// populate c

MyRecord v = c.front();

v.i = 22; // v's position in c is automatically fixed

struct MyAllocator{
 T* allocate(T)(size_t i); // return pointer to chunk of memory containing i*T.sizeof bytes
 void deallocate(T)(T* t); // release chunk of memory at t
}

alias MultiIndexContainer!(int,IndexedBy!(Sequenced!()), MyAllocator) G;

struct CompatibleLess{
    static:
    bool kc_less(KeyType, CompatibleKeyType);
    bool ck_less(CompatibleKeyType, KeyType);
    bool cc_less(CompatibleKeyType, CompatibleKeyType);
}

template Sequenced ()

A doubly linked list index.

struct SequencedRange (bool is_const);

Defines the index' primary range, which embodies a bidirectional range

bool empty ();

@property auto front ();

@property auto back ();

@property auto save ();

void popFront ();

void popBack ();

alias SeqRange ;

alias ConstSeqRange ;

const size_t length ();

Returns the number of elements in the container.

Complexity:
.

const bool empty ();

Property returning if and only if the container has no elements.

Complexity:

SeqRange opSlice ();
const ConstSeqRange opSlice ();

Fetch a range that spans all the elements in the container.

Complexity:

inout @property auto front ();

Complexity:

void front (Value value);

Complexity:
;
for this index

inout @property auto back ();

Complexity:

void back (Value value);

Complexity:

void relocateFront (PosRange)(ref PosRange moveme, PosRange tohere);

Moves moveme.front to the position before tohere.front and increments moveme. Takes either a range from this index, or any positional range originating from this index.

Preconditions:
moveme and tohere are both ranges of the same container

Postconditions:
moveme is incremented

Complexity:

void relocateBack (PosRange)(ref PosRange moveme, PosRange tohere);

Moves moveme.back to the position after tohere.back and decrements moveme. Takes either a range from this index, or any positional range originating from this index.

Preconditions:
moveme and tohere are both ranges of the same container

Postconditions:
moveme.back is decremented

Complexity:

void modify (SomeRange, Modifier)(SomeRange r, Modifier mod);

Perform mod on elements of r and performs any necessary fixups to container's indeces. If the result of mod violates any index' invariant, the element is removed from the container.

Preconditions:
mod is a callable of the form void mod(ref Value)

Complexity:
,
for this index

bool replace (Position!(ThisNode) r, Value value);

Replaces value at r with value

Returns:
whether replacement succeeded

Complexity:
??

size_t insertFront (SomeRange)(SomeRange stuff);

Inserts every element of stuff not rejected by another index into the front of the index.

Returns:
The number of elements inserted.

Complexity:
;
for this index

size_t insertFront (SomeValue)(SomeValue value);

Inserts value into the front of the sequence, if no other index rejects value

Returns:
The number if elements inserted into the index.

Complexity:
;
for this index

size_t insertBack (SomeRange)(SomeRange stuff);

Inserts every element of stuff not rejected by another index into the back of the index.

Returns:
The number of elements inserted.

Complexity:
;
for this index

size_t insertBack (SomeValue)(SomeValue value);

Inserts value into the back of the sequence, if no other index rejects value

Returns:
The number if elements inserted into the index.

Complexity:
;
for this index

alias insert ;

Forwards to insertBack

void removeFront ();

Removes the value at the front of the index from the container.

Precondition:


Complexity:
; for this index

void removeBack ();

Removes the value at the back of the index from the container.

Precondition:


Complexity:
;
for this index

alias removeAny ;

Forwards to removeBack

SeqRange remove (R)(R r);

Removes the values of r from the container. Takes either a range from this index, or any positional range originating from this index.

Returns:
an empty range (EMN: why?)

Preconditions:
r came from this index

Complexity:
,
for this index

template RandomAccess ()

A random access index.

struct RARangeT (bool is_const);

Defines the index' primary range, which embodies a random access range

@property auto front ();

void popFront ();

const bool empty ();

const size_t length ();

@property auto back ();

void popBack ();

@property auto save ();

auto opIndex (size_t i);

RARange opSlice ();
const ConstRARange opSlice ();

Fetch a range that spans all the elements in the container.

Complexity:

RARange opSlice (size_t a, size_t b);
const ConstRARange opSlice (size_t a, size_t b);

Fetch a range that spans all the elements in the container from index (inclusive) to index (exclusive).

Preconditions:
a <= b && b <= length

Complexity:

const size_t length ();

Returns the number of elements in the container.

Complexity:
.

const bool empty ();

Property returning if and only if the container has no elements.

Complexity:

const size_t capacity ();

Returns the capacity of the index, which is the length of the underlying store

void reserve (size_t count);

Ensures sufficient capacity to accommodate elements.

Postcondition:


Complexity:
if , otherwise .

inout @property auto front ();

Complexity:

void front (ValueView value);

Complexity:
;
for this index

inout @property auto back ();

Complexity:

void back (ValueView value);

Complexity:
;
for this index

void clear ();

inout auto opIndex (size_t i);

Preconditions:
i < length

Complexity:

ValueView opIndexAssign (ValueView value, size_t i);

Sets index i to value, unless another index refuses value

Preconditions:
i < length

Returns:
the resulting value at index i

Complexity:
;
for this index

void swapAt (size_t i, size_t j);

Swaps element at index with element at index .

Preconditions:
i < length && j < length

Complexity:

void removeBack ();

Removes the last element from this index.

Preconditions:
!empty

Complexity:
;
for this index

size_t insertBack (SomeValue)(SomeValue value);

inserts value in the back of this index.

Complexity:
,
amortized for this index

size_t insertBack (SomeRange)(SomeRange r);

inserts elements of r in the back of this index.

Complexity:
,
amortized for this index

alias insert ;

inserts elements of r in the back of this index.

Complexity:
,
amortized for this index

void modify (SomeRange, Modifier)(SomeRange r, Modifier mod);

Perform mod on elements of r and performs any necessary fixups to container's indeces. If the result of mod violates any index' invariant, the element is removed from the container.

Preconditions:
mod is a callable of the form void mod(ref Value)

Complexity:
,
for this index

bool replace (Position!(ThisNode) r, ValueView value);

Replaces the value at r with value

Returns:
whether replacement succeeded

Complexity:
??

RARange remove (Range)(Range r);

Removes elements of r from this container. Takes either a range from this index, or any positional range originating from this index.

Returns:
An empty range.

Complexity:
,
for this index

template Ordered (bool allowDuplicates = false,alias KeyFromValue = "a",alias Compare = "a<b")

A red black tree index

struct OrderedRangeT (bool is_const);

The range type for this index, which embodies a bidirectional range

const bool empty ();

Returns if the range is empty

@property auto front ();

Returns the first element in the range

@property auto back ();

Returns the last element in the range

void popFront ();

pop the front element from the range

complexity:
amortized

void popBack ();

pop the back element from the range

complexity:
amortized

void removeFront ();

Pops front and removes it from the container. Does not invalidate this range.

Preconditions:
!empty

Complexity:
,
for this index

void removeBack ();

Pops back and removes it from the container. Does not invalidate this range.

Preconditions:
!empty

Complexity:
,
for this index

@property auto save ();

Trivial save implementation, needed for .

alias ConstOrderedRange ;

alias OrderedRange ;

alias Elem ;

Element type for the tree

const bool empty ();

Check if any elements exist in the container. Returns if at least one element exists.

Complexity:

const size_t length ();

Returns the number of elements in the container.

Complexity:
.

OrderedRange opSlice ();
const ConstOrderedRange opSlice ();

Fetch a range that spans all the elements in the container.

Complexity:

inout @property auto front ();

The front element in the container

Complexity:

inout @property auto back ();

The last element in the container

Complexity:

const bool opBinaryRight (string op)(Elem e);

operator. Check to see if the given element exists in the container.

Complexity:

bool opBinaryRight (string op, K)(K k);

operator. Check to see if the given element exists in the container.

Complexity:

void clear ();

Removes all elements from the container.

Complexity:
??

inout ValueView opIndex (KeyType k);

Available for Unique variant.

Complexity:

void modify (SomeRange, Modifier)(SomeRange r, Modifier mod);

Perform mod on elements of r and performs any necessary fixups to container's indeces. If the result of mod violates any index' invariant, r.front is removed from the container.

Preconditions:
!r.empty,
mod is a callable of the form void mod(ref Value)

Complexity:
,
for this index

bool replace (Position!(ThisNode) r, ValueView value);

Replaces value at r with value

Returns:
whether replacement succeeded

Complexity:
??

size_t insert (Stuff)(Stuff stuff);

Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container.

Complexity:
;
for this index

size_t insert (Stuff)(Stuff stuff);

Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.

Complexity:
;
for this index

Elem removeAny ();

Remove an element from the container and return its value.

Complexity:
;
for this index

void removeFront ();

Remove the front element from the container.

Complexity:
;
for this index

void removeBack ();

Remove the back element from the container.

Complexity:
;
for this index

OrderedRange remove (R)(R r);

Removes the given range from the container.

Returns:
An empty range.

Complexity:
;
for this index

size_t removeKey (Keys...)(Keys keys);
size_t removeKey (Key)(Key[] keys);
size_t removeKey (Stuff)(Stuff stuff);

Removes elements from the container that are equal to the given values according to the less comparator. One element is removed for each value given which is in the container. If is true, duplicates are removed only if duplicate values are given.

Returns:
The number of elements removed.

Complexity:
;
for this index

Examples:

    alias MultiIndexContainer!(int, IndexedBy!(OrderedNonUnique!())) C;
    C c = new C();
    auto rbt = c.get_index!0;
    rbt.insert([0, 1, 1, 1, 4, 5, 7]);
    rbt.removeKey(1, 4, 7);
    assert(std.algorithm.equal(rbt[], [0, 1, 1, 5]));
    rbt.removeKey(1, 1, 0);
    assert(std.algorithm.equal(rbt[], [5]));

auto upperBound (U)(U k);
const auto upperBound (U)(U k);

Get a range from the container with all elements that are > k according to the less comparator

Complexity:

auto upperBound (CompatibleLess, CompatibleKey)(CompatibleKey k);
const auto upperBound (CompatibleLess, CompatibleKey)(CompatibleKey k);

Get a range from the container with all elements that are > k according to the compatible sorting criterion.

Complexity:

auto lowerBound (U)(U k);
const auto lowerBound (U)(U k);

Get a range from the container with all elements that are < k according to the less comparator

Complexity:

auto lowerBound (CompatibleLess, CompatibleKey)(CompatibleKey k);
const auto lowerBound (CompatibleLess, CompatibleKey)(CompatibleKey k);

Get a range from the container with all elements that are < k according to the compatible sorting criterion.

Complexity:

auto equalRange (U)(U k);
const auto equalRange (U)(U k);

Get a range from the container with all elements that are == k according to the less comparator

Complexity:

OrderedRange cEqualRange (CompatibleLess, CompatibleKey)(CompatibleKey k);
const ConstOrderedRange cEqualRange (CompatibleLess, CompatibleKey)(CompatibleKey k);

Get a range from the container with all elements that are == k according to the compatible sorting criterion.

Complexity:

auto bounds (string boundaries = "[]", U)(U lower, U upper);

Get a range of values bounded below by lower and above by upper, with inclusiveness defined by boundaries.

Complexity:

auto bounds (CompatibleLess, string boundaries = "[]", CompatibleKey)(CompatibleKey lower, CompatibleKey upper);

Get a range of values bounded below by lower and above by upper, with inclusiveness defined by boundaries.

Complexity:

template OrderedNonUnique (alias KeyFromValue = "a",alias Compare = "a<b")

A red black tree index

template OrderedUnique (alias KeyFromValue = "a",alias Compare = "a<b")

A red black tree index

template Heap (alias KeyFromValue = "a",alias Compare = "a<b")

a max heap index

struct HeapRangeT (bool is_const);

The primary range of the index, which embodies a bidirectional range. Ends up performing a breadth first traversal (I think..) removeFront and removeBack are not possible.

@property auto front ();

void popFront ();

@property auto back ();

void popBack ();

const bool empty ();

const size_t length ();

@property auto save ();

alias ConstHeapRange ;

alias HeapRange ;

HeapRange opSlice ();
const ConstHeapRange opSlice ();

Fetch a range that spans all the elements in the container.

Complexity:

const size_t length ();

Returns the number of elements in the container.

Complexity:
.

const bool empty ();

Property returning if and only if the container has no elements.

Complexity:

inout @property auto front ();

Returns:
the max element in this index

Complexity:

inout @property auto back ();

Returns:
the back of this index

Complexity:

void clear ();

??

void modify (SomeRange, Modifier)(SomeRange r, Modifier mod);

Perform mod on elements of r and performs any necessary fixups to container's indeces. If the result of mod violates any index' invariant, r.front is removed from the container.

Preconditions:
!r.empty,
mod is a callable of the form void mod(ref Value)

Complexity:
,
for this index

bool replace (Position!(ThisNode) r, ValueView value);

Replaces value at r with value

Returns:
whether replacement succeeded

Complexity:
??

const size_t capacity ();

Returns the capacity of the index, which is the length of the underlying store

void reserve (size_t count);

Ensures sufficient capacity to accommodate elements.

Postcondition:


Complexity:
if , otherwise .

size_t insert (SomeValue)(SomeValue value);

Inserts value into this heap, unless another index refuses it.

Returns:
the number of values added to the container

Complexity:
;
for this index

void removeFront ();

Removes the max element of this index from the container.

Complexity:
;
for this index

alias removeAny ;

Forwards to removeFront

void removeBack ();

removes the back of this index from the container. Why would you do this? No idea.

Complexity:
;
for this index

HeapRange remove (R)(R r);

Removes the given range from the container.

Returns:
An empty range.

Complexity:
;
for this index

template Hashed (bool allowDuplicates = false,alias KeyFromValue = "a",alias Hash = "??",alias Eq = "a==b")

a hash table index

KeyFromValue(value) = key of type KeyType

Hash(key) = hash of type size_t (on Hash = "??", uses D's default hashing mechanism)

Eq(key1, key2) determines equality of key1, key2

struct HashedRangeT (bool is_const);

the primary range for this index, which embodies a forward range. iteration has time complexity O(n)

bool empty ();

@property auto front ();

void popFront ();

void removeFront ();

@property auto save ();

alias ConstHashedRange ;

alias HashedRange ;

const size_t length ();

Returns the number of elements in the container.

Complexity:
.

const bool empty ();

Property returning if and only if the container has no elements.

Complexity:

inout @property auto front ();

Preconditions:
!empty

Complexity:

void clear ();

??

HashedRange opSlice ();
const ConstHashedRange opSlice ();

Gets a range of all elements in container.

Complexity:

const ValueView opIndex (KeyType k);

Available for Unique variant.

Complexity:
( on a good day)

const bool opBinaryRight (string op)(KeyType k);
const bool opBinaryRight (string op)(ValueView value);

Reports whether a value exists in the collection such that eq(k, key(value)).

Complexity:
( on a good day)

const bool contains (ValueView value);
const bool contains (KeyType k);

Reports whether value exists in this collection

Complexity:
( on a good day)

void modify (SomeRange, Modifier)(SomeRange r, Modifier mod);

Perform mod on r.front and performs any necessary fixups to container's indeces. If the result of mod violates any index' invariant, r.front is removed from the container.

Preconditions:
!r.empty,
mod is a callable either of the form void mod(ref Value) or Value mod(Value)

Complexity:
,
for this index ( on a good day)

bool replace (SomeRange)(SomeRange r, ValueView value);

Replaces r.front with value

Returns:
whether replacement succeeded

Complexity:
??

BucketSeqRange equalRange (KeyType k);
const ConstBucketSeqRange equalRange (KeyType k);

Returns a range of all elements with eq(key(elem), k).

Complexity:
( on a good day)

const size_t loadFactor ();

const size_t capacity ();

size_t insert (SomeValue)(SomeValue value);

insert value into this container. For Unique variant, will refuse value if value already exists in index.

Returns:
number of items inserted into this container.

Complexity:

for this index ( on a good day)

size_t insert (SomeRange)(SomeRange r);

insert contents of r into this container. For Unique variant, will refuse any items in content if it already exists in index.

Returns:
number of items inserted into this container.

Complexity:

for this index ( on a good day)

HashedRange remove (R)(R r);

Removes all of r from this container.

Preconditions:
r came from this index

Returns:
an empty range

Complexity:
,
for this index

size_t removeKey (KeyType k);

Removes all elements with key k from this container.

Returns:
the number of elements removed

Complexity:
,
for this index ( on a good day)

template HashedUnique (alias KeyFromValue = "a",alias Hash = "??",alias Eq = "a==b")

template HashedNonUnique (alias KeyFromValue = "a",alias Hash = "??",alias Eq = "a==b")

class Position (MNode);

Encapsulates a container item and its position in the container. Access the item via

position.v

Don't access container internals.

@property auto v ();

auto PSR (Range)(Range rng);

Extract a positional range from an index's range.

struct IndexedBy (L...);

Encapsulate the list of indeces to be used by the container.

IndexedBy!(Sequenced(), HashedUnique!())

Indeces may be named:

IndexedBy!(Sequenced(), "seq", HashedUnique!(), "hash")

Then they may be accessed from the container by name:

auto seq_index = container.seq;

Otherwise, an index is accessed by its index (ouch) in the list:

auto seq_index = container.get_index!0

struct ComparisonEx (alias _key,alias _less);

For use with MultiCompare

struct DefaultComparison (alias _less);

For use with MultiCompare

template MultiCompare (F...)

Convenience template to compose comparison of a sequence of items. Consider when comparison of an object is dependent on more than one field:

struct A {
    int x;
    int y;

    int opCmp(A other) {
        if(x == other.x) {
            if(y == other.y) {
                return 0;
            }else {
                return y < other.y ? -1 : 1;
            }
        }else{
            return x < other.x ? -1 : 1;
        }
    }
}

Manual translation to a function usable by appropriate indeces is kind of nasty:

alias binaryFun!"a.x == b.x ? a.y < b.y : a.x < b.x" less;

and gets progressively worse with more fields. An equvalent using MultiCompare :

alias MultiCompare!("a.x", "a.y") less;

The actual comparison operator used can be controlled on a per-field basis:

alias MultiCompare!("a.x", ComparisonEx!("a.y", "a>b")) less1;

Or on all subsequent fields:

// equivalent to less1
alias MultiCompare!("a.x", DefaultComparison!"a>b","a.y") less2;

By default, MultiCompare uses the 'a<b' less than operator.

bool MultiCompare (T)(T a, T b);

struct CriterionFromKey (MultiIndex,size_t index,alias CompatibleKeyFromKey,alias CompatibleLess = "a<b");

Build a compatible sorting criterion given a MultiIndexContainer index, a conversion from KeyType to CompatibleKeyType, and an optional comparison operator over CompatibleKeyType.

struct ValueChangedSlots (L...);

Specifies how to hook up value signals to indeces with the semantics that whenever value changes in a way that will cause its position in index to change or become invalid, a signal is sent to the index. The index will respond by fixing the position, or if that is not possible, by throwing an exception.

Pass in one or more instantiations of .

A signal can be shared by multiple indeces; however do not associate a signal to the same index more than once.

struct ValueSignal (size_t index,string mixinAlias = "");

A specifies which receives signals, and how to access the value's signal interface. Of course, the value type must provide a signal interface, e.g.

value.connect(void delegate() slot);
value.disconnect(void delegate() slot);

See for an example implementation.

If a value type wishes to support multiple signal interfaces, mixin aliases are expected to disambiguate:

value.mixinAlias.connect(void delegate() slot);
// etc

If you wish to associate a signal with every index,

ValueSignal!("*", mixinAlias)

may be used.

struct ValueSignal (string tag,string mixinAlias = "");

struct ConstView ;

struct MutableView ;

class MultiIndexContainer (Value,Args...);

The container. Don't call any index methods from this container directly; use a reference to an individual index, which can be obtained via

container.get_index!N
container.name // for named indeces

IndexN get_index (size_t n)();

Obtain a reference to the nth index in this container.

void check ();

Test each index for consistency. Don't expect this to be a quick operation.

@property auto to_range (size_t N, Range0)(Range0 r);

Similar to C++ multi_index's project function. Converts r to a range of type index!N .Range, guaranteeing that result.front == r.front.

template Signal ()

Simple signal implementation, which can be used in conjunction with

* ValueChangedSlots: In your value type, call emit when (after) the value has been mutated and its position in the index may have changed

void connect (void delegate() slot);

void disconnect (void delegate() slot);

void emit ();