stl4go

package module
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 11, 2022 License: Apache-2.0 Imports: 9 Imported by: 2

README

stl4go -- STL for Golang

English | 简体中文

This library contains generic containers and algorithms, it is designed to be STL for Golang.

License Apache 2.0 Python Build Status Coverage Status GoReport

This library depends on go generics, which is introduced in 1.18+.

stl4go

import "github.com/chen3feng/stl4go"

Package stl4go is a generic container and algorithm library for go.

Index

func AllOf

func AllOf[T any](a []T, pred func(T) bool) bool

AllOf return true if pred(e) returns true for all emements e in a.

Complexity: O(len(a)).

func AnyOf

func AnyOf[T any](a []T, pred func(T) bool) bool

AnyOf return true if pred(e) returns true for any emements e in a.

Complexity: O(len(a)).

func Average

func Average[T Numeric](a []T) T

Average returns the average value of a.

func AverageAs

func AverageAs[R, T Numeric](a []T) R

AverageAs returns the average value of a as type R.

func BinarySearch

func BinarySearch[T Ordered](a []T, value T) (index int, ok bool)

BinarySearch returns the (index, true) to the first element in the ascending ordered slice a such that element == value, or (-1, false) if no such element is found.

Complexity: O(log(len(a))).

func BinarySearchFunc

func BinarySearchFunc[T any](a []T, value T, less LessFn[T]) (index int, ok bool)

BinarySearchFunc returns the (index, true) to the first element in the ordered slice a such that less(element, value) and less(value, element) are both false, or (-1, false) if no such element is found.

The elements in the slice a should sorted according with compare func less.

Complexity: O(log(len(a))).

func Compare

func Compare[E Ordered](a, b []E) int

Compare compares each elements in a and b.

return 0 if they are equals, return 1 if a > b, return -1 if a < b.

Complexity: O(min(len(a), len(b))).

func Copy

func Copy[T any](a []T) []T

Copy make a copy of slice a.

Complexity: O(len(a)).

func Count

func Count[T comparable](a []T, x T) int

Count returns the number of elements in the slice equals to x.

Complexity: O(len(a)).

func CountIf

func CountIf[T comparable](a []T, pred func(T) bool) int

CountIf returns the number of elements in the slice which pred returns true.

Complexity: O(len(a)).

func DescSort

func DescSort[T Ordered](a []T)

DescSort sorts data in descending order. The order of equal elements is not guaranteed to be preserved.

Complexity: O(N*log(N)), N=len(a).

func DescStableSort

func DescStableSort[T Ordered](a []T)

DescStableSort sorts data in descending order stably. The order of equivalent elements is guaranteed to be preserved.

Complexity: O(N*log(N)), N=len(a).

func Equal

func Equal[T comparable](a, b []T) bool

Equal returns whether two slices are equal. Return true if they are the same length and all elements are equal.

Complexity: O(min(len(a), len(b))).

func Equals

func Equals[T comparable](a, b T) bool

Equals wraps the '==' operator for comparable types.

func Find

func Find[T comparable](a []T, x T) (index int, ok bool)

Find find the first value x in the given slice a linearly. return (index, true) if found, return (_, false) if not found.

Complexity: O(len(a)).

func FindIf

func FindIf[T any](a []T, cond func(T) bool) (index int, ok bool)

FindIf find the first value x satisfying function cond in the given slice a linearly. return (index, true) if found, return (_, false) if not found.

Complexity: O(len(a)).

func Generate

func Generate[T any](a []T, gen func() T)

