path: root/src/TCollection/TCollection_AVLSearchTree.cdl

-- File:	AVLSearchTree.cdl
-- Created:	Tue May 21 17:43:21 1991
-- Author:	Annick PANCHER
--		<apc@topsn2>
-- Revised:	Mireille MERCIEN
--		<jpt@sdsun3>
--		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 <aTree> from the root of the
	    -- AVLSearchtree.
    	    returns AVLIterator;

        Create( aTree: AVLSearchTree; theItem : Item)
	    ---Purpose: Creates an iterator on <aTree> 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 <me>
    
    	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 <me>,
	    -- 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 <me>
	---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 <theItem>
	---Category: Reading
    	returns Boolean
        is static;    

    Find( me; theItem: Item; theOrig: in out Item)
        ---Level: Public
	---Purpose: Returns the Node containing <theItem>
	---Category: Reading
    	returns Boolean
        is static;    
		
    
    GetRoot( me)
    	returns Address
        is static;    
        ---Level: Public
	---Purpose: Returns the Root of the tree <me>.
	---Category: Reading
	---C++: inline

    GetComparator( me)
    	returns Comparator
        is static;    
        ---Level: Public
	---Purpose: Returns the Comparator of the tree <me>.
	---Category: Reading
	---C++: inline

    Insert( me : in out ; theItem: Item)
        is static;    
        ---Level: Public
    	---Purpose: Inserts <theItem>  at  the  right place;  if  it's
	-- already in <me>, only changes its <count>.
	-- 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 <theItem> at the right place,  but only if
	-- it isn't already in <me>; 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 <me> the  Node containing <theItem>,
	--          if its count=1,  or reduces its  count if count>1;
	--          in    this   aim,  calls   the   recursive  method
	--          RecursiveRemove, with <forAll>=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 <me>  the Node containing <theItem>;
	--          in   this  aim,  calls   the   recursive    method
	--          RecursiveRemove, with <forAll>=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 <me> and <another>
	---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 <theNode> becomes the parent, and
	-- <theNode> becomes its left  child; left child of A
	-- becomes  the  right  child of  <theNode>.     This
	-- rotation will  permit to  balance   <me>  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 <theNode> becomes  the parent, and
	-- <theNode> becomes its right  child; right child of
	-- A  becomes  the left  child    of <theNode>.  This
	-- rotation  will permit to   balance  <me>  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 <theNode> 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 <theNode> is too long.
    	is static private;

    InsertBalance( me ; theNode  : in out Address; 
    	    	        theFather: Address;
    	    	        theSide  : Side)
        ---Level: Internal
	---Purpose: Balances <me> 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 <me> 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 <theItem> 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
	-- <theItem>.  In case it's <theNode>,  removes it if
	-- <forAll> is True, or reduces its count if <forAll>
	-- 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;