module cachetools.containers.hashmap;

import std.traits;
import std.experimental.logger;
import std.format;
import std.typecons;

import core.memory;
import core.bitop;

private import std.experimental.allocator;
private import std.experimental.allocator.mallocator: Mallocator;

private import cachetools.internal;
private import cachetools.hash;
private import cachetools.containers.lists;

class KeyNotFound: Exception
{
    this(string msg = "key not found") @safe
    {
        super(msg);
    }
}
///
/// Return true if it is worth to store values inline in hash table
/// V footprint should be small enough
///
package bool SmallValueFootprint(V)() {
    import std.traits;
    static if (
           isNumeric!V
        || isSomeString!V
        || isSomeChar!V
        || isPointer!V )
    {
            return true;
    }
    else static if (
           is(V == struct) && V.sizeof <= (void*).sizeof )
    {
            return true;
    }
    else static if (
            is(V == class ) && __traits(classInstanceSize, V) <= (void*).sizeof)
    {
        return true;
    }
    else
        return false;
}

private bool keyEquals(K)(const K a, const K b)
{
    static if ( is(K==class) )
    {
        if (a is b)
        {
            return true;
        }
        if (a is null || b is null)
        {
            return false;
        }
        return a.opEquals(b);
    }
    else
    {
        return a == b;
    }
}
/*
dub run -b release --compiler ldc2
Running ./cachetools 
AA!(int,int)    [137 ms, 348 μs, and 6 hnsecs]
OA!(int,int)    [77 ms, 913 μs, and 1 hnsec]
OA!(int,int) GC [80 ms, 571 μs, and 3 hnsecs]
---
AA large        [122 ms and 157 μs]
OA large        [177 ms, 167 μs, and 4 hnsecs]
OA large GC     [125 ms, 771 μs, and 8 hnsecs]
---
AA largeClass   [183 ms, 366 μs, and 3 hnsecs]
OA largeClass   [124 ms, 617 μs, and 3 hnsecs]
OA largeClassGC [106 ms, 407 μs, and 7 hnsecs]
---
*/

struct HashMap(K, V, Allocator = Mallocator) {

    enum initial_buckets_num = 32;
    enum grow_factor = 2;
    enum inlineValues = true;//SmallValueFootprint!V()|| is(V==class);

    //static if ( is(K==class) && (is(K==immutable) || is(K==const)) )
    //{
    //    alias StoredKeyType = Rebindable!K;
    //}
    //else static if (is(K==struct) && (is(K==immutable) || is(K==const)) )
    //{
    //    alias StoredKeyType = Unqual!K;
    //}
    //else
    //{
    //    alias StoredKeyType = K;
    //}

    alias StoredKeyType   = StoredType!K;
    alias StoredValueType = StoredType!V;

    private {
        alias   allocator = Allocator.instance;
        static if (hash_t.sizeof == 8)
        {
            enum    EMPTY_HASH =     0x00_00_00_00_00_00_00_00;
            enum    DELETED_HASH =   0x10_00_00_00_00_00_00_00;
            enum    ALLOCATED_HASH = 0x20_00_00_00_00_00_00_00;
            enum    TYPE_MASK =      0xF0_00_00_00_00_00_00_00;
            enum    HASH_MASK =      0x0F_FF_FF_FF_FF_FF_FF_FF;
        }
        else static if (hash_t.sizeof == 4)
        {
            enum    EMPTY_HASH =     0x00_00_00_00;
            enum    DELETED_HASH =   0x10_00_00_00;
            enum    ALLOCATED_HASH = 0x20_00_00_00;
            enum    TYPE_MASK =      0xF0_00_00_00;
            enum    HASH_MASK =      0x0F_FF_FF_FF;
        }

        struct _Bucket {
            hash_t          hash;
            StoredKeyType   key;
            static if (inlineValues)
            {
                StoredValueType   value;
            }
            else
            {
                V*  value_ptr;
            }
            string toString() const {
                import std.format;
                static if (inlineValues) {
                    return "%s, hash: %0x,key: %s, value: %s".format(
                        [EMPTY_HASH:"free", DELETED_HASH:"deleted", ALLOCATED_HASH:"allocated"][cast(long   )(hash & TYPE_MASK)],
                        hash, key, value);
                } else {
                    return "%s, hash: %0x, key: %s, value: %s".format(
                        [EMPTY_HASH:"free", DELETED_HASH:"deleted", ALLOCATED_HASH:"allocated"][cast(long)(hash & TYPE_MASK)],
                        hash, key,
                        value_ptr !is null?  format("%s", *value_ptr) : "-");
                }
            }
        }

        _Bucket[]   _buckets;
        int         _buckets_num;
        int         _mask;
        int         _allocated;
        int         _deleted;
        int         _empty;
    }

