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 tutorial_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

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)>

combine(a: auto; b: auto): auto
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

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

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

6.1.2.3. is_sorted

is_sorted(a: auto): bool

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

Arguments:

  • a : auto

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

6.1.2.4. max_element

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

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

6.1.2.5. min_element

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>

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

6.1.2.6. reverse

reverse(a: auto): auto

Reverses the elements of array a in place.

Arguments:

  • a : auto

reverse(a: array<auto>): auto

6.1.2.7. rotate

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

rotate(a: auto; mid: int): auto
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)>

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)>

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

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>

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>

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>

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>

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>

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>