README

gtreap

gtreap is an immutable treap implementation in the Go Language

Overview

gtreap implements an immutable treap data structure in golang.

By treap, this data structure is both a heap and a binary search tree.

By immutable, any updates/deletes to a treap will return a new treap which can share internal nodes with the previous treap. All nodes in this implementation are read-only after their creation. This allows concurrent readers to operate safely with concurrent writers as modifications only create new data structures and never modify existing data structures. This is a simple approach to achieving MVCC or multi-version concurrency control.

By heap, items in the treap follow the heap-priority property, where a parent node will have higher priority than its left and right children nodes.

By binary search tree, items are store lexigraphically, ordered by a user-supplied Compare function.

To get a probabilistic O(lg N) tree height, you should use a random priority number during the Upsert() operation.

LICENSE

MIT

Example

import (
    "math/rand"
    "github.com/steveyen/gtreap"
)

func stringCompare(a, b interface{}) int {
    return bytes.Compare([]byte(a.(string)), []byte(b.(string)))
}

t := gtreap.NewTreap(stringCompare)
t = t.Upsert("hi", rand.Int())
t = t.Upsert("hola", rand.Int())
t = t.Upsert("bye", rand.Int())
t = t.Upsert("adios", rand.Int())

hi = t.Get("hi")
bye = t.Get("bye")

// Some example Delete()'s...
t = t.Delete("bye")
nilValueHere = t.Get("bye")
t2 = t.Delete("hi")
nilValueHere2 = t2.Get("hi")

// Since we still hold onto treap t, we can still access "hi".
hiStillExistsInTreapT = t.Get("hi")

t.VisitAscend("cya", func(i Item) bool {
    // This visitor callback will be invoked with every item
    // from "cya" onwards.  So: "hi", "hola".
    // If we want to stop visiting, return false;
    // otherwise a true return result means keep visiting items.
    return true
})

Tips

The Upsert() method takes both an Item (an interface{}) and a heap priority. Usually, that priority should be a random int (math/rand.Int()) or perhaps even a hash of the item. However, if you want to shuffle more commonly accessed items nearer to the top of the treap for faster access, at the potential cost of not approaching a probabilistic O(lg N) tree height, then you might tweak the priority.

See also

For a simple, ordered, key-value storage or persistence library built on immutable treaps, see: https://github.com/steveyen/gkvlite

Documentation

Index

• type Compare
• type Item
• type ItemVisitor
• type Iterator
  • func (it *Iterator) Next() (Item, bool)
• type Treap
  • func NewTreap(c Compare) *Treap
  • func (t *Treap) Delete(target Item) *Treap
  • func (t *Treap) Get(target Item) Item
  • func (t *Treap) Iterator(pivot Item) *Iterator
  • func (t *Treap) Max() Item
  • func (t *Treap) Min() Item
  • func (t *Treap) Upsert(item Item, itemPriority int) *Treap
  • func (t *Treap) VisitAscend(pivot Item, visitor ItemVisitor)

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Compare

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

Compare returns an integer comparing the two items lexicographically. The result will be 0 if a==b, -1 if a < b, and +1 if a > b.

type Item

type Item interface{}

Item can be anything.

type ItemVisitor

type ItemVisitor func(i Item) bool

type Iterator

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

Iterator supports iterative ascending traversal of the Treap. An Iterator is instantiated by calling a Treap's Iterator method.

func (*Iterator) Next

func (it *Iterator) Next() (Item, bool)

Next returns the next Item in the iteration sequence.

If another item exists in the iteration sequence, true will be returned as the second return value; if not, false will be returned, indicating end of iteration. Additional calls to Next after end of iteration will continue to return false.

type Treap

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

func NewTreap

func NewTreap(c Compare) *Treap

func (*Treap) Delete

func (t *Treap) Delete(target Item) *Treap

func (*Treap) Get

func (t *Treap) Get(target Item) Item

func (*Treap) Iterator

func (t *Treap) Iterator(pivot Item) *Iterator

Iterator returns an ascending Iterator instance that is bound to this Treap. The iterator begins at "pivot" and iterates through the end of the Treap.

func (*Treap) Max

func (t *Treap) Max() Item

func (*Treap) Min

func (t *Treap) Min() Item

func (*Treap) Upsert

func (t *Treap) Upsert(item Item, itemPriority int) *Treap

Note: only the priority of the first insert of an item is used. Priorities from future updates on already existing items are ignored. To change the priority for an item, you need to do a Delete then an Upsert.

func (*Treap) VisitAscend

func (t *Treap) VisitAscend(pivot Item, visitor ItemVisitor)

Visit items greater-than-or-equal to the pivot.