packagebst

packageredblack

Example

tree:=NewRedBlackTree()// Operations on arbitrary keys are allow as long as the type implements they// Key interface.typemyIntintfunc (imyInt)Less(vKey)bool {returni<v.(myInt)}// Insert items.tree.Upsert(myInt(5),"test")tree.Upsert(myInt(10),"foo")tree.Upsert(myInt(15),42)// Search for an item.fmt.Println(tree.Search(15))// Replace a payload.tree.Upsert(myInt(15),"bar")

Benchmarks

goos: darwingoarch: amd64pkg: github.com/obitech/go-tree/redblackBenchmarkRBTree_Upsert-8                 2012917               775 ns/op              31 B/op          0 allocs/opBenchmarkRBTree_Search10_000-8          11450182               102 ns/op               0 B/op          0 allocs/opBenchmarkRBTree_Search100_000-8          5394513               235 ns/op               0 B/op          0 allocs/opBenchmarkRBTree_Search1_000_000-8         411782              2487 ns/op             117 B/op          3 allocs/opBenchmarkRBTree_Delete10_000-8          25755091                43.7 ns/op             0 B/op          0 allocs/opBenchmarkRBTree_Delete100_000-8         23051653                46.5 ns/op             0 B/op          0 allocs/opBenchmarkRBTree_Delete1_000_000-8          37518             26899 ns/op            1291 B/op         43 allocs/op

packageinterval

Example

tree:=NewIntervalTree()nov,err:=NewInterval(newTime(t,"2020-Nov-01"),newTime(t,"2020-Nov-02"))iferr!=nil {panic(err)}feb,err:=NewInterval(newTime(t,"2020-Feb-01"),newTime(t,"2020-Feb-02"))iferr!=nil {panic(err)}dec,err:=NewInterval(newTime(t,"2020-Dec-01"),newTime(t,"2020-Dec-02"))iferr!=nil {panic(err)}tree.Upsert(nov)tree.Upsert(feb)tree.Upsert(dec)search1,err:=NewInterval(newTime(t,"2020-Feb-01"),newTime(t,"2021-Feb-02"))r,err:=tree.FindFirstOverlapping(search)iferr!=nil {fmt.Println("no overlapping interval found for %s",search1)}r,err=tree.FindAllOverlapping(search)iferr!=nil {fmt.Println("no overlapping interval found for %s",search1)}

Benchmarks