collections

package
v1.3.21 Latest Latest
Warning

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

 Go to latest Published: Nov 17, 2021 License: BSD-3-Clause Imports: 10 Imported by: 0

Documentation

Index

Examples

Constants

View Source 
const (
	ZSKIPLIST_MAXLEVEL = 12   // Should be enough
	ZSKIPLIST_P        = 0.25 // Skiplist P = 1/4
)
View Source 
const (
	ReplicaCount = 20 // 虚拟节点数量
)
View Source 
const WildCardStar = '*' // '\u002A'

通配符

Variables

This section is empty.

Functions

func HeapSort 

func HeapSort(data sort.Interface)

堆排序

func InsertionSort 

func InsertionSort(data sort.Interface)

插入排序

Types

type BitSet 

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

定长bitset

func BitSetFrom 

func BitSetFrom(bitsize int, array []uint64) *BitSet

func NewBitSet 

func NewBitSet(bitsize int) *BitSet

func (*BitSet) Clear 

func (bs *BitSet) Clear(i int) bool

设置bits[i]为0

func (*BitSet) ClearAll 

func (bs *BitSet) ClearAll()

清零所有位

func (*BitSet) Count 

func (bs *BitSet) Count() int

置为1的位的数量

func (*BitSet) Flip 

func (bs *BitSet) Flip(i int) bool

反转第i位

func (BitSet) FormattedString 

func (bs BitSet) FormattedString(width int) string

func (BitSet) HashCode 

func (bs BitSet) HashCode() string

func (*BitSet) Set 

func (bs *BitSet) Set(i int) bool

设置bits[i]为1

func (*BitSet) Size 

func (bs *BitSet) Size() int

bit的数量

func (BitSet) String 

func (bs BitSet) String() string

func (*BitSet) Test 

func (bs *BitSet) Test(i int) bool

查看bits[i]是否为1

type Comparable 

type Comparable interface {
	// a.CompareTo(b) < 0 表明a < b
	// a.CompareTo(b) > 0 表明a > b
	// a.CompareTo(b) == 0 表明a == b
	//
	// 内部实现要符合结合律:
	// (a.compareTo(b) > 0 && b.compareTo(c) > 0) implies a.compareTo(c) > 0
	CompareTo(Comparable) int
}

丐版java.lang.Comparable https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/lang/Comparable.java

type Consistent 

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

一致性hash

func NewConsistent 

func NewConsistent() *Consistent

func (*Consistent) AddNode 

func (c *Consistent) AddNode(node string)

添加一个节点

func (*Consistent) GetNodeBy 

func (c *Consistent) GetNodeBy(key string) string

获取一个节点

func (*Consistent) RemoveNode 

func (c *Consistent) RemoveNode(node string)

type Deque 

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

func NewDeque 

func NewDeque(size ...int) *Deque

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.New(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.New(0, 64)

Note that any values supplied here are rounded up to the nearest power of 2.

func (*Deque) At 

func (q *Deque) At(i int) interface{}

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 any 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) Back 

func (q *Deque) Back() interface{}

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

func (q *Deque) Cap() int

Cap returns the current capacity of the Deque.

func (*Deque) Clear 

func (q *Deque) 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) Front 

func (q *Deque) Front() interface{}

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

func (q *Deque) Len() int

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

func (*Deque) PopBack 

func (q *Deque) PopBack() interface{}

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

func (q *Deque) PopFront() interface{}

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

func (q *Deque) PushBack(elem interface{})

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

func (q *Deque) PushFront(elem interface{})

PushFront prepends an element to the front of the queue.

func (*Deque) Rotate 

func (q *Deque) 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) Set 

func (q *Deque) Set(i int, elem interface{})

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

func (q *Deque) 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 Float32Array 

type Float32Array []float32

func (Float32Array) Len 

func (x Float32Array) Len() int

func (Float32Array) Less 

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

func (Float32Array) Swap 

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

type Float64Array 

type Float64Array []float64

func (Float64Array) Len 

func (x Float64Array) Len() int

func (Float64Array) Less 

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

func (Float64Array) Swap 

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

type HashTrie 

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

哈希表实现的字典树

func NewHashTrie 

func NewHashTrie() *HashTrie

func (*HashTrie) AddWord 

func (t *HashTrie) AddWord(word string)

添加到单词表

func (*HashTrie) Contains 

func (t *HashTrie) Contains(word string) bool

模糊匹配（包含通配符）

func (*HashTrie) ExactMatch 

func (t *HashTrie) ExactMatch(word string) bool

精确匹配

func (*HashTrie) Filter 

func (t *HashTrie) Filter(word string) string

将敏感字符替换为星号

func (*HashTrie) Remove 

func (t *HashTrie) Remove(word string) bool

从单词表中删除一个单词

func (*HashTrie) Reset 

func (t *HashTrie) Reset()

func (*HashTrie) String 

func (t *HashTrie) String() string

func (*HashTrie) WordsCount 

func (t *HashTrie) WordsCount() int

单词表数量

type IDSet 

type IDSet []int32

无序整数集合，用于存储少量数据且插入/删除多于查询的场合

func (IDSet) Delete 

