Module imm/sorted_set
Persistent immutable sorted set using a left-leaning red-black tree.
SortedSet(T) is a thin wrapper around SortedMap(T, bool), keeping
elements in sorted order. All mutations return new sets, leaving the
original unchanged.
Elements must implement Eq, Ord, and Send.
Examples
{ SortedSet } :: import "std/imm/sorted_set";
s := SortedSet(i32).new();
s = s.insert(i32(3));
s = s.insert(i32(1));
s = s.insert(i32(2));
// elements are always sorted: 1, 2, 3
contains, insert and remove are O(log n) through the tree, and
min/max are the leftmost/rightmost walk. The set operations are
eager — each builds a new set, O(n log n) — and to_list(), like the
IntoIterator behind for(set, ...), materializes an imm.List in
ascending order, O(n).
Stability
unstable — inherits both open questions of the map it wraps
(plans/STD_API_STABILIZATION.md §4): remove(elem) -> Self cannot say
whether the element was present, and the wrapper stores
SortedMap(T, bool) where D16's rule for HashSet says the value slot
should be unit, now that unit is a true ZST. Freezing follows those
two.
Types
Persistent immutable sorted set backed by a left-leaning red-black tree.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: (Eq(T), Ord(T), Send, Acyclic)), SortedSet(T), Acyclic())
impl(generic(T : Type), where(T <: (Eq(T), Ord(T), Send, Acyclic)), SortedSet(T), ...)
new : (fn() -> Self)Create an empty sorted 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)
min : (fn(self : Self) -> Option(T))Get the minimum element.
Returns: Option(T)
max : (fn(self : Self) -> Option(T))Get the maximum element.
Returns: Option(T)
to_list : (fn(self : Self) -> List(T))Return elements as a sorted List.
Returns: List(T)
union : (fn(self : Self, other : Self) -> Self)Return the union of two sorted sets.
Returns: Self
intersection : (fn(self : Self, other : Self) -> Self)Return the intersection of two sorted sets.
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 sorted sets are disjoint.
Returns: bool
from_list : (fn(l : ArrayList(T)) -> Self)Create a sorted set from a slice of elements.
Returns: Self
impl(generic(T : Type), where(T <: (Eq(T), Ord(T), Send, Acyclic)), SortedSet(T), Eq(SortedSet(T))(...))
impl(generic(T : Type), where(T <: (Eq(T), Ord(T), Send, Acyclic)), SortedSet(T), IntoIterator(...))
Item : TIntoIter : ListIter(T)into_iter : (fn(self : Self) -> ListIter(T))Returns: ListIter(T)
impl(generic(T : Type), where(T <: (Eq(T), Ord(T), Send, Acyclic)), SortedSet(T), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self