    ~this() @safe {
        if ( _buckets_num > 0 )
        {
            static if ( !inlineValues )
            {
                for(int i=0;i<_buckets_num;i++)
                {
                    auto t = _buckets[i].hash;
                    if ( t <= DELETED_HASH )
                    {
                        continue;
                    }
                    (() @trusted {dispose(allocator, _buckets[i].value_ptr);})();
                }
            }
            (() @trusted {
                GC.removeRange(_buckets.ptr);
                dispose(allocator, _buckets);
            })();
        }
    }
    invariant {
        assert(_allocated>=0 && _deleted>=0 && _empty >= 0);
        assert(_allocated + _deleted + _empty == _buckets_num, "a:%s + d:%s + e:%s != total: %s".format(_allocated, _deleted,  _empty, _buckets_num));
    }
    ///
    /// Find any unallocated bucket starting from start_index (inclusive)
    /// Returns index on success or hash_t.max on fail
    ///
    private hash_t findEmptyIndex(const hash_t start_index) pure const @safe @nogc
    in
    {
        assert(start_index < _buckets_num);
    }
    do {
        hash_t index = start_index;

        do {
            () @nogc {debug(cachetools) tracef("test index %d for non-ALLOCATED", index);}();
            if ( _buckets[index].hash < ALLOCATED_HASH )
            {
                return index;
            }
            index = (index + 1) & _mask;
        } while(index != start_index);
        return hash_t.max;
    }
    ///
    /// Find allocated bucket for given key and computed hash starting from start_index
    /// Returns: index if bucket found or hash_t.max otherwise
    ///
    /// Inherits @nogc and from K opEquals()
    ///
    private hash_t findEntryIndex(const hash_t start_index, const hash_t hash, in K key) pure const @safe
    in
    {
        assert(hash < DELETED_HASH);        // we look for real hash
        assert(start_index < _buckets_num); // start position inside array
    }
    do {
        hash_t index = start_index;

        do {
            immutable h = _buckets[index].hash;

            () @nogc @trusted {debug(cachetools) tracef("test entry index %d (%s) for key %s", index, _buckets[index].toString, key);}();

            if ( h == EMPTY_HASH ) {
                break;
            }

            if ( h >= ALLOCATED_HASH && (h & HASH_MASK) == hash && keyEquals(_buckets[index].key, key) ) {
                //() @nogc @trusted {debug(cachetools) tracef("test entry index %d for key %s - success", index, key);}();
                return index;
            }
            index = (index + 1) & _mask;
        } while(index != start_index);
        return hash_t.max;
    }

    ///
    /// Find place where we can insert(DELETED or EMPTY bucket) or update existent (ALLOCATED)
    /// bucket for key k and precomputed hash starting from start_index
    ///
    ///
    /// Inherits @nogc from K opEquals()
    ///
    private hash_t findUpdateIndex(const hash_t start_index, const hash_t computed_hash, in K key) pure const @safe
    in 
    {
        assert(computed_hash < DELETED_HASH);
        assert(start_index < _buckets_num);
    }
    do {
        hash_t index = start_index;

        do {
            immutable h = _buckets[index].hash;

            () @nogc @trusted {debug(cachetools) tracef("test update index %d (%s) for key %s", index, _buckets[index], key);}();

            if ( h <= DELETED_HASH ) // empty or deleted
            {
                () @nogc @trusted {debug(cachetools) tracef("test update index %d (%s) for key %s - success", index, _buckets[index], key);}();
                return index;
            }
            assert((h & TYPE_MASK) == ALLOCATED_HASH);
            if ( (h & HASH_MASK) == computed_hash && keyEquals(_buckets[index].key, key) ) 
            {
                () @nogc @trusted {debug(cachetools) tracef("test update index %d (%s) for key %s - success", index, _buckets[index], key);}();
                return index;
            }
            index = (index + 1) & _mask;
        } while(index != start_index);
        return hash_t.max;
    }
    ///
    /// Find unallocated entry in the buckets slice
    /// We use this function during resize() only.
    ///
    private long findEmptyIndexExtended(const hash_t start_index, in ref _Bucket[] buckets, int new_mask) pure const @safe @nogc
    in
    {
        assert(start_index < buckets.length);
    }
    do
    {
        hash_t index = start_index;

        do {
            immutable t = buckets[index].hash;

            () @nogc @trusted {debug(cachetools) tracef("test empty index %d (%s)", 
                index, buckets[index]);}();
            
            if ( t <= DELETED_HASH ) // empty or deleted
            {
                return index;
            }

            index = (index + 1) & new_mask;
        } while(index != start_index);
        return hash_t.max;
    }

