collections

package
v1.0.12 Latest Latest
Warning

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

 Go to latest Published: Feb 14, 2025 License: BSD-3-Clause Imports: 15 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	ZSKIPLIST_MAXLEVEL = 32   // Should be enough for 2^64 elements
	ZSKIPLIST_P        = 0.25 // Skiplist P = 1/4
)
View Source 
const (
	ReplicaCount = 20 // 固定大小的虚拟节点数量
)

Variables

This section is empty.

Functions

func BitBytesCount 

func BitBytesCount(bitSize int) int

func BitWordsCount 

func BitWordsCount(bitSize int) int

func BoolCmp 

func BoolCmp(a, b bool) int

func Complex128Cmp 

func Complex128Cmp(a, b complex128) int

func Complex64Cmp 

func Complex64Cmp(a, b complex64) int

func HeapFix 

func HeapFix[S ~[]E, E cmp.Ordered](h S, i int)

HeapFix re-establishes the heap ordering after the element at index i has changed its Value. Changing the Value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Remove(h, i) followed by a Push of the new Value. The complexity is O(log n) where n = h.Len().

func HeapPop 

func HeapPop[S ~[]E, E cmp.Ordered](h S) (S, E)

HeapPop removes and returns the minimum element (according to Less) from the heap. Pop is equivalent to Remove(h, 0).

func HeapPush 

func HeapPush[S ~[]E, E cmp.Ordered](h S, x E) S

HeapPush pushes the element x onto the heap.

func HeapRemove 

func HeapRemove[S ~[]E, E cmp.Ordered](h S, i int) (S, E)

HeapRemove removes and returns the element at index i from the heap.

func Heapify 

func Heapify[S ~[]E, E cmp.Ordered](h S)

Heapify establishes the heap invariants required by the other routines in this package. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated.

func InsertAt 

func InsertAt[E any](s []E, i int, v E) []E

InsertAt 把`v`插入到第`i`个位置

func IsAllZeroElem 

func IsAllZeroElem[E cmp.Ordered | ~bool](s []E) bool

IsAllZeroElem 是否数组的所有元素都为0

func MapAdd 

func MapAdd[M ~map[K]V, K comparable, V cmp.Ordered](a, b M) M

MapAdd 把b的所有值加到a里

func MapIntersect 

func MapIntersect[M ~map[K]V, K, V comparable](a, b M) M

MapIntersect 返回两个map的交集, a ∩ b

func MapKeyValues 

func MapKeyValues[M ~map[K]V, K comparable, V any](m M) ([]K, []V)

MapKeyValues 返回map的key和value列表

func MapKeys 

func MapKeys[M ~map[K]V, K comparable, V any](m M) []K

MapKeys 返回map的key列表

func MapOrderedKeyValues 

func MapOrderedKeyValues[M ~map[K]V, K cmp.Ordered, V any](m M) ([]K, []V)

MapOrderedKeyValues 返回map里已排序的key和value列表

func MapOrderedKeys 

func MapOrderedKeys[M ~map[K]V, K cmp.Ordered, V any](m M) []K

MapOrderedKeys 返回map里已排序的key列表

func MapOrderedValues 

func MapOrderedValues[M ~map[K]V, K cmp.Ordered, V any](m M) []V

MapOrderedValues 返回map里按key排序的value列表

func MapUnion 

func MapUnion[M ~map[K]V, K comparable, V any](a, b M) M

MapUnion 返回两个map的并集, copy of a ∪ b

func MapValues 

func MapValues[M ~map[K]V, K comparable, V any](m M) []V

MapValues 返回map的value列表

func OrderedCmp 

func OrderedCmp[T cmp.Ordered](a, b T) int

func OrderedContains 

func OrderedContains[T cmp.Ordered](set []T, elem T) bool

OrderedContains `elem`是否在有序数组`set`中

func OrderedDelete 

func OrderedDelete[T cmp.Ordered](set []T, elem T) []T

OrderedDelete 把`n`从有序数组中删除

func OrderedIndexOf 

func OrderedIndexOf[T cmp.Ordered](set []T, elem T) int

OrderedIndexOf `elem`在有序数组`set`中的索引，如果不存在返回-1

func OrderedIntersect 

func OrderedIntersect[T cmp.Ordered](a, b []T) []T

OrderedIntersect 有序数组交集, A ∩ B

func OrderedPutIfAbsent 

func OrderedPutIfAbsent[T cmp.Ordered](set []T, elem T) []T

OrderedPutIfAbsent 插入`n`到有序数组

func OrderedUnion 

func OrderedUnion[T cmp.Ordered](a, b []T) []T

OrderedUnion 有序数组并集, A ∪ B

func RemoveAt 

func RemoveAt[E any](s []E, i int) []E

RemoveAt 删除第`i`个元素，不保证原来元素的顺序

func RemoveFirst 

func RemoveFirst[E comparable](s []E, elem E) []E

RemoveFirst 删除第一个查询到的元素

func ReverseOrderedCmp 

func ReverseOrderedCmp[T cmp.Ordered](a, b T) int

func Shrink 

func Shrink[E any](s []E) []E

func Shuffle 

