container.linkedaa.d

module container.linkedaa;

pragma(inline, true):

struct LinkedAssociativeArray(Key, Value)
{
    // Initialize a LinkedAssociativeArray with an AssociativeArray.
    // For supporting `aa = [key1:value1, key2:value2, ...]` syntax.
    this(AssociativeArray!(Key, Value) aa) pure nothrow
    {
        dangerouslyReconstructAA(this, aa);
    }
    // ditto
    auto opAssign(AssociativeArray!(Key, Value) aa) pure nothrow
    {
        dangerouslyReconstructAA(this, aa);
    }

    // Lookup `key` in the associative array and return its value.
    // For supporting `aa[key]` syntax.
    ref opIndex(Key key) pure nothrow
    {
        return this.impl[key].value;
    }

    // Lookup `key` in the associative array and assign it a new `value`.
    // For supporting `aa[key] = value` syntax.
    auto opIndexAssign(Value value, const Key key) pure nothrow
    {
        this.impl[key] = this.addEntry(key, value);
        return value;
    }

    // Return a pointer to the value corresponding to the given key.
    // For supporting `key in aa` syntax.
    inout(Value)* opBinaryRight(string op : "in")(Key key) inout pure nothrow @nogc
    {
        if (auto p = key in this.impl)
            return &(*p).value;
        return null;
    }

    // Foreach over all values.
    // For supporting `foreach (value; aa) { ... }` syntax.
    int opApply(scope int delegate(ref Value) dg)
    {
        for (auto e = this.root; e !is null; e = e.next)
        {
            if (auto result = dg(e.value))
                return result;
        }
        return 0;
    }

    // Foreach over all key-value pairs.
    // For supporting `foreach (key, value; aa) { ... }` syntax.
    int opApply(scope int delegate(const ref Key, ref Value) dg)
    {
        for (auto e = this.root; e !is null; e = e.next)
        {
            if (auto result = dg(e.key, e.value))
                return result;
        }
        return 0;
    }

    // Reverse foreach over all values.
    // Note: This is impossible with native associative arrays, neat!
    // For supporting `foreach_reverse (value; aa) { ... }` syntax.
    int opApplyReverse(scope int delegate(ref Value) dg)
    {
        if (this.root is null)
            return 0;

        for (auto e = this.root.prev; e !is this.root; e = e.prev)
        {
            if (auto result = dg(e.value))
                return result;
        }
        return dg(this.root.value);
    }

    // Reverse foreach over all key-value pairs.
    // Note: This is impossible with native associative arrays, neat!
    // For supporting `foreach_reverse (key, value; aa) { ... }` syntax.
    int opApplyReverse(scope int delegate(const ref Key, ref Value) dg)
    {
        if (this.root is null)
            return 0;

        for (auto e = this.root.prev; e !is this.root; e = e.prev)
        {
            if (auto result = dg(e.key, e.value))
                return result;
        }
        return dg(this.root.key, this.root.value);
    }

    // Returns the number of entries n the associative array.
    // For supporting `aa.length` syntax.
    size_t length()() pure nothrow @nogc @safe
    {
        return this.impl.length;
    }

    // Removes `key` from the associative array and returns `true`.
    // If the key does not exist, this does nothing and return `false`.
    // For supporting `aa.remove(key)` syntax.
    bool remove()(Key key) pure nothrow @nogc @safe
    {
        return this.removeEntry(key);
    }

    // Internally, `Value[Key]` is stored in a `Value[LinkedEntry(Key, Value)*]`
    // associative array, so that we can continue to benefit from O(log N)
    // complexity of a native associative array.
    private AssociativeArray!(Key, LinkedEntry!(Key, Value)*) impl;

    // The oldest entry to begin iteration at.
    private LinkedEntry!(Key, Value)* root;
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa = ["c": 3, "a": 1, "b": 2];
    assert(aa.impl !is null);
    assert(aa.root !is null);

    assert(aa.root.next !is null);
    assert(aa.root.prev !is null);
    assert(aa.root.prev.next is null);
    assert(aa.root.prev.prev is aa.root.next);