    private bool tooMuchDeleted() pure const @safe @nogc {
        //
        // _deleted > _buckets_num / 8
        //
        return _deleted << 3 > _buckets_num;
    }

    private bool tooHighLoad() pure const @safe @nogc {
        //
        // _allocated/_buckets_num > 0.8
        // 5 * allocated > 4 * buckets_num
        //
        return _allocated + (_allocated << 2) > _buckets_num << 2;
    }

    private void doResize(int dest) @safe {
        immutable _new_buckets_num = dest;
        immutable _new_mask = dest - 1;
        _Bucket[] _new_buckets = makeArray!(_Bucket)(allocator, _new_buckets_num);

        () @trusted {GC.addRange(_new_buckets.ptr, _new_buckets_num * _Bucket.sizeof);}();

        // iterate over entries

        debug(cachetools)
        {
            () @nogc {tracef("start resizing: old loadfactor: %s", (1.0*_allocated) / _buckets_num);}();
        }

        for(int i=0;i<_buckets_num;i++) {
            immutable hash_t h = _buckets[i].hash;
            if ( h < ALLOCATED_HASH ) { // empty or deleted
                continue;
            }

            immutable hash_t start_index = h & _new_mask;
            immutable new_position = findEmptyIndexExtended(start_index, _new_buckets, _new_mask);

            debug(cachetools) () @nogc {tracef("old hash: %0x, old pos: %d, new_pos: %d", h, i, new_position);}();

            assert( new_position >= 0 );
            assert( _new_buckets[cast(hash_t)new_position].hash  == EMPTY_HASH );

            _new_buckets[cast(hash_t)new_position] = _buckets[i];
        }
        (() @trusted {
            GC.removeRange(_buckets.ptr);
            dispose(allocator, _buckets);
        })();
        _buckets = _new_buckets;
        _buckets_num = _new_buckets_num;
        assert(_popcnt(_buckets_num) == 1, "Buckets number must be power of 2");
        _mask = _buckets_num - 1;
        _deleted = 0;
        _empty = _buckets_num - _allocated;

        debug(cachetools)
        {
            () @nogc {tracef("resizing done: new loadfactor: %s", (1.0*_allocated) / _buckets_num);}();
        }
    }

    ///
    /// Lookup methods
    ///
    V* opBinaryRight(string op)(in K k) @safe if (op == "in")
    {

        if ( _buckets_num == 0 ) return null;

        immutable computed_hash = hash_function(k) & HASH_MASK;
        immutable start_index = computed_hash & _mask;
        immutable lookup_index = findEntryIndex(start_index, computed_hash, k);
        if ( lookup_index == hash_t.max) {
            return null;
        }
        static if ( inlineValues )
        {
            static if ( is(V==StoredValueType) )
            {
                return &_buckets[lookup_index].value;
            }
            else
            {
                V* r = () @trusted {return cast(V*)&_buckets[lookup_index].value;}();
                return r;
            }
        }
        else
        {
            return _buckets[lookup_index].value_ptr;
        }
    }

    ref V getOrAdd(T)(K k, T defaultValue) @safe
    {
        V* v = k in this;
        if ( v )
        {
            return *v;
        }
        static if (isAssignable!(V, T))
        {
            return *put(k, defaultValue);
        }
        else static if ( isCallable!T && isAssignable!(V, ReturnType!T))
        {
            return *put(k, defaultValue());
        }
        else
        {
            static assert(0, "what?");
        }
    }

    alias require = getOrAdd;