func Shuffle[E any](s []E)

func SortAndRemoveDup 

func SortAndRemoveDup[E cmp.Ordered](s []E) []E

SortAndRemoveDup 去重并排序

Types

type BitMap64 

type BitMap64 []uint64

func NewBitMap64 

func NewBitMap64(bitSize int) BitMap64

func (BitMap64) ClearBit 

func (bm BitMap64) ClearBit(i int)

ClearBit clears the bit at the given index.

func (BitMap64) FlipBit 

func (bm BitMap64) FlipBit(i int)

FlipBit flips the bit at the given index.

func (BitMap64) FormattedString 

func (bm BitMap64) FormattedString(width int) string

FormattedString 按指定宽度对齐

func (BitMap64) IsZero 

func (bm BitMap64) IsZero() bool

IsZero 是否所有位都是0

func (BitMap64) MustSetBit 

func (bm BitMap64) MustSetBit(i int) BitMap64

MustSetBit 指定位是否为1，并且自动增长数组

func (BitMap64) OnesCount 

func (bm BitMap64) OnesCount() int

OnesCount returns the number of bits set to 1.

func (BitMap64) SetBit 

func (bm BitMap64) SetBit(i int)

func (BitMap64) String 

func (bm BitMap64) String() string

String returns a string representation of the bitmap from LSB to MSB.

func (BitMap64) TestAndClearBit 

func (bm BitMap64) TestAndClearBit(i int) bool

TestAndClearBit returns the old Value of the bit at the given index and clears it.

func (BitMap64) TestAndSetBit 

func (bm BitMap64) TestAndSetBit(i int) bool

TestAndSetBit returns the old Value of the bit at the given index and sets it to 1.

func (BitMap64) TestBit 

func (bm BitMap64) TestBit(i int) bool

TestBit checks if the bit at the given index which starting from LSB is set.

type BitMap8 

type BitMap8 []uint8

func NewBitMap8 

func NewBitMap8(bitSize int) BitMap8

func (BitMap8) ClearBit 

func (bm BitMap8) ClearBit(i int)

ClearBit clears the bit at the given index.

func (BitMap8) FlipBit 

func (bm BitMap8) FlipBit(i int)

FlipBit flips the bit at the given index.

func (BitMap8) FormattedString 

func (bm BitMap8) FormattedString(width int) string

FormattedString 按指定宽度对齐

func (BitMap8) IsZero 

func (bm BitMap8) IsZero() bool

IsZero 是否所有位都是0

func (BitMap8) MustSetBit 

func (bm BitMap8) MustSetBit(i int) BitMap8

MustSetBit 指定位是否为1，并且自动增长数组

func (BitMap8) OnesCount 

func (bm BitMap8) OnesCount() int

OnesCount returns the number of bits set to 1.

func (BitMap8) SetBit 

func (bm BitMap8) SetBit(i int)

func (BitMap8) String 

func (bm BitMap8) String() string

func (BitMap8) TestAndClearBit 

func (bm BitMap8) TestAndClearBit(i int) bool

TestAndClearBit returns the old Value of the bit at the given index and clears it.

func (BitMap8) TestAndSetBit 

func (bm BitMap8) TestAndSetBit(i int) bool

TestAndSetBit returns the old Value of the bit at the given index and sets it to 1.

func (BitMap8) TestBit 

func (bm BitMap8) TestBit(i int) bool

type Color 

type Color uint8

Color Red-black mechanics 

const (
	RED   Color = 0
	BLACK Color = 1
)

func (Color) String 

func (c Color) String() string

type Comparable 

type Comparable interface {
	// CompareTo returns an integer comparing two Comparables.
	// a.CompareTo(b) < 0 implies a < b
	// a.CompareTo(b) > 0 implies a > b
	// a.CompareTo(b) == 0 implies a == b
	CompareTo(b Comparable) int
}

Comparable compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. The implementor must ensure that signum(compare(x, y)) == -signum(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.) The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0. Finally, the implementor must ensure that compare(x, y)==0 implies that signum(compare(x, z))==signum(compare(y, z)) for all z.

type Comparator 

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

Comparator compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the Value of expression is negative, zero or positive.

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.) The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0. Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z. It is generally the case, but not strictly required that (compare(x, y)==0) == (x.equals(y)). Generally speaking, any comparator that violates this condition should clearly indicate this fact.

func Reversed 

func Reversed[T any](cmp Comparator[T]) Comparator[T]

type Consistent 

type Consistent struct {
	// contains filtered or unexported fields
}

Consistent 一致性hash code inspired by github.com/stathat/consistent

func NewConsistent 

func NewConsistent() *Consistent

func (*Consistent) Add 

func (c *Consistent) Add(node uint64)

func (*Consistent) AddElem 

func (c *Consistent) AddElem(node string)

AddElem inserts an element node in the consistent hash.

func (*Consistent) Clear 

func (c *Consistent) Clear()

func (*Consistent) Get 

func (c *Consistent) Get(name string) string

Get returns an element close to where name hashes to in the circle.

func (*Consistent) GetNode 

func (c *Consistent) GetNode(node uint64) uint64

func (*Consistent) GetTwo 

