imbl

imbl provides efficient immutable data structures for Rust that utilize structural sharing. This means that when you copy or modify a data structure, most of the memory is shared between the original and the new version, making operations like cloning very cheap (essentially just incrementing a reference counter).

Supported Data Structures

Key Concepts

• Lazy Cloning: Cloning a data structure is an instant operation that only increments a reference count. Actual data cloning happens lazily only when a specific node is modified (Copy-on-Write).
• In-place Mutation: If you are the sole owner of a data structure (reference count is 1), imbl can perform in-place mutations, making it nearly as fast as standard mutable collections.
• Value Requirements: Values stored in these structures must implement Clone. For expensive-to-clone values, wrap them in std::rc::Rc or std::sync::Arc to store only the pointer.

The HashSet<A> is an immutable hash set implementation using Hash Array Mapped Tries (HAMT). It is a generic set where values must implement Hash and Eq. Most operations are $O(\log_{x} n)$, which is nearly $O(1)$ for most sets.

By default, HashSet<A> uses std::collections::hash_map::RandomState as the hasher and DefaultSharedPtr as the pointer type.

Key characteristics:

• Immutability: Operations like update or without return a new set rather than mutating the existing one in place (though insert and remove do provide in-place mutation for the local instance).
• Predictable Order: Values have a predictable order based on the hasher used, though this is not insertion or sort order.
• Efficiency: Cloning is $O(1)$ due to the underlying structural sharing.

# #[macro_use] extern crate imbl;
# use imbl::HashSet;
# fn main() {
# assert_eq!(
#   hashset![1, 2, 3],
#   HashSet::from(vec![1, 2, 3])
# );
# }

A Focus provides optimized indexing over a Vector. It works by caching the last accessed tree node and the path taken to reach it, making lookups for adjacent or nearby indices significantly faster than standard index lookups.

When to use Focus:

• Batching lookups: When performing a large number of index lookups that are likely to be close to each other.
• Random access performance: Even for random access, Focus often provides a performance gain over standard vec.get(i) calls.

When NOT to use Focus:

• Sequential iteration: If you are just iterating forwards or backwards, use a standard Vector::iter() instead. Iterators are implemented using Focus internally but provide a simpler, more idiomatic interface.
• Small vectors: For vectors with a length below the internal RRB tree branching factor (64), the setup cost of Focus may outweigh the benefits.
• Few lookups: If you only need to perform a very small number of lookups, the overhead is not worth it.

# #[macro_use] extern crate imbl;
# use imbl::vector::Vector;
# use std::iter::FromIterator;
let mut vec: Vector<i64> = Vector::from_iter(0..1000);

// Summing a vector faster using a Focus:
let mut sum = 0;
let mut focus = vec.focus();
for i in 0..1000 {
    sum += *focus.get(i).unwrap();
}
assert_eq!(499500, sum);