Oberon || Library || Module Index || Search Engine || Definition || Module


Ulm's Oberon Library:
AVLTrees


NAME

AVLTrees - height-balanced-binary trees for data-storage and retrieval

SYNOPSIS

CONST ascending = 0;
CONST descending = 1;
TYPE Order = Iterators.Mode (* ascending, descending *)


TYPE AVLTree = POINTER TO AVLTreeRec; TYPE AVLTree = RECORD (Services.ObjectRec) END; CONST keyUsed = 0 CONST noSuchKey = 1 CONST wrongKey = 2 CONST errorcodes = 3

TYPE ErrorCode = SHORTINT; TYPE ErrorEvent = POINTER TO ErrorEventRec; TYPE ErrorEventRec = RECORD (Events.EventRec) errorcode: ErrorCode; avlTree: AVLTree; object: Services.Object; key: Keys.Value; END;

VAR error: Events.EventType; VAR errormsg: ARRAY errorcodes OF Events.Message;

PROCEDURE Create(VAR new: AVLTree; key: Keys.Key); PROCEDURE GetKey(avlTree: AVLTree; VAR key: Keys.Key); PROCEDURE Add(avlTree: AVLTree; object: Services.Object) : BOOLEAN PROCEDURE Remove(avlTree: AVLTree; keyval: Keys.Value) : BOOLEAN; PROCEDURE Get(avlTree: AVLTree; keyval: Keys.Value; VAR object: Services.Object) : BOOLEAN; PROCEDURE Card(avlTree: AVLTree) : INTEGER; PROCEDURE GetEntries(avlTree: AVLTree; order: Order; from, to: Keys.Value; VAR it: Iterators.Iterator); PROCEDURE Exists(avlTree: AVLTree; keyValue: Keys.Value) : BOOLEAN;

DESCRIPTION

AVLTrees implements AVL trees (named after Adelson-Velsky and Landis, the inventors). Every AVL tree has an associated key with a total-order relation (see Keys) and allows to store and retrieve objects that support that key. As AVL trees are sorted height-balanced binary trees, all operations have a worst cases time of log(N) where N is the number of objects stored in the AVL tree.

Create creates an empty AVL tree. All objects to be added to this AVL tree are expected to support key which defines the sorting order.

GetKey returns the key of the given AVL tree.

Add adds object to the AVL tree. This means, it can be retrieved by the key components as defined by the key of the given AVL tree. There must not be an object with the same value (of its key) in the AVL tree. Add returns TRUE if object has been added to avlTree, otherwise FALSE.

Remove removes an object from the AVL tree specified by the given key. A return value of TRUE indicates success.

Get returns the object with the given value (with respect to key), if the AVL tree contains such an object. Otherwise noSuchKey is raised. A return value of TRUE indicates success.

Card returns the number of objects in the AVL tree.

GetEntries returns an iterator of objects in AVL tree. Possible orders are ascending and descending. The range of objects to be iterated can be narrowed by from and to. If NIL is given for from (respectively to), iteration starts at the first (respectively stops at the last) object. Note, that iteration must not be carried on over changing operations on the AVL tree.

Exists returns TRUE, iff the AVL tree contains an object with the given value (with respect to key).

DIAGNOSTICS

Errors lead to events raised by AVLTrees or an underlying implementation. Following errors may be raised by AVLTrees:
keyUsed
There is already an object with this value (with respect to key) in the AVL tree.
noSuchKey
The AVL tree contains no object with this value (of its key).
wrongKey
A parameter does not support the needed key.

SEE ALSO

Keys
support of total-order relations

AUTHOR

Sven Lutz
Edited by: borchert, last change: 2004/07/19, revision: 1.2, converted to HTML: 2004/07/19

Oberon || Library || Module Index || Search Engine || Definition || Module