Generate fill each element of `a`` with `gen()`.

Complexity: O(len(a)).

func Index

func Index[T comparable](a []T, x T) int

Index find the value x in the given slice a linearly.

Return index if found, -1 if not found.

Complexity: O(len(a)).

func IsDescSorted

func IsDescSorted[T Ordered](a []T) bool

IsDescSorted returns whether the slice a is sorted in descending order.

Complexity: O(len(a)).

func IsSorted

func IsSorted[T Ordered](a []T) bool

IsSorted returns whether the slice a is sorted in ascending order.

Complexity: O(len(a)).

func Less

func Less[T Ordered](a, b T) bool

Less wraps the '<' operator for ordered types.

func LowerBound

func LowerBound[T Ordered](a []T, value T) int

LowerBound returns an index to the first element in the ascending ordered slice a that does not satisfy element < value (i.e. greater or equal to), or len(a) if no such element is found.

Complexity: O(log(len(a))).

func LowerBoundFunc

func LowerBoundFunc[T any](a []T, value T, less LessFn[T]) int

LowerBoundFunc returns an index to the first element in the ordered slice a that does not satisfy less(element, value)), or len(a) if no such element is found.

The elements in the slice a should sorted according with compare func less.

Complexity: O(log(len(a))).

func Max

func Max[T Ordered](a, b T) T

Max return the larger value between `a` and `b`.

Complexity: O(1).

func MaxN

func MaxN[T Ordered](a ...T) T

MaxN return the maximum value in the sequence `a`.

Complexity: O(len(a)).

func Min

func Min[T Ordered](a, b T) T

Min return the smaller value between `a` and `b`.

Complexity: O(1).

func MinMax

func MinMax[T Ordered](a, b T) (min, max T)

MinMax returns both min and max between a and b.

Complexity: O(1).

func MinMaxN

func MinMaxN[T Ordered](a ...T) (min, max T)

MinMaxN returns both min and max in slice a.

Complexity: O(len(a))

func MinN

func MinN[T Ordered](a ...T) T

MinN return the minimum value in the sequence `a`.

Complexity: O(len(a)).

func NoneOf

func NoneOf[T any](a []T, pred func(T) bool) bool

NoneOf return true pred(e) returns true for none emements e in a.

Complexity: O(len(a)).

func OrderedCompare

func OrderedCompare[T Ordered](a, b T) int

OrderedCompare provide default CompareFn for ordered types.

func Range

func Range[T Numeric](first, last T) []T

Range make a []T filled with values in the `[first, last)` sequence. NOTE: the last is not included in the result.

Complexity: O(last-first).

func Remove

func Remove[T comparable](a []T, x T) []T

Remove remove the elements which equals to x from the input slice. return the processed slice, and the content of the input slice is also changed.

Complexity: O(len(a)).

func RemoveCopy

func RemoveCopy[T comparable](a []T, x T) []T

RemoveCopy remove all elements which equals to x from the input slice. return the processed slice, and the content of the input slice is also changed.

Complexity: O(len(a)).

func RemoveIf

func RemoveIf[T any](a []T, cond func(T) bool) []T

RemoveIf remove each element which make cond(x) returns true from the input slice, copy other elements to a new slice and return it. The input slice is kept unchanged.

Complexity: O(len(a)).

func RemoveIfCopy

func RemoveIfCopy[T any](a []T, cond func(T) bool) []T

RemoveIfCopy drops each element which make cond(x) returns true from the input slice, copy other elements to a new slice and return it. The input slice is kept unchanged.

Complexity: O(len(a)).

func Reverse

func Reverse[T any](a []T)

Reverse reverses the order of the elements in the slice a.

Complexity: O(len(a)).

func ReverseCopy

func ReverseCopy[T any](a []T) []T

ReverseCopy returns a reversed copy of slice a.

Complexity: O(len(a)).

func Shuffle

func Shuffle[T any](a []T)

Shuffle pseudo-randomizes the order of elements.

Complexity: O(len(a)).

func Sort

func Sort[T Ordered](a []T)

Sort sorts data in ascending order. The order of equal elements is not guaranteed to be preserved.

Complexity: O(N*log(N)), where N=len(a).

func SortFunc

func SortFunc[T any](a []T, less func(x, y T) bool)

SortFunc sorts data in ascending order with compare func less. The order of equal elements is not guaranteed to be preserved.

Complexity: O(N*log(N)), N=len(a).

func StableSort

func StableSort[T Ordered](a []T)

StableSort sorts data in ascending order stably. The order of equivalent elements is guaranteed to be preserved.

Complexity: O(N*log(N)^2), where N=len(a).

func StableSortFunc

func StableSortFunc[T any](a []T, less func(x, y T) bool)

StableSortFunc sorts data in ascending order with compare func less stably. The order of equivalent elements is guaranteed to be preserved.

Complexity: O(N*log(N)), N=len(a).

func Sum

func Sum[T Numeric](a []T) T

Sum summarize all elements in a. returns the result as type R, you should use SumAs if T can't hold the result. Complexity: O(len(a)).

func SumAs

func SumAs[R, T Numeric](a []T) R

SumAs summarize all elements in a. returns the result as type R, this is useful when T is too small to hold the result. Complexity: O(len(a)).

func Transform

func Transform[T any](a []T, op func(T) T)

Transform applies the function op to each element in slice a and set it back to the same place in a.

Complexity: O(len(a)).

func TransformCopy

func TransformCopy[R any, T any](a []T, op func(T) R) []R

TransformCopy applies the function op to each element in slice a and return all the result as a slice.

Complexity: O(len(a)).

func TransformTo

func TransformTo[R any, T any](a []T, op func(T) R, b []R)

TransformTo applies the function op to each element in slice a and fill it to slice b.

The len(b) must not lesser than len(a).

Complexity: O(len(a)).

func Unique

func Unique[T comparable](a []T) []T

Unique remove adjacent repeated elements from the input slice. return the processed slice, and the content of the input slice is also changed.

Complexity: O(len(a)).

func UniqueCopy

func UniqueCopy[T comparable](a []T) []T

UniqueCopy remove adjacent repeated elements from the input slice. return the result slice, and the input slice is kept unchanged.

Complexity: O(len(a)).

func UpperBound

func UpperBound[T Ordered](a []T, value T) int

UpperBound returns an index to the first element in the ascending ordered slice a such that value < element (i.e. strictly greater), or len(a) if no such element is found.

Complexity: O(log(len(a))).

func UpperBoundFunc

func UpperBoundFunc[T any](a []T, value T, less LessFn[T]) int

UpperBoundFunc returns an index to the first element in the ordered slice a such that less(value, element)) is true (i.e. strictly greater), or len(a) if no such element is found.

The elements in the slice a should sorted according with compare func less.

Complexity: O(log(len(a))).

type BuiltinSet

BuiltinSet is an associative container that contains a unordered set of unique objects of type K.

type BuiltinSet[K comparable] map[K]bool
func MakeBuiltinSetOf
func MakeBuiltinSetOf[K comparable](ks ...K) BuiltinSet[K]

MakeBuiltinSetOf creates a new BuiltinSet object with the initial content from ks.

func (*BuiltinSet[K]) Clear
func (s *BuiltinSet[K]) Clear()
func (*BuiltinSet[K]) ForEach
func (s *BuiltinSet[K]) ForEach(cb func(k K))
func (*BuiltinSet[K]) ForEachIf
func (s *BuiltinSet[K]) ForEachIf(cb func(k K) bool)
func (*BuiltinSet[K]) Has
func (s *BuiltinSet[K]) Has(k K) bool
func (*BuiltinSet[K]) Insert
func (s *BuiltinSet[K]) Insert(k K)
func (*BuiltinSet[K]) InsertN
func (s *BuiltinSet[K]) InsertN(ks ...K)
func (*BuiltinSet[K]) IsEmpty
func (s *BuiltinSet[K]) IsEmpty() bool
func (*BuiltinSet[K]) Keys
func (s *BuiltinSet[K]) Keys() []K
func (*BuiltinSet[K]) Len
func (s *BuiltinSet[K]) Len() int
func (*BuiltinSet[K]) Remove
func (s *BuiltinSet[K]) Remove(k K) bool
func (*BuiltinSet[K]) RemoveN
func (s *BuiltinSet[K]) RemoveN(ks ...K)
func (BuiltinSet[K]) String
func (s BuiltinSet[K]) String() string

type CompareFn

CompareFn is a 3 way compare function that returns 1 if a > b, returns 0 if a == b, returns -1 if a < b.

type CompareFn[T any] func(a, b T) int

type Container

Container is a holder object that stores a collection of other objects.

type Container interface {
    IsEmpty() bool // IsEmpty checks if the container has no elements.
    Len() int      // Len returns the number of elements in the container.
    Clear()        // Clear erases all elements from the container. After this call, Len() returns zero.
}

type DList

DList is a doubly linked list.

type DList[T any] struct {
    // contains filtered or unexported fields
}
func NewDList
func NewDList[T any]() *DList[T]

NewDList make a new DList object

func NewDListOf
func NewDListOf[T any](vs ...T) *DList[T]

NewDListOf make a new DList from a serial of values

func (*DList[T]) Clear
func (l *DList[T]) Clear()

Clear cleanup the list

func (*DList[T]) ForEach
func (l *DList[T]) ForEach(cb func(val T))

ForEach iterate the list, apply each element to the cb callback function

func (*DList[T]) ForEachIf
func (l *DList[T]) ForEachIf(cb func(val T) bool)

ForEach iterate the list, apply each element to the cb callback function, stop if cb returns false.

func (*DList[T]) IsEmpty
func (l *DList[T]) IsEmpty() bool

IsEmpty return whether the list is empty

func (*DList[T]) Len
func (l *DList[T]) Len() int

Len return the length of the list

func (*DList[T]) PopBack
func (l *DList[T]) PopBack() (T, bool)
func (*DList[T]) PopFront
func (l *DList[T]) PopFront() (T, bool)
func (*DList[T]) PushBack
func (l *DList[T]) PushBack(val T)
func (*DList[T]) PushFront
func (l *DList[T]) PushFront(val T)
func (*DList[T]) String
func (l *DList[T]) String() string

String convert the list to string

type Float

Float is a constraint that permits any floating-point type. If future releases of Go add new predeclared floating-point types, this constraint will be modified to include them.

type Float interface {
    // contains filtered or unexported methods
}

type HashFn

HashFn is a function that returns the hash of 't'.

type HashFn[T any] func(t T) uint64

type Integer

Integer is a constraint that permits any integer type. If future releases of Go add new predeclared integer types, this constraint will be modified to include them.

type Integer interface {
    // contains filtered or unexported methods
}

type LessFn

LessFn is a function that returns whether 'a' is less than 'b'.

type LessFn[T any] func(a, b T) bool

type Map

Map is a associative container that contains key-value pairs with unique keys.

type Map[K any, V any] interface {
    Container
    Has(K) bool                        // Checks whether the container contains element with specific key.
    Find(K) *V                         // Finds element with specific key.
    Insert(K, V)                       // Inserts a key-value pair in to the container or replace existing value.
    Remove(K) bool                     // Remove element with specific key.
    ForEach(func(K, V))                // Iterate the container.
    ForEachIf(func(K, V) bool)         // Iterate the container, stops when the callback returns false.
    ForEachMutable(func(K, *V))        // Iterate the container, *V is mutable.
    ForEachMutableIf(func(K, *V) bool) // Iterate the container, *V is mutable, stops when the callback returns false.
}

type Numeric

Numeric is a constraint that permits any numeric type.

type Numeric interface {
    // contains filtered or unexported methods
}

type Ordered

Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >. If future releases of Go add new ordered types, this constraint will be modified to include them.

type Ordered interface {
    // contains filtered or unexported methods
}

type Queue

Queue is a FIFO container

type Queue[T any] struct {
    // contains filtered or unexported fields
}
func NewQueue
func NewQueue[T any]() *Queue[T]

NewQueue create a new Queue object.

func (*Queue[T]) Clear
func (q *Queue[T]) Clear()
func (*Queue[T]) IsEmpty
func (q *Queue[T]) IsEmpty() bool
func (*Queue[T]) Len
func (q *Queue[T]) Len() int
func (*Queue[T]) PopBack
func (q *Queue[T]) PopBack() (T, bool)
func (*Queue[T]) PopFront
func (q *Queue[T]) PopFront() (T, bool)
func (*Queue[T]) PushBack
func (q *Queue[T]) PushBack(val T)
func (*Queue[T]) PushFront
func (q *Queue[T]) PushFront(val T)
func (*Queue[T]) String
func (q *Queue[T]) String() string

type Set

Set is a containers that store unique elements.

type Set[K any] interface {
    Container
    Has(K) bool             // Checks whether the container contains element with specific key.
    Insert(K)               // Inserts a key-value pair in to the container or replace existing value.
    InsertN(...K)           // Inserts multiple key-value pairs in to the container or replace existing value.
    Remove(K) bool          // Remove element with specific key.
    RemoveN(...K)           // Remove multiple elements with specific keys.
    ForEach(func(K))        // Iterate the container.
    ForEachIf(func(K) bool) // Iterate the container, stops when the callback returns false.
}

type Signed

Signed is a constraint that permits any signed integer type. If future releases of Go add new predeclared signed integer types, this constraint will be modified to include them.

type Signed interface {
    // contains filtered or unexported methods
}

type SkipList

SkipList is a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

See https://en.wikipedia.org/wiki/Skip_list for more details.

type SkipList[K any, V any] struct {
    // contains filtered or unexported fields
}
func NewSkipList
func NewSkipList[K Ordered, V any]() *SkipList[K, V]

NewSkipList creates a new SkipList for Ordered key type.

func NewSkipListFromMap
func NewSkipListFromMap[K Ordered, V any](m map[K]V) *SkipList[K, V]

NewSkipListFromMap creates a new SkipList from a map.

func NewSkipListFunc
func NewSkipListFunc[K any, V any](keyCmp CompareFn[K]) *SkipList[K, V]

NewSkipListFunc creates a new SkipList with specified compare function keyCmp.

func (*SkipList[K, V]) Clear
func (sl *SkipList[K, V]) Clear()
func (*SkipList[K, V]) Find
func (sl *SkipList[K, V]) Find(key K) *V

Find returns the value associated with the passed key if the key is in the skiplist, otherwise returns nil.

func (*SkipList[K, V]) ForEach
func (sl *SkipList[K, V]) ForEach(op func(K, V))
func (*SkipList[K, V]) ForEachIf
func (sl *SkipList[K, V]) ForEachIf(op func(K, V) bool)
func (*SkipList[K, V]) ForEachMutable
func (sl *SkipList[K, V]) ForEachMutable(op func(K, *V))
func (*SkipList[K, V]) ForEachMutableIf
func (sl *SkipList[K, V]) ForEachMutableIf(op func(K, *V) bool)
func (*SkipList[K, V]) Has
func (sl *SkipList[K, V]) Has(key K) bool
func (*SkipList[K, V]) Insert
func (sl *SkipList[K, V]) Insert(key K, value V)

Insert inserts a key-value pair into the skiplist. If the key is already in the skip list, it's value will be updated.

func (*SkipList[K, V]) IsEmpty
func (sl *SkipList[K, V]) IsEmpty() bool
func (*SkipList[K, V]) Len
func (sl *SkipList[K, V]) Len() int
func (*SkipList[K, V]) Remove
func (sl *SkipList[K, V]) Remove(key K) bool

Remove removes the key-value pair associated with the passed key and returns true if the key is in the skiplist, otherwise returns false.

type Stack

Stack s is a container adaptor that provides the functionality of a stack, a LIFO (last-in, first-out) data structure.

type Stack[T any] struct {
    // contains filtered or unexported fields
}
func NewStack
func NewStack[T any]() *Stack[T]

NewStack creates a new Stack object.

func NewStackCap
func NewStackCap[T any](capicity int) *Stack[T]

NewStackCap creates a new Stack object with the specified capicity.

func (*Stack[T]) Cap
func (s *Stack[T]) Cap() int
func (*Stack[T]) Clear
func (s *Stack[T]) Clear()
func (*Stack[T]) IsEmpty
func (s *Stack[T]) IsEmpty() bool
func (*Stack[T]) Len
func (s *Stack[T]) Len() int
func (*Stack[T]) MustPop
func (s *Stack[T]) MustPop() T
func (*Stack[T]) Pop
func (s *Stack[T]) Pop() (val T, ok bool)
func (*Stack[T]) Push
func (s *Stack[T]) Push(t T)

type Unsigned

Unsigned is a constraint that permits any unsigned integer type. If future releases of Go add new predeclared unsigned integer types, this constraint will be modified to include them.

type Unsigned interface {
    // contains filtered or unexported methods
}

type Vector

Vector is a sequence container representing array that can change in size.

type Vector[T any] []T
func MakeVector
func MakeVector[T any]() Vector[T]

MakeVector creates an empty Vector object.

func MakeVectorCap
func MakeVectorCap[T any](c int) Vector[T]

MakeVectorCap creates an empty Vector object with specified capacity.

func MakeVectorOf
func MakeVectorOf[T any](v ...T) Vector[T]

MakeVectorOf creates an Vector object with initial values.

func (*Vector[T]) Append
func (v *Vector[T]) Append(x ...T)

Append appends the values x... to the tail of the vector.

func (*Vector[T]) At
func (v *Vector[T]) At(i int) T
func (*Vector[T]) Cap
func (v *Vector[T]) Cap() int
func (*Vector[T]) Clear
func (v *Vector[T]) Clear()

Clear erases all elements from the vector. After this call, Len() returns zero. Leaves the Cap() of the vector unchanged.

func (*Vector[T]) Insert
func (v *Vector[T]) Insert(i int, x ...T)

Insert inserts the values x... into the vector at index i. After the insertion, (*v)[i] == x[0]. Insert panics if i is out of range.

Complexity: O(len(s) + len(v)).

func (*Vector[T]) IsEmpty
func (v *Vector[T]) IsEmpty() bool
func (*Vector[T]) Len
func (v *Vector[T]) Len() int
func (*Vector[T]) PushBack
func (v *Vector[T]) PushBack(x T)
func (*Vector[T]) Remove
func (v *Vector[T]) Remove(i int)

Remove removes 1 element in the vector.

Complexity: O(len(s) - i).

func (*Vector[T]) RemoveLength
func (v *Vector[T]) RemoveLength(i int, len int)

Remove removes the elements in the range[i, i+len) from the vector.

func (*Vector[T]) RemoveRange
func (v *Vector[T]) RemoveRange(i, j int)

Remove removes the elements in the range[i, j) from the vector.

func (*Vector[T]) Reserve
func (v *Vector[T]) Reserve(l int)

Reserve increases the capacity of the vector (the total number of elements that the vector can hold without requiring reallocation)to a value that's greater or equal to l. If l is greater than the current Cap(), new storage is allocated, otherwise the function does nothing.

Reserve() does not change the size of the vector.

func (*Vector[T]) Set
func (v *Vector[T]) Set(i int, x T)
func (*Vector[T]) Shrink
func (v *Vector[T]) Shrink()

Shrink removes unused capacity from the vector.

Generated by gomarkdoc

Reference

Documentation

Overview

Package stl4go is a generic container and algorithm library for go.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AllOf 

func AllOf[T any](a []T, pred func(T) bool) bool

AllOf return true if pred(e) returns true for all emements e in a.

Complexity: O(len(a)).

func AnyOf 

func AnyOf[T any](a []T, pred func(T) bool) bool

AnyOf return true if pred(e) returns true for any emements e in a.

Complexity: O(len(a)).

func Average 

func Average[T Numeric](a []T) T

Average returns the average value of a.

func AverageAs 

func AverageAs[R, T Numeric](a []T) R

AverageAs returns the average value of a as type R.

func BinarySearch 

func BinarySearch[T Ordered](a []T, value T) (index int, ok bool)

BinarySearch returns the (index, true) to the first element in the ascending ordered slice a such that element == value, or (-1, false) if no such element is found.

Complexity: O(log(len(a))).

func BinarySearchFunc 

func BinarySearchFunc[T any](a []T, value T, less LessFn[T]) (index int, ok bool)

BinarySearchFunc returns the (index, true) to the first element in the ordered slice a such that less(element, value) and less(value, element) are both false, or (-1, false) if no such element is found.

The elements in the slice a should sorted according with compare func less.

Complexity: O(log(len(a))).

func Compare 

func Compare[E Ordered](a, b []E) int

Compare compares each elements in a and b.

return 0 if they are equals, return 1 if a > b, return -1 if a < b.

Complexity: O(min(len(a), len(b))).

func Copy 

func Copy[T any](a []T) []T

Copy make a copy of slice a.

Complexity: O(len(a)).

func Count 

func Count[T comparable](a []T, x T) int

Count returns the number of elements in the slice equals to x.

Complexity: O(len(a)).

func CountIf 

func CountIf[T comparable](a []T, pred func(T) bool) int

CountIf returns the number of elements in the slice which pred returns true.

Complexity: O(len(a)).

func DescSort 

func DescSort[T Ordered](a []T)

DescSort sorts data in descending order. The order of equal elements is not guaranteed to be preserved.

Complexity: O(N*log(N)), N=len(a).

func DescStableSort 

func DescStableSort[T Ordered](a []T)

DescStableSort sorts data in descending order stably. The order of equivalent elements is guaranteed to be preserved.

Complexity: O(N*log(N)), N=len(a).

func Equal 

func Equal[T comparable](a, b []T) bool

Equal returns whether two slices are equal. Return true if they are the same length and all elements are equal.

Complexity: O(min(len(a), len(b))).

func Equals 

func Equals[T comparable](a, b T) bool

Equals wraps the '==' operator for comparable types.

func Find 

func Find[T comparable](a []T, x T) (index int, ok bool)

Find find the first value x in the given slice a linearly. return (index, true) if found, return (_, false) if not found.

Complexity: O(len(a)).

func FindIf 

func FindIf[T any](a []T, cond func(T) bool) (index int, ok bool)

FindIf find the first value x satisfying function cond in the given slice a linearly. return (index, true) if found, return (_, false) if not found.

Complexity: O(len(a)).

func Generate 

func Generate[T any](a []T, gen func() T)

Generate fill each element of `a“ with `gen()`.

