stl4go

package module
v0.1.1 Latest Latest
Warning

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

 Go to latest Published: Aug 15, 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 Golang Build Status Coverage Status GoReport Go Reference

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

import "github.com/chen3feng/stl4go"

Package stl4go is a generic container and algo rithm library for go.

Introduce

This library is a general container and algorithm library that attempts to learn from the C++ STL implementation after Go 1.18 began to support generics. (Personally I's totally unacceptable for me use to languages without generics, so I didn't try it until go 1.18).

The code quality of this library is quite high and follows the latest best practices in the industry. Test coverage is close💯%, ✅，CI, and gosec check are both set up, got GoReport score。

Features

As we all know, C++'s STL includes containers, algorithms, and iterators relate the two.

Due to language limitations, it is impossible and unnecessary to completely imitate the interface of C++ STL in Go, so C++ users may feel familiar, and sometimes (maybe) feel more convenient.

Containers

Currently implemented containers are:

  • BuiltinSet provided a set funtionality based on Go's own map
  • Vector is a thin encapsulation based on slice. It provides functions such as insertion and deletion in the middle, range deletion, etc., and is still compatible with slices.
  • DList is a doubly linked list.
  • SkipList is an ordered associative container that fills the gap where Go map only supports unordered. This is currently the fastest skip list I tested in GitHub, see skiplist-survey for performance comparison
  • Stack, is a FILO container based on Slice implementation
  • Queue is a bidirectional FIFO queue, implemented based on linked list.

Different containers support different methods. The following are the methods supported by all containers:

  • IsEmpty() bool Returns whether the container is empty
  • Len() int returns the number of elements in the container
  • Clear() to clear the container
Iterators

DList and SkipList support simple iterators.

    l := stl4go.NewDListOf(Range(1, 10000)...)
    sum := 0
    for i := 0; i < b.N; i++ {
        for it := l.Iterate(); it.IsNotEnd(); it.MoveToNext() {
            sum += it.Value()
        }
    }

SkipList also supports interval iteration:

    l := stl4go.NewDListOf(Range(1, 1000)...)
    it := sl.FindRange(120, 350)

Iterating over it yields numbers between 120 and 349.

In many cases, it is more convenient to use the ForEach and ForEachIf methods provided by the container, and the performance is often better:

func TestSkipList_ForEach(t *testing.T) {
    sl := newSkipListN(100)
    a := []int{}
    sl.ForEach(func(k int, v int) {
        a = append(a, k)
    })
    expectEq(t, len(a), 100)
    expectTrue(t, IsSorted(a))
}

ForEachIf is used for scenarios that you want to end early during the iteration:

func Test_DList_ForEachIf(t *testing.T) {
   l := NewDListOf(1, 2, 3)
   c := 0
   l.ForEachIf(func(n int) bool {
       c = n
       return n != 2
   })
   expectEq(t, c, 2)
}

You can use ForEachMutable or ForEachMutable to modify the value of an element during the iteration:

func TestSkipList_ForEachMutable(t *testing.T) {
    sl := newSkipListN(100)
    sl.ForEachMutable(func(k int, v *int) {
        *v = -*v
    })
    for i := 0; i < sl.Len(); i++ {
        expectEq(t, *sl.Find(i), -i)
    }
}
Algorithms

Due to the limitations of language, most algorithms only support Slice. The functions name of the algorithms ends with If, Func, indicating that a custom comparison function can be passed.

Generate
  • Range returns a Slice of contains integers in the range of [begin, end)
  • Generate generates a sequence with the given function to fill the Slice
Compute
  • Sum Sum
  • SumAs sums and returns a result as another type (eg. use int64 to return the sum of []int32).
  • Average finds the average value.
  • AverageAs averages and returns the result as another type (eg. use float64 to return the sum of []int).
  • Count returns the number equivalent to the specified value
  • CountIf returns the number of elements for which the specified function returns true
Compare
  • Equal checks whether two sequences are equal
  • Compare compares two sequences and returns -1, 0, and 1 in lexicographical order, respectively indicating the relationship of 2 slices.
Lookup
  • Min, Max find the maximum and minimum
  • MinN, MaxN, MinMax return the maximum and minimum values in the slice
  • Find linearly finds the first specified value and returns its index
  • FindIf linearly finds the first value that make specified function returns true and returns its index
  • AllOf, AnyOf, NoneOf return whether all, any, or none of the elements in the range can make the passed function return true accordingly.

See C++ STL.

  • BinarySearch
  • LowerBound
  • UpperBound
Sort
  • Sort sorting
  • DescSort descending sorting
  • StableSort stable sorting
  • DescStableSort descending stable sorting
  • IsSorted check whether the slice is sorted
  • IsDescSorted check whether the slice is sorted in descending order
Interface Design and Naming

The design leart much from the C++ STL. The T here represents template. Yes, Go's generic is not template. but who made C++ so influential and STL so famous?

Many libraries are designed for small code repositories or split into multiple subpackages in one repository. For example:

import (
    "github.com/someone/awesomelib/skiplist"
    "github.com/someone/awesomelib/binarysearch"
)

func main() {
    sl := skiplist.New()
}

This way of writing seems elegant, but because everyone likes good names, import renaming has to be introduced in use in case of package name conflict, and different users have different renaming style, which increases the mental burden of code reading and writing.

I don't like this style, especially in a larger repository.

