home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / wxos2233.zip / wxOS2-2_3_3.zip / wxWindows-2.3.3 / utils / HelpGen / src / wxstlac.h < prev    next >
C/C++ Source or Header  |  2001-11-19  |  15KB  |  672 lines
  1. /////////////////////////////////////////////////////////////////////////////
  2. // Name:        No names yet.
  3. // Purpose:     Contrib. demo
  4. // Author:      Aleksandras Gluchovas
  5. // Modified by:
  6. // Created:     27/09/98
  7. // RCS-ID:      $Id: wxstlac.h,v 1.2 2001/11/18 12:25:11 GD Exp $
  8. // Copyright:   (c) Aleskandars Gluchovas
  9. // Licence:       wxWindows licence
  10. /////////////////////////////////////////////////////////////////////////////
  11.  
  12. #ifndef __WXSTLAC_G__
  13. #define __WXSTLAC_G__
  14.  
  15. #ifdef new
  16. #undef new
  17. #endif
  18.  
  19. #include <stddef.h>
  20. #if !defined(__WXMAC__) || defined(__DARWIN__)
  21. #  include <sys/types.h>
  22. #endif
  23. #include <memory.h>
  24. #include <limits.h>
  25. #include <new.h>
  26.  
  27. // the below macro used internally (see actual interface after this macro)
  28.  
  29. // arguments:
  30. //
  31. //        ARG_IS_UNIQUE
  32. //        ASSOC_CONT_CLASS_NAME
  33. //
  34. //        ARG_VALUE_TYPE
  35. //      ARG_KEY_TYPE
  36. //      ARG_ACTUAL_VALUE_TYPE
  37. //      
  38. //      _KEY_NAME
  39. //      _VALUE_NAME
  40. //
  41. //        _X_KEY_NAME
  42. //         _X_VALUE_NAME
  43. //
  44. //      _INSERT_METHOD_DEFINITION
  45.  
  46. #define __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE, \
  47. FUNCTOR,\
  48. ASSOC_CONT_CLASS_NAME, \
  49. ARG_VALUE_TYPE, \
  50. ARG_KEY_TYPE, \
  51. ARG_ACTUAL_VALUE_TYPE, \
  52. _KEY_NAME, \
  53. _VALUE_NAME, \
  54. _X_KEY_NAME, \
  55. _X_VALUE_NAME, \
  56. _INSERT_METHOD_DEFINITION \
  57. ) class \
  58. ASSOC_CONT_CLASS_NAME\
  59. {\
  60. protected:\
  61. \
  62. public:\
  63.     typedef ARG_VALUE_TYPE        value_type;\
  64.     typedef ARG_KEY_TYPE          key_type;\
  65.     typedef ARG_ACTUAL_VALUE_TYPE actual_value_type;\
  66. \
  67.     typedef value_type*              pointer;\
  68.     typedef value_type&              reference;\
  69. \
  70.     typedef const value_type&      const_reference;\
  71. \
  72.     typedef FUNCTOR                  key_compare;\
  73.     typedef key_compare           Compare;\
  74. \
  75. protected:\
  76. \
  77.     struct tree_node \
  78.     {\
  79.         tree_node*  mpParent;\
  80.         tree_node*  mpLeft;\
  81.         tree_node*  mpRight;\
  82. \
  83.         value_type  mData;\
  84.     };\
  85. \
  86.     typedef tree_node* node_ref_type;\
  87. \
  88.     node_ref_type   mpRoot;\
  89.     node_ref_type   mpLeftMost;\
  90.     node_ref_type   mpRightMost;\
  91. \
  92.     node_ref_type   mpFreeListHead;\
  93.     int             mKeyIsUnique;\
  94. \
  95.     key_compare     mCmpFunctorObj;\
  96. \
  97. public:\
  98. \
  99.     static inline node_ref_type next( node_ref_type pNode )\
  100.     {\
  101.         if ( pNode->mpRight ) \
  102.         {\
  103.             pNode = pNode->mpRight;\
  104. \
  105.             while ( pNode->mpLeft ) pNode = pNode->mpLeft;\
  106. \
  107.             return pNode;\
  108.         }\
  109.         else\
  110.         if ( pNode->mpParent )\
  111.         {\
  112.             if ( pNode == pNode->mpParent->mpLeft )\
  113. \
  114.                 return pNode->mpParent;\
  115. \
  116.             pNode = pNode->mpParent;\
  117. \
  118.             node_ref_type prevNode = pNode;\
  119.             pNode = pNode->mpParent;\
  120. \
  121.             while(pNode)\
  122.             {\
  123.                 if ( pNode->mpRight &&\
  124.                      pNode->mpRight != prevNode\
  125.                    ) return pNode;\
  126. \
  127.                 prevNode = pNode;\
  128.                 pNode= pNode->mpParent;\
  129.             }\
  130. \
  131.             return 0;\
  132.         }\
  133.         else\
  134.             return 0;\
  135.     }\
  136. \
  137.     static inline node_ref_type prev( node_ref_type pNode )\
  138.     {\
  139.         if ( pNode->mpLeft ) \
  140.         {\
  141.             pNode = pNode->mpLeft;\
  142. \
  143.             while ( pNode->mpRight ) pNode = pNode->mpRight;\
  144. \
  145.             return pNode;\
  146.         }\
  147.         else\
  148.         if ( pNode->mpParent )\
  149.         {\
  150.             if ( pNode == pNode->mpParent->mpRight )\
  151.                 return pNode->mpParent;\
  152. \
  153.             pNode = pNode->mpParent;\
  154. \
  155.             node_ref_type prevNode = pNode;\
  156.             pNode = pNode->mpParent;\
  157. \
  158.             while(pNode)\
  159.             {\
  160.                 if ( pNode->mpLeft &&\
  161.                      pNode->mpLeft != prevNode\
  162.                    ) return pNode;\
  163. \
  164.                 prevNode = pNode;\
  165.                 pNode= pNode->mpParent;\
  166.             }\
  167. \
  168.             return 0;\
  169.         }\
  170.         else \
  171.             return 0;\
  172.     }\
  173. \
  174. protected:\
  175. \
  176.     inline int are_equel( const key_type& x, const key_type& y )\
  177.     {\
  178.         return ( !mCmpFunctorObj(x,y) && !mCmpFunctorObj(y,x) );\
  179.     }\
  180. \
  181.     inline int is_less( const key_type& x, const key_type& y )\
  182.     {\
  183.         return mCmpFunctorObj(x,y);\
  184.     }\
  185. \
  186.     static inline const actual_value_type& value( node_ref_type pNode )\
  187.     {\
  188.         return pNode->_VALUE_NAME;\
  189.     }\
  190. \
  191.     static inline const key_type& key( node_ref_type pNode )\
  192.     {\
  193.         return pNode->_KEY_NAME;\
  194.     }\
  195. \
  196.     inline node_ref_type AllocNode() \
  197.     { \
  198.         if ( mpFreeListHead ) \
  199.         {\
  200.             node_ref_type pFreeNode = mpFreeListHead;\
  201.             mpFreeListHead = mpFreeListHead->mpLeft;\
  202. \
  203.             return pFreeNode;\
  204.         }\
  205.         else\
  206.         {\
  207.             char* pHeapBlock = new char[sizeof(tree_node)];\
  208. \
  209.             return (node_ref_type)pHeapBlock;\
  210.         }\
  211.     }\
  212. \
  213.     inline void DestroyFreeList()\
  214.     {\
  215.         while ( mpFreeListHead )\
  216.         {\
  217.             node_ref_type tmp = mpFreeListHead;\
  218.             mpFreeListHead = mpFreeListHead->mpLeft;\
  219. \
  220.             delete [](char*)tmp;\
  221.         }\
  222.     }\
  223. \
  224.     inline void RecycleNode( node_ref_type pNode ) \
  225.     {\
  226.         pNode->mpLeft = mpFreeListHead;\
  227.         mpFreeListHead = pNode;\
  228.     }\
  229. \
  230.     inline node_ref_type do_insert(const value_type& x = value_type() )\
  231.     {\
  232.         node_ref_type pNewNode = AllocNode();\
  233. \
  234.         pNewNode->mpParent = \
  235.             pNewNode->mpLeft =\
  236.                 pNewNode->mpRight = 0;\
  237. \
  238.         node_ref_type pCurrent = mpRoot;\
  239.         node_ref_type pParent = 0;\
  240.     \
  241.         while (pCurrent) \
  242.         {\
  243.             if ( mKeyIsUnique && are_equel( _X_KEY_NAME, value(pCurrent) ) )\
  244.             {\
  245.                 RecycleNode(pNewNode);\
  246.                 return 0;\
  247.             }\
  248. \
  249.             pParent = pCurrent;\
  250. \
  251.             pCurrent = is_less( _X_KEY_NAME, value(pCurrent) ) \
  252.                 ? pCurrent->mpLeft \
  253.                 : pCurrent->mpRight;\
  254.         }\
  255.     \
  256.         pNewNode->mpParent = pParent;\
  257. \
  258.         if(pParent)\
  259. \
  260.             if( is_less(_X_KEY_NAME, value(pParent) ) )\
  261.             \
  262.                 pParent->mpLeft = pNewNode;\
  263.             else\
  264.                 pParent->mpRight = pNewNode;\
  265.             else\
  266.                 mpRoot = pNewNode;\
  267. \
  268.         new ( &pNewNode->_KEY_NAME   ) key_type(_X_KEY_NAME);\
  269.         new ( &pNewNode->_VALUE_NAME ) actual_value_type(_X_VALUE_NAME);\
  270. \
  271.         if ( prev(pNewNode) == 0 ) mpLeftMost = pNewNode;\
  272.         if ( next(pNewNode) == 0 ) mpRightMost = pNewNode;\
  273. \
  274.         return pNewNode;\
  275.     }\
  276. \
  277.     friend class iterator;\
  278. \
  279. public:\
  280. \
  281.     class iterator;\
  282.     class const_iterator;\
  283. \
  284.     class iterator \
  285.     {\
  286.     public:\
  287.         node_ref_type mpNode;\
  288.         friend class CONT_CLASS_NAME;\
  289.         friend class const_iterator;\
  290.         friend class const_reverse_iterator;\
  291. \
  292.         inline iterator( node_ref_type pNode )\
  293.         {\
  294.             mpNode = pNode;\
  295.         }\
  296.     \
  297.     public:\
  298.         inline iterator() {}\
  299.         inline int operator==( const iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
  300.         inline int operator!=( const iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
  301. \
  302.         inline iterator( const iterator& other )\
  303.         {\
  304.             mpNode = other.mpNode;\
  305.         }\
  306. \
  307.         inline const iterator& operator=( const iterator& other )\
  308.         {\
  309.             mpNode = other.mpNode;\
  310.             return *this;\
  311.         }\
  312. \
  313.         inline const iterator& operator--() \
  314.         {\
  315.             mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
  316.             return *this;\
  317.         }\
  318. \
  319.         inline iterator operator--(int)\
  320.         {\
  321.             iterator tmp = *this;\
  322.             mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
  323.             return tmp;\
  324.         }\
  325. \
  326.         inline const iterator& operator++() \
  327.         {\
  328.             mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
  329.             return *this;\
  330.         }\
  331. \
  332.         inline iterator operator++(int)\
  333.         {\
  334.             iterator tmp = *this;\
  335.             mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
  336.             return tmp;\
  337.         }\
  338. \
  339.         inline reference operator*() const { return mpNode->mData; }\
  340.     };\
  341. \
  342. \
  343.     class const_iterator \
  344.     {\
  345.     public:\
  346.         node_ref_type mpNode;\
  347.         friend class CONT_CLASS_NAME;\
  348.         friend class const_reverse_iterator;\
  349. \
  350.         inline const_iterator( node_ref_type pNode )\
  351.         {\
  352.             mpNode = pNode;\
  353.         }\
  354.     \
  355.     public:\
  356.         inline const_iterator() {}\
  357. \
  358.         inline int operator==( const const_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
  359.         inline int operator!=( const const_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
  360. \
  361.         inline const_iterator( const iterator& other )\
  362.         {\
  363.             mpNode = other.mpNode;\
  364.         }\
  365. \
  366.         inline const_iterator( const const_iterator& other )\
  367.         {\
  368.             mpNode = other.mpNode;\
  369.         }\
  370. \
  371.         inline const const_iterator& operator=( const const_iterator& other )\
  372.         {\
  373.             mpNode = other.mpNode;\
  374.             return *this;\
  375.         }\
  376. \
  377.         inline const const_iterator& operator--() \
  378.         {\
  379.             mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
  380.             return *this;\
  381.         }\
  382. \
  383.         inline const_iterator operator--(int)\
  384.         {\
  385.             const_iterator tmp = *this;\
  386.             mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
  387.             return tmp;\
  388.         }\
  389. \
  390.         inline const const_iterator& operator++() \
  391.         {\
  392.             mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
  393.             return *this;\
  394.         }\
  395. \
  396.         inline const_iterator operator++(int)\
  397.         {\
  398.             const_iterator tmp = *this;\
  399.             mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
  400.             return tmp;\
  401.         }\
  402. \
  403.         inline const_reference operator*() const { return mpNode->mData; }\
  404.     };\
  405. \
  406. public:\
  407. \
  408.     inline ASSOC_CONT_CLASS_NAME( key_compare cmpFunctorObj = key_compare(),\
  409.                                   int keyIsUnique = ARG_IS_UNIQUE )\
  410.             : mpFreeListHead( 0 ),\
  411.               mKeyIsUnique( keyIsUnique ),\
  412.               mCmpFunctorObj( cmpFunctorObj )\
  413.     {\
  414.         mpLeftMost = 0;\
  415.         mpRightMost = 0;\
  416.         mpRoot = 0;\
  417.     }\
  418. \
  419.     inline ~ASSOC_CONT_CLASS_NAME() \
  420.     { \
  421.         erase( begin(), end() ); \
  422. \
  423.         DestroyFreeList();\
  424.     }\
  425. \
  426.     inline iterator begin() { return mpLeftMost; }\
  427.     inline iterator end()   { return 0; }\
  428. \
  429.     inline const_iterator begin() const { return mpLeftMost; }\
  430.     inline const_iterator end()   const { return 0; }\
  431. \
  432.     inline iterator lower_bound( const key_type& x )\
  433.     { \
  434.         node_ref_type pCurrent = mpRoot;\
  435.     \
  436.         while( pCurrent )\
  437.         {\
  438.             node_ref_type pParent = pCurrent;\
  439. \
  440.             if( are_equel( x, key(pCurrent) ) )\
  441.                 \
  442.                 return (pCurrent);\
  443.             else\
  444.                 pCurrent = is_less( x, key(pCurrent) ) \
  445.                     ? pCurrent->mpLeft \
  446.                     : pCurrent->mpRight;\
  447. \
  448.             if ( !pCurrent ) return (pParent);\
  449.         }\
  450. \
  451.         return begin();\
  452.     }\
  453. \
  454.     inline const_iterator lower_bound( const key_type& x ) const\
  455. \
  456.         { return const_iterator( lower_bound(x).mpNode ); }\
  457. \
  458.     inline iterator upper_bound( const key_type& x )\
  459.     {\
  460.         node_ref_type pCurrent = mpRoot;\
  461.     \
  462.         while( pCurrent )\
  463.         {\
  464.             node_ref_type pParent = pCurrent;\
  465. \
  466.             if( are_equel( x, key(pCurrent) ) )\
  467.                 \
  468.                 return (pCurrent);\
  469.             else\
  470.                 pCurrent = is_less( x, key(pCurrent) ) \
  471.                     ? pCurrent->mpLeft \
  472.                     : pCurrent->mpRight;\
  473. \
  474.             if ( !pCurrent ) return next(pParent);\
  475.         }\
  476. \
  477.         return end();\
  478.     }\
  479. \
  480.     inline const_iterator upper_bound( const key_type& x ) const\
  481. \
  482.         { return const_iterator( upper_bound(x).mpNode ); }\
  483. \
  484.     inline iterator find( const key_type& x )\
  485.     {\
  486.         node_ref_type pCurrent = mpRoot;\
  487.     \
  488.         while( pCurrent )\
  489.         {\
  490.             if( are_equel( x, key(pCurrent) ) )\
  491.                 \
  492.                 return (pCurrent);\
  493.             else\
  494.                 pCurrent = is_less( x, key(pCurrent) ) \
  495.                     ? pCurrent->mpLeft \
  496.                     : pCurrent->mpRight;\
  497.         }\
  498. \
  499.         return end();\
  500.     }\
  501. \
  502.     inline const_iterator find( const key_type& x ) const\
  503. \
  504.         { return const_iterator( find(x).mpNode ); }\
  505. \
  506.     inline void erase(iterator first, iterator last)\
  507.     {\
  508.         if ( first.mpNode == 0 ) return;\
  509. \
  510.         while( first != last ) \
  511.         {\
  512.             iterator next = first;\
  513.             ++next;\
  514.             erase( first );\
  515.             first = next;\
  516.         }\
  517.     }\
  518. \
  519.     inline void erase(iterator position)\
  520.     {\
  521.         if ( position.mpNode == 0 ) return;\
  522. \
  523.         node_ref_type pZ = position.mpNode;\
  524.         node_ref_type pX, pY;\
  525. \
  526.         if ( pZ == mpLeftMost ) mpLeftMost   = next(pZ);\
  527.         if ( pZ == mpRightMost ) mpRightMost = prev( pZ );\
  528. \
  529.         if ( !pZ->mpLeft || !pZ->mpRight )\
  530.         \
  531.             pY = pZ;\
  532.         else \
  533.         {\
  534.             pY = pZ->mpRight;\
  535.         \
  536.             while (pY->mpLeft) \
  537.                 \
  538.                 pY = pY->mpLeft;\
  539.         }\
  540.         \
  541.         if ( pY->mpLeft)\
  542.         \
  543.             pX = pY->mpLeft;\
  544.         else\
  545.             pX = pY->mpRight;\
  546.         \
  547.         if ( pX ) pX->mpParent = pY->mpParent;\
  548.         \
  549.         if (pY->mpParent)\
  550.         \
  551.             if (pY == pY->mpParent->mpLeft )\
  552.         \
  553.                 pY->mpParent->mpLeft = pX;\
  554.             else\
  555.                 pY->mpParent->mpRight = pX;\
  556.         else\
  557.             mpRoot = pX;\
  558.         \
  559.         node_ref_type toRemove = 0;\
  560.         \
  561.         if (pY != pZ) {\
  562.         \
  563.             pY->mpLeft = pZ->mpLeft;\
  564.         \
  565.             if (pY->mpLeft) pY->mpLeft->mpParent = pY;\
  566.         \
  567.             pY->mpRight = pZ->mpRight;\
  568.         \
  569.             if ( pY->mpRight ) \
  570.                 \
  571.                 pY->mpRight->mpParent = pY;\
  572.         \
  573.             pY->mpParent = pZ->mpParent;\
  574.         \
  575.             if (pZ->mpParent)\
  576.         \
  577.                 if (pZ == pZ->mpParent->mpLeft)\
  578.         \
  579.                     pZ->mpParent->mpLeft = pY;\
  580.                 else\
  581.                     pZ->mpParent->mpRight = pY;\
  582.             else\
  583.                 mpRoot = pY;\
  584.         \
  585.             toRemove = pZ;\
  586.         } \
  587.         else \
  588.             toRemove = pY;\
  589.         \
  590.         value(toRemove).~actual_value_type();\
  591.         key(toRemove).~actual_value_type();\
  592. \
  593.         RecycleNode( toRemove );\
  594.     }\
  595. \
  596.     _INSERT_METHOD_DEFINITION\
  597. }
  598.  
  599. // do not undefine ___WXSTL_COMMA, where associated containers are defined!
  600. // (it is used as workaround for constraints of C-Preprocessor's nested macros)
  601.  
  602. #define ___WXSTL_COMMA ,
  603.  
  604. #define __DEFINE_MAP(ARG_IS_UNIQUE, KEY_TYPE, VAL_TYPE, FUNCTOR ) \
  605. __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
  606. FUNCTOR,\
  607. __WXSTLMAP_##KEY_TYPE##VAL_TYPE##ARG_IS_UNIQUE, \
  608. struct key_value_pair   { KEY_TYPE first ; \
  609.                           VAL_TYPE second;\
  610.                           key_value_pair() {}\
  611.                           key_value_pair( const KEY_TYPE& key ___WXSTL_COMMA const VAL_TYPE& value ) \
  612.                             : first(key) ___WXSTL_COMMA second( value ) {} \
  613.                          } , \
  614. KEY_TYPE,\
  615. VAL_TYPE,\
  616. mData.first, mData.second, x.first, x.second, \
  617. struct insert_result_iterator\
  618. {\
  619.     iterator first;\
  620.     int      second;\
  621. };\
  622. inline insert_result_iterator insert( const value_type& x )\
  623. {\
  624.     insert_result_iterator result;\
  625. \
  626.     result.first = do_insert(x);\
  627.     result.second  = ( result.first == end() ) ? 0 : 1;\
  628. \
  629.     return result;\
  630. } )
  631.  
  632. #define __DEFINE_SET(ARG_IS_UNIQUE, KEY_TYPE, FUNCTOR ) \
  633. __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
  634. FUNCTOR,\
  635. __WXSTLSET_##TYPE##ARG_IS_UNIQUE, \
  636. KEY_TYPE,\
  637. KEY_TYPE,\
  638. KEY_TYPE,\
  639. mData, mData, x, x, \
  640. struct insert_result_iterator\
  641. {\
  642.     iterator first;\
  643.     int      second;\
  644. };\
  645. inline insert_result_iterator insert( const value_type& x )\
  646. {\
  647.     insert_result_iterator result;\
  648. \
  649.     result.first = do_insert(x);\
  650.     result.second  = ( result.first == end() ) ? 0 : 1;\
  651. \
  652.     return result;\
  653. } )
  654.  
  655. // helper macros to create functor objects for associative containers of the given type
  656.  
  657. #define LESS_THEN_FUNCTOR(TYPE) struct \
  658. { inline int operator()(const TYPE& x, const TYPE& y ) const { return x < y; } }
  659.  
  660. #define GREATER_THEN_FUNCTOR(TYPE) struct \
  661. { inline int operator()(const TYPE& x, const TYPE& y ) const { return x > y; } }
  662.  
  663. // functor argument should be created using the two above macros 
  664. // or passing own class with method "operator()(const TYPE&,cosnt TYPE&)" defined in it
  665.  
  666. #define WXSTL_MAP( KEY_TYPE, VALUE_TYPE, FUNCTOR )      __DEFINE_MAP( 1 ,KEY_TYPE, VALUE_TYPE, FUNCTOR)
  667. #define WXSTL_MULTIMAP( KEY_TYPE, VALUE_TYPE, FUNCTOR ) __DEFINE_MAP( 0 ,KEY_TYPE, VALUE_TYPE, FUNCTOR)
  668. #define WXSTL_SET( KEY_TYPE, FUNCTOR )                  __DEFINE_SET( 1 ,KEY_TYPE, FUNCTOR )
  669. #define WXSTL_MULTISET( KEY_TYPE, FUNCTOR )             __DEFINE_SET( 0 ,KEY_TYPE, FUNCTOR )
  670.  
  671. #endif
  672.