Complexity: O(len(a)).

func Index 

func Index[T comparable](a []T, x T) int

Index find the value x in the given slice a linearly.

Return index if found, -1 if not found.

Complexity: O(len(a)).

func IsDescSorted 

func IsDescSorted[T Ordered](a []T) bool

IsDescSorted returns whether the slice a is sorted in descending order.

Complexity: O(len(a)).

func IsSorted 

func IsSorted[T Ordered](a []T) bool

IsSorted returns whether the slice a is sorted in ascending order.

Complexity: O(len(a)).

func Less 

func Less[T Ordered](a, b T) bool

Less wraps the '<' operator for ordered types.

func LowerBound 

func LowerBound[T Ordered](a []T, value T) int

LowerBound returns an index to the first element in the ascending ordered slice a that does not satisfy element < value (i.e. greater or equal to), or len(a) if no such element is found.

Complexity: O(log(len(a))).

func LowerBoundFunc 

func LowerBoundFunc[T any](a []T, value T, less LessFn[T]) int

LowerBoundFunc returns an index to the first element in the ordered slice a that does not satisfy less(element, value)), or len(a) if no such element is found.

The elements in the slice a should sorted according with compare func less.

Complexity: O(log(len(a))).

func Max 

func Max[T Ordered](a, b T) T

