collections

package
v0.2.5 Latest Latest
Warning

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

 Go to latest Published: Apr 21, 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 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 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 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 U32Array 

type U32Array []uint32

func (U32Array) Len 

func (x U32Array) Len() int

func (U32Array) Less 

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

func (U32Array) Swap 

func (x U32Array) 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.