Module imm/set
Persistent immutable hash set using a Hash Array Mapped Trie (HAMT).
Set(T) is a thin wrapper around Map(T, bool), backed by atomic object
nodes for thread-safe structural sharing. All mutations return new sets,
leaving the original unchanged.
Elements must implement Eq, Hash, and Send.
Examples
{ Set } :: import "std/imm/set";
s := Set(i32).new();
s = s.insert(i32(1));
s = s.insert(i32(2));
assert(s.contains(i32(1)), "set contains 1");
assert((s.len() == usize(2)), "two elements");
Membership, insert and remove are O(log32 n) and share every node the
mutation did not touch. The set operations (union, intersection,
difference, is_subset, is_disjoint) are eager: each walks a set and
builds a NEW one, so they cost O(n log32 n) rather than Rust's lazy
iterator adaptors. to_list() — and the IntoIterator behind
for(set, ...) — materializes an imm.List of the elements first, O(n).
Stability
unstable — two decisions from plans/STD_API_STABILIZATION.md still land
on this module. D16 ("HashSet(T) IS HashMap(T, unit)") says the same
treatment applies here, and it has NOT been done: the backing map is
Map(T, bool) whose value is always true, which costs a byte per entry
now that unit is a true ZST. And §4's open imm remove shape applies
as it does to imm.Map: remove(elem) -> Self cannot tell a caller
whether the element was present. Both change signatures or storage, so
neither can be frozen first.
Types
Persistent immutable hash set backed by a HAMT.
Wraps Map(T, bool) internally. The bool values are always true.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: (Eq(T), Hash, Send, Acyclic)), Set(T), Acyclic())
impl(generic(T : Type), where(T <: (Eq(T), Hash, Send, Acyclic)), Set(T), ...)
new : (fn() -> Self)Create an empty set.
Returns: Self
len : (fn(self : Self) -> usize)Number of elements.
Returns: usize
is_empty : (fn(self : Self) -> bool)Check if the set is empty.
Returns: bool
contains : (fn(self : Self, elem : T) -> bool)Check if the set contains elem.
Returns: bool
insert : (fn(self : Self, elem : T) -> Self)Return a new set with elem added.
Returns: Self
remove : (fn(self : Self, elem : T) -> Self)Return a new set with elem removed — im's without. An element that
is not present gives back an equal set, and says nothing about whether
anything was there; extract is the form that does.
Returns: Self
extract : (fn(self : Self, elem : T) -> Option(Self))The set WITHOUT elem, or .None when elem was not a member — im's
extract.
A set has no value to hand back, so the Option carries the whole
answer: .Some means "it was there, and here is the set without it",
.None means "nothing to remove, and your own set is already correct".
That is what remove alone cannot say — its result is
indistinguishable from a no-op.
Returns: Option(Self)
union : (fn(self : Self, other : Self) -> Self)Return the union of two sets (self ∪ other).
Returns: Self
intersection : (fn(self : Self, other : Self) -> Self)Return the intersection of two sets (self ∩ other).
Returns: Self
difference : (fn(self : Self, other : Self) -> Self)Return the difference (self \ other).
Returns: Self
is_subset : (fn(self : Self, other : Self) -> bool)Check if self is a subset of other.
Returns: bool
is_disjoint : (fn(self : Self, other : Self) -> bool)Check if two sets are disjoint.
Returns: bool
to_list : (fn(self : Self) -> List(T))Collect all elements into a List.
Returns: List(T)
from_list : (fn(l : ArrayList(T)) -> Self)Create a set from a slice of elements.
Returns: Self
impl(generic(T : Type), where(T <: (Eq(T), Hash, Send, Acyclic)), Set(T), Eq(Set(T))(...))
impl(generic(T : Type), where(T <: (Eq(T), Hash, Send, Acyclic)), Set(T), IntoIterator(...))
Item : TIntoIter : ListIter(T)into_iter : (fn(self : Self) -> ListIter(T))Returns: ListIter(T)
impl(generic(T : Type), where(T <: (Eq(T), Hash, Send, Acyclic)), Set(T), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self