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: wxstllst.h 34519 2005-06-02 09:44:45Z ABX $ 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/assign-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 33typedef 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{\ 41public:\ 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\ 51protected:\ 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 m_Size;\ 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\ 99public:\ 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\ 317public:\ 318\ 319 inline listClass()\ 320 : mpFreeListHead( 0 ),\ 321 m_Size(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 m_Size(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 (m_Size == 0); }\ 388\ 389 inline size_type size() const { return m_Size; }\ 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 ++m_Size;\ 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 m_Size += other.m_Size;\ 445 other.m_Size = 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 m_Size += sz;\ 461 other.m_Size -= 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 --m_Size;\ 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 ( m_Size < 2 ) return;\ 522\ 523 iterator from = begin();\ 524 iterator other_end = end();\ 525 --other_end;\ 526\ 527 for( size_type i = 0; i != m_Size; ++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 562