skiplist

package module
v1.2.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 23, 2024 License: MIT Imports: 6 Imported by: 63

README

Skip List in Golang

Go Go Doc Go Report Coverage Status

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

Examples

Constants

View Source 
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

View Source 
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 

type Comparable interface {
	Compare(lhs, rhs interface{}) int
	CalcScore(key interface{}) float64
}

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) Element 

func (header *Element) Element() *Element

func (*Element) Key 

func (elem *Element) Key() interface{}

Key returns the key of the elem.

func (*Element) Level 

func (elem *Element) Level() int

Level returns the level of this elem.

func (*Element) Next 

func (elem *Element) Next() *Element

Next returns next adjacent elem.

func (*Element) NextLevel 

func (elem *Element) NextLevel(level int) *Element

NextLevel returns next element at specific level. If level is invalid, returns nil.

func (*Element) Prev 

func (elem *Element) Prev() *Element

Prev returns previous adjacent elem.

func (*Element) PrevLevel 

func (elem *Element) PrevLevel(level int) *Element

PrevLevel returns previous element which points to this element at specific level. If level is invalid, returns nil.

func (*Element) Score 

func (elem *Element) Score() float64

Score returns the score of this element. The score is a hint when comparing elements. Skip list keeps all elements sorted by score from smallest to largest.

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) Back 

func (list *SkipList) Back() *Element

Back returns the last element.

The complexity is O(1).

func (*SkipList) Element 

func (header *SkipList) Element() *Element

func (*SkipList) Find added in v1.2.0 

func (list *SkipList) Find(key interface{}) (elem *Element)

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 

func (list *SkipList) FindNext(start *Element, key interface{}) (elem *Element)

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) Front 

func (list *SkipList) Front() *Element

Front returns the first element.

The complexity is O(1).

func (*SkipList) Get 

func (list *SkipList) Get(key interface{}) (elem *Element)

Get returns an element with the key. If the key is not found, returns nil.

The complexity is O(log(N)).

func (*SkipList) GetValue 

func (list *SkipList) GetValue(key interface{}) (val interface{}, ok bool)

GetValue returns value of the element with the key. It's short hand for Get().Value.

The complexity is O(log(N)).

func (*SkipList) Init 

func (list *SkipList) Init() *SkipList

Init resets the list and discards all existing elements.

func (*SkipList) Len 

func (list *SkipList) Len() int

Len returns element count in this list.

The complexity is O(1).

func (*SkipList) MaxLevel 

func (list *SkipList) MaxLevel() int

MaxLevel returns current max level value.

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 

func (list *SkipList) Remove(key interface{}) (elem *Element)

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 

func (list *SkipList) RemoveBack() (back *Element)

RemoveBack removes back element node and returns the removed element.

The complexity is O(log(N)).

func (*SkipList) RemoveElement 

func (list *SkipList) RemoveElement(elem *Element)

RemoveElement removes the elem from the list.

The complexity is O(log(N)).

func (*SkipList) RemoveFront 

func (list *SkipList) RemoveFront() (front *Element)

RemoveFront removes front element node and returns the removed element.

The complexity is O(1).

func (*SkipList) Set 

func (list *SkipList) Set(key, value interface{}) (elem *Element)

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 

func (list *SkipList) SetMaxLevel(level int) (old int)

SetMaxLevel changes skip list max level. If level is not greater than 0, just panic.

func (*SkipList) SetRandSource 

func (list *SkipList) SetRandSource(source rand.Source)

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

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.