func (c *Consistent) GetTwo(name string) []string

GetTwo returns the two closest distinct elements to the name input in the circle.

func (*Consistent) GetTwoNodes 

func (c *Consistent) GetTwoNodes(node uint64) []uint64

GetTwoNodes returns the two closest distinct elements to the name input in the circle.

func (*Consistent) HasMember 

func (c *Consistent) HasMember(node string) bool

func (*Consistent) HasMemberNode 

func (c *Consistent) HasMemberNode(node uint64) bool

func (*Consistent) Len 

func (c *Consistent) Len() int

func (*Consistent) Members 

func (c *Consistent) Members() []string

func (*Consistent) Remove 

func (c *Consistent) Remove(node uint64) bool

func (*Consistent) RemoveElem 

func (c *Consistent) RemoveElem(node string) bool

RemoveElem removes an element node from the hash.

type Deque 

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

func NewDeque 

func NewDeque[T any](size ...int) *Deque[T]

NewDeque creates a new Deque, optionally setting the current and minimum capacity when non-zero values are given for these.

To create a Deque with capacity to store 2048 items without resizing, and that will not resize below space for 32 items when removing itmes: 

d := deque.NewList(2048, 32)

To create a Deque that has not yet allocated memory, but after it does will never resize to have space for less than 64 items: 

d := deque.NewList(0, 64)

Note that interface{} values supplied here are rounded up to the nearest power of 2.

func (*Deque[T]) At 

func (q *Deque[T]) At(i int) T

At returns the element at index i in the queue without removing the element from the queue. This method accepts only non-negative index values. At(0) refers to the first element and is the same as Front(). At(Len()-1) refers to the last element and is the same as Back(). If the index is invalid, the call panics.

The purpose of At is to allow Deque to serve as a more general purpose circular buffer, where items are only added to and removed from the ends of the deque, but may be read from T place within the deque. Consider the case of a fixed-size circular log buffer: A new entry is pushed onto one end and when full the oldest is popped from the other end. All the log entries in the buffer must be readable without altering the buffer contents.

func (*Deque[T]) Back 

func (q *Deque[T]) Back() T

Back returns the element at the back of the queue. This is the element that would be returned by PopBack(). This call panics if the queue is empty.

func (*Deque[T]) Cap 

func (q *Deque[T]) Cap() int

Cap returns the current capacity of the Deque.

func (*Deque[T]) Clear 

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

Clear removes all elements from the queue, but retains the current capacity. This is useful when repeatedly reusing the queue at high frequency to avoid GC during reuse. The queue will not be resized smaller as long as items are only added. Only when items are removed is the queue subject to getting resized smaller.

func (*Deque[T]) Front 

func (q *Deque[T]) Front() T

Front returns the element at the front of the queue. This is the element that would be returned by PopFront(). This call panics if the queue is empty.

func (*Deque[T]) IsEmpty 

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

func (*Deque[T]) Len 

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

Len returns the number of elements currently stored in the queue.

func (*Deque[T]) PopBack 

func (q *Deque[T]) PopBack() T

PopBack removes and returns the element from the back of the queue. Implements LIFO when used with PushBack(). If the queue is empty, the call panics.

func (*Deque[T]) PopFront 

func (q *Deque[T]) PopFront() T

PopFront removes and returns the element from the front of the queue. Implements FIFO when used with PushBack(). If the queue is empty, the call panics.

func (*Deque[T]) PushBack 

func (q *Deque[T]) PushBack(elem T)

PushBack appends an element to the back of the queue. Implements FIFO when elements are removed with PopFront(), and LIFO when elements are removed with PopBack().

func (*Deque[T]) PushFront 

func (q *Deque[T]) PushFront(elem T)

PushFront prepends an element to the front of the queue.

func (*Deque[T]) Rotate 

func (q *Deque[T]) Rotate(n int)

Rotate rotates the deque n steps front-to-back. If n is negative, rotates back-to-front. Having Deque provide Rotate() avoids resizing that could happen if implementing rotation using only Pop and Push methods.

func (*Deque[T]) Set 

func (q *Deque[T]) Set(i int, elem T)

Set puts the element at index i in the queue. Set shares the same purpose than At() but perform the opposite operation. The index i is the same index defined by At(). If the index is invalid, the call panics.

func (*Deque[T]) SetMinCapacity 

func (q *Deque[T]) SetMinCapacity(minCapacityExp uint)

SetMinCapacity sets a minimum capacity of 2^minCapacityExp. If the Value of the minimum capacity is less than or equal to the minimum allowed, then capacity is set to the minimum allowed. This may be called at anytime to set a new minimum capacity.

Setting a larger minimum capacity may be used to prevent resizing when the number of stored items changes frequently across a wide range.

type Float32Slice 

type Float32Slice []float32

func (Float32Slice) Len 

func (x Float32Slice) Len() int

func (Float32Slice) Less 

func (x Float32Slice) Less(i, j int) bool

func (Float32Slice) Swap 

func (x Float32Slice) Swap(i, j int)

type Float64Slice 

type Float64Slice = sort.Float64Slice

type Int16Slice 

type Int16Slice []int16

func (Int16Slice) Len 

