slices

All function #

All returns an iterator over index-value pairs in the slice in the usual order.

func All(s Slice) *ast.IndexListExpr

AppendSeq function #

AppendSeq appends the values from seq to the slice and returns the extended slice.

func AppendSeq(s Slice, seq *ast.IndexExpr) Slice

Backward function #

Backward returns an iterator over index-value pairs in the slice, traversing it backward with descending indices.

func Backward(s Slice) *ast.IndexListExpr

BinarySearch function #

BinarySearch searches for target in a sorted slice and returns the earliest position where target is found, or the position where target would appear in the sort order; it also returns a bool saying whether the target is really found in the slice. The slice must be sorted in increasing order.

func BinarySearch(x S, target E) (int, bool)

BinarySearchFunc function #

BinarySearchFunc works like [BinarySearch], but uses a custom comparison function. The slice must be sorted in increasing order, where "increasing" is defined by cmp. cmp should return 0 if the slice element matches the target, a negative number if the slice element precedes the target, or a positive number if the slice element follows the target. cmp must implement the same ordering as the slice, such that if cmp(a, t) < 0 and cmp(b, t) >= 0, then a must precede b in the slice.

func BinarySearchFunc(x S, target T, cmp func(E, T) int) (int, bool)

Chunk function #

Chunk returns an iterator over consecutive sub-slices of up to n elements of s. All but the last sub-slice will have size n. All sub-slices are clipped to have no capacity beyond the length. If s is empty, the sequence is empty: there is no empty slice in the sequence. Chunk panics if n is less than 1.

func Chunk(s Slice, n int) *ast.IndexExpr

Clip function #

Clip removes unused capacity from the slice, returning s[:len(s):len(s)].

func Clip(s S) S

Clone function #

Clone returns a copy of the slice. The elements are copied using assignment, so this is a shallow clone. The result may have additional unused capacity.

func Clone(s S) S

Collect function #

Collect collects values from seq into a new slice and returns it.

func Collect(seq *ast.IndexExpr) []E

Compact function #

Compact replaces consecutive runs of equal elements with a single copy. This is like the uniq command found on Unix. Compact modifies the contents of the slice s and returns the modified slice, which may have a smaller length. Compact zeroes the elements between the new length and the original length.

func Compact(s S) S

CompactFunc function #

CompactFunc is like [Compact] but uses an equality function to compare elements. For runs of elements that compare equal, CompactFunc keeps the first one. CompactFunc zeroes the elements between the new length and the original length.

func CompactFunc(s S, eq func(E, E) bool) S

Compare function #

Compare compares the elements of s1 and s2, using [cmp.Compare] on each pair of elements. The elements are compared sequentially, starting at index 0, until one element is not equal to the other. The result of comparing the first non-matching elements is returned. If both slices are equal until one of them ends, the shorter slice is considered less than the longer one. The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2.

func Compare(s1 S, s2 S) int

CompareFunc function #

CompareFunc is like [Compare] but uses a custom comparison function on each pair of elements. The result is the first non-zero result of cmp; if cmp always returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2), and +1 if len(s1) > len(s2).

func CompareFunc(s1 S1, s2 S2, cmp func(E1, E2) int) int

Concat function #

Concat returns a new slice concatenating the passed in slices.

func Concat(slices ...S) S

Contains function #

Contains reports whether v is present in s.

func Contains(s S, v E) bool

ContainsFunc function #

ContainsFunc reports whether at least one element e of s satisfies f(e).

func ContainsFunc(s S, f func(E) bool) bool

Delete function #

Delete removes the elements s[i:j] from s, returning the modified slice. Delete panics if j > len(s) or s[i:j] is not a valid slice of s. Delete is O(len(s)-i), so if many items must be deleted, it is better to make a single call deleting them all together than to delete one at a time. Delete zeroes the elements s[len(s)-(j-i):len(s)].

func Delete(s S, i int, j int) S

DeleteFunc function #

DeleteFunc removes any elements from s for which del returns true, returning the modified slice. DeleteFunc zeroes the elements between the new length and the original length.

func DeleteFunc(s S, del func(E) bool) S

Equal function #

Equal reports whether two slices are equal: the same length and all elements equal. If the lengths are different, Equal returns false. Otherwise, the elements are compared in increasing index order, and the comparison stops at the first unequal pair. Empty and nil slices are considered equal. Floating point NaNs are not considered equal.

func Equal(s1 S, s2 S) bool

EqualFunc function #