Max return the larger value between `a` and `b`.

Complexity: O(1).

func MaxN 

func MaxN[T Ordered](a ...T) T

MaxN return the maximum value in the sequence `a`.

Complexity: O(len(a)).

func Min 

func Min[T Ordered](a, b T) T

Min return the smaller value between `a` and `b`.

Complexity: O(1).

func MinMax 

func MinMax[T Ordered](a, b T) (min, max T)

MinMax returns both min and max between a and b.

Complexity: O(1).

func MinMaxN 

func MinMaxN[T Ordered](a ...T) (min, max T)

MinMaxN returns both min and max in slice a.

Complexity: O(len(a))

func MinN 

func MinN[T Ordered](a ...T) T

MinN return the minimum value in the sequence `a`.

Complexity: O(len(a)).

func NoneOf 

func NoneOf[T any](a []T, pred func(T) bool) bool

NoneOf return true pred(e) returns true for none emements e in a.

Complexity: O(len(a)).

func OrderedCompare 

func OrderedCompare[T Ordered](a, b T) int

OrderedCompare provide default CompareFn for ordered types.

func Range 

func Range[T Numeric](first, last T) []T

Range make a []T filled with values in the `[first, last)` sequence. NOTE: the last is not included in the result.

Complexity: O(last-first).

