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