16. 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

16.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>

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

16.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>