ADTTree

A RBTree (red-black) is a variant of binary search tree. The trees keep the order of nodes on insertion/delete and allow for fast find operations. It has O(log n) worst-case time for each operation.

If life time handling of allocated elements is needed the callback procedures duplicate and dispose can be used.

By default the tree only takes references of elements and the caller is responsible for keeping elements alive.

Reference to Wikipedia page on the subject for implementation details. Adapted from https://github.com/sakeven/RbTree License MIT.

Types

DuplicateElementProc* = PROCEDURE(VAR dst: Element;

Procedures

DefaultDuplicateElement

defaults to assignment

PROCEDURE DefaultDuplicateElement* (VAR dst: Element; src-: Element);

DefaultDisposeElement

defaults to no operation

PROCEDURE DefaultDisposeElement* (VAR dst: Element);

Tree.Init

Initialize

PROCEDURE (VAR this : Tree) Init*;

Tree.Size

Returns the size of the tree.

PROCEDURE (VAR this-: Tree) Size* (): LENGTH;

Tree.Dispose

Removes all elements from the tree.

PROCEDURE (VAR this: Tree) Dispose*;

Tree.HasElement

Return TRUE if tree has element equal to given element

PROCEDURE (VAR this- : Tree) HasElement*(element- : Element): BOOLEAN;

Tree.First

Forward iterator for the tree.

PROCEDURE (VAR this-: Tree) First* (VAR iterator: Iterator);

Tree.Last

Reverse iterator for the tree.

PROCEDURE (VAR this-: Tree) Last* (VAR iterator: Iterator);

Tree.FindForward

Forward iterator where element is found.

PROCEDURE (VAR this-: Tree) FindForward* (VAR iterator: Iterator; element- : Element);

Tree.FindReverse

Reverse iterator where element is found.

PROCEDURE (VAR this-: Tree) FindReverse* (VAR iterator: Iterator; element- : Element);

Iterator.Next

Advance iterator. Return FALSE if end is reached. Note: this potentially set the element to a reference.

PROCEDURE (VAR this: Iterator) Next* (VAR element: Element): BOOLEAN;

Tree.Insert

Insert or replace element

PROCEDURE (VAR this : Tree) Insert*(element-: Element);

Tree.Remove

Remove node from tree if found. Return TRUE if item present and it was removed

PROCEDURE (VAR this : Tree) Remove*(element- : Element): BOOLEAN;