Dictionary.h

Go to the documentation of this file.

#pragma once
 
#include "Common.h"
#include "System/Object.h"
#include "System/Array.h"
#include "System/ArgumentException.h"
#include "System/InvalidOperationException.h"
#include "System/HashHelper.h"
#include <new>
#include <utility>
 
namespace DotNetDupe {
    namespace System {
        namespace Collections {
            namespace Generic {

                template <typename TKey, typename TValue>
                struct KeyValuePair {
                    TKey Key;     
                    TValue Value; 

                    KeyValuePair() {}

                    KeyValuePair(TKey k, TValue v) : Key(k), Value(v) {}
                };

                struct HashHelpers {
                    inline static const int s_primes[] = {
                        3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
                        1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
                        17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
                        187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
                        1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
                    };

                    static int GetPrime(int min) {
                        for (int i = 0; i < (int)(sizeof(s_primes) / sizeof(s_primes[0])); ++i) {
                            if (s_primes[i] >= min) return s_primes[i];
                        }
                        return min;
                    }
                };

                template <typename TKey, typename TValue>
                class Dictionary : public Object {
                private:
                    struct Entry {
                        int hashCode;
                        int next;
                        TKey key;
                        TValue value;
                        
                        Entry() : hashCode(-1), next(-1) {}
                        Entry(int h, int n, const TKey& k, const TValue& v) : hashCode(h), next(n), key(k), value(v) {}
                        Entry(const Entry& other) : hashCode(other.hashCode), next(other.next), key(other.key), value(other.value) {}
                        Entry(Entry&& other) noexcept : hashCode(other.hashCode), next(other.next), key(std::move(other.key)), value(std::move(other.value)) {}
                    };
 
                    int* m_pBuckets;
                    Entry* m_pEntries;
                    int m_iCount;
                    int m_iFreeList;
                    int m_iFreeCount;
                    int m_iCapacity;
 
                    void Initialize(int capacity) {
                        m_iCapacity = HashHelpers::GetPrime(capacity);
                        m_pBuckets = (int*)AllocateCollectionBuffer(m_iCapacity * sizeof(int));
                        for (int i = 0; i < m_iCapacity; i++) m_pBuckets[i] = -1;
                        m_pEntries = (Entry*)AllocateCollectionBuffer(m_iCapacity * sizeof(Entry));
                        m_iFreeList = -1;
                        m_iFreeCount = 0;
                        m_iCount = 0;
                    }
 
                    void FreeBuffer() {
                        if (m_pBuckets) FreeCollectionBuffer(m_pBuckets);
                        if (m_pEntries) {
                            for (int i = 0; i < m_iCount; ++i) {
                                if (m_pEntries[i].hashCode >= 0) m_pEntries[i].~Entry();
                            }
                            FreeCollectionBuffer(m_pEntries);
                        }
                        m_pBuckets = nullptr;
                        m_pEntries = nullptr;
                    }
 
                    void Resize() {
                        Resize(m_iCount > 0 ? m_iCount * 2 : 4);
                    }
 
                    void Resize(int newSize) {
                        int newCapacity = HashHelpers::GetPrime(newSize);
                        int* pNewBuckets = (int*)AllocateCollectionBuffer(newCapacity * sizeof(int));
                        for (int i = 0; i < newCapacity; i++) pNewBuckets[i] = -1;
                        Entry* pNewEntries = (Entry*)AllocateCollectionBuffer(newCapacity * sizeof(Entry));
                        for (int i = 0; i < m_iCount; i++) {
                            if (m_pEntries[i].hashCode >= 0) {
                                ::new ((void*)&pNewEntries[i]) Entry(std::move(m_pEntries[i]));
                                m_pEntries[i].~Entry();
                            } else {
                                ::new ((void*)&pNewEntries[i]) Entry();
                            }
                        }
                        for (int i = 0; i < m_iCount; i++) {
                            if (pNewEntries[i].hashCode >= 0) {
                                int bucket = pNewEntries[i].hashCode % newCapacity;
                                pNewEntries[i].next = pNewBuckets[bucket];
                                pNewBuckets[bucket] = i;
                            }
                        }
                        if (m_pBuckets) FreeCollectionBuffer(m_pBuckets);
                        if (m_pEntries) FreeCollectionBuffer(m_pEntries);
                        m_pBuckets = pNewBuckets;
                        m_pEntries = pNewEntries;
                        m_iCapacity = newCapacity;
                    }
 
