This module has the classic search functions in it.
depth-first-search init done? expander | [Function] |
Performs a depth-first search from initial state init. It will return the first state it sees for which predicate done? returns #t. It will use function expander to get a list of all states reacheable from a given state.
init can take any form the user wishes. This function treats it as opaque data to pass to done? and expander.
done? takes one argument, of the same type as init, and returns either #t or #f.
expander takes one argument, of the same type as init, and returns a list of states that can be reached from there.
breadth-first-search init done? expander | [Function] |
Performs a breadth-first search from initial state init. It will return the first state it sees for which predicate done? returns #t. It will use function expander to get a list of all states reacheable from a given state.
init can take any form the user wishes. This function treats it as opaque data to pass to done? and expander.
done? takes one argument, of the same type as init, and returns either #t or #f.
expander takes one argument, of the same type as init, and returns a list of states that can be reached from there.
binary-search-sorted-vector vec target [cmp] [default] | [Function] |
Searches a sorted vector vec for item target. A binary search is employed which should find an item in O(log n) time if it is present. If target is found, the index into vec is returned.
As part of the search, the function cmp is applied to determine whether a vector item is less than, greater than, or equal to the target. If target cannot be found in the vector, then default is returned.
cmp defaults to -, which gives a correct comparison for vectors of numbers. default will be #f if another value is not given.
(binary-search-sorted-vector #(10 20 30) 20) ⇒ 1