Imports #
"fmt"
"strconv"
"strings"
abt
Imports
Constants & Variables
LEAF_HEIGHT const #
const LEAF_HEIGHT = 1NOT_KEY32 const #
const NOT_KEY32 = *ast.CallExprZERO_HEIGHT const #
const ZERO_HEIGHT = 0Structs
Iterator struct #
type Iterator struct {
it iterator
}T struct #
T is the exported applicative balanced tree data type. A T can be used as a value; updates to one copy of the value do not change other copies.
type T struct {
root *node32
size int
}iterator struct #
type iterator struct {
parents []*node32
}node32 struct #
node32 is the internal tree node data type
type node32 struct {
left *node32
right *node32
data interface{}
key int32
height_ int8
}Functions
Copy method #
func (t *T) Copy() *TDelete method #
func (t *T) Delete(x int32) interface{}DeleteMax method #
func (t *T) DeleteMax() (int32, interface{})DeleteMin method #
func (t *T) DeleteMin() (int32, interface{})Difference method #
Difference returns the difference of t and u, subject to the result of f applied to data corresponding to equal keys. If f returns nil (or if f is nil) then the key+data are excluded, as usual. If f returns not-nil, then that key+data pair is inserted. instead.
func (t *T) Difference(u *T, f func(x interface{}, y interface{}) interface{}) *TDone method #
func (it *Iterator) Done() boolEquals method #
func (t *T) Equals(u *T) boolEquiv method #
func (t *T) Equiv(u *T, eqv func(x interface{}, y interface{}) bool) boolFind method #
Find returns the data associated with x in the tree, or nil if x is not in the tree.
func (t *T) Find(x int32) interface{}Glb method #
Glb returns the greatest-lower-bound-exclusive of x and the associated data. If x has no glb in the tree, then (NOT_KEY32, nil) is returned.
func (t *T) Glb(x int32) (k int32, d interface{})GlbEq method #
GlbEq returns the greatest-lower-bound-inclusive of x and the associated data. If x has no glbEQ in the tree, then (NOT_KEY32, nil) is returned.
func (t *T) GlbEq(x int32) (k int32, d interface{})Insert method #
Insert either adds x to the tree if x was not previously a key in the tree, or updates the data for x in the tree if x was already a key in the tree. The previous data associated with x is returned, and is nil if x was not previously a key in the tree.
func (t *T) Insert(x int32, data interface{}) interface{}Intersection method #
Intersection returns the intersection of t and u, where the result data for any common keys is given by f(t's data, u's data) -- f need not be symmetric. If f returns nil, then the key and data are not added to the result. If f itself is nil, then whatever value was already present in the smaller set is used.
func (t *T) Intersection(u *T, f func(x interface{}, y interface{}) interface{}) *TIsEmpty method #
IsEmpty returns true iff t is empty.
func (t *T) IsEmpty() boolIsSingle method #
IsSingle returns true iff t is a singleton (leaf).
func (t *T) IsSingle() boolIterator method #
func (t *T) Iterator() IteratorLub method #
Lub returns the least-upper-bound-exclusive of x and the associated data. If x has no lub in the tree, then (NOT_KEY32, nil) is returned.
func (t *T) Lub(x int32) (k int32, d interface{})LubEq method #
LubEq returns the least-upper-bound-inclusive of x and the associated data. If x has no lubEq in the tree, then (NOT_KEY32, nil) is returned.
func (t *T) LubEq(x int32) (k int32, d interface{})Max method #
Max returns the maximum element of t. If t is empty, then (NOT_KEY32, nil) is returned.
func (t *T) Max() (k int32, d interface{})Min method #
Min returns the minimum element of t. If t is empty, then (NOT_KEY32, nil) is returned.
func (t *T) Min() (k int32, d interface{})Next method #
func (it *Iterator) Next() (int32, interface{})Size method #
func (t *T) Size() intString method #
func (t *T) String() stringUnion method #
Union returns the union of t and u, where the result data for any common keys is given by f(t's data, u's data) -- f need not be symmetric. If f returns nil, then the key and data are not added to the result. If f itself is nil, then whatever value was already present in the larger set is used.
func (t *T) Union(u *T, f func(x interface{}, y interface{}) interface{}) *TVisitInOrder method #
VisitInOrder applies f to the key and data pairs in t, with keys ordered from smallest to largest.
func (t *T) VisitInOrder(f func(int32, interface{}))aDelete method #
func (t *node32) aDelete(key int32) (deleted *node32, newSubTree *node32)aDeleteMax method #
func (t *node32) aDeleteMax() (deleted *node32, newSubTree *node32)aDeleteMin method #
func (t *node32) aDeleteMin() (deleted *node32, newSubTree *node32)aInsert method #
func (t *node32) aInsert(x int32) (newroot *node32, newnode *node32, oldnode *node32)aLeftIsHigh method #
aLeftIsHigh does rotations necessary to fix a high left child assume that t and t.left are already fresh copies.
func (t *node32) aLeftIsHigh(newnode *node32) *node32aRebalanceAfterLeftDeletion method #
func (t *node32) aRebalanceAfterLeftDeletion(oldLeftHeight int8, tleft *node32) *node32aRebalanceAfterRightDeletion method #
func (t *node32) aRebalanceAfterRightDeletion(oldRightHeight int8, tright *node32) *node32aRightIsHigh method #
aRightIsHigh does rotations necessary to fix a high right child assume that t and t.right are already fresh copies.
func (t *node32) aRightIsHigh(newnode *node32) *node32copy method #
func (t *node32) copy() *node32done method #
func (it *iterator) done() boolequals method #
func (t *node32) equals(u *node32) boolequiv method #
func (t *node32) equiv(u *node32, eqv func(x interface{}, y interface{}) bool) boolfind method #
func (t *node32) find(key int32) *node32glb method #
func (t *node32) glb(key int32, allow_eq bool) *node32height method #
func (n *node32) height() int8isLeaf method #
func (t *node32) isLeaf() booliterator method #
func (t *node32) iterator() iteratorleftToRoot method #
leftToRoot does that rotation, modifying t and t.left in the process.
func (t *node32) leftToRoot() *node32leftmost method #
func (it *iterator) leftmost(t *node32)lub method #
func (t *node32) lub(key int32, allow_eq bool) *node32makeNode function #
func makeNode(key int32) *node32max method #
func (t *node32) max() *node32min method #
func (t *node32) min() *node32next method #
func (it *iterator) next() *node32nilOrData method #
func (n *node32) nilOrData() interface{}nilOrKeyAndData method #
func (n *node32) nilOrKeyAndData() (k int32, d interface{})rightToRoot method #
rightToRoot does that rotation, modifying t and t.right in the process.
func (t *node32) rightToRoot() *node32visitInOrder method #
func (t *node32) visitInOrder(f func(int32, interface{}))Generated with Arrow