README
¶
go-rbtree
Package rbtree provides an iterative (not recursive) red-black tree with
obvious semantics and powerful, resettable iteration.
This package was born out of a need to modify elements during tree iteration. Most packages do not provide an obvious way to efficiently "reset" a node or an iterator. To aid in this need, this package primarily operates on the basis of nodes rather than node items.
For more information about a red-black tree, and to understand the implementation, see Wikipedia.
Documentation
Documentation
¶
Overview ¶
Package rbtree provides an iterative (not recursive) red-black tree with obvious semantics and powerful, resettable iteration.
This package provides the easy ability to modify nodes on the fly, but note that this comes with the easy footgun of messing up iteration. If you modify a tree during iteration, you will likely need to reset your iterator. The node under the iterator may no longer be where you expect.
For more information about a red-black tree, and to understand the implementation, see Wikipedia:
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Index ¶
- type Item
- type Iter
- type Node
- type Tree
- func (t *Tree) Delete(n *Node) *Node
- func (t *Tree) Find(needle Item) *Node
- func (t *Tree) FindOrInsert(needle Item) *Node
- func (t *Tree) FindWith(cmp func(*Node) int) *Node
- func (t *Tree) FindWithOrInsertWith(find func(*Node) int, insert func() Item) *Node
- func (t *Tree) Fix(n *Node) *Node
- func (t *Tree) Insert(i Item) *Node
- func (t *Tree) Len() int
- func (t *Tree) Max() *Node
- func (t *Tree) Min() *Node
- func (t *Tree) Reinsert(n *Node)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Item ¶
type Item interface {
// Less returns whether an item is less than another item.
Less(other Item) bool
}
Item is the interface required for implenting to use a tree.
The red-black tree does support duplicate items, but one is not guaranteed which duplicate is found when looking to remove one of many duplicates. Essentially, there is no stable ordering to duplicate items.
type Iter ¶
type Iter struct {
// contains filtered or unexported fields
}
Iter iterates over a tree. This returns nodes in the tree to support easy node deletion.
Note that if you modify the tree during iteration, you need to reset the iterator or stop iterating.
Example ¶
package main
import (
"fmt"
"github.com/twmb/go-rbtree"
)
type Int int
func (l Int) Less(r rbtree.Item) bool {
return l < r.(Int)
}
func main() {
var r rbtree.Tree
for i := 0; i < 10; i++ {
r.Insert(Int(i)) // Int provides Less on int
}
// Declaring iter here to show we can reset it later.
var iter rbtree.Iter
// We can start iterating _at_ the max.
fmt.Println("iterating down...")
for iter = rbtree.IterAt(r.Max()); iter.Ok(); iter.Left() {
fmt.Println(iter.Item())
}
// Or, we can start iterating just before the min so that
// our first call to Right will start at the min.
iter.Reset(rbtree.Into(r.Min()))
fmt.Println("iterating up...")
for {
next := iter.Right()
if next == nil { // when right returns nil, we are done
break
}
fmt.Println(next.Item)
}
// Putting it together...
fmt.Println("iterating down very inefficiently...")
for it := rbtree.IterAt(r.Min()); it.Ok(); it.Right() {
if it.Item() == r.Max().Item {
fmt.Println(it.Item())
r.Delete(it.Node())
it.Reset(rbtree.Into(r.Min()))
}
}
}
Output: iterating down... 9 8 7 6 5 4 3 2 1 0 iterating up... 0 1 2 3 4 5 6 7 8 9 iterating down very inefficiently... 9 8 7 6 5 4 3 2 1 0
func IterAt ¶
IterAt returns an iterator for a tree starting on the given node.
Note that modifications to the tree during iteration may invalidate the iterator and the iterator may need resetting.
func (Iter) Item ¶
Item returns the item in the node the iterator is currently on. This will panic if the iterator is not on a node.
This is shorthand for i.Node().Item.
func (*Iter) Left ¶
Left moves the iterator to the left (more towards the min) and returns the resulting node it lands on, or nil if this moves past the left side of the tree. This will panic if not on a node.
func (Iter) PeekLeft ¶
PeekLeft peeks at the next left node the iterator can move onto without moving the iterator. This will panic if not on a node.
For maximal efficiency, to move left after a left peek, use Reset with the peeked node.
func (Iter) PeekRight ¶
PeekRight peeks at the next right node the iterator can move onto without moving the iterator. This will panic if not on a node.
For maximal efficiency, to move right after a right peek, use Reset with the peeked node.
type Node ¶
type Node struct {
Item Item
// contains filtered or unexported fields
}
Node is an element in a tree containing a user provided item.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is a red-black tree.
func (*Tree) Delete ¶
Delete removes a node from the tree, returning the resulting node that was removed. Note that you cannot reuse the "deleted" node for anything; you must use the returned node. The node for deletion may actually remain in the tree with a different item.
func (*Tree) FindOrInsert ¶
FindOrInsert finds a node equal to the needle, if any. If the node does not exist, this inserts a new node into the tree with new and returns that node.
func (*Tree) FindWith ¶
FindWith calls cmp to find a node in the tree. To continue searching left, cmp must return negative. To continue searching right, cmp must return positive. To stop at the node containing the current item to cmp, return zero.
If cmp never returns zero, this returns nil.
This can be used to find an arbitrary node meeting a condition.
func (*Tree) FindWithOrInsertWith ¶
FindWithOrInsertWith calls cmp to find a node in the tree following the semantics described in FindWith. If the cmp function never returns zero, this inserts a new node into the tree with new and returns that node.
func (*Tree) Fix ¶
Fix removes a node from the tree and reinserts it. This can be used to "fix" a node after the item has been updated, removing some minor garbage. This returns the updated node.
This is shorthand for t.Reinsert(t.Delete(n)).
Source Files