func (x Int16Slice) Len() int

func (Int16Slice) Less 

func (x Int16Slice) Less(i, j int) bool

func (Int16Slice) Swap 

func (x Int16Slice) Swap(i, j int)

type Int32Slice 

type Int32Slice []int32

func (Int32Slice) Len 

func (x Int32Slice) Len() int

func (Int32Slice) Less 

func (x Int32Slice) Less(i, j int) bool

func (Int32Slice) Swap 

func (x Int32Slice) Swap(i, j int)

type Int64Slice 

type Int64Slice []int64

func (Int64Slice) Len 

func (x Int64Slice) Len() int

func (Int64Slice) Less 

func (x Int64Slice) Less(i, j int) bool

func (Int64Slice) Swap 

func (x Int64Slice) Swap(i, j int)

type Int8Slice 

type Int8Slice []int8

func (Int8Slice) Len 

func (x Int8Slice) Len() int

func (Int8Slice) Less 

func (x Int8Slice) Less(i, j int) bool

func (Int8Slice) Swap 

func (x Int8Slice) Swap(i, j int)

type IntSlice 

type IntSlice = sort.IntSlice

type Iterator 

type Iterator[T any] interface {
	// HasNext returns true if the iteration has more elements.
	HasNext() bool

	// Next returns the next element in the iteration.
	Next() T

	// Remove removes from the underlying collection the last element returned by this iterator.
	Remove()
}

type KeyValVisitor 

type KeyValVisitor[K, V any] func(key K, value V) bool

type LRUCache 

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

LRUCache LRU缓存 https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)

func NewLRUCache 

func NewLRUCache[K comparable, V any](size int, onEvicted func(key K, value V)) *LRUCache[K, V]

func (*LRUCache[K, V]) Cap 

func (c *LRUCache[K, V]) Cap() int

func (*LRUCache[K, V]) Contains 

func (c *LRUCache[K, V]) Contains(key K) bool

Contains 查看key是否存在，不移动链表

func (*LRUCache[K, V]) Get 

func (c *LRUCache[K, V]) Get(key K) (V, bool)

Get 获取key对应的值，并把其移动到链表头部

func (*LRUCache[K, V]) GetOldest 

func (c *LRUCache[K, V]) GetOldest() (key K, value V, ok bool)

GetOldest 获取最老的值（链表尾节点）

func (*LRUCache[K, V]) Keys 

func (c *LRUCache[K, V]) Keys() []K

Keys 返回所有的key（从旧到新）

func (*LRUCache[K, V]) Len 

func (c *LRUCache[K, V]) Len() int

func (*LRUCache[K, V]) Peek 

func (c *LRUCache[K, V]) Peek(key K) (V, bool)

Peek 获取key对应的值，不移动链表

func (*LRUCache[K, V]) Purge 

func (c *LRUCache[K, V]) Purge()

Purge 清除所有

func (*LRUCache[K, V]) Put 

func (c *LRUCache[K, V]) Put(key K, value V) bool

Put 把key-value加入到cache中，并移动到链表头部

func (*LRUCache[K, V]) Remove 

func (c *LRUCache[K, V]) Remove(key K) bool

Remove 把key从cache中删除

func (*LRUCache[K, V]) RemoveOldest 

func (c *LRUCache[K, V]) RemoveOldest() (key K, value V, ok bool)

RemoveOldest 删除最老的的key-Value，并返回

func (*LRUCache[K, V]) Resize 

func (c *LRUCache[K, V]) Resize(size int) int

Resize changes the cache size.

type LRUEntry 

type LRUEntry[K comparable, V any] struct {
	Key   K
	Value V
}

type List 

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

List represents a doubly linked list. The zero Value for List is an empty list ready to use.

func NewList 

func NewList[T any]() *List[T]

NewList returns an initialized list.

func (*List[T]) Back 

func (l *List[T]) Back() *ListElem[T]

Back returns the last element of list l or nil if the list is empty.

func (*List[T]) Front 

func (l *List[T]) Front() *ListElem[T]

Front returns the first element of list l or nil if the list is empty.

func (*List[T]) Init 

func (l *List[T]) Init() *List[T]

Init initializes or clears list l.

func (*List[T]) InsertAfter 

func (l *List[T]) InsertAfter(v T, mark *ListElem[T]) *ListElem[T]

InsertAfter inserts a new element e with Value v immediately after mark and returns e. If mark is not an element of l, the list is not modified. The mark must not be nil.

func (*List[T]) InsertBefore 

func (l *List[T]) InsertBefore(v T, mark *ListElem[T]) *ListElem[T]

InsertBefore inserts a new element e with Value v immediately before mark and returns e. If mark is not an element of l, the list is not modified. The mark must not be nil.

func (*List[T]) Len 

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

Len returns the number of elements of list l. The complexity is O(1).

func (*List[T]) MoveAfter 

func (l *List[T]) MoveAfter(e, mark *ListElem[T])

MoveAfter moves element e to its new position after mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.

func (*List[T]) MoveBefore 

func (l *List[T]) MoveBefore(e, mark *ListElem[T])

MoveBefore moves element e to its new position before mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.

