🥮 mooncakes.io

    moonbitstack/moonstl/algo does not have a README file

    Combinations

    source
    pub struct Combinations[T] {
      pool : Array[T]
      indices : Array[Int]
      started : Bool
      done : Bool
    }

    The k-element subsets, in lexicographic order of positions.

    test {
      let combinations : @algo.Combinations[Int32] = @algo.Combinations::new(
        [1, 2, 3, 4],
        k=2,
      )
      @test.assert_eq(combinations.iter().to_array(), [
        [1, 2],
        [1, 3],
        [1, 4],
        [2, 3],
        [2, 4],
        [3, 4],
      ])
    }

    Combinations::iter

    source
    fn[T] Combinations::iter(self : Combinations[T]) -> Iter[Array[T]]

    Combinations::new

    source
    fn[T] Combinations::new(pool : ArrayView[T], k~ : Int) -> Combinations[T]

    Combinations::next

    source
    fn[T] Combinations::next(self : Combinations[T]) -> Array[T]?

    CombinationsWithReplacement

    source
    pub struct CombinationsWithReplacement[T] {
      pool : Array[T]
      indices : Array[Int]
      started : Bool
      done : Bool
    }

    The k-element selections that may repeat an element, in lexicographic order of positions.

    test {
      let with_repeats : @algo.CombinationsWithReplacement[Int32] = @algo.CombinationsWithReplacement::new(
        [1, 2],
        k=2,
      )
      @test.assert_eq(with_repeats.iter().to_array(), [[1, 1], [1, 2], [2, 2]])
    }

    CombinationsWithReplacement::iter

    source

    CombinationsWithReplacement::new

    source

    CombinationsWithReplacement::next

    source

    GrayCode

    source
    pub struct GrayCode {
      bits : Int
      step : Int
      done : Bool
    }

    The reflected binary code over bits positions: consecutive words differ in exactly one bit, and the first is all zeroes.

    test {
      let code : @algo.GrayCode = @algo.GrayCode::new(2)
      @test.assert_eq(code.iter().take(4).to_array(), [
        [false, false],
        [false, true],
        [true, true],
        [true, false],
      ])
    }

    GrayCode::iter

    source
    fn GrayCode::iter(self : GrayCode) -> Iter[Array[Bool]]

    GrayCode::new

    source
    fn GrayCode::new(bits : Int) -> GrayCode

    GrayCode::next

    source
    fn GrayCode::next(self : GrayCode) -> Array[Bool]?

    JoinEntry

    source
    pub(all) enum JoinEntry[A, B] {
      Left(A)
      Right(B)
      Both(A, B)
    } derive(Eq, 
    Debug    )

    The result of stepping two ordered runs side by side: an element of the first run only, of the second only, or a pair of equal elements.

    JoinEntry::equal

    source
    fn[A : Eq, B : Eq] JoinEntry::equal(JoinEntry[A, B], JoinEntry[A, B]) -> Bool

    JoinEntry::not_equal

    source
    fn[A : Eq, B : Eq] JoinEntry::not_equal(x : JoinEntry[A, B], y : JoinEntry[A, B]) -> Bool

    JoinEntry::to_repr

    source

    Permutations

    source
    pub struct Permutations[T] {
      pool : Array[T]
      indices : Array[Int]
      cycles : Array[Int]
      size : Int
      started : Bool
      done : Bool
    }

    The k-permutations of a run, in the order Python's itertools.permutations produces them: the positions advance like an odometer, so the first element changes slowest.

    test {
      let permutations : @algo.Permutations[Int32] = @algo.Permutations::new(
        [1, 2, 3],
        length=2,
      )
      @test.assert_eq(permutations.iter().to_array(), [
        [1, 2],
        [1, 3],
        [2, 1],
        [2, 3],
        [3, 1],
        [3, 2],
      ])
    }

    Permutations::iter

    source
    fn[T] Permutations::iter(self : Permutations[T]) -> Iter[Array[T]]

    Permutations::new

    source
    fn[T] Permutations::new(pool : ArrayView[T], length? : Int) -> Permutations[T]

    length shorter than the pool gives k-permutations; leaving it out gives every arrangement of the whole pool.

    Permutations::next

    source
    fn[T] Permutations::next(self : Permutations[T]) -> Array[T]?

    The next arrangement, or None when they are exhausted.

    Position

    source
    pub(all) enum Position {
      Only
      First
      Middle
      Last
    } derive(Eq, 
    Debug    )

    Where an element sits in a sequence that is being consumed.

    Position::equal

    source
    fn Position::equal(Position, Position) -> Bool

    Position::not_equal

    source
    fn Position::not_equal(x : Position, y : Position) -> Bool

    Position::to_repr

    source

    Powerset

    source
    pub struct Powerset[T] {
      inner : Combinations[T]
      pool : Array[T]
      size : Int
    }

    Every subset, shortest first: the order chain.from_iterable(combinations(s, r) for r in range(len(s) + 1)) gives.

    test {
      let powerset : @algo.Powerset[Int32] = @algo.Powerset::new([1, 2])
      @test.assert_eq(powerset.iter().to_array(), [[], [1], [2], [1, 2]])
    }

    Powerset::iter

    source
    fn[T] Powerset::iter(self : Powerset[T]) -> Iter[Array[T]]

    Powerset::new

    source
    fn[T] Powerset::new(pool : ArrayView[T]) -> Powerset[T]

    Powerset::next

    source
    fn[T] Powerset::next(self : Powerset[T]) -> Array[T]?

    Product

    source
    pub struct Product[T] {
      pools : Array[Array[T]]
      digits : Array[Int]
      started : Bool
      done : Bool
    }

    The cartesian product of several runs, rightmost pool varying fastest, the order itertools.product uses.

    test {
      let pools : Array[ArrayView[Int32]] = [[1, 2][:], [3, 4][:]]
      let product : @algo.Product[Int32] = @algo.Product::new(pools)
      @test.assert_eq(product.iter().to_array(), [[1, 3], [1, 4], [2, 3], [2, 4]])
    }

    Product::iter

    source
    fn[T] Product::iter(self : Product[T]) -> Iter[Array[T]]

    Product::new

    source
    fn[T] Product::new(pools : ArrayView[ArrayView[T]]) -> Product[T]

    Product::next

    source
    fn[T] Product::next(self : Product[T]) -> Array[T]?

    adjacent_difference

    source
    fn[T] adjacent_difference(a : ArrayView[T], op~ : (T, T) -> T) -> Array[T]

    The first difference of adjacent elements: element 0 is kept, element i is op(a[i - 1], a[i]). The empty run yields an empty array.

    all_equal

    source
    fn[T : Eq] all_equal(a : ArrayView[T]) -> Bool

    Whether every element of the run is equal to every other. Empty and single-element runs are equal by vacuity.

    all_unique

    source
    fn[T : Hash + Eq] all_unique(a : ArrayView[T]) -> Bool

    Whether all elements are distinct, using a hash set of the values seen.

    apply_permutation_in_place

    source
    fn[T] apply_permutation_in_place(a : Array[T], order : ArrayView[Int]) -> Unit

    Rearranges the run so that the element that was at position i moves to position order[i].

    order must be a permutation of 0..a.length(). When it is not, or when its length differs from the run's, the run is left unchanged. The rearrangement uses cycle following, so it needs no second copy of the run.

    at_most_one

    source
    fn[T] at_most_one(a : ArrayView[T], pred : (T) -> Bool) -> Bool

    Whether at most one element satisfies pred. Stops at the second match.

    bisect_left

    source
    fn[T : Compare + Eq] bisect_left(a : ArrayView[T], value : T) -> Int

    The first index at which value could be inserted while keeping a ascending: every element before the result is smaller than value.

    a must already be sorted ascending. The result is in 0..=a.length().

    bisect_left_by

    source
    fn[T] bisect_left_by(a : ArrayView[T], value : T, cmp~ : (T, T) -> Int) -> Int

    bisect_left with an explicit comparator, for an ordering the Compare trait cannot express.

    bisect_right

    source
    fn[T : Compare + Eq] bisect_right(a : ArrayView[T], value : T) -> Int

    The first index past every element equal to value: every element before the result is less than or equal to value.

    a must already be sorted ascending. The result is in 0..=a.length().

    bisect_right_by

    source
    fn[T] bisect_right_by(a : ArrayView[T], value : T, cmp~ : (T, T) -> Int) -> Int

    bisect_right with an explicit comparator, for an ordering the Compare trait cannot express.

    chunk_by

    source
    fn[T] chunk_by(it : Iter[T], same : (T, T) -> Bool) -> Iter[Array[T]]

    Splits a sequence into runs in which each adjacent pair satisfies same.

    chunks

    source
    fn[T] chunks(it : Iter[T], size : Int) -> Iter[Array[T]]

    Splits a sequence into consecutive arrays of at most size elements; the last one may be shorter. A non-positive size yields nothing.

    clamp

    source
    fn[T : Compare + Eq] clamp(value : T, min~ : T, max~ : T) -> T

    Restricts value to the closed interval [min, max].

    Core's numeric clamp covers the built-in number types only; this one works for any ordered value, such as a date or a version. min must not be greater than max.

    count

    source
    fn count(n : Int) -> Iter[Int]

    The unbounded sequence n, n+1, n+2, ....

    cycle

    source
    fn[T] cycle(it : Iter[T]) -> Iter[T]

    Repeats a sequence forever. The elements are buffered on the first pass, so the source must be finite; an empty source yields an empty iterator.

    duplicates

    source
    fn[T : Hash + Eq] duplicates(a : ArrayView[T]) -> Array[T]

    Every element that occurs more than once, repeated once for each occurrence past the first, in the order the extra occurrences are met.

    equal_range

    source
    fn[T : Compare + Eq] equal_range(a : ArrayView[T], value : T) -> (Int, Int)

    The half-open range of elements equal to value in an ascending run, as (bisect_left, bisect_right).

    exactly_one

    source
    fn[T] exactly_one(a : ArrayView[T], pred : (T) -> Bool) -> Bool

    Whether exactly one element satisfies pred. Stops at the second match.

    find_run

    source
    fn[T : Eq] find_run(haystack : ArrayView[T], needle : ArrayView[T]) -> Int?

    The first index at which needle occurs as a contiguous run inside haystack, or None. An empty needle occurs at index 0.

    fold_first

    source
    fn[T] fold_first(it : Iter[T], f : (T, T) -> T) -> T?

    Folds the elements pairwise with f, or None when the sequence is empty.

    fold_while

    source
    fn[A, B] fold_while(it : Iter[A], init~ : B, f : (B, A) -> Result[B, B]) -> B

    Folds while f returns Ok, and returns the value carried by the first Err, or the final accumulator when the source ends.

    gather_in_place

    source
    fn[T] gather_in_place(a : Array[T], mid~ : Int, pred : (T) -> Bool) -> Int

    Gathers every element satisfying pred into one contiguous block that starts as close to mid as the run allows, preserving the relative order of the gathered elements (and, here, of the rest too).

    Returns the index just past the gathered block. A mid that would push the block past the end is moved left so the block still fits.

    group_by

    source
    fn[T, K : Eq] group_by(it : Iter[T], key~ : (T) -> K) -> Iter[(K, Array[T])]

    Groups consecutive elements that share a key, yielding each key with its run. Equal keys that are not adjacent form separate groups, as in itertools.groupby.

    insort_left_in_place

    source
    fn[T : Compare + Eq] insort_left_in_place(a : Array[T], value : T) -> Unit

    Inserts value before any element equal to it, keeping a ascending.

    insort_right_in_place

    source
    fn[T : Compare + Eq] insort_right_in_place(a : Array[T], value : T) -> Unit

    Inserts value after any element equal to it, keeping a ascending.

    interleave

    source
    fn[T] interleave(a : Iter[T], b : Iter[T]) -> Iter[T]

    Alternates elements of the two sequences, starting with the first, and drains the longer one once the shorter ends.

    interleave_shortest

    source
    fn[T] interleave_shortest(a : Iter[T], b : Iter[T]) -> Iter[T]

    Alternates elements of the two sequences and stops as soon as either one is exhausted, so the result has twice the shorter length.

    is_palindrome

    source
    fn[T : Eq] is_palindrome(a : ArrayView[T]) -> Bool

    Whether the run reads the same forwards and backwards.

    is_partitioned

    source
    fn[T] is_partitioned(a : ArrayView[T], pred : (T) -> Bool) -> Bool

    Whether every element satisfying pred comes before every element that does not. An empty run is partitioned.

    is_partitioned_until

    source
    fn[T] is_partitioned_until(a : ArrayView[T], pred : (T) -> Bool) -> Int?

    The first index at which the partitioning breaks: an element that satisfies pred and follows one that does not, or None when the whole run is partitioned. The result is therefore the partition point when it exists, and partition_point alone cannot tell the two cases apart.

    k_largest

    source
    fn[T : Compare + Eq] k_largest(k : Int, a : ArrayView[T]) -> Array[T]

    The k largest elements, in descending order. A negative or zero k yields an empty array.

    k_smallest

    source
    fn[T : Compare + Eq] k_smallest(k : Int, a : ArrayView[T]) -> Array[T]

    The k smallest elements, in ascending order. A negative or zero k yields an empty array.

    k_way_merge

    source
    fn[T : Compare + Eq] k_way_merge(lists : ArrayView[ArrayView[T]]) -> Array[T]

    Merges k ascending runs into one ascending run with a heap of the runs' current heads, in O(n log k). Equal elements are taken from the earlier run first, so the merge is deterministic.

    max_set

    source
    fn[T : Compare + Eq] max_set(a : ArrayView[T]) -> Array[T]

    Every element equal to the largest, in their original order.

    merge

    source
    fn[T : Compare + Eq] merge(a : ArrayView[T], b : ArrayView[T]) -> Array[T]

    Merges two ascending runs into one ascending run, keeping equal elements in the order they had in the inputs (all of a before b's equal ones).

    merge_in_place

    source
    fn[T : Compare + Eq] merge_in_place(a : Array[T], b : Array[T]) -> Unit

    Merges two ascending runs in place, leaving b unchanged and a holding the merged result.

    merge_join_by

    source
    fn[A, B] merge_join_by(a : ArrayView[A], b : ArrayView[B], cmp~ : (A, B) -> Int) -> Iter[JoinEntry[A, B]]

    Walks two ordered runs together with an explicit comparator, yielding one JoinEntry per step in the order the runs are consumed.

    min_max

    source
    fn[T : Compare + Eq] min_max(it : Iter[T]) -> (T, T)?

    The smallest and largest elements of a sequence, or None when it is empty.

    min_max_element

    source
    fn[T : Compare + Eq] min_max_element(a : ArrayView[T]) -> (Int, Int)?

    The positions of the first smallest and the first largest element, or None for an empty run.

    min_set

    source
    fn[T : Compare + Eq] min_set(a : ArrayView[T]) -> Array[T]

    Every element equal to the smallest, in their original order.

    mismatch

    source
    fn[T : Eq] mismatch(a : ArrayView[T], b : ArrayView[T]) -> (Int, Int)?

    The first pair of positions at which two runs differ.

    Returns None when the runs are equal. When one run is a prefix of the other, the difference is reported at the end of the shorter run, so both components of the result are its length.

    next_permutation_in_place

    source
    fn[T : Compare + Eq] next_permutation_in_place(a : Array[T]) -> Bool

    Rearranges the run into the next lexicographic permutation, returning false and wrapping around to the ascending order when the run is already the largest permutation.

    nth_element_in_place

    source
    fn[T : Compare + Eq] nth_element_in_place(a : Array[T], k : Int) -> Unit

    Arranges the run so that the element at position k is the one that would be there if the whole run were sorted, with smaller elements before it and larger ones after. Expected linear time.

    An out-of-range k leaves the run unchanged.

    pad_using

    source
    fn[T] pad_using(it : Iter[T], n : Int, f : (Int) -> T) -> Iter[T]

    Yields the source elements, then pads with f(i) where i is the position in the output, until the output has at least n elements.

    partial_sort_in_place

    source
    fn[T : Compare + Eq] partial_sort_in_place(a : Array[T], k : Int) -> Unit

    Partially orders the run so that the first k elements are the k smallest, in ascending order. The rest stays in the run in no particular order. k is clamped to the run length.

    partition_copy

    source
    fn[T] partition_copy(a : ArrayView[T], pred : (T) -> Bool) -> (Array[T], Array[T])

    Splits the run into the elements satisfying pred and the rest, both in their original order.

    partition_in_place

    source
    fn[T] partition_in_place(a : Array[T], pred : (T) -> Bool) -> Int

    Groups the run so that every element satisfying pred comes first, and returns the boundary: the number of elements that satisfy pred. Unstable and linear.

    partition_pair

    source
    fn[A, B] partition_pair(a : ArrayView[A], f : (A) -> B?) -> (Array[B], Array[A])

    Applies f to every element: the mapped results keep their original order in the first array, the elements for which f returns None keep theirs in the second.

    partition_point

    source
    fn[T] partition_point(a : ArrayView[T], pred : (T) -> Bool) -> Int

    The first index for which pred is false, assuming every true element precedes every false one. The result is in 0..=a.length().

    peek_nth

    source
    fn[T] peek_nth(it : Iter[T], n : Int) -> Iter[T]

    An iterator over the same elements that keeps up to n elements of lookahead buffered, so that a source with side effects is read ahead. The yielded sequence is unchanged.

    position_max

    source
    fn[T : Compare + Eq] position_max(a : ArrayView[T]) -> Int?

    The position of the first largest element, or None when empty.

    position_min

    source
    fn[T : Compare + Eq] position_min(a : ArrayView[T]) -> Int?

    The position of the first smallest element, or None when empty.

    position_min_max

    source
    fn[T : Compare + Eq] position_min_max(a : ArrayView[T]) -> (Int, Int)?

    Both extremum positions in one pass, or None when empty.

    prefix_sum

    source
    fn[T] prefix_sum(a : ArrayView[T], op~ : (T, T) -> T) -> Array[T]

    Running combination without an identity element: element i of the result is a[0] op a[1] op ... op a[i]. The empty run yields an empty array.

    prev_permutation_in_place

    source
    fn[T : Compare + Eq] prev_permutation_in_place(a : Array[T]) -> Bool

    Rearranges the run into the previous lexicographic permutation, returning false and wrapping around to the descending order when the run is already the smallest permutation.

    replace_in_place

    source
    fn[T : Eq] replace_in_place(a : Array[T], old : T, new : T) -> Int

    Replaces every element equal to old with new and returns how many elements were replaced.

    rotate

    source
    fn[T] rotate(a : ArrayView[T], mid~ : Int) -> Array[T]

    rotate_in_place on a copy, leaving the input alone.

    rotate_in_place

    source
    fn[T] rotate_in_place(a : Array[T], mid~ : Int) -> Unit

    Rotates the run left by mid: the element at mid becomes the first and the elements before it move to the end. mid is clamped to the run.

    scan

    source
    fn[A, B] scan(it : Iter[A], init~ : B, f : (B, A) -> B) -> Iter[B]

    Running combination: yields acc after folding each source element into it, starting from init. Unlike core's accumulate, no initial value is yielded, so an empty source yields nothing.

    scan_in_place

    source
    fn[T] scan_in_place(a : Array[T], op~ : (T, T) -> T) -> Unit

    Replaces every element but the first with the running combination up to it, in place.

    shift_left_in_place

    source
    fn[T] shift_left_in_place(a : Array[T], n~ : Int) -> Unit

    Moves the run left by n positions: the result starts at the element that was at n, and the vacated tail repeats the last element. The length does not change. n is clamped to the run.

    C++20's std::shift_left leaves the tail in an unspecified state; this function makes the state deterministic by duplicating the boundary element.

    shift_right_in_place

    source
    fn[T] shift_right_in_place(a : Array[T], n~ : Int) -> Unit

    Moves the run right by n positions: the vacated head repeats the first element, and the elements that would pass the end are dropped. The length does not change. n is clamped to the run.

    C++20's std::shift_right leaves the head in an unspecified state; this function makes the state deterministic by duplicating the boundary element.

    sort_subrange_in_place

    source
    fn[T : Compare + Eq] sort_subrange_in_place(a : Array[T], start~ : Int, end~ : Int) -> Unit

    Sorts the half-open subrange [start, end) ascending and leaves the rest of the run untouched. Bounds are clamped to the run.

    sorted

    source
    fn[T : Compare + Eq] sorted(a : ArrayView[T]) -> Array[T]

    A sorted copy of the run, ascending.

    sorted_by_key

    source
    fn[T, K : Compare + Eq] sorted_by_key(a : ArrayView[T], key~ : (T) -> K) -> Array[T]

    A sorted copy of the run, ordered by key rather than by the element itself. key is evaluated on every comparison, so keep it cheap.

    stable_partition_in_place

    source
    fn[T] stable_partition_in_place(a : Array[T], pred : (T) -> Bool) -> Int

    Like partition_in_place, but keeps the relative order within both groups. The partition is done by recursively partitioning halves and rotating the two middle blocks into place, which is O(n log n) time and O(log n) stack.

    take_while_inclusive

    source
    fn[T] take_while_inclusive(it : Iter[T], pred : (T) -> Bool) -> Iter[T]

    Yields elements while pred holds, and also yields the first element for which it fails, then stops.

    tee

    source
    fn[T] tee(it : Iter[T]) -> (Iter[T], Iter[T])

    Splits a sequence into two independent iterators over the same elements. Elements are buffered until both iterators have passed them, so the memory is proportional to how far the two consumers drift apart.

    tree_reduce

    source
    fn[T] tree_reduce(it : Iter[T], f : (T, T) -> T) -> T?

    Combines adjacent pairs level by level, keeping the shape of a balanced reduction tree, and returns the final value. The empty sequence yields None.

    unique

    source
    fn[T : Hash + Eq] unique(a : ArrayView[T]) -> Array[T]

    The distinct elements of the run in order of first appearance.

    windows_circular

    source
    fn[T] windows_circular(a : ArrayView[T], size : Int) -> Iter[Array[T]]

    Every window of size elements taken with wraparound, starting at each index: n windows for a run of n. A non-positive size or an empty run yields nothing. A window longer than the run repeats elements.

    with_position

    source
    fn[T] with_position(it : Iter[T]) -> Iter[(Position, T)]

    Pairs each element with its position, using one element of lookahead so the last element can be recognised.

    zip_eq

    source
    fn[A, B] zip_eq(a : Iter[A], b : Iter[B]) -> Iter[(A, B)] raise 
    Refused

    Pairs the two sequences element by element and raises @spec.Refused::Incompatible when their lengths differ.

    Both sequences are read in full when this function is called, because the check has to happen before the first pair is produced; it therefore requires finite inputs.

    zip_longest

    source
    fn[A, B] zip_longest(a : Iter[A], b : Iter[B], fill~ : A, fill_b~ : B) -> Iter[(A, B)]

    Pairs elements while both sequences have them, then pairs the leftovers of the longer one with the corresponding fill value.

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io