ocean.core.array.Search

Collection of utilities to search within arrays and buffers.

All functions in this module must never mutate their arguments and must never allocate new memory each call. Some may keep internal static GC buffers if required by algorithm.

Based on tango.core.Array module from Tango library.

Members

Aliases

ssize_t
alias ssize_t = long
Undocumented in source.
ssize_t
alias ssize_t = int
Undocumented in source.

Functions

bcontains
bool bcontains(T[] array, T match)

Searches a sorted array for the specified element. The array is assumed to be pre-sorted in ascending order, the search will not work properly if it is not. If T is a class or struct, comparison is performed using T.opCmp(). Otherwise, elements of T are compared using ">" and ">=" or, if T is compatible to size_t (which includes ssize_t, the signed version of size_t), by calculating the difference.

bsearch
bool bsearch(T[] array, T match, size_t position)

Searches a sorted array for the specified element or for the insert position of the element. The array is assumed to be pre-sorted in ascending order, the search will not work properly if it is not. If T is a class or struct, comparison is performed using T.opCmp(). Otherwise, elements of T are compared using ">" and ">=" or, if T is compatible to size_t (which includes ssize_t, the signed version of size_t), by calculating the difference.

bsearchCustom
bool bsearchCustom(size_t array_length, ssize_t delegate(size_t i) cmp, size_t position)

Searches a sorted array for an element or an insert position for an element. The array is assumed to be pre-sorted according to cmp.

bsubset
bool bsubset(T[] a, T[] b)

Checks if array B is a subset of array A. Array A is assumed to be pre-sorted in ascending order. Array B doesn't need to be sorted and might have duplicate elements. It checks if array A contains each item of array B using binary search. If T is a class or struct, comparison is performed using T.opCmp(). Otherwise, elements of T are compared using ">" and ">=" or, if T is compatible to size_t (which includes ssize_t, the signed version of size_t), by calculating the difference.

contains
equals_t contains(T[] haystack, T needle, Pred pred)
equals_t contains(T[] haystack, T[] needle, Pred pred)
equals_t contains(Buffer!(T) haystack, T needle, Pred pred)
equals_t contains(Buffer!(T) haystack, T[] needle, Pred pred)

Performs a linear scan of haystack from [0 .. haystack.length$(RP), returning true if an element matching needle is found. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

count
size_t count(T[] haystack, T needle, Pred pred)
size_t count(Buffer!(T) haystack, T needle, Pred pred)

Performs a linear scan of haystack from [0 .. haystack.length$(RP), returning a count of the number of elements matching needle. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

countIf
size_t countIf(T[] haystack, Pred pred)

Performs a linear scan of haystack from [0 .. haystack.length$(RP), returning a count of the number of elements where pred returns true.

countIf
size_t countIf(Buffer!(T) haystack, Pred pred)
Undocumented in source. Be warned that the author may not have intended to support it.
endsWith
bool endsWith(T[] arr, T[] suffix)

Check if the given array ends with the given suffix

find
size_t find(T[] haystack, T needle, Pred pred)
size_t find(T[] haystack, T[] needle, Pred pred)
size_t find(Buffer!(T) haystack, T[] needle, Pred pred)
size_t find(Buffer!(T) haystack, T needle, Pred pred)

Linear search in an array

findAdj
size_t findAdj(T[] haystack, Pred pred)
size_t findAdj(Buffer!(T) haystack, Pred pred)

Performs a linear scan of haystack from [0 .. haystack.length$(RP), returning the index of the first element that compares equal to the next element in the sequence. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

findIf
size_t findIf(T[] haystack, Pred pred)
size_t findIf(Buffer!(T) haystack, Pred pred)

Performs a linear scan of haystack from [0 .. haystack.length$(RP), returning the index of the first element where pred returns true.

includes
bool includes(T[] setA, T[] setB, Pred pred)

Performs a parallel linear scan of setA and setB from [0 .. N$(RP) where N = min(setA.length, setB.length), returning true if setA includes all elements in setB and false if not. Both setA and setB are required to be sorted, and duplicates in setB require an equal number of duplicates in setA. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

kfind
size_t kfind(T[] haystack, T needle, Pred pred)
size_t kfind(T[] haystack, T[] needle, Pred pred)
size_t kfind(Buffer!(T) haystack, T[] needle, Pred pred)
size_t kfind(Buffer!(T) haystack, T needle, Pred pred)

Performs a linear scan of haystack from [0 .. haystack.length$(RP), returning the index of the first element matching needle, or haystack.length if no match was found. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

mismatch
size_t mismatch(T[] arr, T[] arr_against, Pred pred)
size_t mismatch(Buffer!(T) arr, Buffer!(T) arr_against, Pred pred)

Performs a parallel linear scan of arr and arr_against from [0 .. N$(RP) where N = min(arr.length, arr_against.length), returning the index of the first element in arr which does not match the corresponding element in arr_against or N if no mismatch occurs. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

removePrefix
T1[] removePrefix(T1[] arr, T2[] prefix)

Remove the given prefix from the given array.

removeSuffix
T1[] removeSuffix(T1[] arr, T2[] suffix)

Remove the given suffix from the given array.

rfind
size_t rfind(T[] haystack, T needle, Pred pred)
size_t rfind(T[] haystack, T[] needle, Pred pred)
size_t rfind(Buffer!(T) haystack, T[] needle, Pred pred)
size_t rfind(Buffer!(T) haystack, T needle, Pred pred)

Performs a linear scan of haystack from $(LP)haystack.length .. 0], returning the index of the first element matching needle, or haystack.length if no match was found. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

rfindIf
size_t rfindIf(T[] haystack, Pred pred)
size_t rfindIf(Buffer!(T) haystack, Pred pred)

Performs a linear scan of haystack from $(LP)haystack.length .. 0], returning the index of the first element where pred returns true.

startsWith
bool startsWith(T[] arr, T[] prefix)

Check if the given array starts with the given prefix

Meta

License

Tango Dual License: 3-Clause BSD License / Academic Free License v3.0. See LICENSE_TANGO.txt for details.