core/data/HashMap.h

#ifndef CORE_HASHMAP_H
#define CORE_HASHMAP_H

#include <stdio.h>

#include "data/LinkedList.h"
#include "data/List.h"
#include "math/Math.h"
#include "utils/String.h"
#include "utils/Types.h"

namespace Core {
    template<typename K, typename V>
    struct HashMap final {
        class Node final {
            friend HashMap;
            friend List<Node>;
            friend LinkedList<Node>;
            K key;

        public:
            V value;

            const K& getKey() const {
                return key;
            }

        private:
            template<typename... Args>
            Node(const K& key_, Args&&... args)
                : key(key_), value(Core::forward<Args>(args)...) {
            }
        };
        using NodePointer = LinkedList<Node>::Node*;
        using NodePointerList = List<NodePointer>;
        using NodeIterator = LinkedList<Node>::Iterator;
        using ConstNodeIterator = LinkedList<Node>::ConstIterator;

        template<typename N, typename I, typename R, R& (*A)(I&)>
        class Iterator final {
            N iterator;

        public:
            Iterator(N iterator_) : iterator(iterator_) {
            }

            Iterator& operator++() {
                ++iterator;
                return *this;
            }

            bool operator!=(const Iterator& other) const {
                return iterator != other.iterator;
            }

            R& operator*() const {
                return A(*iterator);
            }
        };

        template<typename R>
        static R& access(R& node) {
            return node;
        }

        template<typename I, typename R>
        static R& accessValue(I& node) {
            return node.value;
        }

        static const K& accessKey(const Node& node) {
            return node.getKey();
        }

        template<typename N, typename R>
        using BaseEntryIterator = Iterator<N, R, R, access<R>>;
        using EntryIterator = BaseEntryIterator<NodeIterator, Node>;
        using ConstEntryIterator =
            BaseEntryIterator<ConstNodeIterator, const Node>;

        template<typename N, typename I, typename R>
        using BaseValueIterator = Iterator<N, I, R, accessValue<I, R>>;
        using ValueIterator = BaseValueIterator<NodeIterator, Node, V>;
        using ConstValueIterator =
            BaseValueIterator<ConstNodeIterator, const Node, const V>;

        using ConstKeyIterator =
            Iterator<ConstNodeIterator, const Node, const K, accessKey>;

        template<typename M, typename I>
        struct IteratorAdapter final {
            M& map;

            I begin() const {
                return I(map.nodes.begin());
            }

            I end() const {
                return I(map.nodes.end());
            }
        };

        using EntryIteratorAdapter = IteratorAdapter<HashMap, EntryIterator>;
        using ConstEntryIteratorAdapter =
            IteratorAdapter<const HashMap, ConstEntryIterator>;

        using ValueIteratorAdapter = IteratorAdapter<HashMap, ValueIterator>;
        using ConstValueIteratorAdapter =
            IteratorAdapter<const HashMap, ConstValueIterator>;

        using ConstKeyIteratorAdapter =
            IteratorAdapter<const HashMap, ConstKeyIterator>;

    private:
        LinkedList<Node> nodes;
        List<NodePointerList> nodePointers;

    public:
        // returns true on error
        check_return bool copyFrom(const HashMap& other) {
            HashMap copy;
            for(const auto& e : other) {
                if(copy.add(e.getKey(), e.value)) {
                    return true;
                }
            }
            swap(copy.nodes, nodes);
            swap(copy.nodePointers, nodePointers);
            return false;
        }

        // returns true on error
        check_return bool rehash(int minCapacity) {
            if(minCapacity <= nodePointers.getLength()) {
                return false;
            }
            HashMap<K, V> map;
            int l = 1 << Math::roundUpLog2(Core::Math::max(minCapacity, 8));
            if(map.nodePointers.resize(l)) {
                return true;
            }
            for(NodePointerList& list : nodePointers) {
                for(NodePointer& n : list) {
                    int h = map.hashIndex(n->data.key);
                    if(map.nodePointers[h].add(n)) {
                        return true;
                    }
                }
            }
            Core::swap(map.nodePointers, nodePointers);
            return false;
        }

