1 // Created on: 1991-05-23
2 // Created by: Jean-Pierre TIRAULT
3 // Copyright (c) 1991-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 // Transient implementation
19 #define TCollection_AVLSearchTreeTrace 0
20 // K_TRACE_A_METHOD used also in Engine.cxx, Engine_Signature.cxx,
21 // Engine_Argument.cxx, Engine_MyClassCompareOfSignature.cxx and
22 // TCollection_AVLSearchTree.gxx (! pour Kernel)
23 #define K_TRACE_A_METHOD 0
25 extern K_Trace_a_Method ;
28 #include <Standard_NoSuchObject.hxx>
29 #include <Standard_Address.hxx>
30 #include <TCollection_Side.hxx>
31 #if TCollection_AVLSearchTreeTrace
32 #include <Engine_Signature.hxx>
36 //-----------------------------------------------------------------------------
37 // Create : creates an empty AVLSearchTCollection_AVLSearchTree
38 //-----------------------------------------------------------------------------
39 TCollection_AVLSearchTree::
40 TCollection_AVLSearchTree(const Comparator& AComparator) : TheRoot(NULL)
42 TheComparator = AComparator;
46 //----------------------------------------------------------------------------
47 Standard_Integer TCollection_AVLSearchTree::Extent () const
49 return TCollection_AVLNode::RecursiveExtent((TCollection_AVLNode*) TheRoot);
53 //----------------------------------------------------------------------------
54 Standard_Integer TCollection_AVLSearchTree::TotalExtent () const
56 return TCollection_AVLNode::RecursiveTotalExtent((TCollection_AVLNode*)TheRoot);
59 //----------------------------------------------------------------------------
60 // Find the Node where an item is located
61 //----------------------------------------------------------------------------
62 Standard_Boolean TCollection_AVLSearchTree::Find(const Item& TheItem) const
64 TCollection_AVLNode* aNode = (TCollection_AVLNode*) TheRoot;
65 #if TCollection_AVLSearchTreeTrace
66 cout << " ++++++++++++++++++ SEARCH1 +++++++++++++++++++++++++++++" << endl ;
67 cout << "BEGINNING OF SEARCH OF " << TheItem->PForMapOfMethods()->Name()
68 << " in " << hex << TheRoot << dec << endl ;
71 if ( TheComparator.IsLower(TheItem, aNode->Value()) ) {
72 aNode = (TCollection_AVLNode*)aNode->Left();
74 if ( K_Trace_a_Method )
75 cout << "TCollection_AVLSearchTree::Find IsLower : Left : " << hex
76 << aNode << dec << endl ;
79 else if ( TheComparator.IsGreater(TheItem, aNode->Value()) ) {
80 aNode = (TCollection_AVLNode*)aNode->Right();
82 if ( K_Trace_a_Method )
83 cout << "TCollection_AVLSearchTree::Find IsGreater : Right : " << hex
84 << aNode << dec << endl ;
89 if ( K_Trace_a_Method )
90 cout << "TCollection_AVLSearchTree::Find IsEqual : " << hex << aNode
97 #if TCollection_AVLSearchTreeTrace
98 cout << "FOUND " << aNode->Value()->PForMapOfMethods()->Name() << endl ;
100 return Standard_True;
102 #if TCollection_AVLSearchTreeTrace
103 cout << " NOT FOUND" << endl ;
105 return Standard_False;
109 //----------------------------------------------------------------------------
110 // Find the Node where an item is located and returns the node associated
111 //----------------------------------------------------------------------------
112 Standard_Boolean TCollection_AVLSearchTree::Find(const Item& TheItem,
113 Standard_Address& TheNode) const
115 TCollection_AVLNode* aNode = (TCollection_AVLNode*) TheRoot;
116 #if TCollection_AVLSearchTreeTrace
117 cout << " ++++++++++++++++++ SEARCH2 +++++++++++++++++++++++++++++" << endl ;
118 cout << "BEGINNING OF SEARCH OF " << TheItem->PForMapOfMethods()->Name()
119 << " in " << hex << TheRoot << dec << endl ;
122 if ( TheComparator.IsLower(TheItem, aNode->Value()) ) {
123 aNode = (TCollection_AVLNode*)aNode->Left();
125 if ( K_Trace_a_Method )
126 cout << "TCollection_AVLSearchTree::Find IsLower : Left : " << hex
127 << aNode << dec << endl ;
130 else if ( TheComparator.IsGreater(TheItem, aNode->Value()) ) {
131 aNode = (TCollection_AVLNode*)aNode->Right();
133 if ( K_Trace_a_Method )
134 cout << "TCollection_AVLSearchTree::Find IsGreater : Right : " << hex
135 << aNode << dec << endl ;
140 if ( K_Trace_a_Method )
141 cout << "TCollection_AVLSearchTree::Find IsEqual : " << hex << aNode
148 TheNode = (Standard_Address) aNode;
149 #if TCollection_AVLSearchTreeTrace
150 cout << "FOUND " << aNode->Value()->PForMapOfMethods()->Name() << endl ;
152 return Standard_True;
154 #if TCollection_AVLSearchTreeTrace
155 cout << " NOT FOUND" << endl ;
157 return Standard_False;
161 //----------------------------------------------------------------------------
162 // Find the Node where an item is located
163 //----------------------------------------------------------------------------
164 Standard_Boolean TCollection_AVLSearchTree::Find(const Item& TheItem,
167 TCollection_AVLNode* aNode = (TCollection_AVLNode*) TheRoot;
168 #if TCollection_AVLSearchTreeTrace
169 cout << " ++++++++++++++++++ SEARCH3 +++++++++++++++++++++++++++++" << endl ;
170 cout << "BEGINNING OF SEARCH OF " << TheItem->PForMapOfMethods()->Name()
171 << " in " << hex << TheRoot << dec << endl ;
174 if ( TheComparator.IsLower(TheItem, aNode->Value()) ) {
175 aNode = (TCollection_AVLNode*)aNode->Left();
177 if ( K_Trace_a_Method )
178 cout << "TCollection_AVLSearchTree::Find IsLower : Left : " << hex
179 << aNode << dec << endl ;
182 else if ( TheComparator.IsGreater(TheItem, aNode->Value()) ) {
183 aNode = (TCollection_AVLNode*)aNode->Right();
185 if ( K_Trace_a_Method )
186 cout << "TCollection_AVLSearchTree::Find IsGreater : Right : " << hex
187 << aNode << dec << endl ;
192 if ( K_Trace_a_Method )
193 cout << "TCollection_AVLSearchTree::Find IsEqual : " << hex << aNode
200 TheOrig = aNode->Value();
201 #if TCollection_AVLSearchTreeTrace
202 cout << "FOUND " << aNode->Value()->PForMapOfMethods()->Name() << endl ;
204 return Standard_True;
206 #if TCollection_AVLSearchTreeTrace
207 cout << " NOT FOUND" << endl ;
209 return Standard_False;
213 //----------------------------------------------------------------------------
215 //-----------------------------------------------------------------------------
216 void TCollection_AVLSearchTree::RotateRight(Standard_Address& TheNode) const
218 // the left child becomes the parent...
219 TCollection_AVLNode* Temp = (TCollection_AVLNode*)((TCollection_AVLNode *)TheNode)->Left();
220 ((TCollection_AVLNode *)TheNode)->Left() = Temp->Right();
221 Temp->Right() = (TCollection_AVLNode *)TheNode;
222 TheNode = (Standard_Address)Temp;
225 //-----------------------------------------------------------------------------
227 //-----------------------------------------------------------------------------
228 void TCollection_AVLSearchTree::
229 RotateLeft(Standard_Address& TheNode) const
231 // the right child becomes the parent...
232 TCollection_AVLNode* Temp = (TCollection_AVLNode*)((TCollection_AVLNode *)TheNode)->Right();
233 ((TCollection_AVLNode *)TheNode)->Right() = Temp->Left();
234 Temp->Left() = (TCollection_AVLNode *)TheNode;
235 TheNode = (Standard_Address)Temp;
238 //-----------------------------------------------------------------------------
240 //-----------------------------------------------------------------------------
241 void TCollection_AVLSearchTree::LeftBalance(Standard_Address& Root) const
243 TCollection_AVLNode* TheNode = (TCollection_AVLNode*)((TCollection_AVLNode*)Root)->Left();
244 if( TCollection_AVLNode::Height(TheNode->Left()) >= TCollection_AVLNode::Height(TheNode->Right()) ) {
248 Standard_Address Ptr = TheNode;
250 TheNode = (TCollection_AVLNode*)Ptr;
251 ((TCollection_AVLNode*)Root)->Left() = TheNode;
255 //----------------------------------------------------------------------------
257 //-----------------------------------------------------------------------------
258 void TCollection_AVLSearchTree::RightBalance(Standard_Address& Root) const
260 TCollection_AVLNode* TheNode = (TCollection_AVLNode*)((TCollection_AVLNode *)Root)->Right();
261 if( TCollection_AVLNode::Height(TheNode->Right()) >= TCollection_AVLNode::Height(TheNode->Left())) {
265 Standard_Address Ptr = TheNode;
267 TheNode = (TCollection_AVLNode*)Ptr;
268 ((TCollection_AVLNode*)Root)->Right() = TheNode;
272 //-----------------------------------------------------------------------------
274 //-----------------------------------------------------------------------------
275 Standard_Boolean TCollection_AVLSearchTree::InsertBalance(Standard_Address& Child,
276 const Standard_Address Father,
277 const TCollection_Side theSide) const
279 // Balance after insertion
280 switch (TCollection_AVLNode::Height(((TCollection_AVLNode*)Child)->Left()) -
281 TCollection_AVLNode::Height(((TCollection_AVLNode*)Child)->Right())) {
282 case 2 : LeftBalance(Child);
284 ((TCollection_AVLNode*)Father)->SetChild((TCollection_AVLNode*)Child, theSide);
285 return Standard_False;
286 case -2 : RightBalance(Child);
288 ((TCollection_AVLNode*)Father)->SetChild((TCollection_AVLNode*)Child, theSide);
289 return Standard_False;
290 case 0 : return Standard_False;
291 default : return Standard_True;
295 //----------------------------------------------------------------------------
297 //-----------------------------------------------------------------------------
298 Standard_Boolean TCollection_AVLSearchTree::
299 RemoveBalance(Standard_Address& Child,
300 const Standard_Address Father,
301 const TCollection_Side theSide) const
303 // Balance after Remove
304 switch (TCollection_AVLNode::Height(((TCollection_AVLNode*)Child)->Left()) -
305 TCollection_AVLNode::Height(((TCollection_AVLNode*)Child)->Right())) {
306 case 2 : LeftBalance(Child);
308 ((TCollection_AVLNode*)Father)->SetChild((TCollection_AVLNode*)Child, theSide);
309 return Standard_True;
310 case -2 : RightBalance(Child);
312 ((TCollection_AVLNode*)Father)->SetChild((TCollection_AVLNode*)Child, theSide);
313 return Standard_True;
314 default : return Standard_True;
318 //---------------------------------------------------------------------------
320 //-----------------------------------------------------------------------------
321 Standard_Boolean TCollection_AVLSearchTree::
323 Standard_Address& Child,
324 const Standard_Address Father,
325 const TCollection_Side theSide,
327 Standard_Boolean& forOnce) const
330 TCollection_AVLNode* Temp;
332 Standard_Address MyTemp;
333 // end of DEC C++ need
334 Standard_Boolean Result = Standard_False;
335 Standard_Integer Number;
337 //-- Firstly find where the item should be insert
339 if(TheComparator.IsLower(theItem, ((TCollection_AVLNode*)Child)->Value() ) )
341 //-- If the item is lower than the root go to left child
344 Temp = (TCollection_AVLNode*)((TCollection_AVLNode*)Child)->Left();
345 //-- If it's a leaf insert it
347 ((TCollection_AVLNode*)Child)->Left() = new TCollection_AVLNode(theItem,(TCollection_AVLNode*)0L,(TCollection_AVLNode*)0L);
348 return Standard_True;
350 //-- else recursive insert...
351 MyTemp = (Standard_Address)Temp;
352 Result = RecursiveInsert( MyTemp, Child, TCollection_Left,
354 //-- and rebuild the tree, if no problem.
355 if(Result) return InsertBalance(Child, Father, theSide) ;
356 else return Standard_False;
359 else if (TheComparator.IsGreater(theItem, ((TCollection_AVLNode*)Child)->Value()))
361 //-- If the item is greater than the root go to right child
364 Temp = (TCollection_AVLNode*)((TCollection_AVLNode*)Child)->Right();
365 //-- If it's a leaf insert it
367 ((TCollection_AVLNode*)Child)->Right() = new TCollection_AVLNode(theItem,(TCollection_AVLNode*)0L,(TCollection_AVLNode*)0L);
368 return Standard_True;
370 //-- else recursive insert...
372 MyTemp = (Standard_Address)Temp;
373 Result = RecursiveInsert( MyTemp, Child, TCollection_Right,
375 //-- and rebuild the tree, if no problem.
376 if(Result) return InsertBalance(Child, Father, theSide);
377 else return Standard_False;
383 //-- Item is already there; add 1 to its count
385 forOnce = Standard_False;
388 Number = ((TCollection_AVLNode*)Child)->Count();
389 ((TCollection_AVLNode*)Child)->Count() = ++Number;
391 return Standard_False;
395 //-----------------------------------------------------------------------------
397 //-----------------------------------------------------------------------------
398 Standard_Boolean TCollection_AVLSearchTree::RecursiveRemove(
399 Standard_Address& Child,
400 const Standard_Address Father,
401 const TCollection_Side theSide,
403 const Standard_Boolean ForAll) const
405 Standard_Boolean Result;
407 if ( ! Child ) Standard_NoSuchObject::Raise();// if Child points to something
409 TCollection_AVLNode* TheLeft = (TCollection_AVLNode*)((TCollection_AVLNode*)Child)->Left(); // left children
410 TCollection_AVLNode* TheRight = (TCollection_AVLNode*)((TCollection_AVLNode*)Child)->Right();// right children
412 Standard_Address MyTheLeft;
413 Standard_Address MyTheRight;
415 if (TheComparator.IsLower(TheItem,((TCollection_AVLNode*)Child)->Value()))
417 MyTheLeft = (Standard_Address)TheLeft;
418 Result = RecursiveRemove( MyTheLeft, // left child becomes root
419 Child , // child becomes father
420 TCollection_Left, // go to left
421 TheItem , // same Item
424 else if (TheComparator.IsGreater(TheItem,(((TCollection_AVLNode*)Child)->Value())))
426 MyTheRight = (Standard_Address)TheRight;
427 Result = RecursiveRemove( MyTheRight,// right child becomes root
428 Child,// child becomes father
429 TCollection_Right,// go to right
430 TheItem ,// same Item
435 //-- The Item has been found
436 ((TCollection_AVLNode*)Child)->Count()--;
437 //-- Is it necessary to remove it ?
438 if (!ForAll && ((TCollection_AVLNode*)Child)->Count() > 0) return Standard_True;
439 //-- In this case we must remove it and rebuild the subtree.
440 if ( TheLeft && TheRight )
442 //-- The subtree has 2 children
443 TCollection_AVLNode* T;
444 TCollection_AVLNode* Temp = TheRight; // From the right child go to
445 while ( Temp ) { // the left leaf
447 Temp = (TCollection_AVLNode*)Temp->Left();
449 //-- We have the left leaf. Push it at the same level than the
450 //-- node we have removed.
451 ((TCollection_AVLNode*)Child)->Value() = T->Value() ;
452 ((TCollection_AVLNode*)Child)->Count() = T->Count() ;
453 //-- Now we must remove in the right subtree this value; because
454 //-- now it appears twice.
455 MyTheRight = (Standard_Address)TheRight;
456 Result = RecursiveRemove( MyTheRight, Child, TCollection_Right,
457 ((TCollection_AVLNode*)Child)->Value(), ForAll);
461 //-- only one subtree exists (left OR right)
462 //-- First delete the node
463 delete ((TCollection_AVLNode*)Child);
464 //-- Secondly see what is the child not empty
465 if ( ! TheLeft ) { Child = (Standard_Address) TheRight; }
466 else { Child = (Standard_Address) TheLeft; }
467 //-- Thirdly update the father node
468 // "mip-avril-94 : if (Father is null) => Raise"
469 // ((TCollection_AVLNode*)Father)->SetChild((TCollection_AVLNode*)Child, theSide);
470 if ((TCollection_AVLNode*)Father != NULL)
471 ((TCollection_AVLNode*)Father)->SetChild((TCollection_AVLNode*)Child, theSide);
472 return Standard_True;
475 //-- Result = Standard_True means we must reorder the tree.
476 if (Result) return RemoveBalance(Child, Father, theSide);
477 return Standard_False; // Child has not been found for now
481 //----------------------------------------------------------------------------
483 //-----------------------------------------------------------------------------
484 void TCollection_AVLSearchTree::Insert (const Item& theItem)
487 TheRoot = new TCollection_AVLNode(theItem,(TCollection_AVLNode*)0L,(TCollection_AVLNode*)0L);
490 TCollection_AVLNode* Father = NULL;
491 Standard_Boolean forOnce = Standard_False;
492 RecursiveInsert( TheRoot, (Standard_Address)Father, TCollection_Left, theItem,
496 //-----------------------------------------------------------------------------
498 //-----------------------------------------------------------------------------
499 Standard_Boolean TCollection_AVLSearchTree::InsertOnce (const Item& theItem)
502 TheRoot = new TCollection_AVLNode(theItem,(TCollection_AVLNode*)0L,(TCollection_AVLNode*)0L);
503 return Standard_True;
505 TCollection_AVLNode* Father = NULL;
506 Standard_Boolean forOnce = Standard_True;
507 RecursiveInsert( TheRoot, (Standard_Address)Father, TCollection_Left, theItem,
509 //-- forOnce = Standard_False if the item was already in the tree
513 //-----------------------------------------------------------------------------
515 //-----------------------------------------------------------------------------
516 void TCollection_AVLSearchTree::Remove (const Item& theItem)
518 TCollection_AVLNode* Father = NULL;
519 //-- remove ONLY ONE item of the tree
520 RecursiveRemove( TheRoot, (Standard_Address)Father, TCollection_Left, theItem,Standard_False);
523 //----------------------------------------------------------------------------
525 //-----------------------------------------------------------------------------
526 void TCollection_AVLSearchTree::RemoveAll (const Item& theItem)
528 TCollection_AVLNode* Father = NULL;
529 //-- Remove ALL item of the tree
530 RecursiveRemove( TheRoot, (Standard_Address)Father, TCollection_Left, theItem,Standard_True);
533 //----------------------------------------------------------------------------
535 //-----------------------------------------------------------------------------
536 TCollection_AVLSearchTree TCollection_AVLSearchTree::Merge(const TCollection_AVLSearchTree& aTree) const
539 // First, make a shallowcopy and push the result into a new tree
541 TCollection_AVLSearchTree newTree = ShallowCopy();
542 // for test-- newTree.ShallowDump(cout);
544 TCollection_AVLIterator Iter( aTree );
545 //-- Secondly, make an iterator on the second tree
547 while( Iter.More()) {
548 //-- Thirdly get back its value
549 // theItem = ((TCollection_AVLNode*)Iter.Value())->Value();
551 theItem = Iter.Value();
553 //-- and push them into the new tree.
555 newTree.Insert(theItem);
562 //----------------------------------------------------------------------------
564 //-----------------------------------------------------------------------------
565 TCollection_AVLSearchTree TCollection_AVLSearchTree::ShallowCopy() const
567 // Construct a new tree
568 // with same comparator
570 TCollection_AVLSearchTree newtree (TheComparator);
572 // Copy an TCollection_AVLNode and put
573 // the result as root of new tree
575 newtree.SetRoot(TCollection_AVLNode::Copy((TCollection_AVLNode*)TheRoot)) ;