skiplist

README

Using SkipListMap

Whenever you find yourself in need of a sorted list/map for range scans or ordered iteration, you can resort to a SkipList. The SkipListMap in this project is based on LevelDBs skiplist and super easy to use:

skipListMap := skiplist.NewSkipListMap(skiplist.IntComparator)
skipListMap.Insert(13, 91)
skipListMap.Insert(3, 1)
skipListMap.Insert(5, 2)
log.Printf("size: %d", skipListMap.Size())

it, _ := skipListMap.Iterator()
for {
    k, v, err := it.Next()
    if err == skiplist.Done {
        break
    }
    log.Printf("key: %d, value: %d", k, v)
}

log.Printf("starting at key: %d", 5)
it, _ = skipListMap.IteratorStartingAt(5)
for {
    k, v, err := it.Next()
    if err == skiplist.Done {
        break
    }
    log.Printf("key: %d, value: %d", k, v)
}

log.Printf("between: %d and %d", 8, 50)
it, _ = skipListMap.IteratorBetween(8, 50)
for {
    k, v, err := it.Next()
    if err == skiplist.Done {
        break
    }
    log.Printf("key: %d, value: %d", k, v)
}

You can supply any kind of element and comparator to sort arbitrary structs and primitives. You can get the full example from examples/skiplist.go.

Documentation

Overview

basically a translation from LevelDBs skiplist (https://github.com/google/leveldb/blob/master/db/skiplist.h)

Index

• Variables
• func BytesComparator(a interface{}, b interface{}) int
• func IntComparator(a interface{}, b interface{}) int
• type KeyComparator
• type SkipListIterator
  • func (it *SkipListIterator) Next() (interface{}, interface{}, error)
• type SkipListIteratorI
• type SkipListMap
  • func (list *SkipListMap) Contains(key interface{}) bool
  • func (list *SkipListMap) Get(key interface{}) (interface{}, error)
  • func (list *SkipListMap) Insert(key interface{}, value interface{})
  • func (list *SkipListMap) Iterator() (SkipListIteratorI, error)
  • func (list *SkipListMap) IteratorBetween(keyLower interface{}, keyHigher interface{}) (SkipListIteratorI, error)
  • func (list *SkipListMap) IteratorStartingAt(key interface{}) (SkipListIteratorI, error)
  • func (list *SkipListMap) Size() int
• type SkipListMapI
  • func NewSkipListMap(comp KeyComparator) SkipListMapI
• type SkipListNode
  • func (n *SkipListNode) Next(height int) *SkipListNode
  • func (n *SkipListNode) SetNext(height int, node *SkipListNode)
• type SkipListNodeI

Variables

var Done = errors.New("no more items in iterator")

iterator pattern as described in https://github.com/GoogleCloudPlatform/google-cloud-go/wiki/Iterator-Guidelines

var NotFound = errors.New("key was not found")

Functions

func BytesComparator

func BytesComparator(a interface{}, b interface{}) int

example comparator for plain byte arrays

func IntComparator

func IntComparator(a interface{}, b interface{}) int

example comparator for plain integers

Types

type KeyComparator

type KeyComparator func(a interface{}, b interface{}) int

Typical comparator contract (similar to Java): < 0 when a < b == 0 when a == b > 0 when a > b

type SkipListIterator

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

func (*SkipListIterator) Next

func (it *SkipListIterator) Next() (interface{}, interface{}, error)

type SkipListIteratorI

type SkipListIteratorI interface {
	// returns the next key, value in sequence
	// returns Done as the error when the iterator is exhausted
	Next() (interface{}, interface{}, error)
}

type SkipListMap

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

func (*SkipListMap) Contains

func (list *SkipListMap) Contains(key interface{}) bool

func (*SkipListMap) Get

func (list *SkipListMap) Get(key interface{}) (interface{}, error)

func (*SkipListMap) Insert

func (list *SkipListMap) Insert(key interface{}, value interface{})

func (*SkipListMap) Iterator

func (list *SkipListMap) Iterator() (SkipListIteratorI, error)

func (*SkipListMap) IteratorBetween

func (list *SkipListMap) IteratorBetween(keyLower interface{}, keyHigher interface{}) (SkipListIteratorI, error)

func (*SkipListMap) IteratorStartingAt

func (list *SkipListMap) IteratorStartingAt(key interface{}) (SkipListIteratorI, error)

func (*SkipListMap) Size

func (list *SkipListMap) Size() int

type SkipListMapI

type SkipListMapI interface {
	Size() int

	// Insert key/value into the list.
	// REQUIRES: nothing that compares equal to key is currently in the list.
	Insert(key interface{}, value interface{})

	// Returns true if an entry that compares equal to key is in the list.
	Contains(key interface{}) bool

	// Returns the value element that compares equal to the key supplied or returns NotFound if it does not exist.
	Get(key interface{}) (interface{}, error)

	// Returns an iterator over the whole sorted sequence
	Iterator() (SkipListIteratorI, error)

	// Returns an iterator over the sorted sequence starting at the given key (inclusive if key is in the list).
	// Using a key that is out of the sequence range will result in either an empty iterator or the full sequence.
	IteratorStartingAt(key interface{}) (SkipListIteratorI, error)

	// Returns an iterator over the sorted sequence starting at the given keyLower (inclusive if key is in the list)
	// and until the given keyHigher was reached (inclusive if key is in the list).
	// Using keys that are out of the sequence range will result in either an empty iterator or the full sequence.
	// If keyHigher is lower than keyLower an error will be returned
	IteratorBetween(keyLower interface{}, keyHigher interface{}) (SkipListIteratorI, error)
}

func NewSkipListMap

func NewSkipListMap(comp KeyComparator) SkipListMapI

type SkipListNode

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

func (*SkipListNode) Next

func (n *SkipListNode) Next(height int) *SkipListNode

func (*SkipListNode) SetNext

func (n *SkipListNode) SetNext(height int, node *SkipListNode)

type SkipListNodeI

type SkipListNodeI interface {
	Next(height int) *SkipListNode
	SetNext(height int, node *SkipListNode)
}