gtreap is an immutable treap implementation in the Go Language

Overview

gtreap

gtreap is an immutable treap implementation in the Go Language

GoDoc Build Status Coverage Status

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

You might also like...
A skip list implementation in Go

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

Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

Go implementation to calculate Levenshtein Distance.

levenshtein Go package to calculate the Levenshtein Distance The library is fully capable of working with non-ascii strings. But the strings are not n

A Merkle Tree implementation written in Go.
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

A Go library for an efficient implementation of a skip list: https://godoc.org/github.com/MauriceGit/skiplist
A Go library for an efficient implementation of a skip list: https://godoc.org/github.com/MauriceGit/skiplist

Fast Skiplist Implementation This Go-library implements a very fast and efficient Skiplist that can be used as direct substitute for a balanced tree o

A slice-based implementation of a stack. In Go!

Stackgo Stackgo is a slice-based implementation of a simple stack in Go. It uses a pre-alloc pagination strategy which adds little memory overhead to

Comments
  • Priority problem

    Priority problem

    type Item struct {
        Key string
        Pri int
    }
    
    func itemCompare(a, b interface{}) int {
        return strings.Compare(a.(Item).Key, b.(Item).Key)
    }
    
    func main() {
        s := gtreap.NewTreap(itemCompare)
        s = s.Upsert(Item{"m", 20}, 20)
        s = s.Upsert(Item{"l", 18}, 18)
        s = s.Upsert(Item{"n", 19}, 19)
        s = s.Upsert(Item{"m", 4}, 4)
        s.VisitAscend(Item{"", 0}, func(i gtreap.Item) bool {
            item := i.(Item)
            fmt.Printf("%s %d\n", item.Key, item.Pri)
            return true
        })
    
    }
    

    It prints

    l 18
    m 4
    n 19
    

    m as root node with priority 4 is lower than it's sons. The reason is in https://github.com/steveyen/gtreap/blob/master/treap.go#L86 When middle is not nil, use middle's priority as result node's priority Always use this.priority should get the correct answer.

    opened by icexin 1
  • Public split and improvements to visit speed

    Public split and improvements to visit speed

    Hi,

    I have a use case where we need to store timestamped data, split off everything before time.Now(), then iterate that split in ascending order in its entirety. I've made a couple improvements to the treap to accomplish this. Would you like to merge them back in?

    The nil pivot short-circuit around the compare method was yielding about a 35% increase in performance for my particular use case. My comparison function is about as simple as you can compare timestamps:

    func compare(a, b interface{}) int {
        pA := a.(myItem)
        pB := b.(myItem)
    
        if pA.Timestamp.Equal(pB.Timestamp) {
            return 0
        }
        if pA.Timestamp.Before(pB.Timestamp) {
            return -1
        }
        return 1
    }
    
    opened by gburgett 0
Releases(1.3.16)
Owner
Steve Yen
Steve Yen
A versioned, snapshottable (immutable) AVL+ tree for persistent data.

IAVL+ Tree Note: Requires Go 1.13+ A versioned, snapshottable (immutable) AVL+ tree for persistent data. The purpose of this data structure is to prov

null 0 Nov 24, 2021
A simple set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp.

golang-set The missing set collection for the Go language. Until Go has sets built-in...use this. Coming from Python one of the things I miss is the s

Ralph Caraveo III 2.8k Dec 5, 2022
go.fifo provides a simple fifo thread-safe queue for the Go programming language

go.fifo Description go.fifo provides a simple FIFO thread-safe queue. *fifo.Queue supports pushing an item at the end with Add(), and popping an item

Foize 42 Aug 29, 2022
Dynamic object-oriented programming support for the Go language

Goop Description The Goop (Go Object-Oriented Programming) package provides support for dynamic object-oriented programming constructs in Go, much lik

Los Alamos National Laboratory 107 Oct 13, 2022
Generates data structure definitions from JSON files for any kind of programming language

Overview Archivist generates data structure definitions from JSON files for any kind of programming language. It also provides a library for golang to

Kingsgroup 45 Jun 28, 2022
A serverless cluster computing system for the Go programming language

Bigslice Bigslice is a serverless cluster data processing system for Go. Bigslice exposes composable API that lets the user express data processing ta

GRAIL 514 Nov 27, 2022
Learning Golang Language In Clean Structure

Learning Golang Language In Clean Structure At this example project, I'm trying to learn Golang with Clean structure and come up with a reusable, nice

Mahmood 3 Sep 25, 2022
Go implementation of Count-Min-Log

Count-Min-Log Count-Min-Log sketch: Approximately counting with approximate counters - Guillaume Pitel & Geoffroy Fouquier TL;DR: Count-Min-Log Sketch

Seif Lotfy 58 Sep 26, 2022
A Go implementation of the Elias-Fano encoding

go-ef A Go implementation of the Elias-Fano encoding Example package main import ( "fmt" "github.com/amallia/go-ef" "os" ) func main() {

Antonio Mallia 27 Nov 23, 2022
Set is a useful collection but there is no built-in implementation in Go lang.

goset Set is a useful collection but there is no built-in implementation in Go lang. Why? The only one pkg which provides set operations now is golang

zoumo 50 Sep 26, 2022