🥮 mooncakes.io
README

#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 inter 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 diff 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 subsets 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 balanced binary trees (the heights of the children differ by at most 2).
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.

#
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

Get the height of 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 n 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