Make HashTable work complex types as key

- Add toHash() function for String
- The key type shouldn't match exact for a lookup.
The key type and lookup key type should be comparable.
- Move elements when inserting if passed by value.

4 files changed, 111 insertions, 13 deletions

diff --git a/source/tanya/container/entry.d b/source/tanya/container/entry.d
index a456dd9..214ba00 100644
--- a/source/tanya/container/entry.d
+++ b/source/tanya/container/entry.d
@@ -82,12 +82,18 @@ package struct Bucket(K, V = void)
         }
     }
 
-    bool opEquals(ref inout(K) key) inout
+    void moveKey(ref K key)
+    {
+        move(key, this.key());
+        this.status = BucketStatus.used;
+    }
+
+    bool opEquals(T)(ref const T key) const
     {
         return this.status == BucketStatus.used && this.key == key;
     }
 
-    bool opEquals(ref inout(typeof(this)) that) inout
+    bool opEquals(ref const(typeof(this)) that) const
     {
         return key == that.key && this.status == that.status;
     }
@@ -180,7 +186,7 @@ package struct HashArray(alias hasher, K, V = void)
      * Returns bucket position for `hash`. `0` may mean the 0th position or an
      * empty `buckets` array.
      */
-    size_t locateBucket(ref const Key key) const
+    size_t locateBucket(T)(ref const T key) const
     {
         return this.array.length == 0 ? 0 : hasher(key) % bucketCount;
     }
@@ -304,7 +310,7 @@ package struct HashArray(alias hasher, K, V = void)
         return 0;
     }
 
