Documentation ¶
Overview ¶
Package sortedset was inspired by SortedSet in Redis: it provides fast access to elements in sorted set by key or score(order).
Introduction ¶
Every node in the set is associated with these properties.
type SortedSetNode[K constraints.Ordered, SCORE constraints.Ordered, V any] struct { key K // unique key of this node Value V // 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 repeat. Nodes are kept ordered by score and key. Each node in the set can be also accessed by rank: the position of the node in the sorted set.
With sorted sets you can add, remove or update nodes in a very efficient way (O(N) = log(N)). You can also retrieve ranges of nodes by score or by rank in a very efficient way. Accessing the middle of a sorted set is also very efficient, so you can use Sorted Sets as smart lists 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 leaderboard in a massive online game, where you update the player's position every time a new score is submitted. You can easily take the top players using GetRangeByRank() method. You can also, given an user id, return their rank in the listing using FindRank() method. Using FindRank() and GetRangeByRank() together you can show users with a score similar to a given user.
Examples
// create a new set set := sortedset.New[string, int64, string]() // 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.GetRangeByRank(1, -1, false) // get & remove the 2nd/3rd nodes in reserve order set.GetRangeByRank(-2, -3, true) // get the nodes whose score are within the interval [60,100] set.GetRangeByScore(60, 100, nil) // get the nodes whose score are within the interval (60,100] set.GetRangeByScore(60, 100, &GetRangeByScoreOptions{ ExcludeStart: true, }) // get the nodes whose score are within the interval [60,100) set.GetRangeByScore(60, 100, &GetRangeByScoreOptions{ ExcludeEnd: true, }) // get the nodes whose score are within the interval [60,100] in reverse order set.GetRangeByScore(100, 60, nil) // get the top 2 nodes with lowest scores within the interval [60,100] set.GetRangeByScore(60, 100, &GetRangeByScoreOptions{ Limit: 2, }) // get the top 2 nodes with highest scores within the interval [60,100] set.GetRangeByScore(100, 60, &GetRangeByScoreOptions{ Limit: 2, }) // get the top 2 nodes with highest scores within the interval (60,100) set.GetRangeByScore(100, 60, &GetRangeByScoreOptions{ Limit: 2, ExcludeStart: true, ExcludeEnd: true, })
Index ¶
- Constants
- type GetRangeByScoreOptions
- type SortedSet
- func (this *SortedSet[K, SCORE, V]) AddOrUpdate(key K, score SCORE, value V) bool
- func (this *SortedSet[K, SCORE, V]) FindRank(key K) int
- func (this *SortedSet[K, SCORE, V]) GetByKey(key K) *SortedSetNode[K, SCORE, V]
- func (this *SortedSet[K, SCORE, V]) GetByRank(rank int, remove bool) *SortedSetNode[K, SCORE, V]
- func (this *SortedSet[K, SCORE, V]) GetCount() int
- func (this *SortedSet[K, SCORE, V]) GetRangeByRank(start int, end int, remove bool) []*SortedSetNode[K, SCORE, V]
- func (this *SortedSet[K, SCORE, V]) GetRangeByScore(start SCORE, end SCORE, options *GetRangeByScoreOptions) []*SortedSetNode[K, SCORE, V]
- func (this *SortedSet[K, SCORE, V]) IterFuncRangeByRank(start int, end int, fn func(key K, value V) bool)
- func (this *SortedSet[K, SCORE, V]) PeekMax() *SortedSetNode[K, SCORE, V]
- func (this *SortedSet[K, SCORE, V]) PeekMin() *SortedSetNode[K, SCORE, V]
- func (this *SortedSet[K, SCORE, V]) PopMax() *SortedSetNode[K, SCORE, V]
- func (this *SortedSet[K, SCORE, V]) PopMin() *SortedSetNode[K, SCORE, V]
- func (this *SortedSet[K, SCORE, V]) Remove(key K) *SortedSetNode[K, SCORE, V]
- type SortedSetLevel
- type SortedSetNode
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 GetRangeByScoreOptions ¶ added in v1.0.1
type SortedSet ¶
type SortedSet[K constraints.Ordered, SCORE constraints.Ordered, V any] struct { // contains filtered or unexported fields }
func New ¶
func New[K constraints.Ordered, SCORE constraints.Ordered, V any]() *SortedSet[K, SCORE, V]
Create a new SortedSet
func (*SortedSet[K, SCORE, V]) AddOrUpdate ¶
Add an element into the sorted set with specific key / value / score. if the element is added, this method returns true; otherwise false means updated
Time complexity of this method is : O(log(N))
func (*SortedSet[K, SCORE, V]) 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 this method is : O(log(N))
func (*SortedSet[K, SCORE, V]) GetByKey ¶
func (this *SortedSet[K, SCORE, V]) GetByKey(key K) *SortedSetNode[K, SCORE, V]
Get node by key
If node is not found, nil is returned Time complexity : O(1)
func (*SortedSet[K, SCORE, V]) GetByRank ¶
func (this *SortedSet[K, SCORE, V]) GetByRank(rank int, remove bool) *SortedSetNode[K, SCORE, V]
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 this method is : O(log(N))
func (*SortedSet[K, SCORE, V]) GetRangeByRank ¶ added in v1.0.1
func (this *SortedSet[K, SCORE, V]) GetRangeByRank(start int, end int, remove bool) []*SortedSetNode[K, SCORE, V]
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 this method is : O(log(N))
func (*SortedSet[K, SCORE, V]) GetRangeByScore ¶ added in v1.0.1
func (this *SortedSet[K, SCORE, V]) GetRangeByScore(start SCORE, end SCORE, options *GetRangeByScoreOptions) []*SortedSetNode[K, SCORE, V]
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 this method is : O(log(N))
func (*SortedSet[K, SCORE, V]) IterFuncRangeByRank ¶ added in v1.0.1
func (this *SortedSet[K, SCORE, V]) IterFuncRangeByRank(start int, end int, fn func(key K, value V) bool)
IterFuncRangeByRank 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, this function return without doing anything
func (*SortedSet[K, SCORE, V]) PeekMax ¶
func (this *SortedSet[K, SCORE, V]) PeekMax() *SortedSetNode[K, SCORE, V]
get the element with maximum score, nil if the set is empty Time Complexity : O(1)
func (*SortedSet[K, SCORE, V]) PeekMin ¶
func (this *SortedSet[K, SCORE, V]) PeekMin() *SortedSetNode[K, SCORE, V]
get the element with minimum score, nil if the set is empty
Time complexity of this method is : O(log(N))
func (*SortedSet[K, SCORE, V]) PopMax ¶
func (this *SortedSet[K, SCORE, V]) PopMax() *SortedSetNode[K, SCORE, V]
get and remove the element with maximum score, nil if the set is empty
Time complexity of this method is : O(log(N))
func (*SortedSet[K, SCORE, V]) PopMin ¶
func (this *SortedSet[K, SCORE, V]) PopMin() *SortedSetNode[K, SCORE, V]
get and remove the element with minimal score, nil if the set is empty
// Time complexity of this method is : O(log(N))
func (*SortedSet[K, SCORE, V]) Remove ¶
func (this *SortedSet[K, SCORE, V]) Remove(key K) *SortedSetNode[K, SCORE, V]
Delete element specified by key
Time complexity of this method is : O(log(N))
type SortedSetLevel ¶
type SortedSetLevel[K constraints.Ordered, SCORE constraints.Ordered, V any] struct { // contains filtered or unexported fields }
type SortedSetNode ¶
type SortedSetNode[K constraints.Ordered, SCORE constraints.Ordered, V any] struct { Value V // associated data // contains filtered or unexported fields }
Node in skip list
func (*SortedSetNode[K, SCORE, V]) Key ¶
func (this *SortedSetNode[K, SCORE, V]) Key() K
Get the key of the node
func (*SortedSetNode[K, SCORE, V]) Score ¶
func (this *SortedSetNode[K, SCORE, V]) Score() SCORE
Get the node of the node