Add HashSet implemented as HashMap with void value type

2 files changed, 109 insertions, 18 deletions

diff --git a/src/hash_map.cc b/src/hash_map.cc
index 6972f34b..245ff206 100644
--- a/src/hash_map.cc
+++ b/src/hash_map.cc
@@ -36,6 +36,7 @@ UnitTest test_hash_map{[] {
         map.insert({10, 1});
         map.insert({10, 2});
         kak_assert(map.find_index(10) == 0);
+        kak_assert(map.size() == 1);
         kak_assert(map[10] == 2);
         map.remove(10);
         kak_assert(map.find_index(10) == -1);
@@ -90,6 +91,61 @@ UnitTest test_hash_map{[] {
     }
 }};
 
+UnitTest test_hash_set{[] {
+    // Basic usage
+    {
+        HashSet<int> set;
+        set.insert({10});
+        set.insert({20});
+        kak_assert(set.find_index(0) == -1);
+        kak_assert(set.find_index(10) == 0);
+        kak_assert(set.find_index(20) == 1);
+        kak_assert(set[10] == 10);
+        kak_assert(set[20] == 20);
+        kak_assert(set[30] == 30);
+        set[30];
+        kak_assert(set.find_index(30) == 2);
+        set.remove(20);
+        kak_assert(set.find_index(30) == 1);
+        kak_assert(set.size() == 2);
+    }
+
+    // Replace Multiple entries with the same key
+    {
+        HashSet<int> set;
+        set.insert({10});
+        set.insert({10});
+        kak_assert(set.find_index(10) == 0);
+        kak_assert(set.size() == 1);
+        set.remove(10);
+        kak_assert(set.find_index(10) == -1);
+    }
+
+    // Multiple entries with the same key
+    {
+        MultiHashSet<int> set;
+        set.insert({10});
+        set.insert({10});
+        kak_assert(set.find_index(10) == 0);
+        set.remove(10);
+        kak_assert(set.find_index(10) == 0);
+        set.remove(10);
+        kak_assert(set.find_index(10) == -1);
+        set.insert({20});
+        set.insert({20});
+        set.remove_all(20);
+        kak_assert(set.find_index(20) == -1);
+    }
+
+    // Check hash compatible support
+    {
+        HashSet<String> set;
+        set.insert({"test"});
+        kak_assert(set["test"_sv] == "test");
+        set.remove("test"_sv);
+    }
+}};
+
 template<typename Map>
 void do_profile(size_t count, StringView type)
 {
diff --git a/src/hash_map.hh b/src/hash_map.hh
index 759cdbe7..0bf36f7d 100644
--- a/src/hash_map.hh
+++ b/src/hash_map.hh
@@ -154,8 +154,18 @@ private:
 template<typename Key, typename Value>
 struct HashItem
 {
+    Key key{};
+    Value value{};
+
+    friend bool operator==(const HashItem&, const HashItem&) = default;
+};
+
+template<typename Key>
+struct HashItem<Key, void>
+{
     Key key;
-    Value value;
+
+    friend bool operator==(const HashItem&, const HashItem&) = default;
 };
 
 template<typename Key, typename Value,
@@ -164,7 +174,9 @@ template<typename Key, typename Value,
          bool multi_key = false>
 struct HashMap
 {
-    using Item = HashItem<Key, Value>;
+    static constexpr bool has_value = not std::is_void_v<Value>;
+    using Item = std::conditional_t<has_value, HashItem<Key, Value>, Key>;
+    using EffectiveValue = std::conditional_t<has_value, Value, const Key>;
     using ContainerType = Container<Item, domain>;
 
     constexpr HashMap() = default;
@@ -175,22 +187,29 @@ struct HashMap
             m_index.add(hash_value(m_items[i].key), i);
     }
 
-    constexpr Value& insert(Item item)
+    template<typename Iterator>
+    constexpr HashMap(Iterator begin, Iterator end)
     {
-        const auto hash = hash_value(item.key);
+        while (begin != end)
+            insert(*begin++);
+    }
+
+    constexpr EffectiveValue& insert(Item item)
+    {
+        const auto hash = hash_value(item_key(item));
         if constexpr (not multi_key)
         {
-            if (auto index = find_index(item.key, hash); index >= 0)
+            if (auto index = find_index(item_key(item), hash); index >= 0)
             {
                 m_items[index] = std::move(item);
-                return m_items[index].value;
+                return item_value(m_items[index]);
             }
         }
 
         m_index.reserve(m_items.size()+1);
         m_index.add(hash, (int)m_items.size());
         m_items.push_back(std::move(item));
-        return m_items.back().value;
+        return item_value(m_items.back());
     }
 
     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
@@ -201,7 +220,7 @@ struct HashMap
             auto& entry = m_index[slot];
             if (entry.index == -1)
                 return -1;
-            if (entry.hash == hash and m_items[entry.index].key == key)
+            if (entry.hash == hash and item_key(m_items[entry.index]) == key)
                 return entry.index;
         }
         return -1;
@@ -214,17 +233,17 @@ struct HashMap
     constexpr bool contains(const KeyType& key) const { return find_index(key) >= 0; }
 
     template<typename KeyType> requires IsHashCompatible<Key, std::remove_cvref_t<KeyType>>
-    constexpr Value& operator[](KeyType&& key)
+    constexpr EffectiveValue& operator[](KeyType&& key) 
     {
         const auto hash = hash_value(key);
         auto index = find_index(key, hash);
         if (index >= 0)
-            return m_items[index].value;
+            return item_value(m_items[index]);
 
         m_index.reserve(m_items.size()+1);
         m_index.add(hash, (int)m_items.size());
-        m_items.push_back({Key(std::forward<KeyType>(key)), {}});
-        return m_items.back().value;
+        m_items.push_back({Key(std::forward<KeyType>(key))});
+        return item_value(m_items.back());
     }
 
     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
@@ -251,7 +270,7 @@ struct HashMap
             m_items.pop_back();
             m_index.remove(hash, index);
             if (index != m_items.size())
-                m_index.unordered_fix_entries(hash_value(m_items[index].key), m_items.size(), index);
+                m_index.unordered_fix_entries(hash_value(item_key(m_items[index])), m_items.size(), index);
         }
     }
 