func (s IDSet) Delete(id int32) IDSet

删除

func (IDSet) Find 

func (s IDSet) Find(id int32) int

func (IDSet) Has 

func (s IDSet) Has(id int32) bool

func (IDSet) Insert 

func (s IDSet) Insert(id int32) IDSet

插入，需要提前判断是否已经存在

func (IDSet) PutIfAbsent 

func (s IDSet) PutIfAbsent(id int32) IDSet

type Int16Array 

type Int16Array []uint16

func (Int16Array) Len 

func (x Int16Array) Len() int

func (Int16Array) Less 

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

func (Int16Array) Swap 

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

type Int32Array 

type Int32Array []int32

func (Int32Array) Len 

func (x Int32Array) Len() int

func (Int32Array) Less 

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

func (Int32Array) Swap 

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

type Int64Array 

type Int64Array []int64

func (Int64Array) Len 

func (x Int64Array) Len() int

func (Int64Array) Less 

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

func (Int64Array) Swap 

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

type Int8Array 

type Int8Array []int8

func (Int8Array) Len 

func (x Int8Array) Len() int

func (Int8Array) Less 

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

func (Int8Array) Swap 

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

type IntArray 

type IntArray []int

func (IntArray) Len 

func (x IntArray) Len() int

func (IntArray) Less 

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

func (IntArray) Swap 

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

type LRUCache 

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

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

func NewLRUCache 

func NewLRUCache(capacity int) *LRUCache

func (*LRUCache) Cap 

func (c *LRUCache) Cap() int

func (*LRUCache) Exist 

func (c *LRUCache) Exist(key string) bool

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

func (*LRUCache) Get 

func (c *LRUCache) Get(key string) (interface{}, bool)

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

func (*LRUCache) GetOldest 

func (c *LRUCache) GetOldest() (key string, value interface{}, ok bool)

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

func (*LRUCache) Keys 

func (c *LRUCache) Keys() []string

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

func (*LRUCache) Len 

func (c *LRUCache) Len() int

func (*LRUCache) Peek 

func (c *LRUCache) Peek(key string) (interface{}, bool)

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

func (*LRUCache) Put 

func (c *LRUCache) Put(key string, value interface{}) bool

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

func (*LRUCache) Remove 

func (c *LRUCache) Remove(key string) bool

把key从cache中删除

func (*LRUCache) RemoveOldest 

func (c *LRUCache) RemoveOldest() (string, interface{}, bool)

删除最老的的key-value，并返回

func (*LRUCache) Reset 

func (c *LRUCache) Reset()

重置cache

type LRUEntry 

type LRUEntry struct {
	Key   string
	Value interface{}
}

type OrderedIDSet 

type OrderedIDSet []int32

用数组实现的有序数字集合，仅用于存储少量数据且查询多过插入/删除的场合

func (OrderedIDSet) Delete 

func (s OrderedIDSet) Delete(id int32) OrderedIDSet

删除

func (OrderedIDSet) Find 

func (s OrderedIDSet) Find(id int32) int

查询使用二分查找

func (OrderedIDSet) Has 

func (s OrderedIDSet) Has(id int32) bool

func (OrderedIDSet) Insert 

func (s OrderedIDSet) Insert(id int32) OrderedIDSet

插入后保持有序

type Queue 

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

Queue represents an unbounded, dynamically growing FIFO queue. The zero value for queue is an empty queue ready to use. see https://github.com/golang/go/issues/27935

func NewQueue 

func NewQueue() *Queue

func (*Queue) Front 

func (q *Queue) Front() (interface{}, bool)

Front returns the first element of queue q or nil if the queue is empty. The second, bool result indicates whether a valid value was returned; 

if the queue is empty, false will be returned.

The complexity is O(1).

func (*Queue) Init 

func (q *Queue) Init() *Queue

Init initializes or clears queue q.

func (*Queue) Len 

func (q *Queue) Len() int

func (*Queue) Pop 

func (q *Queue) Pop() (interface{}, bool)

Pop retrieves and removes the current element from the queue. The second, bool result indicates whether a valid value was returned; 

if the queue is empty, false will be returned.

The complexity is O(1).

func (*Queue) Push 

func (q *Queue) Push(v interface{})

Push adds a value to the queue. The complexity is O(1).

type SortedSet 

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

跳表实现的有序字典

func NewSortedSet 

func NewSortedSet() *SortedSet

func (*SortedSet) Add 

func (s *SortedSet) Add(ele Comparable, score int64) bool

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

func (*SortedSet) Count 

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

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

func (*SortedSet) GetRange 

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

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

func (*SortedSet) GetRangeByScore 

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

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

func (*SortedSet) GetRank 

func (s *SortedSet) GetRank(ele Comparable, reverse bool) int

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

func (*SortedSet) GetScore 

func (s *SortedSet) GetScore(ele Comparable) int64

获取元素的score

func (*SortedSet) Len 

func (s *SortedSet) Len() int

func (*SortedSet) Remove 

func (s *SortedSet) Remove(ele Comparable) bool

删除一个元素

func (*SortedSet) RemoveRangeByRank 

