+++ /dev/null
--- Created on: 1991-05-21
--- Created by: Annick PANCHER
--- Copyright (c) 1991-1999 Matra Datavision
--- Copyright (c) 1999-2014 OPEN CASCADE SAS
---
--- This file is part of Open CASCADE Technology software library.
---
--- This library is free software; you can redistribute it and/or modify it under
--- the terms of the GNU Lesser General Public License version 2.1 as published
--- by the Free Software Foundation, with special exception defined in the file
--- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
--- distribution for complete text of the license and disclaimer of any warranty.
---
--- Alternatively, this file may be used under the terms of Open CASCADE
--- commercial license or contractual agreement.
-
--- Revised: Mireille MERCIEN
-
-
-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;
-
-
-
-
projects / occt.git / blobdiff