src/PCollection/PCollection_HArbitraryTree.cdl

   1 -- Created on: 1991-06-20
   2 -- Created by: Annick PANCHER
   3 -- Copyright (c) 1991-1999 Matra Datavision
   4 -- Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 --
   6 -- This file is part of Open CASCADE Technology software library.
   7 --
   8 -- This library is free software; you can redistribute it and/or modify it under
   9 -- the terms of the GNU Lesser General Public License version 2.1 as published
  10 -- by the Free Software Foundation, with special exception defined in the file
  11 -- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 -- distribution for complete text of the license and disclaimer of any warranty.
  13 --
  14 -- Alternatively, this file may be used under the terms of Open CASCADE
  15 -- commercial license or contractual agreement.
  16
  17 -- Revised:      Mireille MERCIEN
  18
  19
  20 generic class HArbitraryTree from PCollection (
  21                Item as Storable)
  22
  23
  24     ---Purpose: Description of  a  tree  with an arbitrary  number  of
  25     -- children  at   each  level.   Each    'node'   is   an
  26     -- ArbitraryTree which knows its parent and its children.
  27     -- An ArbitraryTree  can't  contain an empty  child.   To
  28     -- separate  a  part  B from  an   ArbitraryTree A,  it's
  29     -- possible to swap B with a Null tree: the parent A will
  30     -- remove its child B, which is returned.
  31     --
  32     -- There are three iterators known  for an ArbitraryTree(
  33     -- PreOrder,  PostOrder and InOrder).   Each  of  them
  34     -- manages a stack whose depth is always less or equal to
  35     -- the tree's  height, and which  describes the  way from
  36     -- the root to the current tree.
  37   --  Warning: It could be a bad choice to use an ArbitraryTree for
  38     -- a great number of items if it's frequently necessary
  39     -- to search them, for there is no optimisation to find
  40     -- an item in an unordered tree.
  41     -- The same item can be stored several times in several places.
  42
  43 inherits Persistent
  44 raises IsNotRoot    ,
  45        IsNullTree   ,
  46        IsContained  ,
  47        NoMoreObject from Standard,
  48        NoSuchObject from Standard,
  49        OutOfRange   from Standard
  50
  51
  52     class SeqArbitraryTree instantiates
  53                 HSequence from PCollection(HArbitraryTree);
  54     class StackArbitraryTree instantiates
  55                 HStack from PCollection(HArbitraryTree);
  56
  57     class ATPreOrderIterator
  58
  59         ---Purpose: Permits to  iterate through  an ArbitraryTree so that,
  60         -- from the   root, it reads each   element  on the left,
  61         -- until  the first leave, then  goes to its rightSibling
  62         -- and upward.
  63         -- IF theTree is ( A (B (C D E)) F G (H (I J K)))
  64         -- THEN it will read ( A B C D E F G H I J K)
  65
  66     raises NoMoreObject from Standard ,
  67            NoSuchObject from Standard
  68     is
  69
  70         Create( theTree : HArbitraryTree)
  71              ---Purpose: Creates an iterator on <theTree>.
  72              returns ATPreOrderIterator;
  73
  74         More( me)
  75             ---Purpose: Returns True if there is at least one element to be read.
  76             ---Level: Public
  77             returns Boolean from Standard;
  78
  79         Next( me : in out) raises NoMoreObject from Standard;
  80              ---Purpose: Manages currentStack  which  always  contains
  81              -- the way from the root to the  next leaf to be
  82              -- visited.  Updates currentTree.
  83              ---Level: Public
  84
  85         Value( me )
  86             ---Purpose: Returns the current element.
  87             ---Level: Public
  88             returns mutable HArbitraryTree
  89             raises NoSuchObject from Standard;
  90
  91         Clear( me : in out);
  92             ---Purpose: Empties <me>, so that More() will answer False.
  93             ---Level: Public
  94
  95
  96
  97         RecursiveRemove( me : in out; aTree : HArbitraryTree)
  98             ---Purpose: Removes the end of currentStack until finding a
  99             -- tree having a right sibling: removes it too, and returns it.
 100             returns mutable HArbitraryTree
 101             ---Level: Internal
 102             is private;
 103
 104     fields
 105         HasMore     : Boolean from Standard;
 106         CurrentTree : HArbitraryTree;
 107         CurrentStack: StackArbitraryTree;
 108     end;
 109
 110
 111     class ATPostOrderIterator
 112
 113         ---Purpose: Permits to iterate through an ArbitraryTree beginning by
 114         -- the most left leave and its rightSibling, then upward to its parent.
 115         -- IF theTree is (  A (B (C D E)) F G (H (I J K)))
 116         -- THEN it will read ( C D E B F I J K H G A)
 117
 118     raises NoMoreObject from Standard,
 119            NoSuchObject from Standard
 120
 121     is
 122
 123         Create( theTree : HArbitraryTree)
 124             ---Purpose: Creates an iterator on the tree theTree
 125             returns ATPostOrderIterator;
 126
 127         More( me) returns Boolean from Standard;
 128             ---Purpose: Returns True if there is at least one element to
 129             -- be read.
 130             ---Level: Public
 131
 132         Next( me : in out) raises NoMoreObject from Standard;
 133             ---Purpose: Sets the iterator on the next element
 134             ---Level: Public
 135
 136         Value( me)
 137             ---Level: Public
 138             returns mutable HArbitraryTree
 139             raises NoSuchObject from Standard;
 140
 141         Clear( me : in out);
 142             ---Purpose: Empties <me>, so that More() will answer False
 143             ---Level: Public
 144
 145         RecursiveAppend( me : in out; aTree : HArbitraryTree)
 146             ---Purpose: adds a new branch to currentStack, until
 147             -- reaching a leaf; the branch's parent is <aTree>
 148             ---Level: Internal
 149             is private;
 150
 151     fields
 152         HasMore     : Boolean from Standard;
 153         CurrentTree : HArbitraryTree;
 154         CurrentStack: StackArbitraryTree;
 155
 156     end;
 157
 158
 159     class ATInOrderIterator
 160
 161         ---Purpose: Permits to iterate through an ArbitraryTree so that, from
 162         -- the most left leave, it reads it, then its parent, then in
 163         -- the same order what is on its right.
 164         -- IF theTree is (  A (B (C D E)) F G (H (I J K)))
 165         -- THEN it will read ( C B D E A F I H J K G)
 166
 167     raises NoMoreObject from Standard,
 168            NoSuchObject from Standard
 169     is
 170
 171         Create( theTree : HArbitraryTree)
 172             ---Purpose: Create an iterator on the tree theTree
 173             returns ATInOrderIterator;
 174
 175         More( me) returns Boolean from Standard;
 176             ---Purpose: Returns True if there is at least one element to be read.
 177             ---Level: Public
 178
 179         Next( me : in out) raises NoMoreObject from Standard;
 180             ---Purpose: Sets the iterator to the next element.
 181             ---Level: Public
 182
 183         Value( me)
 184             returns mutable HArbitraryTree
 185             raises NoSuchObject from Standard;
 186             ---Level: Public
 187
 188         Clear( me : in out);
 189             ---Purpose: Empties <me>, so that More() will answer False.
 190             ---Level: Public
 191
 192         RecursiveAppend( me : in out; aTree : HArbitraryTree)
 193             ---Purpose: Adds to currentStack a new branch of the tree,
 194             -- which has not been visited; this branch's parent is <aTree>.
 195             ---Level: Internal
 196             is private;
 197
 198         RecursiveRemove( me : in out; aTree : HArbitraryTree)
 199             ---Purpose: Removes from currentStack one or more trees,
 200             -- which have already been visited and have no
 201             -- more children not visited; the first tree
 202             -- removed is <aTree>.
 203             ---Level: Internal
 204             returns mutable HArbitraryTree
 205             is private;
 206
 207     fields
 208         HasMore     : Boolean from Standard;
 209         CurrentTree : HArbitraryTree;
 210         CurrentStack: StackArbitraryTree;
 211     end;
 212
 213
 214 is
 215
 216
 217     Create ( TheItem : Item)
 218         ---Purpose: Creation of a root tree of value Item with no child(e.g. a leaf)
 219         --  Example:
 220         -- if <TheItem> = i0
 221         -- returns
 222         --  ( i0 )
 223         -- The field <MyParent> is Null and so is <MyChildren>.
 224         returns mutable HArbitraryTree;
 225
 226     Children( me)
 227         ---Purpose: Reads all children of <me>, to be able to know the
 228         -- location of one of them.
 229         ---Level: Internal
 230         returns mutable SeqArbitraryTree
 231         is private;
 232
 233     Child( me; Index : Integer from Standard)
 234         ---Purpose: Returns the child of <me> at the range <Index>.
 235         -- Raises an exception if <Index> is out of range.
 236         --  Example:Before
 237         --   me = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) ), Index = 2
 238         -- After
 239         --   me = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) )
 240         -- returns   (i2)
 241         ---Level: Public
 242         returns mutable HArbitraryTree
 243         raises OutOfRange from Standard;
 244
 245     Value( me) returns any Item;
 246         ---Purpose: Returns the value of <me>.
 247         --  Example:Before and After
 248         --   me = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) )
 249         -- returns  i0
 250         ---Level: Public
 251
 252     NbChildren( me) returns Integer from Standard;
 253         ---Purpose: Returns the number of children of me.
 254         --  Example: me = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) )
 255         -- returns 3
 256         ---Level: Public
 257
 258     IsLeaf( me) returns Boolean from Standard;
 259         ---Purpose: Returns True if the tree <me> is a leaf.
 260         --  Example: me = ( i0 )
 261         -- returns True
 262         ---Level: Public
 263
 264     Parent( me)
 265         ---Purpose: Returns the father of <me>.
 266         -- The returned ArbitraryTree can be Null.
 267         --  Example: if T = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) ) and
 268         --   me = ( i1 (i4 i5) )
 269         -- returns T.
 270         ---Level: Public
 271         returns mutable HArbitraryTree;
 272
 273     IsRoot( me)
 274         ---Purpose: Returns True if <me> has no father.
 275         ---Level: Public
 276         returns Boolean from Standard;
 277
 278     Root( me)
 279         ---Purpose: Returns the root of the tree <me>.
 280         -- If <me> is a root, returns <me>
 281         --  Example: if T = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) ) and
 282         --   me = (i1( i4 i5 )) and T->IsRoot == True
 283         -- returns  T
 284         ---Level: Public
 285         returns mutable HArbitraryTree ;
 286
 287     LeftSibling( me)
 288         ---Purpose: Returns the left neighbour of the tree <me>.
 289         -- May return a Null tree.
 290         -- if T = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) )
 291         --   and me = (i2)
 292         -- returns  ( i1 (i4 i5) )
 293         ---Level: Public
 294         returns mutable HArbitraryTree;
 295
 296     RightSibling( me)
 297         ---Purpose: Returns the right neighbour of the tree <me>.
 298         -- May return a Null tree.
 299         --  Example: if T = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) )
 300         --   and  me = (i2)
 301         -- returns  ( i3 (i6 i7) )
 302         ---Level: Public
 303         returns mutable HArbitraryTree;
 304
 305     Contains( me; aTree: HArbitraryTree)
 306         ---Purpose: Checks <aTree> is contained by <me>.
 307         ---Level: Public
 308         returns Boolean from Standard
 309         raises IsNullTree ;
 310
 311     SetValue( me : mutable ; theItem : Item) ;
 312         ---Purpose: Changes the value of MyItem.
 313         --  Example: before
 314         --   me = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) ), theItem= i10
 315         -- after
 316         --   me = ( i10 (i1 (i4 i5) i2 i3 (i6 i7) ) )
 317         ---Level: Public
 318
 319     SwapChild( me : mutable ; Index : Integer from Standard;
 320                WithTree : in out mutable HArbitraryTree)
 321         ---Purpose: Replaces the child of <me> at range <Index> by <WithTree>
 322         -- and conversely.
 323         -- Only removes Child at range <Index> if <WithTree> is Null.
 324         --  Trigger: Raises an exception if <Index> is greater than NbChildren;
 325         -- raises IsNotRoot if <WithTree> is not a root;
 326         --  Example: Before
 327         --   me = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) ),
 328         --   Index = 2,  WithTree = ( i8 (i9  i10) )
 329         -- After
 330         --   me = ( i0 (i1 (i4 i5) i8 (i9 i10) i3 (i6 i7) ) )
 331         --   WithTree = (i2)
 332         ---Level: Public
 333         raises OutOfRange from Standard,
 334                IsNotRoot;
 335
 336     SwapChildren( me : mutable ; subtree1, subtree2 : mutable HArbitraryTree)
 337         ---Purpose: TradeOff between two subtrees of <me>.
 338         --  Example: Before
 339         --   me = ( i0 (i1 (i4 i5) i2 i3 (i6 i7) ) ),
 340         --   subtree1 = (i4), subtree2 = (i3 (i6 i7)),
 341         -- After
 342         --   me = ( i0 (i1 ( i3 (i6 i7) i5)  i2 i4))
 343         --  Trigger:Raises an  exception if <subtree1>  or  <subtree2>
 344         -- are not subtrees of <me>.
 345         -- Raises an exception if one of the  two subtrees is
 346         -- contained by the other one.For instance :
 347         --  Example: IF subtree1 = (i3( i6 i7)) and subtree2 = (i6).
 348         -- Raises an exception if one of the two subtrees is null.
 349         ---Level: Public
 350         raises OutOfRange from Standard,
 351                NoSuchObject from Standard,
 352                IsContained,
 353                IsNullTree;
 354
 355     AppendChild( me: mutable; theTree: HArbitraryTree)
 356         ---Purpose: Appends <theTree> as last child of <me>
 357         --  Example:
 358         -- Before
 359         --   me = ( i0 ( i1 i2 i3))
 360         --   theTree = ( i4)
 361         -- After
 362         --   me = ( i0 ( i1 i2 i3 i4))
 363         --  Trigger: Raises IsNotRoot if <theTree> is not a root.
 364         -- Raises IsNullTree if <theTree> is Null.
 365         ---Level: Public
 366         raises IsNotRoot,
 367                IsNullTree;
 368
 369     PrependChild( me: mutable; theTree: HArbitraryTree)
 370         ---Purpose: Appends <theTree> as first child of <me>.
 371         --  Example:
 372         -- Before
 373         --   me = ( i0 ( i1 i2 i3))
 374         --   theTree = ( i4)
 375         -- After
 376         --   me = ( i0 ( i4 i1 i2 i3))
 377         --  Trigger: Raises IsNotRoot if <theTree> is not a root.
 378         -- Raises IsNullTree if <theTree> is Null.
 379         ---Level: Public
 380         raises IsNotRoot,
 381                IsNullTree;
 382
 383     InsertChildBefore( me : mutable; Index : Integer from Standard;
 384                        theTree: HArbitraryTree)
 385         ---Purpose: Adds   <theTree> to  the   field  <MyChildren>, at
 386         -- <Index>, and all  children  from <Index> pushed on
 387         -- the right.
 388         --  Example: Before
 389         --   me = ( i0 ( i1 i2 i3))
 390         --   theTree = ( i4), Index = 2
 391         -- After
 392         --   me = ( i0 ( i1 i4 i2 i3))
 393         -- Trigger: Raises  OutOfRange if   <Index>  is  greater  than
 394         -- NbChildren.
 395         -- Raises IsNotRoot if <theTree> is not a root.
 396         -- Raises IsNullTree if <theTree> is Null.
 397         ---Level: Public
 398         raises OutOfRange from Standard,
 399                IsNotRoot,
 400                IsNullTree;
 401
 402     InsertChildAfter( me: mutable; Index: Integer from Standard;
 403                       theTree: HArbitraryTree)
 404         ---Purpose: Adds <theTree> to  <MyChildren>, at <Index>+1, and
 405         -- all children from <Index>+1 pushed on the right.
 406         --  Example: Before
 407         --   me = ( i0 ( i1 i2 i3))
 408         --   theTree = ( i4), Index = 2
 409         -- After
 410         --   me = ( i0 ( i1 i2 i4 i3))
 411         --  Trigger: Raises OutOfRange if <Index> is greater than NbChildren
 412         -- Raises IsNotRoot if <theTree> is not a root
 413         -- Raises IsNullTree if <theTree> is Null
 414         ---Level: Public
 415         raises OutOfRange from Standard,
 416                IsNotRoot,
 417                IsNullTree;
 418
 419     RemoveChild( me : mutable; Index: Integer from Standard)
 420         ---Purpose: Removes from <MyChildren> the ArbitraryTree at range <Index>.
 421         --  Example: Before
 422         --   me = ( i0 ( i1 i2 i3 i4)) and Index = 2
 423         -- After
 424         --   me = ( i0 ( i1 i3 i4))
 425         --  Trigger: Raises OutOfRange if <Index> is greater than NbChildren
 426         ---Level: Public
 427         raises OutOfRange from Standard;
 428
 429     RemoveAllChildren( me: mutable);
 430         ---Purpose: Removes all my children.
 431         ---Level: Public
 432
 433     RemoveChildren( me: mutable; FromIndex, ToIndex : Integer from Standard)
 434         ---Purpose: Removes from <MyChildren> all the ArbitraryTree
 435         -- located from range <FromIndex> to <ToIndex>.
 436         --  Example: Before
 437         --   me = ( i0 ( i1 i2 i3 i4))
 438         --   FromIndex = 2 and ToIndex = 4
 439         -- After
 440         --   me = ( i0 ( i1))
 441         --  Trigger: Raises OutOfRange if <FromIndex> or <ToIndex> is
 442         -- greater than NbChildren.
 443         ---Level: Public
 444         raises OutOfRange from Standard;
 445
 446     SetParent( me : mutable; theTree : HArbitraryTree)
 447         ---Purpose: Changes the value of MyParent.
 448         ---Level: Internal
 449         is private;
 450
 451
 452     ShallowCopy(me) returns mutable like me
 453         is redefined;
 454         ---Level: Advanced
 455         ---C++: function call
 456
 457     ShallowDump (me; s: in out OStream)
 458         is redefined;
 459         ---Level: Advanced
 460         ---C++: function call
 461
 462 fields
 463
 464     MyParent  : HArbitraryTree;
 465     MyItem    : Item;
 466     MyChildren: SeqArbitraryTree;
 467 end;