| 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 |