    // ??? It passes, but is this reliable?
    //assert(aa.keys == ["c", "a", "b"]);
    //assert(aa.values == [3, 1, 2]);

    aa = ["e": 5, "d": 4];
    assert(aa.impl !is null);
    assert(aa.root !is null);

    assert(aa.root.next !is null);
    assert(aa.root.prev !is null);
    assert(aa.root.prev.next is null);
    assert(aa.root.prev.prev is aa.root);

    // ??? It passes, but is this reliable?
    //assert(aa.keys == ["e", "d"]);
    //assert(aa.values == [5, 4]);
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa = [
        "1":2, "3":4, "5":6, "7":8, "9":10,
        "11":12, "13":14, "15":16, "17":18,
        "19":20, "21":22, "23":24, "25":26,
    ];
    assert(aa.length == 13);
    // ??? It passes, but is this reliable?
    //assert(aa.keys == ["1","3","5","7","9","11","13","15","17","19","21","23","25"]);
    //assert(aa.values == [2,4,6,8,10,12,14,16,18,20,22,24,26]);

    int[string] bb = [
        "1":2, "3":4, "5":6, "7":8, "9":10,
        "19":20, "21":22, "23":24, "25":26,
        "11":12, "13":14, "15":16, "17":18,
    ];

    assert(bb["23"] == 24);
    aa = bb;
    assert(bb["23"] == 24);
    assert(aa.length == 13);
    // ??? It passes, but is this reliable?
    //assert(aa.keys == ["1","3","5","7","9","19","21","23","25","11","13","15","17"]);
    //assert(aa.values == [2,4,6,8,10,20,22,24,26,12,14,16,18]);
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa;
    aa["one"] = 1;
    assert(aa["one"] == 1);

    auto value = aa["two"] = 2;
    assert(value == 2);

    assert(aa.keys == ["one", "two"]);
    assert(aa.values == [1, 2]);
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa;

    assert("one" !in aa);
    aa["one"] = 1;
    assert("one" in aa);
    assert("two" !in aa);
}

@safe unittest
{
    LinkedAssociativeArray!(uint, uint) aa;
    foreach (uint i; 0 .. 20)
        aa[i] = i;

    uint index = 0;
    for (auto e = aa.root; e !is null; e = e.next, index++)
    {
        assert(e.key == index);
        assert(e.value == index);
    }
}

@system unittest
{
    LinkedAssociativeArray!(uint, uint) aa;
    foreach (uint i; 0 .. 20)
        aa[i] = i;

    uint index = 0;
    foreach (v; aa)
    {
        assert(v == index++);
    }

    index = 0;
    foreach (k, v; aa)
    {
        assert(k == v);
        assert(v == index++);
    }
}

@system unittest
{
    LinkedAssociativeArray!(uint, uint) aa;
    foreach (uint i; 0 .. 20)
        aa[i] = i;

    uint index = 20;
    foreach_reverse (v; aa)
    {
        assert(v == --index);
    }

    index = 20;
    foreach_reverse (k, v; aa)
    {
        assert(k == v);
        assert(v == --index);
    }
}

@safe unittest
{
    LinkedAssociativeArray!(uint, uint) aa;
    assert(aa.length == 0);

    foreach (uint i; 1 .. 21)
    {
        aa[i] = i;
        assert(aa.length == i);
    }
}

@safe unittest
{
    LinkedAssociativeArray!(uint, uint) aa;

    foreach (uint i; 0 .. 10)
        aa[i] = i;

    assert(aa.length == 10);
    assert(aa.root.key == 0);
    assert(aa.root.prev.key == 9);

    assert(aa.remove(10) == false);
    assert(aa.length == 10);
    assert(aa.root.key == 0);
    assert(aa.root.prev.key == 9);

    assert(aa.remove(9) == true);
    assert(aa.length == 9);
    assert(aa.root.key == 0);
    assert(aa.root.prev.key == 8);

    assert(aa.remove(3) == true);
    assert(aa.length == 8);
    assert(aa.root.key == 0);
    assert(aa.root.prev.key == 8);

    assert(aa.remove(0) == true);
    assert(aa.length == 7);
    assert(aa.root.key == 1);
    assert(aa.root.prev.key == 8);

    assert(aa.keys == [1,2,4,5,6,7,8]);
    assert(aa.values == [1,2,4,5,6,7,8]);
}

