Deterministic lookup implementation with MemoryPack serialization

DDictionary.cs

using System;
using System.Collections.Generic;
using MemoryPack;

/// <summary>
/// A deterministic dictionary implementation optimized for lookups only.
/// Uses arrays for keys and values with a hash table for O(1) lookups.
/// Maintains MemoryPack serialization compatibility and preserves references.
/// </summary>
[MemoryPackable(GenerateType.CircularReference, SerializeLayout.Explicit)]
public partial class DDictionary<TKey, TValue>
{
    [MemoryPackInclude][MemoryPackOrder(0)] private int _count;
    [MemoryPackInclude][MemoryPackOrder(1)] private TKey[] _keys;
    [MemoryPackInclude][MemoryPackOrder(2)] private TValue[] _values;
    [MemoryPackInclude][MemoryPackOrder(3)] private bool[] _occupied;
    [MemoryPackInclude][MemoryPackOrder(4)] private int[] _hashTable;
    [MemoryPackInclude][MemoryPackOrder(5)] private int _hashTableSize;

    /// <summary>
    /// Current number of key-value pairs in the dictionary
    /// </summary>
    [MemoryPackIgnore] public int Count => _count;

    /// <summary>
    /// Current capacity of the internal arrays
    /// </summary>
    [MemoryPackIgnore] public int Capacity => _keys.Length;

    /// <summary>
    /// Whether the dictionary is empty
    /// </summary>
    [MemoryPackIgnore] public bool IsEmpty => _count == 0;

    /// <summary>
    /// Whether the dictionary is full (no more space for new pairs)
    /// </summary>
    [MemoryPackIgnore] public bool IsFull => _count >= _keys.Length;

    /// <summary>
    /// Whether the dictionary is read-only (always false for this implementation)
    /// </summary>
    [MemoryPackIgnore] public bool IsReadOnly => false;

    [MemoryPackConstructor]
    private DDictionary()
    {
        throw new NotImplementedException();
    }

    /// <summary>
    /// Initializes a new instance with specified capacity
    /// </summary>
    /// <param name="capacity">Fixed capacity</param>
    public DDictionary(int capacity)
    {
        if (capacity < 0)
            throw new ArgumentOutOfRangeException(nameof(capacity), "Capacity cannot be negative");

        _keys = new TKey[capacity];
        _values = new TValue[capacity];
        _occupied = new bool[capacity];

        // Initialize hash table (use prime size for better distribution)
        _hashTableSize = GetNextPrime(capacity * 2); // 2x capacity for load factor
        _hashTable = new int[_hashTableSize];
        Array.Fill(_hashTable, -1); // -1 means empty slot

        _count = 0;
    }

