-- File: AVLSearchTree.cdl -- Created: Tue May 21 17:43:21 1991 -- Author: Annick PANCHER -- -- Revised: Mireille MERCIEN -- -- J.P. TIRAULT -- Feb,19 1993 -- Adaptation of this persistent structure to a transient -- structure. -- J.P. TIRAULT -- R.BARRETO -- Aug,11 1993 -- Update of method AVLSearchTree::Find. This method returns -- a boolean status according to the method finds the Item or not. -- Update of method AVLIterator::Value. This method returns an -- Item. ---Copyright: Matra Datavision 1992,1993 generic class AVLSearchTree from TCollection ( Item as any; Comparator as Compare(Item)) ---Purpose: Defines a binary search tree, e.g. an ordered and -- balanced binary tree. An AVLSearchTree is created -- with a kind of Item and a Comparator. It's -- composed with Nodes. One item is contained only by -- one Node, and a 'count' stores the number of its -- occurences. -- The only public operations on an AVLSearchTree, -- except reading ( the number of its Nodes, its Root -- or the Node containing an item) are to insert or -- remove an item, plus, of course, to find an item. -- Then, it's possible to ask to a Node its value, -- the number of occurences of this value, and its -- right and left children. Other methods of Node are -- private and called by the private methods of -- AVLSearchTree which manage the Find method, and -- Insert and Remove operations, always ensuring -- order and balance. -- 1. ORDER : -- If the tree contains three elements A,B,C, which -- are ordered, regarding to a comparator Comp, as -- following: -- A < B < C -- Then TheRoot of the tree will contain B, with A as -- LeftChild and C as RightChild. -- Each element on the left of a node A are 'lower' -- than A in respect with the used comparator, and -- each element on its right are greater. -- 2. BALANCE : The height of two children of a Node -- will never have a difference of more than one -- level. An AVLSearch Tree is ALWAYS balanced. -- Keywords: binary tree, ordered, balanced -- Warning: To use an AVLSearchTree, since it's ordered and -- balanced each time an item is inserted or removed, -- may be a bad choice if there are more changing -- operations than searching requests, for -- performances criterias. It can be judicious to -- use it when there are many items to consult -- frequently. -- References: Classix, Reusable C++ Components( Empathy -- incorporated, 1990). -- Algorithms are attributed to -- G.M.Adel'son-Vel'skii and E.M.Landis, 1962. uses Side raises NoSuchObject from Standard, NoMoreObject from Standard class AVLList from TCollection inherits TShared from MMgt is Create returns mutable AVLList from TCollection; ---C++: inline Value(me) returns Item; ---C++: inline ---C++: return & Next(me) returns Address; ---C++: inline ---C++: return & fields myValue : Item; myNext : Address from Standard; end; class AVLNode from TCollection inherits AVLBaseNode from TCollection uses AVLBaseNodePtr from TCollection is Create(I : Item; r,l : AVLBaseNodePtr from TCollection) returns AVLNode from TCollection; ---C++: inline Copy(myclass; ANode : AVLBaseNodePtr from TCollection) returns AVLBaseNodePtr from TCollection; RecursiveCopy(myclass; ANode,aCopy : AVLBaseNodePtr from TCollection); Value(me) returns Item; ---C++: inline ---C++: return & fields myValue : Item; friends class AVLList from TCollection end; class AVLIterator raises NoMoreObject from Standard, NoSuchObject from Standard is ---Purpose: This class provides to iterate on an AVLSearchTree. -- The type of traversal is the in-order traversal. -- Example : If the AVLTree is the following: -- 5 -- 2 7 -- 1 3 6 8 -- -- The result is: -- 1 2 3 5 6 7 8 -- -- During the exploration of the tree no updating of the -- tree must be done. -- Create( aTree: AVLSearchTree) ---Purpose: Creates an iterator on from the root of the -- AVLSearchtree. returns AVLIterator; Create( aTree: AVLSearchTree; theItem : Item) ---Purpose: Creates an iterator on from the node that -- contains the Item (It is not necessary the root of the tree). returns AVLIterator; More( me ) ---Level: Public ---Purpose: Returns True if there is still an element to be read ---C++: inline returns Boolean from Standard is static; Next( me: in out) raises NoMoreObject from Standard; ---Level: Public ---Purpose: Goes to next element of Value( me) returns Item raises NoSuchObject from Standard; ---Level: Public ---C++: return const & Clear (me: in out) is static ; ---Level: Public ---Purpose: Empties my structure, so that if next call on , -- it will raise an exception NoMoreObject InOrderTraversal (me : in out ; A : Address) is static private; ---Level: Internal ---Purpose: Internal method. fields FirstNode : Address; HasMore : Boolean; end; ------------------------------ AVLSearchTree -------------------------------- is Create( aComparator: Comparator) ---Purpose: creates an empty tree (root points to NULL) returns AVLSearchTree; IsEmpty( me) ---Level: Public ---Purpose: Returns true if the tree is empty. ---Category: Reading ---C++: inline returns Boolean from Standard is static; Extent( me) ---Level: Public ---Purpose: Returns number of different items contained by ---Category: Reading returns Integer from Standard is static; TotalExtent( me) ---Level: Public ---Purpose: Returns total number of items (considers account -- of each Node) ---Category: Reading returns Integer from Standard is static; Find( me; theItem: Item) ---Level: Public ---Purpose: Returns the Node containing ---Category: Reading returns Boolean is static; Find( me; theItem: Item; theOrig: in out Item) ---Level: Public ---Purpose: Returns the Node containing ---Category: Reading returns Boolean is static; GetRoot( me) returns Address is static; ---Level: Public ---Purpose: Returns the Root of the tree . ---Category: Reading ---C++: inline GetComparator( me) returns Comparator is static; ---Level: Public ---Purpose: Returns the Comparator of the tree . ---Category: Reading ---C++: inline Insert( me : in out ; theItem: Item) is static; ---Level: Public ---Purpose: Inserts at the right place; if it's -- already in , only changes its . -- Before -- me = ( i5( i3( i1)) -i7) and theItem = i2 -- After -- me = ( i5( i2( i1 -i3)) -i7)) -- ( i means LeftChild, -i means RightChild) ---Category: Writing InsertOnce(me : in out ; theItem: Item) ---Level: Public ---Purpose: Inserts at the right place, but only if -- it isn't already in ; Returns False if already there. -- Before -- me = ( i5( i3( i1)) -i7) and theItem = i3 -- After -- me = ( i5( i3( i1)) -i7) and return False ---Category: Writing returns Boolean from Standard is static; Remove( me : in out; theItem : Item) ---Level: Public ---Purpose: Removes from the Node containing , -- if its count=1, or reduces its count if count>1; -- in this aim, calls the recursive method -- RecursiveRemove, with =False; -- Before -- me = ( i5( i3( i1)) -i7) and theItem = i7 -- After -- me = ( i3( i1 -i5)) if count(i7)=1 -- Or -- me = ( i5( i3( i1)) -i7) if count(i7)>1 ---Category: Writing raises NoSuchObject from Standard is static; RemoveAll( me : in out; theItem: Item) ---Level: Public ---Purpose: removes from the Node containing ; -- in this aim, calls the recursive method -- RecursiveRemove, with =True; -- Before -- me = ( i5( i3( i1)) -i7) and theItem = i7 -- After -- me = ( i3( i1 -i5)) ---Category: Writing raises NoSuchObject from Standard is static; Merge (me; another:AVLSearchTree) ---Level: Public ---Purpose: creates a third one from and ---Category: Writing returns AVLSearchTree is static; SetRoot(me : in out ; theNode: Address) ---Level: Internal is static private; ---C++: inline RotateLeft( me ; theNode : in out Address) ---Level: Internal ---Purpose: Right child A of becomes the parent, and -- becomes its left child; left child of A -- becomes the right child of . This -- rotation will permit to balance after a -- pertubating action ( insert or remove) on it. is static private; RotateRight( me ; theNode : in out Address) ---Level: Internal ---Purpose: left child A of becomes the parent, and -- becomes its right child; right child of -- A becomes the left child of . This -- rotation will permit to balance after a -- pertubating action ( insert or remove) on it. is static private; LeftBalance( me; theNode : in out Address) ---Level: Internal ---Purpose: called after inserting or removing an item, if the -- left branch of is too long is static private; RightBalance( me ; theNode : in out Address) ---Level: Internal ---Purpose: Called after inserting or removing an item, if the -- right branch of is too long. is static private; InsertBalance( me ; theNode : in out Address; theFather: Address; theSide : Side) ---Level: Internal ---Purpose: Balances after inserting an item. returns Boolean from Standard is static private; RemoveBalance( me ; theNode : in out Address; theFather: Address; theSide : Side) ---Level: Internal ---Purpose: Balances after removing an item. returns Boolean from Standard is static private; RecursiveInsert( me ; theNode : in out Address; theFather: Address; theSide : Side; theItem : Item; forOnce : in out Boolean from Standard) ---Level: Internal ---Purpose: Recursive method to insert a new Node OR to find -- the existing one containing and increase -- its count. -- Returns True when a new Node has been created to -- know it needs to be balanced, and then returns -- False again. returns Boolean from Standard is static private; Find ( me ; theItem : Item ; theNode : in out Address) returns Boolean is static private; ---Level: Internal ---Purpose: Returns the Node associated to the Item. RecursiveRemove( me ; theNode : in out Address; theFather: Address; theSide : Side; theItem : Item; forAll : Boolean from Standard) ---Level: Internal ---Purpose: Recursive method to find the Node containing -- . In case it's , removes it if -- is True, or reduces its count if -- is False. -- Returns True when theItem has been found returns Boolean from Standard is static private; ShallowCopy(me) returns AVLSearchTree; ---Level: Advanced ---C++: function call fields TheRoot : Address from Standard; TheComparator : Comparator; friends class AVLIterator from TCollection end;