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