    /// Attention: this can't return ref as default value can be rvalue
    V get(T)(K k, T defaultValue) @safe
    {
        V* v = k in this;
        if ( v )
        {
            return *v;
        }
        static if (isAssignable!(V, T))
        {
            return defaultValue;
        }
        else static if ( isCallable!T && isAssignable!(V, ReturnType!T))
        {
            return defaultValue();
        }
        else
        {
            static assert(0, "You must call 'get' with default value of HashMap 'value' type, or with callable, returning HashMap 'value'");
        }
    }

    ///
    /// Attention: you can't use this method in @nogc code.
    /// Usual aa[key] method.
    /// Throws exception if key not found
    ///
    ref V opIndex(in K k) @safe
    {
        V* v = k in this;
        if ( v !is null )
        {
            return *v;
        }
        throw new KeyNotFound();
    }

    ///
    /// Modifiers
    ///
    void opIndexAssign(V v, K k) @safe
    {
        put(k, v);
    }
    ///
    /// put pair (k,v) into hash.
    /// it must be @safe, it inherits @nogc properties from K and V
    /// It can resize hashtable it is overloaded or has too much deleted entries
    ///
    V* put(K k, V v) @safe
    out
    {
        assert(__result !is null);
    }
    do {
        if ( !_buckets_num ) {
            _buckets_num = _empty = initial_buckets_num;
            assert(_popcnt(_buckets_num) == 1, "Buckets number must be power of 2");
            _mask = _buckets_num - 1;
            _buckets = makeArray!(_Bucket)(allocator, _buckets_num);
            () @trusted {GC.addRange(_buckets.ptr, _buckets_num * _Bucket.sizeof);}();
        }

        () @nogc @trusted {debug(cachetools) tracef("put k: %s, v: %s", k,v);}();

        if ( tooHighLoad ) {
            doResize(grow_factor * _buckets_num);
        }

        V* r; //result
        immutable computed_hash = hash_function(k) & HASH_MASK;
        immutable start_index = computed_hash & _mask;
        immutable placement_index = findUpdateIndex(start_index, computed_hash, k);
        assert(placement_index >= 0);
        _Bucket* bucket = &_buckets[placement_index];
        immutable h = bucket.hash;

        debug(cachetools) () @nogc @trusted {tracef("start_index: %d, placement_index: %d", start_index, placement_index);}();

        if ( h < ALLOCATED_HASH )
        {
            _allocated++;
            _empty--;
        }
        static if ( inlineValues )
        {
            debug(cachetools) () @nogc @trusted {tracef("place inline buckets[%d] '%s'='%s'", placement_index, k, v);}();
            bucket.value = v;
            static if ( is(V==StoredValueType) )
            {
                r = &bucket.value;
            }
            else
            {
                () @trusted {r = cast(V*)&bucket.value;}();
            }
        }
        else
        {
            debug(cachetools) () @nogc @trusted {tracef("place with allocation buckets[%d] '%s'='%s'", placement_index, k, v);}();
            if ( (bucket.hash & TYPE_MASK) == ALLOCATED_HASH )
            {
                // we just replace what we already allocated
                r = (bucket.value_ptr);
                *r = v;
            }
            else
            {
                r = bucket.value_ptr = make!(V)(allocator);
                *r = v;
            }
        }
        bucket.hash = computed_hash | ALLOCATED_HASH;
        bucket.key = k;
        return r;
    }

