abt

Documentation

Index

• Constants
• type Iterator
  • func (it *Iterator) Done() bool
  • func (it *Iterator) Next() (int32, interface{})
• type T
  • func (t *T) Copy() *T
  • func (t *T) Delete(x int32) interface{}
  • func (t *T) DeleteMax() (int32, interface{})
  • func (t *T) DeleteMin() (int32, interface{})
  • func (t *T) Difference(u *T, f func(x, y interface{}) interface{}) *T
  • func (t *T) Equals(u *T) bool
  • func (t *T) Equiv(u *T, eqv func(x, y interface{}) bool) bool
  • func (t *T) Find(x int32) interface{}
  • func (t *T) Glb(x int32) (k int32, d interface{})
  • func (t *T) GlbEq(x int32) (k int32, d interface{})
  • func (t *T) Insert(x int32, data interface{}) interface{}
  • func (t *T) Intersection(u *T, f func(x, y interface{}) interface{}) *T
  • func (t *T) IsEmpty() bool
  • func (t *T) IsSingle() bool
  • func (t *T) Iterator() Iterator
  • func (t *T) Lub(x int32) (k int32, d interface{})
  • func (t *T) LubEq(x int32) (k int32, d interface{})
  • func (t *T) Max() (k int32, d interface{})
  • func (t *T) Min() (k int32, d interface{})
  • func (t *T) Size() int
  • func (t *T) String() string
  • func (t *T) Union(u *T, f func(x, y interface{}) interface{}) *T
  • func (t *T) VisitInOrder(f func(int32, interface{}))

Constants

const (
	LEAF_HEIGHT = 1
	ZERO_HEIGHT = 0
	NOT_KEY32   = int32(-0x80000000)
)

Types

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

func (*Iterator) Done

func (it *Iterator) Done() bool

func (*Iterator) Next

func (it *Iterator) Next() (int32, interface{})

type T

type T struct {
	// contains filtered or unexported fields
}

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.

func (*T) Copy

func (t *T) Copy() *T

func (*T) Delete

func (t *T) Delete(x int32) interface{}

func (*T) DeleteMax

func (t *T) DeleteMax() (int32, interface{})

func (*T) DeleteMin

func (t *T) DeleteMin() (int32, interface{})

func (*T) Difference

func (t *T) Difference(u *T, f func(x, y interface{}) interface{}) *T

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) Equals

func (t *T) Equals(u *T) bool

func (*T) Equiv

func (t *T) Equiv(u *T, eqv func(x, y interface{}) bool) bool

func (*T) Find

func (t *T) Find(x int32) interface{}

Find returns the data associated with x in the tree, or nil if x is not in the tree.

func (*T) Glb

func (t *T) Glb(x int32) (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) GlbEq

func (t *T) GlbEq(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) Insert

func (t *T) Insert(x int32, data interface{}) 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) Intersection

func (t *T) Intersection(u *T, f func(x, y interface{}) interface{}) *T

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) IsEmpty

func (t *T) IsEmpty() bool

IsEmpty returns true iff t is empty.

func (*T) IsSingle

func (t *T) IsSingle() bool

IsSingle returns true iff t is a singleton (leaf).

func (*T) Iterator

func (t *T) Iterator() Iterator

func (*T) Lub

func (t *T) Lub(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) LubEq

func (t *T) LubEq(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) Max

func (t *T) Max() (k int32, d interface{})

Max returns the maximum element of t. If t is empty, then (NOT_KEY32, nil) is returned.

func (*T) Min

func (t *T) Min() (k int32, d interface{})

Min returns the minimum element of t. If t is empty, then (NOT_KEY32, nil) is returned.

func (*T) Size

func (t *T) Size() int

func (*T) String

func (t *T) String() string

func (*T) Union

func (t *T) Union(u *T, f func(x, y interface{}) interface{}) *T

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) VisitInOrder

func (t *T) VisitInOrder(f func(int32, interface{}))

VisitInOrder applies f to the key and data pairs in t, with keys ordered from smallest to largest.