home *** CD-ROM | disk | FTP | other *** search
/ C Programming Starter Kit 2.0 / SamsPublishing-CProgrammingStarterKit-v2.0-Win31.iso / bc45 / classinc.pak / BINIMP.H < prev    next >
C/C++ Source or Header  |  1997-07-23  |  17KB  |  569 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  BINIMP.H                                                              */
  4. /*                                                                        */
  5. /*  Copyright (c) 1993, 1994 Borland International                        */
  6. /*  All Rights Reserved                                                   */
  7. /*                                                                        */
  8. /*------------------------------------------------------------------------*/
  9.  
  10. #if !defined( CLASSLIB_BINIMP_H )
  11. #define CLASSLIB_BINIMP_H
  12.  
  13. #if !defined( CLASSLIB_DEFS_H )
  14. #include <classlib/defs.h>
  15. #endif
  16.  
  17. #if !defined( CLASSLIB_VOIDP_H )
  18. #include <classlib/voidp.h>
  19. #endif
  20.  
  21. #if !defined( CLASSLIB_STACKS_H )
  22. #include <classlib/stacks.h>
  23. #endif
  24.  
  25. #pragma option -Vo-
  26. #if defined( BI_CLASSLIB_NO_po )
  27. #pragma option -po-
  28. #endif
  29.  
  30. /*------------------------------------------------------------------------*/
  31. /*                                                                        */
  32. /*  class TBinarySearchTreeBase                                           */
  33. /*                                                                        */
  34. /*  Base class for binary search tree templates.                          */
  35. /*                                                                        */
  36. /*------------------------------------------------------------------------*/
  37.  
  38. class _BIDSCLASS TBinarySearchTreeBase
  39. {
  40.  
  41.     friend class _BIDSCLASS TBinaryTreeInternalIteratorBase;
  42.     friend class _BIDSCLASS TBinaryTreeExternalIteratorBase;
  43.     friend class _BIDSCLASS TBinaryTreeKiller;
  44.  
  45. public:
  46.  
  47.     enum IteratorOrder
  48.         {
  49.         PreOrder,
  50.         InOrder,
  51.         PostOrder
  52.         };
  53.  
  54.     class _BIDSCLASS BinNode
  55.         {
  56.         public:
  57.             BinNode() : Left(0), Right(0) {}
  58.             BinNode _BIDSFAR *Left;
  59.             BinNode _BIDSFAR *Right;
  60.         };
  61.  
  62.     void Flush( int del = 0 );
  63.  
  64.     unsigned GetItemsInContainer() const
  65.         {
  66.         return ItemsInContainer;
  67.         }
  68.  
  69.     int IsEmpty() const
  70.         {
  71.         return Root == 0;
  72.         }
  73.  
  74. protected:
  75.  
  76.     TBinarySearchTreeBase();
  77.  
  78.     int InsertNode( BinNode _BIDSFAR *node );
  79.     int RemoveNode( BinNode _BIDSFAR *node, int del );
  80.     BinNode _BIDSFAR *FindNode( BinNode _BIDSFAR *node );
  81.  
  82.     int RemNode( BinNode _BIDSFAR *node, BinNode _BIDSFAR *parent, int del );
  83.  
  84.     virtual int EqualTo( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 ) = 0;
  85.     virtual int LessThan( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 ) = 0;
  86.     virtual void DeleteNode( BinNode _BIDSFAR *node, int del ) = 0;
  87.  
  88.     BinNode _BIDSFAR *Root;
  89.  
  90. private:
  91.  
  92.     unsigned ItemsInContainer;
  93.  
  94.     TBinarySearchTreeBase( const TBinarySearchTreeBase _BIDSFAR & );
  95.     const TBinarySearchTreeBase _BIDSFAR &
  96.         operator = ( const TBinarySearchTreeBase _BIDSFAR & );
  97.  
  98. };
  99.  
  100. /*------------------------------------------------------------------------*/
  101. /*                                                                        */
  102. /*  class TBinaryTreeInternalIteratorBase                                 */
  103. /*  class TBinaryTreeExternalIteratorBase                                 */
  104. /*                                                                        */
  105. /*  Base classes for binary search tree iterator templates.               */
  106. /*                                                                        */
  107. /*------------------------------------------------------------------------*/
  108.  
  109. class _BIDSCLASS TBinaryTreeInternalIteratorBase
  110. {
  111.  
  112. public:
  113.  
  114.     TBinaryTreeInternalIteratorBase( TBinarySearchTreeBase _BIDSFAR & tree,
  115.         TBinarySearchTreeBase::IteratorOrder order ) :
  116.         _tree(tree),
  117.         Node(tree.Root),
  118.         Order(order)
  119.         {
  120.         }
  121.  
  122.  
  123.     void Iterate();
  124.  
  125. protected:
  126.  
  127.     TBinarySearchTreeBase _BIDSFAR &Tree()
  128.         {
  129.         return _tree;
  130.         }
  131.  
  132. private:
  133.  
  134.     virtual void Apply( TBinarySearchTreeBase::BinNode _BIDSFAR *Node,
  135.                         TBinarySearchTreeBase::BinNode _BIDSFAR *Parent ) = 0;
  136.  
  137.     TBinarySearchTreeBase _BIDSFAR &_tree;
  138.     TBinarySearchTreeBase::BinNode _BIDSFAR *Node;
  139.     TBinarySearchTreeBase::IteratorOrder Order;
  140.  
  141.     TBinaryTreeInternalIteratorBase( const TBinaryTreeInternalIteratorBase _BIDSFAR & );
  142.     const TBinaryTreeInternalIteratorBase _BIDSFAR &
  143.         operator = ( const TBinaryTreeInternalIteratorBase _BIDSFAR & );
  144.  
  145. };
  146.  
  147. class _BIDSCLASS TBinaryTreeExternalIteratorBase
  148. {
  149.  
  150. public:
  151.  
  152.     void Restart();
  153.  
  154. protected:
  155.  
  156.     TBinaryTreeExternalIteratorBase( TBinarySearchTreeBase _BIDSFAR & tree,
  157.         TBinarySearchTreeBase::IteratorOrder order = TBinarySearchTreeBase::InOrder );
  158.     ~TBinaryTreeExternalIteratorBase();
  159.  
  160.     TBinarySearchTreeBase::BinNode _BIDSFAR *GetCurrent() const
  161.         {
  162.         return Current;
  163.         }
  164.  
  165.     TBinarySearchTreeBase::BinNode _BIDSFAR *Next();
  166.  
  167. private:
  168.  
  169.     TStackAsList<TBinarySearchTreeBase::BinNode _BIDSFAR *> *Stack;
  170.     TBinarySearchTreeBase _BIDSFAR *Tree;
  171.     TBinarySearchTreeBase::BinNode _BIDSFAR *Current;
  172.     TBinarySearchTreeBase::IteratorOrder Order;
  173.     int LeftVisited;
  174.     int RightVisited;
  175.     int Processed;
  176.  
  177.     int IsInOrder() const;
  178.  
  179.     TBinaryTreeExternalIteratorBase( const TBinaryTreeExternalIteratorBase _BIDSFAR & );
  180.     const TBinaryTreeExternalIteratorBase _BIDSFAR &
  181.         operator = ( const TBinaryTreeExternalIteratorBase _BIDSFAR & );
  182.  
  183. };
  184.  
  185. inline int TBinaryTreeExternalIteratorBase::IsInOrder() const
  186. {
  187.     return (Current->Left == 0 || LeftVisited != 0) &&
  188.            (Current->Right == 0 || RightVisited == 0);
  189. }
  190.  
  191. /*------------------------------------------------------------------------*/
  192. /*                                                                        */
  193. /*  template <class T> class TBinaryNodeImp                               */
  194. /*                                                                        */
  195. /*  Node for use with binary trees                                        */
  196. /*                                                                        */
  197. /*------------------------------------------------------------------------*/
  198.  
  199. template <class T> class _BIDSCLASS TBinaryNodeImp :
  200.     public TBinarySearchTreeBase::BinNode
  201. {
  202.  
  203. public:
  204.  
  205.     TBinaryNodeImp( const T& t ) : Data(t) {}
  206.     T Data;
  207. }
  208.  
  209. /*------------------------------------------------------------------------*/
  210. /*                                                                        */
  211. /*  template <class T> class TBinarySearchTreeImp                         */
  212. /*  template <class T> class TBinaryTreeInternalIterator                  */
  213. /*  template <class T> class TBinarySearchTreeIteratorImp                 */
  214. /*                                                                        */
  215. /*  Standard unbalanced binary tree and iterators                         */
  216. /*                                                                        */
  217. /*------------------------------------------------------------------------*/
  218.  
  219. template <class T> class _BIDSCLASS TBinarySearchTreeImp :
  220.     public TBinarySearchTreeBase
  221. {
  222.  
  223.     typedef TBinarySearchTreeBase Parent;
  224.  
  225. public:
  226.  
  227.     typedef void (_BIDSFAR *IterFunc)(T _BIDSFAR&, void _BIDSFAR*);
  228.  
  229.     ~TBinarySearchTreeImp()
  230.         {
  231.         Flush();
  232.         }
  233.  
  234.     int Add( const T& t )
  235.         {
  236.         return Parent::InsertNode( new TBinaryNodeImp<T>(t) );
  237.         }
  238.  
  239.     int Detach( const T& t )
  240.         {
  241.         return Parent::RemoveNode( &TBinaryNodeImp<T>(t), 0 );
  242.         }
  243.  
  244.     T _BIDSFAR * Find( const T& t ) const
  245.         {
  246.         TBinaryNodeImp<T> _BIDSFAR *res =
  247.             Promote(Parent::FindNode( &TBinaryNodeImp<T>(t) ));
  248.         return res == 0 ? 0 : &Promote(res)->Data;
  249.         }
  250.  
  251.     void ForEach( IterFunc iter,
  252.                   void _BIDSFAR * args,
  253.                   IteratorOrder order = InOrder );
  254.  
  255.     void Flush()
  256.         {
  257.         Parent::Flush();
  258.         }
  259.  
  260.     Parent::GetItemsInContainer;
  261.     Parent::IsEmpty;
  262.  
  263. protected:
  264.  
  265.     virtual int EqualTo( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 )
  266.         {
  267.         return Promote(n1)->Data == Promote(n2)->Data;
  268.         }
  269.  
  270.     virtual int LessThan( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 )
  271.         {
  272.         return Promote(n1)->Data < Promote(n2)->Data;
  273.         }
  274.  
  275.     virtual void DeleteNode( BinNode _BIDSFAR *node, int )
  276.         {
  277.         delete Promote(node);
  278.         }
  279.  
  280. private:
  281.  
  282.     static TBinaryNodeImp<T> _BIDSFAR _BIDSFAR *Promote( BinNode _BIDSFAR *node )
  283.         {
  284.         return STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,node);
  285.         }
  286.  
  287.     static const TBinaryNodeImp<T> _BIDSFAR *Promote( const BinNode _BIDSFAR *node )
  288.         {
  289.         return STATIC_CAST(const TBinaryNodeImp<T>_BIDSFAR *,node);
  290.         }
  291.  
  292. };
  293.  
  294. template <class T> class _BIDSCLASS TBinaryTreeInternalIterator :
  295.     public TBinaryTreeInternalIteratorBase
  296. {
  297.  
  298. public:
  299.  
  300.     typedef void (_BIDSFAR *IterFunc)(T _BIDSFAR&, void _BIDSFAR*);
  301.  
  302.     TBinaryTreeInternalIterator(
  303.                         TBinarySearchTreeBase& tree,
  304.                         IterFunc iter,
  305.                         void _BIDSFAR * args,
  306.                         TBinarySearchTreeBase::IteratorOrder order );
  307.  
  308. private:
  309.  
  310.     virtual void Apply( TBinarySearchTreeBase::BinNode _BIDSFAR *Node,
  311.                         TBinarySearchTreeBase::BinNode _BIDSFAR * );
  312.  
  313.     IterFunc Iter;
  314.     void _BIDSFAR *Args;
  315.  
  316. };
  317.  
  318. template <class T>
  319. TBinaryTreeInternalIterator<T>::TBinaryTreeInternalIterator(
  320.                     TBinarySearchTreeBase _BIDSFAR & tree,
  321.                     IterFunc iter,
  322.                     void _BIDSFAR *args,
  323.                     TBinarySearchTreeBase::IteratorOrder order ) :
  324.     TBinaryTreeInternalIteratorBase( tree, order ),
  325.     Iter(iter),
  326.     Args(args)
  327. {
  328. }
  329.  
  330. template <class T>
  331. void TBinaryTreeInternalIterator<T>::Apply( TBinarySearchTreeBase::BinNode *Node,
  332.                                             TBinarySearchTreeBase::BinNode _BIDSFAR * )
  333. {
  334.     Iter( STATIC_CAST(TBinaryNodeImp<T>*,Node)->Data, Args );
  335. }
  336.  
  337. template <class T>
  338. void TBinarySearchTreeImp<T>::ForEach( IterFunc iter,
  339.                                        void _BIDSFAR * args,
  340.                                        TBinarySearchTreeBase::IteratorOrder order = TBinarySearchTreeBase::InOrder )
  341. {
  342.     if( Root != 0 )
  343.         TBinaryTreeInternalIterator<T>( *this, iter, args, order ).Iterate();
  344. }
  345.  
  346. template <class T> class _BIDSCLASS TBinarySearchTreeIteratorImp :
  347.     private TBinaryTreeExternalIteratorBase
  348. {
  349.  
  350. public:
  351.  
  352.     TBinarySearchTreeIteratorImp( TBinarySearchTreeImp<T>& tree,
  353.         TBinarySearchTreeBase::IteratorOrder order = TBinarySearchTreeBase::InOrder ) :
  354.         TBinaryTreeExternalIteratorBase( tree, order ),
  355.         CurNode(STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,Next()))
  356.         {
  357.         }
  358.  
  359.     operator int() const
  360.         {
  361.         return CurNode != 0;
  362.         }
  363.  
  364.     const T& Current() const
  365.         {
  366.         PRECONDITION( CurNode != 0 );
  367.         return CurNode->Data;
  368.         }
  369.  
  370.     const T& operator ++ ( int )
  371.         {
  372.         PRECONDITION( CurNode != 0 );
  373.         const T& t = Current();
  374.         CurNode = STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,Next());
  375.         return t;
  376.         }
  377.  
  378.     const T& operator ++ ()
  379.         {
  380.         PRECONDITION( CurNode != 0 );
  381.         CurNode = STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,Next());
  382.         return Current();
  383.         }
  384.  
  385.     void Restart()
  386.         {
  387.         TBinaryTreeExternalIteratorBase::Restart();
  388.         CurNode = STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,Next());
  389.         }
  390.  
  391. private:
  392.  
  393.     TBinaryNodeImp<T>_BIDSFAR * CurNode;
  394.  
  395. };
  396.  
  397. /*------------------------------------------------------------------------*/
  398. /*                                                                        */
  399. /*  template <class T> class TIBinarySearchTreeImp                        */
  400. /*  template <class T> class TIBinarySearchTreeIteratorImp                */
  401. /*                                                                        */
  402. /*  Standard indirect unbalanced binary tree and iterators                */
  403. /*                                                                        */
  404. /*------------------------------------------------------------------------*/
  405.  
  406. template <class T> class _BIDSCLASS TIBinarySearchTreeIteratorImp;
  407.  
  408. template <class T> class _BIDSCLASS TIBinarySearchTreeImp :
  409.     private TBinarySearchTreeImp<TVoidPointer>
  410. {
  411.  
  412. public:
  413.  
  414.     typedef void (_BIDSFAR *IterFunc)(T _BIDSFAR&, void _BIDSFAR*);
  415.  
  416.     typedef TBinarySearchTreeImp<TVoidPointer> Parent;
  417.     friend class _BIDSCLASS TIBinarySearchTreeIteratorImp<T>;
  418.  
  419.     int Add( T _BIDSFAR * t )
  420.         {
  421.         return Parent::Add( t );
  422.         }
  423.         
  424.     int Detach( T _BIDSFAR *t, int del = 0 )
  425.         {
  426.         return Parent::RemoveNode( &TBinaryNodeImp<TVoidPointer>(t), del );
  427.         }
  428.  
  429.     void Flush( int del = 0 )
  430.         {
  431.         TBinarySearchTreeBase::Flush(del);
  432.         }
  433.  
  434.     T _BIDSFAR * Find( T _BIDSFAR * t ) const
  435.         {
  436.         TVoidPointer *res = Parent::Find(t);
  437.         return res == 0 ? 0 :
  438.                STATIC_CAST(T _BIDSFAR *,STATIC_CAST(void _BIDSFAR *,*res));
  439.         }
  440.  
  441.     void ForEach( IterFunc iter, void _BIDSFAR * args,
  442.                   IteratorOrder order = InOrder )
  443. {
  444.     if( Root != 0 )
  445.         TIBinaryTreeInternalIterator<T>( *this, iter, args, order ).Iterate();
  446. }
  447.  
  448.  
  449.     Parent::GetItemsInContainer;
  450.     Parent::IsEmpty;
  451.  
  452. protected:
  453.  
  454.     virtual int EqualTo( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 )
  455.         {
  456.         return *GetData(n1) == *GetData(n2);
  457.         }
  458.  
  459.     virtual int LessThan( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 )
  460.         {
  461.         return *GetData(n1) < *GetData(n2);
  462.         }
  463.  
  464.     virtual void DeleteNode( BinNode _BIDSFAR *node, int del )
  465.         {
  466.         if( del )
  467.             delete GetData(node);
  468.         delete Promote(node);
  469.         }
  470.  
  471. private:
  472.  
  473.     static TBinaryNodeImp<TVoidPointer> _BIDSFAR *Promote( BinNode _BIDSFAR *node )
  474.         {
  475.         return STATIC_CAST(TBinaryNodeImp<TVoidPointer> _BIDSFAR *,node);
  476.         }
  477.  
  478.     static const TBinaryNodeImp<TVoidPointer> _BIDSFAR *Promote( const BinNode _BIDSFAR *node )
  479.         {
  480.         return STATIC_CAST(const TBinaryNodeImp<TVoidPointer> _BIDSFAR *,node);
  481.         }
  482.  
  483.     static T _BIDSFAR *GetData( BinNode _BIDSFAR *node )
  484.         {
  485.         return STATIC_CAST(T _BIDSFAR *,STATIC_CAST(void _BIDSFAR *,Promote(node)->Data));
  486.         }
  487.  
  488. };
  489.  
  490. template <class T> class _BIDSCLASS TIBinaryTreeInternalIterator :
  491.     public TBinaryTreeInternalIteratorBase
  492. {
  493.  
  494. public:
  495.  
  496.     typedef void (_BIDSFAR *IterFunc)(T _BIDSFAR&, void _BIDSFAR*);
  497.  
  498.     TIBinaryTreeInternalIterator( TBinarySearchTreeBase& tree,
  499.                         IterFunc iter,
  500.                         void _BIDSFAR * args,
  501.                         TBinarySearchTreeBase::IteratorOrder order ) :
  502.         TBinaryTreeInternalIteratorBase( tree, order ),
  503.         Iter(iter),
  504.         Args(args)
  505.         {
  506.         }
  507.  
  508.  
  509. private:
  510.  
  511.     virtual void Apply( TBinarySearchTreeBase::BinNode _BIDSFAR *Node,
  512.                         TBinarySearchTreeBase::BinNode _BIDSFAR * );
  513.  
  514.     IterFunc Iter;
  515.     void _BIDSFAR *Args;
  516.  
  517. };
  518.  
  519. template <class T>
  520. void TIBinaryTreeInternalIterator<T>::Apply( TBinarySearchTreeBase::BinNode _BIDSFAR *Node, TBinarySearchTreeBase::BinNode _BIDSFAR * )
  521. {
  522.     Iter( *(T _BIDSFAR *)(void _BIDSFAR *)(STATIC_CAST(TBinaryNodeImp<TVoidPointer>*,Node)->Data), Args );
  523. }
  524.  
  525. template <class T> class _BIDSCLASS TIBinarySearchTreeIteratorImp :
  526.     private TBinarySearchTreeIteratorImp<TVoidPointer>
  527. {
  528.  
  529.     typedef TBinarySearchTreeIteratorImp<TVoidPointer> Parent;
  530.  
  531. public:
  532.  
  533.     TIBinarySearchTreeIteratorImp( TIBinarySearchTreeImp<T>& tree,
  534.         TBinarySearchTreeBase::IteratorOrder order = TBinarySearchTreeBase::InOrder ) :
  535.         TBinarySearchTreeIteratorImp<TVoidPointer>(tree,order)
  536.         {
  537.         }
  538.  
  539.     Parent::operator int;
  540.  
  541.     T _BIDSFAR *Current() const
  542.         {
  543.         return (T _BIDSFAR *)(void _BIDSFAR *)(Parent::Current());
  544.         }
  545.  
  546.     T _BIDSFAR *operator ++ ( int i )
  547.         {
  548.         return (T _BIDSFAR *)(void _BIDSFAR *)(Parent::operator++(i));
  549.         }
  550.  
  551.     T _BIDSFAR *operator ++ ()
  552.         {
  553.         return (T _BIDSFAR *)(void _BIDSFAR *)(Parent::operator++());
  554.         }
  555.  
  556.     Parent::Restart;
  557.  
  558. };
  559.  
  560. #if defined( BI_CLASSLIB_NO_po )
  561. #pragma option -po.
  562. #endif
  563.  
  564. #pragma option -Vo.
  565.  
  566. #endif  // CLASSLIB_BINIMP_H
  567.  
  568.  
  569.