README
¶
btree
A Go generic library providing copy-on-write B-tree data structures including maps, sets, interval trees, and order-statistic trees. All variants share a common augmented B-tree implementation and support O(1) lazy cloning.
Note: This library is still in beta. Please report any issues on the GitHub issue tracker.
Read more about the design in the blog post.
Interval Trees
The interval package provides interval trees for efficiently finding all intervals that overlap a query range. The iterator supports FirstOverlap() and NextOverlap() methods for querying overlapping intervals.
Order-Statistic Trees
The orderstat package provides order-statistic trees that support O(log n) rank queries and nth element selection. The iterator adds Rank() and SeekNth() methods for efficient positional queries.
License
Copyright 2021 Andrew Werner. Licensed under the Apache License, Version 2.0.
Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
Map is a ordered map from K to V.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/ajwerner/btree"
)
func main() {
m := btree.MakeMap[string, int](strings.Compare)
m.Upsert("foo", 1)
m.Upsert("bar", 2)
fmt.Println(m.Get("foo"))
fmt.Println(m.Get("baz"))
it := m.Iterator()
for it.First(); it.Valid(); it.Next() {
fmt.Println(it.Cur(), it.Value())
}
}
Output: 1 true 0 false bar 2 foo 1
type MapIterator ¶
MapIterator is an iterator for a Map.
type Set ¶
Set is an ordered set of items of type T.
type SetIterator ¶
type SetIterator[T any] = MapIterator[T, struct{}]
SetIterator is an iterator for a Set.
Source Files
Directories