    bool remove(K k) @safe {

        if ( tooMuchDeleted ) {
            // do not shrink, just compact table
            doResize(_buckets_num);
        }


        debug(cachetools) () @nogc @trusted {tracef("remove k: %s", k);}();

        immutable computed_hash = hash_function(k) & HASH_MASK;
        immutable start_index = computed_hash & _mask;
        immutable lookup_index = findEntryIndex(start_index, computed_hash, k);
        if ( lookup_index == hash_t.max )
        {
            // nothing to remove
            return false;
        }

        assert((_buckets[lookup_index].hash & TYPE_MASK) == ALLOCATED_HASH, "tried to remove non allocated bucket");

        static if ( inlineValues )
        {
            // what we have to do with removed values XXX?
        }
        else
        {
            // what we have to do with removed values XXX?
            // free space
            (() @trusted {dispose(allocator, _buckets[lookup_index].value_ptr);})();
            _buckets[lookup_index].value_ptr = null;
        }

        _allocated--;
        immutable next_index = (lookup_index + 1) & _mask;
        // if next bucket is EMPTY, then we can convert all DELETED buckets down staring from current to EMPTY buckets
        if ( _buckets[next_index].hash == EMPTY_HASH )
        {
            _empty++;
            _buckets[lookup_index].hash = EMPTY_HASH;
            auto free_index = (lookup_index - 1) & _mask;
            while (free_index != lookup_index) {
                if ( _buckets[free_index].hash != DELETED_HASH ) {
                    break;
                }
                _buckets[free_index].hash = EMPTY_HASH;
                _deleted--;
                _empty++;
                free_index = (free_index - 1) & _mask;
            }
            assert(free_index != lookup_index, "table full of deleted buckets?");
        }
        else
        {
            _buckets[lookup_index].hash = DELETED_HASH;
            _deleted++;
        }
        return true;
    }
    void clear() @safe 
    {
        static if ( !inlineValues )
        {
           // dispose every element
           foreach(k; byKey)
           {
               remove(k);
           }
        }
        (() @trusted {
            GC.removeRange(_buckets.ptr);
            dispose(allocator, _buckets);
        })();
        _buckets = makeArray!(_Bucket)(allocator, _buckets_num);
        _allocated = _deleted = 0;
        _empty = _buckets_num;
    }
    auto length() const pure nothrow @nogc @safe
    {
        return _allocated;
    }

    auto size() const pure nothrow @nogc @safe
    {
        return _buckets_num;
    }

    auto byKey() pure @safe @nogc
    {
        struct _kvRange {
            int         _pos;
            ulong       _buckets_num;
            _Bucket[]   _buckets;
            this(_Bucket[] _b)
            {
                _buckets = _b;
                _buckets_num = _b.length;
                _pos = 0;
                while( _pos < _buckets_num  && _buckets[_pos].hash < ALLOCATED_HASH )
                {
                    _pos++;
                }
            }
            bool empty() const pure nothrow @safe @nogc
            {
                return _pos == _buckets_num;
            }
            K front()
            {
                return _buckets[_pos].key;
            }
            void popFront() pure nothrow @safe @nogc
            {
                _pos++;
                while( _pos < _buckets_num && _buckets[_pos].hash <  ALLOCATED_HASH )
                {
                    _pos++;
                }
            }
        }
        return _kvRange(_buckets);
    }

    auto byValue() pure @safe
    {
        struct _kvRange {
            int         _pos;
            ulong       _buckets_num;
            _Bucket[]   _buckets;
            this(_Bucket[] _b)
            {
                _buckets = _b;
                _buckets_num = _b.length;
                _pos = 0;
                while( _pos < _buckets_num  && _buckets[_pos].hash < ALLOCATED_HASH )
                {
                    _pos++;
                }
            }
            bool empty() const pure nothrow @safe @nogc
            {
                return _pos == _buckets_num;
            }
            V front()
            {
                static if (inlineValues)
                {
                    return _buckets[_pos].value;
                }
                else
                {
                    return *(_buckets[_pos].value_ptr);
                }
            }
            void popFront() pure nothrow @safe @nogc
            {
                _pos++;
                while( _pos < _buckets_num && _buckets[_pos].hash < ALLOCATED_HASH )
                {
                    _pos++;
                }
            }
        }
        return _kvRange(_buckets);
    }

    auto byPair() pure @safe
    {
        import std.typecons;

        struct _kvRange {
            int         _pos;
            ulong       _buckets_num;
            _Bucket[]   _buckets;
            this(_Bucket[] _b)
            {
                _buckets = _b;
                _buckets_num = _b.length;
                _pos = 0;
                while( _pos < _buckets_num  && _buckets[_pos].hash < ALLOCATED_HASH )
                {
                    _pos++;
                }
            }
            bool empty() const pure nothrow @safe @nogc
            {
                return _pos == _buckets_num;
            }
            auto front() @safe
            {
                static if (inlineValues)
                {
                    return Tuple!(K, "key", V, "value")(_buckets[_pos].key, _buckets[_pos].value);
                }
                else
                {
                    return Tuple!(K, "key", V, "value")(_buckets[_pos].key, *(_buckets[_pos].value_ptr));
                }
            }
            void popFront() pure nothrow @safe @nogc
            {
                _pos++;
                while( _pos < _buckets_num && _buckets[_pos].hash < ALLOCATED_HASH )
                {
                    _pos++;
                }
            }
        }
        return _kvRange(_buckets);
    }
}

