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