func (*List[T]) MoveToBack 

func (l *List[T]) MoveToBack(e *ListElem[T])

MoveToBack moves element e to the back of list l. If e is not an element of l, the list is not modified. The element must not be nil.

func (*List[T]) MoveToFront 

func (l *List[T]) MoveToFront(e *ListElem[T])

MoveToFront moves element e to the front of list l. If e is not an element of l, the list is not modified. The element must not be nil.

func (*List[T]) PushBack 

func (l *List[T]) PushBack(v T) *ListElem[T]

PushBack inserts a new element e with Value v at the back of list l and returns e.

func (*List[T]) PushBackList 

func (l *List[T]) PushBackList(other *List[T])

PushBackList inserts a copy of another list at the back of list l. The lists l and other may be the same. They must not be nil.

func (*List[T]) PushFront 

func (l *List[T]) PushFront(v T) *ListElem[T]

PushFront inserts a new element e with Value v at the front of list l and returns e.

func (*List[T]) PushFrontList 

func (l *List[T]) PushFrontList(other *List[T])

PushFrontList inserts a copy of another list at the front of list l. The lists l and other may be the same. They must not be nil.

func (*List[T]) Remove 

func (l *List[T]) Remove(e *ListElem[T]) T

Remove removes e from l if e is an element of list l. It returns the element Value e.Value. The element must not be nil.

type ListElem 

type ListElem[T any] struct {

	// The Value stored with this element.
	Value T
	// contains filtered or unexported fields
}

ListElem is an element of a linked list.

func (*ListElem[T]) Next 

func (e *ListElem[T]) Next() *ListElem[T]

Next returns the next list element or nil.

func (*ListElem[T]) Prev 

func (e *ListElem[T]) Prev() *ListElem[T]

Prev returns the previous list element or nil.

type MapInterface 

type MapInterface[K comparable, V any] interface {
	Size() int
	Contains(K) bool
	Load(K) (V, bool)
	Store(key K, value V)
	LoadOrStore(key K, value V) (actual V, loaded bool)
	LoadAndDelete(key K) (value V, loaded bool)
	Delete(K)
	Range(func(key K, value V) (shouldContinue bool))
	Keys() []K
	Values() []V
	CloneMap() map[K]V
}

MapInterface is the interface SyncMap implements.

type MutexMap 

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

MutexMap is an implementation of mapInterface using a sync.RWMutex.

func (*MutexMap[K, V]) CloneMap 

func (m *MutexMap[K, V]) CloneMap() map[K]V

func (*MutexMap[K, V]) Contains 

func (m *MutexMap[K, V]) Contains(key K) bool

func (*MutexMap[K, V]) Delete 

func (m *MutexMap[K, V]) Delete(key K)

func (*MutexMap[K, V]) IsEmpty 

func (m *MutexMap[K, V]) IsEmpty() bool

func (*MutexMap[K, V]) Keys 

func (m *MutexMap[K, V]) Keys() []K

func (*MutexMap[K, V]) Load 

func (m *MutexMap[K, V]) Load(key K) (value V, ok bool)

func (*MutexMap[K, V]) LoadAndDelete 

func (m *MutexMap[K, V]) LoadAndDelete(key K) (value V, loaded bool)

func (*MutexMap[K, V]) LoadOrStore 

func (m *MutexMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)

func (*MutexMap[K, V]) Range 

func (m *MutexMap[K, V]) Range(f func(key K, value V) (shouldContinue bool))

func (*MutexMap[K, V]) Size 

func (m *MutexMap[K, V]) Size() int

Size returns the number of Key-Value mappings in this map.

func (*MutexMap[K, V]) Store 

func (m *MutexMap[K, V]) Store(key K, value V)

func (*MutexMap[K, V]) Values 

func (m *MutexMap[K, V]) Values() []V

type PQItem 

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

type Pair added in v1.0.12 

type Pair[T1, T2 any] struct {
	First  T1
	Second T2
}

Pair is a type that provides a way to store two heterogeneous objects as a single unit.

func MakePair added in v1.0.12 

func MakePair[T1, T2 any](a T1, b T2) Pair[T1, T2]

MakePair creates a Pair object, deducing the target type from the types of arguments

type PriorityQueue 

type PriorityQueue[T any] []*PQItem[T]

A PriorityQueue implements heap.Interface and holds Items.

func (PriorityQueue[T]) Len 

func (pq PriorityQueue[T]) Len() int

func (PriorityQueue[T]) Less 

func (pq PriorityQueue[T]) Less(i, j int) bool

func (*PriorityQueue[T]) Pop 

func (pq *PriorityQueue[T]) Pop() any

func (*PriorityQueue[T]) Push 

func (pq *PriorityQueue[T]) Push(x any)

func (PriorityQueue[T]) Swap 

func (pq PriorityQueue[T]) Swap(i, j int)

type Range added in v1.0.12 

type Range struct {
	Min int
	Max int
}

Range contains a min value and a max value

func ParseRange added in v1.0.12 

func ParseRange(text, sep string) Range

func (*Range) In added in v1.0.12 

func (r *Range) In(val int) bool

In returns true if the value is in the range

func (*Range) Mid added in v1.0.12 

