Tuesday, May 22, 2012

Hash Array Mapped Trie for C# - Feature Complete

I finally got around to finishing the immutable HAMT implementation I wrote about in my last post. The only missing features were tree merging and hash collision handling. Both features are now implemented with unit tests, and the whole branch has been merged back into "default".

It now also conforms to Sasa's standard collection semantics, namely the publicly exported type is a struct, so null reference errors are impossible, and it provides an atomic swap operation for concurrent use. Here's the API:

/// <summary>
/// An immutable hash-array mapped trie.
/// </summary>
/// <typeparam name="K">The type of keys.</typeparam>
/// <typeparam name="T">The type of values.</typeparam>
public struct Tree<K, T> : IEnumerable<KeyValuePair<K, T>>,
                           IAtomic<Tree<K, T>>
{
    /// <summary>
    /// The empty tree.
    /// </summary>
    public static Tree<K, T> Empty { get; }
    /// <summary>
    /// The number of elements in the tree.
    /// </summary>
    public int Count { get; }
    /// <summary>
    /// Find the value for the given key.
    /// </summary>
    /// <param name="key">The key to lookup.</param>
    /// <returns>
    /// The value corresponding to <paramref name="key"/>.
    /// </returns>
    /// <exception cref="KeyNotFoundException">
    /// Thrown if the key is not found in this tree.
    /// </exception>
    public T this[K key] { get; }
    /// <summary>
    /// Add the given key-value pair to the tree.
    /// </summary>
    /// <param name="key">The key.</param>
    /// <param name="value">The value for the given key.</param>
    /// <returns>A tree containing the key-value pair.</returns>
    public Tree<K, T> Add(K key, T value);
    /// <summary>
    /// Remove the element with the given key.
    /// </summary>
    /// <param name="key">The key to remove.</param>
    /// <returns>A tree without the value corresponding to
    /// <paramref name="key"/>.</returns>
    public Tree<K, T> Remove(K key);
    /// <summary>
    /// Merge two trees.
    /// </summary>
    /// <param name="other">The tree to merge with this one.</param>
    /// <returns>
    /// A tree merging the entries from <paramref name="other"/>.
    /// </returns>
    public Tree<K, T> Merge(Tree<K, T> other);
    /// <summary>
    /// Atomically set the slot.
    /// </summary>
    /// <param name="slot">The slot to set.</param>
    /// <returns>True if set atomically, false otherwise.</returns>
    public bool Set(ref Tree<K, T> slot);
}