skiplist

README

cloned from mauricegit/skiplist and modify to support generic.

Documentation

Overview

Package skiplist is an implementation of a skiplist to store elements in increasing order. It allows finding, insertion and deletion operations in approximately O(n log(n)). Additionally, there are methods for retrieving the next and previous element as well as changing the actual value without the need for re-insertion (as long as the key stays the same!) Skiplist is a fast alternative to a balanced tree.

Index

• type Ordered
• type SkipList
  • func New[K Ordered, V any]() *SkipList[K, V]
  • func NewSeed[K Ordered, V any](seed int64) *SkipList[K, V]
  • func (t *SkipList[K, V]) ChangeValue(key K, newValue V) (ok bool)
  • func (t *SkipList[K, V]) Delete(key K)
  • func (t *SkipList[K, V]) Find(key K) (v V, ok bool)
  • func (t *SkipList[K, V]) FindGreaterOrEqual(key K) (elem *SkipListElement[K, V], ok bool)
  • func (t *SkipList[K, V]) GetLargestNode() *SkipListElement[K, V]
  • func (t *SkipList[K, V]) GetNodeCount() int
  • func (t *SkipList[K, V]) GetSmallestNode() *SkipListElement[K, V]
  • func (t *SkipList[K, V]) Insert(key K, e V)
  • func (t *SkipList[K, V]) IsEmpty() bool
  • func (t *SkipList[K, V]) Next(e *SkipListElement[K, V]) *SkipListElement[K, V]
  • func (t *SkipList[K, V]) Prev(e *SkipListElement[K, V]) *SkipListElement[K, V]
  • func (t *SkipList[K, V]) String() string
• type SkipListElement
  • func (e *SkipListElement[K, V]) GetValue() V

Types

type Ordered

type Ordered = constraints.Ordered

Ordered is an interface for elements which can be ordered.

type SkipList

type SkipList[K Ordered, V any] struct {
	// contains filtered or unexported fields
}

SkipList is the actual skiplist representation. It saves all nodes accessible from the start and end and keeps track of element count, eps and levels.

func New

func New[K Ordered, V any]() *SkipList[K, V]

New returns a new empty, initialized Skiplist.

func NewSeed

func NewSeed[K Ordered, V any](seed int64) *SkipList[K, V]

NewSeed returns a new empty, initialized Skiplist. Given a seed, a deterministic height/list behaviour can be achieved.

func (*SkipList[K, V]) ChangeValue

func (t *SkipList[K, V]) ChangeValue(key K, newValue V) (ok bool)

ChangeValue can be used to change the actual value of a node in the skiplist without the need of Deleting and reinserting the node again. Be advised, that ChangeValue only works, if the actual key from ExtractKey() will stay the same! ok is an indicator, wether the value is actually changed.

func (*SkipList[K, V]) Delete

func (t *SkipList[K, V]) Delete(key K)

Delete removes an element equal to e from the skiplist, if there is one. If there are multiple entries with the same value, Delete will remove one of them (Which one will change based on the actual skiplist layout) Delete runs in approx. O(log(n))

func (*SkipList[K, V]) Find

func (t *SkipList[K, V]) Find(key K) (v V, ok bool)

Find tries to find an element in the skiplist based on the key from the given ListElement. elem can be used, if ok is true. Find runs in approx. O(log(n))

func (*SkipList[K, V]) FindGreaterOrEqual

func (t *SkipList[K, V]) FindGreaterOrEqual(key K) (elem *SkipListElement[K, V], ok bool)

FindGreaterOrEqual finds the first element, that is greater or equal to the given ListElement e. The comparison is done on the keys (So on ExtractKey()). FindGreaterOrEqual runs in approx. O(log(n))

func (*SkipList[K, V]) GetLargestNode

func (t *SkipList[K, V]) GetLargestNode() *SkipListElement[K, V]

GetLargestNode returns the very last/largest node in the skiplist. GetLargestNode runs in O(1)

func (*SkipList[K, V]) GetNodeCount

func (t *SkipList[K, V]) GetNodeCount() int

GetNodeCount returns the number of nodes currently in the skiplist.

func (*SkipList[K, V]) GetSmallestNode

func (t *SkipList[K, V]) GetSmallestNode() *SkipListElement[K, V]

GetSmallestNode returns the very first/smallest node in the skiplist. GetSmallestNode runs in O(1)

func (*SkipList[K, V]) Insert

func (t *SkipList[K, V]) Insert(key K, e V)

Insert inserts the given ListElement into the skiplist. Insert runs in approx. O(log(n))

func (*SkipList[K, V]) IsEmpty

func (t *SkipList[K, V]) IsEmpty() bool

IsEmpty checks, if the skiplist is empty.

func (*SkipList[K, V]) Next

func (t *SkipList[K, V]) Next(e *SkipListElement[K, V]) *SkipListElement[K, V]

Next returns the next element based on the given node. Next will loop around to the first node, if you call it on the last!

func (*SkipList[K, V]) Prev

func (t *SkipList[K, V]) Prev(e *SkipListElement[K, V]) *SkipListElement[K, V]

Prev returns the previous element based on the given node. Prev will loop around to the last node, if you call it on the first!

func (*SkipList[K, V]) String

func (t *SkipList[K, V]) String() string

String returns a string format of the skiplist. Useful to get a graphical overview and/or debugging.

type SkipListElement

type SkipListElement[K Ordered, V any] struct {
	// contains filtered or unexported fields
}

SkipListElement represents one actual Node in the skiplist structure. It saves the actual element, pointers to the next nodes and a pointer to one previous node.

func (*SkipListElement[K, V]) GetValue

func (e *SkipListElement[K, V]) GetValue() V

GetValue extracts the ListElement value from a skiplist node.