skiplist

package
v1.0.1 Latest Latest
Warning

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

Go to latest
Published: Mar 4, 2024 License: Apache-2.0 Imports: 1 Imported by: 0

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

View Source
const DefaultMaxLevel = 32

Variables

This section is empty.

Functions

This section is empty.

Types

type Iterator

type Iterator interface {
	// Next returns true if the iterator contains subsequent elements
	// and advances its state to the next element if that is possible.
	Next() (ok bool)
	// Previous returns true if the iterator contains previous elements
	// and rewinds its state to the previous element if that is possible.
	Previous() (ok bool)
	// Key returns the current key.
	Key() interface{}
	// Value returns the current value.
	Value() interface{}
	// Seek reduces iterative seek costs for searching forward into the Skip List
	// by remarking the range of keys over which it has scanned before.  If the
	// requested key occurs prior to the point, the Skip List will start searching
	// as a safeguard.  It returns true if the key is within the known range of
	// the list.
	Seek(key interface{}) (ok bool)
	// Close this iterator to reap resources associated with it.  While not
	// strictly required, it will provide extra hints for the garbage collector.
	Close()
}

Iterator is an interface that you can use to iterate through the skip list (in its entirety or fragments). For an use example, see the documentation of SkipList.

Key and Value return the key and the value of the current node.

type Ordered

type Ordered interface {
	LessThan(other Ordered) bool
}

Ordered is an interface which can be linearly ordered by the LessThan method, whereby this instance is deemed to be less than other. Additionally, Ordered instances should behave properly when compared using == and !=.

type Set

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

Set is an ordered set data structure.

Its elements must implement the Ordered interface. It uses a SkipList for storage, and it gives you similar performance guarantees.

To iterate over a set (where s is a *Set):

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

func NewCustomSet

func NewCustomSet(lessThan func(l, r interface{}) bool) *Set

NewCustomSet returns a new Set that will use lessThan as the comparison function. lessThan should define a linear order on elements you intend to use with the Set.

func NewIntSet

func NewIntSet() *Set

NewIntSet returns a new Set that accepts int elements.

func NewSet

func NewSet() *Set

NewSet returns a new Set.

func NewStringSet

func NewStringSet() *Set

NewStringSet returns a new Set that accepts string elements.

func (*Set) Add

func (s *Set) Add(key interface{})

Add adds key to s.

func (*Set) Contains

func (s *Set) Contains(key interface{}) bool

Contains returns true if key is present in s.

func (*Set) GetMaxLevel

func (s *Set) GetMaxLevel() int

GetMaxLevel returns MaxLevel fo the underlying skip list.

func (*Set) Iterator

func (s *Set) Iterator() Iterator

func (*Set) Len

func (s *Set) Len() int

Len returns the length of the set.

func (*Set) Range

func (s *Set) Range(from, to interface{}) Iterator

Range returns an iterator that will go through all the elements of the set that are greater or equal than from, but less than to.

func (*Set) Remove

func (s *Set) Remove(key interface{}) (ok bool)

Remove tries to remove key from the set. It returns true if key was present.

func (*Set) SetMaxLevel

func (s *Set) SetMaxLevel(newMaxLevel int)

SetMaxLevel sets MaxLevel in the underlying skip list.

type SkipList

type SkipList struct {

	// MaxLevel determines how many items the SkipList can store
	// efficiently (2^MaxLevel).
	//
	// It is safe to increase MaxLevel to accomodate more
	// elements. If you decrease MaxLevel and the skip list
	// already contains nodes on higer levels, the effective
	// MaxLevel will be the greater of the new MaxLevel and the
	// level of the highest node.
	//
	// A SkipList with MaxLevel equal to 0 is equivalent to a
	// standard linked list and will not have any of the nice
	// properties of skip lists (probably not what you want).
	MaxLevel int
	// 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 New

func New() *SkipList

New returns a new SkipList.

Its keys must implement the Ordered interface.

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

func (s *SkipList) GetElementByRank(rank int) (interface{}, bool)

Finds an element by its rank. The rank argument needs to be 1-based.

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

func (s *SkipList) GetRank(key interface{}) int

Find the rank for an element by both score and key.

Returns 0 when the element cannot be found, rank otherwise.

Note that the rank is 1-based due to the span of s.header to the first element.

func (*SkipList) Iterator

func (s *SkipList) Iterator() Iterator

Iterator returns an Iterator that will go through all elements s.

func (*SkipList) Len

func (s *SkipList) Len() int

Len returns the length of s.

func (*SkipList) Range

func (s *SkipList) Range(from, to interface{}) Iterator

Range returns an iterator that will go through all the elements of the skip list that are greater or equal than from, but less than to.

func (*SkipList) Seek

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

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

func (s *SkipList) SeekToFirst() Iterator

SeekToFirst returns a bidirectional iterator starting from the first element in the list if the list is populated; otherwise, a nil iterator is returned.

func (*SkipList) SeekToLast

func (s *SkipList) SeekToLast() Iterator

SeekToLast returns a bidirectional iterator starting from the last element in the list if the list is populated; 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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL