.. _stdlib_algorithm: ======================== Miscellaneous algorithms ======================== .. das:module:: algorithm 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 :ref:`tutorial_algorithm` for a hands-on tutorial. All functions and symbols are in "algorithm" module, use require to get access to it. .. code-block:: das require daslib/algorithm Example: .. code-block:: das 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") } ++++++ Search ++++++ * :ref:`binary_search (a: auto; f: int; last: int; val: auto) : auto ` * :ref:`binary_search (a: array\; val: TT) : auto ` * :ref:`binary_search (a: auto; f: int; last: int; val: auto(TT); less: block\<(a:TT;b:TT):bool\>) : auto ` * :ref:`binary_search (a: auto; val: auto) : auto ` * :ref:`binary_search (a: array\; val: TT; less: block\<(a:TT;b:TT):bool\>) : auto ` * :ref:`binary_search (a: array\; f: int; last: int; val: TT) : auto ` * :ref:`binary_search (a: array\; f: int; last: int; val: TT; less: block\<(a:TT;b:TT):bool\>) : auto ` * :ref:`binary_search (a: auto; val: auto(TT); less: block\<(a:TT;b:TT):bool\>) : auto ` * :ref:`equal_range (a: array\; f: int; l: int; val: TT) : auto ` * :ref:`equal_range (a: array\; val: TT) : auto ` * :ref:`lower_bound (a: array\; value: auto(QQ); less: block\<(a:TT;b:QQ):bool\>) : auto ` * :ref:`lower_bound (a: array\; val: TT) : auto ` * :ref:`lower_bound (a: auto; val: auto(TT); less: block\<(a:TT;b:TT):bool\>) : auto ` * :ref:`lower_bound (a: array\; f: int; l: int; val: TT) : auto ` * :ref:`lower_bound (a: array\; f: int; l: int; value: auto(QQ); less: block\<(a:TT;b:QQ):bool\>) : auto ` * :ref:`lower_bound (a: auto; f: int; l: int; val: auto) : auto ` * :ref:`lower_bound (a: auto; val: auto) : auto ` * :ref:`lower_bound (a: auto; f: int; l: int; val: auto(TT); less: block\<(a:TT;b:TT):bool\>) : auto ` * :ref:`upper_bound (a: array\; f: int; l: int; value: auto(QQ); less: block\<(a:TT;b:QQ):bool\>) : auto ` * :ref:`upper_bound (a: array\; val: TT) : auto ` * :ref:`upper_bound (a: auto; f: int; l: int; val: auto) : auto ` * :ref:`upper_bound (a: array\; value: auto(QQ); less: block\<(a:TT;b:QQ):bool\>) : auto ` * :ref:`upper_bound (a: auto; val: auto) : auto ` * :ref:`upper_bound (a: array\; f: int; l: int; val: TT) : auto ` * :ref:`upper_bound (a: auto; val: auto(TT); less: block\<(a:TT;b:TT):bool\>) : auto ` * :ref:`upper_bound (a: auto; f: int; l: int; val: auto(TT); less: block\<(a:TT;b:TT):bool\>) : auto ` binary_search ^^^^^^^^^^^^^ .. _function-algorithm_binary_search_auto_int_int_auto_0x12a: .. das:function:: binary_search(a: auto; f: int; last: int; val: auto) : auto Returns true if val appears within the range [f, last). :Arguments: * **a** : auto * **f** : int * **last** : int * **val** : auto .. _function-algorithm_binary_search_array_ls_autoTT_gr__TT: .. das:function:: binary_search(a: array; val: TT) : auto .. _function-algorithm_binary_search_auto_int_int_autoTT_block_ls_a_c_TT;b_c_TT_c_bool_gr__0x144: .. das:function:: binary_search(a: auto; f: int; last: int; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto .. _function-algorithm_binary_search_auto_auto_0x11d: .. das:function:: binary_search(a: auto; val: auto) : auto .. _function-algorithm_binary_search_array_ls_autoTT_gr__TT_block_ls_a_c_TT;b_c_TT_c_bool_gr_: .. das:function:: binary_search(a: array; val: TT; less: block<(a:TT;b:TT):bool>) : auto .. _function-algorithm_binary_search_array_ls_autoTT_gr__int_int_TT: .. das:function:: binary_search(a: array; f: int; last: int; val: TT) : auto .. _function-algorithm_binary_search_array_ls_autoTT_gr__int_int_TT_block_ls_a_c_TT;b_c_TT_c_bool_gr_: .. das:function:: binary_search(a: array; f: int; last: int; val: TT; less: block<(a:TT;b:TT):bool>) : auto .. _function-algorithm_binary_search_auto_autoTT_block_ls_a_c_TT;b_c_TT_c_bool_gr__0x137: .. das:function:: binary_search(a: auto; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto ---- equal_range ^^^^^^^^^^^ .. _function-algorithm_equal_range_array_ls_autoTT_gr__int_int_TT: .. das:function:: equal_range(a: array; f: int; l: int; val: TT) : auto Returns a pair of indices [lower, upper) bounding the range of elements equal to val within [f, l). The array must be sorted. :Arguments: * **a** : array * **f** : int * **l** : int * **val** : TT .. _function-algorithm_equal_range_array_ls_autoTT_gr__TT: .. das:function:: equal_range(a: array; val: TT) : auto ---- lower_bound ^^^^^^^^^^^ .. _function-algorithm_lower_bound_array_ls_autoTT_gr__autoQQ_block_ls_a_c_TT;b_c_QQ_c_bool_gr__0x70: .. das:function:: lower_bound(a: array; value: auto(QQ); less: block<(a:TT;b:QQ):bool>) : auto Returns the index of the first element in the array for which less returns false, or length(a) if no such element is found. :Arguments: * **a** : array * **value** : auto(QQ) * **less** : block<(a:TT;b:QQ):bool> .. _function-algorithm_lower_bound_array_ls_autoTT_gr__TT: .. das:function:: lower_bound(a: array; val: TT) : auto .. _function-algorithm_lower_bound_auto_autoTT_block_ls_a_c_TT;b_c_TT_c_bool_gr__0x110: .. das:function:: lower_bound(a: auto; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto .. _function-algorithm_lower_bound_array_ls_autoTT_gr__int_int_TT: .. das:function:: lower_bound(a: array; f: int; l: int; val: TT) : auto .. _function-algorithm_lower_bound_array_ls_autoTT_gr__int_int_autoQQ_block_ls_a_c_TT;b_c_QQ_c_bool_gr__0x5d: .. das:function:: lower_bound(a: array; f: int; l: int; value: auto(QQ); less: block<(a:TT;b:QQ):bool>) : auto .. _function-algorithm_lower_bound_auto_int_int_auto_0xe9: .. das:function:: lower_bound(a: auto; f: int; l: int; val: auto) : auto .. _function-algorithm_lower_bound_auto_auto_0xf6: .. das:function:: lower_bound(a: auto; val: auto) : auto .. _function-algorithm_lower_bound_auto_int_int_autoTT_block_ls_a_c_TT;b_c_TT_c_bool_gr__0x103: .. das:function:: lower_bound(a: auto; f: int; l: int; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto ---- upper_bound ^^^^^^^^^^^ .. _function-algorithm_upper_bound_array_ls_autoTT_gr__int_int_autoQQ_block_ls_a_c_TT;b_c_QQ_c_bool_gr__0xac: .. das:function:: upper_bound(a: array; f: int; l: int; value: auto(QQ); less: block<(a:TT;b:QQ):bool>) : auto Returns the index of the first element in the range [f, l) for which less(val, element) returns true, or l if no such element is found. :Arguments: * **a** : array * **f** : int * **l** : int * **value** : auto(QQ) * **less** : block<(a:TT;b:QQ):bool> .. _function-algorithm_upper_bound_array_ls_autoTT_gr__TT: .. das:function:: upper_bound(a: array; val: TT) : auto .. _function-algorithm_upper_bound_auto_int_int_auto_0x151: .. das:function:: upper_bound(a: auto; f: int; l: int; val: auto) : auto .. _function-algorithm_upper_bound_array_ls_autoTT_gr__autoQQ_block_ls_a_c_TT;b_c_QQ_c_bool_gr__0xbf: .. das:function:: upper_bound(a: array; value: auto(QQ); less: block<(a:TT;b:QQ):bool>) : auto .. _function-algorithm_upper_bound_auto_auto_0x15e: .. das:function:: upper_bound(a: auto; val: auto) : auto .. _function-algorithm_upper_bound_array_ls_autoTT_gr__int_int_TT: .. das:function:: upper_bound(a: array; f: int; l: int; val: TT) : auto .. _function-algorithm_upper_bound_auto_autoTT_block_ls_a_c_TT;b_c_TT_c_bool_gr__0x178: .. das:function:: upper_bound(a: auto; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto .. _function-algorithm_upper_bound_auto_int_int_autoTT_block_ls_a_c_TT;b_c_TT_c_bool_gr__0x16b: .. das:function:: upper_bound(a: auto; f: int; l: int; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto ++++++++++++++++++ Array manipulation ++++++++++++++++++ * :ref:`combine (a: array\; b: array\) : auto ` * :ref:`combine (a: auto; b: auto) : auto ` * :ref:`erase_all (var arr: auto; value: auto) : auto ` * :ref:`fill (var a: array\; value: TT) : auto ` * :ref:`fill (var a: auto; value: auto) : auto ` * :ref:`is_sorted (a: auto) : bool ` * :ref:`is_sorted (a: array\) : bool ` * :ref:`is_sorted (a: array\; less: block\<(a:TT;b:TT):bool\>) : bool ` * :ref:`max_element (a: auto) : int ` * :ref:`max_element (a: array\; less: block\<(a:TT;b:TT):bool\>) : int ` * :ref:`max_element (a: array\) : int ` * :ref:`min_element (a: array\; less: block\<(a:TT;b:TT):bool\>) : int ` * :ref:`min_element (a: auto) : int ` * :ref:`min_element (a: array\) : int ` * :ref:`reverse (var a: auto) : auto ` * :ref:`reverse (var a: array\) : auto ` * :ref:`rotate (var a: array\; mid: int) : auto ` * :ref:`rotate (var a: auto; mid: int) : auto ` * :ref:`sort_unique (var a: array\) : auto ` * :ref:`topological_sort (nodes: array\) : auto ` * :ref:`unique (var a: array\) : auto ` combine ^^^^^^^ .. _function-algorithm_combine_array_ls_autoTT_gr__array_ls_autoTT_gr_: .. das:function:: combine(a: array; b: array) : auto Returns a new array containing elements from a followed by b. :Arguments: * **a** : array * **b** : array .. _function-algorithm_combine_auto_auto_0xe1: .. das:function:: combine(a: auto; b: auto) : auto ---- .. _function-algorithm_erase_all_auto_auto_0x185: .. das:function:: 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 fill ^^^^ .. _function-algorithm_fill_array_ls_autoTT_gr__TT: .. das:function:: fill(a: array; value: TT) : auto Sets all elements of the array to the given value using clone. :Arguments: * **a** : array * **value** : TT .. _function-algorithm_fill_auto_auto_0x1a3: .. das:function:: fill(a: auto; value: auto) : auto ---- is_sorted ^^^^^^^^^ .. _function-algorithm_is_sorted_auto_0x1c5: .. das:function:: is_sorted(a: auto) : bool Returns true if the array is sorted in non-descending order. :Arguments: * **a** : auto .. _function-algorithm_is_sorted_array_ls_autoTT_gr_: .. das:function:: is_sorted(a: array) : bool .. _function-algorithm_is_sorted_array_ls_autoTT_gr__block_ls_a_c_TT;b_c_TT_c_bool_gr_: .. das:function:: is_sorted(a: array; less: block<(a:TT;b:TT):bool>) : bool ---- max_element ^^^^^^^^^^^ .. _function-algorithm_max_element_auto_0x230: .. das:function:: 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 .. _function-algorithm_max_element_array_ls_autoTT_gr__block_ls_a_c_TT;b_c_TT_c_bool_gr_: .. das:function:: max_element(a: array; less: block<(a:TT;b:TT):bool>) : int .. _function-algorithm_max_element_array_ls_autoTT_gr_: .. das:function:: max_element(a: array) : int ---- min_element ^^^^^^^^^^^ .. _function-algorithm_min_element_array_ls_autoTT_gr__block_ls_a_c_TT;b_c_TT_c_bool_gr_: .. das:function:: min_element(a: array; 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 * **less** : block<(a:TT;b:TT):bool> .. _function-algorithm_min_element_auto_0x228: .. das:function:: min_element(a: auto) : int .. _function-algorithm_min_element_array_ls_autoTT_gr_: .. das:function:: min_element(a: array) : int ---- reverse ^^^^^^^ .. _function-algorithm_reverse_auto_0xd9: .. das:function:: reverse(a: auto) : auto Reverses the elements of array a in place. :Arguments: * **a** : auto .. _function-algorithm_reverse_array_ls_auto_gr_: .. das:function:: reverse(a: array) : auto ---- rotate ^^^^^^ .. _function-algorithm_rotate_array_ls_auto_gr__int: .. das:function:: rotate(a: array; 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 * **mid** : int .. _function-algorithm_rotate_auto_int_0x1e6: .. das:function:: rotate(a: auto; mid: int) : auto ---- .. _function-algorithm_sort_unique_array_ls_autoTT_gr_: .. das:function:: sort_unique(a: array) : 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 .. _function-algorithm_topological_sort_array_ls_autoNode_gr_: .. das:function:: topological_sort(nodes: array) : 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 .. _function-algorithm_unique_array_ls_autoTT_gr_: .. das:function:: unique(a: array) : 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 ++++++++++++++++++ Table manipulation ++++++++++++++++++ * :ref:`difference (a: table\; b: table\) : table\ ` * :ref:`identical (a: table\; b: table\) : bool ` * :ref:`intersection (a: table\; b: table\) : table\ ` * :ref:`is_subset (a: table\; b: table\) : bool ` * :ref:`symmetric_difference (a: table\; b: table\) : table\ ` * :ref:`union (a: table\; b: table\) : table\ ` .. _function-algorithm_difference_table_ls_autoTT,_void_gr__table_ls_autoTT,_void_gr_: .. das:function:: difference(a: table; b: table) : table Returns the difference of two sets. :Arguments: * **a** : table * **b** : table .. _function-algorithm_identical_table_ls_autoTT,_void_gr__table_ls_autoTT,_void_gr_: .. das:function:: identical(a: table; b: table) : bool Returns true if the two sets are identical. :Arguments: * **a** : table * **b** : table .. _function-algorithm_intersection_table_ls_autoTT,_void_gr__table_ls_autoTT,_void_gr_: .. das:function:: intersection(a: table; b: table) : table Returns the intersection of two sets. :Arguments: * **a** : table * **b** : table .. _function-algorithm_is_subset_table_ls_autoTT,_void_gr__table_ls_autoTT,_void_gr_: .. das:function:: is_subset(a: table; b: table) : bool Returns true if all elements of a are contained in b. :Arguments: * **a** : table * **b** : table .. _function-algorithm_symmetric_difference_table_ls_autoTT,_void_gr__table_ls_autoTT,_void_gr_: .. das:function:: symmetric_difference(a: table; b: table) : table Returns the symmetric difference of two sets (elements in either set but not both). :Arguments: * **a** : table * **b** : table .. _function-algorithm_union_table_ls_autoTT,_void_gr__table_ls_autoTT,_void_gr_: .. das:function:: union(a: table; b: table) : table Returns the union of two sets. :Arguments: * **a** : table * **b** : table