///////////////////////////////////////////////////////////////////////////////
// LinkedAssociativeArray standard runtime functions.
///////////////////////////////////////////////////////////////////////////////

// Returns `true` if there are no entries in this associative array.
// See also `bool std.range.primitives.empty`.
@property bool empty(T : LinkedAssociativeArray!(K, V), K, V)(T aa)
{
    return aa.root is null;
}

@safe unittest
{
    LinkedAssociativeArray!(string, uint) aa;
    assert(aa.empty);
    aa["zero"] = 0;
    assert(!aa.empty);
}

// Construct a range iterating over an associative array by key-value tuples.
// See also `auto std.array.byPair`.
auto byPair(T : LinkedAssociativeArray!(K, V), K, V)(T aa)
{
    import std.algorithm.iteration : map;
    import std.typecons : tuple;

    return aa.byKeyValue
        .map!(pair => tuple!("key", "value")(pair.key, pair.value));
}

@safe pure nothrow unittest
{
    import std.algorithm.sorting : sort;
    import std.typecons : tuple, Tuple;

    LinkedAssociativeArray!(string, int) aa = ["a": 1, "b": 2, "c": 3];
    Tuple!(string, int)[] pairs;

    // Iteration over key/value pairs.
    foreach (pair; aa.byPair)
    {
        if (pair.key == "b")
            pairs ~= tuple("B", pair.value);
        else
            pairs ~= pair;
    }

    assert(pairs == [
        tuple("a", 1),
        tuple("B", 2),
        tuple("c", 3)
    ]);
}

///////////////////////////////////////////////////////////////////////////////
// LinkedAssociativeArray core runtime functions.
///////////////////////////////////////////////////////////////////////////////

// Returns a forward range which will iterate over the keys.
// See also `auto object.byKey`.
auto byKey(T : LinkedAssociativeArray!(K, V), K, V)(T aa) pure nothrow @nogc @safe
{
    return aa.byKeyValueImpl!(Iterate.byKey)();
}
// ditto
auto byKey(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) pure nothrow @nogc
{
    return (*aa).byKey();
}

@safe unittest
{
    LinkedAssociativeArray!(int, string) aa = [1: "v1", 2: "v2"];
    int sum;
    foreach (v; aa.byKey)
        sum += v;

    assert(sum == 3);
}

// Returns a forward range which will iterate over the key-value pairs
// See also `auto object.byKeyValue`.
auto byKeyValue(T : LinkedAssociativeArray!(K, V), K, V)(T aa) pure nothrow @nogc @safe
{
    return aa.byKeyValueImpl!(Iterate.byKeyValue)();
}
// ditto
auto byKeyValue(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) pure nothrow @nogc
{
    return (*aa).byKeyValue();
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa = ["k1": 1, "k2": 2];
    int sum;
    foreach (e; aa.byKeyValue)
    {
        assert(e.key[1] == e.value + '0');
        sum += e.value;
    }

    assert(sum == 3);
}

// Returns a forward range which will iterate over the values
// See also `auto object.byValue`.
auto byValue(T : LinkedAssociativeArray!(K, V), K, V)(T aa) pure nothrow @nogc @safe
{
    return aa.byKeyValueImpl!(Iterate.byValue)();
}
// ditto
auto byValue(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) pure nothrow @nogc
{
    return (*aa).byValue();
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa = ["k1": 1, "k2": 2];
    int sum;
    foreach (v; aa.byValue)
        sum += v;

    assert(sum == 3);
}

// Removes all remaining keys and values from the associative array.
// See also `void object.clear`.
void clear(T : LinkedAssociativeArray!(K, V), K, V)(T aa)
{
    // O(1) complexity.
    object.clear(aa.impl);
    aa.root = null;
}
// ditto
void clear(T : LinkedAssociativeArray!(K, V), K, V)(T* aa)
{
    (*aa).clear();
}

