1gtreap 2------ 3 4gtreap is an immutable treap implementation in the Go Language 5 6[![GoDoc](https://godoc.org/github.com/steveyen/gtreap?status.svg)](https://godoc.org/github.com/steveyen/gtreap) [![Build Status](https://drone.io/github.com/steveyen/gtreap/status.png)](https://drone.io/github.com/steveyen/gtreap/latest) [![Coverage Status](https://coveralls.io/repos/steveyen/gtreap/badge.png)](https://coveralls.io/r/steveyen/gtreap) 7 8Overview 9======== 10 11gtreap implements an immutable treap data structure in golang. 12 13By treap, this data structure is both a heap and a binary search tree. 14 15By immutable, any updates/deletes to a treap will return a new treap 16which can share internal nodes with the previous treap. All nodes in 17this implementation are read-only after their creation. This allows 18concurrent readers to operate safely with concurrent writers as 19modifications only create new data structures and never modify 20existing data structures. This is a simple approach to achieving MVCC 21or multi-version concurrency control. 22 23By heap, items in the treap follow the heap-priority property, where a 24parent node will have higher priority than its left and right children 25nodes. 26 27By binary search tree, items are store lexigraphically, ordered by a 28user-supplied Compare function. 29 30To get a probabilistic O(lg N) tree height, you should use a random 31priority number during the Upsert() operation. 32 33LICENSE 34======= 35 36MIT 37 38Example 39======= 40 41 import ( 42 "math/rand" 43 "github.com/steveyen/gtreap" 44 ) 45 46 func stringCompare(a, b interface{}) int { 47 return bytes.Compare([]byte(a.(string)), []byte(b.(string))) 48 } 49 50 t := gtreap.NewTreap(stringCompare) 51 t = t.Upsert("hi", rand.Int()) 52 t = t.Upsert("hola", rand.Int()) 53 t = t.Upsert("bye", rand.Int()) 54 t = t.Upsert("adios", rand.Int()) 55 56 hi = t.Get("hi") 57 bye = t.Get("bye") 58 59 // Some example Delete()'s... 60 t = t.Delete("bye") 61 nilValueHere = t.Get("bye") 62 t2 = t.Delete("hi") 63 nilValueHere2 = t2.Get("hi") 64 65 // Since we still hold onto treap t, we can still access "hi". 66 hiStillExistsInTreapT = t.Get("hi") 67 68 t.VisitAscend("cya", func(i Item) bool { 69 // This visitor callback will be invoked with every item 70 // from "cya" onwards. So: "hi", "hola". 71 // If we want to stop visiting, return false; 72 // otherwise a true return result means keep visiting items. 73 return true 74 }) 75 76Tips 77==== 78 79The Upsert() method takes both an Item (an interface{}) and a heap 80priority. Usually, that priority should be a random int 81(math/rand.Int()) or perhaps even a hash of the item. However, if you 82want to shuffle more commonly accessed items nearer to the top of the 83treap for faster access, at the potential cost of not approaching a 84probabilistic O(lg N) tree height, then you might tweak the priority. 85 86See also 87======== 88 89For a simple, ordered, key-value storage or persistence library built 90on immutable treaps, see: https://github.com/steveyen/gkvlite 91