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