tango.core.Array

License:

Authors:

size_t find(T)(Elem[] buf, Elem pat, Pred2E pred = init) ¶

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

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t find(Elem[] buf, Elem[] pat, Pred2E pred = init) ¶

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

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t rfind(Elem[] buf, Elem pat, Pred2E pred = init) ¶

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

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t rfind(Elem[] buf, Elem[] pat, Pred2E pred = init) ¶

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

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t kfind(Elem[] buf, Elem pat, Pred2E pred = init) ¶

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

This function uses the KMP algorithm and offers O(M+N) performance but must allocate a temporary buffer of size pat.sizeof to do so. If it is available on the target system, alloca will be used for the allocation, otherwise a standard dynamic memory allocation will occur.

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t kfind(Elem[] buf, Elem[] pat, Pred2E pred = init) ¶

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

This function uses the KMP algorithm and offers O(M+N) performance but must allocate a temporary buffer of size pat.sizeof to do so. If it is available on the target system, alloca will be used for the allocation, otherwise a standard dynamic memory allocation will occur.

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t krfind(Elem[] buf, Elem pat, Pred2E pred = init) ¶

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

This function uses the KMP algorithm and offers O(M+N) performance but must allocate a temporary buffer of size pat.sizeof to do so. If it is available on the target system, alloca will be used for the allocation, otherwise a standard dynamic memory allocation will occur.

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t krfind(Elem[] buf, Elem[] pat, Pred2E pred = init) ¶

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

This function uses the KMP algorithm and offers O(M+N) performance but must allocate a temporary buffer of size pat.sizeof to do so. If it is available on the target system, alloca will be used for the allocation, otherwise a standard dynamic memory allocation will occur.

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t findIf(Elem[] buf, Pred1E pred) ¶

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

Parameters:

buf	The array to search.
pred	The evaluation predicate, which should return true if the element is a valid match and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t rfindIf(Elem[] buf, Pred1E pred) ¶

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

Parameters:

buf	The array to search.
pred	The evaluation predicate, which should return true if the element is a valid match and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t findAdj(Elem[] buf, Pred2E pred = init) ¶

Performs a linear scan of buf from [0 .. buf.length), 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.

Parameters:

buf	The array to scan.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

equals_t contains(Elem[] buf, Elem pat, Pred2E pred = init) ¶

Performs a linear scan of buf from [0 .. buf.length), returning true if an element matching pat is found. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

True if an element equivalent to pat is found, false if not.

equals_t contains(Elem[] buf, Elem[] pat, Pred2E pred = init) ¶

Performs a linear scan of buf from [0 .. buf.length), returning true if a sequence matching pat is found. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

buf	The array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

True if an element equivalent to pat is found, false if not.

size_t mismatch(Elem[] bufA, Elem[] bufB, Pred2E pred = init) ¶

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

Parameters:

bufA	The array to evaluate.
bufB	The array to match against.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first mismatch or N if the first N elements of bufA and bufB match, where N = min(bufA.length, bufB.length).

size_t count(Elem[] buf, Elem pat, Pred2E pred = init) ¶

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

Parameters:

buf	The array to scan.
pat	The pattern to match.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The number of elements matching pat.

size_t countIf(Elem[] buf, Pred1E pred = init) ¶

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

Parameters:

buf	The array to scan.
pred	The evaluation predicate, which should return true if the element is a valid match and false if not. This predicate may be any callable type.

Returns:

The number of elements where pred returns true.

size_t replace(Elem[] buf, Elem pat, Elem val, Pred2E pred = init) ¶

Performs a linear scan of buf from [0 .. buf.length), replacing occurrences of pat with val. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

Parameters:

buf	The array to scan.
pat	The pattern to match.
val	The value to substitute.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The number of elements replaced.

size_t replaceIf(Elem[] buf, Elem val, Pred2E pred = init) ¶

Performs a linear scan of buf from [0 .. buf.length), replacing elements where pred returns true with val.

Parameters:

buf	The array to scan.
val	The value to substitute.
pred	The evaluation predicate, which should return true if the element is a valid match and false if not. This predicate may be any callable type.

Returns:

The number of elements replaced.

size_t remove(Elem[] buf, Elem pat, Pred2E pred = init) ¶

Performs a linear scan of buf from [0 .. buf.length), moving all elements matching pat to the end of the sequence. The relative order of elements not matching pat will be preserved. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

Parameters:

buf	The array to scan. This parameter is not marked 'ref' to allow temporary slices to be modified. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
pat	The pattern to match against.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The number of elements that do not match pat.

size_t remove(Elem[] buf, Elem pat) ¶

