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/skiplistBasic 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.