@system unittest
{
    LinkedAssociativeArray!(string, int) aa = ["k1": 2];
    assert("k1" in aa);
    aa.clear;
    assert("k1" !in aa);
}

// Creates a newly allocated associative array containing a copy of the originals contents.
// See also `V[K] object.dup`.
T dup(T : LinkedAssociativeArray!(K, V), K, V)(T aa)
{
    // This seems more reasonable than forwarding .dup, as we don't want
    // the internal LinkedEntry to have more than one reference.
    T copy;

    // O(n) complexity, but then so is `object.dup`.
    for (auto e = aa.root; e !is null; e = e.next)
    {
        // TODO: ??? handle calling __xpostblit on copied value?
        copy.impl[e.key] = copy.addEntry(e.key, e.value);
    }

    return copy;
}
// ditto
T dup(T : LinkedAssociativeArray!(K, V), K, V)(T* aa)
{
    return (*aa).dup;
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa = ["k1": 2];
    auto a2 = aa.dup;
    aa["k2"] = 3;
    assert("k2" !in a2);
}

// Looks up `key`; if it exists returns corresponding value else evaluates and
// returns `defaultValue`. See also `inout(V) object.get`.
inout(V) get(K, V)(LinkedAssociativeArray!(K, V) aa, K key, lazy inout(V) defaultValue)
{
    auto p = key in aa;
    return p ? *p : defaultValue;
}
// ditto
inout(V) get(K, V)(LinkedAssociativeArray!(K, V)* aa, K key, lazy inout(V) defaultValue)
{
    return (*aa).get(key, defaultValue);
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa = ["k1": 1];
    assert(aa.get("k1", 0) == 1);
    assert(aa.get("k2", 0) == 0);
}

// Returns a newly allocated dynamic array containing a copy of all keys.
// See also `Key[] object.keys`.
@property K[] keys(T : LinkedAssociativeArray!(K, V), K, V)(T aa)
{
    // Note: Not using `impl.keys()` to retain insertion order.
    K[] res;
    res.length = aa.impl.length;
    size_t idx = 0;

    // O(n) complexity, but then so is `object.keys`.
    // TODO: ??? handle calling __xpostblit on copied keys?
    for (auto e = aa.root; e !is null; e = e.next)
        res[idx++] = e.key;

    return res;
}
// ditto
@property K[] keys(T : LinkedAssociativeArray!(K, V), K, V)(T* aa)
{
    return (*aa).keys;
}

@safe unittest
{
    LinkedAssociativeArray!(int, string) aa = [1: "v1", 2: "v2"];
    int sum;
    foreach (k; aa.keys)
        sum += k;

    assert(sum == 3);
}

@safe unittest
{
    static struct S
    {
        string str;
        LinkedAssociativeArray!(string, void[]) dict;
        alias dict this;
    }

    auto s = S("a");
    assert(s.keys.length == 0);
}

@safe unittest
{
    @safe static struct Key
    {
         string str;
         this(this) @safe {}
    }
    LinkedAssociativeArray!(Key, string) aa;
    static assert(__traits(compiles, {
                void test() @safe {
                    const _ = aa.keys;
                }
            }));
}

@safe unittest
{
    static struct Key
    {
        string str;
        this(this) @system {}
    }
    LinkedAssociativeArray!(Key, string) aa;
    static assert(!__traits(compiles, {
                void test() @safe {
                    const _ = aa.keys;
                }
            }));
}

// Reorganizes the associative array in place so that lookups are more efficient.
// See also `T object.rehash`.
T rehash(T : LinkedAssociativeArray!(K, V), K, V)(T aa)
{
    object.rehash(aa.impl);
    return aa;
}
// ditto
T rehash(T : LinkedAssociativeArray!(K, V), K, V)(T* aa)
{
    object.rehash(aa.impl);
    return *aa;
}

