skiplist

README

Skiplist implementation for Go. Comes with tests. Currently no docs, but it's pretty obvious stuff.

Documentation

Index

• type Cmp
• type Comparable
• type Node
  • func (n *Node) Get(k Comparable) *Node
  • func (n *Node) Insert(k Comparable, v interface{}) *Node
  • func (n *Node) Next() *Node
  • func (n *Node) Prev() *Node
  • func (n *Node) Remove() interface{}
  • func (n *Node) Reposition(k Comparable)
  • func (n *Node) String() string
• type SkipList
  • func New(rng *rand.Rand) *SkipList
  • func (s *SkipList) First() *Node
  • func (s *SkipList) Get(k Comparable) *Node
  • func (s *SkipList) Insert(k Comparable, v interface{}) *Node
  • func (s *SkipList) Last() *Node
  • func (s *SkipList) Len() uint
  • func (s *SkipList) Merge(t *SkipList)
  • func (s *SkipList) Remove(k Comparable) interface{}
  • func (s *SkipList) String() string

Types

type Cmp

type Cmp int8

const (
	LT Cmp = iota - 1
	EQ
	GT
)

type Comparable

type Comparable interface {
	Compare(Comparable) Cmp
}

type Node

type Node struct {
	Key   Comparable
	Value interface{}
	// contains filtered or unexported fields
}

func (*Node) Get

func (n *Node) Get(k Comparable) *Node

func (*Node) Insert

func (n *Node) Insert(k Comparable, v interface{}) *Node

func (*Node) Next

func (n *Node) Next() *Node

func (*Node) Prev

func (n *Node) Prev() *Node

func (*Node) Remove

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

func (*Node) Reposition

func (n *Node) Reposition(k Comparable)

func (*Node) String

func (n *Node) String() string

type SkipList

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

func New

func New(rng *rand.Rand) *SkipList

func (*SkipList) First

func (s *SkipList) First() *Node

func (*SkipList) Get

func (s *SkipList) Get(k Comparable) *Node

func (*SkipList) Insert

func (s *SkipList) Insert(k Comparable, v interface{}) *Node

func (*SkipList) Last

func (s *SkipList) Last() *Node

func (*SkipList) Len

func (s *SkipList) Len() uint

func (*SkipList) Merge

func (s *SkipList) Merge(t *SkipList)

NB: this destroys t. Do not use t after this.

func (*SkipList) Remove

func (s *SkipList) Remove(k Comparable) interface{}

func (*SkipList) String

func (s *SkipList) String() string