utils/HelpGen/src/wxstlac.h

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