BufferMap - A dense, associative map from handle to value, with O(1) amortized complexity for all operations.

BufferMap.cs

// SPDX-License-Identifier: MIT
// Author: pema99

// This file contains an implementation of a data structure I've named a BufferMap.
// It works as a map from 'handles' to values, where handles are just integers.
// You insert values into the map, and are returned an automatically generated handle.
// You can then use this handle to retrieve the value, or remove it from the map.
// Handles are never invalidated until they are explicitly removed.
// Amortized time complexities for adding, removing and getting a value from
// the map are all O(1). Additionally, the data structure has the property that
// the value store is always dense array with no holes, which is useful if you for
// example plan to upload it to a GPU.

public class BufferMap<T>
    where T : struct
{
    public record struct Handle
    {
        public int Id { get; set; }

        public Handle(int value)
        {
            Id = value;
        }

        public static Handle Invalid = new(-1);
    }

    // Handle generation
    private Queue<Handle> freeHandles = new();
    private int nextHandle = 0;

    // Handle <-> Index
    private int[] handleToIndex;
    private Handle[] indexToHandle;

    // Value store
    private T[] values;
    private int count = 0;

    public BufferMap()
        : this(8) {}

    public BufferMap(int capacity)
    {
        handleToIndex = new int[capacity];
        indexToHandle = new Handle[capacity];
        values = new T[capacity];

        Array.Fill(handleToIndex, -1);
        Array.Fill(indexToHandle, Handle.Invalid);
    }

    private void GrowBuffersIfNeeded(int desiredSize)
    {
        int capacity = values.Length;
        if (desiredSize > capacity)
        {
            int newCapacity = capacity > 0 ? capacity * 2 : 1;
            Array.Resize(ref values, newCapacity);
            Array.Resize(ref handleToIndex, newCapacity);
            Array.Resize(ref indexToHandle, newCapacity);
        }
    }

    private Handle AllocateHandle()
    {
        if (freeHandles.Count > 0)
        {
            return freeHandles.Dequeue();
        }
        else
        {
            return new Handle(nextHandle++);
        }
    }

    private void ReleaseHandle(Handle handle)
    {
        freeHandles.Enqueue(handle);
    }

    public bool Contains(Handle handle)
    {
        return handleToIndex[handle.Id] >= 0;
    }

    public Handle Add(in T value)
    {
        GrowBuffersIfNeeded(count + 1);   // We may have to grow the buffers to fit the new element
        Handle handle = AllocateHandle(); // Allocate handle
        handleToIndex[handle.Id] = count; // Update 2-way mapping
        indexToHandle[count] = handle;
        values[count] = value;            // Store value at the end of the array
        count++;                          // Increase size
        return handle;
    }

    public T Get(Handle handle)
    {
        int index = handleToIndex[handle.Id];
        return values[index];
    }

    public ref T GetReference(Handle handle)
    {
        int index = handleToIndex[handle.Id];
        return ref values[index];
    }

    public bool Remove(Handle handle)
    {
        int index = handleToIndex[handle.Id];         // Get index of the given handle
        if (index < 0)
            return false;
       
        ReleaseHandle(handle);                        // Release the handle
        count--;
        values[index] = values[count];                // Move the last elements value to the removed element's position

        var lastElementHandle = indexToHandle[count]; // Find the handle of the last element
        indexToHandle[index] = lastElementHandle;     // The new handle for the overwritten element is the handle of the last element
        handleToIndex[lastElementHandle.Id] = index;  // The last element's handle now corresponds to the overwritten element's index

        // Not strictly necessary stuff, but nice for debugging
        handleToIndex[handle.Id] = -1;
        indexToHandle[count] = Handle.Invalid;
        
        return true;
    }

    public bool Update(Handle handle, in T value)
    {
        int index = handleToIndex[handle.Id];
        if (index < 0)
            return false;

        values[index] = value;
        return true;
    }

    public T this[Handle handle]
    {
        get => Get(handle);
        set => Update(handle, value);
    }

    public int Length => count;

    public T[] Buffer => values;

    public override string ToString()
    {
        string result = "BufferMap(";
        for (int i = 0; i < count; i++)
        {
            result += values[i] + ", ";
        }
        return result + ")";
    }
}

// This is just some quick and dirty testing code to prove that the data structure stays consistent under random operations.
public class Test
{
    public static bool CheckConsistency(Dictionary<char, List<BufferMap<char>.Handle>> handles, BufferMap<char> map)
    {
        foreach (var pair in handles)
        {
            foreach (var handle in pair.Value)
            {
                try
                {
                    if (map.Get(handle) != pair.Key)
                    {
                        return false;
                    }
                } 
                catch
                {
                    Console.WriteLine("Failed to check " + pair.Key + " with handle " + handle.Id);
                    return false;
                }
            }
        }
        return true;
    }

    public static void Main()
    {
        BufferMap<char> map = new();

        Dictionary<char, List<BufferMap<char>.Handle>> handles = new();
        for (char c = 'a'; c <= 'z'; c++)
        {
            handles.Add(c, new List<BufferMap<char>.Handle>());
        }
        
        Random rand = new Random(1421214);
        for (int i = 0; i < 3000; i++)
        {
            bool anythingToRemove = handles.Where((pair) => pair.Value.Count > 0).Count() > 0;

            // Insert
            if (!anythingToRemove || rand.NextDouble() > 0.5)
            {
                char c = (char)('a' + rand.Next(0, 26));
                var handle = map.Add(c);
                handles[c].Add(handle);
            }
            // Remove
            else
            {
                char c;
                do 
                {
                    c = (char)('a' + rand.Next(0, 26));
                } while (handles[c].Count == 0);

                var all = handles[c];
                if (all.Count > 0)
                {
                    int index = rand.Next(0, all.Count);
                    var handle = all[index];
                    map.Remove(handle);
                    all.RemoveAt(index);
                }
            }
        }
    }
}