func Remove 

func Remove[T comparable](a []T, x T) []T

Remove remove the elements which equals to x from the input slice. return the processed slice, and the content of the input slice is also changed.

Complexity: O(len(a)).

func RemoveCopy 

func RemoveCopy[T comparable](a []T, x T) []T

RemoveCopy remove all elements which equals to x from the input slice. return the processed slice, and the content of the input slice is also changed.

Complexity: O(len(a)).

func RemoveIf 

func RemoveIf[T any](a []T, cond func(T) bool) []T

RemoveIf remove each element which make cond(x) returns true from the input slice, copy other elements to a new slice and return it. The input slice is kept unchanged.

Complexity: O(len(a)).

func RemoveIfCopy 

func RemoveIfCopy[T any](a []T, cond func(T) bool) []T

RemoveIfCopy drops each element which make cond(x) returns true from the input slice, copy other elements to a new slice and return it. The input slice is kept unchanged.

Complexity: O(len(a)).

func Reverse 

func Reverse[T any](a []T)

Reverse reverses the order of the elements in the slice a.

Complexity: O(len(a)).

func ReverseCopy 

func ReverseCopy[T any](a []T) []T

ReverseCopy returns a reversed copy of slice a.

Complexity: O(len(a)).

func Shuffle 

func Shuffle[T any](a []T)

