>My next goal is a persistent tree-map, probably cribbing from Haskell's >Data.Map.
I look forward to hearing how that goes! I've been meaning to make a data structure in Rust too, but it's hard to find the time, so how's about I tell you guys about it instead. I call my data structure an "optionally-persistent" hashtable or hashset. In C# I implemented this "optionally-persistent" hashtable and hashset with mutable and immutable variants of each (the term "semi-persistent" was already taken and means something else). I've been meaning to write an article about this, but didn't get around to it yet. Optionally-persistent means that it's structured as if it were persistent, but each node can be either mutable (locally) or immutable (recursively). Each node has a "frozen" flag which implicitly applies recursively to all children. Converting the tree from immutable to mutable, or mutable to immutable takes O(1) time. Immutable to mutable is essentially a no-op (the mutable copy has copy-on-write behavior), while mutable-to-immutable simply requires marking the root node as frozen. The "hashtable" is really a tree that is up to 8 levels deep, with each level representing 4 bits of the hashcode (not sure if this is the best approach). Lots more details in the doc comment: https://sourceforge.net/p/loyc/code/HEAD/tree/Src/Loyc.Collections/Sets/InternalSet.cs My benchmarks show that mutating such a set/map is dramatically faster than immutable editing (which requires copying multiple nodes for each change), and not that much slower than a traditional hashtable, so I think it's "hands down" superior to a traditional persistent hash tree. In my version, from the end-user's perspective, there's a separate data type for immutable and mutable versions of the data structure (MMap<T> and MSet<T> are mutable, Map<T> and Set<T> are immutable). Both data types encapsulate an instance of InternalSet<T> which is the "real" data structure. InternalSet<T> manages a tree of nodes, where each node has 16 entries and represents 4 bits of the hashcode. There's also an interesting variation called InvertibleSet<T>; an invertible set can represent a negative set such as "all integers except 0 and 1". -- - David http://loyc-etc.blogspot.com
_______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