-    bool opBinaryRight(string op : "in")(ref inout(Key) key) inout
+    bool opBinaryRight(string op : "in", T)(ref const T key) const
     {
         foreach (ref e; this.array[locateBucket(key) .. $])
         {
diff --git a/source/tanya/container/hashtable.d b/source/tanya/container/hashtable.d
index deb0586..fc1c668 100644
--- a/source/tanya/container/hashtable.d
+++ b/source/tanya/container/hashtable.d
@@ -14,6 +14,7 @@
  */
 module tanya.container.hashtable;
 
+import tanya.algorithm.mutation;
 import tanya.container.array;
 import tanya.container.entry;
 import tanya.hash.lookup;
@@ -155,7 +156,7 @@ struct Range(T)
  *  hasher = Hash function for $(D_PARAM Key).
  */
 struct HashTable(Key, Value, alias hasher = hash)
-if (is(typeof(hasher(Key.init)) == size_t))
+if (is(typeof(((Key k) => hasher(k))(Key.init)) == size_t))
 {
     private alias HashArray = .HashArray!(hasher, Key, Value);
     private alias Buckets = HashArray.Buckets;
@@ -468,14 +469,28 @@ if (is(typeof(hasher(Key.init)) == size_t))
      *
      * Returns: Just inserted element.
      */
-    ref Value opIndexAssign(Value value, Key key)
+    ref Value opIndexAssign()(auto ref Value value, auto ref Key key)
     {
         auto e = ((ref v) @trusted => &this.data.insert(v))(key);
         if (e.status != BucketStatus.used)
         {
-            e.key = key;
+            static if (__traits(isRef, key))
+            {
+                e.key = key;
+            }
+            else
+            {
+                e.moveKey(key);
+            }
+        }
+        static if (__traits(isRef, value))
+        {
+            return e.kv.value = value;
+        }
+        else
+        {
+            return e.kv.value = move(value);
         }
-        return e.kv.value = value;
     }
 
     ///
@@ -505,7 +520,7 @@ if (is(typeof(hasher(Key.init)) == size_t))
      *
      * Returns: The number of the inserted elements with a unique key.
      */
-    size_t insert(KeyValue keyValue)
+    size_t insert(ref KeyValue keyValue)
     {
         auto e = ((ref v) @trusted => &this.data.insert(v))(keyValue.key);
         size_t inserted;
@@ -518,6 +533,20 @@ if (is(typeof(hasher(Key.init)) == size_t))
         return inserted;
     }
 
+    /// ditto
+    size_t insert(KeyValue keyValue)
+    {
+        auto e = ((ref v) @trusted => &this.data.insert(v))(keyValue.key);
+        size_t inserted;
+        if (e.status != BucketStatus.used)
+        {
+            e.moveKey(keyValue.key);
+            inserted = 1;
+        }
+        move(keyValue.value, e.kv.value);
+        return inserted;
+    }
+
     ///
     @nogc nothrow pure @safe unittest
     {
@@ -572,13 +601,15 @@ if (is(typeof(hasher(Key.init)) == size_t))
      * Find the element with the key $(D_PARAM key).
      *
      * Params:
+     *  T   = Type comparable with the key type, used for the lookup.
      *  key = The key to be find.
      *
      * Returns: The value associated with $(D_PARAM key).
      *
      * Precondition: Element with $(D_PARAM key) is in this hash table.
      */
-    ref Value opIndex(Key key)
+    ref Value opIndex(T)(auto ref const T key)
+    if (ifTestable!(T, a => Key.init == a))
     {
         const code = this.data.locateBucket(key);
 
@@ -634,12 +665,14 @@ if (is(typeof(hasher(Key.init)) == size_t))
      * Looks for $(D_PARAM key) in this hash table.
      *
      * Params:
+     *  T   = Type comparable with the key type, used for the lookup.
      *  key = The key to look for.
      *
      * Returns: $(D_KEYWORD true) if $(D_PARAM key) exists in the hash table,
      *          $(D_KEYWORD false) otherwise.
      */
-    bool opBinaryRight(string op : "in")(auto ref inout(Key) key) inout
+    bool opBinaryRight(string op : "in", T)(auto ref const T key) const
+    if (ifTestable!(T, a => Key.init == a))
     {
         return key in this.data;
     }
@@ -739,6 +772,9 @@ if (is(typeof(hasher(Key.init)) == size_t))
     static assert(is(HashTable!(string, int) a));
     static assert(is(const HashTable!(string, int)));
     static assert(isForwardRange!(HashTable!(string, int).Range));
+
+    static assert(is(HashTable!(int, int, (ref const int) => size_t.init)));
+    static assert(is(HashTable!(int, int, (int) => size_t.init)));
 }
 
 // Constructs by reference
@@ -809,3 +845,36 @@ if (is(typeof(hasher(Key.init)) == size_t))
         assert(hashtable[-1131293824] == 6);
     }
 }
+
+@nogc nothrow pure @safe unittest
+{
+    static struct String
+    {
+        bool opEquals(string) const @nogc nothrow pure @safe
+        {
+            return true;
+        }
+
+        bool opEquals(ref const string) const @nogc nothrow pure @safe
+        {
+            return true;
+        }
+
+        bool opEquals(String) const @nogc nothrow pure @safe
+        {
+            return true;
+        }
+
+        bool opEquals(ref const String) const @nogc nothrow pure @safe
+        {
+            return true;
+        }
+
+        size_t toHash() const @nogc nothrow pure @safe
+        {
+            return 0;
+        }
+    }
+    static assert(is(typeof("asdf" in HashTable!(String, int)())));
+    static assert(is(typeof(HashTable!(String, int)()["asdf"])));
+}
diff --git a/source/tanya/container/set.d b/source/tanya/container/set.d
index d578280..bd889a1 100644
--- a/source/tanya/container/set.d
+++ b/source/tanya/container/set.d
@@ -15,7 +15,6 @@
  */
 module tanya.container.set;
 
-import tanya.algorithm.mutation;
 import tanya.container.array;
 import tanya.container.entry;
 import tanya.hash.lookup;
@@ -460,6 +459,17 @@ if (is(typeof(hasher(T.init)) == size_t))
      *
      * Returns: Amount of new elements inserted.
      */
+    size_t insert(ref T value)
+    {
+        auto e = ((ref v) @trusted => &this.data.insert(v))(value);
+        if (e.status != BucketStatus.used)
+        {
+            e.moveKey(value);
+            return 1;
+        }
+        return 0;
+    }
+
     size_t insert(T value)
     {
         auto e = ((ref v) @trusted => &this.data.insert(v))(value);
@@ -551,12 +561,14 @@ if (is(typeof(hasher(T.init)) == size_t))
      * $(D_KEYWORD in) operator.
      *
      * Params:
+     *  U     = Type comparable with the element type, used for the lookup.
      *  value = Element to be searched for.
      *
      * Returns: $(D_KEYWORD true) if the given element exists in the container,
      *          $(D_KEYWORD false) otherwise.
      */
-    bool opBinaryRight(string op : "in")(auto ref inout(T) value) inout
+    bool opBinaryRight(string op : "in", U)(auto ref const U value) const
+    if (ifTestable!(U, a => T.init == a))
     {
         return value in this.data;
     }
diff --git a/source/tanya/container/string.d b/source/tanya/container/string.d
index ad8fa82..1eca1df 100644
--- a/source/tanya/container/string.d
+++ b/source/tanya/container/string.d
@@ -31,6 +31,7 @@ import std.algorithm.mutation : bringToFront, copy;
 import std.algorithm.searching;
 import tanya.algorithm.comparison;
 import tanya.algorithm.mutation;
+import tanya.hash.lookup;
 import tanya.memory;
 import tanya.meta.trait;
 import tanya.meta.transform;
@@ -1614,6 +1615,16 @@ struct String
         assert(s == "Казнить, нельзя помиловать.");
     }
 
+    /**
+     * Calculates the hash value for the string.
+     *
+     * Returns: Hash value for the string.
+     */
+    size_t toHash() const @nogc nothrow pure @safe
+    {
+        return hash(get);
+    }
+
     mixin DefaultAllocator;
 }