Search¶

Usage

use Search;

The Search module is designed to support standard search routines on 1D arrays

proc search(Data: [?Dom], val, comparator: ?rec = defaultComparator, lo = Dom.low, hi = Dom.high, sorted = false)¶

General purpose searching interface for searching through a 1D array. For pre-sorted arrays, denoted by passing sorted=true as an argument, this function wraps binarySearch, otherwise it wraps :proc`linearSearch`.

Arguments:	Data : [] eltType -- The array to be searched val : eltType -- The value to find in the array comparator -- Comparator record that defines how the data is sorted, and the equality operation for the array data. lo : Dom.idxType -- The lowest index to consider while searching hi : Dom.idxType -- The highest index to consider while searching sorted : bool -- Indicate if the array is pre-sorted, determining which search algorithm to call
Returns:	A tuple indicating (1) if the value was found and (2) the location of the value if it was found or the location where the value should have been if it was not found.
Return type:	(bool, Dom.idxType)

proc linearSearch(Data: [?Dom], val, comparator: ?rec = defaultComparator, lo = Dom.low, hi = Dom.high)¶

Searches through the array Data looking for the value val using a sequential linear search. Returns a tuple indicating (1) whether or not the value was found and (2) the location of the first occurrence of the value if it was found, or Data.domain.high+1 if it was not found.

Arguments:	Data : [] eltType -- The array to search val : eltType -- The value to find in the array comparator -- Comparator record that defines the equality operation for the array data. lo : Dom.idxType -- The lowest index to consider while searching hi : Dom.idxType -- The highest index to consider while searching
Returns:	A tuple indicating (1) if the value was found and (2) the location of the value if it was found or Data.domain.high+1 if it was not found.
Return type:	(bool, Dom.idxType)

proc binarySearch(Data: [?Dom], val, comparator: ?rec = defaultComparator, in lo = Dom.low, in hi = Dom.high)¶

Searches through the pre-sorted array Data looking for the value val using a sequential binary search. If provided, only the indices lo through hi will be considered, otherwise the whole array will be searched. Returns a tuple indicating (1) whether or not the value was found and (2) the location of the value if it was found, or the location where the value should have been if it was not found.

Arguments:	Data : [] eltType -- The sorted array to search val : eltType -- The value to find in the array comparator -- Comparator record that defines how the data is sorted. lo : Dom.idxType -- The lowest index to consider while searching hi : Dom.idxType -- The highest index to consider while searching
Returns:	A tuple indicating (1) if the value was found and (2) the location of the value if it was found or the location where the value should have been if it was not found.
Return type:	(bool, Dom.idxType)