    /// <summary>
    /// Initializes a new instance with elements from a collection
    /// </summary>
    /// <param name="collection">Collection to copy elements from</param>
    /// <param name="capacity">Fixed capacity</param>
    public DDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, int capacity)
    {
        if (collection == null)
            throw new ArgumentNullException(nameof(collection));
        if (capacity < 0)
            throw new ArgumentOutOfRangeException(nameof(capacity), "Capacity cannot be negative");

        _keys = new TKey[capacity];
        _values = new TValue[capacity];
        _occupied = new bool[capacity];

        // Initialize hash table (use prime size for better distribution)
        _hashTableSize = GetNextPrime(capacity * 2); // 2x capacity for load factor
        _hashTable = new int[_hashTableSize];
        Array.Fill(_hashTable, -1); // -1 means empty slot

        _count = 0;

        foreach (var kvp in collection)
        {
            if (_count < capacity)
            {
                Add(kvp.Key, kvp.Value);
            }
        }
    }

    /// <summary>
    /// Gets or sets the value associated with the specified key
    /// </summary>
    /// <param name="key">The key</param>
    /// <returns>The value associated with the key</returns>
    public TValue this[TKey key]
    {
        get
        {
            int index = FindKeyIndex(key);
            if (index < 0)
                throw new KeyNotFoundException($"The key '{key}' was not found in the dictionary.");

            return _values[index];
        }
        set
        {
            int index = FindKeyIndex(key);
            if (index >= 0)
            {
                _values[index] = value;
            }
            else
            {
                Add(key, value);
            }
        }
    }

    /// <summary>
    /// Adds a key-value pair to the dictionary
    /// </summary>
    /// <param name="key">The key</param>
    /// <param name="value">The value</param>
    public void Add(TKey key, TValue value)
    {
        if (key == null)
            throw new ArgumentNullException(nameof(key));
        if (_count >= _keys.Length)
            throw new InvalidOperationException("Dictionary is full. Cannot add more elements.");
        if (ContainsKey(key))
            throw new ArgumentException("An element with the same key already exists in the dictionary.", nameof(key));

        // Find first empty slot in main arrays
        int arrayIndex = -1;
        for (int i = 0; i < _keys.Length; i++)
        {
            if (!_occupied[i])
            {
                arrayIndex = i;
                break;
            }
        }

        if (arrayIndex == -1)
            throw new InvalidOperationException("No empty slots available");

        // Add to main arrays
        _keys[arrayIndex] = key;
        _values[arrayIndex] = value;
        _occupied[arrayIndex] = true;
        _count++;

        // Add to hash table
        AddToHashTable(key, arrayIndex);
    }


    /// <summary>
    /// Removes the value with the specified key
    /// </summary>
    /// <param name="key">The key to remove</param>
    /// <returns>True if the key was found and removed</returns>
    public bool Remove(TKey key)
    {
        if (key == null)
            return false;

        int index = FindKeyIndex(key);
        if (index >= 0)
        {
            // Remove from hash table
            RemoveFromHashTable(key);

            // Don't set to default - just mark as unoccupied
            // This preserves references for MemoryPack serialization
            _occupied[index] = false;
            _count--;
            return true;
        }
        return false;
    }


    /// <summary>
    /// Determines whether the dictionary contains the specified key
    /// </summary>
    /// <param name="key">The key to locate</param>
    /// <returns>True if the key is found</returns>
    public bool ContainsKey(TKey key)
    {
        return FindKeyIndex(key) >= 0;
    }


    /// <summary>
    /// Gets the value associated with the specified key
    /// </summary>
    /// <param name="key">The key</param>
    /// <param name="value">When this method returns, contains the value associated with the key, if found</param>
    /// <returns>True if the key was found</returns>
    public bool TryGetValue(TKey key, out TValue value)
    {
        if (key == null)
        {
            value = default(TValue);
            return false;
        }

        int index = FindKeyIndex(key);
        if (index >= 0)
        {
            value = _values[index];
            return true;
        }

        value = default(TValue);
        return false;
    }

    /// <summary>
    /// Gets the value associated with the specified key, or the default value if the key is not found
    /// </summary>
    /// <param name="key">The key</param>
    /// <returns>The value associated with the key, or default(TValue) if not found</returns>
    public TValue GetValueOrDefault(TKey key)
    {
        return GetValueOrDefault(key, default(TValue));
    }

    /// <summary>
    /// Gets the value associated with the specified key, or the specified default value if the key is not found
    /// </summary>
    /// <param name="key">The key</param>
    /// <param name="defaultValue">The default value to return if the key is not found</param>
    /// <returns>The value associated with the key, or the default value if not found</returns>
    public TValue GetValueOrDefault(TKey key, TValue defaultValue)
    {
        if (key == null)
            return defaultValue;

        int index = FindKeyIndex(key);
        return index >= 0 ? _values[index] : defaultValue;
    }

    /// <summary>
    /// Removes all key-value pairs from the dictionary
    /// </summary>
    public void Clear()
    {
        // Don't clear the arrays - just mark all as unoccupied
        // This preserves references for MemoryPack serialization
        Array.Clear(_occupied, 0, _occupied.Length);

        // Reset hash table
        Array.Fill(_hashTable, -1);

        _count = 0;
    }

    /// <summary>
    /// Compacts the dictionary by moving all occupied entries to the front
    /// This should be called periodically to maintain performance
    /// </summary>
    public void Compact()
    {
        int writeIndex = 0;

        for (int readIndex = 0; readIndex < _keys.Length; readIndex++)
        {
            if (_occupied[readIndex])
            {
                if (writeIndex != readIndex)
                {
                    _keys[writeIndex] = _keys[readIndex];
                    _values[writeIndex] = _values[readIndex];
                    _occupied[writeIndex] = true;
                    _occupied[readIndex] = false;
                }
                writeIndex++;
            }
        }

        // Clear remaining slots
        for (int i = writeIndex; i < _keys.Length; i++)
        {
            _keys[i] = default(TKey);
            _values[i] = default(TValue);
            _occupied[i] = false;
        }

        // Rebuild hash table after compaction
        Array.Fill(_hashTable, -1);
        for (int i = 0; i < writeIndex; i++)
        {
            AddToHashTable(_keys[i], i);
        }
    }


    /// <summary>
    /// Gets the next prime number greater than or equal to the given number
    /// </summary>
    /// <param name="min">Minimum value</param>
    /// <returns>Next prime number</returns>
    private static int GetNextPrime(int min)
    {
        // Simple prime finder - you could use a lookup table for small values
        for (int i = min; i < min + 1000; i++)
        {
            if (IsPrime(i)) return i;
        }
        return min; // Fallback
    }

    /// <summary>
    /// Checks if a number is prime
    /// </summary>
    /// <param name="n">Number to check</param>
    /// <returns>True if prime</returns>
    private static bool IsPrime(int n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        for (int i = 3; i * i <= n; i += 2)
        {
            if (n % i == 0) return false;
        }
        return true;
    }

    /// <summary>
    /// Gets a deterministic hash code for the key
    /// </summary>
    /// <param name="key">The key to hash</param>
    /// <returns>Hash code</returns>
    private int GetHashCode(TKey key)
    {
        if (key == null) return 0;
        return key.GetHashCode() & int.MaxValue; // Ensure positive
    }

    /// <summary>
    /// Adds a key to the hash table
    /// </summary>
    /// <param name="key">The key to add</param>
    /// <param name="arrayIndex">The index in the main arrays</param>
    private void AddToHashTable(TKey key, int arrayIndex)
    {
        int hash = GetHashCode(key);
        int index = hash % _hashTableSize;

        // Linear probing for collision resolution
        for (int i = 0; i < _hashTableSize; i++)
        {
            int slotIndex = (index + i) % _hashTableSize;
            if (_hashTable[slotIndex] == -1)
            {
                _hashTable[slotIndex] = arrayIndex;
                return;
            }
        }

        // This should never happen with proper load factor
        throw new InvalidOperationException("Hash table is full");
    }

    /// <summary>
    /// Removes a key from the hash table
    /// </summary>
    /// <param name="key">The key to remove</param>
    private void RemoveFromHashTable(TKey key)
    {
        int hash = GetHashCode(key);
        int index = hash % _hashTableSize;

        // Find and remove from hash table
        for (int i = 0; i < _hashTableSize; i++)
        {
            int slotIndex = (index + i) % _hashTableSize;
            int keyIndex = _hashTable[slotIndex];

            if (keyIndex == -1) return; // Not found

            if (_occupied[keyIndex] && EqualityComparer<TKey>.Default.Equals(_keys[keyIndex], key))
            {
                _hashTable[slotIndex] = -1;
                return;
            }
        }
    }

    /// <summary>
    /// Finds the index of the specified key in the internal arrays using hash table
    /// </summary>
    /// <param name="key">The key to find</param>
    /// <returns>The index of the key, or -1 if not found</returns>
    private int FindKeyIndex(TKey key)
    {
        if (key == null)
            return -1;

        int hash = GetHashCode(key);
        int index = hash % _hashTableSize;

        // Linear probing for collision resolution
        for (int i = 0; i < _hashTableSize; i++)
        {
            int slotIndex = (index + i) % _hashTableSize;
            int keyIndex = _hashTable[slotIndex];

            if (keyIndex == -1) return -1; // Not found
            if (_occupied[keyIndex] && EqualityComparer<TKey>.Default.Equals(_keys[keyIndex], key))
                return keyIndex;
        }
        return -1;
    }


}