EqualFunc reports whether two slices are equal using an equality function on each pair of elements. If the lengths are different, EqualFunc returns false. Otherwise, the elements are compared in increasing index order, and the comparison stops at the first index for which eq returns false.

func EqualFunc(s1 S1, s2 S2, eq func(E1, E2) bool) bool

Grow function #

Grow increases the slice's capacity, if necessary, to guarantee space for another n elements. After Grow(n), at least n elements can be appended to the slice without another allocation. If n is negative or too large to allocate the memory, Grow panics.

func Grow(s S, n int) S

Index function #

Index returns the index of the first occurrence of v in s, or -1 if not present.

func Index(s S, v E) int

IndexFunc function #

IndexFunc returns the first index i satisfying f(s[i]), or -1 if none do.

func IndexFunc(s S, f func(E) bool) int

Insert function #

Insert inserts the values v... into s at index i, returning the modified slice. The elements at s[i:] are shifted up to make room. In the returned slice r, r[i] == v[0], and, if i < len(s), r[i+len(v)] == value originally at r[i]. Insert panics if i > len(s). This function is O(len(s) + len(v)).

func Insert(s S, i int, v ...E) S

IsSorted function #

IsSorted reports whether x is sorted in ascending order.

func IsSorted(x S) bool

IsSortedFunc function #

IsSortedFunc reports whether x is sorted in ascending order, with cmp as the comparison function as defined by [SortFunc].

func IsSortedFunc(x S, cmp func(a E, b E) int) bool

Max function #

Max returns the maximal value in x. It panics if x is empty. For floating-point E, Max propagates NaNs (any NaN value in x forces the output to be NaN).

func Max(x S) E

MaxFunc function #

MaxFunc returns the maximal value in x, using cmp to compare elements. It panics if x is empty. If there is more than one maximal element according to the cmp function, MaxFunc returns the first one.

func MaxFunc(x S, cmp func(a E, b E) int) E

Min function #

Min returns the minimal value in x. It panics if x is empty. For floating-point numbers, Min propagates NaNs (any NaN value in x forces the output to be NaN).

func Min(x S) E

MinFunc function #

MinFunc returns the minimal value in x, using cmp to compare elements. It panics if x is empty. If there is more than one minimal element according to the cmp function, MinFunc returns the first one.

func MinFunc(x S, cmp func(a E, b E) int) E

Next method #

func (r *xorshift) Next() uint64

Repeat function #

Repeat returns a new slice that repeats the provided slice the given number of times. The result has length and capacity (len(x) * count). The result is never nil. Repeat panics if count is negative or if the result of (len(x) * count) overflows.

func Repeat(x S, count int) S

Replace function #

Replace replaces the elements s[i:j] by the given v, and returns the modified slice. Replace panics if j > len(s) or s[i:j] is not a valid slice of s. When len(v) < (j-i), Replace zeroes the elements between the new length and the original length.

func Replace(s S, i int, j int, v ...E) S

Reverse function #

Reverse reverses the elements of the slice in place.

func Reverse(s S)

Sort function #

Sort sorts a slice of any ordered type in ascending order. When sorting floating-point numbers, NaNs are ordered before other values.

func Sort(x S)

SortFunc function #

SortFunc sorts the slice x in ascending order as determined by the cmp function. This sort is not guaranteed to be stable. cmp(a, b) should return a negative number when a < b, a positive number when a > b and zero when a == b or a and b are incomparable in the sense of a strict weak ordering. SortFunc requires that cmp is a strict weak ordering. See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings. The function should return 0 for incomparable items.

func SortFunc(x S, cmp func(a E, b E) int)

SortStableFunc function #

SortStableFunc sorts the slice x while keeping the original order of equal elements, using cmp to compare elements in the same way as [SortFunc].

func SortStableFunc(x S, cmp func(a E, b E) int)

Sorted function #

Sorted collects values from seq into a new slice, sorts the slice, and returns it.

func Sorted(seq *ast.IndexExpr) []E

SortedFunc function #

SortedFunc collects values from seq into a new slice, sorts the slice using the comparison function, and returns it.

func SortedFunc(seq *ast.IndexExpr, cmp func(E, E) int) []E

SortedStableFunc function #

SortedStableFunc collects values from seq into a new slice. It then sorts the slice while keeping the original order of equal elements, using the comparison function to compare elements. It returns the new slice.

func SortedStableFunc(seq *ast.IndexExpr, cmp func(E, E) int) []E

Values function #