Shuffle pseudo-randomizes the order of elements.

Complexity: O(len(a)).

func Sort 

func Sort[T Ordered](a []T)

Sort sorts data in ascending order. The order of equal elements is not guaranteed to be preserved.

Complexity: O(N*log(N)), where N=len(a).

func SortFunc 

func SortFunc[T any](a []T, less func(x, y T) bool)

SortFunc sorts data in ascending order with compare func less. The order of equal elements is not guaranteed to be preserved.

Complexity: O(N*log(N)), N=len(a).

func StableSort 

func StableSort[T Ordered](a []T)

StableSort sorts data in ascending order stably. The order of equivalent elements is guaranteed to be preserved.

Complexity: O(N*log(N)^2), where N=len(a).

func StableSortFunc 

func StableSortFunc[T any](a []T, less func(x, y T) bool)

StableSortFunc sorts data in ascending order with compare func less stably. The order of equivalent elements is guaranteed to be preserved.

Complexity: O(N*log(N)), N=len(a).

func Sum 

func Sum[T Numeric](a []T) T

Sum summarize all elements in a. returns the result as type R, you should use SumAs if T can't hold the result. Complexity: O(len(a)).

func SumAs 

func SumAs[R, T Numeric](a []T) R

SumAs summarize all elements in a. returns the result as type R, this is useful when T is too small to hold the result. Complexity: O(len(a)).

func Transform 

func Transform[T any](a []T, op func(T) T)

Transform applies the function op to each element in slice a and set it back to the same place in a.

Complexity: O(len(a)).

func TransformCopy 

func TransformCopy[R any, T any](a []T, op func(T) R) []R

TransformCopy applies the function op to each element in slice a and return all the result as a slice.

Complexity: O(len(a)).

func TransformTo 

func TransformTo[R any, T any](a []T, op func(T) R, b []R)

TransformTo applies the function op to each element in slice a and fill it to slice b.

The len(b) must not lesser than len(a).

Complexity: O(len(a)).

func Unique 

func Unique[T comparable](a []T) []T

Unique remove adjacent repeated elements from the input slice. return the processed slice, and the content of the input slice is also changed.

Complexity: O(len(a)).

func UniqueCopy 

func UniqueCopy[T comparable](a []T) []T

UniqueCopy remove adjacent repeated elements from the input slice. return the result slice, and the input slice is kept unchanged.

Complexity: O(len(a)).

func UpperBound 

func UpperBound[T Ordered](a []T, value T) int

UpperBound returns an index to the first element in the ascending ordered slice a such that value < element (i.e. strictly greater), or len(a) if no such element is found.

Complexity: O(log(len(a))).

func UpperBoundFunc 

func UpperBoundFunc[T any](a []T, value T, less LessFn[T]) int

UpperBoundFunc returns an index to the first element in the ordered slice a such that less(value, element)) is true (i.e. strictly greater), or len(a) if no such element is found.

The elements in the slice a should sorted according with compare func less.

Complexity: O(log(len(a))).

Types

type BuiltinSet 

type BuiltinSet[K comparable] map[K]bool

BuiltinSet is an associative container that contains a unordered set of unique objects of type K.

func MakeBuiltinSetOf 

func MakeBuiltinSetOf[K comparable](ks ...K) BuiltinSet[K]

MakeBuiltinSetOf creates a new BuiltinSet object with the initial content from ks.

func (*BuiltinSet[K]) Clear 

func (s *BuiltinSet[K]) Clear()

func (*BuiltinSet[K]) ForEach 

func (s *BuiltinSet[K]) ForEach(cb func(k K))

func (*BuiltinSet[K]) ForEachIf 

func (s *BuiltinSet[K]) ForEachIf(cb func(k K) bool)

func (*BuiltinSet[K]) Has 

func (s *BuiltinSet[K]) Has(k K) bool

func (*BuiltinSet[K]) Insert 

func (s *BuiltinSet[K]) Insert(k K)

func (*BuiltinSet[K]) InsertN 

func (s *BuiltinSet[K]) InsertN(ks ...K)

func (*BuiltinSet[K]) IsEmpty 

func (s *BuiltinSet[K]) IsEmpty() bool

func (*BuiltinSet[K]) Keys 

func (s *BuiltinSet[K]) Keys() []K

func (*BuiltinSet[K]) Len 

func (s *BuiltinSet[K]) Len() int

