core/data/ProbingHashMap.h

#ifndef CORE_PROBING_HASHMAP_H
#define CORE_PROBING_HASHMAP_H

#include "data/List.h"
#include "utils/ArrayString.h"
#include "utils/HashCode.h"
#include "utils/Logger.h"

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

        public:
            V& value;

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

            template<typename String>
            check_return Error toString(String& s) const {
                CORE_RETURN_ERROR(s.append(key));
                CORE_RETURN_ERROR(s.append(" = "));
                return s.append(value);
            }

        private:
            Node(const K& key_, V& value_) : key(key_), value(value_) {
            }
        };

    private:
        /*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<ProbingHashMap, EntryIterator>;
        using ConstEntryIteratorAdapter =
            IteratorAdapter<const ProbingHashMap, ConstEntryIterator>;

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

        using ConstKeyIteratorAdapter =
            IteratorAdapter<const ProbingHashMap, ConstKeyIterator>;*/

    private:
        List<K> keys;
        List<V> values;
        K emptyKey;
        int entries;

    public:
        ProbingHashMap(const K& emptyKey_) : emptyKey(emptyKey_), entries(0) {
        }

        /*check_return Error copyFrom(const ProbingHashMap& other) {
            ProbingHashMap copy;
            for(const auto& en : other) {
                CORE_RETURN_ERROR(copy.add(en.getKey(), en.value));
            }
            swap(copy.nodes, nodes);
            swap(copy.nodePointers, nodePointers);
            return Error::NONE;
        }*/

        check_return Error rehash(int minCapacity) {
            minCapacity *= 2;
            if(minCapacity <= keys.getLength()) {
                return Error::NONE;
            }
            ProbingHashMap<K, V> map(emptyKey);
            int l = 1 << Math::roundUpLog2(Core::Math::max(minCapacity, 8));
            CORE_RETURN_ERROR(map.keys.resize(l, emptyKey));
            CORE_RETURN_ERROR(map.values.resize(l));
            for(int i = 0; i < keys.getLength(); i++) {
                if(keys[i] != emptyKey) {
                    CORE_RETURN_ERROR(map.add(keys[i], values[i]));
                }
            }
            Core::swap(map.keys, keys);
            Core::swap(map.values, values);
            return Error::NONE;
        }

        /*template<typename... Args>
        check_return Error tryEmplace(V*& v, const K& key, Args&&... args) {
            CORE_RETURN_ERROR(rehash(nodes.getLength() + 1));
            int h = hashIndex(key);
            v = searchList(key, h);
            if(v != nullptr) {
                return Error::EXISTING_KEY;
            }
            NodePointer np = nullptr;
            CORE_RETURN_ERROR(nodes.put(np, key, Core::forward<Args>(args)...));
            Error e = Error::NONE;
            if(checkError(e, nodePointers[h].add(np))) {
                nodes.remove(np);
                return e;
            }
            v = &(np->data.value);
            return Error::NONE;
        }*/

        template<typename VA>
        check_return Error put(V*& v, const K& key, VA&& value) {
            CORE_RETURN_ERROR(rehash(entries + 1));
            int index = searchList(key);
            if(index < 0) {
                return Error::CAPACITY_REACHED;
            }
            entries += keys[index] != key;
            keys[index] = key;
            values[index] = Core::forward<VA>(value);
            v = &(values[index]);
            return Error::NONE;
        }

        template<typename VA>
        check_return Error add(const K& key, VA&& value) {
            V* v = nullptr;
            return put(v, key, Core::forward<VA>(value));
        }

        /*check_return Error remove(const K& key) {
            NodePointerList& list = nodePointers[hashIndex(key)];
            for(int i = 0; i < list.getLength(); i++) {
                if(list[i]->data.key == key) {
                    nodes.remove(list[i]);
                    return list.removeBySwap(i);
                }
            }
            return Error::NOT_FOUND;
        }*/

        const V* search(const K& key) const {
            int i = searchList(key);
            return i < 0 || keys[i] == emptyKey ? nullptr : &(values[i]);
        }

        V* search(const K& key) {
            int i = searchList(key);
            return i < 0 || keys[i] == emptyKey ? nullptr : &(values[i]);
        }

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

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

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

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

        /*ConstKeyIteratorAdapter keys() const {
            return keys.begin();
        }

        ValueIteratorAdapter values() {
            return values.begin();
        }

        ConstValueIteratorAdapter values() const {
            return values.begin();
        }*/

        /*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());
        }

        template<typename String>
        check_return Error toString(String& s) const {
            return Core::toString(s, *this);
        }*/

    private:
        int searchList(const K& key) const {
            int baseHash = static_cast<int>(hashCode(key));
            int end = keys.getLength() - 1;
            for(int i = 0; i <= end; i++) {
                int hash = (baseHash + i) & end;
                if(keys[hash] == emptyKey || keys[hash] == key) {
                    return hash;
                }
            }
            return -1;
        }

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

#endif