/// Tests

/// test immutable struct and class as Key type
@safe unittest
{
    () @nogc
    {
        struct S
        {
            int s;
        }
        HashMap!(immutable S, int) hs1;
        immutable ss = S(1);
        hs1[ss] = 1;
        assert(ss in hs1 && *(ss in hs1) == 1);
        HashMap!(int, immutable S) hs2;
        hs2[1] = ss;
        assert(1 in hs2 && *(1 in hs2) == ss);
        assert(!(2 in hs2));
    }();

    // class
    class C
    {
        int v;
        this(int _v) pure inout
        {
            v = _v;
        }
        bool opEquals(const C o) pure const @safe @nogc nothrow {
            return v == o.v;
        }
        override hash_t toHash() const @safe @nogc {
            return hash_function(v);
        }
    }
    HashMap!(immutable C, int) hc1;
    immutable cc = new immutable C(1);
    hc1[cc] = 1;
    assert(hc1[cc] == 1);
    HashMap!(int, immutable C) hc2;
    hc2[1] = cc;
    assert(hc2[1] is cc);
}
@safe unittest {
    // test class as key
    globalLogLevel = LogLevel.info;
    class A {
        int v;

        bool opEquals(const A o) pure const @safe @nogc nothrow {
            return v == o.v;
        }
        override hash_t toHash() const @safe @nogc {
            return hash_function(v);
        }
        this(int v)
        {
            this.v = v;
        }
        override string toString() const
        {
            import std.format;
            return "A(%d)".format(v);
        }
    }

    globalLogLevel = LogLevel.info;
    auto x = new A(1);
    auto y = new A(2);
    HashMap!(A, string) dict;
    dict.put(x, "x");
    dict.put(y, "y");
}

@safe unittest {
    globalLogLevel = LogLevel.info;
    () @nogc {
        HashMap!(int, int) int2int;
        foreach(i; 1..5) {
            int2int.put(i,i);
        }
        int2int.put(33,33); // <- follow key 1, move key 2 on pos 3
        assert(1 in int2int, "1 not in hash");
        assert(2 in int2int, "2 not in hash");
        assert(1 in int2int, "3 not in hash");
        assert(4 in int2int, "4 not in hash");
        assert(33 in int2int, "33 not in hash");
        int2int.remove(33);
        int2int.put(2,2); // <- must replace key 2 on pos 3
        assert(2 in int2int, "2 not in hash");
    }();
    () @nogc {
        struct LargeStruct {
            ulong a;
            ulong b;
        }
        HashMap!(int, LargeStruct) int2ls;
        foreach(i; 1..5) {
            int2ls.put(i,LargeStruct(i,i));
        }
        int2ls.put(33,LargeStruct(33,33)); // <- follow key 1, move key 2 on pos 3
        assert(1 in int2ls, "1 not in hash");
        assert(2 in int2ls, "2 not in hash");
        assert(3 in int2ls, "3 not in hash");
        assert(4 in int2ls, "4 not in hash");
        assert(33 in int2ls, "33 not in hash");
        int2ls.remove(33);
        int2ls.put(2,LargeStruct(2,2)); // <- must replace key 2 on pos 3
        assert(2 in int2ls, "2 not in hash");
    }();
}

@safe unittest {
    globalLogLevel = LogLevel.info;
    () @nogc {
        assert(SmallValueFootprint!int());
        assert(SmallValueFootprint!double());
        struct SmallStruct {
            ulong a;
        }
        //assert(SmallValueFootprint!SmallStruct);
        struct LargeStruct {
            ulong a;
            ulong b;
        }
        assert(!SmallValueFootprint!LargeStruct);
        class SmallClass {
            ulong a;
        }
        //assert(!SmallValueFootprint!SmallClass);

        HashMap!(int, string) int2string;
        auto u = int2string.put(1, "one");
        {
            auto v = 1 in int2string;
            assert(v !is null);
            assert(*v == "one");
        }
        assert(2 !in int2string);
        u = int2string.put(32+1, "33");
        assert(33 in int2string);
        assert(int2string.remove(33));
        assert(!int2string.remove(33));
        
        HashMap!(int, LargeStruct) int2LagreStruct;
        int2LagreStruct.put(1, LargeStruct(1,2));
        {
            auto v = 1 in int2LagreStruct;
            assert(v !is null);
            assert(*v == LargeStruct(1, 2));
        }
    }();

    globalLogLevel = LogLevel.info;
}

