petar / gollrb Goto Github PK
View Code? Open in Web Editor NEWA Left-Leaning Red-Black (LLRB) implementation of balanced binary search trees for Google Go
License: BSD 3-Clause "New" or "Revised" License
A Left-Leaning Red-Black (LLRB) implementation of balanced binary search trees for Google Go
License: BSD 3-Clause "New" or "Revised" License
Hi Petar,
Thanks for writing this data structure.
I was giving it a drive, and the following throws a runtime panic
func lessString(a, b interface{}) bool {
return a.(string) < b.(string)
}
iofile, err := os.OpenFile("testfile.gob", os.O_RDWR|os.O_CREATE, 0666)
if err != nil {
panic("Could not find, or create file: error code:" + err.String())
}
enc := gob.NewEncoder(iofile)
//dec := gob.NewDecoder(iofile)
tree := llrb.New(lessString)
tree.ReplaceOrInsert("alex")
errdecode := enc.Encode(tree)
if errdecode != nil {
fmt.Printf("decode error:%s", err.String())
}
However, if you simply encode another struct like this one
type Test struct {
Test string
}
everything works fine.
What is the license and copyright of files in doc?
Content of doc
directory apparently authored by Robert Sedgewick but there are no .PDF sources...
Hi, I'm looking to use this library for a production tool, and was wondering if it's still being actively maintained?
Throughout the LLRB code it is assumed the root node has been set. But there is no sensible way to create a root node for a new instance of LLRB.
By the way, the example is out of date.
Hi,
I noticed this because I've been writing an llrb, and on my own project I can't get deletion to test as correct when using top down 2-3-4 insertion (see post on golang-nuts).
I wanted to check my sanity (I've pored over the code so many times to see if I'm doing something stupid), so I inserted one of my failing deletion tests into GoLLRB and it gives equivalent behaviour (passes on bottom up 2-3 and fails catastrophically on top down 2-3-4).
func TestRandomInsertionDeletion(t *testing.T) {
count, max := 100000, 1000
tree := New(IntLess)
for i := 0; i < count; i++ {
if rand.Float64() < 0.5 {
tree.ReplaceOrInsert(rand.Intn(max))
}
if rand.Float64() < 0.5 {
tree.Delete(rand.Intn(max))
}
}
}
The test is obviously very vicious, but is fine with the standard 2-3 GoLLRB insertion mode.
Any ideas?
I've ran into a case where the delete code path appears to panic within the llrb package:
panic: runtime error: invalid memory address or nil pointer dereference [recovered]
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x20 pc=0x100bc7b40]
goroutine 7 [running]:
testing.tRunner.func1.2({0x100d5dd60, 0x100f44d30})
/usr/local/go/src/testing/testing.go:1209 +0x258
testing.tRunner.func1(0x1400008d040)
/usr/local/go/src/testing/testing.go:1212 +0x284
panic({0x100d5dd60, 0x100f44d30})
/usr/local/go/src/runtime/panic.go:1038 +0x21c
github.com/petar/GoLLRB/llrb.flip(...)
/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:417
github.com/petar/GoLLRB/llrb.moveRedRight(0x1400016fa40)
/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:434 +0x30
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400016fa40, {0x100da86c0, 0x14000067f80})
/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:361 +0x25c
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400017eea0, {0x100da86c0, 0x14000067f80})
/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400018a0c0, {0x100da86c0, 0x14000067f80})
/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400018bda0, {0x100da86c0, 0x14000067f80})
/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).Delete(0x140001567f0, {0x100da86c0, 0x14000067f80})
/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:328 +0x40
It seems that moveRedRight
requires both the left and right children to exist https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L432, but here only the right child is tested https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L359-L362?
The example code in Readme.md does not compile. I had to convert it to the following to get it to work:
package main
import (
"fmt"
"github.com/petar/GoLLRB/llrb"
)
type IntItem int
func IntLess(p, q interface{}) bool {
return p.(int) < q.(int)
}
func main() {
tree := llrb.New(IntLess)
tree.ReplaceOrInsert(1)
tree.ReplaceOrInsert(2)
tree.ReplaceOrInsert(3)
tree.ReplaceOrInsert(4)
tree.DeleteMin()
tree.Delete(4)
c := tree.IterAscend()
for {
u := <-c
if u == nil {
break
}
fmt.Printf("%d\n", u.(int))
}
}
for i := 0; i < 1000000; i++ {
rid, _ := utils.RandInt(100000, 999999)
cnt++
tree.InsertNoReplace(NewMatchRoom(rid))
}
for i := 0; i < 1000000; i++ {
rid, _ := utils.RandInt(100000, 999999)
cnt++
tree.Delete(NewMatchRoom(rid))
}
Sorry, but the author of the method is Robert Sedgewick, not Roger. You can check it here: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
I encountered a crash in a data processing app that makes use of GoLLRB.
panic: runtime error: invalid memory address or nil pointer dereference
at llrb/llrb.go:423 (moveRedLeft)
I found a particular sequence of data that causes the tree to become inconsistent and crash. I've attached a simple test program that reproduces the error.
Download the code file llrbcrash.go and run with:
go get github.com/petar/GoLLRB
go run llrbcrash.go
Hello, is there an algorithm for fast merge of LLRB trees?
I think somebody else would find my fork useful, but I don't want to pollute the google wiki with this fork. Perhaps it's worth mentioning my fork in your README.
I want to iterate from a given key to the end of the tree inclusively. But there seems to be no way to get the last (tree.Max()) value as part of that iteration. I don't know what the most elegant solution would be...
< @upper
to <= @upper
?@lower <= E <= @upper
?Please consider assigning version numbers and tagging releases. Tags/releases
are useful for downstream package maintainers (in Debian and other distributions) to export source tarballs, automatically track new releases and to declare dependencies between packages. Read more in the Debian Upstream Guide.
Versioning provides additional benefits to encourage vendoring of a particular (e.g. latest stable) release contrary to random unreleased snapshots.
Versioning provides safety margin for situations like "ops, we've made a mistake but reverted problematic commit in master". Presumably tagged version/release is better tested/reviewed than random snapshot of "master" branch.
Thank you.
See also
Here you broke compatibly by removing comparator function from New
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.