func (r *Range) Mid() int

Mid returns the middle value of the range

func (*Range) Rand added in v1.0.12 

func (r *Range) Rand() int

Rand returns a random value in the range

type SortedSet 

type SortedSet[T comparable] struct {
	// contains filtered or unexported fields
}

SortedSet 跳表实现的有序字典

func NewSortedSet 

func NewSortedSet[T comparable](comparator Comparator[T]) *SortedSet[T]

func NewSortedSetCmp 

func NewSortedSetCmp[T cmp.Ordered]() *SortedSet[T]

func (*SortedSet[T]) Add 

func (s *SortedSet[T]) Add(ele T, score int64) bool

Add 添加或者更新一个元素的score

func (*SortedSet[T]) Count 

func (s *SortedSet[T]) Count(min, max int64) int

Count score在[min, max]之间的元素数量

func (*SortedSet[T]) GetRange 

func (s *SortedSet[T]) GetRange(start, end int, reverse bool) []T

GetRange 返回排名在[start, end]之间的所有元素

func (*SortedSet[T]) GetRangeByScore 

func (s *SortedSet[T]) GetRangeByScore(min, max int64, reverse bool) []T

GetRangeByScore 获取score在[min, max]之间的所有元素

func (*SortedSet[T]) GetRank 

func (s *SortedSet[T]) GetRank(ele T, reverse bool) int

GetRank 返回元素的排名，排名从0开始，如果元素不在zset里，返回-1

func (*SortedSet[T]) GetScore 

func (s *SortedSet[T]) GetScore(ele T) int64

GetScore 获取元素的score

func (*SortedSet[T]) Len 

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

func (*SortedSet[T]) Remove 

func (s *SortedSet[T]) Remove(ele T) bool

Remove 删除一个元素

func (*SortedSet[T]) RemoveRangeByRank 

func (s *SortedSet[T]) RemoveRangeByRank(start, end int) int

RemoveRangeByRank 删除排名在[start, end]之间的元素，排名从1开始

func (*SortedSet[T]) RemoveRangeByScore 

func (s *SortedSet[T]) RemoveRangeByScore(min, max int64) int

RemoveRangeByScore 删除score区间[min, max]的元素

type StringSlice 

type StringSlice = sort.StringSlice

type TreeEntry 

type TreeEntry[K comparable, V any] struct {
	Key   K
	Value V
	// contains filtered or unexported fields
}

func NewTreeEntry 

func NewTreeEntry[K comparable, V any](key K, val V, parent *TreeEntry[K, V]) *TreeEntry[K, V]

func (*TreeEntry[K, V]) GetKey 

func (e *TreeEntry[K, V]) GetKey() K

func (*TreeEntry[K, V]) GetValue 

func (e *TreeEntry[K, V]) GetValue() V

func (*TreeEntry[K, V]) Height 

func (e *TreeEntry[K, V]) Height() int

func (*TreeEntry[K, V]) SetValue 

func (e *TreeEntry[K, V]) SetValue(val V) V

func (*TreeEntry[K, V]) Size 

func (e *TreeEntry[K, V]) Size() int

Size returns the number of elements stored in the subtree.

type TreeMap 

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

TreeMap is a Red-Black tree based map implementation. The map is sorted by a comparator passed to its constructor. This implementation provides guaranteed log(n) time cost for the Contains(), Get(), Put() and Remove() operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's <Introduction to Algorithms>.

func NewTreeMap 

func NewTreeMap[K comparable, V any](comparator Comparator[K]) *TreeMap[K, V]

func NewTreeMapCmp 

func NewTreeMapCmp[K cmp.Ordered, V any]() *TreeMap[K, V]

func TreeMapOf 

func TreeMapOf[M ~map[K]V, K cmp.Ordered, V any](m M) *TreeMap[K, V]

func (*TreeMap[K, V]) CeilingEntry 

func (m *TreeMap[K, V]) CeilingEntry(key K) *TreeEntry[K, V]

CeilingEntry gets the entry corresponding to the specified Key; returns the entry for the least Key greater than the specified Key if not exist.

func (*TreeMap[K, V]) CeilingKey 

func (m *TreeMap[K, V]) CeilingKey(key K) (K, bool)

CeilingKey gets the specified Key, return the least Key greater than the specified Key if not exist.

func (*TreeMap[K, V]) Clear 

func (m *TreeMap[K, V]) Clear()

Clear removes all the mappings from this map.

func (*TreeMap[K, V]) CloneMap 

func (m *TreeMap[K, V]) CloneMap() map[K]V

func (*TreeMap[K, V]) Contains 

func (m *TreeMap[K, V]) Contains(key K) bool

Contains return true if this map contains a mapping for the specified Key

func (*TreeMap[K, V]) Delete 

func (m *TreeMap[K, V]) Delete(key K)

func (*TreeMap[K, V]) FirstEntry 

func (m *TreeMap[K, V]) FirstEntry() *TreeEntry[K, V]

func (*TreeMap[K, V]) FirstKey 

func (m *TreeMap[K, V]) FirstKey() (K, bool)

