skiplist

Documentation

Index

• type SkipList
  • func New[K constraints.Ordered, V any](compare cmp.SortFunc[K]) *SkipList[K, V]
  • func (s *SkipList[K, V]) Del(k K) (v V, ok bool)
  • func (s *SkipList[K, V]) Get(k interface{}) (v interface{}, ok bool)
  • func (s *SkipList[K, V]) Len() int
  • func (s *SkipList[K, V]) Range(from, to interface{}, op func(v interface{}))
  • func (s *SkipList[K, V]) Search(k interface{}) (ok bool)
  • func (s *SkipList[K, V]) Set(k interface{}, v interface{})

Types

type SkipList

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

A SkipList maintains an ordered collection of key:valkue pairs. It support insertion, lookup, and deletion operations with O(log n) time complexity Paper: Pugh, William (June 1990). "Skip lists: a probabilistic alternative to balanced trees". Communications of the ACM 33 (6): 668–676

func New

func New[K constraints.Ordered, V any](compare cmp.SortFunc[K]) *SkipList[K, V]

New returns a skiplist.

func (*SkipList[K, V]) Del

func (s *SkipList[K, V]) Del(k K) (v V, ok bool)

Del returns the deleted value if ok

func (*SkipList[K, V]) Get

func (s *SkipList[K, V]) Get(k interface{}) (v interface{}, ok bool)

Get returns corresponding v with given k.

func (*SkipList[K, V]) Len

func (s *SkipList[K, V]) Len() int

Len returns the length of given skiplist.

func (*SkipList[K, V]) Range

func (s *SkipList[K, V]) Range(from, to interface{}, op func(v interface{}))

Range interates `from` to `to` with `op`.

func (*SkipList[K, V]) Search

func (s *SkipList[K, V]) Search(k interface{}) (ok bool)

Search returns true if k is founded in the skiplist.

func (*SkipList[K, V]) Set

func (s *SkipList[K, V]) Set(k interface{}, v interface{})

Set sets given k and v pair into the skiplist.