@@ -308,11 +327,7 @@ struct HashMap
     template<MemoryDomain otherDomain>
     constexpr bool operator==(const HashMap<Key, Value, otherDomain, Container>& other) const
     {
-        return size() == other.size() and
-            std::equal(begin(), end(), other.begin(),
-                       [](const Item& lhs, const Item& rhs) {
-                           return lhs.key == rhs.key and lhs.value == rhs.value;
-                       });
+        return size() == other.size() and std::equal(begin(), end(), other.begin());
     }
 
     template<MemoryDomain otherDomain>
@@ -322,6 +337,16 @@ struct HashMap
     }
 
 private:
+    static EffectiveValue& item_value(Item& item)
+    {
+        if constexpr (has_value) { return item.value; } else { return item; }
+    }
+
+    static const Key& item_key(const Item& item)
+    {
+        if constexpr (has_value) { return item.key; } else { return item; }
+    }
+
     ContainerType m_items;
     HashIndex<domain, Container> m_index;
 };
@@ -331,6 +356,16 @@ template<typename Key, typename Value,
          template<typename, MemoryDomain> class Container = Vector>
  using MultiHashMap = HashMap<Key, Value, domain, Container, true>;
 
+template<typename Value,
+         MemoryDomain domain = MemoryDomain::Undefined,
+         template<typename, MemoryDomain> class Container = Vector>
+ using HashSet = HashMap<Value, void, domain, Container>;
+
+template<typename Value,
+         MemoryDomain domain = MemoryDomain::Undefined,
+         template<typename, MemoryDomain> class Container = Vector>
+ using MultiHashSet = HashMap<Value, void, domain, Container, true>;
+
 void profile_hash_maps();
 
 }