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 / wxstllst.h < prev    next >
C/C++ Source or Header  |  2001-11-19  |  13KB  |  562 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: wxstllst.h,v 1.2 2001/11/18 12:25:12 GD Exp $
  8. // Copyright:   (c) Aleskandars Gluchovas
  9. // Licence:       wxWindows licence
  10. /////////////////////////////////////////////////////////////////////////////
  11.  
  12. #ifndef __WXSTLLST_G__
  13. #define __WXSTLLST_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. // VERSION:: 0.2 (copy-constructor/adign-op added)
  28.  
  29. // FOR NOW:: class-member operators "new" and "delete"
  30. //           are ignored by list class, memory allocated 
  31. //           and freed using global operators
  32.  
  33. typedef int Type;
  34.  
  35.  
  36. // the below macro used internally (see actual interface after this macro)
  37.  
  38. #define __DEFINE_STL_LIST(listClass,Type) class \
  39.  listClass \
  40. {\
  41. public:\
  42. \
  43.     typedef Type              value_type;\
  44.     typedef value_type*          pointer;\
  45.     typedef const value_type* const_pointer;\
  46.     typedef value_type&       reference;\
  47.     typedef const value_type& const_reference;\
  48.     typedef size_t              size_type;\
  49.     typedef ptrdiff_t          difference_type;\
  50. \
  51. protected:\
  52.     struct list_node\
  53.     {\
  54.         list_node* mpNext;\
  55.         list_node* mpPrev;\
  56.         value_type mData;\
  57.     };\
  58. \
  59.     typedef list_node* node_ref_type;\
  60. \
  61.     node_ref_type mpFreeListHead;\
  62.     node_ref_type mpTerminator;\
  63.     size_type     mSize;\
  64. \
  65.     inline node_ref_type AllocNode() \
  66.     { \
  67.         if ( mpFreeListHead ) \
  68.         {\
  69.             node_ref_type pFreeNode = mpFreeListHead;\
  70.             mpFreeListHead = mpFreeListHead->mpPrev;\
  71. \
  72.             return pFreeNode;\
  73.         }\
  74.         else\
  75.         {\
  76.             char* pHeapBlock = new char[sizeof(list_node)];\
  77. \
  78.             return (node_ref_type)pHeapBlock;\
  79.         }\
  80.     }\
  81. \
  82.     inline void DestroyFreeList()\
  83.     {\
  84.         while ( mpFreeListHead )\
  85.         {\
  86.             node_ref_type tmp = mpFreeListHead;\
  87.             mpFreeListHead = mpFreeListHead->mpPrev;\
  88. \
  89.             delete [](char*)tmp;\
  90.         }\
  91.     }\
  92. \
  93.     inline void RecycleNode( node_ref_type pNode ) \
  94.     {\
  95.         pNode->mpPrev = mpFreeListHead;\
  96.         mpFreeListHead = pNode;\
  97.     }\
  98. \
  99. public:\
  100. \
  101.     class iterator \
  102.     {\
  103.     public:\
  104.         node_ref_type mpNode;\
  105.         friend class listClass;\
  106.         friend class const_iterator;\
  107.         friend class const_reverse_iterator;\
  108. \
  109.     protected:\
  110.         iterator( node_ref_type pNode )\
  111.         {\
  112.             mpNode = pNode;\
  113.         }\
  114.     \
  115.     public:\
  116.         iterator() {}\
  117.         int operator==( const iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
  118.         int operator!=( const iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
  119. \
  120.         inline iterator( const iterator& other )\
  121.         {\
  122.             mpNode = other.mpNode;\
  123.         }\
  124. \
  125.         inline const iterator& operator--() \
  126.         {\
  127.             mpNode = mpNode->mpPrev;\
  128.             return *this;\
  129.         }\
  130. \
  131.         inline iterator operator--(int)\
  132.         {\
  133.             iterator tmp = *this;\
  134.             mpNode = mpNode->mpPrev;\
  135.             return tmp;\
  136.         }\
  137. \
  138.         inline const iterator& operator++() \
  139.         {\
  140.             mpNode = mpNode->mpNext;\
  141.             return *this;\
  142.         }\
  143. \
  144.         inline iterator operator++(int)\
  145.         {\
  146.             iterator tmp = *this;\
  147.             mpNode = mpNode->mpNext;\
  148.             return tmp;\
  149.         }\
  150. \
  151.         inline reference operator*()       const { return mpNode->mData; }\
  152.     };\
  153. \
  154. \
  155.     class const_iterator \
  156.     {\
  157.     protected:\
  158.         node_ref_type mpNode;\
  159.         friend class listClass;\
  160. \
  161.     protected:\
  162.         const_iterator( node_ref_type pNode )\
  163.         {\
  164.             mpNode = pNode;\
  165.         }\
  166.     \
  167.     public:\
  168.         \
  169.         const_iterator() {}\
  170.         int operator==( const const_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
  171.         int operator!=( const const_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
  172. \
  173. \
  174.         inline const_iterator( const iterator& other )\
  175.         {\
  176.             mpNode = other.mpNode;\
  177.         }\
  178. \
  179.         inline const const_iterator& operator--() \
  180.         {\
  181.             mpNode = mpNode->mpPrev;\
  182.             return *this;\
  183.         }\
  184. \
  185.         inline const_iterator operator--(int)\
  186.         {\
  187.             const_iterator tmp = *this;\
  188.             mpNode = mpNode->mpPrev;\
  189.             return tmp;\
  190.         }\
  191. \
  192.         inline const const_iterator& operator++() \
  193.         {\
  194.             mpNode = mpNode->mpNext;\
  195.             return *this;\
  196.         }\
  197. \
  198.         inline const_iterator operator++(int)\
  199.         {\
  200.             const_iterator tmp = *this;\
  201.             mpNode = mpNode->mpNext;\
  202.             return tmp;\
  203.         }\
  204. \
  205.         inline const_reference operator*() const { return mpNode->mData; }\
  206.     };\
  207. \
  208.     typedef iterator       OutputIterator;\
  209.     typedef const_iterator InputIterator;\
  210. \
  211.     class reverse_iterator \
  212.     {\
  213.     public:\
  214.         node_ref_type mpNode;\
  215.         friend class listClass;\
  216.         friend class const_reverse_iterator;\
  217. \
  218.     protected:\
  219.         reverse_iterator ( node_ref_type pNode )\
  220.         {\
  221.             mpNode = pNode;\
  222.         }\
  223.     \
  224.     public:\
  225. \
  226.         reverse_iterator() {}\
  227.         int operator==( const reverse_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
  228.         int operator!=( const reverse_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
  229. \
  230.         inline reverse_iterator( const reverse_iterator& other )\
  231.         {\
  232.             mpNode = other.mpNode;\
  233.         }\
  234. \
  235.         inline const reverse_iterator& operator--() \
  236.         {\
  237.             mpNode = mpNode->mpNext;\
  238.             return *this;\
  239.         }\
  240. \
  241.         inline reverse_iterator operator--(int)\
  242.         {\
  243.             reverse_iterator tmp = *this;\
  244.             mpNode = mpNode->mpPrev;\
  245.             return tmp;\
  246.         }\
  247. \
  248.         inline const reverse_iterator & operator++() \
  249.         {\
  250.             mpNode = mpNode->mpNext;\
  251.             return *this;\
  252.         }\
  253. \
  254.         inline reverse_iterator  operator++(int)\
  255.         {\
  256.             reverse_iterator tmp = *this;\
  257.             mpNode = mpNode->mpPrev;\
  258.             return tmp;\
  259.         }\
  260. \
  261.         inline const_reference operator*() const { return mpNode->mData; }\
  262.     };\
  263. \
  264. \
  265.     class const_reverse_iterator \
  266.     {\
  267.     protected:\
  268.         node_ref_type mpNode;\
  269.         friend class listClass;\
  270. \
  271.     protected:\
  272.         const_reverse_iterator( node_ref_type pNode )\
  273.         {\
  274.             mpNode = pNode;\
  275.         }\
  276.     \
  277.     public:\
  278. \
  279.         const_reverse_iterator() {}\
  280.         int operator==( const const_reverse_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
  281.         int operator!=( const const_reverse_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
  282. \
  283.         inline const_reverse_iterator( const reverse_iterator& other )\
  284.         {\
  285.             mpNode = other.mpNode;\
  286.         }\
  287. \
  288.         inline const const_reverse_iterator& operator--() \
  289.         {\
  290.             mpNode = mpNode->mpNext;\
  291.             return *this;\
  292.         }\
  293. \
  294.         inline const_reverse_iterator operator--(int)\
  295.         {\
  296.             const_reverse_iterator tmp = *this;\
  297.             mpNode = mpNode->mpNext;\
  298.             return tmp;\
  299.         }\
  300. \
  301.         inline const const_reverse_iterator& operator++() \
  302.         {\
  303.             mpNode = mpNode->mpPrev;\
  304.             return *this;\
  305.         }\
  306. \
  307.         inline const_reverse_iterator operator++(int)\
  308.         {\
  309.             const_reverse_iterator tmp = *this;\
  310.             mpNode = mpNode->mpPrev;\
  311.             return tmp;\
  312.         }\
  313. \
  314.         inline const_reference operator*() const { return mpNode->mData; }\
  315.     };\
  316. \
  317. public:\
  318. \
  319.     inline listClass()\
  320.             : mpFreeListHead( 0 ),\
  321.               mSize(0)\
  322.     {\
  323.         mpTerminator = AllocNode();\
  324.         mpTerminator->mpPrev = mpTerminator->mpNext = mpTerminator;\
  325.     }\
  326. \
  327.     listClass( const listClass& other )\
  328.     {\
  329.         mpTerminator = AllocNode();\
  330.         mpTerminator->mpPrev = mpTerminator->mpNext = mpTerminator;\
  331. \
  332.         for( listClass::const_iterator i = other.begin(); i != other.end(); ++i )\
  333. \
  334.             push_back( (*i) );\
  335.     }\
  336. \
  337.     inline const listClass& operator=( const listClass& rhs ) \
  338.     {\
  339.         erase( begin(), end() );\
  340. \
  341.         for( listClass::const_iterator i = rhs.begin(); i != rhs.end(); ++i )\
  342. \
  343.             push_back( (*i) );\
  344. \
  345.         return *this;\
  346.     }\
  347. \
  348.     inline listClass(const_iterator first, const_iterator last)\
  349.             : mpFreeListHead( 0 ),\
  350.               mSize(0)\
  351.     \
  352.         { while( first != last ) push_back( *first++ ); }\
  353. \
  354.     inline listClass( size_type n, const value_type& value = value_type() )\
  355.     \
  356.         { for( size_t i = 0; i != n; ++n ) push_back( value ); }\
  357. \
  358.     inline ~listClass() \
  359.     { \
  360.         erase( begin(), end() ); \
  361. \
  362.         RecycleNode( mpTerminator );\
  363.         DestroyFreeList();\
  364.     }\
  365. \
  366.     inline iterator begin() { return iterator(mpTerminator->mpNext); }\
  367.     \
  368.     inline const_iterator begin() const \
  369.         { return const_iterator(mpTerminator->mpNext); }\
  370.     \
  371.     inline iterator end() { return iterator(mpTerminator); }\
  372. \
  373.     inline const_iterator end() const { return const_iterator(mpTerminator); }\
  374. \
  375.     inline reverse_iterator rbegin() \
  376.         { return reverse_iterator(mpTerminator->mpPrev); }\
  377. \
  378.     inline reverse_iterator rend() \
  379.         { return reverse_iterator(mpTerminator); }\
  380. \
  381.     inline const_reverse_iterator rbegin() const\
  382.         { return const_reverse_iterator(mpTerminator->mpPrev); }\
  383. \
  384.     inline const_reverse_iterator  rend() const\
  385.         { return const_reverse_iterator(mpTerminator); }\
  386. \
  387.     inline int empty() const { return (mSize == 0); }\
  388. \
  389.     inline size_type size() const { return mSize; }\
  390. \
  391.     inline size_type max_size() const { return UINT_MAX/sizeof(list_node); }\
  392. \
  393.     inline reference front() { return mpTerminator->mData; }\
  394. \
  395.     inline const_reference front() const { return mpTerminator->mData; }\
  396. \
  397.     inline reference back() { return mpTerminator->mpPrev->mData; }\
  398. \
  399.     inline const_reference back() const { return mpTerminator->mpPrev->mData; }\
  400. \
  401.     inline void push_front(const value_type& x) { insert( begin(), x ); }\
  402. \
  403.     inline void push_back(const value_type& x) { insert( end(), x ); }\
  404. \
  405.     iterator insert(iterator position, const value_type& x = value_type())\
  406.     {\
  407.         node_ref_type pNew = AllocNode();\
  408. \
  409.         node_ref_type pos = *((node_ref_type*)&position);\
  410. \
  411.         pNew->mpNext = pos;\
  412.         pNew->mpPrev = pos->mpPrev;\
  413.         pos->mpPrev->mpNext = pNew;\
  414.         pos->mpPrev  = pNew;\
  415. \
  416.         new (&pNew->mData) value_type(x);\
  417. \
  418.         ++mSize;\
  419. \
  420.         return iterator(pNew);\
  421.     }\
  422. \
  423.     inline void insert(iterator position, const_iterator first, const_iterator last )\
  424.     {\
  425.         while( first != last ) insert( position, *first++ );\
  426.     }\
  427. \
  428.     inline void splice( iterator position, listClass& other )\
  429.     {\
  430.         if ( other.begin() == other.end() ) return;\
  431. \
  432.         node_ref_type pTill = other.mpTerminator->mpPrev;\
  433.         node_ref_type pFrom = other.begin().mpNode;\
  434. \
  435.         mpTerminator->mpPrev->mpNext = pFrom;\
  436.         pFrom->mpPrev = mpTerminator->mpPrev->mpNext;\
  437. \
  438.         pTill->mpNext = mpTerminator;\
  439.         mpTerminator->mpPrev = pTill;\
  440. \
  441.         other.mpTerminator->mpNext = \
  442.             other.mpTerminator->mpPrev = other.mpTerminator;\
  443. \
  444.         mSize += other.mSize;\
  445.         other.mSize = 0;\
  446.     }\
  447. \
  448.     inline void splice( iterator position, listClass& other, iterator first, iterator last )\
  449.     {\
  450.         if ( first == last ) return;\
  451. \
  452.         size_type sz = 0;\
  453.         iterator tmp = first;\
  454.         while( tmp != last ) \
  455.         {\
  456.             ++tmp;\
  457.             ++sz;\
  458.         }\
  459. \
  460.         mSize += sz;\
  461.         other.mSize -= sz;\
  462. \
  463.         node_ref_type pPos   = position.mpNode;\
  464.         node_ref_type pFirst = first.mpNode;\
  465.         node_ref_type pLast  = last.mpNode;\
  466.         node_ref_type pTill  = last.mpNode->mpPrev;\
  467. \
  468.         pPos->mpPrev->mpNext = pFirst;\
  469.         pPos->mpPrev = pTill;\
  470. \
  471.         pFirst->mpPrev->mpNext = last.mpNode;\
  472.         pLast->mpPrev = pTill;\
  473. \
  474.         pFirst->mpPrev = pPos->mpPrev;\
  475.         pTill->mpNext = pPos;\
  476.     }\
  477. \
  478.     inline void pop_front() { erase( begin() ); }\
  479.     inline void pop_back()  { erase( --end() );   }\
  480.     \
  481.     inline void erase(iterator position)\
  482.     {\
  483.         erase( position, ++position );\
  484.     }\
  485.     \
  486.     inline void erase(iterator first, iterator last)\
  487.     {\
  488.         node_ref_type firstNode = *((node_ref_type*)&first);\
  489.         node_ref_type lastNode = *((node_ref_type*)&last);\
  490. \
  491.         firstNode->mpPrev->mpNext = lastNode;\
  492.         lastNode->mpPrev = firstNode->mpPrev;\
  493. \
  494.         while( firstNode != lastNode )\
  495.         {\
  496.             node_ref_type next = firstNode->mpNext;\
  497. \
  498.             typedef value_type value_type_local;\
  499.             firstNode->mData.value_type_local::~value_type_local();\
  500. \
  501.             RecycleNode( firstNode );\
  502. \
  503.             firstNode = next;\
  504. \
  505.             --mSize;\
  506.         }\
  507.     }\
  508. \
  509.     inline void remove(const value_type& value)\
  510.     {\
  511.         for( iterator i = begin(); i != end(); ++i )\
  512.         \
  513.             if ( (*i) == value ) \
  514.             {\
  515.                 erase( i ); break;\
  516.             }\
  517.     }\
  518. \
  519.     void sort()\
  520.     {\
  521.         if ( mSize < 2 ) return;\
  522. \
  523.         iterator from = begin();\
  524.         iterator other_end = end();\
  525.         --other_end;\
  526. \
  527.         for( size_type i = 0; i != mSize; ++i )\
  528.         {\
  529.             size_type nSwaps = 0;\
  530. \
  531.             iterator next = begin();\
  532.             ++next;\
  533. \
  534.             for( iterator j = begin(); j != other_end;  ++j )\
  535.             {\
  536. \
  537.                 if ( (*next) < (*j) )\
  538.                 {\
  539.                     value_type tmp = (*j);\
  540.                     (*j) = (*next);\
  541.                     (*next) = tmp;\
  542. \
  543.                     ++nSwaps;\
  544.                 }\
  545. \
  546.                 ++next;\
  547.             }\
  548. \
  549.             if ( !nSwaps) break;\
  550. \
  551.             --other_end;\
  552.         }\
  553.     }\
  554. }
  555.  
  556. // defines list class with the given element type
  557. #define WXSTL_LIST(ELEMENT_CLASS)  __DEFINE_STL_LIST(\
  558. \
  559. _WXSTL_LIST_##ELEMENT_CLASS, ELEMENT_CLASS )
  560.  
  561. #endif
  562.