🥮 mooncakes.io

    #Immutable Set

    ImmutableSet is an immutable, persistent implementation of the set structure (each operation returns a new ImmutableSet), implemented here using a balance tree.

    #Usage

    #Create

    Since set is based on comparison, the type used to construct ImmutableSet needs to implement Compare trait.

    You can create an empty ImmutableSet with a value separately through the following methods, or create it directly from the Array.

    ///|
    test {
      let _set1 : @sorted_set.SortedSet[Int] = @sorted_set.new()
      let _set2 = @sorted_set.singleton(1)
      let _set4 = @sorted_set.SortedSet([1])
      let _set5 = @sorted_set.SortedSet([1])
    }

    #Conversion

    You can convert an immutable set to an array, which will be sorted.

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

    #Add & Remove

    You can use add to add an element to the ImmutableSet.

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

    You can use remove to remove a specific value.

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

    #Max & Min & Contains

    You can use contains to query whether an element is in the set.

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

    You can also use min and max to obtain the minimum or maximum value in the set. When the set is empty, an error will be reported, and they have corresponding Option versions to handle this.

    ///|
    test {
      let set = @sorted_set.SortedSet([1, 2, 3, 4])
      @test.assert_eq(set.min(), 1)
      @test.assert_eq(set.max(), 4)
      @test.assert_eq(set.min_option(), Some(1))
      @test.assert_eq(set.max_option(), Some(4))
    }

    #Split & Union & Inter & Diff & Filter

    You can provide an intermediate value to divide a set into two sets by split, and whether the intermediate value is in the set will also be returned as the return value.

    ///|
    test {
      let (left, present, right) = @sorted_set.SortedSet([7, 2, 9, 4, 5, 6, 3, 8, 1]).split(
        5,
      )
      @test.assert_eq(present, true)
      @test.assert_eq(left.to_array(), [1, 2, 3, 4])
      @test.assert_eq(right.to_array(), [6, 7, 8, 9])
    }

    At the same time, you can use union and intersection to take the union or intersection of two sets.

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

    You can also use the difference function to obtain the difference between two sets.

    ///|
    test {
      let set1 = @sorted_set.SortedSet([1, 2, 3])
      let set2 = @sorted_set.SortedSet([4, 5, 1])
      @test.assert_eq(set1.difference(set2).to_array(), [2, 3])
    }

    You can use filter to filter the elements in the set.

    ///|
    test {
      let set = @sorted_set.SortedSet([1, 2, 3, 4, 5, 6])
      @test.assert_eq(set.filter(v => v % 2 == 0).to_array(), [2, 4, 6])
    }

    #Subset & Disjoint

    You can use subset and disjoint to determine the inclusion and separation relationship between two sets

    ///|
    test {
      @test.assert_eq(
        @sorted_set.SortedSet([1, 2, 3]).subset(
          SortedSet([7, 2, 9, 4, 5, 6, 3, 8, 1]),
        ),
        true,
      )
      @test.assert_eq(
        @sorted_set.SortedSet([1, 2, 3]).disjoint(SortedSet([4, 5, 6])),
        true,
      )
    }

    #Iter & Fold & Map

    Like other sequential containers, set also has iterative methods such as iter, fold, and map, and their order is based on the comparison being less than the order.

    ///|
    test {
      let arr = []
      @sorted_set.SortedSet([7, 2, 9, 4, 5, 6, 3, 8, 1]).each(v => arr.push(v))
      @test.assert_eq(arr, [1, 2, 3, 4, 5, 6, 7, 8, 9])
      let val = @sorted_set.SortedSet([1, 2, 3, 4, 5]).fold(init=0, (acc, x) => {
        acc + x
      })
      @test.assert_eq(val, 15)
      let set = @sorted_set.SortedSet([1, 2, 3])
      @test.assert_eq(set.map(x => x * 2).to_array(), [2, 4, 6])
    }

    You can also use rev_iter() to iterate in descending order.

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

    #All & Any

    all and any can detect whether all elements in the set match or if there are elements that match.

    ///|
    test {
      @test.assert_eq(@sorted_set.SortedSet([2, 4, 6]).all(v => v % 2 == 0), true)
      @test.assert_eq(@sorted_set.SortedSet([1, 4, 3]).any(v => v % 2 == 0), true)
    }

    #Empty

    is_empty can determine whether a set is empty.

    ///|
    test {
      let set1 : @sorted_set.SortedSet[Int] = SortedSet([])
      @test.assert_eq(set1.is_empty(), true)
      let set2 = @sorted_set.SortedSet([1])
      @test.assert_eq(set2.is_empty(), false)
    }

    SortedSet

    source
    type SortedSet[A]

    ImmutableSets are represented by size balanced binary trees: in every subtree of more than two elements, neither child's size exceeds 5 times the other's. Subtrees of one or two elements are exempt, so a two-element set may have children of size 1 and 0.
    impl Add for SortedSet[A]
    impl Compare for SortedSet[A]
    impl Default for SortedSet[A]
    impl Eq for SortedSet[A]
    impl Hash for SortedSet[A]
    impl Show for SortedSet[A]
    impl Sub for SortedSet[A]
    impl ToJson for SortedSet[A]
    impl Debug for SortedSet[K]
    impl FromJson for SortedSet[A]

    SortedSet::SortedSet

    source
    fn[A : Compare + Eq] SortedSet::SortedSet(array : ArrayView[A]) -> SortedSet[A]

    Initialize a SortedSet from an array.

    Example

    test {
      @test.assert_eq(@sorted_set.SortedSet([3, 1, 2, 3]).to_array(), [1, 2, 3])
    }

    SortedSet::add

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

    Insert a value into the ImmutableSet.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([6, 3, 8, 1]).add(5),
        SortedSet([1, 3, 5, 6, 8]),
      )
    }

    SortedSet::all

    source
    fn[A] SortedSet::all(self : SortedSet[A], f : (A) -> Bool raise?) -> Bool raise?

    Test if all values of the ImmutableSet satisfy the predicate.

    Example

    test {
      @test.assert_eq(@sorted_set.SortedSet([2, 4, 6]).all(v => v % 2 == 0), true)
    }

    SortedSet::any

    source
    fn[A] SortedSet::any(self : SortedSet[A], f : (A) -> Bool raise?) -> Bool raise?

    Checks if at least one element of the set satisfies the predicate.

    Example

    test {
      @test.assert_eq(@sorted_set.SortedSet([1, 4, 3]).any(v => v % 2 == 0), true)
    }

    SortedSet::compare

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

    SortedSet::contains

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

    Returns true if the set contains the given value.

    SortedSet::difference

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

    Returns the difference between self and other.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([1, 2, 3]).difference(SortedSet([4, 5, 1])),
        SortedSet([2, 3]),
      )
    }

    SortedSet::disjoint

    source
    fn[A : Compare + Eq] SortedSet::disjoint(self : SortedSet[A], other : SortedSet[A]) -> Bool

    Returns true if the two sets do not intersect.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([1, 2, 3]).disjoint(SortedSet([4, 5, 6])),
        true,
      )
    }

    SortedSet::each

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

    Iterates over the ImmutableSet.

    Example

    test {
      let arr = []
      @sorted_set.SortedSet([7, 2, 9, 4, 5, 6, 3, 8, 1]).each(x => arr.push(x))
      @test.assert_eq(arr, [1, 2, 3, 4, 5, 6, 7, 8, 9])
    }

    SortedSet::equal

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

    SortedSet::filter

    source
    fn[A] SortedSet::filter(self : SortedSet[A], f : (A) -> Bool raise?) -> SortedSet[A] raise?

    Filter the ImmutableSet.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([1, 2, 3, 4, 5, 6]).filter(v => v % 2 == 0),
        SortedSet([2, 4, 6]),
      )
    }

    SortedSet::fold

    source
    fn[A, B] SortedSet::fold(self : SortedSet[A], init~ : B, f : (B, A) -> B raise?) -> B raise?

    Fold the ImmutableSet.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([1, 2, 3, 4, 5]).fold(init=0, (acc, x) => acc + x),
        15,
      )
    }

    SortedSet::from_array

    source
    #deprecated("Use @immut/sorted_set.SortedSet([...]) instead")
    #as_free_fn(of, deprecated="Use @immut/sorted_set.SortedSet([...]) instead")
    #alias(of, deprecated="Use @immut/sorted_set.SortedSet([...]) instead")
    #as_free_fn(deprecated="Use @immut/sorted_set.SortedSet([...]) instead")
    fn[A : Compare + Eq] SortedSet::from_array(array : ArrayView[A]) -> SortedSet[A]

    Initialize a SortedSet[A] from an array. O(n) when the input is already monotonic, otherwise O(n*log n).

    SortedSet::from_iter

    source
    #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[A : Compare + Eq] SortedSet::from_iter(iter : Iter[A]) -> SortedSet[A]

    Creates a sorted set from an iterator of values.

    SortedSet::from_json

    source

    Create from json.

    SortedSet::hash

    source
    fn[A : Hash] SortedSet::hash(self : SortedSet[A]) -> Int

    SortedSet::intersection

    source
    #alias(inter, deprecated="`inter` is deprecated, use `intersection` instead")
    fn[A : Compare + Eq] SortedSet::intersection(self : SortedSet[A], other : SortedSet[A]) -> SortedSet[A]

    Returns the intersection of self with other.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([3, 4, 5]).intersection(SortedSet([4, 5, 6])),
        SortedSet([4, 5]),
      )
    }

    SortedSet::is_empty

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

    Returns true if sorted_set is empty

    SortedSet::iter

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

    Returns an iterator over elements in ascending order.

    SortedSet::length

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

    Returns the number of elements in the set.

    SortedSet::map

    source
    fn[A, B : Compare + Eq] SortedSet::map(self : SortedSet[A], f : (A) -> B raise?) -> SortedSet[B] raise?

    Maps the ImmutableSet.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([1, 2, 3]).map(x => x * 2),
        SortedSet([2, 4, 6]),
      )
    }

    SortedSet::max

    source
    fn[A] SortedSet::max(self : SortedSet[A]) -> A

    Returns the largest value in the sorted_set. This function will panic if the set is empty.

    Example

    test {
      @test.assert_eq(@sorted_set.SortedSet([7, 2, 9, 4, 5, 6, 3, 8, 1]).max(), 9)
    }

    SortedSet::max_option

    source
    fn[A] SortedSet::max_option(self : SortedSet[A]) -> A?

    Returns the largest value in the ImmutableSet. But returns None when the value does not exist.

    SortedSet::min

    source
    fn[A] SortedSet::min(self : SortedSet[A]) -> A

    Returns the smallest value in the sorted_set. This function will panic if the set is empty.

    Example

    test {
      @test.assert_eq(@sorted_set.SortedSet([7, 2, 9, 4, 5, 6, 3, 8, 1]).min(), 1)
    }

    SortedSet::min_option

    source
    fn[A] SortedSet::min_option(self : SortedSet[A]) -> A?

    Returns the smallest value in the sorted_set. But returns None when the value does not exist.

    SortedSet::new

    source
    #as_free_fn
    fn[A] SortedSet::new() -> SortedSet[A]

    Creates an empty immutable sorted set.

    SortedSet::range

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

    Returns an iterator over all values in the set that fall within the inclusive range [low, high].

    The iterator yields values in ascending order. Values equal to low or high are included if present.

    Arguments

    • low - The lower bound of the range (inclusive).
    • high - The upper bound of the range (inclusive).

    Returns

    An Iter[A] that yields values where low <= value <= high.

    Performance

    Time complexity is O(log n + k) where n is the size of the set and k is the number of elements in the range. The algorithm efficiently prunes subtrees that fall entirely outside the range.

    Behavior

    • If low > high, the iterator yields no elements.
    • If the range contains no values from the set, the iterator yields no elements.
    • The iterator is single-use; create a new one for multiple traversals.

    Example

    test {
      let set = @sorted_set.SortedSet([1, 2, 3, 4, 5])
      let result = []
      for v in set.range(low=2, high=4) {
        result.push(v)
      }
      @test.assert_eq(result, [2, 3, 4])
    }

    SortedSet::remove

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

    Remove a value from the ImmutableSet.

    Example

    test {
      @test.assert_eq(@sorted_set.SortedSet([3, 8, 1]).remove(8), SortedSet([1, 3]))
    }

    SortedSet::remove_min

    source
    fn[A] SortedSet::remove_min(self : SortedSet[A]) -> SortedSet[A]

    Remove the smallest value. This function will panic if the set is empty.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([3, 4, 5]).remove_min(),
        SortedSet([4, 5]),
      )
    }

    SortedSet::rev_iter

    source
    #alias(rev_iterator, deprecated="`rev_iterator` is deprecated, use `rev_iter` instead")
    fn[A] SortedSet::rev_iter(self : SortedSet[A]) -> Iter[A]

    Iterate over the elements in the set in descending order.

    Example

      let set = @sorted_set.SortedSet([1, 2, 3, 4, 5])
      let result = set.rev_iter().collect()
      @test.assert_eq(result, [5, 4, 3, 2, 1])

    SortedSet::singleton

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

    Returns the one-value ImmutableSet containing only value.

    SortedSet::split

    source
    fn[A : Compare + Eq] SortedSet::split(self : SortedSet[A], divide : A) -> (SortedSet[A], Bool, SortedSet[A])

    Returns a triple (left, present, right), where left < divide < right. present == false if self contains no value equal to divide, present == true if self contains a value equal to divide.

    Example

    test {
      let (left, present, right) = @sorted_set.SortedSet([7, 2, 9, 4, 5, 6, 3, 8, 1]).split(
        5,
      )
      inspect(present, content="true")
      @test.assert_eq(left, SortedSet([1, 2, 3, 4]))
      @test.assert_eq(right, SortedSet([6, 7, 8, 9]))
    }

    SortedSet::sub

    source
    fn[A : Compare + Eq] SortedSet::sub(self : SortedSet[A], other : SortedSet[A]) -> SortedSet[A]

    SortedSet::subset

    source
    fn[A : Compare + Eq] SortedSet::subset(self : SortedSet[A], other : SortedSet[A]) -> Bool

    Returns true if self is a subset of other.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([1, 2, 3]).subset(
          SortedSet([7, 2, 9, 4, 5, 6, 3, 8, 1]),
        ),
        true,
      )
    }

    SortedSet::symmetric_difference

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

    Returns a new set containing elements that are in either self or other, but not in both sets.

    Parameters:

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

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

    Example:

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

    SortedSet::to_array

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

    Returns an array of all elements in ascending order.

    SortedSet::to_json

    source
    fn[A : ToJson] SortedSet::to_json(self : SortedSet[A]) -> Json

    Convert to json.

    SortedSet::union

    source
    fn[A : Compare + Eq] SortedSet::union(self : SortedSet[A], other : SortedSet[A]) -> SortedSet[A]

    Returns the union of self and other.

    Example

    test {
      @test.assert_eq(
        @sorted_set.SortedSet([3, 4, 5]).union(SortedSet([4, 5, 6])),
        SortedSet([3, 4, 5, 6]),
      )
    }

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io