skiplist

Documentation

Index

• Constants
• type Element
  • func (e *Element) Key() float64
  • func (element *Element) Next() *Element
  • func (e *Element) Value() interface{}
• type SkipList
  • func New() *SkipList
  • func NewWithMaxLevel(maxLevel int) *SkipList
  • func (list *SkipList) Front() *Element
  • func (list *SkipList) Get(key float64) *Element
  • func (list *SkipList) Remove(key float64) *Element
  • func (list *SkipList) Set(key float64, value interface{}) *Element
  • func (list *SkipList) SetProbability(newProbability float64)

Constants

const (
	// Suitable for math.Floor(math.Pow(math.E, 18)) == 65659969 elements in list
	DefaultMaxLevel    int     = 18
	DefaultProbability float64 = 1 / math.E
)

Types

type Element

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

func (*Element) Key

func (e *Element) Key() float64

Key allows retrieval of the key for a given Element

func (*Element) Next

func (element *Element) Next() *Element

Next returns the following Element or nil if we're at the end of the list. Only operates on the bottom level of the skip list (a fully linked list).

func (*Element) Value

func (e *Element) Value() interface{}

Value allows retrieval of the value for a given Element

type SkipList

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

func New

func New() *SkipList

New creates a new skip list with default parameters. Returns a pointer to the new list.

func NewWithMaxLevel

func NewWithMaxLevel(maxLevel int) *SkipList

NewWithMaxLevel creates a new skip list with MaxLevel set to the provided number. maxLevel has to be int(math.Ceil(math.Log(N))) for DefaultProbability (where N is an upper bound on the number of elements in a skip list). See http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.524 Returns a pointer to the new list.

func (*SkipList) Front

func (list *SkipList) Front() *Element

Front returns the head node of the list.

func (*SkipList) Get

func (list *SkipList) Get(key float64) *Element

Get finds an element by key. It returns element pointer if found, nil if not found. Locking is optimistic and happens only after searching with a fast check for deletion after locking.

func (*SkipList) Remove

func (list *SkipList) Remove(key float64) *Element

Remove deletes an element from the list. Returns removed element pointer if found, nil if not found. Locking is optimistic and happens only after searching with a fast check on adjacent nodes after locking.

func (*SkipList) Set

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

Set inserts a value in the list with the specified key, ordered by the key. If the key exists, it updates the value in the existing node. Returns a pointer to the new element. Locking is optimistic and happens only after searching.

func (*SkipList) SetProbability

func (list *SkipList) SetProbability(newProbability float64)

SetProbability changes the current P value of the list. It doesn't alter any existing data, only changes how future insert heights are calculated.