Therefore, this library is all under the stl4go package, and it is expected that it will not namesake in other people's libraries.

TODO

See Issue。

And add more detailed documents.

Go Doc

Clock to view the generated doc.

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()

Clear implements the Container interface.

func (*BuiltinSet[K]) ForEach 

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

ForEach implements the Set interface.

func (*BuiltinSet[K]) ForEachIf 

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

ForEachIf implements the Container interface.

func (*BuiltinSet[K]) Has 

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

Has implements the Set interface.

func (*BuiltinSet[K]) Insert 

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

Insert implements the Set interface.

func (*BuiltinSet[K]) InsertN 

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

InsertN implements the Set interface.

func (*BuiltinSet[K]) IsEmpty 

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

IsEmpty implements the Container interface.

func (*BuiltinSet[K]) Keys 

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

Keys return a copy of all keys as a slice.

func (*BuiltinSet[K]) Len 

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

Len implements the Container interface.

func (*BuiltinSet[K]) Remove 

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

Remove implements the Set interface.

func (*BuiltinSet[K]) RemoveN 

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

RemoveN implements the Set interface.

func (BuiltinSet[K]) String 

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

String implements the fmt.Stringer interface

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)

ForEachIf 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]) Iterate added in v0.1.1 

func (l *DList[T]) Iterate() Iterator[T]

Iterate returns an iterator to the first element in the list.

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)

PopBack popups a element from the back of the list.

func (*DList[T]) PopFront 

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

PopFront popups a element from the front of the list.

func (*DList[T]) PushBack 

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

PushBack pushes an element at the back of the list.

func (*DList[T]) PushFront 

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

PushFront pushes an element at the front of the list.

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 Iterator added in v0.1.1 

type Iterator[T any] interface {
	IsNotEnd() bool // Whether it is point to the end of the range.
	MoveToNext()    // Let it point to the next element.
	Value() T       // Return the value of current element.
}

Iterator is the interface for container's iterator.

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 MapIterator added in v0.1.1 

type MapIterator[K any, V any] interface {
	Iterator[V]
	Key() K // The key of the element
}

MapIterator is the interface for map's iterator.

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()

Clear implements the Container interface.

func (*Queue[T]) IsEmpty 

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

IsEmpty implements the Container interface.

func (*Queue[T]) Len 

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

Len implements the Container interface.

func (*Queue[T]) PopBack 

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

PopBack popups an element from the back of the queue.

func (*Queue[T]) PopFront 

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

PopFront popups an element from the front of the queue.

func (*Queue[T]) PushBack 

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

PushBack pushed an element to the back of the queue.

func (*Queue[T]) PushFront 

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

PushFront pushed an element to the front of the queue.

func (*Queue[T]) String 

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

Len implements the fmt.Stringer interface.

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()

Clear implements the Container interface.

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]) FindRange added in v0.1.1 

func (sl *SkipList[K, V]) FindRange(first, last K) MapIterator[K, V]

FindRange returns an iterator in range [first, last) (last is not includeed).

func (*SkipList[K, V]) ForEach 

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

ForEach implements the Map interface.

func (*SkipList[K, V]) ForEachIf 

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

ForEachIf implements the Map interface.

func (*SkipList[K, V]) ForEachMutable 

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

ForEachMutable implements the Map interface.

func (*SkipList[K, V]) ForEachMutableIf 

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

ForEachMutableIf implements the Map interface.

func (*SkipList[K, V]) Has 

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

Has implement the Map interface.

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

IsEmpty implements the Container interface.

func (*SkipList[K, V]) Iterate added in v0.1.1 

func (sl *SkipList[K, V]) Iterate() MapIterator[K, V]

Iterate return an iterator to the skiplist.

func (*SkipList[K, V]) Len 

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

Len implements the Container interface.

func (*SkipList[K, V]) LowerBound added in v0.1.1 

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

LowerBound returns an iterator to the first element in the skiplist that does not satisfy element < value (i.e. greater or equal to), or a end itetator if no such element is found.

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.

func (*SkipList[K, V]) UpperBound added in v0.1.1 

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

UpperBound returns an iterator to the first element in the skiplist that does not satisfy value < element (i.e. strictly greater), or a end itetator if no such element is found.

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

Cap returns the capacity of the stack.

func (*Stack[T]) Clear 

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

Clear implements the Container interface.

func (*Stack[T]) IsEmpty 

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

IsEmpty implements the Container interface.

func (*Stack[T]) Len 

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

Len implements the Container interface.

func (*Stack[T]) MustPop 

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

MustPop popups an element from the top of the stack. It must be called whtn IsEmpty() returned false, otherwise it will panic.

func (*Stack[T]) Pop 

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

Pop try popup an element from the top of the stack.

func (*Stack[T]) Push 

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

Push pushes the element to the top of the stack.

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

At returns the element value at the index i. You can also use the [] operator, and it's better.

func (*Vector[T]) Cap 

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

Cap returns the capacity of the vector.

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

IsEmpty implements the Container interface.

func (*Vector[T]) Len 

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

Len implements the Container interface.

func (*Vector[T]) PushBack 

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

PushBack pushs an element to the end of the vector.

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)

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

func (*Vector[T]) RemoveRange 

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

RemoveRange 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)

Set sets the value of the element at the index i. You can also use the [] operator, and it's better.

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.