utils/HelpGen/src/wxstllst.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 __WXSTLLST_G__
  13 #define __WXSTLLST_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 // VERSION:: 0.2 (copy-constructor/adign-op added)
  28
  29 // FOR NOW:: class-member operators "new" and "delete"
  30 //           are ignored by list class, memory allocated
  31 //           and freed using global operators
  32
  33 typedef int Type;
  34
  35
  36 // the below macro used internally (see actual interface after this macro)
  37
  38 #define __DEFINE_STL_LIST(listClass,Type) class \
  39  listClass \
  40 {\
  41 public:\
  42 \
  43         typedef Type                      value_type;\
  44         typedef value_type*           pointer;\
  45         typedef const value_type* const_pointer;\
  46         typedef value_type&       reference;\
  47         typedef const value_type& const_reference;\
  48         typedef size_t                    size_type;\
  49         typedef ptrdiff_t                 difference_type;\
  50 \
  51 protected:\
  52         struct list_node\
  53         {\
  54                 list_node* mpNext;\
  55                 list_node* mpPrev;\
  56                 value_type mData;\
  57         };\
  58 \
  59         typedef list_node* node_ref_type;\
  60 \
  61         node_ref_type mpFreeListHead;\
  62         node_ref_type mpTerminator;\
  63         size_type     mSize;\
  64 \
  65         inline node_ref_type AllocNode() \
  66         { \
  67                 if ( mpFreeListHead ) \
  68                 {\
  69                         node_ref_type pFreeNode = mpFreeListHead;\
  70                         mpFreeListHead = mpFreeListHead->mpPrev;\
  71 \
  72                         return pFreeNode;\
  73                 }\
  74                 else\
  75                 {\
  76                         char* pHeapBlock = new char[sizeof(list_node)];\
  77 \
  78                         return (node_ref_type)pHeapBlock;\
  79                 }\
  80         }\
  81 \
  82         inline void DestroyFreeList()\
  83         {\
  84                 while ( mpFreeListHead )\
  85                 {\
  86                         node_ref_type tmp = mpFreeListHead;\
  87                         mpFreeListHead = mpFreeListHead->mpPrev;\
  88 \
  89                         delete [](char*)tmp;\
  90                 }\
  91         }\
  92 \
  93         inline void RecycleNode( node_ref_type pNode ) \
  94         {\
  95                 pNode->mpPrev = mpFreeListHead;\
  96                 mpFreeListHead = pNode;\
  97         }\
  98 \
  99 public:\
 100 \
 101         class iterator \
 102         {\
 103         public:\
 104                 node_ref_type mpNode;\
 105                 friend class listClass;\
 106                 friend class const_iterator;\
 107                 friend class const_reverse_iterator;\
 108 \
 109         protected:\
 110                 iterator( node_ref_type pNode )\
 111                 {\
 112                         mpNode = pNode;\
 113                 }\
 114         \
 115         public:\
 116                 iterator() {}\
 117                 int operator==( const iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
 118                 int operator!=( const iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
 119 \
 120                 inline iterator( const iterator& other )\
 121                 {\
 122                         mpNode = other.mpNode;\
 123                 }\
 124 \
 125                 inline const iterator& operator--() \
 126                 {\
 127                         mpNode = mpNode->mpPrev;\
 128                         return *this;\
 129                 }\
 130 \
 131                 inline iterator operator--(int)\
 132                 {\
 133                         iterator tmp = *this;\
 134                         mpNode = mpNode->mpPrev;\
 135                         return tmp;\
 136                 }\
 137 \
 138                 inline const iterator& operator++() \
 139                 {\
 140                         mpNode = mpNode->mpNext;\
 141                         return *this;\
 142                 }\
 143 \
 144                 inline iterator operator++(int)\
 145                 {\
 146                         iterator tmp = *this;\
 147                         mpNode = mpNode->mpNext;\
 148                         return tmp;\
 149                 }\
 150 \
 151                 inline reference operator*()       const { return mpNode->mData; }\
 152         };\
 153 \
 154 \
 155         class const_iterator \
 156         {\
 157         protected:\
 158                 node_ref_type mpNode;\
 159                 friend class listClass;\
 160 \
 161         protected:\
 162                 const_iterator( node_ref_type pNode )\
 163                 {\
 164                         mpNode = pNode;\
 165                 }\
 166         \
 167         public:\
 168                 \
 169                 const_iterator() {}\
 170                 int operator==( const const_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
 171                 int operator!=( const const_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
 172 \
 173 \
 174                 inline const_iterator( const iterator& other )\
 175                 {\
 176                         mpNode = other.mpNode;\
 177                 }\
 178 \
 179                 inline const const_iterator& operator--() \
 180                 {\
 181                         mpNode = mpNode->mpPrev;\
 182                         return *this;\
 183                 }\
 184 \
 185                 inline const_iterator operator--(int)\
 186                 {\
 187                         const_iterator tmp = *this;\
 188                         mpNode = mpNode->mpPrev;\
 189                         return tmp;\
 190                 }\
 191 \
 192                 inline const const_iterator& operator++() \
 193                 {\
 194                         mpNode = mpNode->mpNext;\
 195                         return *this;\
 196                 }\
 197 \
 198                 inline const_iterator operator++(int)\
 199                 {\
 200                         const_iterator tmp = *this;\
 201                         mpNode = mpNode->mpNext;\
 202                         return tmp;\
 203                 }\
 204 \
 205                 inline const_reference operator*() const { return mpNode->mData; }\
 206         };\
 207 \
 208         typedef iterator       OutputIterator;\
 209         typedef const_iterator InputIterator;\
 210 \
 211         class reverse_iterator \
 212         {\
 213         public:\
 214                 node_ref_type mpNode;\
 215                 friend class listClass;\
 216                 friend class const_reverse_iterator;\
 217 \
 218         protected:\
 219                 reverse_iterator ( node_ref_type pNode )\
 220                 {\
 221                         mpNode = pNode;\
 222                 }\
 223         \
 224         public:\
 225 \
 226                 reverse_iterator() {}\
 227                 int operator==( const reverse_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
 228                 int operator!=( const reverse_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
 229 \
 230                 inline reverse_iterator( const reverse_iterator& other )\
 231                 {\
 232                         mpNode = other.mpNode;\
 233                 }\
 234 \
 235                 inline const reverse_iterator& operator--() \
 236                 {\
 237                         mpNode = mpNode->mpNext;\
 238                         return *this;\
 239                 }\
 240 \
 241                 inline reverse_iterator operator--(int)\
 242                 {\
 243                         reverse_iterator tmp = *this;\
 244                         mpNode = mpNode->mpPrev;\
 245                         return tmp;\
 246                 }\
 247 \
 248                 inline const reverse_iterator & operator++() \
 249                 {\
 250                         mpNode = mpNode->mpNext;\
 251                         return *this;\
 252                 }\
 253 \
 254                 inline reverse_iterator  operator++(int)\
 255                 {\
 256                         reverse_iterator tmp = *this;\
 257                         mpNode = mpNode->mpPrev;\
 258                         return tmp;\
 259                 }\
 260 \
 261                 inline const_reference operator*() const { return mpNode->mData; }\
 262         };\
 263 \
 264 \
 265         class const_reverse_iterator \
 266         {\
 267         protected:\
 268                 node_ref_type mpNode;\
 269                 friend class listClass;\
 270 \
 271         protected:\
 272                 const_reverse_iterator( node_ref_type pNode )\
 273                 {\
 274                         mpNode = pNode;\
 275                 }\
 276         \
 277         public:\
 278 \
 279                 const_reverse_iterator() {}\
 280                 int operator==( const const_reverse_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
 281                 int operator!=( const const_reverse_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
 282 \
 283                 inline const_reverse_iterator( const reverse_iterator& other )\
 284                 {\
 285                         mpNode = other.mpNode;\
 286                 }\
 287 \
 288                 inline const const_reverse_iterator& operator--() \
 289                 {\
 290                         mpNode = mpNode->mpNext;\
 291                         return *this;\
 292                 }\
 293 \
 294                 inline const_reverse_iterator operator--(int)\
 295                 {\
 296                         const_reverse_iterator tmp = *this;\
 297                         mpNode = mpNode->mpNext;\
 298                         return tmp;\
 299                 }\
 300 \
 301                 inline const const_reverse_iterator& operator++() \
 302                 {\
 303                         mpNode = mpNode->mpPrev;\
 304                         return *this;\
 305                 }\
 306 \
 307                 inline const_reverse_iterator operator++(int)\
 308                 {\
 309                         const_reverse_iterator tmp = *this;\
 310                         mpNode = mpNode->mpPrev;\
 311                         return tmp;\
 312                 }\
 313 \
 314                 inline const_reference operator*() const { return mpNode->mData; }\
 315         };\
 316 \
 317 public:\
 318 \
 319     inline listClass()\
 320                         : mpFreeListHead( 0 ),\
 321                           mSize(0)\
 322         {\
 323                 mpTerminator = AllocNode();\
 324                 mpTerminator->mpPrev = mpTerminator->mpNext = mpTerminator;\
 325         }\
 326 \
 327         listClass( const listClass& other )\
 328         {\
 329                 mpTerminator = AllocNode();\
 330                 mpTerminator->mpPrev = mpTerminator->mpNext = mpTerminator;\
 331 \
 332                 for( listClass::const_iterator i = other.begin(); i != other.end(); ++i )\
 333 \
 334                         push_back( (*i) );\
 335         }\
 336 \
 337         inline const listClass& operator=( const listClass& rhs ) \
 338         {\
 339                 erase( begin(), end() );\
 340 \
 341                 for( listClass::const_iterator i = rhs.begin(); i != rhs.end(); ++i )\
 342 \
 343                         push_back( (*i) );\
 344 \
 345                 return *this;\
 346         }\
 347 \
 348         inline listClass(const_iterator first, const_iterator last)\
 349                         : mpFreeListHead( 0 ),\
 350                           mSize(0)\
 351         \
 352                 { while( first != last ) push_back( *first++ ); }\
 353 \
 354         inline listClass( size_type n, const value_type& value = value_type() )\
 355         \
 356                 { for( size_t i = 0; i != n; ++n ) push_back( value ); }\
 357 \
 358         inline ~listClass() \
 359         { \
 360                 erase( begin(), end() ); \
 361 \
 362                 RecycleNode( mpTerminator );\
 363                 DestroyFreeList();\
 364         }\
 365 \
 366         inline iterator begin() { return iterator(mpTerminator->mpNext); }\
 367         \
 368         inline const_iterator begin() const \
 369                 { return const_iterator(mpTerminator->mpNext); }\
 370         \
 371         inline iterator end() { return iterator(mpTerminator); }\
 372 \
 373         inline const_iterator end() const { return const_iterator(mpTerminator); }\
 374 \
 375         inline reverse_iterator rbegin() \
 376                 { return reverse_iterator(mpTerminator->mpPrev); }\
 377 \
 378         inline reverse_iterator rend() \
 379                 { return reverse_iterator(mpTerminator); }\
 380 \
 381         inline const_reverse_iterator rbegin() const\
 382                 { return const_reverse_iterator(mpTerminator->mpPrev); }\
 383 \
 384         inline const_reverse_iterator  rend() const\
 385                 { return const_reverse_iterator(mpTerminator); }\
 386 \
 387         inline int empty() const { return (mSize == 0); }\
 388 \
 389         inline size_type size() const { return mSize; }\
 390 \
 391         inline size_type max_size() const { return UINT_MAX/sizeof(list_node); }\
 392 \
 393         inline reference front() { return mpTerminator->mData; }\
 394 \
 395         inline const_reference front() const { return mpTerminator->mData; }\
 396 \
 397         inline reference back() { return mpTerminator->mpPrev->mData; }\
 398 \
 399         inline const_reference back() const { return mpTerminator->mpPrev->mData; }\
 400 \
 401         inline void push_front(const value_type& x) { insert( begin(), x ); }\
 402 \
 403         inline void push_back(const value_type& x) { insert( end(), x ); }\
 404 \
 405         iterator insert(iterator position, const value_type& x = value_type())\
 406         {\
 407                 node_ref_type pNew = AllocNode();\
 408 \
 409                 node_ref_type pos = *((node_ref_type*)&position);\
 410 \
 411                 pNew->mpNext = pos;\
 412                 pNew->mpPrev = pos->mpPrev;\
 413                 pos->mpPrev->mpNext = pNew;\
 414                 pos->mpPrev  = pNew;\
 415 \
 416                 new (&pNew->mData) value_type(x);\
 417 \
 418                 ++mSize;\
 419 \
 420                 return iterator(pNew);\
 421         }\
 422 \
 423         inline void insert(iterator position, const_iterator first, const_iterator last )\
 424         {\
 425                 while( first != last ) insert( position, *first++ );\
 426         }\
 427 \
 428         inline void splice( iterator position, listClass& other )\
 429         {\
 430                 if ( other.begin() == other.end() ) return;\
 431 \
 432                 node_ref_type pTill = other.mpTerminator->mpPrev;\
 433                 node_ref_type pFrom = other.begin().mpNode;\
 434 \
 435                 mpTerminator->mpPrev->mpNext = pFrom;\
 436                 pFrom->mpPrev = mpTerminator->mpPrev->mpNext;\
 437 \
 438                 pTill->mpNext = mpTerminator;\
 439                 mpTerminator->mpPrev = pTill;\
 440 \
 441                 other.mpTerminator->mpNext = \
 442                         other.mpTerminator->mpPrev = other.mpTerminator;\
 443 \
 444                 mSize += other.mSize;\
 445                 other.mSize = 0;\
 446         }\
 447 \
 448         inline void splice( iterator position, listClass& other, iterator first, iterator last )\
 449         {\
 450                 if ( first == last ) return;\
 451 \
 452                 size_type sz = 0;\
 453                 iterator tmp = first;\
 454                 while( tmp != last ) \
 455                 {\
 456                         ++tmp;\
 457                         ++sz;\
 458                 }\
 459 \
 460                 mSize += sz;\
 461                 other.mSize -= sz;\
 462 \
 463                 node_ref_type pPos   = position.mpNode;\
 464                 node_ref_type pFirst = first.mpNode;\
 465                 node_ref_type pLast  = last.mpNode;\
 466                 node_ref_type pTill  = last.mpNode->mpPrev;\
 467 \
 468                 pPos->mpPrev->mpNext = pFirst;\
 469                 pPos->mpPrev = pTill;\
 470 \
 471                 pFirst->mpPrev->mpNext = last.mpNode;\
 472                 pLast->mpPrev = pTill;\
 473 \
 474                 pFirst->mpPrev = pPos->mpPrev;\
 475                 pTill->mpNext = pPos;\
 476         }\
 477 \
 478         inline void pop_front() { erase( begin() ); }\
 479         inline void pop_back()  { erase( --end() );   }\
 480         \
 481         inline void erase(iterator position)\
 482         {\
 483                 erase( position, ++position );\
 484         }\
 485         \
 486         inline void erase(iterator first, iterator last)\
 487         {\
 488                 node_ref_type firstNode = *((node_ref_type*)&first);\
 489                 node_ref_type lastNode = *((node_ref_type*)&last);\
 490 \
 491                 firstNode->mpPrev->mpNext = lastNode;\
 492                 lastNode->mpPrev = firstNode->mpPrev;\
 493 \
 494                 while( firstNode != lastNode )\
 495                 {\
 496                         node_ref_type next = firstNode->mpNext;\
 497 \
 498                         typedef value_type value_type_local;\
 499                         firstNode->mData.value_type_local::~value_type_local();\
 500 \
 501                         RecycleNode( firstNode );\
 502 \
 503                         firstNode = next;\
 504 \
 505                         --mSize;\
 506                 }\
 507         }\
 508 \
 509         inline void remove(const value_type& value)\
 510         {\
 511                 for( iterator i = begin(); i != end(); ++i )\
 512                 \
 513                         if ( (*i) == value ) \
 514                         {\
 515                                 erase( i ); break;\
 516                         }\
 517         }\
 518 \
 519         void sort()\
 520         {\
 521                 if ( mSize < 2 ) return;\
 522 \
 523                 iterator from = begin();\
 524                 iterator other_end = end();\
 525                 --other_end;\
 526 \
 527                 for( size_type i = 0; i != mSize; ++i )\
 528                 {\
 529                         size_type nSwaps = 0;\
 530 \
 531                         iterator next = begin();\
 532                         ++next;\
 533 \
 534                         for( iterator j = begin(); j != other_end;  ++j )\
 535                         {\
 536 \
 537                                 if ( (*next) < (*j) )\
 538                                 {\
 539                                         value_type tmp = (*j);\
 540                                         (*j) = (*next);\
 541                                         (*next) = tmp;\
 542 \
 543                                         ++nSwaps;\
 544                                 }\
 545 \
 546                                 ++next;\
 547                         }\
 548 \
 549                         if ( !nSwaps) break;\
 550 \
 551                         --other_end;\
 552                 }\
 553         }\
 554 }
 555
 556 // defines list class with the given element type
 557 #define WXSTL_LIST(ELEMENT_CLASS)  __DEFINE_STL_LIST(\
 558 \
 559 _WXSTL_LIST_##ELEMENT_CLASS, ELEMENT_CLASS )
 560
 561 #endif