6.1. Miscellaneous algorithms

The ALGORITHM module provides array and collection manipulation algorithms including sorting, searching, set operations, element removal, and more.

Key features:

  • Search: lower_bound, upper_bound, binary_search, equal_range

  • Array manipulation: unique, sort_unique, reverse, combine, fill, rotate, erase_all, min_element, max_element, is_sorted, topological_sort

  • Set operations (on tables): intersection, union, difference, symmetric_difference, identical, is_subset

Most functions also support fixed-size arrays via [expect_any_array] overloads.

See Algorithm for a hands-on tutorial.

All functions and symbols are in “algorithm” module, use require to get access to it.

require daslib/algorithm

Example:

require daslib/algorithm

    [export]
    def main() {
        var arr <- [3, 1, 4, 1, 5, 9, 2, 6, 5]
        sort_unique(arr)
        print("sort_unique: {arr}\n")
        print("has 4: {binary_search(arr, 4)}\n")
        print("has 7: {binary_search(arr, 7)}\n")
        print("lower_bound(4): {lower_bound(arr, 4)}\n")
        print("upper_bound(4): {upper_bound(arr, 4)}\n")
        let er = equal_range(arr, 5)
        print("equal_range(5): {er}\n")
        print("min index: {min_element(arr)}\n")
        print("is_sorted: {is_sorted(arr)}\n")
    }

6.1.2. Array manipulation

6.1.2.1. combine

algorithm::combine(a: array<auto(TT)>; b: array<auto(TT)>) : auto()

Returns a new array containing elements from a followed by b.

Arguments

  • a : array<auto(TT)>

  • b : array<auto(TT)>

algorithm::combine(a: auto; b: auto) : auto()
algorithm::erase_all(arr: auto; value: auto) : auto()

Erases all elements equal to value from arr in O(n) time. Uses swap to support non-copyable types. Removed elements are swapped to the tail and properly finalized by resize.

Arguments

  • arr : auto

  • value : auto

6.1.2.2. fill

algorithm::fill(a: array<auto(TT)>; value: TT) : auto()

Sets all elements of the array to the given value using clone.

Arguments

  • a : array<auto(TT)>

  • value : TT

algorithm::fill(a: auto; value: auto) : auto()

6.1.2.3. is_sorted

algorithm::is_sorted(a: auto) : bool()

Returns true if the array is sorted in non-descending order.

Arguments

  • a : auto

algorithm::is_sorted(a: array<auto(TT)>) : bool()
algorithm::is_sorted(a: array<auto(TT)>; less: block<(a:TT;b:TT):bool>) : bool()

6.1.2.4. max_element

algorithm::max_element(a: auto) : int()

Returns the index of the maximum element in the array, or -1 if the array is empty.

Arguments

  • a : auto

algorithm::max_element(a: array<auto(TT)>; less: block<(a:TT;b:TT):bool>) : int()
algorithm::max_element(a: array<auto(TT)>) : int()

6.1.2.5. min_element

algorithm::min_element(a: array<auto(TT)>; less: block<(a:TT;b:TT):bool>) : int()

Returns the index of the minimum element according to the provided less function, or -1 if the array is empty.

Arguments

  • a : array<auto(TT)>

  • less : block<(a:TT;b:TT):bool>

algorithm::min_element(a: auto) : int()
algorithm::min_element(a: array<auto(TT)>) : int()

6.1.2.6. reverse

algorithm::reverse(a: auto) : auto()

Reverses the elements of array a in place.

Arguments

  • a : auto

algorithm::reverse(a: array<auto>) : auto()

6.1.2.7. rotate

algorithm::rotate(a: array<auto>; mid: int) : auto()

Rotates the array so that the element at index mid becomes the first element. Elements before mid are moved to the end.

Arguments

  • a : array<auto>

  • mid : int

algorithm::rotate(a: auto; mid: int) : auto()
algorithm::sort_unique(a: array<auto(TT)>) : auto()

Returns an array of elements from a, sorted and with duplicates removed. The elements are sorted in ascending order. The resulting array has only unique elements.

Arguments

  • a : array<auto(TT)>

algorithm::topological_sort(nodes: array<auto(Node)>) : auto()

Topological sort of a graph. Each node has an id, and set (table with no values) of dependencies. Dependency before represents a link from a node, which should appear in the sorted list before the node. Returns a sorted list of nodes.

Arguments

  • nodes : array<auto(Node)>

algorithm::unique(a: array<auto(TT)>) : auto()

Returns an array with adjacent duplicate elements removed. The array should be sorted first if all duplicates need to be removed.

Arguments

  • a : array<auto(TT)>

6.1.3. Table manipulation

algorithm::difference(a: table<auto(TT), void>; b: table<auto(TT), void>) : table<TT, void>()

Returns the difference of two sets.

Arguments

  • a : table<auto(TT);void>

  • b : table<auto(TT);void>

algorithm::identical(a: table<auto(TT), void>; b: table<auto(TT), void>) : bool()

Returns true if the two sets are identical.

Arguments

  • a : table<auto(TT);void>

  • b : table<auto(TT);void>

algorithm::intersection(a: table<auto(TT), void>; b: table<auto(TT), void>) : table<TT, void>()

Returns the intersection of two sets.

Arguments

  • a : table<auto(TT);void>

  • b : table<auto(TT);void>

algorithm::is_subset(a: table<auto(TT), void>; b: table<auto(TT), void>) : bool()

Returns true if all elements of a are contained in b.

Arguments

  • a : table<auto(TT);void>

  • b : table<auto(TT);void>

algorithm::symmetric_difference(a: table<auto(TT), void>; b: table<auto(TT), void>) : table<TT, void>()

Returns the symmetric difference of two sets (elements in either set but not both).

Arguments

  • a : table<auto(TT);void>

  • b : table<auto(TT);void>

algorithm::union(a: table<auto(TT), void>; b: table<auto(TT), void>) : table<TT, void>()

Returns the union of two sets.

Arguments

  • a : table<auto(TT);void>

  • b : table<auto(TT);void>