Values returns an iterator that yields the slice elements in order.

func Values(s Slice) *ast.IndexExpr

breakPatternsCmpFunc function #

breakPatternsCmpFunc scatters some elements around in an attempt to break some patterns that might cause imbalanced partitions in quicksort.

func breakPatternsCmpFunc(data []E, a int, b int, cmp func(a E, b E) int)

breakPatternsOrdered function #

breakPatternsOrdered scatters some elements around in an attempt to break some patterns that might cause imbalanced partitions in quicksort.

func breakPatternsOrdered(data []E, a int, b int)

choosePivotCmpFunc function #

choosePivotCmpFunc chooses a pivot in data[a:b]. [0,8): chooses a static pivot. [8,shortestNinther): uses the simple median-of-three method. [shortestNinther,∞): uses the Tukey ninther method.

func choosePivotCmpFunc(data []E, a int, b int, cmp func(a E, b E) int) (pivot int, hint sortedHint)

choosePivotOrdered function #

choosePivotOrdered chooses a pivot in data[a:b]. [0,8): chooses a static pivot. [8,shortestNinther): uses the simple median-of-three method. [shortestNinther,∞): uses the Tukey ninther method.

func choosePivotOrdered(data []E, a int, b int) (pivot int, hint sortedHint)

heapSortCmpFunc function #

func heapSortCmpFunc(data []E, a int, b int, cmp func(a E, b E) int)

heapSortOrdered function #

func heapSortOrdered(data []E, a int, b int)

insertionSortCmpFunc function #

insertionSortCmpFunc sorts data[a:b] using insertion sort.

func insertionSortCmpFunc(data []E, a int, b int, cmp func(a E, b E) int)

insertionSortOrdered function #

insertionSortOrdered sorts data[a:b] using insertion sort.

func insertionSortOrdered(data []E, a int, b int)

isNaN function #

isNaN reports whether x is a NaN without requiring the math package. This will always return false if T is not floating-point.

func isNaN(x T) bool

medianAdjacentCmpFunc function #

medianAdjacentCmpFunc finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.

func medianAdjacentCmpFunc(data []E, a int, swaps *int, cmp func(a E, b E) int) int

medianAdjacentOrdered function #

medianAdjacentOrdered finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.

func medianAdjacentOrdered(data []E, a int, swaps *int) int

medianCmpFunc function #

medianCmpFunc returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.

func medianCmpFunc(data []E, a int, b int, c int, swaps *int, cmp func(a E, b E) int) int

medianOrdered function #

medianOrdered returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.

func medianOrdered(data []E, a int, b int, c int, swaps *int) int

nextPowerOfTwo function #

func nextPowerOfTwo(length int) uint

order2CmpFunc function #

order2CmpFunc returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.

func order2CmpFunc(data []E, a int, b int, swaps *int, cmp func(a E, b E) int) (int, int)

order2Ordered function #

order2Ordered returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.

func order2Ordered(data []E, a int, b int, swaps *int) (int, int)

overlaps function #

overlaps reports whether the memory ranges a[:len(a)] and b[:len(b)] overlap.

func overlaps(a []E, b []E) bool

partialInsertionSortCmpFunc function #

partialInsertionSortCmpFunc partially sorts a slice, returns true if the slice is sorted at the end.

func partialInsertionSortCmpFunc(data []E, a int, b int, cmp func(a E, b E) int) bool

partialInsertionSortOrdered function #

partialInsertionSortOrdered partially sorts a slice, returns true if the slice is sorted at the end.

func partialInsertionSortOrdered(data []E, a int, b int) bool

partitionCmpFunc function #

partitionCmpFunc does one quicksort partition. Let p = data[pivot] Moves elements in data[a:b] around, so that data[i]

=p for inewpivot. On return, data[newpivot] = p

func partitionCmpFunc(data []E, a int, b int, pivot int, cmp func(a E, b E) int) (newpivot int, alreadyPartitioned bool)

partitionEqualCmpFunc function #

partitionEqualCmpFunc partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot]. It assumed that data[a:b] does not contain elements smaller than the data[pivot].

func partitionEqualCmpFunc(data []E, a int, b int, pivot int, cmp func(a E, b E) int) (newpivot int)

partitionEqualOrdered function #

partitionEqualOrdered partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot]. It assumed that data[a:b] does not contain elements smaller than the data[pivot].

func partitionEqualOrdered(data []E, a int, b int, pivot int) (newpivot int)

partitionOrdered function #

