Search

Usage

use Search;

or

import Search;

Support for standard search routines on 1D arrays.

proc search(Data: [?Dom], val, comparator: ?rec = new 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 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 = new 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 hi+abs(Dom.stride) 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 hi+abs(Dom.stride) if it was not found.

Return type:

(bool, Dom.idxType)

proc binarySearch(Data: [?Dom], val, comparator: ?rec = new 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)