// Looks up `key`; if it exists returns corresponding value else evaluates
// `value`, adds it to the associative array, and returns it.
// See also `V object.require`.
ref V require(K, V)(ref LinkedAssociativeArray!(K, V) aa, K key, lazy V value = V.init)
{
    return object.require(aa.impl, key, aa.addEntry(key, value)).value;
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa = ["k1": 1];
    assert(aa.require("k1", 0) == 1);
    assert(aa.require("k2", 0) == 0);
    assert(aa["k2"] == 0);
}

// Looks up `key`; calls `create` if `key` doesn't exist in the associative
// array, otherwise `update`. See also `object.update`.
void update(K, V, C, U)(ref LinkedAssociativeArray!(K, V) aa, K key, scope C create, scope U update)
    if (is(typeof(create()) : V) &&
        (is(typeof(update(aa[key])) : V) || is(typeof(update(aa[key])) == void)))
{
    return object.update(aa.impl, key,
        () {
            return aa.addEntry(key, create());
        },
        (ref LinkedEntry!(K, V)* v) {
            static if (is(typeof(update(v.value)) == void))
                update(v.value);
            else
                v.value = update(v.value);
        });
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa;

    // create
    aa.update("key",
        () => 1,
        (int) {} // not executed
        );
    assert(aa["key"] == 1);

    // update value by ref
    aa.update("key",
        () => 0, // not executed
        (ref int v) {
            v += 1;
        });
    assert(aa["key"] == 2);

    // update from return value
    aa.update("key",
        () => 0, // not executed
        (int v) => v * 2
        );
    assert(aa["key"] == 4);

    // 'update' without changing value
    aa.update("key",
        () => 0, // not executed
        (int) {
            // do something else
        });
    assert(aa["key"] == 4);
}

@safe unittest
{
    static struct S
    {
        int x;
    @nogc nothrow pure:
        this(this) @system {}

    @safe const:
        // stubs
        bool opEquals(S rhs) { assert(0); }
        size_t toHash() { assert(0); }
    }

    LinkedAssociativeArray!(string, int) aai;
    static assert(is(typeof(() @safe { aai.require("a", 1234); })));
    static assert(is(typeof(() @safe { aai.update("a", { return 1234; }, (ref int x) { x++; return x; }); })));

    LinkedAssociativeArray!(string, S) aas;
    static assert(is(typeof(() { aas.require("a", S(1234)); })));
    static assert(is(typeof(() { aas.update("a", { return S(1234); }, (ref S s) { s.x++; return s; }); })));
    static assert(!is(typeof(() @safe { aas.update("a", { return S(1234); }, (ref S s) { s.x++; return s; }); })));

    LinkedAssociativeArray!(S, int) aais;
    static assert(is(typeof(() { aais.require(S(1234), 1234); })));
    static assert(is(typeof(() { aais.update(S(1234), { return 1234; }, (ref int x) { x++; return x; }); })));
    static assert(!is(typeof(() @safe { aais.require(S(1234), 1234); })));
    static assert(!is(typeof(() @safe { aais.update(S(1234), { return 1234; }, (ref int x) { x++; return x; }); })));
}

@safe unittest
{
    struct S0
    {
        int opCall(ref int v)
        {
            return v + 1;
        }
    }

    struct S1
    {
        int opCall()()
        {
            return -2;
        }

        T opCall(T)(ref T v)
        {
            return v + 1;
        }
    }

    LinkedAssociativeArray!(string, int) a = ["2" : 1];
    a.update("2", () => -1, S0.init);
    assert(a["2"] == 2);
    a.update("0", () => -1, S0.init);
    assert(a["0"] == -1);
    a.update("2", S1.init, S1.init);
    assert(a["2"] == 3);
    a.update("1", S1.init, S1.init);
    assert(a["1"] == -2);
}

@system unittest
{
    LinkedAssociativeArray!(string, int) aa;

    foreach (n; 0 .. 2)
        aa.update("k1", {
            return 7;
        }, (ref int v) {
            return v + 3;
        });
    assert(aa["k1"] == 10);
}

