Documentation
¶
Overview ¶
This package implements balanced and threaded trees (D. E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching). Trees may be sorted or not; they are guaranteed to be sorted if insertion of values are made through the method 'SearchIns' (with a correct total 'Comparer'); if methods 'Insert', 'Prepend', 'Append' or 'Cat' are used, sorting may not be maintained. With sorted trees, methods 'SearchIns', 'Search', 'SearchNext' and 'Delete' can be used, but not with unsorted trees; all other methods may be used with all trees.
Index ¶
- Constants
- type Comp
- type Comparer
- type Copier
- type DoFunc
- type Elem
- type Tree
- func (t *Tree) Append(key interface{})
- func (t1 *Tree) Cat(t2 *Tree)
- func (t *Tree) Copy() *Tree
- func (t *Tree) Delete(key Comparer) bool
- func (t *Tree) Empty()
- func (t *Tree) Erase(rank int)
- func (t *Tree) Find(rank int) (res *Elem, found bool)
- func (t *Tree) Insert(key interface{}, rank int)
- func (t *Tree) IsEmpty() bool
- func (t *Tree) Next(e *Elem) *Elem
- func (t *Tree) NumberOfElems() int
- func (t *Tree) Prepend(key interface{})
- func (t *Tree) Previous(e *Elem) *Elem
- func (t *Tree) Search(key Comparer) (res *Elem, found bool, rank int)
- func (t *Tree) SearchIns(key Comparer) (res *Elem, found bool, rank int)
- func (t *Tree) SearchNext(key Comparer) (res *Elem, found bool, rank int)
- func (t1 *Tree) Split(after int) (t2 *Tree)
- func (t *Tree) WalkThrough(do DoFunc, p ...interface{})
Constants ¶
const ( //Results of comparison. Lt = Comp(-1) //less than Eq = Comp(0) //equal Gt = Comp(+1) //greater than )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Comparer ¶
type Comparer interface {
// Compare two values; the comparison must be reflexive, transitive, antisymmetric and total.
Compare(Comparer) Comp
}
Values in elements of trees must verify the interface 'Comparer' if these trees implement the methods 'SearchIns', 'Search', 'SearchNext' or 'Delete'; in this case, if the methods 'Insert', 'Prepend', 'Append' and 'Cat' are not used, trees remain sorted.
type Copier ¶
type Copier interface {
// Copy a value.
Copy() Copier
}
Values in elements of trees must verify the interface 'Copier' if these trees should be copied; for a value 'val', 'val.Copy ()' must return a copy of 'val'.
type DoFunc ¶
type DoFunc func(v interface{}, p ...interface{})
Type of function used by 'WalkThrough'; 'v' is the value of an element of tree, 'p' are parameters.
type Elem ¶
type Elem struct {
// contains filtered or unexported fields
}
Element of a tree.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
A tree.
func (*Tree) Append ¶
func (t *Tree) Append(key interface{})
'Append' inserts the value 'key' at the last place into the tree 't'.
func (*Tree) Cat ¶
'Cat' concatenates the trees 't1' and 't2'; it returns the result in 't1', and 't2' is no more valid.
func (*Tree) Copy ¶
'Copy' returns a copy of 't'; values owned by elements of 't' must verify the interface 'Copier'
func (*Tree) Delete ¶
'Delete' erases the value 'key', if it exists, in the sorted tree 't'; returns true if 'key' is found, else does nothing.
func (*Tree) Erase ¶
'Erase' erases the element at position 'rank' in the tree 't'; 'rank' must verify 1 <= rank <= t.NumberOfElems().
func (*Tree) Find ¶
'Find' finds and returns in 'res' the element at position 'rank' in the tree 't'; if the element does not exist, 'found' is false and 'res' returns nil. The rank of the first element in a tree is 1.
func (*Tree) Insert ¶
'Insert' inserts the value 'key' at the position Min(Max(rank, 1), t.NumberOfElems() + 1) in the tree 't'. The rank of the first element in a tree is 1.
func (*Tree) Next ¶
'Next' returns the element following 'e' in the tree 't'; if 'e' is nil, the first element is returned; if 'e' is the last element of the tree, nil is returned.
func (*Tree) NumberOfElems ¶
'NumberOfElems' returns the number of elements in the tree 't'.
func (*Tree) Prepend ¶
func (t *Tree) Prepend(key interface{})
'Prepend' inserts the value 'key' at the first place into the tree 't'.
func (*Tree) Previous ¶
'Previous' returns the element preceding 'e' in the tree 't'; if 'e' is nil, the last element is returned; if 'e' is the first element of the tree, nil is returned.
func (*Tree) Search ¶
'Search' searches the value 'key' in the sorted tree 't'; if 'key' is found, 'found' is true, the element containing this value is returned in 'res' and its rank in the tree in 'rank'; if 'key' is not found, 'res' is nil, 'found' is false and 'rank' is 0. The rank of the first element in a tree is 1.
func (*Tree) SearchIns ¶
'SearchIns' searches the value 'key' in the sorted tree 't'; if 'key' is found, 'found' is true, the element containing this value is returned in 'res' and its rank in the tree in 'rank'; if 'key' is not found, it is inserted into a new element returned in 'res', 'found' is false and 'rank' returns the rank of the new element. The rank of the first element in a tree is 1.
func (*Tree) SearchNext ¶
SearchNext searches the value 'key' in the sorted tree 't', or the next value if not found; if 'key' is found, 'found' is true, the element containing this value is returned in 'res' and its rank in the tree in 'rank'; if 'key' is not found, 'found' is false, 'res' returns the element containing the next value and its rank is returned in 'rank'; if 'key' is not found and there is no next value, 'res' is nil and 'rank' is 0. The rank of the first element in a tree is 1.
func (*Tree) Split ¶
'Split' splits the tree 't1' after the element of rank 'after'; the result is returned in 't1' and 't2'.
func (*Tree) WalkThrough ¶
'WalkThrough' traverses the tree 't' in inorder and calls the function 'do', with 'p' as parameters, on the value of each element.
Source Files