multi_index

A port of Joaquín M López Muñoz' multi_index library.

compilation options:
version=PtrHackery - In boost::multi_index, Muñoz stores the color of a RB Tree Node in the low bit of one of the pointers with the rationale that on 'many' architectures, pointers only point to even addresses.

Source:
https://bitbucket.org/ariovistus/multi_index/src/

License:
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at ).

Authors:
Steven Schveighoffer, Ellery Newcomer

Introduction:
A standard container maintains its elements in a specific structure which allows it to offer interesting or useful access to its elements. However, sometimes a programmer needs functionality which is not offered by a single collection type. Faced with such a need, a programmer must maintain auxiliary containers, either of duplicated elements or of pointers to elements of the primary container. In either solution, keeping the parallel containers synchronized quickly becomes a pain, and may introduce inefficiencies in time or memory complexity.

Into this use case steps multi_index . It allows the user to specify multiple indeces on the container elements, each of which provides interesting access functionality. A multi_index container will automatically keep all indeces synchronized over insertion, removal, or replacement operations performed on any one index.

Each index will typically require () additional bytes of memory, for some k < 4

Quick Start:

A MultiIndexContainer needs two things: a value type and a list of indeces. Put the list of indeces inside .

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

MyContainer c = new MyContainer;
If you like, you can name your indeces
alias MultiIndexContainer!(int, IndexedBy!(Sequenced!(),"seq")) MyContainer;

MyContainer c = new MyContainer;
Generally you do not perform operations on a MultiIndexContainer, but on one of its indeces. Access an index by its position in IndexedBy:
auto seq_index = c.get_index!0;
If you named your index, you can access it that way:
auto seq_index = c.seq;
Although an element is inserted into the container through a single index, it must appear in every index, and each index provides a default insertion, which will be automatically invoked. This is relevant when an index provides multiple insertion methods:
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]));
The following index types are provided:

Mutability:
Providing multiple indeces to the same data does introduce some complexities, though. Consider:
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!
In general, the container must either require the user not to perform any damning operation on its elements (which likely will entail paranoid and continual checking of the validity of its indeces), or else not provide a mutable view of its elements. By default, multi_index chooses the latter (with controlled exceptions).

Thus you are limited to modification operations for which the indeces can detect and perform any fixups (or possibly reject). You can use a remove/modify/insert workflow here, or functions modify and replace, which each index implements.

For modifications which are sure not to invalidate any index, you might simply cast away the constness of the returned element. This will work, but it is not recommended on the grounds of aesthetics (it's ew) and maintainability (if the code changes, it's a ticking time bomb).

Finally, if you just have to have a mutable view, include MutableView in the MultiIndexContainer specification. This is the least safe option (but see ), and you might make liberal use of the convenience function check provided by MultiIndexContainer, which asserts the validity of each index.

Efficiency:
To draw on an example from boost::multi_index, suppose a collection of Tuple!(int,int) needs to be kept in sorted order by both elements of the tuple. This might be accomplished by the following:
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;
Insertion remains straightforward
tree1.insert(item);
tree2.insert(&item);
However removal introduces some inefficiency
tree1.remove(item);
tree2.remove(&item); // requires a log(n) search, followed by a potential log(n) rebalancing
Muñoz suggests making the element type of T2 an iterator of T1 for to obviate the need for the second search. However, this is not possible in D, as D espouses ranges rather than indeces. (As a side note, Muñoz proceeds to point out that the iterator solution will require at minimum (N * ptrsize) more bytes of memory than will multi_index, so we needn't lament over this fact.)

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

T t = new T;
makes insertion and removal somewhat simpler:

t.insert(item);
t.remove(item);
and removal will not perform a log(n) search on the second index (rebalancing can't be avoided).

Signals and Slots:
An experimental feature of multi_index .

You can receive signals from MultiIndexContainer. Someday. Maybe.

Provided signals:

*crickets*

You can design your value type to signal to MultiIndexContainer.

(Note: std.signals won't work with multi_index , so don't bother trying)

Provided slots:

ValueChangedSlots - MultiIndexContainer receives signals from a value when value is mutated such that its position in an index may have changed.

Example:
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
Thus, MultiIndexContainers can be kept valid automatically PROVIDED no modifications occur other than those succeeded by a call to emit.

But what happens if a modification breaks, for example, a uniqueness constraint? Well, you have two options: remove the offending element silently, or remove it loudly (throw an exception). multi_index chooses the latter in this case.

Thread Safety:

multi_index is not designed to be used in multithreading. Find yourself a relational database.

Memory Allocation

In C++, memory allocators are used to control how a container allocates memory. D does not have a standardized allocator interface (but will soon). Until it does, multi_index will use a simple allocator protocol to regulate allocation of container structures. Define a struct with two static methods:

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
}
Pass the struct type in to MultiIndexContainer:
alias MultiIndexContainer!(int,IndexedBy!(Sequenced!()), MyAllocator) G;
Two allocators are predefined in multi_index : GCAllocator (default), and MallocAllocator

Compatible Sorting Criteria:
Loosely, predicates C1 and C2 are compatible if a sequence sorted by C1 is also sorted by C2 (consult multi_index for a more complete definition).

For (KeyType, CompatibleKeyType), a compatible sorting criterion takes the form:
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 ();


Page was generated with on Fri Sep 21 00:22:05 2012