Documentation ¶
Overview ¶
Package sortedset provides the data-struct allows fast access the element in set by key or by score(order). It is inspired by Sorted Set from Redis.
Introduction ¶
Every node in the set is associated with these properties.
type SortedSetNode struct { key string // unique key of this node value interface{} // associated data score SCORE // int64 score to determine the order of this node in the set }
Each node in the set is associated with a key. While keys are unique, scores may be repeated. Nodes are taken in order (from low score to high score) instead of ordered afterwards. If scores are the same, the node is ordered by its key in lexicographic order. Each node in the set also can be accessed by rank, which represents the position in the sorted set.
Sorted Set is implemented basing on skip list and hash map internally. With sorted sets you can add, remove, or update nodes in a very fast way (in a time proportional to the logarithm of the number of nodes). You can also get ranges by score or by rank (position) in a very fast way. Accessing the middle of a sorted set is also very fast, so you can use Sorted Sets as a smart list of non repeating nodes where you can quickly access everything you need: nodes in order, fast existence test, fast access to nodes in the middle!
Use Case ¶
A typical use case of sorted set is a leader board in a massive online game, where every time a new score is submitted you update it using AddOrUpdate() method. You can easily take the top users using GetByRankRange() method, you can also, given an user id, return its rank in the listing using FindRank() method. Using FindRank() and GetByRankRange() together you can show users with a score similar to a given user. All very quickly.
Examples
// create a new set set := sortedset.New() // fill in new node set.AddOrUpdate("a", 89, "Kelly") set.AddOrUpdate("b", 100, "Staley") set.AddOrUpdate("c", 100, "Jordon") set.AddOrUpdate("d", -321, "Park") set.AddOrUpdate("e", 101, "Albert") set.AddOrUpdate("f", 99, "Lyman") set.AddOrUpdate("g", 99, "Singleton") set.AddOrUpdate("h", 70, "Audrey") // update an existing node by key set.AddOrUpdate("e", 99, "ntrnrt") // get the node by key set.GetByKey("b") // remove node by key set.Remove("b") // get the number of nodes in this set set.GetCount() // find the rank(postion) in the set. set.FindRank("d") // return 1 here // get and remove the node with minimum score set.PopMin() // get the node with maximum score set.PeekMax() // get the node at rank 1 (the node with minimum score) set.GetByRank(1, false) // get & remove the node at rank -1 (the node with maximum score) set.GetByRank(-1, true) // get the node with the 2nd highest maximum score set.GetByRank(-2, false) // get nodes with in rank range [1, -1], that is all nodes actually set.GetByRankRange(1, -1, false) // get & remove the 2nd/3rd nodes in reserve order set.GetByRankRange(-2, -3, true) // get the nodes whose score are within the interval [60,100] set.GetByScoreRange(60, 100, nil) // get the nodes whose score are within the interval (60,100] set.GetByScoreRange(60, 100, &GetByScoreRangeOptions{ ExcludeStart: true, }) // get the nodes whose score are within the interval [60,100) set.GetByScoreRange(60, 100, &GetByScoreRangeOptions{ ExcludeEnd: true, }) // get the nodes whose score are within the interval [60,100] in reverse order set.GetByScoreRange(100, 60, nil) // get the top 2 nodes with lowest scores within the interval [60,100] set.GetByScoreRange(60, 100, &GetByScoreRangeOptions{ Limit: 2, }) // get the top 2 nodes with highest scores within the interval [60,100] set.GetByScoreRange(100, 60, &GetByScoreRangeOptions{ Limit: 2, }) // get the top 2 nodes with highest scores within the interval (60,100) set.GetByScoreRange(100, 60, &GetByScoreRangeOptions{ Limit: 2, ExcludeStart: true, ExcludeEnd: true, })
Index ¶
- Constants
- type Float
- type GetByScoreRangeOptions
- type Indexable
- type Integer
- type Numeric
- type Ordered
- type Signed
- type SortedSet
- func (s *SortedSet[K, V, ScoreType]) AddOrUpdate(key K, score ScoreType, value V) bool
- func (s *SortedSet[K, V, ScoreType]) FindRank(key K) int
- func (s *SortedSet[K, V, ScoreType]) GetByKey(key K) *SortedSetNode[K, V, ScoreType]
- func (s *SortedSet[K, V, ScoreType]) GetByRank(rank int, remove bool) *SortedSetNode[K, V, ScoreType]
- func (s *SortedSet[K, V, ScoreType]) GetByRankRange(start int, end int, remove bool) []*SortedSetNode[K, V, ScoreType]
- func (s *SortedSet[K, V, ScoreType]) GetByScoreRange(start ScoreType, end ScoreType, options *GetByScoreRangeOptions) []*SortedSetNode[K, V, ScoreType]
- func (s *SortedSet[K, V, ScoreType]) GetCount() int
- func (s *SortedSet[K, V, ScoreType]) IterFuncByRankRange(start int, end int, fn func(key K, value V) bool)
- func (s *SortedSet[K, V, ScoreType]) PeekMax() *SortedSetNode[K, V, ScoreType]
- func (s *SortedSet[K, V, ScoreType]) PeekMin() *SortedSetNode[K, V, ScoreType]
- func (s *SortedSet[K, V, ScoreType]) PopMax() *SortedSetNode[K, V, ScoreType]
- func (s *SortedSet[K, V, ScoreType]) PopMin() *SortedSetNode[K, V, ScoreType]
- func (s *SortedSet[K, V, ScoreType]) Remove(key K) *SortedSetNode[K, V, ScoreType]
- type SortedSetLevel
- type SortedSetNode
- type Unsigned
Constants ¶
const SKIPLIST_MAXLEVEL = 32 /* Should be enough for 2^32 elements */
const SKIPLIST_P = 0.25 /* Skiplist P = 1/4 */
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Float ¶
Float is a constraint that permits any floating-point type. If future releases of Go add new predeclared floating-point types, this constraint will be modified to include them.
type GetByScoreRangeOptions ¶
type Integer ¶
Integer is a constraint that permits any integer type. If future releases of Go add new predeclared integer types, this constraint will be modified to include them.
type Ordered ¶
Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >. If future releases of Go add new ordered types, this constraint will be modified to include them.
type Signed ¶
Signed is a constraint that permits any signed integer type. If future releases of Go add new predeclared signed integer types, this constraint will be modified to include them.
type SortedSet ¶
type SortedSet[K Indexable, V any, ScoreType constraints.Ordered] struct { // contains filtered or unexported fields }
func NewSortedSet ¶
func NewSortedSet[K Indexable, V any, ScoreType constraints.Ordered]() *SortedSet[K, V, ScoreType]
NewSortedSet Create a new SortedSet
func (*SortedSet[K, V, ScoreType]) AddOrUpdate ¶
Add an element into the sorted set with specific key / value / score. if the element is added, s method returns true; otherwise false means updated
Time complexity of s method is : O(log(N))
func (*SortedSet[K, V, ScoreType]) FindRank ¶
FindRank Find the rank of the node specified by key Note that the rank is 1-based integer. Rank 1 means the first node
If the node is not found, 0 is returned. Otherwise rank(> 0) is returned
Time complexity of s method is : O(log(N))
func (*SortedSet[K, V, ScoreType]) GetByKey ¶
func (s *SortedSet[K, V, ScoreType]) GetByKey(key K) *SortedSetNode[K, V, ScoreType]
Get node by key
If node is not found, nil is returned Time complexity : O(1)
func (*SortedSet[K, V, ScoreType]) GetByRank ¶
func (s *SortedSet[K, V, ScoreType]) GetByRank(rank int, remove bool) *SortedSetNode[K, V, ScoreType]
Get node by rank. Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node;
If remove is true, the returned nodes are removed If node is not found at specific rank, nil is returned
Time complexity of s method is : O(log(N))
func (*SortedSet[K, V, ScoreType]) GetByRankRange ¶
func (s *SortedSet[K, V, ScoreType]) GetByRankRange(start int, end int, remove bool) []*SortedSetNode[K, V, ScoreType]
Get nodes within specific rank range [start, end] Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node;
If start is greater than end, the returned array is in reserved order If remove is true, the returned nodes are removed
Time complexity of s method is : O(log(N))
func (*SortedSet[K, V, ScoreType]) GetByScoreRange ¶
func (s *SortedSet[K, V, ScoreType]) GetByScoreRange( start ScoreType, end ScoreType, options *GetByScoreRangeOptions, ) []*SortedSetNode[K, V, ScoreType]
GetByScoreRange Get the nodes whose score within the specific range
If options is nil, it searchs in interval [start, end] without any limit by default
Time complexity of s method is : O(log(N))
func (*SortedSet[K, V, ScoreType]) IterFuncByRankRange ¶
func (s *SortedSet[K, V, ScoreType]) IterFuncByRankRange(start int, end int, fn func(key K, value V) bool)
IterFuncByRankRange apply fn to node within specific rank range [start, end] or until fn return false
Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node; If start is greater than end, apply fn in reserved order If fn is nil, s function return without doing anything
func (*SortedSet[K, V, ScoreType]) PeekMax ¶
func (s *SortedSet[K, V, ScoreType]) PeekMax() *SortedSetNode[K, V, ScoreType]
get the element with maximum score, nil if the set is empty Time Complexity : O(1)
func (*SortedSet[K, V, ScoreType]) PeekMin ¶
func (s *SortedSet[K, V, ScoreType]) PeekMin() *SortedSetNode[K, V, ScoreType]
PeekMin get the element with minimum score, nil if the set is empty
Time complexity of s method is : O(log(N))
func (*SortedSet[K, V, ScoreType]) PopMax ¶
func (s *SortedSet[K, V, ScoreType]) PopMax() *SortedSetNode[K, V, ScoreType]
get and remove the element with maximum score, nil if the set is empty
Time complexity of s method is : O(log(N))
func (*SortedSet[K, V, ScoreType]) PopMin ¶
func (s *SortedSet[K, V, ScoreType]) PopMin() *SortedSetNode[K, V, ScoreType]
PopMin get and remove the element with minimal score, nil if the set is empty
// Time complexity of s method is : O(log(N))
func (*SortedSet[K, V, ScoreType]) Remove ¶
func (s *SortedSet[K, V, ScoreType]) Remove(key K) *SortedSetNode[K, V, ScoreType]
Delete element specified by key
Time complexity of s method is : O(log(N))
type SortedSetLevel ¶
type SortedSetLevel[K Indexable, V any, ScoreType constraints.Ordered] struct { // contains filtered or unexported fields }
SortedSetLevel ...
type SortedSetNode ¶
type SortedSetNode[K Indexable, V any, ScoreType constraints.Ordered] struct { // contains filtered or unexported fields }
SortedSetNode Node in skip list
func NewSortedSetNode ¶
func NewSortedSetNode[K Indexable, V any, ScoreType constraints.Ordered]( level int, key K, value V, score ScoreType, ) *SortedSetNode[K, V, ScoreType]
func (*SortedSetNode[K, V, ScoreType]) Key ¶
func (n *SortedSetNode[K, V, ScoreType]) Key() K
Key Get the key of the node
func (*SortedSetNode[K, V, ScoreType]) Score ¶
func (n *SortedSetNode[K, V, ScoreType]) Score() ScoreType
Score Get the score of the node
func (*SortedSetNode[K, V, ScoreType]) Value ¶
func (n *SortedSetNode[K, V, ScoreType]) Value() V
Value get the value of node