tango.core.Array

The array module provides array manipulation routines in a manner that balances performance and flexibility. Operations are provided for sorting, and for processing both sorted and unsorted arrays.

License:
BSD style: see license.txt

Authors:
Sean Kelly

uint find (Elem[] buf, Elem pat, Pred2E pred = null);

Elem[] buf	The array to search.
Elem pat	The pattern to search for.
Pred2E 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.

uint find (Elem[] buf, Elem[] pat, Pred2E pred = null);

Elem[] buf	The array to search.
Elem[] pat	The pattern to search for.
Pred2E 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.

uint rfind (Elem[] buf, Elem pat, Pred2E pred = null);

Elem[] buf	The array to search.
Elem pat	The pattern to search for.
Pred2E 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.

uint rfind (Elem[] buf, Elem[] pat, Pred2E pred = null);

Elem[] buf	The array to search.
Elem[] pat	The pattern to search for.
Pred2E 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.

uint kfind (Elem[] buf, Elem pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to search.
Elem pat	The pattern to search for.
Pred2E 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.

uint kfind (Elem[] buf, Elem[] pat, Pred2E pred = null);

Elem[] buf	The array to search.
Elem[] pat	The pattern to search for.
Pred2E 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.

uint krfind (Elem[] buf, Elem pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to search.
Elem pat	The pattern to search for.
Pred2E 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.

uint krfind (Elem[] buf, Elem[] pat, Pred2E pred = null);

Elem[] buf	The array to search.
Elem[] pat	The pattern to search for.
Pred2E 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.

uint 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.

Params:

Elem[] buf	The array to search.
Pred1E 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.

uint 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.

Params:

Elem[] buf	The array to search.
Pred1E 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.

uint findAdj (Elem[] buf, Elem pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to scan.
Pred2E 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.

uint contains (Elem[] buf, Elem pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to search.
Elem pat	The pattern to search for.
Pred2E 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.

uint contains (Elem[] buf, Elem[] pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to search.
Elem[] pat	The pattern to search for.
Pred2E 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.

uint mismatch (Elem[] bufA, Elem[] bufB, Pred2E pred = null);

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.

Params:

Elem[] bufA	The array to evaluate.
Elem[] bufB	The array to match against.
Pred2E 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).

uint count (Elem[] buf, Elem pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to scan.
Elem pat	The pattern to match.
Pred2E 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.

uint countIf (Elem[] buf, Pred1E pred = null);

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

Params:

Elem[] buf	The array to scan.
Pred1E 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.

uint replace (Elem[] buf, Elem pat, Elem val, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to scan.
Elem pat	The pattern to match.
Elem val	The value to substitute.
Pred2E 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.

uint replaceIf (Elem[] buf, Elem val, Pred2E pred = null);

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

Params:

Elem[] buf	The array to scan.
Elem val	The value to substitute.
Pred2E 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.

uint remove (Elem[] buf, Elem pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to scan. This parameter is not marked 'inout' to allow temporary slices to be modified. As buf is not resized in any way, omitting the 'inout' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
Elem pat	The pattern to match against.
Pred2E 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.

uint 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.

Params:

Elem[] buf	The array to scan. This parameter is not marked 'inout' to allow temporary slices to be modified. As buf is not resized in any way, omitting the 'inout' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
Pred1E 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.

uint distinct (Elem[] buf, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to scan. This parameter is not marked 'inout' to allow temporary slices to be modified. As buf is not resized in any way, omitting the 'inout' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
Pred2E 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 = null);

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.

Params:

Elem[] buf	The array to shuffle .
Oper1A 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.

uint 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.

Params:

Elem[] buf	The array to partition . This parameter is not marked 'inout' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'inout' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
Pred1E 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.

uint select (Elem[] buf, Num num, Pred2E pred = null);

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.

Params:

Elem[] buf	The array to partition. This parameter is not marked 'inout' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'inout' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
Num 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.
Pred2E 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 = Pred2E.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).

Params:

buf	The array to sort . This parameter is not marked 'inout' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'inout' 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.

uint lbound (Elem[] buf, Elem pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The sorted array to search.
Elem pat	The pattern to search for.
Pred2E 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.

uint ubound (Elem[] buf, Elem pat, Pred2E pred = null);

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.

Params:

Elem[] buf	The sorted array to search.
Elem pat	The pattern to search for.
Pred2E 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 = null);

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.

Params:

Elem[] buf	The sorted array to search.
Elem pat	The pattern to search for.
Pred2E 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 = null);

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.

Params:

Elem[] setA	The sorted array to evaluate.
Elem[] setB	The sorted array to match against.
Pred2E 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 = null);

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.

Params:

Elem[] setA	The first sorted array to evaluate.
Elem[] setB	The second sorted array to evaluate.
Pred2E 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 = null);

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.

Params:

Elem[] setA	The first sorted array to evaluate.
Elem[] setB	The second sorted array to evaluate.
Pred2E 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 = null);

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.

Params:

Elem[] setA	The first sorted array to evaluate.
Elem[] setB	The second sorted array to evaluate.
Pred2E 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 = null);

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.

Params:

Elem[] setA	The first sorted array to evaluate.
Elem[] setB	The second sorted array to evaluate.
Pred2E 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 = null);

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

Params:

Elem[] buf	The array to convert. This parameter is not marked 'inout' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'inout' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
Pred2E 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 = null);

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

Params:

Elem[] buf	The heap to modify. This parameter is marked 'inout' because buf.length will be altered.
Elem val	The element to push onto buf.
Pred2E 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 = null);

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.

Params:

Elem[] buf	The heap to modify. This parameter is marked 'inout' because buf.length will be altered.
Pred2E 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 = null);

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.

Params:

Elem[] buf	The heap to sort. This parameter is not marked 'inout' to allow temporary slices to be sorted. As buf is not resized in any way, omitting the 'inout' qualifier has no effect on the result of this operation, even though it may be viewed as a side-effect.
Pred2E 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.

anchorFromTitle('tango.core.Array', 'source/', 'html');