goskiplist

module
v0.0.0-...-2dfbae5 Latest Latest
Warning

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

Go to latest
Published: Mar 12, 2015 License: Apache-2.0

README

About

This is a library implementing skip lists for the Go programming language (http://golang.org/).

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

Build Status

Installing

$ go get github.com/ryszard/goskiplist/skiplist

Example

package main

import (
	"fmt"
	"github.com/ryszard/goskiplist/skiplist"
)

func main() {
	s := skiplist.NewIntMap()
	s.Set(7, "seven")
	s.Set(1, "one")
	s.Set(0, "zero")
	s.Set(5, "five")
	s.Set(9, "nine")
	s.Set(10, "ten")
	s.Set(3, "three")

	firstValue, ok := s.Get(0)
	if ok {
		fmt.Println(firstValue)
	}
	// prints:
	//  zero

	s.Delete(7)

	secondValue, ok := s.Get(7)
	if ok {
		fmt.Println(secondValue)
	}
	// prints: nothing.

	s.Set(9, "niner")

	// Iterate through all the elements, in order.
	unboundIterator := s.Iterator()
	for unboundIterator.Next() {
		fmt.Printf("%d: %s\n", unboundIterator.Key(), unboundIterator.Value())
	}
	// prints:
	//  0: zero
	//  1: one
	//  3: three
	//  5: five
	//  9: niner
	//  10: ten

	for unboundIterator.Previous() {
		fmt.Printf("%d: %s\n", unboundIterator.Key(), unboundIterator.Value())
	}
	//  9: niner
	//  5: five
	//  3: three
	//  1: one
	//  0: zero

	boundIterator := s.Range(3, 10)
	// Iterate only through elements in some range.
	for boundIterator.Next() {
		fmt.Printf("%d: %s\n", boundIterator.Key(), boundIterator.Value())
	}
	// prints:
	//  3: three
	//  5: five
	//  9: niner

	for boundIterator.Previous() {
		fmt.Printf("%d: %s\n", boundIterator.Key(), boundIterator.Value())
	}
	// prints:
	//  5: five
	//  3: three

	var iterator skiplist.Iterator

	iterator = s.Seek(3)
	fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value())
	// prints:
	//  3: three

	iterator = s.Seek(2)
	fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value())
	// prints:
	//  3: three

  iterator = s.SeekToFirst()
  fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value())
  // prints:
  //  0: zero

  iterator = s.SeekToLast()
  fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value())
  // prints:
  //  10: ten

  // SkipList can also reduce subsequent forward seeking costs by reusing the
  // same iterator:

  iterator = s.Seek(3)
	fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value())
	// prints:
	//  3: three

  iterator.Seek(5)
	fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value())
	// prints:
	//  5: five
}

Full documentation

Read it online or run

$ go doc github.com/ryszard/goskiplist/skiplist

Other implementations

This list is probably incomplete.

Directories

Path Synopsis
Package skiplist implements skip list based maps and sets.
Package skiplist implements skip list based maps and sets.

Jump to

Keyboard shortcuts

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