func (*BuiltinSet[K]) Remove 

func (s *BuiltinSet[K]) Remove(k K) bool

func (*BuiltinSet[K]) RemoveN 

func (s *BuiltinSet[K]) RemoveN(ks ...K)

func (BuiltinSet[K]) String 

func (s BuiltinSet[K]) String() string

type CompareFn 

type CompareFn[T any] func(a, b T) int

CompareFn is a 3 way compare function that returns 1 if a > b, returns 0 if a == b, returns -1 if a < b.

type Container 

type Container interface {
	IsEmpty() bool // IsEmpty checks if the container has no elements.
	Len() int      // Len returns the number of elements in the container.
	Clear()        // Clear erases all elements from the container. After this call, Len() returns zero.
}

Container is a holder object that stores a collection of other objects.

type DList 

type DList[T any] struct {
	// contains filtered or unexported fields
}

DList is a doubly linked list.

func NewDList 

func NewDList[T any]() *DList[T]

NewDList make a new DList object

func NewDListOf 

func NewDListOf[T any](vs ...T) *DList[T]

NewDListOf make a new DList from a serial of values

func (*DList[T]) Clear 

func (l *DList[T]) Clear()

Clear cleanup the list

func (*DList[T]) ForEach 

func (l *DList[T]) ForEach(cb func(val T))

ForEach iterate the list, apply each element to the cb callback function

func (*DList[T]) ForEachIf 

func (l *DList[T]) ForEachIf(cb func(val T) bool)

ForEach iterate the list, apply each element to the cb callback function, stop if cb returns false.

func (*DList[T]) IsEmpty 

func (l *DList[T]) IsEmpty() bool

IsEmpty return whether the list is empty

func (*DList[T]) Len 

func (l *DList[T]) Len() int

Len return the length of the list

func (*DList[T]) PopBack 

func (l *DList[T]) PopBack() (T, bool)

func (*DList[T]) PopFront 

func (l *DList[T]) PopFront() (T, bool)

func (*DList[T]) PushBack 

func (l *DList[T]) PushBack(val T)

func (*DList[T]) PushFront 

func (l *DList[T]) PushFront(val T)

func (*DList[T]) String 

func (l *DList[T]) String() string

String convert the list to string

type Float 

type Float interface {
	~float32 | ~float64
}

Float is a constraint that permits any floating-point type. If future releases of Go add new predeclared floating-point types, this constraint will be modified to include them.

type HashFn 

type HashFn[T any] func(t T) uint64

HashFn is a function that returns the hash of 't'.

type Integer 

type Integer interface {
	Signed | Unsigned
}

Integer is a constraint that permits any integer type. If future releases of Go add new predeclared integer types, this constraint will be modified to include them.

type LessFn 

type LessFn[T any] func(a, b T) bool

LessFn is a function that returns whether 'a' is less than 'b'.

type Map 

type Map[K any, V any] interface {
	Container
	Has(K) bool                        // Checks whether the container contains element with specific key.
	Find(K) *V                         // Finds element with specific key.
	Insert(K, V)                       // Inserts a key-value pair in to the container or replace existing value.
	Remove(K) bool                     // Remove element with specific key.
	ForEach(func(K, V))                // Iterate the container.
	ForEachIf(func(K, V) bool)         // Iterate the container, stops when the callback returns false.
	ForEachMutable(func(K, *V))        // Iterate the container, *V is mutable.
	ForEachMutableIf(func(K, *V) bool) // Iterate the container, *V is mutable, stops when the callback returns false.
}

Map is a associative container that contains key-value pairs with unique keys.

type Numeric 

type Numeric interface {
	Integer | Float
}

Numeric is a constraint that permits any numeric type.

type Ordered 

type Ordered interface {
	Integer | Float | ~string
}

Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >. If future releases of Go add new ordered types, this constraint will be modified to include them.

type Queue 

type Queue[T any] struct {
	// contains filtered or unexported fields
}

Queue is a FIFO container

func NewQueue 

func NewQueue[T any]() *Queue[T]

NewQueue create a new Queue object.

func (*Queue[T]) Clear 

func (q *Queue[T]) Clear()

func (*Queue[T]) IsEmpty 

func (q *Queue[T]) IsEmpty() bool

func (*Queue[T]) Len 

func (q *Queue[T]) Len() int

func (*Queue[T]) PopBack 

func (q *Queue[T]) PopBack() (T, bool)

func (*Queue[T]) PopFront 

func (q *Queue[T]) PopFront() (T, bool)

func (*Queue[T]) PushBack 

func (q *Queue[T]) PushBack(val T)

func (*Queue[T]) PushFront 

func (q *Queue[T]) PushFront(val T)

func (*Queue[T]) String 

func (q *Queue[T]) String() string

type Set 

type Set[K any] interface {
	Container
	Has(K) bool             // Checks whether the container contains element with specific key.
	Insert(K)               // Inserts a key-value pair in to the container or replace existing value.
	InsertN(...K)           // Inserts multiple key-value pairs in to the container or replace existing value.
	Remove(K) bool          // Remove element with specific key.
	RemoveN(...K)           // Remove multiple elements with specific keys.
	ForEach(func(K))        // Iterate the container.
	ForEachIf(func(K) bool) // Iterate the container, stops when the callback returns false.
}

Set is a containers that store unique elements.

type Signed 

type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

Signed is a constraint that permits any signed integer type. If future releases of Go add new predeclared signed integer types, this constraint will be modified to include them.

type SkipList 

type SkipList[K any, V any] struct {
	// contains filtered or unexported fields
}

SkipList is a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

See https://en.wikipedia.org/wiki/Skip_list for more details.

func NewSkipList 

func NewSkipList[K Ordered, V any]() *SkipList[K, V]

