-- File:	PCollection_HAVLSearchTree.cdl
-- Created:	Tue May 21 17:43:21 1991
-- Author:	Annick PANCHER
--		<apc@topsn2>
-- Revised:	Mireille MERCIEN
--		<jpt@sdsun3>
---Copyright:	 Matra Datavision 1992


generic class HAVLSearchTree from PCollection (
               Item as Storable;
               Comparator as Compare from PCollection(Item))

inherits Persistent
 
---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 from PCollection 


raises NoSuchObject from Standard,
       NoMoreObject from Standard



    class AVLNode  inherits PManaged
    uses Side from PCollection
    is
    
    	---Purpose: Private class. This class provides tools to manipulate
    	-- an AVLSearchTree node.
    
    	Create( theItem: Item)
	    returns mutable AVLNode ;

    	RightChild( me) returns mutable AVLNode;
	    ---Purpose: Reads the value of MyRightChild.    

       	LeftChild( me) returns mutable AVLNode;
	    ---Purpose: Reads the value of MyLeftChild.
    
    	Value( me) returns any Item;
	    ---Purpose: Reads TheItem.
    
    	GetMultiplicity( me)
	    ---Purpose: Returns number of occurences of Item contained
	    --          by <me>.
    	    returns Integer from Standard;
    

    	SetRightChild( me:mutable; theNode: AVLNode);
	    ---Purpose: Modifies the value of MyRightChild.
    
    	SetLeftChild( me:mutable; theNode: AVLNode);
	    ---Purpose: Modifies the value of MyLeftChild.

    	SetChild ( me: mutable; theNode: AVLNode; 
                   theSide: Side from PCollection);
	    ---Purpose: Modifies the value of right or left child.
        
    	SetValue( me:mutable; theValue: Item);
    	    ---Purpose: Modifies the value of TheItem.
    
    	SetMultiplicity( me:mutable; theCount: Integer from Standard);
	    ---Purpose: Modifies the value of Count.
     
        Copy(me)
           returns mutable AVLNode
	   is private;

    	-- REDEFINED

     	ShallowCopy(me) returns mutable like me 
            	is redefined;
	    	---Purpose: ShallowCopy redefinition.
	    	---C++: function call


     	ShallowDump (me; s: in out OStream) 
            	is redefined;
	    	---Purpose: ShallowDump redefinition.
    	    	---C++: function call


    fields
    	MyRightChild: AVLNode;
    	MyLeftChild : AVLNode;
    	MyItem      : Item;
    	Count       : Integer from Standard;
	
    friends class HAVLSearchTree from PCollection
        
    end;

    class AVLNodeStack instantiates HStack(AVLNode);

    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
    	--                      

    	Create( aTree: HAVLSearchTree)
	    ---Purpose: Creates an iterator on <aTree>.
            ---Level: Public
    	    returns AVLIterator;

    	More( me)
	    ---Purpose: Returns True if there is still an element to be read.
            ---Level: Public
	    returns Boolean from Standard;
	    
    	Next( me: in out) raises NoMoreObject from Standard;
	    ---Purpose: Goes to next element of <me>.
            ---Level: Public
    
    	Value( me)
    	    returns mutable AVLNode
            ---Level: Public
    	    raises NoSuchObject from Standard;
	   
        Clear (me: in out);
	    ---Purpose: Empties my structure, so that if next call on <me>,
	    -- it will raise an exception NoMoreObject.
            ---Level: Public

        Append (me: in out; ANode:AVLNode)
            ---Purpose: Adds Nodes to <CurrentStack> from <ANode>.
            ---Level: Internal
	    is private;
    
        RecursiveAppend (me: in out; ANode:AVLNode)
	    ---Purpose: Called by Append to add <ANode> to
	    -- <CurrentStack>, and goes down to left
            ---Level: Internal
	    is private;

        RecursiveRemove (me: in out; ANode:AVLNode)
	    ---Purpose: Called by Next to remove <ANode> and
	    -- the Node which is before in CurrentStack.
	    -- If <ANode> was its rightChild.
            ---Level: Internal
	    is private;
	
fields
    CurrentNode  : AVLNode;
    CurrentStack : AVLNodeStack;
    HasMore      : Boolean;
end;