@safe unittest {
    import std.experimental.allocator.gc_allocator;
    globalLogLevel = LogLevel.info;
    static int i;
    () @safe @nogc {
        struct LargeStruct {
            ulong a;
            ulong b;
            ~this() @safe @nogc {
                i++;
            }
        }
        HashMap!(int, LargeStruct) int2LagreStruct;
        int2LagreStruct.put(1, LargeStruct(1,2));
    }();
    globalLogLevel = LogLevel.info;
}

@safe unittest
{
    import std.typecons;
    alias K = Tuple!(int, int);
    alias V = int;
    HashMap!(K,V) h;
    K k0 = K(0,1);
    V v0 = 1;
    h.put(k0, v0);
    int *v = k0 in h;
    assert(v);
    assert(*v == 1);
    h[k0] = v0;
    assert(h[k0] == v0);
}

@safe unittest
{
    class c {
        int a;
        this(int a)
        {
            this.a = a;
        }
        override hash_t toHash() const pure @nogc @safe
        {
            return hash_function(a);
        }
        bool opEquals(const c other) pure const @safe @nogc
        {
            return this is other || this.a == other.a;
        }
    }
    alias K = c;
    alias V = int;
    K k0 = new c(0);
    V v0 = 1;
    () @nogc {
        HashMap!(K,V) h;
        h.put(k0, v0);
        int *v = k0 in h;
        assert(v);
        assert(*v == 1);
        h[k0] = 2;
        v = k0 in h;
        assert(*v == 2);
    }();
}

/// Test if we can work with non-@nogc opEquals for class-key.
/// opEquals anyway must be non-@system.
@safe unittest
{
    class c {
        int a;
        this(int a)
        {
            this.a = a;
        }
        override hash_t toHash() const pure @safe
        {
            int[] _ = [1, 2, 3]; // this cause GC
            return hash_function(a);
        }

        bool opEquals(const c other) const pure @safe
        {
            auto _ = [1,2,3]; // this cause GC
            return this is other || this.a == other.a;
        }
    }
    alias K = c;
    alias V = int;
    HashMap!(K,V) h;
    K k0 = new c(0);
    V v0 = 1;
    h.put(k0, v0);
    int *v = k0 in h;
    assert(v);
    assert(*v == 1);

}

@safe unittest
{
    import std.algorithm;
    import std.array;
    import std.stdio;

    HashMap!(int, string) m;
    m[1] = "one";
    m[2] = "two";
    m[10] = "ten";
    assert(equal(m.byKey.array.sort, [1,2,10]));
    assert(equal(m.byValue.array.sort, ["one", "ten", "two"]));
    assert(equal(
        m.byPair.map!"tuple(a.key, a.value)".array.sort, 
        [tuple(1, "one"), tuple(2, "two"), tuple(10, "ten")]
    ));
    m.remove(1);
    m.remove(10);
    assert(equal(
    m.byPair.map!"tuple(a.key, a.value)".array.sort,
        [tuple(2, "two")]
    ));
    m.remove(2);
    assert(m.byPair.map!"tuple(a.key, a.value)".array.sort.length() == 0);
    m.remove(2);
    assert(m.byPair.map!"tuple(a.key, a.value)".array.sort.length() == 0);
}

unittest {
    import std.random;
    import std.array;
    import std.algorithm;
    import std.stdio;

    enum iterations = 400_000;

    globalLogLevel = LogLevel.info;

    HashMap!(int, int) hashMap;
    int[int]             AA;

    auto rnd = Random(unpredictableSeed);

    foreach(i;0..iterations) {
        int k = uniform(0, iterations, rnd);
        hashMap.put(k, i);
        AA[k] = i;
    }
    assert(equal(AA.keys().sort(), hashMap.byKey().array.sort()));
    assert(equal(AA.values().sort(), hashMap.byValue().array.sort()));
    assert(AA.length == hashMap.length);
}

@safe unittest
{
    // test removal while iterating
    import std.random;
    import std.array;
    import std.algorithm;
    import std.stdio;

    enum iterations = 400_000;

    globalLogLevel = LogLevel.info;

    HashMap!(int, int) hashMap;

    auto rnd = Random(unpredictableSeed);

    foreach(i;0..iterations) {
        int k = uniform(0, iterations, rnd);
        hashMap[k] = i;
    }
    foreach(k; hashMap.byKey)
    {
        hashMap.remove(k);
    }
    assert(hashMap.length == 0);
}

