#Sorted Set

    A mutable set backed by an AVL tree that maintains elements in sorted order.

    #Usage

    Floating elements and keys used by ordinary comparison-based operations must not be NaN, including floating components of derived/composite keys. Signed zeros, infinities, and subnormals are supported. This is an input precondition, not an automatic NaN check; see the Eq and Compare trait contracts.

    #Create

    You can create an empty SortedSet or a SortedSet from other containers.

    ///|
    test {
    let _set1 : @sorted_set.SortedSet[Int32] = SortedSet([])
    let _set2 = @sorted_set.singleton(1)
    let _set3 = @sorted_set.from_array([1])
    }

    #Container Operations

    Add an element to the SortedSet in place.

    ///|
    test {
    let set4 = @sorted_set.from_array([1, 2, 3, 4])
    set4.add(5) // ()
    let set6 = @sorted_set.from_array([1, 2, 3, 4, 5])
    @test.assert_eq(set6.to_array(), [1, 2, 3, 4, 5])
    }

    Remove an element from the SortedSet in place.

    ///|
    test {
    let set = @sorted_set.from_array([3, 8, 1])
    set.remove(8) // ()
    let set7 = @sorted_set.from_array([1, 3])
    @test.assert_eq(set7.to_array(), [1, 3])
    }

    Whether an element is in the set.

    ///|
    test {
    let set = @sorted_set.from_array([1, 2, 3, 4])
    @test.assert_eq(set.contains(1), true)
    @test.assert_eq(set.contains(5), false)
    }

    Iterates over the elements in the set.

    ///|
    test {
    let arr = []
    @sorted_set.from_array([1, 2, 3, 4]).each(v => arr.push(v))
    @test.assert_eq(arr, [1, 2, 3, 4])
    }

    Get the size of the set.

    ///|
    test {
    let set = @sorted_set.from_array([1, 2, 3, 4])
    @test.assert_eq(set.length(), 4)
    }

    Whether the set is empty.

    ///|
    test {
    let set : @sorted_set.SortedSet[Int32] = SortedSet([])
    @test.assert_eq(set.is_empty(), true)
    }

    #Set Operations

    Union, intersection and difference of two sets. They return a new set that does not overlap with the original sets in memory.

    ///|
    test {
    let set1 = @sorted_set.from_array([3, 4, 5])
    let set2 = @sorted_set.from_array([4, 5, 6])
    let set3 = set1.union(set2)
    @test.assert_eq(set3.to_array(), [3, 4, 5, 6])
    let set4 = set1.intersection(set2)
    @test.assert_eq(set4.to_array(), [4, 5])
    let set5 = set1.difference(set2)
    @test.assert_eq(set5.to_array(), [3])
    }

    Determine the inclusion and separation relationship between two sets.

    ///|
    test {
    let set1 = @sorted_set.from_array([1, 2, 3])
    let set2 = @sorted_set.from_array([7, 2, 9, 4, 5, 6, 3, 8, 1])
    @test.assert_eq(set1.is_subset(set2), true)
    let set3 = @sorted_set.from_array([4, 5, 6])
    @test.assert_eq(set1.is_disjoint(set3), true)
    }

    #Symmetric Difference

    Elements in one set but not both:

    ///|
    test {
    let a = @sorted_set.from_array([1, 2, 3])
    let b = @sorted_set.from_array([2, 3, 4])
    @test.assert_eq(a.symmetric_difference(b).to_array(), [1, 4])
    }

    #Range Queries

    range(low, high) returns an iterator over elements in [low, high]:

    ///|
    test {
    let set = @sorted_set.from_array([1, 3, 5, 7, 9, 11])
    let in_range = set.range(3, 9).collect()
    @test.assert_eq(in_range, [3, 5, 7, 9])
    }

    #Indexed Iteration

    eachi iterates with an index (in sorted order):

    ///|
    test {
    let set = @sorted_set.from_array([10, 20, 30])
    let pairs = []
    set.eachi(fn(i, v) { pairs.push((i, v)) })
    @test.assert_eq(pairs, [(0, 10), (1, 20), (2, 30)])
    }

    #Iterators & Conversion

    ///|
    test {
    let set = @sorted_set.from_array([3, 1, 2])
    // iter returns elements in sorted order
    debug_inspect(set.iter().to_array(), content="[1, 2, 3]")
    // to_array
    @test.assert_eq(set.to_array(), [1, 2, 3])
    // from_iter
    let set2 = @sorted_set.from_iter([|4, 5, 6|])
    @test.assert_eq(set2.to_array(), [4, 5, 6])
    }

    #Copy

    copy() creates a shallow clone:

    ///|
    test {
    let set = @sorted_set.from_array([1, 2, 3])
    let cloned = set.copy()
    cloned.add(4)
    @test.assert_eq(set.to_array(), [1, 2, 3]) // original unchanged
    @test.assert_eq(cloned.to_array(), [1, 2, 3, 4])
    }

    #@debug.Debug

    SortedSet implements @debug.Debug, which allows you to inspect its elements in sorted order.

    ///|
    test {
    let set = @sorted_set.from_array([1, 2, 3])
    debug_inspect(
    set,
    content=(
    #|<SortedSet: [1, 2, 3]>
    ),
    )
    }

    #Performance

    • add: O(log n)
    • remove: O(log n)
    • contains: O(log n)
    • iterate: O(n)
    • space complexity: O(n)

    #Implementation Notes

    The SortedSet is implemented as an AVL tree, a self-balancing binary search tree. After insertions and deletions, the tree automatically rebalances to maintain O(log n) search, insertion, and deletion times.

    Key properties of the AVL tree implementation:
    • Each node stores a height field indicating the height of that subtree
    • The balance factor (height difference between left and right subtrees) is maintained between -1 and 1 for all nodes
    • Rebalancing is done through tree rotations (single and double rotations)

    #Comparison with Other Collections

    • @hashset.HashSet: Provides O(1) average case lookups but doesn't maintain order; use when order doesn't matter
    • @sorted_set.SortedSet: Maintains elements in sorted order; use when you need elements to be sorted

    Choose SortedSet when you need:
    • Elements in sorted order
    • Efficient ordered iteration
    • Logarithmic time operations

    SortedSet

    type SortedSet[V]

    impl Compare for SortedSet[V]
    impl Default for SortedSet[K]
    impl Eq for SortedSet[V]
    impl Show for SortedSet[V]
    impl FromJson for SortedSet[V]
    impl ToJson for SortedSet[V]

    SortedSet::SortedSet

    #as_free_fn(of, deprecated="Use from_array instead")
    #alias(of, deprecated="Use from_array instead")
    #as_free_fn(from_array)
    #alias(from_array)
    fn[V : Compare + Eq] SortedSet::SortedSet(array : ArrayView[V]) -> SortedSet[V]

    Initialize a set from an array.

    Of several equal values, the first one is kept, as if the values were added in order.

    Example

    test {
    let set = @sorted_set.SortedSet([3, 1, 2])
    @test.assert_eq(set.length(), 3)
    }

    SortedSet::add

    fn[V : Compare + Eq] SortedSet::add(self : SortedSet[V], value : V) -> Unit

    Adds a value to the set. If an equal value is already present, the set is left unchanged (the existing value is kept).

    SortedSet::clear

    fn[V] SortedSet::clear(self : SortedSet[V]) -> Unit

    Removes all elements from the set.

    Example

    test {
    let set = @sorted_set.SortedSet([3, 1, 2])
    set.clear()
    inspect(set.is_empty(), content="true")
    }

    SortedSet::compare

    fn[V : Compare + Eq] SortedSet::compare(self : SortedSet[V], other : SortedSet[V]) -> Int

    SortedSet::contains

    fn[V : Compare + Eq] SortedSet::contains(self : SortedSet[V], value : V) -> Bool

    Returns true if the set contains the given value.

    SortedSet::copy

    #alias(clone, deprecated="`clone` is deprecated, use `copy` instead")
    #alias(deep_clone, deprecated="`deep_clone` is deprecated, use `copy` instead")
    fn[V] SortedSet::copy(self : SortedSet[V]) -> SortedSet[V]

    Returns a shallow copy of the set.

    It is just copying the tree structure, not the values.

    SortedSet::difference

    #alias(diff, deprecated="`diff` is deprecated, use `difference` instead")
    fn[V : Compare + Eq] SortedSet::difference(self : SortedSet[V], src : SortedSet[V]) -> SortedSet[V]

    Returns a new set containing elements in self that are not in src.

    SortedSet::each

    fn[V] SortedSet::each(self : SortedSet[V], f : (V) -> Unit raise?) -> Unit raise?

    Iterates over all elements in the set in ascending order.

    If f structurally modifies the set (adds or removes elements, or clears it), the result is unspecified, though memory-safe.

    SortedSet::eachi

    fn[V] SortedSet::eachi(self : SortedSet[V], f : (Int, V) -> Unit raise?) -> Unit raise?

    Iterates over all elements in the set with their index, in ascending order.

    If f structurally modifies the set (adds or removes elements, or clears it), the result is unspecified, though memory-safe.

    SortedSet::equal

    fn[V : Eq] SortedSet::equal(self : SortedSet[V], other : SortedSet[V]) -> Bool

    SortedSet::from_iter

    #as_free_fn(from_iterator, deprecated="Use SortedSet::from_iter instead.")
    #alias(from_iterator, deprecated="`from_iterator` is deprecated, use `from_iter` instead")
    #as_free_fn
    fn[V : Compare + Eq] SortedSet::from_iter(iter : Iter[V]) -> SortedSet[V]

    Creates a set from an iterator of values.

    Of several equal values, the first one is kept, as if the values were added in order.

    SortedSet::intersection

    #alias(intersect, deprecated="`intersect` is deprecated, use `intersection` instead")
    fn[V : Compare + Eq] SortedSet::intersection(self : SortedSet[V], src : SortedSet[V]) -> SortedSet[V]

    Returns a new set containing only elements present in both sets.

    SortedSet::is_disjoint

    #alias(disjoint, deprecated="Use `is_disjoint` instead")
    fn[V : Compare + Eq] SortedSet::is_disjoint(self : SortedSet[V], src : SortedSet[V]) -> Bool

    Returns true if the two sets have no elements in common.

    SortedSet::is_empty

    fn[V] SortedSet::is_empty(self : SortedSet[V]) -> Bool

    Returns true if the set contains no elements.

    SortedSet::is_subset

    #alias(subset, deprecated="Use `is_subset` instead")
    fn[V : Compare + Eq] SortedSet::is_subset(self : SortedSet[V], src : SortedSet[V]) -> Bool

    Returns true if every element of self is also in src.

    SortedSet::is_superset

    fn[V : Compare + Eq] SortedSet::is_superset(self : SortedSet[V], src : SortedSet[V]) -> Bool

    Returns true if every element of src is also in self.

    SortedSet::iter

    #alias(iterator, deprecated="`iterator` is deprecated, use `iter` instead")
    fn[V] SortedSet::iter(self : SortedSet[V]) -> Iter[V]

    Returns an iterator over the elements in ascending order.

    If the set is structurally modified (elements added or removed, or the set cleared) while the iterator is in use, what it yields is unspecified, though memory-safe.

    SortedSet::length

    #alias(size, deprecated="`size` is deprecated, use `length` instead")
    fn[V] SortedSet::length(self : SortedSet[V]) -> Int

    Returns the number of elements in the set.

    SortedSet::new

    #as_free_fn(deprecated="Use `SortedSet([])` instead")
    #deprecated("Use `SortedSet([])` instead")
    fn[V] SortedSet::new() -> SortedSet[V]

    Construct an empty set.

    Deprecated: use SortedSet([]) instead.

    SortedSet::range

    fn[V : Compare + Eq] SortedSet::range(self : SortedSet[V], low : V, high : V) -> Iter[V]

    Returns an iterator over elements in the range [low, high] (inclusive).

    If the set is structurally modified (elements added or removed, or the set cleared) while the iterator is in use, what it yields is unspecified, though memory-safe.

    SortedSet::remove

    fn[V : Compare + Eq] SortedSet::remove(self : SortedSet[V], value : V) -> Unit

    Removes a value from the set. Does nothing if the value is not present.

    SortedSet::singleton

    #as_free_fn
    fn[V] SortedSet::singleton(value : V) -> SortedSet[V]

    Returns the one-value set containing only value.

    SortedSet::symmetric_difference

    fn[V : Compare + Eq] SortedSet::symmetric_difference(self : SortedSet[V], other : SortedSet[V]) -> SortedSet[V]

    Returns a new set containing elements that are in either of the two sets, but not in their intersection. In other words, returns a new set containing elements that are in exactly one of the two sets.

    Parameters:

    • self : The first set.
    • other : The second set.

    Returns a new set containing elements that appear in exactly one of the input sets.

    Example:

    test {
    let set1 = @sorted_set.from_array([1, 2, 3, 4])
    let set2 = @sorted_set.from_array([3, 4, 5, 6])
    let diff = set1.symmetric_difference(set2)
    @debug.debug_inspect(
    diff,
    content=(
    #|<SortedSet: [1, 2, 5, 6]>
    ),
    )
    }

    SortedSet::to_array

    fn[V] SortedSet::to_array(self : SortedSet[V]) -> Array[V]

    Converts the set to an array.

    SortedSet::union

    fn[V : Compare + Eq] SortedSet::union(self : SortedSet[V], src : SortedSet[V]) -> SortedSet[V]

    Returns a new set containing all elements from both sets.