B-TREE <DEFINITION MODULE - GENERIC>
Author Message
B-TREE <DEFINITION MODULE - GENERIC>

(****************************************************)
(* THIS IS B-TREE FOR MODULA 2 - I HAD AN ASSIGNMENT*)
(* TO BUILD A LIBRARY FOR IT AND THIS IS THE RESULT *)
(* IT SHOULDN'T BE TOO DIFFICULT TO UNDERSTAND AND  *)
(* IT IS GENERIC SO IT CAN BE USED WITH ANY TYPE.   *)
(* LET ME KNOW IF YOU FIND ANY BUGS IN IT SO I CAN  *)
(* FIX IT BEFORE THE DUE DATE AND MORE IMPORTANTLY  *)
(* WHAT YOU THINK.                                  *)
(*                 -Ted Furuya                      *)
(* student of the university of Lethbridge          *)
(* NOTE : insert, search, and delete came out of a  *)
(* book called "Further Topics on Trees"            *)
(****************************************************)

DEFINITION MODULE BTree;

FROM Texts IMPORT TEXT;

CONST max = 4;
min = 2; (* Number of Elements *)

TYPE          BTree;
btree;
Order      = (preOrder,inOrder,postOrder,revOrder);

(**************************************************************************)
(* AvgProbeLength - This function  returns a the average probe length to  *)
(* get to a node in a given tree.  The average returned is in the form    *)
(* of a real number.                                                      *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE AvgProbeLength(B: BTree):REAL;

(**************************************************************************)
(* Contents - This function takes in a node and a given position and      *)
(* returns the key that in that location in the form of an ADDRESS.       *)
(* PARAMETERS:                                                            *)
(* b - is the imported node.                                              *)
(* pos - is the imported position of the key.                             *)
(**************************************************************************)

(**************************************************************************)
(* CopyTree - This function takes in a B-Tree structure and makes a       *)
(* duplicate copy of it and returns it in the form of another B-Tree.     *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE CopyTree(B: BTree):BTree;

(**************************************************************************)
(* Delete - This procedure takes a target key and removes it from the     *)
(* B-Tree structure if it exists.  If the key is not found it does        *)
(* nothing.                                                               *)
(* PARAMETERS:                                                            *)
(* target - is the imported target key to be deleted.                     *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE Delete(target: ADDRESS; VAR B: BTree);

(**************************************************************************)
(* DeleteLeaves - This procedure takes a given tree and removes all the   *)
(* leaves in that tree (it deletes the bottom level of that tree).  If    *)
(* the tree is empty then nothing is done.                                *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE DeleteLeaves(VAR B: BTree);

(**************************************************************************)
(* DeleteTree - This procedure deletes a tree so that no elements are left*)
(* existing within that B-Tree structure.                                 *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE DeleteTree(VAR B: BTree);

(**************************************************************************)
(* ElementCount - is a function that thats in a B-Tree structure and      *)
(* returns the number of elements that exist in that tree in the form     *)
(* of an integer.                                                         *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE ElementCount(B: BTree):INTEGER;

(**************************************************************************)
(* EmptyTree - is a function that takes a B-Tree structure and returns    *)
(* TRUE if that tree contains no elements and FALSE otherwise.            *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE EmptyBTree(B: BTree):BOOLEAN;

(**************************************************************************)
(* EmptyNode - is a function that takes a node and returns a boolean      *)
(* TRUE if that node contains no elements and FALSE otherwise.            *)
(* PARAMETERS:                                                            *)
(* b - is the imported node.                                              *)
(**************************************************************************)
PROCEDURE EmptyNode(b: btree):BOOLEAN;

(**************************************************************************)
(* GetChild - is a function that takes a node and a path and returns a    *)
(* child of that node by the path given.                                  *)
(* PARAMETERS:                                                            *)
(* b - is the imported node.                                              *)
(* path - is the imported path.                                           *)
(**************************************************************************)
PROCEDURE GetChild(b: btree; path: INTEGER):btree;

(**************************************************************************)
(* GetLeftCorner - is a function that takes a B-Tree structure and returns*)
(* the left most bottom node in that tree.                                *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE GetLeftCorner(B:BTree):btree;

(**************************************************************************)
(* GetParent - is a function that takes a B-Tree structure and a given    *)
(* node and returns that node's parent.  If the node passed in is the     *)
(* root then that node is passed back since it has no parent.             *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* b - is the imported node.                                              *)
(**************************************************************************)
PROCEDURE GetParent(B: BTree;b: btree):btree;

(**************************************************************************)
(* GetRightCorner- is a function that takes a B-Tree structure and returns*)
(* the right most bottom node of that tree.                               *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE GetRightCorner(B:BTree):btree;

(**************************************************************************)
(* Height - is a function that returns the height of a tree in the form   *)
(* of an integer.                                                         *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE Height(B: BTree):INTEGER;

(**************************************************************************)
(* InitTree - is a procedure that creates a B-Tree structure.             *)
(* PARAMETERS:                                                            *)
(* B - is the B-Tree structure to be exported.                            *)
(* valueSize - is the amount of space a key will take in bytes.           *)
(* print - is the imported print procedure defined by the user.           *)
(* less  - is the imported less than compare procedure defined by the user*)
(* equal - is the imported equal compare procedure defined by the user.   *)
(**************************************************************************)
PROCEDURE InitTree (VAR B: BTree; valueSize: INTEGER; print: PrintProc;
less: CompProc; equal: CompProc);

(**************************************************************************)
(* IsChild - is a function that takes a given node and a key and returns  *)
(* a boolean TRUE if that key is a child of the given node and FALSE      *)
(* otherwise.                                                             *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* b - is the imported node.                                              *)
(* element - is the imported key to check for.                            *)
(**************************************************************************)
PROCEDURE IsChild(B: BTree; b: btree; element: ADDRESS):BOOLEAN;

(**************************************************************************)
(* Insert - is a procedure that takes a newkey and inserts it into an     *)
(* existing B-Tree structure. If the element already exists then the      *)
(* insert is not performed.                                               *)
(* PARAMETERS:                                                            *)
(* newkey - is the imported key.                                          *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE Insert(newkey: ADDRESS; VAR B: BTree);

(**************************************************************************)
(* IsLeaf - is a function that takes a node and returns a boolean TRUE    *)
(* if the node is a leaf and FALSE otherwise.                             *)
(* PARAMETERS:                                                            *)
(* b - is the imported node.                                              *)
(**************************************************************************)
PROCEDURE IsLeaf(b: btree):BOOLEAN;

(**************************************************************************)
(* LevelElementCount - is a function that takes a given B-Tree structure  *)
(* and a level number and returns the number of keys that exist on that   *)
(* level.                                                                 *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* level - is the imported level to check.                                *)
(**************************************************************************)
PROCEDURE LevelElementCount(B: BTree; level: INTEGER):INTEGER;

(**************************************************************************)
(* LevelNodeCount -    is a function that takes a given B-Tree structure  *)
(* and a level number and returns the number of nodes that exist on that  *)
(* level.                                                                 *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* level - is the imported level to check.                                *)
(**************************************************************************)
PROCEDURE LevelNodeCount(B: BTree; level: INTEGER):INTEGER;

(**************************************************************************)
(* LoadBTree - is a function that takes a B-Tree structure and a name     *)
(* and saves that tree to a binary file by the name given.                *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* name - is the imported name of the file.                               *)
(**************************************************************************)
PROCEDURE LoadBTree(B: BTree; name: ARRAY OF CHAR);

(**************************************************************************)
(* MergeTree - is a function that merges two trees into a new one and then*)
(* returns the result. The old trees are not destroyed.                   *)
(* PARAMETERS:                                                            *)
(* B1,B2 - are the imported B-Tree structures.                            *)
(**************************************************************************)
PROCEDURE MergeBTree(B1, B2: BTree):BTree;

(**************************************************************************)
(* NumEntries - is a function that takes a node and returns the number of *)
(* keys that exist in that node.                                          *)
(* PARAMETERS:                                                            *)
(* b - is the imported node.                                              *)
(**************************************************************************)
PROCEDURE NumEntries(b:btree):INTEGER;

(**************************************************************************)
(* PrintLevel - is a procedure that takes a B-Tree structure and a level  *)
(* number and prints that level.                                          *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* level - is the imported level to print.                                *)
(**************************************************************************)
PROCEDURE PrintLevel(B: BTree; level: INTEGER);

(**************************************************************************)
(* PrintNode - is a procedure that prints a given node.                   *)
(* PARAMETERS:                                                            *)
(* B - is the B-Tree structure.                                           *)
(* b - is the imported node.                                              *)
(**************************************************************************)
PROCEDURE PrintNode(B: BTree; b: btree);

(**************************************************************************)
(* PrintSubTree - is a procedure that prints a sub-tree and not the entire*)
(* tree itself.                                                           *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* b - is the imported node to start printing from.                       *)
(**************************************************************************)
PROCEDURE PrintSubTree(B: BTree; b: btree);

(**************************************************************************)
(* PrintTree - is a procedure that prints the entire tree.                *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE PrintTree(B: BTree);

(**************************************************************************)
(* Root - is a function  that takes a B-Tree structure and returns the    *)
(* root of the tree.                                                      *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(**************************************************************************)
PROCEDURE Root(B: BTree):btree;

(**************************************************************************)
(* SaveBTree- is a procedure that takes a B-Tree and a name and saves that*)
(* tree to a binary file.                                                 *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* name - is the imported name of the file.                               *)
(**************************************************************************)
PROCEDURE SaveBTree(VAR B: BTree; name: ARRAY OF CHAR);

(**************************************************************************)
(* Search - is a procedure that searches a B-Tree structure for a given   *)
(* key.  If it is found it sets the found parameter to true and sets      *)
(* targetnode to point to the node location of the key and targetpos to   *)
(* the position of the key within that node.                              *)
(* PARAMETERS:                                                            *)
(* target - is the key to search for.                                     *)
(* B - is the B-Tree structure to search through.                         *)
(* found - is the boolean exported to indicate if the key was found.      *)
(* targetnode - is the node location of the key exported if it was found. *)
(* targetpos - is the position of that key exported if it was found.      *)
(**************************************************************************)
PROCEDURE Search(target: ADDRESS; B: BTree; VAR found: BOOLEAN;
VAR targetnode: btree; VAR targetpos: INTEGER);

(**************************************************************************)
(* SplitTree - is a procedure that splits a B-Tree and exports  two new   *)
(* trees created from the original one.  The original tree is not         *)
(* destroyed. A pivot is used to indicate where the tree should be split  *)
(* eveything less then the pivot will be put in B1 and everything greater *)
(* or equal to the pivot will be put in B2.                               *)
(* PARAMETERS:                                                            *)
(* B - is the imported B-Tree structure.                                  *)
(* pivot - is the imported pivot point.                                   *)
(* B1,B2 - are the exported B-Tree that are to be created.                *)
(**************************************************************************)
PROCEDURE SplitBTree(B: BTree; pivot: ADDRESS; VAR B1: BTree; VAR B2: BTree);

(**************************************************************************)
(* TraverseTree - is a procedure that traverses the tree and performs an  *)
(* imported operation on that tree.                                       *)
(* PARAMETERS:                                                            *)
(* ord - is the imported type of traversal.                               *)
(* B - is the imported B-Tree structure.                                  *)
(* visit - is the imported operation to be performed.                     *)
(* addr - is an extra imported address for use with the visit operation.  *)
(**************************************************************************)