26. Miscelanious algorithms

The ALGORITHM module exposes collection of miscellaneous array manipulation algorithms.

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

require daslib/algorithm

26.1. Search

• lower_bound (a: array<auto(TT)>; f: int; l: int; val: TT) : auto

• lower_bound (a: array<auto(TT)>; val: TT) : auto

• lower_bound (a: array<auto(TT)>; f: int; l: int; value: auto(QQ); less: block<(a:TT;b:QQ):bool>) : auto

• lower_bound (a: array<auto(TT)>; value: auto(QQ); less: block<(a:TT;b:QQ):bool>) : auto

• binary_search (a: array<auto(TT)>; val: TT) : auto

• binary_search (a: array<auto(TT)>; f: int; last: int; val: TT) : auto

• binary_search (a: array<auto(TT)>; val: TT; less: block<(a:TT;b:TT):bool>) : auto

• binary_search (a: array<auto(TT)>; f: int; last: int; val: TT; less: block<(a:TT;b:TT):bool>) : auto

• lower_bound (a: auto; f: int; l: int; val: auto) : auto

• lower_bound (a: auto; val: auto) : auto

• lower_bound (a: auto; f: int; l: int; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto

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

• binary_search (a: auto; val: auto) : auto

• binary_search (a: auto; f: int; last: int; val: auto) : auto

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

• binary_search (a: auto; f: int; last: int; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto

lower_bound(a: array<auto(TT)>; f: int; l: int; val: TT) : auto()

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

Arguments

• a : array<auto(TT)>

• f : int

• l : int

• val : TT

lower_bound(a: array<auto(TT)>; val: TT) : auto()

Returns an iterator pointing to the first element in the array that is not less than (i.e. greater or equal to) value, or length(a) if no such element is found.

Arguments

• a : array<auto(TT)>

• val : TT

lower_bound(a: array<auto(TT)>; f: int; l: int; value: auto(QQ); less: block<(a:TT;b:QQ):bool>) : auto()

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

Arguments

• a : array<auto(TT)>

• f : int

• l : int

• value : auto(QQ)

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

lower_bound(a: array<auto(TT)>; value: auto(QQ); less: block<(a:TT;b:QQ):bool>) : auto()

Returns an iterator pointing to the first element in the array that is not less than (i.e. greater or equal to) value, or length(a) if no such element is found.

Arguments

• a : array<auto(TT)>

• value : auto(QQ)

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

binary_search(a: array<auto(TT)>; val: TT) : auto()

Returns true if an val appears within the array a. Array a must be sorted.

Arguments

• a : array<auto(TT)>

• val : TT

binary_search(a: array<auto(TT)>; f: int; last: int; val: TT) : auto()

Returns true if an val appears within the range [f, last). Array a must be sorted.

Arguments

• a : array<auto(TT)>

• f : int

• last : int

• val : TT

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

Returns true if an val appears within the array a. Array a must be sorted according to the provided less function.

Arguments

• a : array<auto(TT)>

• val : TT

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

binary_search(a: array<auto(TT)>; f: int; last: int; val: TT; less: block<(a:TT;b:TT):bool>) : auto()

Returns true if an val appears within the range [f, last). Array a must be sorted according to the provided less function.

Arguments

• a : array<auto(TT)>

• f : int

• last : int

• val : TT

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

lower_bound(a: auto; f: int; l: int; val: auto) : auto()

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

Arguments

• a : auto

• f : int

• l : int

• val : auto

lower_bound(a: auto; val: auto) : auto()

Returns an iterator pointing to the first element in the array that is not less than (i.e. greater or equal to) value, or length(a) if no such element is found.

Arguments

• a : auto

• val : auto

lower_bound(a: auto; f: int; l: int; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto()

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

Arguments

• a : auto

• f : int

• l : int

• val : auto(TT)

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

lower_bound(a: auto; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto()

Returns an iterator pointing to the first element in the array that is not less than (i.e. greater or equal to) value, or length(a) if no such element is found.

Arguments

• a : auto

• val : auto(TT)

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

binary_search(a: auto; val: auto) : auto()

Returns true if an val appears within the array a.

Arguments

• a : auto

• val : auto

binary_search(a: auto; f: int; last: int; val: auto) : auto()

Returns true if an val appears within the range [f, last).

Arguments

• a : auto

• f : int

• last : int

• val : auto

binary_search(a: auto; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto()

Returns true if an val appears within the array a.

Arguments

• a : auto

• val : auto(TT)

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

binary_search(a: auto; f: int; last: int; val: auto(TT); less: block<(a:TT;b:TT):bool>) : auto()

Returns true if an val appears within the range [f, last).

Arguments

• a : auto

• f : int

• last : int

• val : auto(TT)

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

26.2. Array manipulation

• unique (var a: array<auto(TT)>) : auto

• sort_unique (var a: array<auto(TT)>) : auto

• reverse (var a: array<auto>) : auto

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

• reverse (var a: auto) : auto

• combine (a: auto; b: auto) : auto

• erase_all (var arr: auto; value: auto) : auto

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

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

Returns array of the elements of a with duplicates removed.

Arguments

• a : array<auto(TT)>

sort_unique(a: array<auto(TT)>) : auto()

Returns array of the elements of a, sorted and with duplicates removed. The elements of a are sorted in ascending order. The resulted array has only unqiue elements.

Arguments

• a : array<auto(TT)>

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

Returns array of the elements of a in reverse order.

Arguments

• a : array<auto>

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

Returns array of the elements of a and then b.

Arguments

• a : array<auto(TT)>

• b : array<auto(TT)>

reverse(a: auto) : auto()

Reverses the elements of array a in place.

Arguments

• a : auto

combine(a: auto; b: auto) : auto()

Returns array of the elements of a and then b.

Arguments

• a : auto

• b : auto

erase_all(arr: auto; value: auto) : auto()

Erase all elements equal to value from arr

Arguments

• arr : auto

• value : auto

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

26.3. Table manipulation

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

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

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

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

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>

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>

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>