@safe @nogc unittest
{
    // test clear

    HashMap!(int, int) hashMap;

    foreach(i;0..100) {
        hashMap[i] = i;
    }
    hashMap.clear();
    assert(hashMap.length == 0);
    hashMap[1] = 1;
    assert(1 in hashMap && hashMap.length == 1);
}

@safe @nogc unittest
{
    // test of nogc getOrAdd

    HashMap!(int, int) hashMap;

    foreach(i;0..100) {
        hashMap[i] = i;
    }
    auto v = hashMap.getOrAdd(-1, -1);
    assert(-1 in hashMap && v == -1);
}

@safe @nogc unittest
{
    // test of nogc getOrAdd with lazy default value

    HashMap!(int, int) hashMap;

    foreach(i;0..100) {
        hashMap[i] = i;
    }
    int v = hashMap.getOrAdd(-1, () => -1);
    assert(-1 in hashMap && v == -1);
    assert(hashMap.get(-1, 0) == -1); // key -1 is in hash, return value
    assert(hashMap.get(-2, 0) == 0);  // key -2 not in map, return default value
    assert(hashMap.get(-3, () => 0) == 0);  // ditto
}

@safe unittest
{
    import std.socket;
    HashMap!(string, Socket) socketPool;
    Socket s0 = socketPool.getOrAdd("http://example.com", () => new Socket(AddressFamily.INET, SocketType.STREAM));
    assert(s0 !is null);
    assert(s0.addressFamily == AddressFamily.INET);
    Socket s1 = socketPool.getOrAdd("http://example.com", () => new Socket(AddressFamily.INET, SocketType.STREAM));
    assert(s1 !is null);
    assert(s1 is s0);
}

@safe unittest
{
    import std.socket;
    class Connection {
        Socket s;
        bool opEquals(const Connection other) const pure @safe
        {
            return s is other.s;
        }
        override hash_t toHash() const @safe
        {
            return hash_function(s.handle);
        }
    }
    HashMap!(Connection, string) socketPool;
}

@safe unittest
{
    // test of non-@nogc getOrAdd with lazy default value
    import std.conv;
    import std.exception;
    class C {
        string v;
        this(int _v) @safe
        {
            v = to!string(_v);
        }
    }

    HashMap!(int, C) hashMap;

    foreach(i;0..100) {
        hashMap[i] = new C(i);
    }
    C v = hashMap.getOrAdd(-1, () => new C(-1));
    assert(-1 in hashMap && v.v == "-1");
    assert(hashMap[-1].v == "-1");
    hashMap[-1].v ~= "1";
    assert(hashMap[-1].v == "-11");
    assertThrown!KeyNotFound(hashMap[-2]);
    // check lazyness
    bool called;
    v = hashMap.getOrAdd(-1, delegate C() {called = true; return new C(0);});
    assert(!called);
    v = hashMap.getOrAdd(-2, delegate C() {called = true; return new C(0);});
    assert(called);
}

@safe @nogc unittest
{
    // test of nogc getOrAdd with lazy default value
    // corner case when V is callable

    alias F = int function() @safe @nogc;

    F one = function()
    {
        return 1;
    };
    F two = function()
    {
        return 2;
    };
    F three = function()
    {
        return 3;
    };
    F four = function()
    {
        return 4;
    };
    HashMap!(int, F) hashMap;
    hashMap.put(1, one);
    hashMap.put(2, two);
    auto p = 1 in hashMap;
    assert(p);
    assert((*p)() == 1);
    p = 2 in hashMap;
    assert(p);
    assert((*p)() == 2);
    auto f3 = hashMap.getOrAdd(3, () => function int() {return 3;}); // used as default()
    assert(f3() == 3);
    auto f4 = hashMap.getOrAdd(4, four);
    assert(f4() == 4);
}

// test get()
@safe @nogc unittest
{
    HashMap!(int, int) hashMap;
    int i = hashMap.get(1, 55);
    assert(i == 55);
    i = hashMap.get(1, () => 66);
    assert(i == 66);
    hashMap[1] = 1;
    i = hashMap.get(1, () => 66);
    assert(i == 1);
}