Documentation
¶
Overview ¶
Package serial implements a number of algorithms from the C++ Standard Template Library. While that library has an "iterator" abstraction, this concept has proven extremely hard to efficiently replicate in Go. Consequently, all the algorithms are implemented on top of slices. Some additional functions have been introduced to deal with the fact that Go does not have function overloading or default arguments.
The goal is to reimplement all the C++ STL algorithms in this library. Currently, most of them are available. A few of the more complex algorithms, like nth_element are still pending.
Most of the algorithms have basic tests ensuring that they function correctly. Eventually I would like to have 100% code line test coverage of all the serial algorithms, and some tests for bad edge cases and performance cliffs.
If you are interested in helping, please feel free to implement an algorithm, a test for the algorithm, and open a pull request against this repo. Or if you just want to write tests, that would also be appreciated!
Index ¶
- func AllOf[T comparable](collection []T, value T) bool
- func AllOfIf[T comparable](collection []T, pred common.Predicate[T]) bool
- func AnyOf[T comparable](collection []T, value T) bool
- func AnyOfIf[T comparable](collection []T, pred common.Predicate[T]) bool
- func Clamp[T constraints.Ordered](value, lower, upper T) T
- func Compare[T constraints.Ordered](x, y []T) int
- func Contains[T comparable](collection []T, value T) bool
- func ContainsIf[T comparable](collection []T, pred common.Predicate[T]) bool
- func Copy[T comparable](srcCollection []T, dstCollection []T)
- func CopyAppendIf[T comparable](srcCollection []T, pred common.Predicate[T]) []T
- func CopyIf[T comparable](srcCollection []T, dstCollection []T, pred common.Predicate[T]) int
- func Count[T comparable](collection []T, value T) int
- func CountIf[T comparable](collection []T, pred common.Predicate[T]) int
- func Fill[T any](collection []T, value T) []T
- func Find[T comparable](collection []T, value T) int
- func FindIf[T comparable](collection []T, pred common.Predicate[T]) int
- func FindIfNot[T comparable](collection []T, pred common.Predicate[T]) int
- func FindNot[T comparable](collection []T, value T) int
- func ForEach[T any](collection []T, op common.UnaryOp[T])
- func Generate[T any](collection []T, g common.Generator[T]) []T
- func HeapSort[T constraints.Ordered](collection []T)
- func InsertionSort[T constraints.Ordered](collection []T)
- func IntroSort[T constraints.Ordered](collection []T)
- func IntroSortWithDepth[T constraints.Ordered](collection []T, maxDepth int)
- func Iota[T constraints.Integer](collection []T) []T
- func IotaN[T constraints.Integer](count int) []T
- func IotaNWithStart[T constraints.Integer](count int, start T) []T
- func IotaWithStart[T constraints.Integer](collection []T, start T) []T
- func MakeHeap[T constraints.Ordered](collection []T) []T
- func Max[T constraints.Ordered](v1, v2 T) T
- func MaxElement[T constraints.Ordered](collection []T) int
- func Min[T constraints.Ordered](v1, v2 T) T
- func MinElement[T constraints.Ordered](collection []T) int
- func MinMaxElement[T constraints.Ordered](collection []T) (int, int)
- func Mismatch[T comparable](collection1, collection2 []T) int
- func NoneOf[T comparable](collection []T, value T) bool
- func NoneOfIf[T comparable](collection []T, pred common.Predicate[T]) bool
- func Partition[T comparable](collection []T, pred common.Predicate[T]) int
- func RandomShuffle[T comparable](collection []T) []T
- func Remove[T comparable](collection []T, value T) []T
- func RemoveIf[T comparable](collection []T, pred common.Predicate[T]) []T
- func Replace[T comparable](collection []T, old_value, new_value T) int
- func ReplaceIf[T comparable](collection []T, pred common.Predicate[T], new_value T) int
- func Reverse[T any](collection []T) []T
- func ReverseCopy[T any](collection []T) []T
- func Rotate[T any](collection []T, nFirst int) int
- func RotateRange[T any](collection []T, first, nFirst, last int) int
- func Sort[T constraints.Ordered](collection []T) []T
- func Swap[T any](i1, i2 *T)
- func SwapIndex[T any](collection []T, i1, i2 int)
- func Transform[T1, T2 any](srcCollection []T1, dstCollection []T2, unary common.UnaryTransform[T1, T2]) []T2
- func TransformAppend[T1, T2 any](srcCollection []T1, unary common.UnaryTransform[T1, T2]) []T2
- func TransformAppendIf[T1, T2 any](srcCollection []T1, pred common.Predicate[T1], unary ...) []T2
- func TransformCopyIf[T any](srcCollection []T, dstCollection []T, pred common.Predicate[T], unary ...) []T
- func TransformIf[T1, T2 any](srcCollection []T1, dstCollection []T2, pred common.Predicate[T1], unary ...) []T2
- func Unique[T comparable](collection []T) []T
- func UniqueIf[T any](collection []T, pred common.BinaryPredicate[T]) []T
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AllOf ¶
func AllOf[T comparable](collection []T, value T) bool
AllOf returns true if all the elements in the collection are equal to value.
func AllOfIf ¶
func AllOfIf[T comparable](collection []T, pred common.Predicate[T]) bool
AllOfIf returns true if all the elements in the collection return true for pred.
func AnyOf ¶
func AnyOf[T comparable](collection []T, value T) bool
AnyOf returns true if any of the elements in the collection are equal to value.
func AnyOfIf ¶
func AnyOfIf[T comparable](collection []T, pred common.Predicate[T]) bool
AnyOfIf returns true if any of the elements in the collection return true for pred.
func Clamp ¶
func Clamp[T constraints.Ordered](value, lower, upper T) T
Clamp returns the value clamped to a range. If value is less than lower, lower is returned. If value is greater than upper, upper is returned. Otherwise value is returned.
func Compare ¶
func Compare[T constraints.Ordered](x, y []T) int
func Contains ¶
func Contains[T comparable](collection []T, value T) bool
Contains returns true if value is in collection.
func ContainsIf ¶
func ContainsIf[T comparable](collection []T, pred common.Predicate[T]) bool
ContainsIf returns true if any element in collection returns true for pred.
func Copy ¶
func Copy[T comparable](srcCollection []T, dstCollection []T)
Copy copies all items in srcCollection to dstCollection.
func CopyAppendIf ¶
func CopyAppendIf[T comparable](srcCollection []T, pred common.Predicate[T]) []T
CopyAppendIf copies items from srcCollection that match the given predicate. The items are copied to a new collection. The return value is a collection of items that match the predicate
func CopyIf ¶
func CopyIf[T comparable](srcCollection []T, dstCollection []T, pred common.Predicate[T]) int
CopyIf copies items from srcCollection that match the given predicate. dstCollection must have space for at most the same number of items as srcCollection. If you know a priori how big the destination collection must be, this will more efficient than CopyAppendIf.
func Count ¶
func Count[T comparable](collection []T, value T) int
Count counts the number of occurrences of value in collection.
func CountIf ¶
func CountIf[T comparable](collection []T, pred common.Predicate[T]) int
CountIf counts the number of elements for which pred returns true in collection.
func Fill ¶
func Fill[T any](collection []T, value T) []T
Fill fills every element of collection with value.
func Find ¶
func Find[T comparable](collection []T, value T) int
Find locates the index of first occurrence of value in collection. If the value is not present it returns -1.
func FindIf ¶
func FindIf[T comparable](collection []T, pred common.Predicate[T]) int
FindIf locates the index of the first element for which pred returns true. If no element returns true for pred the function returns -1.
func FindIfNot ¶
func FindIfNot[T comparable](collection []T, pred common.Predicate[T]) int
FindIfNot locates the index of the first element for which pred returns false. If no element returns false for pred the function returns -1.
func FindNot ¶
func FindNot[T comparable](collection []T, value T) int
FindNot locates the index of first element in collection that is not equal to value. If the value is not present it returns -1.
func HeapSort ¶
func HeapSort[T constraints.Ordered](collection []T)
HeapSort sorts the collection using the heap sort algorithm.
func InsertionSort ¶
func InsertionSort[T constraints.Ordered](collection []T)
InsertionSort sorts the collection using the insertion sort algorithm.
func IntroSort ¶
func IntroSort[T constraints.Ordered](collection []T)
IntroSort sorts the collection in ascending order using the introsort algorithm and a default depth for recursion bail-out.
func IntroSortWithDepth ¶
func IntroSortWithDepth[T constraints.Ordered](collection []T, maxDepth int)
IntroSortWithDepth sorts the collection using the introsort algorithm. The maxDepth parameter is an indication of how many deep the recursion can go before bailing out and falling back to heap sort. This prevents the worst case behavior of quicksort. Normally that should be set to int(math.Log2(float64(len(collection)))) * 2, which is what the IntroSort function sets it to. It shouldn't be larger than that, but it may be less if you want to fall back to heap sort sooner.
func Iota ¶
func Iota[T constraints.Integer](collection []T) []T
Iota fills collection with monotonically increasing integers starting from 0.
func IotaN ¶
func IotaN[T constraints.Integer](count int) []T
IotaN fills a collection with N monotonically increasing integers starting from 0.
func IotaNWithStart ¶
func IotaNWithStart[T constraints.Integer](count int, start T) []T
IotaNWithStart fills a collection with N monotonically increasing integers starting from 0.
func IotaWithStart ¶
func IotaWithStart[T constraints.Integer](collection []T, start T) []T
IotaWithStart fills a collection with monotonically increasing integers starting at start.
func MakeHeap ¶
func MakeHeap[T constraints.Ordered](collection []T) []T
MakeHeap turns the collection into a heap, in place.
func Max ¶
func Max[T constraints.Ordered](v1, v2 T) T
Max returns the greater of the two values, or the first value if they are the same.
func MaxElement ¶
func MaxElement[T constraints.Ordered](collection []T) int
MaxElement finds the index of the first occurrence of the largest item in the collection.
func Min ¶
func Min[T constraints.Ordered](v1, v2 T) T
Min returns the lesser of the two values, or the first value if they are the same.
func MinElement ¶
func MinElement[T constraints.Ordered](collection []T) int
MinElement finds the index of the first occurrence of the smallest item in the collection.
func MinMaxElement ¶
func MinMaxElement[T constraints.Ordered](collection []T) (int, int)
MinMaxElement finds the index of the first occurrence of the smallest and largest items in the collection. Returns a tuple of (min_index, max_index).
func Mismatch ¶
func Mismatch[T comparable](collection1, collection2 []T) int
Mismatch returns the first mismatching pair of elements from two slices. The return value is the first index in collection1 that does not match the same index in collection2.
func NoneOf ¶
func NoneOf[T comparable](collection []T, value T) bool
NoneOf returns true if none of the elements in the collection are equal to value.
func NoneOfIf ¶
func NoneOfIf[T comparable](collection []T, pred common.Predicate[T]) bool
NoneOfIf returns true if none of the elements in the collection return true for pred.
func Partition ¶
func Partition[T comparable](collection []T, pred common.Predicate[T]) int
Partition reorders the elements in the range [first, last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false. Relative order of the elements is not preserved. The return value is the index to the first element of the second group.
func RandomShuffle ¶
func RandomShuffle[T comparable](collection []T) []T
RandomShuffle reorders the elements in the given collection such that each possible permutation of those elements has equal probability of appearance.
func Remove ¶
func Remove[T comparable](collection []T, value T) []T
Remove removes all elements that are equal to value. Returns a new slice with items removed.
func RemoveIf ¶
func RemoveIf[T comparable](collection []T, pred common.Predicate[T]) []T
RemoveIf removes all elements where pred returns true. Returns a new slice with items removed.
func Replace ¶
func Replace[T comparable](collection []T, old_value, new_value T) int
Replace replaces all elements that are equal to old_value with new_value. Returns the number of replacements made.
func ReplaceIf ¶
func ReplaceIf[T comparable](collection []T, pred common.Predicate[T], new_value T) int
ReplaceIf replaces all elements where pred is true with new_value. Returns the number of replacements made.
func Reverse ¶
func Reverse[T any](collection []T) []T
Reverse reverses the order of the elements in the collection. Behaves as if applying SwapIndex to every pair of iterators first+i, (last-i) - 1 for each non-negative i < (last-first)/2. Returns the collection passed in.
func ReverseCopy ¶
func ReverseCopy[T any](collection []T) []T
ReverseCopy performs the same operation as Reverse, but does it on a copy instead of doing it in place. Returns a reversed copy of the input.
func Rotate ¶
Rotate swaps the elements in the collection in such a way that the element nFirst becomes the first element of the new collection and nFirst - 1 becomes the last element.
func RotateRange ¶
RotateRange swaps the elements in the range [first, last) in such a way that the element nFirst becomes the first element of the new range and nFirst - 1 becomes the last element. A precondition of this function is that [first, nFirst) and [nFirst, last) are valid ranges.
func Sort ¶
func Sort[T constraints.Ordered](collection []T) []T
Sort sorts the collection in ascending order.
func Transform ¶
func Transform[T1, T2 any](srcCollection []T1, dstCollection []T2, unary common.UnaryTransform[T1, T2]) []T2
Transform transforms all items in srcCollection to items in dstCollection. dstCollection must be at least as big as srcCollection.
func TransformAppend ¶
func TransformAppend[T1, T2 any](srcCollection []T1, unary common.UnaryTransform[T1, T2]) []T2
TransformAppend transforms all items in srcCollection to items in dstCollection. dstCollection must be at least as big as srcCollection.
func TransformAppendIf ¶
func TransformAppendIf[T1, T2 any](srcCollection []T1, pred common.Predicate[T1], unary common.UnaryTransform[T1, T2]) []T2
TransformAppendIf transforms all items in srcCollection that match the given predicate. Transformed items are appended to a new collection. The return value is the collection of all transformed items.
func TransformCopyIf ¶
func TransformCopyIf[T any](srcCollection []T, dstCollection []T, pred common.Predicate[T], unary common.UnaryTransform[T, T]) []T
TransformCopyIf transforms all items in srcCollection that match the given predicate. Items which don't match are just copied. dstCollection must be at least as large as srcCollection. The return value indicates how many items were transformed.
func TransformIf ¶
func TransformIf[T1, T2 any](srcCollection []T1, dstCollection []T2, pred common.Predicate[T1], unary common.UnaryTransform[T1, T2]) []T2
TransformIf transforms all items in srcCollection that match the given predicate. dstCollection must be at least as large as srcCollection. The return value indicates how many items werre copied.
func Unique ¶
func Unique[T comparable](collection []T) []T
Unique eliminates all except the first element from every consecutive group of equivalent elements from the collection.
func UniqueIf ¶
func UniqueIf[T any](collection []T, pred common.BinaryPredicate[T]) []T
UniqueIf eliminates all except the first element from every consecutive group of equivalent elements from the collection. Elements are compared using a binary predicate.
Types ¶
This section is empty.
Source Files