func (s *SortedSet) RemoveRangeByRank(start, end int) int

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

func (*SortedSet) RemoveRangeByScore 

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

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

type StringArray 

type StringArray []string

func (StringArray) Len 

func (x StringArray) Len() int

func (StringArray) Less 

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

func (StringArray) Swap 

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

type Uint16Array 

type Uint16Array []uint16

func (Uint16Array) Len 

func (x Uint16Array) Len() int

func (Uint16Array) Less 

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

func (Uint16Array) Swap 

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

type Uint32Array 

type Uint32Array []uint32

func (Uint32Array) Len 

func (x Uint32Array) Len() int

func (Uint32Array) Less 

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

func (Uint32Array) Swap 

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

type Uint64Array 

type Uint64Array []uint64

func (Uint64Array) Len 

func (x Uint64Array) Len() int

func (Uint64Array) Less 

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

func (Uint64Array) Swap 

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

type Uint8Array 

type Uint8Array []uint8

func (Uint8Array) Len 

func (x Uint8Array) Len() int

func (Uint8Array) Less 

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

func (Uint8Array) Swap 

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

type UintArray 

type UintArray []uint

func (UintArray) Len 

func (x UintArray) Len() int

func (UintArray) Less 

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

func (UintArray) Swap 

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

type ZSkipList 

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

带索引的排序链表

Example 
var playerMap = make(map[int64]*testPlayer)
var zset = NewSortedSet()

//简单的测试角色数据
var p1 = &testPlayer{Uid: 1001, Level: 12, Point: 2012}
var p2 = &testPlayer{Uid: 1002, Level: 13, Point: 2015}
var p3 = &testPlayer{Uid: 1003, Level: 14, Point: 2014}
var p4 = &testPlayer{Uid: 1004, Level: 11, Point: 2014}
var p5 = &testPlayer{Uid: 1005, Level: 14, Point: 2011}
playerMap[p1.Uid] = p1
playerMap[p2.Uid] = p2
playerMap[p3.Uid] = p3
playerMap[p4.Uid] = p4
playerMap[p5.Uid] = p5

//插入角色数据到zskiplist
for _, v := range playerMap {
	zset.Add(v, v.Point)
}

//打印调试信息
// fmt.Printf("%v\n", zset.zsl)

//获取角色的排行信息
var rank = zset.GetRank(p1, false) // in ascend order
var myRank = zset.Len() - rank + 1 // get descend rank
fmt.Printf("rank of %d: %d\n", p1.Uid, myRank)

//根据排行获取角色信息
//var node = zset.GetRank(rank)
//var player = playerMap[node.Obj.Uuid()]
//fmt.Printf("rank at %d is: %s\n", rank, player.name)
//
////遍历整个zskiplist
//zsl.Walk(true, func(rank int, v RankInterface) bool {
//	fmt.Printf("rank %d: %v", rank, v)
//	return true
//})
//
////从zset中删除p1
//if !zset.Remove(p1) {
//	// error handling
//}
//
//p1.score += 10
//if zset.Insert(p1.score, p1) == nil {
//	// error handling
//}

Output:

func NewZSkipList 

func NewZSkipList() *ZSkipList

func (*ZSkipList) Delete 

func (zsl *ZSkipList) Delete(score int64, ele Comparable) *ZSkipListNode

删除对应score的节点

func (*ZSkipList) DeleteRangeByRank 

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

删除排名在[start-end]之间的节点，排名从1开始

func (*ZSkipList) DeleteRangeByScore 

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

删除score在[min-max]之间的节点

func (*ZSkipList) Dump 

func (zsl *ZSkipList) Dump(w io.Writer)

Dump dump whole list to w, mostly for debug usage

func (*ZSkipList) FirstInRange 

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

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

func (*ZSkipList) GetElementByRank 

func (zsl *ZSkipList) GetElementByRank(rank int) *ZSkipListNode

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

func (*ZSkipList) GetRank 

func (zsl *ZSkipList) GetRank(score int64, ele Comparable) int

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

func (*ZSkipList) HeadNode 

func (zsl *ZSkipList) HeadNode() *ZSkipListNode

头结点

func (*ZSkipList) Height 

func (zsl *ZSkipList) Height() int

链表的层级

func (*ZSkipList) Insert 

func (zsl *ZSkipList) Insert(score int64, ele Comparable) *ZSkipListNode

插入一个不存在的节点

func (*ZSkipList) IsInRange 

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

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

func (*ZSkipList) LastInRange 

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

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

func (*ZSkipList) Len 

func (zsl *ZSkipList) Len() int

链表的节点数量

func (ZSkipList) String 

func (zsl ZSkipList) String() string

func (*ZSkipList) TailNode 

func (zsl *ZSkipList) TailNode() *ZSkipListNode

尾节点

type ZSkipListNode 

type ZSkipListNode struct {
	Ele   Comparable
	Score int64
	// contains filtered or unexported fields
}

list node

func (*ZSkipListNode) Before 

func (n *ZSkipListNode) Before() *ZSkipListNode

func (*ZSkipListNode) Next 

func (n *ZSkipListNode) Next() *ZSkipListNode

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.