Documentation
¶
Overview ¶
package skiplist implements a skiplist data structure.
In computer science, a skip list (or skiplist) is a probabilistic data structure that allows O(log n) average complexity for search as well as O(log n) average complexity for insertion within an ordered sequence of n elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one. Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally searching in the full sequence. The elements that are skipped over may be chosen probabilistically or deterministically, with the former being more common.
Reference: https://en.wikipedia.org/wiki/Skip_list
Index ¶
- type Element
- type Node
- type Skiplist
- func (l *Skiplist[K, V]) Clear()
- func (l *Skiplist[K, V]) Get(k K) (*Element[K, V], int)
- func (l *Skiplist[K, V]) GetByRank(rank int) *Element[K, V]
- func (l *Skiplist[K, V]) GetRange(k1, k2 K) []*Element[K, V]
- func (l *Skiplist[K, V]) GetRangeByRank(rank1, rank2 int) []*Element[K, V]
- func (l *Skiplist[K, V]) Insert(k K, v V)
- func (l *Skiplist[K, V]) Keys() []K
- func (l *Skiplist[K, V]) Len() int
- func (l *Skiplist[K, V]) MarshalJSON() ([]byte, error)
- func (l *Skiplist[K, V]) Max() *Element[K, V]
- func (l *Skiplist[K, V]) MaxInRange(k1, k2 K) *Element[K, V]
- func (l *Skiplist[K, V]) MaxNode() *Node[K, V]
- func (l *Skiplist[K, V]) MaxNodeInRange(k1, k2 K) *Node[K, V]
- func (l *Skiplist[K, V]) Min() *Element[K, V]
- func (l *Skiplist[K, V]) MinInRange(k1, k2 K) *Element[K, V]
- func (l *Skiplist[K, V]) MinNode() *Node[K, V]
- func (l *Skiplist[K, V]) MinNodeInRange(k1, k2 K) *Node[K, V]
- func (l *Skiplist[K, V]) Range(f func(k K, v V) bool)
- func (l *Skiplist[K, V]) Remove(k K) *Element[K, V]
- func (l *Skiplist[K, V]) RemoveByRank(rank int) *Element[K, V]
- func (l *Skiplist[K, V]) RemoveRange(k1, k2 K) []*Element[K, V]
- func (l *Skiplist[K, V]) RemoveRangeByRank(rank1, rank2 int) []*Element[K, V]
- func (l *Skiplist[K, V]) String() string
- func (l *Skiplist[K, V]) UnmarshalJSON(data []byte) error
- func (l *Skiplist[K, V]) Values() []V
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Element ¶
type Element[K comparable, V any] struct { // The value stored with this element. Value V // contains filtered or unexported fields }
Element represents a key-value pair of a node.
type Node ¶
type Node[K comparable, V any] struct { // The element stored with this node. Element *Element[K, V] // contains filtered or unexported fields }
Node is a node of a skiplist.
type Skiplist ¶
type Skiplist[K comparable, V any] struct { // contains filtered or unexported fields }
Skiplist represents a skiplist.
Example ¶
package main
import (
"fmt"
"github.com/docodex/gopkg/container/skiplist"
)
func main() {
strs := []string{"Hello", "World", "Golang", "Python", "Rust", "C", "JavaScript", "Haskell", "Pascal", "ZZ"}
ints := []int{3, 5, 4, 1, 8, 6, 5, 7, 9, 0}
t1 := skiplist.New[string, int]()
t2 := skiplist.New[int, string]()
for i := range len(strs) {
t1.Insert(strs[i], ints[i])
t2.Insert(ints[i], strs[i])
}
k1 := t1.Keys()
v1 := t1.Values()
for i := range k1 {
fmt.Printf("%s:%d\n", k1[i], v1[i])
}
k2 := t2.Keys()
v2 := t2.Values()
for i := range k2 {
fmt.Printf("%d:%s\n", k2[i], v2[i])
}
}
Output: C:6 Golang:4 Haskell:7 Hello:3 JavaScript:5 Pascal:9 Python:1 Rust:8 World:5 ZZ:0 0:ZZ 1:Python 3:Hello 4:Golang 5:JavaScript 6:C 7:Haskell 8:Rust 9:Pascal
func New ¶
New returns an initialized skiplist with cmp.Compare as the cmp function.
func NewFunc ¶
func NewFunc[K comparable, V any](cmp container.Compare[K]) *Skiplist[K, V]
NewFunc returns an initialized skiplist with the given function cmp as the cmp function.
func (*Skiplist[K, V]) Clear ¶
func (l *Skiplist[K, V]) Clear()
Clear removes all nodes in skiplist.
func (*Skiplist[K, V]) Get ¶
Get returns the element which key equals to the given key k. Get also returns the rank of the returned element in skiplist.
func (*Skiplist[K, V]) GetByRank ¶
GetByRank returns the element which rank equals to the given rank.
func (*Skiplist[K, V]) GetRange ¶
GetRange returns the elements which keys is within the given range [k1, k2) in which k1 is inclusive and k2 is exclusive.
func (*Skiplist[K, V]) GetRangeByRank ¶
GetRangeByRank removes the nodes which rank is within the given range [rank1, rank2) which rank1 is inclusive and rank2 is exclusive.
func (*Skiplist[K, V]) Insert ¶
func (l *Skiplist[K, V]) Insert(k K, v V)
Insert inserts a new node with the given key-value pair (k, v) to skiplist, or update the key and value if the given key k already exists in skiplist.
func (*Skiplist[K, V]) Keys ¶
func (l *Skiplist[K, V]) Keys() []K
Values returns all keys in skiplist.
func (*Skiplist[K, V]) MarshalJSON ¶
MarshalJSON marshals skiplist into valid JSON. Ref: std json.Marshaler.
func (*Skiplist[K, V]) MaxInRange ¶
MaxInRange returns the element which key is the maximum key within the given range [k1, k2) in which k1 is inclusive and k2 is exclusive.
func (*Skiplist[K, V]) MaxNodeInRange ¶
MaxNodeInRange returns the node which key is the maximum key within the given range [k1, k2) in which k1 is inclusive and k2 is exclusive.
func (*Skiplist[K, V]) MinInRange ¶
MinInRange returns the element which key is the minimum key within the given range [k1, k2) in which k1 is inclusive and k2 is exclusive.
func (*Skiplist[K, V]) MinNodeInRange ¶
MinNodeInRange returns the node which key is the minimum key within the given range [k1, k2) in which k1 is inclusive and k2 is exclusive.
func (*Skiplist[K, V]) Range ¶
Range calls f sequentially for each key-value pair (k, v) present in skiplist. If f returns false, range stops the iteration.
func (*Skiplist[K, V]) Remove ¶
Remove removes the node which key equals to the given key k from skiplist and returns the element of that node.
func (*Skiplist[K, V]) RemoveByRank ¶
RemoveByRank removes the node which rank equals to the given rank from skiplist and returns the element of that node.
func (*Skiplist[K, V]) RemoveRange ¶
RemoveRange removes the nodes which keys is within the given range [k1, k2) in which k1 is inclusive and k2 is exclusive from skiplist and returns the elements of those nodes.
func (*Skiplist[K, V]) RemoveRangeByRank ¶
RemoveRangeByRank removes the nodes which rank is within the given range [rank1, rank2) which rank1 is inclusive and rank2 is exclusive from skiplist and returns the elements of those nodes.
func (*Skiplist[K, V]) String ¶
String returns the string representation of skiplist. Ref: std fmt.Stringer.
func (*Skiplist[K, V]) UnmarshalJSON ¶
UnmarshalJSON unmarshals a JSON description of skiplist. The input can be assumed to be a valid encoding of a JSON value. UnmarshalJSON must copy the JSON data if it wishes to retain the data after returning. Ref: std json.Unmarshaler.
Source Files