skiplist

Documentation

Overview

Package skiplist implements skip list based maps and sets.

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

Skip lists were first described in Pugh, William (June 1990). "Skip lists: a probabilistic alternative to balanced trees". Communications of the ACM 33 (6): 668–676

Index

• Constants
• type Node
  • func (n *Node) Key() interface{}
  • func (n *Node) Next() *Node
  • func (n *Node) Previous() *Node
  • func (n *Node) Value() interface{}
• type SkipList
  • func NewCustomMap(lessThan func(l, r interface{}) bool) *SkipList
  • func NewInt32Map() *SkipList
  • func NewIntMap() *SkipList
  • func NewStringMap() *SkipList
  • func (s *SkipList) Delete(key interface{}) (value interface{}, ok bool)
  • func (s *SkipList) Front() *Node
  • func (s *SkipList) Get(key interface{}) (value interface{}, ok bool)
  • func (s *SkipList) GetGreaterOrEqual(min interface{}) (actualKey, value interface{}, ok bool)
  • func (s *SkipList) Last() *Node
  • func (s *SkipList) Len() int
  • func (s *SkipList) Seek(key interface{}) *Node
  • func (s *SkipList) Set(key, value interface{})

Constants

const DefaultMaxLevel = 32

Types

type Node

type Node struct {
	// contains filtered or unexported fields
}

A Node is a container for key-value pairs that are stored in a skip list.

func (*Node) Key

func (n *Node) Key() interface{}

func (*Node) Next

func (n *Node) Next() *Node

Next returns the Next Node in the skip list containing n.

func (*Node) Previous

func (n *Node) Previous() *Node

Previous returns the Previous Node in the skip list containing n.

func (*Node) Value

func (n *Node) Value() interface{}

type SkipList

type SkipList struct {
	// contains filtered or unexported fields
}

A SkipList is a map-like data structure that maintains an ordered collection of key-value pairs. Insertion, lookup, and deletion are all O(log n) operations. A SkipList can efficiently store up to 2^MaxLevel items.

To iterate over a skip list (where s is a *SkipList):

for i := s.Iterator(); i.Next(); {
	// do something with i.Key() and i.Value()
}

func NewCustomMap

func NewCustomMap(lessThan func(l, r interface{}) bool) *SkipList

NewCustomMap returns a new SkipList that will use lessThan as the comparison function. lessThan should define a linear order on keys you intend to use with the SkipList.

func NewInt32Map

func NewInt32Map() *SkipList

NewIntKey returns a SkipList that accepts int keys.

func NewIntMap

func NewIntMap() *SkipList

NewIntKey returns a SkipList that accepts int keys.

func NewStringMap

func NewStringMap() *SkipList

NewStringMap returns a SkipList that accepts string keys.

func (*SkipList) Delete

func (s *SkipList) Delete(key interface{}) (value interface{}, ok bool)

Delete removes the Node with the given key.

It returns the old value and whether the Node was present.

func (*SkipList) Front

func (s *SkipList) Front() *Node

func (*SkipList) Get

func (s *SkipList) Get(key interface{}) (value interface{}, ok bool)

Get returns the value associated with key from s (nil if the key is not present in s). The second return value is true when the key is present.

func (*SkipList) GetGreaterOrEqual

func (s *SkipList) GetGreaterOrEqual(min interface{}) (actualKey, value interface{}, ok bool)

GetGreaterOrEqual finds the Node whose key is greater than or equal to min. It returns its value, its actual key, and whether such a Node is present in the skip list.

func (*SkipList) Last

func (s *SkipList) Last() *Node

func (*SkipList) Len

func (s *SkipList) Len() int

Len returns the length of s.

func (*SkipList) Seek

func (s *SkipList) Seek(key interface{}) *Node

Seek returns a bidirectional iterator starting with the first element whose key is greater or equal to key; otherwise, a nil iterator is returned.

func (*SkipList) Set

func (s *SkipList) Set(key, value interface{})

Sets set the value associated with key in s.