                    int FindEntry(const TKey& key) const {
                        if (m_pBuckets != nullptr) {
                            int hashCode = HashHelper<TKey>::GetHashCode(key) & 0x7FFFFFFF;
                            for (int i = m_pBuckets[hashCode % m_iCapacity]; i >= 0; i = m_pEntries[i].next) {
                                if (m_pEntries[i].hashCode == hashCode && m_pEntries[i].key == key) return i;
                            }
                        }
                        return -1;
                    }
 
                    bool Insert(const TKey& key, const TValue& value, bool add) {
                        if (m_pBuckets == nullptr) Initialize(0);
                        int hashCode = HashHelper<TKey>::GetHashCode(key) & 0x7FFFFFFF;
                        int targetBucket = hashCode % m_iCapacity;
 
                        for (int i = m_pBuckets[targetBucket]; i >= 0; i = m_pEntries[i].next) {
                            if (m_pEntries[i].hashCode == hashCode && m_pEntries[i].key == key) {
                                if (add) throw System::ArgumentException("An item with the same key has already been added.");
                                m_pEntries[i].value = value;
                                return false;
                            }
                        }
 
                        int index;
                        if (m_iFreeCount > 0) {
                            index = m_iFreeList;
                            m_iFreeList = m_pEntries[index].next;
                            m_iFreeCount--;
                        } else {
                            if (m_iCount == m_iCapacity) {
                                Resize();
                                targetBucket = hashCode % m_iCapacity;
                            }
                            index = m_iCount;
                            m_iCount++;
                        }
                        ::new ((void*)&m_pEntries[index]) Entry(hashCode, m_pBuckets[targetBucket], key, value);
                        m_pBuckets[targetBucket] = index;
                        return true;
                    }
 
                public:
                    Dictionary() : m_pBuckets(nullptr), m_pEntries(nullptr), m_iCount(0), m_iFreeList(-1), m_iFreeCount(0), m_iCapacity(0) {}
                    
                    ~Dictionary() override {
                        FreeBuffer();
                    }
 
                    Dictionary(const Dictionary& other) : Dictionary() {
                        if (other.m_iCount > 0) {
                            Initialize(other.m_iCount);
                            for (int i = 0; i < other.m_iCount; i++) {
                                if (other.m_pEntries[i].hashCode >= 0) {
                                    Add(other.m_pEntries[i].key, other.m_pEntries[i].value);
                                }
                            }
                        }
                    }
 
                    Dictionary& operator=(const Dictionary& other) {
                        if (this != &other) {
                            Clear();
                            if (other.m_iCount > 0) {
                                Initialize(other.m_iCount);
                                for (int i = 0; i < other.m_iCount; i++) {
                                    if (other.m_pEntries[i].hashCode >= 0) {
                                        Add(other.m_pEntries[i].key, other.m_pEntries[i].value);
                                    }
                                }
                            }
                        }
                        return *this;
                    }
 
                    Dictionary(Dictionary&& other) noexcept : m_pBuckets(other.m_pBuckets), m_pEntries(other.m_pEntries), m_iCount(other.m_iCount), m_iFreeList(other.m_iFreeList), m_iFreeCount(other.m_iFreeCount), m_iCapacity(other.m_iCapacity) {
                        other.m_pBuckets = nullptr;
                        other.m_pEntries = nullptr;
                        other.m_iCount = 0;
                        other.m_iFreeList = -1;
                        other.m_iFreeCount = 0;
                        other.m_iCapacity = 0;
                    }
 
                    Dictionary& operator=(Dictionary&& other) noexcept {
                        if (this != &other) {
                            FreeBuffer();
                            m_pBuckets = other.m_pBuckets;
                            m_pEntries = other.m_pEntries;
                            m_iCount = other.m_iCount;
                            m_iFreeList = other.m_iFreeList;
                            m_iFreeCount = other.m_iFreeCount;
                            m_iCapacity = other.m_iCapacity;
                            other.m_pBuckets = nullptr;
                            other.m_pEntries = nullptr;
                            other.m_iCount = 0;
                            other.m_iFreeList = -1;
                            other.m_iFreeCount = 0;
                            other.m_iCapacity = 0;
                        }
                        return *this;
                    }
 
