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