home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c083 / 12.ddi / CLASSINC.PAK / BINIMP.H < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-02  |  16.6 KB  |  568 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  BINIMP.H                                                              */
  4. /*                                                                        */
  5. /*  Copyright (c) 1993 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  // __CLASSLIB_DEFS_H
  16.  
  17. #if !defined( __CLASSLIB_VOIDP_H )
  18. #include "classlib\voidp.h"
  19. #endif  // __CLASSLIB_VOIDP_H
  20.  
  21. #if !defined( __CLASSLIB_STACKS_H )
  22. #include "classlib\stacks.h"
  23. #endif  // __CLASSLIB_STACKS_H
  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.  
  159.     TBinarySearchTreeBase::BinNode _BIDSFAR *GetCurrent() const
  160.         {
  161.         return Current;
  162.         }
  163.  
  164.     TBinarySearchTreeBase::BinNode _BIDSFAR *Next();
  165.  
  166. private:
  167.  
  168.     TStackAsList<TBinarySearchTreeBase::BinNode _BIDSFAR *> Stack;
  169.     TBinarySearchTreeBase _BIDSFAR *Tree;
  170.     TBinarySearchTreeBase::BinNode _BIDSFAR *Current;
  171.     TBinarySearchTreeBase::IteratorOrder Order;
  172.     int LeftVisited;
  173.     int RightVisited;
  174.     int Processed;
  175.  
  176.     int IsInOrder() const;
  177.  
  178.     TBinaryTreeExternalIteratorBase( const TBinaryTreeExternalIteratorBase _BIDSFAR & );
  179.     const TBinaryTreeExternalIteratorBase _BIDSFAR &
  180.         operator = ( const TBinaryTreeExternalIteratorBase _BIDSFAR & );
  181.  
  182. };
  183.  
  184. inline int TBinaryTreeExternalIteratorBase::IsInOrder() const
  185. {
  186.     return (Current->Left == 0 || LeftVisited != 0) &&
  187.            (Current->Right == 0 || RightVisited == 0);
  188. }
  189.  
  190. /*------------------------------------------------------------------------*/
  191. /*                                                                        */
  192. /*  template <class T> class TBinaryNodeImp                               */
  193. /*                                                                        */
  194. /*  Node for use with binary trees                                        */
  195. /*                                                                        */
  196. /*------------------------------------------------------------------------*/
  197.  
  198. template <class T> class _BIDSCLASS TBinaryNodeImp :
  199.     public TBinarySearchTreeBase::BinNode
  200. {
  201.  
  202. public:
  203.  
  204.     TBinaryNodeImp( const T& t ) : Data(t) {}
  205.     T Data;
  206. }
  207.  
  208. /*------------------------------------------------------------------------*/
  209. /*                                                                        */
  210. /*  template <class T> class TBinarySearchTreeImp                         */
  211. /*  template <class T> class TBinaryTreeInternalIterator                  */
  212. /*  template <class T> class TBinarySearchTreeIteratorImp                 */
  213. /*                                                                        */
  214. /*  Standard unbalanced binary tree and iterators                         */
  215. /*                                                                        */
  216. /*------------------------------------------------------------------------*/
  217.  
  218. template <class T> class _BIDSCLASS TBinarySearchTreeImp :
  219.     public TBinarySearchTreeBase
  220. {
  221.  
  222.     typedef TBinarySearchTreeBase Parent;
  223.  
  224. public:
  225.  
  226.     typedef void (_BIDSFAR *IterFunc)(T _BIDSFAR&, void _BIDSFAR*);
  227.  
  228.     ~TBinarySearchTreeImp()
  229.         {
  230.         Flush();
  231.         }
  232.  
  233.     int Add( const T& t )
  234.         {
  235.         return Parent::InsertNode( new TBinaryNodeImp<T>(t) );
  236.         }
  237.  
  238.     int Detach( const T& t )
  239.         {
  240.         return Parent::RemoveNode( &TBinaryNodeImp<T>(t), 0 );
  241.         }
  242.  
  243.     T _BIDSFAR * Find( const T& t ) const
  244.         {
  245.         TBinaryNodeImp<T> _BIDSFAR *res =
  246.             Promote(Parent::FindNode( &TBinaryNodeImp<T>(t) ));
  247.         return res == 0 ? 0 : &Promote(res)->Data;
  248.         }
  249.  
  250.     void ForEach( IterFunc iter,
  251.                   void _BIDSFAR * args,
  252.                   IteratorOrder order = InOrder );
  253.  
  254.     void Flush()
  255.         {
  256.         Parent::Flush();
  257.         }
  258.  
  259.     Parent::GetItemsInContainer;
  260.     Parent::IsEmpty;
  261.  
  262. protected:
  263.  
  264.     virtual int EqualTo( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 )
  265.         {
  266.         return Promote(n1)->Data == Promote(n2)->Data;
  267.         }
  268.  
  269.     virtual int LessThan( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 )
  270.         {
  271.         return Promote(n1)->Data < Promote(n2)->Data;
  272.         }
  273.  
  274.     virtual void DeleteNode( BinNode _BIDSFAR *node, int )
  275.         {
  276.         delete Promote(node);
  277.         }
  278.  
  279. private:
  280.  
  281.     static TBinaryNodeImp<T> _BIDSFAR _BIDSFAR *Promote( BinNode _BIDSFAR *node )
  282.         {
  283.         return STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,node);
  284.         }
  285.  
  286.     static const TBinaryNodeImp<T> _BIDSFAR *Promote( const BinNode _BIDSFAR *node )
  287.         {
  288.         return STATIC_CAST(const TBinaryNodeImp<T>_BIDSFAR *,node);
  289.         }
  290.  
  291. };
  292.  
  293. template <class T> class _BIDSCLASS TBinaryTreeInternalIterator :
  294.     public TBinaryTreeInternalIteratorBase
  295. {
  296.  
  297. public:
  298.  
  299.     typedef void (_BIDSFAR *IterFunc)(T _BIDSFAR&, void _BIDSFAR*);
  300.  
  301.     TBinaryTreeInternalIterator(
  302.                         TBinarySearchTreeBase& tree,
  303.                         IterFunc iter,
  304.                         void _BIDSFAR * args,
  305.                         TBinarySearchTreeBase::IteratorOrder order );
  306.  
  307. private:
  308.  
  309.     virtual void Apply( TBinarySearchTreeBase::BinNode _BIDSFAR *Node,
  310.                         TBinarySearchTreeBase::BinNode _BIDSFAR * );
  311.  
  312.     IterFunc Iter;
  313.     void _BIDSFAR *Args;
  314.  
  315. };
  316.  
  317. template <class T>
  318. TBinaryTreeInternalIterator<T>::TBinaryTreeInternalIterator(
  319.                     TBinarySearchTreeBase _BIDSFAR & tree,
  320.                     IterFunc iter,
  321.                     void _BIDSFAR *args,
  322.                     TBinarySearchTreeBase::IteratorOrder order ) :
  323.     TBinaryTreeInternalIteratorBase( tree, order ),
  324.     Iter(iter),
  325.     Args(args)
  326. {
  327. }
  328.  
  329. template <class T>
  330. void TBinaryTreeInternalIterator<T>::Apply( TBinarySearchTreeBase::BinNode *Node,
  331.                                             TBinarySearchTreeBase::BinNode _BIDSFAR * )
  332. {
  333.     Iter( STATIC_CAST(TBinaryNodeImp<T>*,Node)->Data, Args );
  334. }
  335.  
  336. template <class T>
  337. void TBinarySearchTreeImp<T>::ForEach( IterFunc iter,
  338.                                        void _BIDSFAR * args,
  339.                                        TBinarySearchTreeBase::IteratorOrder order = TBinarySearchTreeBase::InOrder )
  340. {
  341.     if( Root != 0 )
  342.         TBinaryTreeInternalIterator<T>( *this, iter, args, order ).Iterate();
  343. }
  344.  
  345. template <class T> class _BIDSCLASS TBinarySearchTreeIteratorImp :
  346.     private TBinaryTreeExternalIteratorBase
  347. {
  348.  
  349. public:
  350.  
  351.     TBinarySearchTreeIteratorImp( TBinarySearchTreeImp<T>& tree,
  352.         TBinarySearchTreeBase::IteratorOrder order = TBinarySearchTreeBase::InOrder ) :
  353.         TBinaryTreeExternalIteratorBase( tree, order ),
  354.         CurNode(STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,Next()))
  355.         {
  356.         }
  357.  
  358.     operator int() const
  359.         {
  360.         return CurNode != 0;
  361.         }
  362.  
  363.     const T& Current() const
  364.         {
  365.         PRECONDITION( CurNode != 0 );
  366.         return CurNode->Data;
  367.         }
  368.  
  369.     const T& operator ++ ( int )
  370.         {
  371.         PRECONDITION( CurNode != 0 );
  372.         const T& t = Current();
  373.         CurNode = STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,Next());
  374.         return t;
  375.         }
  376.  
  377.     const T& operator ++ ()
  378.         {
  379.         PRECONDITION( CurNode != 0 );
  380.         CurNode = STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,Next());
  381.         return Current();
  382.         }
  383.  
  384.     void Restart()
  385.         {
  386.         TBinaryTreeExternalIteratorBase::Restart();
  387.         CurNode = STATIC_CAST(TBinaryNodeImp<T>_BIDSFAR *,Next());
  388.         }
  389.  
  390. private:
  391.  
  392.     TBinaryNodeImp<T>_BIDSFAR * CurNode;
  393.  
  394. };
  395.  
  396. /*------------------------------------------------------------------------*/
  397. /*                                                                        */
  398. /*  template <class T> class TIBinarySearchTreeImp                        */
  399. /*  template <class T> class TIBinarySearchTreeIteratorImp                */
  400. /*                                                                        */
  401. /*  Standard indirect unbalanced binary tree and iterators                */
  402. /*                                                                        */
  403. /*------------------------------------------------------------------------*/
  404.  
  405. template <class T> class _BIDSCLASS TIBinarySearchTreeIteratorImp;
  406.  
  407. template <class T> class _BIDSCLASS TIBinarySearchTreeImp :
  408.     private TBinarySearchTreeImp<TVoidPointer>
  409. {
  410.  
  411. public:
  412.  
  413.     typedef void (_BIDSFAR *IterFunc)(T _BIDSFAR&, void _BIDSFAR*);
  414.  
  415.     typedef TBinarySearchTreeImp<TVoidPointer> Parent;
  416.     friend class _BIDSCLASS TIBinarySearchTreeIteratorImp<T>;
  417.  
  418.     int Add( T _BIDSFAR * t )
  419.         {
  420.         return Parent::Add( t );
  421.         }
  422.         
  423.     int Detach( T _BIDSFAR *t, int del = 0 )
  424.         {
  425.         return Parent::RemoveNode( &TBinaryNodeImp<TVoidPointer>(t), del );
  426.         }
  427.  
  428.     void Flush( int del = 0 )
  429.         {
  430.         TBinarySearchTreeBase::Flush(del);
  431.         }
  432.  
  433.     T _BIDSFAR * Find( T _BIDSFAR * t ) const
  434.         {
  435.         TVoidPointer *res = Parent::Find(t);
  436.         return res == 0 ? 0 :
  437.                STATIC_CAST(T _BIDSFAR *,STATIC_CAST(void _BIDSFAR *,*res));
  438.         }
  439.  
  440.     void ForEach( IterFunc iter, void _BIDSFAR * args,
  441.                   IteratorOrder order = InOrder )
  442. {
  443.     if( Root != 0 )
  444.         TIBinaryTreeInternalIterator<T>( *this, iter, args, order ).Iterate();
  445. }
  446.  
  447.  
  448.     Parent::GetItemsInContainer;
  449.     Parent::IsEmpty;
  450.  
  451. protected:
  452.  
  453.     virtual int EqualTo( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 )
  454.         {
  455.         return *GetData(n1) == *GetData(n2);
  456.         }
  457.  
  458.     virtual int LessThan( BinNode _BIDSFAR *n1, BinNode _BIDSFAR *n2 )
  459.         {
  460.         return *GetData(n1) < *GetData(n2);
  461.         }
  462.  
  463.     virtual void DeleteNode( BinNode _BIDSFAR *node, int del )
  464.         {
  465.         if( del )
  466.             delete GetData(node);
  467.         delete Promote(node);
  468.         }
  469.  
  470. private:
  471.  
  472.     static TBinaryNodeImp<TVoidPointer> _BIDSFAR *Promote( BinNode _BIDSFAR *node )
  473.         {
  474.         return STATIC_CAST(TBinaryNodeImp<TVoidPointer> _BIDSFAR *,node);
  475.         }
  476.  
  477.     static const TBinaryNodeImp<TVoidPointer> _BIDSFAR *Promote( const BinNode _BIDSFAR *node )
  478.         {
  479.         return STATIC_CAST(const TBinaryNodeImp<TVoidPointer> _BIDSFAR *,node);
  480.         }
  481.  
  482.     static T _BIDSFAR *GetData( BinNode _BIDSFAR *node )
  483.         {
  484.         return STATIC_CAST(T _BIDSFAR *,STATIC_CAST(void _BIDSFAR *,Promote(node)->Data));
  485.         }
  486.  
  487. };
  488.  
  489. template <class T> class _BIDSCLASS TIBinaryTreeInternalIterator :
  490.     public TBinaryTreeInternalIteratorBase
  491. {
  492.  
  493. public:
  494.  
  495.     typedef void (_BIDSFAR *IterFunc)(T _BIDSFAR&, void _BIDSFAR*);
  496.  
  497.     TIBinaryTreeInternalIterator( TBinarySearchTreeBase& tree,
  498.                         IterFunc iter,
  499.                         void _BIDSFAR * args,
  500.                         TBinarySearchTreeBase::IteratorOrder order ) :
  501.         TBinaryTreeInternalIteratorBase( tree, order ),
  502.         Iter(iter),
  503.         Args(args)
  504.         {
  505.         }
  506.  
  507.  
  508. private:
  509.  
  510.     virtual void Apply( TBinarySearchTreeBase::BinNode _BIDSFAR *Node,
  511.                         TBinarySearchTreeBase::BinNode _BIDSFAR * );
  512.  
  513.     IterFunc Iter;
  514.     void _BIDSFAR *Args;
  515.  
  516. };
  517.  
  518. template <class T>
  519. void TIBinaryTreeInternalIterator<T>::Apply( TBinarySearchTreeBase::BinNode _BIDSFAR *Node, TBinarySearchTreeBase::BinNode _BIDSFAR * )
  520. {
  521.     Iter( *(T _BIDSFAR *)(void _BIDSFAR *)(STATIC_CAST(TBinaryNodeImp<TVoidPointer>*,Node)->Data), Args );
  522. }
  523.  
  524. template <class T> class _BIDSCLASS TIBinarySearchTreeIteratorImp :
  525.     private TBinarySearchTreeIteratorImp<TVoidPointer>
  526. {
  527.  
  528.     typedef TBinarySearchTreeIteratorImp<TVoidPointer> Parent;
  529.  
  530. public:
  531.  
  532.     TIBinarySearchTreeIteratorImp( TIBinarySearchTreeImp<T>& tree,
  533.         TBinarySearchTreeBase::IteratorOrder order = TBinarySearchTreeBase::InOrder ) :
  534.         TBinarySearchTreeIteratorImp<TVoidPointer>(tree,order)
  535.         {
  536.         }
  537.  
  538.     Parent::operator int;
  539.  
  540.     T _BIDSFAR *Current() const
  541.         {
  542.         return (T _BIDSFAR *)(void _BIDSFAR *)(Parent::Current());
  543.         }
  544.  
  545.     T _BIDSFAR *operator ++ ( int i )
  546.         {
  547.         return (T _BIDSFAR *)(void _BIDSFAR *)(Parent::operator++(i));
  548.         }
  549.  
  550.     T _BIDSFAR *operator ++ ()
  551.         {
  552.         return (T _BIDSFAR *)(void _BIDSFAR *)(Parent::operator++());
  553.         }
  554.  
  555.     Parent::Restart;
  556.  
  557. };
  558.  
  559. #if defined( BI_CLASSLIB_NO_po )
  560. #pragma option -po.
  561. #endif
  562.  
  563. #pragma option -Vo.
  564.  
  565. #endif  // __CLASSLIB_BINIMP_H
  566.  
  567.  
  568.