                    int GetCount() const { return m_iCount - m_iFreeCount; }
 
                    void Add(const TKey& key, const TValue& value) {
                        Insert(key, value, true);
                    }
 
                    bool Remove(const TKey& key) {
                        if (m_pBuckets != nullptr) {
                            int hashCode = HashHelper<TKey>::GetHashCode(key) & 0x7FFFFFFF;
                            int bucket = hashCode % m_iCapacity;
                            int last = -1;
                            for (int i = m_pBuckets[bucket]; i >= 0; last = i, i = m_pEntries[i].next) {
                                if (m_pEntries[i].hashCode == hashCode && m_pEntries[i].key == key) {
                                    if (last < 0) m_pBuckets[bucket] = m_pEntries[i].next;
                                    else m_pEntries[last].next = m_pEntries[i].next;
                                    m_pEntries[i].~Entry();
                                    m_pEntries[i].hashCode = -1;
                                    m_pEntries[i].next = m_iFreeList;
                                    m_iFreeList = i;
                                    m_iFreeCount++;
                                    return true;
                                }
                            }
                        }
                        return false;
                    }
 
                    void Clear() {
                        if (m_iCount > 0) {
                            for (int i = 0; i < m_iCapacity; i++) m_pBuckets[i] = -1;
                            for (int i = 0; i < m_iCount; i++) {
                                if (m_pEntries[i].hashCode >= 0) m_pEntries[i].~Entry();
                            }
                            m_iFreeList = -1;
                            m_iCount = 0;
                            m_iFreeCount = 0;
                        }
                    }
 
                    bool ContainsKey(const TKey& key) const {
                        return FindEntry(key) >= 0;
                    }
 
                    bool TryGetValue(const TKey& key, TValue& value) const {
                        int i = FindEntry(key);
                        if (i >= 0) {
                            value = m_pEntries[i].value;
                            return true;
                        }
                        return false;
                    }
 
                    TValue& operator[](const TKey& key) {
                        int i = FindEntry(key);
                        if (i >= 0) return m_pEntries[i].value;
                        Insert(key, TValue(), false);
                        return m_pEntries[FindEntry(key)].value;
                    }
 
                    const TValue& operator[](const TKey& key) const {
                        int i = FindEntry(key);
                        if (i >= 0) return m_pEntries[i].value;
                        throw System::ArgumentException("Key not found.");
                    }
 
                    Array<TKey> GetKeys() const {
                        Array<TKey> arrKeys(GetCount());
                        int index = 0;
                        for (int i = 0; i < m_iCount; ++i) {
                            if (m_pEntries[i].hashCode >= 0) arrKeys[index++] = m_pEntries[i].key;
                        }
                        return arrKeys;
                    }
 
                    Array<TValue> GetValues() const {
                        Array<TValue> arrValues(GetCount());
                        int index = 0;
                        for (int i = 0; i < m_iCount; ++i) {
                            if (m_pEntries[i].hashCode >= 0) arrValues[index++] = m_pEntries[i].value;
                        }
                        return arrValues;
                    }
 
                    class Iterator {
                    private:
                        const Dictionary* m_pDict;
                        int m_iIndex;
                        void AdvanceToValid() {
                            while (m_pDict && m_iIndex < m_pDict->m_iCount && m_pDict->m_pEntries[m_iIndex].hashCode < 0) {
                                m_iIndex++;
                            }
                        }
                    public:
                        Iterator(const Dictionary* dict, int index) : m_pDict(dict), m_iIndex(index) {
                            AdvanceToValid();
                        }
                        bool operator!=(const Iterator& other) const { return m_iIndex != other.m_iIndex; }
                        Iterator& operator++() {
                            m_iIndex++;
                            AdvanceToValid();
                            return *this;
                        }
                        KeyValuePair<TKey, TValue> operator*() const {
                            return KeyValuePair<TKey, TValue>(m_pDict->m_pEntries[m_iIndex].key, m_pDict->m_pEntries[m_iIndex].value);
                        }
                    };
 
                    Iterator begin() const { return Iterator(this, 0); }
                    Iterator end() const { return Iterator(this, m_iCount); }
                };
 
            }
        }
    }
}