FirstKey returns the first Key in the TreeMap (according to the Key's order)

func (*TreeMap[K, V]) FloorEntry 

func (m *TreeMap[K, V]) FloorEntry(key K) *TreeEntry[K, V]

FloorEntry gets the entry corresponding to the specified Key; if no such entry exists, returns the entry for the greatest Key less than the specified Key;

func (*TreeMap[K, V]) FloorKey 

func (m *TreeMap[K, V]) FloorKey(key K) (K, bool)

FloorKey gets the specified Key, returns the greatest Key less than the specified Key if not exist.

func (*TreeMap[K, V]) Get 

func (m *TreeMap[K, V]) Get(key K) (V, bool)

Get returns the Value to which the specified Key is mapped, or nil if this map contains no mapping for the Key.

func (*TreeMap[K, V]) GetEntry 

func (m *TreeMap[K, V]) GetEntry(key K) *TreeEntry[K, V]

func (*TreeMap[K, V]) GetOrDefault 

func (m *TreeMap[K, V]) GetOrDefault(key K, defVal V) V

GetOrDefault returns the Value to which the specified Key is mapped, or `defaultValue` if this map contains no mapping for the Key.

func (*TreeMap[K, V]) HigherEntry 

func (m *TreeMap[K, V]) HigherEntry(key K) *TreeEntry[K, V]

HigherEntry gets the entry for the least Key greater than the specified Key

func (*TreeMap[K, V]) HigherKey 

func (m *TreeMap[K, V]) HigherKey(key K) (K, bool)

HigherKey returns the least Key greater than the specified Key

func (*TreeMap[K, V]) IsEmpty 

func (m *TreeMap[K, V]) IsEmpty() bool

func (*TreeMap[K, V]) IterBackwards 

func (m *TreeMap[K, V]) IterBackwards() iter.Seq2[K, V]

func (*TreeMap[K, V]) IterSeq 

func (m *TreeMap[K, V]) IterSeq() iter.Seq2[K, V]

func (*TreeMap[K, V]) Keys 

func (m *TreeMap[K, V]) Keys() []K

Keys return list of all keys

func (*TreeMap[K, V]) LastEntry 

func (m *TreeMap[K, V]) LastEntry() *TreeEntry[K, V]

func (*TreeMap[K, V]) LastKey 

func (m *TreeMap[K, V]) LastKey() (K, bool)

LastKey returns the last Key in the TreeMap (according to the Key's order)

func (*TreeMap[K, V]) Load 

func (m *TreeMap[K, V]) Load(key K) (V, bool)

func (*TreeMap[K, V]) LoadAndDelete 

func (m *TreeMap[K, V]) LoadAndDelete(key K) (value V, loaded bool)

LoadAndDelete deletes the Value for a Key, returning the previous Value if any. The loaded result reports whether the Key was present.

func (*TreeMap[K, V]) LoadOrStore 

func (m *TreeMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)

LoadOrStore returns the existing Value for the Key if present. Otherwise, it stores and returns the given Value. The loaded result is true if the Value was loaded, false if stored.

func (*TreeMap[K, V]) Put 

func (m *TreeMap[K, V]) Put(key K, value V) V

Put associates the specified Value with the specified Key in this map. If the map previously contained a mapping for the Key, the old Value is replaced.

func (*TreeMap[K, V]) PutIfAbsent 

func (m *TreeMap[K, V]) PutIfAbsent(key K, value V) V

PutIfAbsent put a Key-Value pair if the Key is not already associated with a Value.

func (*TreeMap[K, V]) Range 

func (m *TreeMap[K, V]) Range(visit func(key K, value V) (shouldContinue bool))

Range calls f sequentially for each Key and Value present in the map. If f returns false, range stops the iteration.

func (*TreeMap[K, V]) Remove 

func (m *TreeMap[K, V]) Remove(key K) bool

Remove removes the mapping for this Key from this TreeMap if present.

func (*TreeMap[K, V]) RootEntry 

func (m *TreeMap[K, V]) RootEntry() *TreeEntry[K, V]

func (*TreeMap[K, V]) Size 

func (m *TreeMap[K, V]) Size() int

Size returns the number of Key-Value mappings in this map.

func (*TreeMap[K, V]) Store 

func (m *TreeMap[K, V]) Store(key K, value V)

Store sets the Value for a Key, equivalent to Put.

func (*TreeMap[K, V]) String 

func (m *TreeMap[K, V]) String() string

func (*TreeMap[K, V]) Swap 

func (m *TreeMap[K, V]) Swap(key K, value V) (previous V, loaded bool)

Swap swaps the Value for a Key and returns the previous Value if any. The loaded result reports whether the Key was present.

func (*TreeMap[K, V]) Values 

func (m *TreeMap[K, V]) Values() []V

Values return list of all values

type Uint16Slice 

type Uint16Slice []uint16

func (Uint16Slice) Len 

func (x Uint16Slice) Len() int

func (Uint16Slice) Less 

func (x Uint16Slice) Less(i, j int) bool

func (Uint16Slice) Swap 

func (x Uint16Slice) Swap(i, j int)

type Uint32Slice 

type Uint32Slice []uint32

func (Uint32Slice) Len 

func (x Uint32Slice) Len() int

func (Uint32Slice) Less 

func (x Uint32Slice) Less(i, j int) bool

func (Uint32Slice) Swap 

func (x Uint32Slice) Swap(i, j int)

type Uint64Slice 

type Uint64Slice []uint64

func (Uint64Slice) Len 

func (x Uint64Slice) Len() int

func (Uint64Slice) Less 

func (x Uint64Slice) Less(i, j int) bool

func (Uint64Slice) Swap 

func (x Uint64Slice) Swap(i, j int)

type Uint8Slice 

type Uint8Slice []uint8

func (Uint8Slice) Len 

func (x Uint8Slice) Len() int

func (Uint8Slice) Less 

func (x Uint8Slice) Less(i, j int) bool

func (Uint8Slice) Swap 

func (x Uint8Slice) Swap(i, j int)

type UintSlice 

type UintSlice []uint

func (UintSlice) Len 

func (x UintSlice) Len() int

func (UintSlice) Less 

func (x UintSlice) Less(i, j int) bool

func (UintSlice) Swap 

func (x UintSlice) Swap(i, j int)

type Visitor 

type Visitor[V any] func(value V) bool

type ZSkipList 

type ZSkipList[T comparable] struct {
	// contains filtered or unexported fields
}

ZSkipList 带索引的排序链表

func NewZSkipList 

func NewZSkipList[T comparable](comparator Comparator[T]) *ZSkipList[T]

func NewZSkipListCmp 

func NewZSkipListCmp[T cmp.Ordered]() *ZSkipList[T]

func (*ZSkipList[T]) Clear 

func (zsl *ZSkipList[T]) Clear()

func (*ZSkipList[T]) Delete 

func (zsl *ZSkipList[T]) Delete(score int64, ele T) *ZSkipListNode[T]

Delete 删除对应score的节点

func (*ZSkipList[T]) DeleteRangeByRank 

func (zsl *ZSkipList[T]) DeleteRangeByRank(start, end int, dict map[T]int64) int

DeleteRangeByRank delete nodes with rank [rank >= start && rank <= end]

func (*ZSkipList[T]) DeleteRangeByScore 

func (zsl *ZSkipList[T]) DeleteRangeByScore(min, max int64, dict map[T]int64) int

DeleteRangeByScore delete nodes with [score >= min && score <= max]

func (*ZSkipList[T]) Dump 

func (zsl *ZSkipList[T]) Dump(w io.Writer)

func (*ZSkipList[T]) FirstInRange 

func (zsl *ZSkipList[T]) FirstInRange(min, max int64) *ZSkipListNode[T]

FirstInRange find the first node that is contained in the specified range. Returns NULL when no element is contained in the range.

func (*ZSkipList[T]) GetElementByRank 

func (zsl *ZSkipList[T]) GetElementByRank(rank int) *ZSkipListNode[T]

GetElementByRank 根据排名获得节点，排名从1开始

func (*ZSkipList[T]) GetRank 

func (zsl *ZSkipList[T]) GetRank(score int64, ele T) int

GetRank 获取score所在的排名，排名从1开始

func (*ZSkipList[T]) HeadNode 

func (zsl *ZSkipList[T]) HeadNode() *ZSkipListNode[T]

func (*ZSkipList[T]) Height 

func (zsl *ZSkipList[T]) Height() int

func (*ZSkipList[T]) Insert 

func (zsl *ZSkipList[T]) Insert(score int64, ele T) *ZSkipListNode[T]

Insert 插入一个不存在的节点

func (*ZSkipList[T]) IsInRange 

func (zsl *ZSkipList[T]) IsInRange(min, max int64) bool

IsInRange Returns if there is a part of the zset is in range.

func (*ZSkipList[T]) LastInRange 

func (zsl *ZSkipList[T]) LastInRange(min, max int64) *ZSkipListNode[T]

LastInRange find the last node that is contained in the specified range. Returns NULL when no element is contained in the range.

func (*ZSkipList[T]) Len 

func (zsl *ZSkipList[T]) Len() int

func (*ZSkipList[T]) Range 

func (zsl *ZSkipList[T]) Range(action func(score int64, elem T))

func (*ZSkipList[T]) String 

func (zsl *ZSkipList[T]) String() string

func (*ZSkipList[T]) TailNode 

func (zsl *ZSkipList[T]) TailNode() *ZSkipListNode[T]

func (*ZSkipList[T]) ToMap 

func (zsl *ZSkipList[T]) ToMap() map[T]int64

func (*ZSkipList[T]) UpdateScore 

func (zsl *ZSkipList[T]) UpdateScore(ele T, curScore, newScore int64) *ZSkipListNode[T]

UpdateScore 更新分数

type ZSkipListNode 

type ZSkipListNode[T comparable] struct {
	Ele   T
	Score int64
	// contains filtered or unexported fields
}

ZSkipListNode

func (*ZSkipListNode[T]) Before 

func (n *ZSkipListNode[T]) Before() *ZSkipListNode[T]

func (*ZSkipListNode[T]) Next 

func (n *ZSkipListNode[T]) Next() *ZSkipListNode[T]

Next return next forward pointer

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.