// Copyright 2026 International Digital Economy Academy
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
/// Constructions
///|
fn[V] new_sorted_set() -> SortedSet[V] {
{ root: None, size: 0, }
}
///|
/// Returns the one-value set containing only `value`.
#as_free_fn
#owned(value)
pub fn[V] SortedSet::singleton(value : V) -> SortedSet[V] {
{ root: Some({ value, left: None, right: None, height: 1, }), size: 1, }
}
///|
/// Initialize a set from an array.
///
/// # Example
/// ```mbt check
/// test {
/// let set = @sorted_set.SortedSet([3, 1, 2])
/// @test.assert_eq(set.length(), 3)
/// }
/// ```
#alias(from_array)
#as_free_fn(from_array)
#alias(of, deprecated="Use from_array instead")
#as_free_fn(of, deprecated="Use from_array instead")
pub fn[V : Compare] SortedSet::SortedSet(array : ArrayView[V]) -> SortedSet[V] {
let set = new_sorted_set()
for x in array {
set.add(x)
}
set
}
///|
/// Returns a shallow copy of the set.
///
/// It is just copying the tree structure, not the values.
///
#alias(deep_clone, deprecated)
#alias(clone, deprecated)
pub fn[V] SortedSet::copy(self : SortedSet[V]) -> SortedSet[V] {
match self.root {
None => new_sorted_set()
Some(_) => { root: copy_tree(self.root), size: self.size, }
}
}
///|
fn[V] copy_tree(node : Node[V]?) -> Node[V]? {
match node {
None => None
Some(node) => {
let left = copy_tree(node.left)
let right = copy_tree(node.right)
let new_node = new_node(node.value, left~, right~, height=node.height)
Some(new_node)
}
}
}
///|
#owned(value, left, right)
fn[V] new_node(
value : V,
left? : Node[V]? = None,
right? : Node[V]? = None,
height? : Int = 1,
) -> Node[V] {
{ value, left, right, height, }
}
///|
#owned(value, left, right)
fn[V] new_node_update_height(
value : V,
left~ : Node[V]?,
right~ : Node[V]?,
) -> Node[V] {
{ value, left, right, height: height(left).max(height(right)) + 1, }
}
// Manipulations
///|
/// Adds a value to the set. If the value already exists, it is replaced.
#owned(value)
pub fn[V : Compare] SortedSet::add(self : SortedSet[V], value : V) -> Unit {
let (new_root, inserted) = add_node(self.root, value)
if self.root != new_root {
self.root = new_root
}
if inserted {
self.size += 1
}
}
///|
/// Removes a value from the set. Does nothing if the value is not present.
pub fn[V : Compare] SortedSet::remove(self : SortedSet[V], value : V) -> Unit {
if self.root is Some(old_root) {
let (new_root, deleted) = delete_node(old_root, value)
if self.root != new_root {
self.root = new_root
}
if deleted {
self.size -= 1
}
}
}
// Set operations
// Including union, intersection, difference, subset, disjoint, contains.
// Note that these functions return a new set that doesn't share memory with
// the original set, and the original sets are not modified.
///|
/// Returns `true` if the set contains the given value.
pub fn[V : Compare] SortedSet::contains(self : SortedSet[V], value : V) -> Bool {
for root = self.root, value = value {
match (root, value) {
(None, _) => break false
(Some(node), value) => {
let compare_result = value.compare(node.value)
if compare_result == 0 {
break true
} else if compare_result < 0 {
continue node.left, value
} else {
continue node.right, value
}
}
}
}
}
///|
/// Returns the stored value that compares equal to `value`, if any.
fn[V : Compare] lookup(root : Node[V]?, value : V) -> V? {
for node = root {
match node {
None => break None
Some(n) => {
let compare_result = value.compare(n.value)
if compare_result == 0 {
break Some(n.value)
} else if compare_result < 0 {
continue n.left
} else {
continue n.right
}
}
}
}
}
///|
/// Returns a new set containing all elements from both sets.
pub fn[V : Compare] SortedSet::union(
self : SortedSet[V],
src : SortedSet[V],
) -> SortedSet[V] {
// An element common to both sets is dropped exactly once, at the found
// pivot of `split_member`; counting those drops gives the result size
// arithmetically instead of re-traversing the merged tree.
let mut dups = 0
fn aux(a : Node[V]?, b : Node[V]?) -> Node[V]? {
match (a, b) {
(Some(_), None) => a
(None, Some(_)) => b
(Some({ value: va, left: la, right: ra, .. }), Some(_)) => {
let { left: l, found, right: r, } = split_member(b, va)
if found {
dups += 1
}
Some(join(aux(la, l), va, aux(ra, r)))
}
(None, None) => None
}
}
match (self.root, src.root) {
(Some(_), Some(_)) => {
let t = aux(copy_tree(self.root), copy_tree(src.root))
{ root: t, size: self.size + src.size - dups, }
}
(Some(_), None) => { root: copy_tree(self.root), size: self.size, }
(None, Some(_)) => { root: copy_tree(src.root), size: src.size, }
(None, None) => new_sorted_set()
}
}
///|
// `#valtype` keeps the split result stack-allocated on the native target:
// `split_member` builds and returns one per visited node on every
// set-operation pivot path.
#valtype
priv struct SplitResult[V] {
left : Node[V]?
found : Bool
right : Node[V]?
}
///|
/// Splits a tree by a value into the elements less than it, a flag for
/// whether it was present, and the elements greater than it.
fn[V : Compare] split_member(root : Node[V]?, value : V) -> SplitResult[V] {
match root {
None => { left: None, found: false, right: None, }
Some(node) => {
let comp = value.compare(node.value)
if comp == 0 {
{ left: node.left, found: true, right: node.right, }
} else if comp < 0 {
let { left, found, right, } = split_member(node.left, value)
{ left, found, right: Some(join(right, node.value, node.right)), }
} else {
let { left, found, right, } = split_member(node.right, value)
{ left: Some(join(node.left, node.value, left)), found, right, }
}
}
}
}
///|
/// Concatenates two trees where all elements in left < all elements in right.
fn[V] concat(left : Node[V]?, right : Node[V]?) -> Node[V]? {
match (left, right) {
(None, _) => right
(_, None) => left
(Some(_), Some(r)) => {
let (min_val, rest) = remove_min(r)
Some(join(left, min_val, rest))
}
}
}
///|
/// Removes the minimum value from a tree, returning it and the remaining tree.
fn[V] remove_min(node : Node[V]) -> (V, Node[V]?) {
match node.left {
None => (node.value, node.right)
Some(left) => {
let (min_val, new_left) = remove_min(left)
(min_val, Some(join(new_left, node.value, node.right)))
}
}
}
///|
#owned(left, value, right)
fn[V] join(left : Node[V]?, value : V, right : Node[V]?) -> Node[V] {
let (hl, hr) = (height(left), height(right))
if hl > hr + 1 {
join_right(left, value, right)
} else if hr > hl + 1 {
join_left(left, value, right)
} else {
new_node_update_height(value, left~, right~)
}
}
///|
#owned(l, v)
fn[V] join_left(l : Node[V]?, v : V, r : Node[V]?) -> Node[V] {
let { value: rv, left: rl, right: rr, .. } = r.unwrap()
let node = if height(rl) <= height(l) + 1 {
let new_l = new_node_update_height(left=l, v, right=rl)
if height(Some(new_l)) <= height(rr) + 1 {
new_node_update_height(left=Some(new_l), rv, right=rr)
} else {
let new_l = rotate_l(new_l)
let new = new_node_update_height(left=Some(new_l), rv, right=rr)
rotate_r(new)
}
} else {
let new_l = join_left(l, v, rl)
let new = new_node_update_height(left=Some(new_l), rv, right=rr)
if height(Some(new_l)) <= height(rr) + 1 {
new
} else {
rotate_r(new)
}
}
node.update_height()
node
}
///|
#owned(v, r)
fn[V] join_right(l : Node[V]?, v : V, r : Node[V]?) -> Node[V] {
let { value: lv, left: ll, right: lr, .. } = l.unwrap()
let node = if height(lr) <= height(r) + 1 {
let new_r = new_node_update_height(left=lr, v, right=r)
if height(Some(new_r)) <= height(ll) + 1 {
new_node_update_height(left=ll, lv, right=Some(new_r))
} else {
let new_r = rotate_r(new_r)
let new = new_node_update_height(left=ll, lv, right=Some(new_r))
rotate_l(new)
}
} else {
let new_r = join_right(lr, v, r)
let new = new_node_update_height(left=ll, lv, right=Some(new_r))
if height(Some(new_r)) <= height(ll) + 1 {
new
} else {
rotate_l(new)
}
}
node.update_height()
node
}
///|
/// Returns a new set containing elements in `self` that are not in `src`.
#alias(diff, deprecated)
pub fn[V : Compare] SortedSet::difference(
self : SortedSet[V],
src : SortedSet[V],
) -> SortedSet[V] {
match (self.root, src.root) {
(None, _) => new_sorted_set()
(_, None) => { root: copy_tree(self.root), size: self.size, }
(Some(_), Some(_)) => {
// The split-based merge below copies both trees, a Theta(n + m) floor
// that dwarfs the O(n log m) probe loop when `self` is far smaller
// than `src` (the result then also has at most `self.size` elements).
// The 1/16 cutoff keeps the probe loop ahead of the merge even in its
// worst case, where every probed element is inserted into the result.
if self.size < src.size / 16 {
let ret = new_sorted_set()
self.each(x => if !src.contains(x) { ret.add(x) })
return ret
}
// `found_count` ends up as the number of elements shared by both sets:
// `aux` takes every node of `a` as a split pivot, except in subtrees
// whose matching `b` fragment is empty and therefore shares no elements.
let mut found_count = 0
fn aux(a : Node[V]?, b : Node[V]?) -> Node[V]? {
match (a, b) {
(None, _) => None
(_, None) => a
(Some({ value: va, left: la, right: ra, .. }), _) => {
let { left: lb, found, right: rb, } = split_member(b, va)
if found {
found_count += 1
concat(aux(la, lb), aux(ra, rb))
} else {
Some(join(aux(la, lb), va, aux(ra, rb)))
}
}
}
}
let t = aux(copy_tree(self.root), copy_tree(src.root))
{ root: t, size: self.size - found_count, }
}
}
}
///|
/// 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:
///
/// ```mbt check
/// 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=(
/// #|
/// ),
/// )
/// }
/// ```
pub fn[V : Compare] SortedSet::symmetric_difference(
self : SortedSet[V],
other : SortedSet[V],
) -> SortedSet[V] {
// See `difference` for why `found_count` counts each shared element once.
let mut found_count = 0
fn aux(a : Node[V]?, b : Node[V]?) -> Node[V]? {
match (a, b) {
(None, _) => b
(_, None) => a
(Some({ value: va, left: la, right: ra, .. }), _) => {
let { left: lb, found, right: rb, } = split_member(b, va)
if found {
found_count += 1
concat(aux(la, lb), aux(ra, rb))
} else {
Some(join(aux(la, lb), va, aux(ra, rb)))
}
}
}
}
let t = aux(copy_tree(self.root), copy_tree(other.root))
{ root: t, size: self.size + other.size - 2 * found_count, }
}
///|
/// Returns a new set containing only elements present in both sets.
#alias(intersect, deprecated)
pub fn[V : Compare] SortedSet::intersection(
self : SortedSet[V],
src : SortedSet[V],
) -> SortedSet[V] {
match (self.root, src.root) {
(None, _) | (_, None) => new_sorted_set()
(Some(_), Some(_)) => {
// The intersection's key set is symmetric and fits in the smaller
// side, so when one side is far smaller, probing with it is
// O(min log max) and beats the Theta(n + m) tree copies of the
// split-based merge (see the analogous cutoff in `difference`).
// The result must still carry `self`'s stored representative of each
// shared value (`add` replaces compare-equal values, and the split
// path below emits `va` from `self`), so when the probing side is
// `src`, each match inserts the value looked up in `self`.
if self.size < src.size / 16 {
let ret = new_sorted_set()
self.each(x => if src.contains(x) { ret.add(x) })
return ret
}
if src.size < self.size / 16 {
let ret = new_sorted_set()
src.each(x => if lookup(self.root, x) is Some(v) { ret.add(v) })
return ret
}
// See `difference` for why `found_count` counts each shared element
// once.
let mut found_count = 0
fn aux(a : Node[V]?, b : Node[V]?) -> Node[V]? {
match (a, b) {
(None, _) | (_, None) => None
(Some({ value: va, left: la, right: ra, .. }), _) => {
let { left: lb, found, right: rb, } = split_member(b, va)
if found {
found_count += 1
Some(join(aux(la, lb), va, aux(ra, rb)))
} else {
concat(aux(la, lb), aux(ra, rb))
}
}
}
}
let t = aux(copy_tree(self.root), copy_tree(src.root))
{ root: t, size: found_count, }
}
}
}
///|
/// Returns `true` if every element of `self` is also in `src`.
pub fn[V : Compare] SortedSet::subset(
self : SortedSet[V],
src : SortedSet[V],
) -> Bool {
self.iter().all(x => src.contains(x))
}
///|
/// Returns `true` if the two sets have no elements in common.
pub fn[V : Compare] SortedSet::disjoint(
self : SortedSet[V],
src : SortedSet[V],
) -> Bool {
self.iter().all(x => !src.contains(x))
}
// General collection operations
///|
pub impl[V : Eq] Eq for SortedSet[V] with fn equal(self, other) {
guard self.size == other.size else { return false }
let iter = self.iter()
let iter1 = other.iter()
while iter.next() is Some(a) && iter1.next() is Some(b) {
guard a == b else { break false }
} nobreak {
true
}
}
///|
/// Returns `true` if the set contains no elements.
pub fn[V] SortedSet::is_empty(self : SortedSet[V]) -> Bool {
self.root is None
}
///|
/// Returns the number of elements in the set.
#alias(size, deprecated)
pub fn[V] SortedSet::length(self : SortedSet[V]) -> Int {
self.size
}
///|
/// Iterates over all elements in the set in ascending order.
pub fn[V] SortedSet::each(
self : SortedSet[V],
f : (V) -> Unit raise?,
) -> Unit raise? {
fn dfs(root : Node[V]?) -> Unit raise? {
if root is Some(root) {
dfs(root.left)
f(root.value)
dfs(root.right)
}
}
dfs(self.root)
}
///|
/// Iterates over all elements in the set with their index, in ascending order.
pub fn[V] SortedSet::eachi(
self : SortedSet[V],
f : (Int, V) -> Unit raise?,
) -> Unit raise? {
let mut i = 0
self.each(v => {
f(i, v)
i += 1
})
}
///|
/// Converts the set to an array.
pub fn[V] SortedSet::to_array(self : SortedSet[V]) -> Array[V] {
if self.size == 0 {
return []
}
let arr = Array::unsafe_make_uninit(self.size)
let mut n = 0
fn dfs(root : Node[V]?) -> Unit {
if root is Some(root) {
dfs(root.left)
let v = root.value
arr.unsafe_set(n, v)
n += 1
dfs(root.right)
}
}
dfs(self.root)
arr
}
///|
/// Returns an iterator over the elements in ascending order.
#alias(iterator, deprecated)
pub fn[V] SortedSet::iter(self : SortedSet[V]) -> Iter[V] {
let mut curr_node = self.root
let parents = []
Iter::new(
fn() {
for x = curr_node {
match x {
Some({ left: None, value, right, height: _, }) => {
curr_node = right
break Some(value)
}
Some({ left, value, right, height: _, }) => {
parents.push((value, right))
continue left
}
None if parents.pop() is Some((value, right)) => {
curr_node = right
break Some(value)
}
None => break None
}
}
},
size_hint=self.size,
)
}
///|
/// Creates a set from an iterator of values.
#as_free_fn
#alias(from_iterator, deprecated)
#as_free_fn(from_iterator, deprecated)
pub fn[V : Compare] SortedSet::from_iter(iter : Iter[V]) -> SortedSet[V] {
let s = new_sorted_set()
while iter.next() is Some(e) {
s.add(e)
}
s
}
///|
/// Outputs the set's string representation to a logger.
#deprecated("Use @debug.Debug instead of Show for debugging purposes. See https://github.com/moonbitlang/core/blob/main/debug/README.mbt.md")
pub impl[V : Show] Show for SortedSet[V]
///|
/// Outputs the set's string representation to a logger.
pub impl[V : Show] Show for SortedSet[V] with fn output(self, logger) {
logger.write_iter(self.iter(), prefix="@sorted_set.from_array([", suffix="])")
}
///|
#deprecated("Use @debug.Debug instead of Show for debugging purposes. See https://github.com/moonbitlang/core/blob/main/debug/README.mbt.md")
impl[T : Show] Show for Node[T]
///|
impl[T : Show] Show for Node[T] with fn output(self, logger) {
fn count(root : Node[T]?) -> Int {
match root {
None => 0
Some(root) => count(root.left) + count(root.right) + 1
}
}
let x = { root: Some(self), size: count(Some(self)), }
logger.write_iter(x.iter())
}
///|
/// Returns an iterator over elements in the range `[low, high]` (inclusive).
pub fn[V : Compare] SortedSet::range(
self : SortedSet[V],
low : V,
high : V,
) -> Iter[V] {
let mut curr_node = self.root
let parents = []
let iter = Iter::new(() => {
for x = curr_node {
match x {
Some({ value, left, right, height: _, }) => {
let cmp_key_low = value.compare(low)
let cmp_key_high = value.compare(high)
if cmp_key_low < 0 {
// `key < low`, the left subtree and the value itself
// should not be visited
continue right
} else if cmp_key_high > 0 {
// `key > high`, the right subtree and the value itself
// should not be visited
continue left
// `low <= value <= high`,
// the value itself falls in the range,
// and both the left and right sub tree need to be visited
} else if left is None {
curr_node = right
break Some(value)
} else {
parents.push((value, right))
continue left
}
}
None if parents.pop() is Some((value, right)) => {
curr_node = right
break Some(value)
}
None => break None
}
}
})
iter.iter()
}
// AVL tree operations
///|
fn[V] replace_root_with_min(root : Node[V], node : Node[V]) -> Node[V]? {
let (l, r) = (node.left, node.right)
match l {
None => {
root.value = node.value
r
}
Some(ln) => {
node.left = replace_root_with_min(root, ln)
Some(balance(node))
}
}
}
///|
fn[V] Node::update_height(self : Node[V]) -> Unit {
self.height = 1 + height(self.left).max(height(self.right))
}
///|
fn[V] height_ge(x1 : Node[V]?, x2 : Node[V]?) -> Bool {
match (x1, x2) {
(
Some({ height: h1, .. })
| (None with h1 = 0),
Some({ height: h2, .. })
| (None with h2 = 0),
) => h1 >= h2
}
}
///|
#owned(root)
fn[V] balance(root : Node[V]) -> Node[V] {
let (l, r) = (root.left, root.right)
let (hl, hr) = (height(l), height(r))
let new_root = if hl > hr + 1 {
let { left: ll, right: lr, .. } = l.unwrap()
if height_ge(ll, lr) {
rotate_r(root)
} else {
rotate_lr(root)
}
} else if hr > hl + 1 {
let { left: rl, right: rr, .. } = r.unwrap()
if height_ge(rr, rl) {
rotate_l(root)
} else {
rotate_rl(root)
}
} else {
root
}
new_root.update_height()
new_root
}
///|
#owned(n)
fn[V] rotate_l(n : Node[V]) -> Node[V] {
let r = n.right.unwrap()
n.right = r.left
// Update n's height before storing it: the store consumes the owned `n`
// reference, and touching `n` afterwards would force an extra
// incref/decref pair to keep it alive across the store.
n.update_height()
r.left = Some(n)
r.update_height()
r
}
///|
#owned(n)
fn[V] rotate_r(n : Node[V]) -> Node[V] {
let l = n.left.unwrap()
n.left = l.right
// See rotate_l: keep the consuming store as the last use of `n`.
n.update_height()
l.right = Some(n)
l.update_height()
l
}
///|
#owned(n)
fn[V] rotate_lr(n : Node[V]) -> Node[V] {
let l = n.left.unwrap()
let v = rotate_l(l)
n.left = Some(v)
rotate_r(n)
}
///|
#owned(n)
fn[V] rotate_rl(n : Node[V]) -> Node[V] {
let r = n.right.unwrap()
let v = rotate_r(r)
n.right = Some(v)
rotate_l(n)
}
///|
#owned(value)
fn[V : Compare] add_node(root : Node[V]?, value : V) -> (Node[V]?, Bool) {
match root {
None => (Some(new_node(value)), true)
Some(n) => {
let comp = value.compare(n.value)
if comp == 0 {
n.value = value
(Some(n), false)
} else {
let (l, r) = (n.left, n.right)
if comp < 0 {
let (nl, inserted) = add_node(l, value)
n.left = nl
(Some(balance(n)), inserted)
} else {
let (nr, inserted) = add_node(r, value)
n.right = nr
(Some(balance(n)), inserted)
}
}
}
}
}
///|
fn[V : Compare] delete_node(root : Node[V], value : V) -> (Node[V]?, Bool) {
let comp = value.compare(root.value)
if comp == 0 {
let (l, r) = (root.left, root.right)
let n = match (l, r) {
(Some(_), Some(nr)) => {
root.right = replace_root_with_min(root, nr)
Some(balance(root))
}
(None, Some(_)) => r
(Some(_), None) | (None, None) => l
}
(n, true)
} else if comp < 0 {
match root.left {
None => (Some(root), false)
Some(l) => {
let (nl, deleted) = delete_node(l, value)
root.left = nl
(Some(balance(root)), deleted)
}
}
} else {
match root.right {
None => (Some(root), false)
Some(r) => {
let (nr, deleted) = delete_node(r, value)
root.right = nr
(Some(balance(root)), deleted)
}
}
}
}
///|
test "copy" {
let set = from_array([1, 2, 3, 4, 5])
let copied_set = set.copy()
@debug.debug_inspect(
copied_set,
content=(
#|
),
)
inspect(set.debug_tree() == copied_set.debug_tree(), content="true")
let set : SortedSet[Int] = from_array([])
let copied_set = set.copy()
@debug.debug_inspect(
copied_set,
content=(
#|
),
)
inspect(set.debug_tree() == copied_set.debug_tree(), content="true")
}
///|
test "union" {
// Test 1: Union of two sets with no common elements
let set1 = from_array([1, 2, 3])
let set2 = from_array([4, 5, 6])
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(
set3.debug_tree(),
content="([3]3,([2]2,([1]1,_,_),_),([2]5,([1]4,_,_),([1]6,_,_)))",
)
// Test 2: Union of two sets with some common elements
let set1 = from_array([1, 2, 3])
let set2 = from_array([2, 3, 4])
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(set3.debug_tree(), content="([3]2,([1]1,_,_),([2]3,_,([1]4,_,_)))")
// Test 3: Union of two sets where one is a subset of the other
let set1 = from_array([1, 2, 3])
let set2 = from_array([2, 3])
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(set3.debug_tree(), content="([2]2,([1]1,_,_),([1]3,_,_))")
// Test 4: Union of two empty sets
let set1 : SortedSet[Int] = new_sorted_set()
let set2 = new_sorted_set()
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(set3.debug_tree(), content="_")
// Test 5: Union of an empty set with a non-empty set
let set1 = from_array([1, 2, 3])
let set2 = from_array([])
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(set3.debug_tree(), content="([2]2,([1]1,_,_),([1]3,_,_))")
let set1 = from_array([])
let set2 = from_array([1, 2, 3])
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(set3.debug_tree(), content="([2]2,([1]1,_,_),([1]3,_,_))")
// Test 6: Union of two large sets with no common elements
let set1 = from_array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
let set2 = from_array([11, 12, 13, 14, 15, 16, 17, 18, 19, 20])
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(
set3.debug_tree(),
content="([5]14,([4]8,([3]4,([2]2,([1]1,_,_),([1]3,_,_)),([2]6,([1]5,_,_),([1]7,_,_))),([3]12,([2]10,([1]9,_,_),([1]11,_,_)),([1]13,_,_))),([3]18,([2]16,([1]15,_,_),([1]17,_,_)),([2]19,_,([1]20,_,_))))",
)
// Test 7: Union of two large sets with some common elements
let set1 = from_array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
let set2 = from_array([6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(
set3.debug_tree(),
content="([5]11,([4]4,([2]2,([1]1,_,_),([1]3,_,_)),([3]8,([2]6,([1]5,_,_),([1]7,_,_)),([2]9,_,([1]10,_,_)))),([3]13,([1]12,_,_),([2]14,_,([1]15,_,_))))",
)
// Test 8: Union of two large sets where one is a subset of the other
let set1 = from_array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
let set2 = from_array([6, 7, 8, 9, 10])
let set3 = set1.union(set2)
@debug.debug_inspect(
set3,
content=(
#|
),
)
inspect(
set3.debug_tree(),
content="([4]4,([2]2,([1]1,_,_),([1]3,_,_)),([3]8,([2]6,([1]5,_,_),([1]7,_,_)),([2]9,_,([1]10,_,_))))",
)
}
///|
#warnings("-deprecated")
test "split_member" {
let { left: l, found, right: r, } = split_member(
from_array([7, 2, 9, 4, 5, 6, 3, 8, 1]).root,
5,
)
inspect(found, content="true")
inspect(l, content="Some([1, 2, 3, 4])")
inspect(r, content="Some([6, 7, 8, 9])")
let { left: l, found, right: r, } = split_member(
from_array([7, 2, 9, 4, 5, 6, 3, 8, 1]).root,
0,
)
inspect(found, content="false")
inspect(l, content="None")
inspect(r, content="Some([1, 2, 3, 4, 5, 6, 7, 8, 9])")
let { left: l, found, right: r, } = split_member(
from_array([7, 2, 9, 4, 5, 6, 3, 8, 1]).root,
10,
)
inspect(found, content="false")
inspect(l, content="Some([1, 2, 3, 4, 5, 6, 7, 8, 9])")
inspect(r, content="None")
let { left: l, found, right: r, } = split_member(
from_array([7, 2, 9, 4, 5, 6, 3, 8, 1]).root,
4,
)
inspect(found, content="true")
inspect(l, content="Some([1, 2, 3])")
inspect(r, content="Some([5, 6, 7, 8, 9])")
let { left: l, found, right: r, } = split_member(from_array([]).root, 7)
inspect(found, content="false")
inspect(l, content="None")
inspect(r, content="None")
}
///|
test "join" {
fn join_to_array(
l : SortedSet[Int],
value : Int,
r : SortedSet[Int],
) -> Array[Int] {
let root = join(l.root, value, r.root)
({ root: Some(root), size: l.size + r.size + 1, } : SortedSet[Int]).to_array()
}
let l = from_array([13, 8, 17, 1, 11, 15, 25, 6])
let r = from_array([27, 28, 40, 35, 33])
@debug.debug_inspect(
join_to_array(l, 26, r),
content=(
#|[1, 6, 8, 11, 13, 15, 17, 25, 26, 27, 28, 33, 35, 40]
),
)
let l = from_array([3, 2, 5, 1, 4])
let r = from_array([7])
@debug.debug_inspect(
join_to_array(l, 6, r),
content=(
#|[1, 2, 3, 4, 5, 6, 7]
),
)
let l = from_array([3, 2, 5, 1, 4])
let r = from_array([])
@debug.debug_inspect(
join_to_array(l, 6, r),
content=(
#|[1, 2, 3, 4, 5, 6]
),
)
let l = from_array([])
let r = from_array([])
@debug.debug_inspect(
join_to_array(l, 6, r),
content=(
#|[6]
),
)
let l = from_array([])
let r = from_array([7, 8, 9, 10, 11, 12])
@debug.debug_inspect(
join_to_array(l, 6, r),
content=(
#|[6, 7, 8, 9, 10, 11, 12]
),
)
}
///|
test "add to empty set" {
let set = new_sorted_set()
set.add(1)
@test.assert_eq(set.contains(1), true)
inspect(set.debug_tree(), content="([1]1,_,_)")
}
///|
test "add to non-empty set" {
let set = new_sorted_set()
set.add(1)
set.add(2)
@test.assert_eq(set.contains(1), true)
@test.assert_eq(set.contains(2), true)
inspect(set.debug_tree(), content="([2]1,_,([1]2,_,_))")
}
///|
test "add duplicate value" {
let set = new_sorted_set()
set.add(1)
set.add(1)
@test.assert_eq(set.contains(1), true)
@test.assert_eq(set.length(), 1)
inspect(set.debug_tree(), content="([1]1,_,_)")
}
///|
test "add multiple values" {
let set = new_sorted_set()
set.add(1)
set.add(2)
set.add(3)
@test.assert_eq(set.contains(1), true)
@test.assert_eq(set.contains(2), true)
@test.assert_eq(set.contains(3), true)
@test.assert_eq(set.length(), 3)
inspect(set.debug_tree(), content="([2]2,([1]1,_,_),([1]3,_,_))")
}
///|
test "add_and_remove" {
let set = from_array([7, 2, 9, 4, 5, 6, 3, 8, 1])
set.remove(8)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]5,([3]3,([2]2,([1]1,_,_),_),([1]4,_,_)),([2]7,([1]6,_,_),([1]9,_,_)))",
)
let set = from_array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
// Test 1: Remove elements
set.remove(1)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]4,([2]2,_,([1]3,_,_)),([3]8,([2]6,([1]5,_,_),([1]7,_,_)),([2]9,_,([1]10,_,_))))",
)
set.remove(5)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]4,([2]2,_,([1]3,_,_)),([3]8,([2]6,_,([1]7,_,_)),([2]9,_,([1]10,_,_))))",
)
set.remove(10)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]4,([2]2,_,([1]3,_,_)),([3]8,([2]6,_,([1]7,_,_)),([1]9,_,_)))",
)
set.remove(4)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([3]6,([2]2,_,([1]3,_,_)),([2]8,([1]7,_,_),([1]9,_,_)))",
)
// Test 2: Add elements
set.add(1)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([3]6,([2]2,([1]1,_,_),([1]3,_,_)),([2]8,([1]7,_,_),([1]9,_,_)))",
)
set.add(5)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]6,([3]2,([1]1,_,_),([2]3,_,([1]5,_,_))),([2]8,([1]7,_,_),([1]9,_,_)))",
)
set.add(10)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]6,([3]2,([1]1,_,_),([2]3,_,([1]5,_,_))),([3]8,([1]7,_,_),([2]9,_,([1]10,_,_))))",
)
set.add(4)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]6,([3]2,([1]1,_,_),([2]4,([1]3,_,_),([1]5,_,_))),([3]8,([1]7,_,_),([2]9,_,([1]10,_,_))))",
)
// Test 3: Add and remove the same element
set.add(11)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]6,([3]2,([1]1,_,_),([2]4,([1]3,_,_),([1]5,_,_))),([3]8,([1]7,_,_),([2]10,([1]9,_,_),([1]11,_,_))))",
)
set.remove(11)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]6,([3]2,([1]1,_,_),([2]4,([1]3,_,_),([1]5,_,_))),([3]8,([1]7,_,_),([2]10,([1]9,_,_),_)))",
)
// Test 4: Remove an element that doesn't exist
set.remove(12)
@debug.debug_inspect(
set,
content=(
#|
),
)
// Test 5: Add an element that already exists
set.add(10)
@debug.debug_inspect(
set,
content=(
#|
),
)
// Test 6: Remove all elements
set.remove(1)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]6,([3]4,([2]2,_,([1]3,_,_)),([1]5,_,_)),([3]8,([1]7,_,_),([2]10,([1]9,_,_),_)))",
)
set.remove(2)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]6,([2]4,([1]3,_,_),([1]5,_,_)),([3]8,([1]7,_,_),([2]10,([1]9,_,_),_)))",
)
set.remove(3)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([4]6,([2]4,_,([1]5,_,_)),([3]8,([1]7,_,_),([2]10,([1]9,_,_),_)))",
)
set.remove(4)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([3]8,([2]6,([1]5,_,_),([1]7,_,_)),([2]10,([1]9,_,_),_))",
)
set.remove(5)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([3]8,([2]6,_,([1]7,_,_)),([2]10,([1]9,_,_),_))",
)
set.remove(6)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="([3]8,([1]7,_,_),([2]10,([1]9,_,_),_))")
set.remove(7)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="([2]9,([1]8,_,_),([1]10,_,_))")
set.remove(8)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="([2]9,_,([1]10,_,_))")
set.remove(9)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="([1]10,_,_)")
set.remove(10)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="_")
let set = from_array([7, 2, 9, 4, 5, 6, 3, 1])
set.remove(3)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([3]5,([2]2,([1]1,_,_),([1]4,_,_)),([2]7,([1]6,_,_),([1]9,_,_)))",
)
set.remove(2)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([3]5,([2]4,([1]1,_,_),_),([2]7,([1]6,_,_),([1]9,_,_)))",
)
set.remove(5)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(
set.debug_tree(),
content="([3]6,([2]4,([1]1,_,_),_),([2]7,_,([1]9,_,_)))",
)
set.remove(9)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="([3]6,([2]4,([1]1,_,_),_),([1]7,_,_))")
set.remove(1)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="([2]6,([1]4,_,_),([1]7,_,_))")
set.remove(7)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="([2]6,([1]4,_,_),_)")
set.remove(4)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="([1]6,_,_)")
set.remove(6)
@debug.debug_inspect(
set,
content=(
#|
),
)
inspect(set.debug_tree(), content="_")
}
///|
pub impl[K] Default for SortedSet[K] with fn default() {
new_sorted_set()
}