partitionOrdered does one quicksort partition. Let p = data[pivot] Moves elements in data[a:b] around, so that data[i]

=p for inewpivot. On return, data[newpivot] = p

func partitionOrdered(data []E, a int, b int, pivot int) (newpivot int, alreadyPartitioned bool)

pdqsortCmpFunc function #

pdqsortCmpFunc sorts data[a:b]. The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf C++ implementation: https://github.com/orlp/pdqsort Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.

func pdqsortCmpFunc(data []E, a int, b int, limit int, cmp func(a E, b E) int)

pdqsortOrdered function #

pdqsortOrdered sorts data[a:b]. The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf C++ implementation: https://github.com/orlp/pdqsort Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.

func pdqsortOrdered(data []E, a int, b int, limit int)

reverseRangeCmpFunc function #

func reverseRangeCmpFunc(data []E, a int, b int, cmp func(a E, b E) int)

reverseRangeOrdered function #

func reverseRangeOrdered(data []E, a int, b int)

rotateCmpFunc function #

rotateCmpFunc rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data: Data of the form 'x u v y' is changed to 'x v u y'. rotate performs at most b-a many calls to data.Swap, and it assumes non-degenerate arguments: a < m && m < b.

func rotateCmpFunc(data []E, a int, m int, b int, cmp func(a E, b E) int)

rotateLeft function #

rotateLeft rotates s left by r spaces. s_final[i] = s_orig[i+r], wrapping around.

func rotateLeft(s []E, r int)

rotateOrdered function #

rotateOrdered rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data: Data of the form 'x u v y' is changed to 'x v u y'. rotate performs at most b-a many calls to data.Swap, and it assumes non-degenerate arguments: a < m && m < b.

func rotateOrdered(data []E, a int, m int, b int)

rotateRight function #

func rotateRight(s []E, r int)

siftDownCmpFunc function #

siftDownCmpFunc implements the heap property on data[lo:hi]. first is an offset into the array where the root of the heap lies.

func siftDownCmpFunc(data []E, lo int, hi int, first int, cmp func(a E, b E) int)

siftDownOrdered function #

siftDownOrdered implements the heap property on data[lo:hi]. first is an offset into the array where the root of the heap lies.

func siftDownOrdered(data []E, lo int, hi int, first int)

stableCmpFunc function #

func stableCmpFunc(data []E, n int, cmp func(a E, b E) int)

stableOrdered function #

func stableOrdered(data []E, n int)

startIdx function #

startIdx returns the index in haystack where the needle starts. prerequisite: the needle must be aliased entirely inside the haystack.

func startIdx(haystack []E, needle []E) int

swapRangeCmpFunc function #

func swapRangeCmpFunc(data []E, a int, b int, n int, cmp func(a E, b E) int)

swapRangeOrdered function #

func swapRangeOrdered(data []E, a int, b int, n int)

symMergeCmpFunc function #

symMergeCmpFunc merges the two sorted subsequences data[a:m] and data[m:b] using the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in Computer Science, pages 714-723. Springer, 2004. Let M = m-a and N = b-n. Wolog M < N. The recursion depth is bound by ceil(log(N+M)). The algorithm needs O(M*log(N/M + 1)) calls to data.Less. The algorithm needs O((M+N)*log(M)) calls to data.Swap. The paper gives O((M+N)*log(M)) as the number of assignments assuming a rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation in the paper carries through for Swap operations, especially as the block swapping rotate uses only O(M+N) Swaps. symMerge assumes non-degenerate arguments: a < m && m < b. Having the caller check this condition eliminates many leaf recursion calls, which improves performance.

func symMergeCmpFunc(data []E, a int, m int, b int, cmp func(a E, b E) int)

symMergeOrdered function #

symMergeOrdered merges the two sorted subsequences data[a:m] and data[m:b] using the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in Computer Science, pages 714-723. Springer, 2004. Let M = m-a and N = b-n. Wolog M < N. The recursion depth is bound by ceil(log(N+M)). The algorithm needs O(M*log(N/M + 1)) calls to data.Less. The algorithm needs O((M+N)*log(M)) calls to data.Swap. The paper gives O((M+N)*log(M)) as the number of assignments assuming a rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation in the paper carries through for Swap operations, especially as the block swapping rotate uses only O(M+N) Swaps. symMerge assumes non-degenerate arguments: a < m && m < b. Having the caller check this condition eliminates many leaf recursion calls, which improves performance.

func symMergeOrdered(data []E, a int, m int, b int)