home *** CD-ROM | disk | FTP | other *** search
/ C Programming Starter Kit 2.0 / SamsPublishing-CProgrammingStarterKit-v2.0-Win31.iso / bc45 / classsrc.pak / BINIMP.CPP next >
C/C++ Source or Header  |  1997-07-23  |  9KB  |  319 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  BINIMP.CPP                                                            */
  4. /*                                                                        */
  5. /*  Copyright (c) 1993, 1994 Borland International                        */
  6. /*  All Rights Reserved                                                   */
  7. /*                                                                        */
  8. /*------------------------------------------------------------------------*/
  9.  
  10. #if !defined( CLASSLIB_BINIMP_H )
  11. #include <classlib/binimp.h>
  12. #endif
  13.  
  14. TBinarySearchTreeBase::TBinarySearchTreeBase() :
  15.     Root(0),
  16.     ItemsInContainer(0)
  17. {
  18. }
  19.  
  20. int TBinarySearchTreeBase::InsertNode( BinNode *node )
  21. {
  22.     BinNode *Current = Root;
  23.     BinNode *Parent = 0;
  24.     while( Current )
  25.         {
  26.         Parent = Current;
  27.         Current = LessThan( node, Current ) ? Current->Left : Current->Right;
  28.         }
  29.     if( Parent == 0 )
  30.         Root = node;
  31.     else
  32.         {
  33.         if( LessThan( node, Parent ) )
  34.             Parent->Left = node;
  35.         else
  36.             Parent->Right = node;
  37.         }
  38.     ItemsInContainer++;
  39.     return 1;
  40. }
  41.  
  42. int TBinarySearchTreeBase::RemoveNode( BinNode *node, int del )
  43. {
  44.     BinNode *Current = Root;
  45.     BinNode *Parent = 0;
  46.     while( Current )
  47.         {
  48.         if( EqualTo( node, Current ) )
  49.             return RemNode( Current, Parent, del );
  50.         else
  51.             {
  52.             Parent = Current;
  53.             Current = LessThan( node, Current ) ? Current->Left :
  54.                                                   Current->Right;
  55.             }
  56.         }
  57.     return 0;
  58. }
  59.  
  60. TBinarySearchTreeBase::BinNode *TBinarySearchTreeBase::FindNode( BinNode *node )
  61. {
  62.     BinNode *Current = Root;
  63.     while( Current )
  64.         {
  65.         if( EqualTo( node, Current ) )
  66.             return Current;
  67.         else
  68.             Current = LessThan( node, Current ) ? Current->Left :
  69.                                                   Current->Right;
  70.         }
  71.     return 0;
  72. }
  73.  
  74. int TBinarySearchTreeBase::RemNode( BinNode *node, BinNode *parent, int del )
  75. {
  76.     // See R. Sedgewick, "Algorithms, 2nd edition",
  77.     //   Addison-Wesley 1988, p.210.
  78.     BinNode *Original = node;
  79.     if( Original->Right == 0 )
  80.         node = node->Left;
  81.     else if( Original->Right->Left )
  82.         {
  83.         BinNode *Current = Original->Right;
  84.         while( Current->Left->Left )
  85.             Current = Current->Left;
  86.         node = Current->Left;
  87.         Current->Left = node->Right;
  88.         node->Left = Original->Left;
  89.         node->Right = Original->Right;
  90.         }
  91.     else
  92.         {
  93.         node = node->Right;
  94.         node->Left = Original->Left;
  95.         }
  96.     if( parent == 0 )
  97.         Root = node;
  98.     else if( LessThan( Original, parent ) )
  99.         parent->Left = node;
  100.     else
  101.         parent->Right = node;
  102.  
  103.     DeleteNode( Original, del );
  104.     ItemsInContainer--;
  105.     return 1;
  106. }
  107.  
  108. class TBinaryTreeKiller : public TBinaryTreeInternalIteratorBase
  109. {
  110.  
  111. public:
  112.  
  113.     TBinaryTreeKiller( TBinarySearchTreeBase& tree, int del ) :
  114.         TBinaryTreeInternalIteratorBase( tree, TBinarySearchTreeBase::PostOrder ),
  115.         Del(del) {}
  116.  
  117. private:
  118.  
  119.     virtual void Apply( TBinarySearchTreeBase::BinNode _FAR *node,
  120.                         TBinarySearchTreeBase::BinNode _FAR *parent );
  121.  
  122.     int Del;
  123.  
  124.     TBinaryTreeKiller( const TBinaryTreeKiller& );
  125.     const TBinaryTreeKiller& operator = ( const TBinaryTreeKiller& );
  126.  
  127. };
  128.  
  129. void TBinaryTreeKiller::Apply( TBinarySearchTreeBase::BinNode _FAR *node,
  130.                            TBinarySearchTreeBase::BinNode _FAR *parent )
  131. {
  132.     Tree().RemNode( node, parent, Del );
  133. }
  134.  
  135. void TBinarySearchTreeBase::Flush( int del )
  136. {
  137.     if( Root != 0 )
  138.         TBinaryTreeKiller( *this, del ).Iterate();
  139. }
  140.  
  141. void TBinaryTreeInternalIteratorBase::Iterate()
  142. {
  143.     TBinarySearchTreeBase::BinNode _FAR *Current = Node;
  144.     TBinarySearchTreeBase::BinNode _FAR *Prev = 0;
  145.     TBinarySearchTreeBase::BinNode _FAR *Next = 0;
  146. step2:
  147.     if( Order == TBinarySearchTreeBase::PreOrder )
  148.         Apply( Current, 0 );
  149.     Next = Current->Left;
  150.     if( Next != 0 )
  151.         {
  152.         Current->Left = Prev;
  153.         Prev = Current;
  154.         Current = Next;
  155.         goto step2;
  156.         }
  157. step4:
  158.     if( Order == TBinarySearchTreeBase::InOrder )
  159.         Apply( Current, 0 );
  160.     Next = Current->Right;
  161.     if( Next != 0 )
  162.         {
  163.         Current->Right = Prev;
  164.         Prev = Current;
  165.         Current = Next;
  166.         goto step2;
  167.         }
  168. step6:
  169.     if( Prev == 0 )
  170.         {
  171.         if( Order == TBinarySearchTreeBase::PostOrder )
  172.             Apply( Current, 0 );
  173.         return;
  174.         }
  175.     if( Tree().LessThan( Current, Prev ) )
  176.         {
  177.         TBinarySearchTreeBase::BinNode _FAR *Temp = Current;
  178.         Next = Prev->Left;
  179.         Prev->Left = Current;
  180.         Current = Prev;
  181.         Prev = Next;
  182.         if( Order == TBinarySearchTreeBase::PostOrder )
  183.             Apply( Temp, Current );
  184.         goto step4;
  185.         }
  186.     else
  187.         {
  188.         TBinarySearchTreeBase::BinNode _FAR *Temp = Current;
  189.         Next = Prev->Right;
  190.         Prev->Right = Current;
  191.         Current = Prev;
  192.         Prev = Next;
  193.         if( Order == TBinarySearchTreeBase::PostOrder )
  194.             Apply( Temp, Current );
  195.         goto step6;
  196.         }
  197. }
  198.  
  199. TBinaryTreeExternalIteratorBase::TBinaryTreeExternalIteratorBase( TBinarySearchTreeBase& tree, TBinarySearchTreeBase::IteratorOrder order ) :
  200.     Stack( new TStackAsList<TBinarySearchTreeBase::BinNode _BIDSFAR *> ),
  201.     Tree(&tree),
  202.     Current( tree.Root ),
  203.     Order( order )
  204. {
  205.     Restart();
  206. }
  207.  
  208. TBinaryTreeExternalIteratorBase::~TBinaryTreeExternalIteratorBase()
  209. {
  210.     delete Stack;
  211. }
  212.  
  213. void TBinaryTreeExternalIteratorBase::Restart()
  214. {
  215.     Stack->Flush();
  216.     Current = Tree->Root;
  217.     LeftVisited = RightVisited = 0;
  218.     Processed = 0;
  219. }
  220.  
  221. TBinarySearchTreeBase::BinNode *TBinaryTreeExternalIteratorBase::Next()
  222. {
  223.     if( Current == 0 )
  224.         return 0;
  225.     for(;;)
  226.         {
  227.         if( Order == TBinarySearchTreeBase::PreOrder && !Processed )
  228.             {
  229.             Processed = 1;
  230.             return Current;
  231.             }
  232.  
  233.         if( Current->Left != 0 && !LeftVisited )
  234.             {
  235.             Stack->Push( Current );
  236.             Current = Current->Left;
  237.             LeftVisited = RightVisited = 0;
  238.             Processed = 0;
  239.             }
  240.         else if( Current->Right != 0 && !RightVisited )
  241.             {
  242.             TBinarySearchTreeBase::BinNode *Res = 0;
  243.             if( Order == TBinarySearchTreeBase::InOrder )
  244.                 Res = Current;
  245.             Stack->Push( Current );
  246.             Current = Current->Right;
  247.             LeftVisited = RightVisited = 0;
  248.             Processed = 0;
  249.             if( Res != 0 )
  250.                 return Res;
  251.             }
  252.         else
  253.             {
  254.             if( Stack->IsEmpty() )
  255.                 {
  256.                 if( Processed == 0 )
  257.                     {
  258.                     Processed = 1;
  259.                     }
  260.                 else
  261.                     {
  262.                     Current = 0;
  263.                     }
  264.                 return Current;
  265.                 }
  266.             else
  267.                 {
  268.                 TBinarySearchTreeBase::BinNode *Res;
  269.                 switch( Order )
  270.                     {
  271.                     case TBinarySearchTreeBase::PreOrder:
  272.                         // This node has already been
  273.                         // processed, so we have further to go.
  274.                         Res = 0;
  275.  
  276.                         // This node's parent has
  277.                         // already been processed
  278.                         Processed = 1;
  279.  
  280.                         break;
  281.  
  282.                     case TBinarySearchTreeBase::InOrder:
  283.                         if( IsInOrder() )
  284.                             {
  285.                             // This node needs to be processed.
  286.                             Res = Current;
  287.                             }
  288.                         else
  289.                             {
  290.                             // Node has already been processed.
  291.                             Res = 0;
  292.                             }
  293.                         // If we're the right-hand child, our parent
  294.                         // has already been processed.
  295.                         Processed = Stack->Top()->Right == Current;
  296.  
  297.                         break;
  298.  
  299.                     case TBinarySearchTreeBase::PostOrder:
  300.                         // This node needs to be processed.
  301.                         Res = Current;
  302.  
  303.                         // This node's parent has not been processed.
  304.                         Processed = 0;
  305.  
  306.                         break;
  307.                     }
  308.  
  309.                 LeftVisited = 1;
  310.                 RightVisited = Stack->Top()->Right == Current;
  311.                 Current = Stack->Pop();
  312.                 if( Res != 0 )
  313.                     return Res;
  314.                 }
  315.             }
  316.         }
  317. }
  318.  
  319.