Performs a linear scan of buf from [0 .. buf.length), moving all elements matching pat to the end of the sequence. The relative order of elements not matching pat will be preserved. Comparisons will be performed '=='.

Parameters:

buf	The array to scan. This parameter is not marked 'ref' to allow temporary slices to be modified. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
pat	The pattern to match against.

Returns:

The number of elements that do not match pat.

size_t removeIf(Elem[] buf, Pred1E pred) ¶

Performs a linear scan of buf from [0 .. buf.length), moving all elements that satisfy pred to the end of the sequence. The relative order of elements that do not satisfy pred will be preserved.

Parameters:

buf	The array to scan. This parameter is not marked 'ref' to allow temporary slices to be modified. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
pred	The evaluation predicate, which should return true if the element satisfies the condition and false if not. This predicate may be any callable type.

Returns:

The number of elements that do not satisfy pred.

size_t distinct(Elem[] buf, Pred2E pred = init) ¶

Performs a linear scan of buf from [0 .. buf.length), moving all but the first element of each consecutive group of duplicate elements to the end of the sequence. The relative order of all remaining elements will be preserved. Comparisons will be performed using the supplied predicate or '==' if none is supplied.

Parameters:

buf	The array to scan. This parameter is not marked 'ref' to allow temporary slices to be modified. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
pred	The evaluation predicate, which should return true if e1 is equal to e2 and false if not. This predicate may be any callable type.

Returns:

The number of distinct sub-sequences in buf.

void shuffle(Elem[] buf, Oper1A oper = init) ¶

Performs a linear scan of buf from [2 .. buf.length), exchanging each element with an element in the range [0 .. pos), where pos represents the current array position.

Parameters:

buf	The array to shuffle.
oper	The randomize operation, which should return a number in the range [0 .. N) for any supplied value N. This routine may be any callable type.

size_t partition(Elem[] buf, Pred1E pred) ¶

Partitions buf such that all elements that satisfy pred will be placed before the elements that do not satisfy pred. The algorithm is not required to be stable.

Parameters:

buf	The array to partition. This parameter is not marked 'ref' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
pred	The evaluation predicate, which should return true if the element satisfies the condition and false if not. This predicate may be any callable type.

Returns:

The number of elements that satisfy pred.

size_t select(Elem[] buf, Num num, Pred2E pred = init) ¶

Partitions buf with num - 1 as a pivot such that the first num elements will be less than or equal to the remaining elements in the array. Comparisons will be performed using the supplied predicate or '<' if none is supplied. The algorithm is not required to be stable.

Parameters:

buf	The array to partition. This parameter is not marked 'ref' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
num	The number of elements which are considered significant in this array, where num - 1 is the pivot around which partial sorting will occur. For example, if num is buf.length / 2 then select will effectively partition the array around its median value, with the elements in the first half of the array evaluating as less than or equal to the elements in the second half.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

The index of the pivot point, which will be the lesser of num - 1 and buf.length.

void sort(Elem, Pred2E = IsLess!(Elem))(Elem[] buf, Pred2E pred = init) ¶

Sorts buf using the supplied predicate or '<' if none is supplied. The algorithm is not required to be stable. The current implementation is based on quicksort, but uses a three-way partitioning scheme to improve performance for ranges containing duplicate values (Bentley and McIlroy, 1993).

Parameters:

buf	The array to sort. This parameter is not marked 'ref' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

size_t lbound(Elem[] buf, Elem pat, Pred2E pred = init) ¶

Performs a binary search of buf, returning the index of the first location where pat may be inserted without disrupting sort order. If the sort order of pat precedes all elements in buf then 0 will be returned. If the sort order of pat succeeds the largest element in buf then buf.length will be returned. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

buf	The sorted array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

size_t ubound(Elem[] buf, Elem pat, Pred2E pred = init) ¶

Performs a binary search of buf, returning the index of the first location beyond where pat may be inserted without disrupting sort order. If the sort order of pat precedes all elements in buf then 0 will be returned. If the sort order of pat succeeds the largest element in buf then buf.length will be returned. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

buf	The sorted array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

The index of the first match or buf.length if no match was found.

bool bsearch(Elem[] buf, Elem pat, Pred2E pred = init) ¶

Performs a binary search of buf, returning true if an element equivalent to pat is found. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

buf	The sorted array to search.
pat	The pattern to search for.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

True if an element equivalent to pat is found, false if not.

bool includes(Elem[] setA, Elem[] setB, Pred2E pred = init) ¶

Performs a parallel linear scan of setA and setB from [0 .. N) 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.

Parameters:

setA	The sorted array to evaluate.
setB	The sorted array to match against.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

