Map with maintained insertion order

[Andrej Mitrovic]

On 3/23/12, Andrej Mitrovic <andrej.mitrovich at gmail.com> wrote:
> Does someone have a map implementation that maintains the insertion
> order of the keys?

Here's a sloppy implementation:

module test;

import std.stdio;
import std.traits;

template KeyType(V : V[K], K)
    if (isAssociativeArray!(V[K]))
{
    alias K KeyType;
}

template ValueType(V : V[K], K)
    if (isAssociativeArray!(V[K]))
{
    alias V ValueType;
}

template BaseElement(T : U[], U)
{
    alias U BaseElement;
}

struct LinkedHash(T)
    if (isAssociativeArray!T)
{
    alias KeyType!T Key;
    alias ValueType!T Value;

    static if (isArray!Value)
        template isValue(T) { enum bool isValue = (is(T == Value) ||
is(BaseElement!Value == T)); }
    else
        template isValue(T) { enum bool isValue = is(T == Value); }

    Value[] payload;
    size_t[Key] keyToIndex;
    Key[size_t] indexToKey;
    size_t lastIndex;

    size_t getNewIndex()
    {
        payload.length = payload.length + 1;
        return lastIndex++;
    }

    size_t* getKeyIndex(string key)
    {
        if (auto index = key in keyToIndex)
            return index;
        else
            return null;
    }

    Value opIndex(in Key key)
    {
        if (auto index = getKeyIndex(key))
            return payload[*index];
        else
            assert(0, "Key '" ~ key ~ "' not found.");
    }

    void opIndexAssign(V)(V value, Key key)
        if (isValue!V)
    {
        if (auto index = getKeyIndex(key))
            payload[*index] = value;
        else
        {
            auto index = getNewIndex();
            payload[index] = value;
            keyToIndex[key] = index;
            indexToKey[index] = key;
        }
    }

    void opIndexOpAssign(string op, V)(V value, Key key)
        if (isValue!V)
    {
        if (auto index = getKeyIndex(key))
            mixin("payload[*index] " ~ op ~ "= value;");
        else
        {
            auto index = getNewIndex();
            mixin("payload[index] " ~ op ~ "= value;");
            keyToIndex[key] = index;
            indexToKey[index] = key;
        }
    }

    int opApply(scope int delegate(ref Key, ref Value) dg)
    {
        foreach (index; 0 .. lastIndex)
        {
            auto result = dg(indexToKey[index], payload[index]);
                if (result)
                    return result;
        }

        return 0;
    }
}

void main()
{
    auto names = ["1", "2", "3", "4", "5", "6", "7", "8"];

    LinkedHash!(string[string]) stringMap;
    foreach (name; names)
        stringMap[name] ~= "test";

    foreach (key, val; stringMap)
        writefln("%s: %s", key, val);

    LinkedHash!(string[][string]) stringArrMap;
    stringArrMap["100"] = ["foo"];
    stringArrMap["101"] ~= "bar";

    foreach (name; names)
        stringArrMap[name] ~= "test";

    foreach (key, val; stringArrMap)
        writefln("%s: %s", key, val);
}