// Returns a newly allocated dynamic array containing a copy of all values.
// See also `object.values`.
@property V[] values(T : LinkedAssociativeArray!(K, V), K, V)(T aa)
{
    // Note: Not using `impl.values()` because it would return an array of LinkedEntry*.
    V[] res;
    res.length = aa.impl.length;
    size_t idx = 0;

    // O(n) complexity, but then so is `object.values`.
    // TODO: ??? handle calling __xpostblit on copied values?
    for (auto e = aa.root; e !is null; e = e.next)
        res[idx++] = e.value;

    return res;
}
// ditto
@property V[] values(T : LinkedAssociativeArray!(K, V), K, V)(T* aa)
{
    return (*aa).values;
}

@safe unittest
{
    LinkedAssociativeArray!(string, int) aa = ["k1": 1, "k2": 2];
    int sum;
    foreach (e; aa.values)
        sum += e;

    assert(sum == 3);
}

@safe unittest
{
    static struct S
    {
        string str;
        LinkedAssociativeArray!(string, void[]) dict;
        alias dict this;
    }

    auto s = S("a");
    assert(s.values.length == 0);
}

@safe unittest
{
    @safe static struct Value
    {
        string str;
        this(this) @safe {}
    }
    LinkedAssociativeArray!(string, Value) aa;
    static assert(__traits(compiles, {
                void test() @safe {
                    const _ = aa.values;
                }
            }));
}

@safe unittest
{
    static struct Value
    {
        string str;
        this(this) @system {}
    }
    LinkedAssociativeArray!(string, Value) aa;
    static assert(!__traits(compiles, {
                void test() @safe {
                    const _ = aa.values;
                }
            }));
}

///////////////////////////////////////////////////////////////////////////////
// LinkedAssociativeArray implementation.
///////////////////////////////////////////////////////////////////////////////

private:

enum Iterate { byKey, byValue, byKeyValue }

// Generic forward range implementation for byKey/Value/KeyValue.
// See also `object.byKey`, `object.byKeyValue`, `object.byValue`.
auto byKeyValueImpl(Iterate type, K, V)(ref LinkedAssociativeArray!(K, V) aa)
{
    static struct Result
    {
        private LinkedEntry!(K, V)* entry;

    pure nothrow @nogc@safe:

        @property bool empty() { return this.entry is null; }

    static if (type == Iterate.byKey)
        @property ref front() { return this.entry.key; }

    static if (type == Iterate.byValue)
        @property ref front() { return this.entry.value; }

    static if (type == Iterate.byKeyValue)
        @property auto front()
        {
            static struct Pair
            {
                private K* keyp;
                private V* valuep;
                @property ref key() inout { return *this.keyp; }
                @property ref value() inout { return *this.valuep; }
            }
            return Pair(&this.entry.key, &this.entry.value);
        }

        void popFront() { this.entry = this.entry.next; }
        @property Result save() { return this; }
    }

    return Result(aa.root);
}

// Represents an entry in the internal associative array.
// Holds a single key-value pair and the double-linked
// insertion order list.
struct LinkedEntry(Key, Value)
{
    private Key key;
    private Value value;

    // The predecessor in the iteration list.
    private LinkedEntry* prev = null;
    // The successor in the iteration list.
    private LinkedEntry* next = null;
}

// Helper which creates and links a new entry.
auto addEntry(K, V)(ref LinkedAssociativeArray!(K, V) aa, K key, V value) pure nothrow
{
    auto e = new LinkedEntry!(K, V)(key, value);
    if (aa.root is null)
    {
        aa.root = e;
        e.prev = e;
    }
    else
    {
        e.prev = aa.root.prev;
        e.prev.next = e;
        aa.root.prev = e;
    }
    return e;
}

// Helper which removes and unlinks an existing entry.
bool removeEntry(K, V)(ref LinkedAssociativeArray!(K, V) aa, K key) pure nothrow @nogc @safe
{
    auto p = key in aa.impl;

    if (p is null)
        return false;

    // Keep the doubly-linked list in order.
    auto e = *p;
    if (e == aa.root)
    {
        aa.root = e.next;
        if (e.next !is null)
            e.next.prev = e.prev;
    }
    else if (e.next is null)
    {
        e.prev.next = null;
        aa.root.prev = e.prev;
    }
    else
    {
        e.prev.next = e.next;
        e.next.prev = e.prev;
    }

    aa.impl.remove(key);
    return true;
}

