README
¶
Skip List in Golang
Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure.
Highlights in this implementation:
- Built-in types can be used as key with predefined key types. See Int and related constants as a sample.
- Support custom comparable function so that any type can be used as key.
- Key sort order can be changed quite easily. See Reverse and LessThanFunc.
- Rand source and max level can be changed per list. It can be useful in performance critical scenarios.
Install
Install this package through go get.
go get github.com/huandu/skiplist
Basic Usage
Here is a quick sample.
package main
import (
"fmt"
"github.com/huandu/skiplist"
)
func main() {
// Create a skip list with int key.
list := skiplist.New(skiplist.Int)
// Add some values. Value can be anything.
list.Set(12, "hello world")
list.Set(34, 56)
list.Set(78, 90.12)
// Get element by index.
elem := list.Get(34) // Value is stored in elem.Value.
fmt.Println(elem.Value) // Output: 56
next := elem.Next() // Get next element.
prev := next.Prev() // Get previous element.
fmt.Println(next.Value, prev.Value) // Output: 90.12 56
// Or, directly get value just like a map
val, ok := list.GetValue(34)
fmt.Println(val, ok) // Output: 56 true
// Find first elements with score greater or equal to key
foundElem := list.Find(30)
fmt.Println(foundElem.Key(), foundElem.Value) // Output: 34 56
// Remove an element for key.
list.Remove(34)
}
Using GreaterThanFunc and LessThanFunc
Define your own GreaterThanFunc or LessThanFunc to use any custom type as the key in a skip list.
The signature of GreaterThanFunc are LessThanFunc are the same.
The only difference between them is that LessThanFunc reverses result returned by custom func
to make the list ordered by key in a reversed order.
type T struct {
Rad float64
}
list := New(GreaterThanFunc(func(k1, k2 interface{}) int {
s1 := math.Sin(k1.(T).Rad)
s2 := math.Sin(k2.(T).Rad)
if s1 > s2 {
return 1
} else if s1 < s2 {
return -1
}
return 0
}))
list.Set(T{math.Pi / 8}, "sin(π/8)")
list.Set(T{math.Pi / 2}, "sin(π/2)")
list.Set(T{math.Pi}, "sin(π)")
fmt.Println(list.Front().Value) // Output: sin(π)
fmt.Println(list.Back().Value) // Output: sin(π/2)
License
This library is licensed under MIT license. See LICENSE for details.
Documentation
¶
Overview ¶
Package skiplist implement skip list data structure. See wikipedia for more details about this data structure. http://en.wikipedia.org/wiki/Skip_list
Skip list is basically an ordered map.
Here is a sample to use this package.
// Creates a new skip list and restricts key type to int-like types. list := skiplist.New(skiplist.Int) // Adds some values for keys. list.Set(20, "Hello") list.Set(10, "World") list.Set(40, true) // Value type is not restricted. list.Set(40, 1000) // Replace the of an existing element. // Finds elements. e := list.Get(10) // Returns the element with the key. _ = e.Value.(string) v, ok := list.GetValue(20) // Directly get value of the element. If the key is not found, ok is false. v2 := list.MustGetValue(10) // Directly get value of the element. Panic if the key is not found. notFound := list.Get(15) // Returns nil if the key is not found. // Removes an element and gets removed element. old := list.Remove(40) notFound := list.Remove(-20) // Returns nil if the key is not found. // Initializes the list again to clean up all elements in the list. list.Init()
Index ¶
- Constants
- Variables
- func CalcScore(key interface{}) (score float64)
- type Comparable
- type Element
- func (header *Element) Element() *Element
- func (elem *Element) Key() interface{}
- func (elem *Element) Level() int
- func (elem *Element) Next() *Element
- func (elem *Element) NextLevel(level int) *Element
- func (elem *Element) Prev() *Element
- func (elem *Element) PrevLevel(level int) *Element
- func (elem *Element) Score() float64
- type GreaterThanFunc
- type LessThanFunc
- type Scorable
- type SkipList
- func (list *SkipList) Back() *Element
- func (header *SkipList) Element() *Element
- func (list *SkipList) Find(key interface{}) (elem *Element)
- func (list *SkipList) FindNext(start *Element, key interface{}) (elem *Element)
- func (list *SkipList) Front() (front *Element)
- func (list *SkipList) Get(key interface{}) (elem *Element)
- func (list *SkipList) GetValue(key interface{}) (val interface{}, ok bool)
- func (list *SkipList) Init() *SkipList
- func (list *SkipList) Len() int
- func (list *SkipList) MaxLevel() int
- func (list *SkipList) MustGetValue(key interface{}) interface{}
- func (list *SkipList) Remove(key interface{}) (elem *Element)
- func (list *SkipList) RemoveBack() (back *Element)
- func (list *SkipList) RemoveElement(elem *Element)
- func (list *SkipList) RemoveFront() (front *Element)
- func (list *SkipList) Set(key, value interface{}) (elem *Element)
- func (list *SkipList) SetMaxLevel(level int) (old int)
- func (list *SkipList) SetRandSource(source rand.Source)
Examples ¶
Constants ¶
const ( Byte = byteType ByteAsc = Byte ByteDesc = -Byte Rune = runeType RuneAsc = Rune RuneDesc = -Rune Int = intType IntAsc = Int IntDesc = -Int Int8 = int8Type Int8Asc = Int8 Int8Desc = -Int8 Int16 = int16Type Int16Asc = Int16 Int16Desc = -Int16 Int32 = int32Type Int32Asc = Int32 Int32Desc = -Int32 Int64 = int64Type Int64Asc = Int64 Int64Desc = -Int64 Uint = uintType UintAsc = Uint UintDesc = -Uint Uint8 = uint8Type Uint8Asc = Uint8 Uint8Desc = -Uint8 Uint16 = uint16Type Uint16Asc = Uint16 Uint16Desc = -Uint16 Uint32 = uint32Type Uint32Asc = Uint32 Uint32Desc = -Uint32 Uint64 = uint64Type Uint64Asc = Uint64 Uint64Desc = -Uint64 Uintptr = uintptrType UintptrAsc = Uintptr UintptrDesc = -Uintptr Float32 = float32Type Float32Asc = Float32 Float32Desc = -Float32 Float64 = float64Type Float64Asc = Float64 Float64Desc = -Float64 String = stringType StringAsc = String StringDesc = -String Bytes = bytesType BytesAsc = Bytes BytesDesc = -Bytes )
Key types for all built-in types. We can use these type as key type when creating a new skip list.
list := New(Int) // Use int as key.
Variables ¶
var DefaultMaxLevel = 48
DefaultMaxLevel is the default level for all newly created skip lists. It can be changed globally. Changing it will not affect existing lists. And all skip lists can update max level after creation through `SetMaxLevel()` method.
Functions ¶
func CalcScore ¶
func CalcScore(key interface{}) (score float64)
CalcScore calculates score of a key.
The score is a hint to optimize comparable performance. A skip list keeps all elements sorted by score from smaller to largest. If there are keys with different scores, these keys must be different.
Types ¶
type Comparable ¶
Comparable defines a comparable func.
func Reverse ¶
func Reverse(comparable Comparable) Comparable
Reverse creates a reversed comparable.
type Element ¶
type Element struct {
Value interface{}
// contains filtered or unexported fields
}
Element is an element node of a skip list.
func (*Element) NextLevel ¶
NextLevel returns next element at specific level. If level is invalid, returns nil.
type GreaterThanFunc ¶
type GreaterThanFunc func(lhs, rhs interface{}) int
GreaterThanFunc returns true if lhs greater than rhs
Example ¶
type T struct {
Rad float64
}
list := New(GreaterThanFunc(func(k1, k2 interface{}) int {
s1 := math.Sin(k1.(T).Rad)
s2 := math.Sin(k2.(T).Rad)
if s1 > s2 {
return 1
} else if s1 < s2 {
return -1
}
return 0
}))
list.Set(T{math.Pi / 8}, "sin(π/8)")
list.Set(T{math.Pi / 2}, "sin(π/2)")
list.Set(T{math.Pi}, "sin(π)")
fmt.Println(list.Front().Value) // Output: sin(π)
fmt.Println(list.Back().Value) // Output: sin(π/2)
Output: sin(π) sin(π/2)
func (GreaterThanFunc) CalcScore ¶
func (f GreaterThanFunc) CalcScore(key interface{}) float64
CalcScore always returns 0 as there is no way to understand how f compares keys.
func (GreaterThanFunc) Compare ¶
func (f GreaterThanFunc) Compare(lhs, rhs interface{}) int
Compare compares lhs and rhs by calling `f(lhs, rhs)`.
type LessThanFunc ¶
type LessThanFunc GreaterThanFunc
LessThanFunc returns true if lhs less than rhs
func (LessThanFunc) CalcScore ¶
func (f LessThanFunc) CalcScore(key interface{}) float64
CalcScore always returns 0 as there is no way to understand how f compares keys.
func (LessThanFunc) Compare ¶
func (f LessThanFunc) Compare(lhs, rhs interface{}) int
Compare compares lhs and rhs by calling `-f(lhs, rhs)`.
type Scorable ¶
type Scorable interface {
Score() float64
}
Scorable is used by skip list to optimize comparing performance. If two keys have different score values, they must be different keys.
For any key `k1` and `k2`, the calculated score must follow these rules.
- If Compare(k1, k2) is positive, k1.Score() >= k2.Score() must be true.
- If Compare(k1, k2) is negative, k1.Score() <= k2.Score() must be true.
- If Compare(k1, k2) is 0, k1.Score() == k2.Score() must be true.
type SkipList ¶
type SkipList struct {
// contains filtered or unexported fields
}
SkipList is the header of a skip list.
Example ¶
// Create a skip list with int key. list := New(Int) // Add some values. Value can be anything. list.Set(12, "hello world") list.Set(34, 56) list.Set(78, 90.12) // Get element by index. elem := list.Get(34) // Value is stored in elem.Value. fmt.Println(elem.Value) // Output: 56 next := elem.Next() // Get next element. prev := next.Prev() // Get previous element. fmt.Println(next.Value, prev.Value) // Output: 90.12 56 // Or, directly get value just like a map val, ok := list.GetValue(34) fmt.Println(val, ok) // Output: 56 true // Find first elements with score greater or equal to key foundElem := list.Find(30) fmt.Println(foundElem.Key(), foundElem.Value)
Output:
func New ¶
func New(comparable Comparable) *SkipList
New creates a new skip list with comparable to compare keys.
There are lots of pre-defined strict-typed keys like Int, Float64, String, etc. We can create custom comparable by implementing Comparable interface.
func (*SkipList) Find ¶ added in v1.2.0
Find returns the first element that is greater or equal to key. It's short hand for FindNext(nil, key).
The complexity is O(log(N)).
func (*SkipList) FindNext ¶ added in v1.2.0
FindNext returns the first element after start that is greater or equal to key. If start is greater or equal to key, returns start. If there is no such element, returns nil. If start is nil, find element from front.
The complexity is O(log(N)).
func (*SkipList) Get ¶
Get returns an element with the key. If the key is not found, returns nil.
The complexity is O(log(N)).
func (*SkipList) GetValue ¶
GetValue returns value of the element with the key. It's short hand for Get().Value.
The complexity is O(log(N)).
func (*SkipList) MustGetValue ¶
func (list *SkipList) MustGetValue(key interface{}) interface{}
MustGetValue returns value of the element with the key. It will panic if the key doesn't exist in the list.
The complexity is O(log(N)).
func (*SkipList) Remove ¶
Remove removes an element. Returns removed element pointer if found, nil if it's not found.
The complexity is O(log(N)).
func (*SkipList) RemoveBack ¶
RemoveBack removes back element node and returns the removed element.
The complexity is O(log(N)).
func (*SkipList) RemoveElement ¶
RemoveElement removes the elem from the list.
The complexity is O(log(N)).
func (*SkipList) RemoveFront ¶
RemoveFront removes front element node and returns the removed element.
The complexity is O(1).
func (*SkipList) Set ¶
Set sets value for the key. If the key exists, updates element's value. Returns the element holding the key and value.
The complexity is O(log(N)).
func (*SkipList) SetMaxLevel ¶
SetMaxLevel changes skip list max level. If level is not greater than 0, just panic.
func (*SkipList) SetRandSource ¶
SetRandSource sets a new rand source.
Skiplist uses global rand defined in math/rand by default. The default rand acquires a global mutex before generating any number. It's not necessary if the skiplist is well protected by caller.
Source Files