Module multi_index

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 (N * ptrsize * k) 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 IndexedBy.

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 ValueChangedSlots), 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);
}