NewSkipList creates a new SkipList for Ordered key type.

func NewSkipListFromMap 

func NewSkipListFromMap[K Ordered, V any](m map[K]V) *SkipList[K, V]

NewSkipListFromMap creates a new SkipList from a map.

func NewSkipListFunc 

func NewSkipListFunc[K any, V any](keyCmp CompareFn[K]) *SkipList[K, V]

NewSkipListFunc creates a new SkipList with specified compare function keyCmp.

func (*SkipList[K, V]) Clear 

func (sl *SkipList[K, V]) Clear()

func (*SkipList[K, V]) Find 

func (sl *SkipList[K, V]) Find(key K) *V

Find returns the value associated with the passed key if the key is in the skiplist, otherwise returns nil.

func (*SkipList[K, V]) ForEach 

func (sl *SkipList[K, V]) ForEach(op func(K, V))

func (*SkipList[K, V]) ForEachIf 

func (sl *SkipList[K, V]) ForEachIf(op func(K, V) bool)

func (*SkipList[K, V]) ForEachMutable 

func (sl *SkipList[K, V]) ForEachMutable(op func(K, *V))

func (*SkipList[K, V]) ForEachMutableIf 

func (sl *SkipList[K, V]) ForEachMutableIf(op func(K, *V) bool)

func (*SkipList[K, V]) Has 

func (sl *SkipList[K, V]) Has(key K) bool

func (*SkipList[K, V]) Insert 

func (sl *SkipList[K, V]) Insert(key K, value V)

Insert inserts a key-value pair into the skiplist. If the key is already in the skip list, it's value will be updated.

func (*SkipList[K, V]) IsEmpty 

func (sl *SkipList[K, V]) IsEmpty() bool

func (*SkipList[K, V]) Len 

func (sl *SkipList[K, V]) Len() int

func (*SkipList[K, V]) Remove 

func (sl *SkipList[K, V]) Remove(key K) bool

Remove removes the key-value pair associated with the passed key and returns true if the key is in the skiplist, otherwise returns false.

type Stack 

type Stack[T any] struct {
	// contains filtered or unexported fields
}

Stack s is a container adaptor that provides the functionality of a stack, a LIFO (last-in, first-out) data structure.

func NewStack 

func NewStack[T any]() *Stack[T]

NewStack creates a new Stack object.

func NewStackCap 

func NewStackCap[T any](capicity int) *Stack[T]

NewStackCap creates a new Stack object with the specified capicity.

func (*Stack[T]) Cap 

func (s *Stack[T]) Cap() int

func (*Stack[T]) Clear 

func (s *Stack[T]) Clear()

func (*Stack[T]) IsEmpty 

func (s *Stack[T]) IsEmpty() bool

func (*Stack[T]) Len 

func (s *Stack[T]) Len() int

func (*Stack[T]) MustPop 

func (s *Stack[T]) MustPop() T

func (*Stack[T]) Pop 

func (s *Stack[T]) Pop() (val T, ok bool)

func (*Stack[T]) Push 

func (s *Stack[T]) Push(t T)

type Unsigned 

type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

Unsigned is a constraint that permits any unsigned integer type. If future releases of Go add new predeclared unsigned integer types, this constraint will be modified to include them.

type Vector 

type Vector[T any] []T

Vector is a sequence container representing array that can change in size.

func MakeVector 

func MakeVector[T any]() Vector[T]

MakeVector creates an empty Vector object.

func MakeVectorCap 

func MakeVectorCap[T any](c int) Vector[T]

MakeVectorCap creates an empty Vector object with specified capacity.

func MakeVectorOf 

func MakeVectorOf[T any](v ...T) Vector[T]

MakeVectorOf creates an Vector object with initial values.

func (*Vector[T]) Append 

func (v *Vector[T]) Append(x ...T)

Append appends the values x... to the tail of the vector.

func (*Vector[T]) At 

func (v *Vector[T]) At(i int) T

func (*Vector[T]) Cap 

func (v *Vector[T]) Cap() int

func (*Vector[T]) Clear 

func (v *Vector[T]) Clear()

Clear erases all elements from the vector. After this call, Len() returns zero. Leaves the Cap() of the vector unchanged.

func (*Vector[T]) Insert 

func (v *Vector[T]) Insert(i int, x ...T)

Insert inserts the values x... into the vector at index i. After the insertion, (*v)[i] == x[0]. Insert panics if i is out of range.

Complexity: O(len(s) + len(v)).

func (*Vector[T]) IsEmpty 

func (v *Vector[T]) IsEmpty() bool

func (*Vector[T]) Len 

func (v *Vector[T]) Len() int

func (*Vector[T]) PushBack 

func (v *Vector[T]) PushBack(x T)

func (*Vector[T]) Remove 

func (v *Vector[T]) Remove(i int)

Remove removes 1 element in the vector.

Complexity: O(len(s) - i).

func (*Vector[T]) RemoveLength 

func (v *Vector[T]) RemoveLength(i int, len int)

Remove removes the elements in the range[i, i+len) from the vector.

func (*Vector[T]) RemoveRange 

func (v *Vector[T]) RemoveRange(i, j int)

Remove removes the elements in the range[i, j) from the vector.

func (*Vector[T]) Reserve 

func (v *Vector[T]) Reserve(l int)

Reserve increases the capacity of the vector (the total number of elements that the vector can hold without requiring reallocation)to a value that's greater or equal to l. If l is greater than the current Cap(), new storage is allocated, otherwise the function does nothing.

Reserve() does not change the size of the vector.

func (*Vector[T]) Set 

func (v *Vector[T]) Set(i int, x T)

func (*Vector[T]) Shrink 

func (v *Vector[T]) Shrink()

Shrink removes unused capacity from the vector.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.