const LEAF_HEIGHT … const ZERO_HEIGHT … const NOT_KEY32 … type T … type node32 … func makeNode(key int32) *node32 { … } // IsEmpty returns true iff t is empty. func (t *T) IsEmpty() bool { … } // IsSingle returns true iff t is a singleton (leaf). func (t *T) IsSingle() bool { … } // 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{ … } func (n *node32) nilOrData() interface{ … } func (n *node32) nilOrKeyAndData() (k int32, d interface{ … } func (n *node32) height() int8 { … } // 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{ … } // 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{ … } func (t *T) Copy() *T { … } func (t *T) Delete(x int32) interface{ … } func (t *T) DeleteMin() (int32, interface{ … } func (t *T) DeleteMax() (int32, interface{ … } func (t *T) Size() int { … } // 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, y interface{ … } // 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, y interface{ … } // 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, y interface{ … } func (t *T) Iterator() Iterator { … } func (t *T) Equals(u *T) bool { … } func (t *T) String() string { … } func (t *node32) equals(u *node32) bool { … } func (t *T) Equiv(u *T, eqv func(x, y interface{ … } func (t *node32) equiv(u *node32, eqv func(x, y interface{ … } type iterator … type Iterator … func (it *Iterator) Next() (int32, interface{ … } func (it *Iterator) Done() bool { … } func (t *node32) iterator() iterator { … } func (it *iterator) leftmost(t *node32) { … } func (it *iterator) done() bool { … } func (it *iterator) next() *node32 { … } // 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{ … } // 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{ … } // 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 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{ … } // 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 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{ … } func (t *node32) isLeaf() bool { … } func (t *node32) visitInOrder(f func(int32, interface{ … } func (t *node32) find(key int32) *node32 { … } func (t *node32) min() *node32 { … } func (t *node32) max() *node32 { … } func (t *node32) glb(key int32, allow_eq bool) *node32 { … } func (t *node32) lub(key int32, allow_eq bool) *node32 { … } func (t *node32) aInsert(x int32) (newroot, newnode, oldnode *node32) { … } func (t *node32) aDelete(key int32) (deleted, newSubTree *node32) { … } func (t *node32) aDeleteMin() (deleted, newSubTree *node32) { … } func (t *node32) aDeleteMax() (deleted, newSubTree *node32) { … } func (t *node32) aRebalanceAfterLeftDeletion(oldLeftHeight int8, tleft *node32) *node32 { … } func (t *node32) aRebalanceAfterRightDeletion(oldRightHeight int8, tright *node32) *node32 { … } // 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) *node32 { … } // 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) *node32 { … } // rightToRoot does that rotation, modifying t and t.right in the process. func (t *node32) rightToRoot() *node32 { … } // leftToRoot does that rotation, modifying t and t.left in the process. func (t *node32) leftToRoot() *node32 { … } func (t *node32) copy() *node32 { … }
Codebase Browser
go