is

    Create( aComparator: Comparator)
	---Purpose: Creates an empty tree (root points to NULL).
    	returns mutable HAVLSearchTree;
    
    
    IsEmpty( me)
        ---Level: Public
    	returns Boolean from Standard;

    Extent( me)
	---Purpose: Returns  number of different items contained by <me>
        ---Level: Public
    	returns Integer from Standard;
    
    TotalExtent( me)
	---Purpose: Returns total number of items (considers account of each Node)
        ---Level: Public
    	returns Integer from Standard;
    
    Find( me; theItem: Item)
	---Purpose: Returns the Node containing <theItem>.
        ---Level: Public
    	returns AVLNode;
    
    GetRoot( me)
    	returns AVLNode;
        ---Level: Public
    

    Insert( me: mutable; theItem: Item);
	---Purpose: Inserts <theItem>  at  the  right place;  if  it's
	-- already in <me>, only changes its <count>.
        --  Level: Public
	--  Example: 
	-- Before 
	--   me = ( i5( i3( i1)) -i7) and theItem = i2
	-- After
	--   me = ( i5( i2( i1 -i3)) -i7))
	-- ( i means LeftChild, -i means RightChild)

    InsertOnce(me: mutable; theItem: Item)
	---Purpose: Inserts <theItem> at the right place,  but only if
	-- it isn't already in <me>; returns False if already there.
        --  Level: Public
	--  Example:
	-- Before 
	--   me = ( i5( i3( i1)) -i7) and theItem = i3
	-- After
	--   me = ( i5( i3( i1)) -i7) and return False
	returns Boolean from Standard;

    Remove( me : mutable; theItem : Item)
	---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;
        --  Level: Public
	--  Example:
	-- 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
    	raises NoSuchObject from Standard;
    
    RemoveAll( me: mutable; theItem: Item)
	---Purpose: Removes  from <me>  the Node containing <theItem>;
	-- in   this  aim,  calls   the   recursive    method
	-- RecursiveRemove, with <forAll>=True;
        --  Level: Public
	--  Example
	-- Before 
	--   me = ( i5( i3( i1)) -i7) and theItem = i7
	-- After
	--   me = ( i3( i1 -i5))        
    	raises NoSuchObject from Standard;

    Merge (me; another:HAVLSearchTree)
    	---Purpose: Creates a third one from <me> and <another>.
        ---Level: Public
    	returns mutable HAVLSearchTree;

    Copy(me)
        returns mutable HAVLSearchTree
        ---Level: Internal
	is private;

    SetRoot( me: mutable; theNode: mutable AVLNode)
        ---Level: Internal
    	is private;

    RotateLeft( me; theNode : in out mutable AVLNode)
	---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.
        ---Level: Internal
    	is private;

    RotateRight( me; theNode : in out mutable AVLNode)
	---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.
        ---Level: Internal
    	is private;

    LeftBalance( me; theNode : in out mutable AVLNode)
	---Purpose: Called after inserting or removing an item, if the
	-- left branch of <theNode> is too long
        ---Level: Internal
    	is private;

    RightBalance( me; theNode : in out mutable AVLNode)
	---Purpose: Called after inserting or removing an item, if the
	-- right branch of <theNode> is too long.
        ---Level: Internal
    	is private;

    InsertBalance( me; theNode  : in out mutable AVLNode; 
    	    	        theFather: mutable AVLNode;
    	    	        theSide  : Side from PCollection)
	---Purpose: Balances <me> after inserting an item.
    	returns Boolean from Standard
        ---Level: Internal
    	is private;

    RemoveBalance( me; theNode  : in out mutable AVLNode; 
    	    	        theFather: mutable AVLNode;
    	    	        theSide  : Side from PCollection)
	---Purpose: Balances <me> after inserting an item.
        ---Level: Internal
       	returns Boolean from Standard
    	is private;

    RecursiveInsert( me; theNode  : in out mutable AVLNode;
    	    	          theFather: mutable AVLNode;
    	    	          theSide  : Side from PCollection; 
                          theItem  : Item;
    	    	    	  forOnce  : in out Boolean from Standard)
	---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.
        ---Level: Internal
	returns Boolean from Standard
    	is private;

    RecursiveRemove( me; theNode  : in out mutable AVLNode;
    	    	          theFather: mutable AVLNode;
    	    	      	  theSide  : Side from PCollection; 
    	    	       	  theItem  : Item; 
    	    	    	  forAll   : Boolean from Standard)
	---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
        ---Level: Internal
	returns Boolean from Standard
        is private;

       
     ShallowCopy(me) returns mutable like me 
        is redefined;
        ---Level: Advanced
	---C++: function call


     ShallowDump (me; s: in out OStream) 
        is redefined;
        ---Level: Advanced
    	---C++: function call


fields

    TheRoot       : AVLNode;
    TheComparator : Comparator;

end;