        // returns true on error
        template<typename... Args>
        check_return bool tryEmplace(const K& key, Args&&... args) {
            if(rehash(nodes.getLength() + 1)) {
                return true;
            }
            int h = hashIndex(key);
            V* v = searchList(key, h);
            if(v != nullptr) {
                return true;
            }
            NodePointer np = nodes.add(key, Core::forward<Args>(args)...);
            if(np == nullptr) {
                return true;
            } else if(nodePointers[h].add(np)) {
                nodes.remove(np);
                return true;
            }
            return false;
        }

        // returns true on error
        template<typename VA>
        check_return bool add(const K& key, VA&& value) {
            if(rehash(nodes.getLength() + 1)) {
                return true;
            }
            int h = hashIndex(key);
            V* v = searchList(key, h);
            if(v == nullptr) {
                NodePointer np = nodes.add(key, Core::forward<VA>(value));
                if(np == nullptr) {
                    return true;
                } else if(nodePointers[h].add(np)) {
                    nodes.remove(np);
                    return true;
                }
            } else {
                *v = Core::forward<VA>(value);
            }
            return false;
        }

        // returns true when a value was removed
        check_return bool remove(const K& key) {
            NodePointerList& list = nodePointers[hashIndex(key)];
            for(int i = 0; i < list.getLength(); i++) {
                if(list[i]->data.key == key) {
                    NodePointer np = list[i];
                    bool r = list.removeBySwap(i);
                    nodes.remove(np);
                    return !r;
                }
            }
            return false;
        }

        const V* search(const K& key) const {
            return searchList(key, hashIndex(key));
        }

        V* search(const K& key) {
            return searchList(key, hashIndex(key));
        }

        bool contains(const K& key) const {
            return search(key) != nullptr;
        }

        HashMap& clear() {
            nodes.clear();
            for(NodePointerList& n : nodePointers) {
                n.clear();
            }
            return *this;
        }

        EntryIteratorAdapter entries() {
            return {*this};
        }

        ConstEntryIteratorAdapter entries() const {
            return {*this};
        }

        ConstKeyIteratorAdapter keys() const {
            return {*this};
        }

        ValueIteratorAdapter values() {
            return {*this};
        }

        ConstValueIteratorAdapter values() const {
            return {*this};
        }

        EntryIterator begin() {
            return EntryIterator(nodes.begin());
        }

        EntryIterator end() {
            return EntryIterator(nodes.end());
        }

        ConstEntryIterator begin() const {
            return ConstEntryIterator(nodes.begin());
        }

        ConstEntryIterator end() const {
            return ConstEntryIterator(nodes.end());
        }

        void toString(String& s) const {
            s.append("[");
            bool c = false;
            for(const NodePointerList& list : nodePointers) {
                for(const NodePointer& n : list) {
                    if(c) {
                        s.append(", ");
                    }
                    s.append(n->data.key).append(" = ").append(n->data.value);
                    c = true;
                }
            }
            s.append("]");
        }

    private:
        template<typename H>
        int hashIndex(const H& key) const {
            return static_cast<int>(fullHash(key)) &
                   (nodePointers.getLength() - 1);
        }

        template<typename H>
        Hash fullHash(const H& key) const {
            return key.hashCode();
        }

        Hash fullHash(int key) const {
            static_assert(sizeof(key) == sizeof(Hash),
                          "unwanted loose of precision in hash");
            return static_cast<Hash>(key);
        }

        Hash fullHash(unsigned int key) const {
            static_assert(sizeof(key) == sizeof(Hash),
                          "unwanted loose of precision in hash");
            return key;
        }

        const V* searchList(const K& key, int h) const {
            if(nodePointers.getLength() == 0) {
                return nullptr;
            }
            for(const NodePointer& n : nodePointers[h]) {
                if(n->data.key == key) {
                    return &n->data.value;
                }
            }
            return nullptr;
        }

        V* searchList(const K& key, int h) {
            return const_cast<V*>(
                static_cast<const HashMap*>(this)->searchList(key, h));
        }
    };
}

#endif