True if setA includes all elements in setB, false if not.

Elem[] unionOf(Elem[] setA, Elem[] setB, Pred2E pred = init) ¶

Computes the union of setA and setB as a set operation and returns the retult in a new sorted array. Both setA and setB are required to be sorted. If either setA or setB contain duplicates, the result will contain the larger number of duplicates from setA and setB. When an overlap occurs, entries will be copied from setA. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

setA	The first sorted array to evaluate.
setB	The second sorted array to evaluate.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

A new array containing the union of setA and setB.

Elem[] intersectionOf(Elem[] setA, Elem[] setB, Pred2E pred = init) ¶

Computes the intersection of setA and setB as a set operation and returns the retult in a new sorted array. Both setA and setB are required to be sorted. If either setA or setB contain duplicates, the result will contain the smaller number of duplicates from setA and setB. All entries will be copied from setA. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

setA	The first sorted array to evaluate.
setB	The second sorted array to evaluate.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

A new array containing the intersection of setA and setB.

Elem[] missingFrom(Elem[] setA, Elem[] setB, Pred2E pred = init) ¶

Returns a new array containing all elements in setA which are not present in setB. Both setA and setB are required to be sorted. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

setA	The first sorted array to evaluate.
setB	The second sorted array to evaluate.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

A new array containing the elements in setA that are not in setB.

Elem[] differenceOf(Elem[] setA, Elem[] setB, Pred2E pred = init) ¶

Returns a new array containing all elements in setA which are not present in setB and the elements in setB which are not present in setA. Both setA and setB are required to be sorted. Comparisons will be performed using the supplied predicate or '<' if none is supplied.

Parameters:

setA	The first sorted array to evaluate.
setB	The second sorted array to evaluate.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Returns:

A new array containing the elements in setA that are not in setB and the elements in setB that are not in setA.

void makeHeap(Elem[] buf, Pred2E pred = init) ¶

Converts buf to a heap using the supplied predicate or '<' if none is supplied.

Parameters:

buf	The array to convert. This parameter is not marked 'ref' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

void pushHeap(ref Elem[] buf, Elem val, Pred2E pred = init) ¶

Adds val to buf by appending it and adjusting it up the heap.

Parameters:

buf	The heap to modify. This parameter is marked 'ref' because buf.length will be altered.
val	The element to push onto buf.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

void popHeap(ref Elem[] buf, Pred2E pred = init) ¶

Removes the top element from buf by swapping it with the bottom element, adjusting it down the heap, and reducing the length of buf by one.

Parameters:

buf	The heap to modify. This parameter is marked 'ref' because buf.length will be altered.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

void sortHeap(Elem[] buf, Pred2E pred = init) ¶

Sorts buf as a heap using the supplied predicate or '<' if none is supplied. Calling makeHeap and sortHeap on an array in succession has the effect of sorting the array using the heapsort algorithm.

Parameters:

buf	The heap to sort. This parameter is not marked 'ref' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'ref' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
pred	The evaluation predicate, which should return true if e1 is less than e2 and false if not. This predicate may be any callable type.

Elem2[] map(Elem[] array, Map2E func, Elem2[] buf = null) ¶

Apply a function to each element an array. The function's return values are stored in another array.

Parameters:

array	the array.
func	the function to apply.
buf	a buffer in which to store the results. This will be resized if it does not have sufficient space.

Returns:

an array (the same as the buffer passed in, if possible) where the ith element is the result of applying func to the ith element of the input array

Elem reduce(Elem[] array, Reduce2E func) ¶

Reduce an array of elements to a single element, using a user-supplied reductor function.

If the array is empty, return the default value for the element type.

If the array contains only one element, return that element.

Otherwise, the reductor function will be called on every member of the array and on every resulting element until there is only one element, which is then returned.

Parameters:

array	the array to reduce
func	the reductor function

Returns:

the single element reduction

Elem[] filter(Elem[] array, Pred1E pred, Elem[] buf = null) ¶

Performs a linear scan of buf from [0 .. buf.length), creating a new array with just the elements that satisfy pred. The relative order of elements will be preserved.

Parameters:

array	The array to scan.
pred	The evaluation predicate, which should return true if the element satisfies the condition and false if not. This predicate may be any callable type.
buf	an optional buffer into which elements are filtered. This is the array that gets returned to you.

Returns:

A new array with just the elements from buf that satisfy pred.

Notes:

While most Array functions that take an output buffer size that buffer optimally, in this case, there is no way of knowing whether the output will be empty or the entire input array. If you have special knowledge in this regard, preallocating the output buffer will be advantageous.