version (GNU)
{
    version (GNU_StackGrowsDown)
        version = HeapGrowsUp;
}
else
{
    version = HeapGrowsUp;
}

// Helper (questionable) which creates a linked associative array from a
// D native associative array literal.
// Laughably @trusted, but we *promise* that we are accessing the internal
// druntime AA ABI in the correct way (even though we shouldn't!).
void dangerouslyReconstructAA(K, V)(ref LinkedAssociativeArray!(K, V) aa, V[K] from) pure nothrow @trusted
{
    // !!! WONTFIX: We can't possibly know the order of keys and values given as
    // there is no way to overload the AA literals assignments in D.
    // The best assumption we can make is that the memory order of entries
    // is the order that they key[] and value[] arrays were passed to the
    // _d_assocarrayLiteral runtime function.
    static struct DRuntimeAABucket
    {
        size_t hash;
        union Entry
        {
            struct KeyValue
            {
                K key;
                V value;
            }
            KeyValue* keyvalue;
            size_t addr;
        }
        Entry entry;
    }

    if (aa.root !is null)
        aa = aa.init;

    // This is why I've called this "dangerously".
    auto buckets = **cast(DRuntimeAABucket[]**)&from;

    // Copy all entries to a new area, so we don't overwrite the original.
    auto entries = new DRuntimeAABucket.Entry[buckets.length];
    size_t nentries = 0;

    // Simple (naive?) inlined in-place merge sort by memory address.
    // Should be O(N log N) time complexity, O(1) space complexity.
    // Probably more as we need to fix-up the address before and after
    // calling the sort function.
    size_t baseAddr = -1;
    size_t maxAddr = 0;

    foreach (b; buckets)
    {
        if (b.entry.keyvalue !is null)
        {
            entries[nentries++] = b.entry;
            if (b.entry.addr < baseAddr)
                baseAddr = b.entry.addr;
            if (maxAddr < b.entry.addr)
                maxAddr = b.entry.addr + 1;
        }
    }

    if (nentries == 0)
        return;

    immutable maxOffset = maxAddr - baseAddr;

    void mergeSort(size_t start, size_t end)
    {
        if (start < end)
        {
            size_t mid = start + (end - start) / 2;
            mergeSort(start, mid);
            mergeSort(mid + 1, end);

            size_t i = start;
            size_t j = mid + 1;
            size_t k = start;

            // Encode the address offset so that both values are stored at `entries[i]`.
            // `entries[i] % max` will give the original value of `entries[i]`, and
            // `entries[i] / max` will give the new value.
            while (i <= mid && j <= end)
            {
                if (entries[i].addr % maxOffset <= entries[j].addr % maxOffset)
                    entries[k++].addr += (entries[i++].addr % maxOffset) * maxOffset;
                else
                    entries[k++].addr += (entries[j++].addr % maxOffset) * maxOffset;
            }
            while (i <= mid)
                entries[k++].addr += (entries[i++].addr % maxOffset) * maxOffset;
            while (j <= end)
                entries[k++].addr += (entries[j++].addr % maxOffset) * maxOffset;
            // Finally compute the actual values for all elements.
            foreach (idx; start .. end + 1)
                entries[idx].addr /= maxOffset;
        }
    }
    // Adjust all entry addresses by the minimum address found, to avoid overflowing.
    foreach (i; 0 .. nentries)
        entries[i].addr -= baseAddr;

    mergeSort(0, nentries - 1);

    foreach (i; 0 .. nentries)
        entries[i].addr += baseAddr;

    // Now add all key-value pairs in memory order.
    version (HeapGrowsUp)
    {
        foreach (i; 0 .. nentries)
            aa[entries[i].keyvalue.key] = entries[i].keyvalue.value;
    }
    else
    {
        foreach_reverse (i; 0 .. nentries)
            aa[entries[i].keyvalue.key] = entries[i].keyvalue.value;
    }
}