Skip to main content


Showing posts from May, 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…