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()
Copyright 2022 Iron Park. All rights reserved.
Index ¶
Constants ¶
const ( DefaultMaxLevel = 18 DefaultProbability float64 = 1 / math.E )
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.
Variables ¶
This section is empty.
Functions ¶
func BytesComparator ¶
func NumberComparator ¶
Types ¶
type Comparable ¶
Comparable defines a comparable func.
func Reverse ¶
func Reverse[K any](comparable Comparable[K]) Comparable[K]
Reverse creates a reversed comparable.
type Element ¶
type Element[K, V any] struct { Value V // contains filtered or unexported fields }
Element is an element node of a skip list.
type Numbers ¶
type Numbers interface { constraints.Integer | constraints.Float | rune }
type Option ¶
type Option func(option *Options)
Option is a function used to set Options
func WithProbability ¶
WithProbability sets probability of Skiplist
type Options ¶
type Options struct {
// contains filtered or unexported fields
}
Options holds Skiplist's options
type SkipList ¶
type SkipList[K, V any] interface { Init() SkipList[K, V] SetProbability(newProbability float64) Front() (front *Element[K, V]) Back() *Element[K, V] Len() int Set(key K, value V) (element *Element[K, V]) FindNext(start *Element[K, V], key K) (next *Element[K, V]) Find(key K) (elem *Element[K, V]) Get(key K) (elem *Element[K, V]) GetValue(key K) (val V, ok bool) MustGetValue(key K) V Remove(key K) (elem *Element[K, V]) RemoveFront() (front *Element[K, V]) RemoveBack() (back *Element[K, V]) RemoveElement(elem *Element[K, V]) MaxLevel() int Values() (values []V) Index(elem *Element[K, V]) (i int) Keys() (keys []K) SetMaxLevel(level int) (old int) }
func New ¶
func New[K, V any](comparable Comparable[K], options ...Option) (skipList SkipList[K, V])
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.