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*  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