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: wxstlvec.h 28244 2004-07-15 06:27:13Z ABX $ 8// Copyright: (c) Aleskandars Gluchovas 9// Licence: wxWindows licence 10///////////////////////////////////////////////////////////////////////////// 11 12#ifndef __WXSTLVEC_G__ 13#define __WXSTLVEC_G__ 14 15#ifdef new 16#undef new 17#endif 18 19#include <memory.h> 20#include <string.h> // imports memmove() 21#include <stddef.h> 22#if !defined(__WXMAC__) || defined(__DARWIN__) 23# include <sys/types.h> 24#endif 25#include <limits.h> 26#include <new> 27 28// the below macro used internally (see actual interface after this macro) 29 30#define __DEFINE_STL_VECTOR_DEEP( vectorClass, Type ) class vectorClass {\ 31\ 32public:\ 33 typedef Type value_type;\ 34 typedef value_type* iterator;\ 35 typedef const value_type* const_iterator;\ 36 typedef iterator pointer;\ 37 typedef const iterator const_pointer;\ 38 typedef value_type& reference;\ 39 typedef const value_type& const_reference;\ 40 typedef size_t size_type;\ 41 typedef ptrdiff_t difference_type;\ 42\ 43 typedef iterator OutputIterator;\ 44 typedef const_iterator InputIterator;\ 45\ 46protected:\ 47\ 48 inline void PlacementCopy( const_iterator first, const_iterator last, iterator result )\ 49 {\ 50 while ( first != last ) \ 51 new (result++) value_type(*first++);\ 52 }\ 53\ 54 inline void ConstructObjects( iterator first, iterator last, const value_type& pattern )\ 55 {\ 56 while( first != last ) \ 57 new (first++) value_type(pattern);\ 58 }\ 59\ 60 inline void CopyObjects( iterator first, iterator last, iterator result )\ 61 {\ 62 while( first != last ) \ 63 *result++ = *first++;\ 64 }\ 65\ 66 inline void CopyObjectsBack( iterator first, iterator last, iterator result )\ 67 {\ 68 result += difference_type(last,first);\ 69\ 70 while( first != last ) \ 71 *(--result) = *(--last);\ 72 }\ 73\ 74public:\ 75\ 76 class reverse_iterator \ 77 {\ 78 friend class vectorClass;\ 79 friend class const_reverse_iterator;\ 80\ 81 public:\ 82 iterator mpPos;\ 83\ 84 public:\ 85\ 86 reverse_iterator() {}\ 87\ 88 reverse_iterator ( iterator pPos )\ 89 {\ 90 mpPos = pPos;\ 91 }\ 92 \ 93 int operator==( const reverse_iterator& rhs ) const { return (mpPos == rhs.mpPos); }\ 94 int operator!=( const reverse_iterator& rhs ) const { return (mpPos != rhs.mpPos); }\ 95\ 96 inline reverse_iterator( const reverse_iterator& other )\ 97 {\ 98 mpPos = other.mpPos;\ 99 }\ 100\ 101 inline const reverse_iterator& operator--() \ 102 {\ 103 --mpPos;\ 104 return *this;\ 105 }\ 106\ 107 inline reverse_iterator operator--(int)\ 108 {\ 109 reverse_iterator tmp = *this;\ 110 --mpPos;\ 111 return tmp;\ 112 }\ 113\ 114 inline const reverse_iterator & operator++() \ 115 {\ 116 ++mpPos;\ 117 return *this;\ 118 }\ 119\ 120 inline reverse_iterator operator++(int)\ 121 {\ 122 reverse_iterator tmp = *this;\ 123 ++mpPos;\ 124 return tmp;\ 125 }\ 126\ 127 inline const_reference operator*() const { return *mpPos; }\ 128 };\ 129\ 130\ 131 class const_reverse_iterator \ 132 {\ 133 protected:\ 134 iterator mpPos;\ 135 public:\ 136\ 137 const_reverse_iterator() {}\ 138\ 139 const_reverse_iterator( const iterator pPos )\ 140 {\ 141 mpPos = pPos;\ 142 }\ 143 \ 144 int operator==( const const_reverse_iterator& rhs ) const { return (mpPos == rhs.mpPos); }\ 145 int operator!=( const const_reverse_iterator& rhs ) const { return (mpPos != rhs.mpPos); }\ 146\ 147 inline const_reverse_iterator( const reverse_iterator& other )\ 148 {\ 149 mpPos = other.mpPos;\ 150 }\ 151\ 152 inline const const_reverse_iterator& operator--() \ 153 {\ 154 --mpPos;\ 155 return *this;\ 156 }\ 157\ 158 inline const_reverse_iterator operator--(int)\ 159 {\ 160 const_reverse_iterator tmp = *this;\ 161 --mpPos;\ 162 return tmp;\ 163 }\ 164\ 165 inline const const_reverse_iterator & operator++() \ 166 {\ 167 ++mpPos;\ 168 return *this;\ 169 }\ 170\ 171 inline const_reverse_iterator operator++(int)\ 172 {\ 173 const_reverse_iterator tmp = *this;\ 174 ++mpPos;\ 175 return tmp;\ 176 }\ 177\ 178 inline const_reference operator*() const { return *mpPos; }\ 179 };\ 180\ 181protected:\ 182 \ 183 pointer mpStart;\ 184 pointer mpEnd;\ 185 pointer mpEndOfBuf;\ 186\ 187protected:\ 188\ 189 inline void quick_sort(int WXUNUSED(low), int WXUNUSED(hi)) \ 190 {\ 191 }\ 192\ 193 inline void DestructRange( iterator first, iterator last )\ 194 {\ 195 typedef value_type value_type_local;\ 196\ 197 while ( first != last ) \ 198 {\ 199 first->value_type_local::~value_type_local();\ 200 ++first;\ 201 }\ 202 }\ 203\ 204 inline iterator DoInsert(iterator position, const value_type& x)\ 205 {\ 206 if ( mpEnd < mpEndOfBuf )\ 207 {\ 208 new (mpEnd) value_type(*(mpEnd-1) );\ 209 \ 210 CopyObjectsBack( position, mpEnd, position + 1 );\ 211 \ 212 *position = x;\ 213 \ 214 ++mpEnd;\ 215 \ 216 return position;\ 217 }\ 218 \ 219 size_type minBufLen = WXSTL_VECTOR_MIN_BUF_SIZE/sizeof(value_type);\ 220 \ 221 size_type doubledSize = size()*2;\ 222 \ 223 size_type newLen = ( doubledSize < minBufLen ) ? minBufLen : doubledSize;\ 224 \ 225 iterator pNewStart = (iterator)( new char[newLen*sizeof(value_type)] );\ 226 \ 227 PlacementCopy( mpStart, position, pNewStart );\ 228 \ 229 iterator atPosition = pNewStart + difference_type( position - mpStart );\ 230 \ 231 new (atPosition) value_type(x);\ 232 \ 233 iterator newPos = atPosition;\ 234 \ 235 ++atPosition;\ 236 \ 237 if ( mpStart ) \ 238 {\ 239 PlacementCopy( position, mpEnd, atPosition );\ 240 DestructRange( mpStart, mpEnd );\ 241 delete [](char*)mpStart;\ 242 }\ 243 \ 244 mpEnd = atPosition + difference_type( mpEnd - position );\ 245 \ 246 mpStart = pNewStart;\ 247 mpEndOfBuf = pNewStart + newLen;\ 248 \ 249 return newPos;\ 250 }\ 251\ 252public:\ 253\ 254 inline vectorClass() : mpStart(0), \ 255 mpEnd(0),\ 256 mpEndOfBuf(0)\ 257 {}\ 258\ 259 inline vectorClass( const_iterator first, const_iterator last )\ 260 : mpStart(0),\ 261 mpEnd(0),\ 262 mpEndOfBuf(0)\ 263 \ 264 { while( first != last ) push_back( *first++ ); }\ 265\ 266 inline vectorClass( size_type n, const value_type& value = value_type() )\ 267 : mpStart(0),\ 268 mpEnd(0),\ 269 mpEndOfBuf(0)\ 270 \ 271 { for( size_type i = 0; i != n; ++i ) push_back( value ); }\ 272\ 273 inline const vectorClass& operator=( const vectorClass& other )\ 274 {\ 275 if (mpStart) \ 276 {\ 277 DestructRange( begin(), end() );\ 278 delete [](char*)mpStart; \ 279 }\ 280\ 281 size_t newLen = difference_type( other.mpEndOfBuf - other.mpStart );\ 282\ 283 mpStart = (iterator)( new char[newLen*sizeof(value_type)] );\ 284\ 285 PlacementCopy( other.begin(), other.end(), mpStart );\ 286\ 287 mpEnd = mpStart + other.size();\ 288\ 289 mpEndOfBuf = mpStart + newLen;\ 290\ 291 return *this;\ 292 }\ 293\ 294 inline vectorClass( const vectorClass& other )\ 295 : mpStart(0),\ 296 mpEnd(0),\ 297 mpEndOfBuf(0)\ 298 {\ 299 this->operator=( other );\ 300 }\ 301\ 302 inline ~vectorClass() \ 303 { \ 304 if (mpStart) \ 305 {\ 306 DestructRange( begin(), end() );\ 307 delete [](char*)mpStart; \ 308 }\ 309 }\ 310\ 311 inline iterator begin() { return mpStart; }\ 312\ 313 inline const_iterator begin() const { return mpStart; }\ 314\ 315 inline iterator end() { return mpEnd; }\ 316\ 317 inline const_iterator end() const { return mpEnd; }\ 318\ 319 inline size_type size() const { return (size_type)difference_type(mpEnd-mpStart); }\ 320\ 321 inline size_type max_size() const { return UINT_MAX/sizeof(value_type); }\ 322\ 323 inline size_type capacity() const \ 324 { return difference_type(mpEndOfBuf-mpStart)/sizeof(value_type); }\ 325\ 326 inline int empty() const { return mpStart == mpEnd; }\ 327\ 328 inline reference operator[](size_type n) { return *(mpStart+n); }\ 329\ 330 inline const_reference operator[](size_type n) const { return *(mpStart+n); }\ 331\ 332 inline reference front() { return (*mpStart); }\ 333 \ 334 inline const_reference front() const { return (*mpStart); }\ 335\ 336 inline reference back() { return (*(mpEnd-1)); }\ 337\ 338 inline const_reference back() const { return (*(mpEnd-1)); }\ 339\ 340 inline void reserve(size_type WXUNUSED(n)) {}\ 341\ 342 inline void push_back(const value_type& x)\ 343 {\ 344 if ( mpEnd != mpEndOfBuf ) \ 345 {\ 346 new (mpEnd) value_type(x);\ 347 ++mpEnd;\ 348 }\ 349 else\ 350 DoInsert( mpEnd, x );\ 351 }\ 352\ 353 inline iterator insert(iterator position, const value_type& x = value_type())\ 354 {\ 355 if ( position == mpEnd && mpEnd != mpEndOfBuf )\ 356 {\ 357 new (mpEnd) value_type(x);\ 358 ++mpEnd;\ 359 return (mpEnd-1);\ 360 }\ 361 else return DoInsert( position, x );\ 362 }\ 363\ 364 inline void pop_back()\ 365 {\ 366 DestructRange( mpEnd-1, mpEnd );\ 367\ 368 --mpEnd;\ 369 }\ 370\ 371 inline void erase(iterator first, iterator last)\ 372 {\ 373 if ( last == mpEnd )\ 374 {\ 375 DestructRange( first, last );\ 376 mpEnd = first;\ 377 return;\ 378 }\ 379 \ 380 CopyObjects( last, last + difference_type( mpEnd - last ), first );\ 381 \ 382 iterator newEnd = mpEnd - difference_type( last - first );\ 383 DestructRange( newEnd, mpEnd );\ 384 \ 385 mpEnd = newEnd;\ 386 }\ 387\ 388 inline void erase( iterator position )\ 389 {\ 390 erase( position, position + 1 );\ 391 }\ 392\ 393 inline void sort()\ 394 {\ 395 if ( size() < 2 ) return;\ 396 quick_sort( 0, size()-1 );\ 397 }\ 398} 399 400/////////////////////////////// shallow-copy container /////////////////////// 401 402#define __DEFINE_STL_VECTOR_SHALLOW( vectorClass, Type ) class vectorClass {\ 403\ 404public:\ 405 typedef Type value_type;\ 406 typedef value_type* iterator;\ 407 typedef const value_type* const_iterator;\ 408 typedef iterator pointer;\ 409 typedef const iterator const_pointer;\ 410 typedef value_type& reference;\ 411 typedef const value_type& const_reference;\ 412 typedef size_t size_type;\ 413 typedef ptrdiff_t difference_type;\ 414\ 415 typedef iterator OutputIterator;\ 416 typedef const_iterator InputIterator;\ 417\ 418protected:\ 419\ 420 inline void PlacementCopy( const_iterator first, const_iterator last, iterator result )\ 421 {\ 422 memcpy(result, first, int(difference_type(last-first)*sizeof(value_type)) );\ 423 }\ 424\ 425 inline void ConstructObjects( iterator first, iterator last, const value_type& pattern )\ 426 {\ 427 if ( sizeof(pattern) == 1 )\ 428 \ 429 memset( first, int(difference_type(last-first)/sizeof(value_type)), \ 430 int(*((char*)&pattern)) );\ 431 else\ 432 while( first != last ) \ 433 *first++ = pattern;\ 434 }\ 435\ 436 inline void CopyObjects( iterator first, iterator last, iterator result )\ 437 {\ 438 memcpy(result, first, int(difference_type(last-first)*sizeof(value_type)) );\ 439 }\ 440\ 441 inline void CopyObjectsBack( iterator first, iterator last, iterator result )\ 442 {\ 443 memmove(result, first, int(difference_type(last-first)*sizeof(value_type)) );\ 444 }\ 445\ 446public:\ 447\ 448 class reverse_iterator \ 449 {\ 450 friend class vectorClass;\ 451 friend class const_reverse_iterator;\ 452\ 453 public:\ 454 iterator mpPos;\ 455\ 456 public:\ 457\ 458 reverse_iterator() {}\ 459\ 460 reverse_iterator ( iterator pPos )\ 461 {\ 462 mpPos = pPos;\ 463 }\ 464 \ 465 int operator==( const reverse_iterator& rhs ) const { return (mpPos == rhs.mpPos); }\ 466 int operator!=( const reverse_iterator& rhs ) const { return (mpPos != rhs.mpPos); }\ 467\ 468 inline reverse_iterator( const reverse_iterator& other )\ 469 {\ 470 mpPos = other.mpPos;\ 471 }\ 472\ 473 inline const reverse_iterator& operator--() \ 474 {\ 475 --mpPos;\ 476 return *this;\ 477 }\ 478\ 479 inline reverse_iterator operator--(int)\ 480 {\ 481 reverse_iterator tmp = *this;\ 482 --mpPos;\ 483 return tmp;\ 484 }\ 485\ 486 inline const reverse_iterator & operator++() \ 487 {\ 488 ++mpPos;\ 489 return *this;\ 490 }\ 491\ 492 inline reverse_iterator operator++(int)\ 493 {\ 494 reverse_iterator tmp = *this;\ 495 ++mpPos;\ 496 return tmp;\ 497 }\ 498\ 499 inline const_reference operator*() const { return *mpPos; }\ 500 };\ 501\ 502\ 503 class const_reverse_iterator \ 504 {\ 505 protected:\ 506 iterator mpPos;\ 507 public:\ 508\ 509 const_reverse_iterator() {}\ 510\ 511 const_reverse_iterator( const iterator pPos )\ 512 {\ 513 mpPos = pPos;\ 514 }\ 515 \ 516 int operator==( const const_reverse_iterator& rhs ) const { return (mpPos == rhs.mpPos); }\ 517 int operator!=( const const_reverse_iterator& rhs ) const { return (mpPos != rhs.mpPos); }\ 518\ 519 inline const_reverse_iterator( const reverse_iterator& other )\ 520 {\ 521 mpPos = other.mpPos;\ 522 }\ 523\ 524 inline const const_reverse_iterator& operator--() \ 525 {\ 526 --mpPos;\ 527 return *this;\ 528 }\ 529\ 530 inline const_reverse_iterator operator--(int)\ 531 {\ 532 const_reverse_iterator tmp = *this;\ 533 --mpPos;\ 534 return tmp;\ 535 }\ 536\ 537 inline const const_reverse_iterator & operator++() \ 538 {\ 539 ++mpPos;\ 540 return *this;\ 541 }\ 542\ 543 inline const_reverse_iterator operator++(int)\ 544 {\ 545 const_reverse_iterator tmp = *this;\ 546 ++mpPos;\ 547 return tmp;\ 548 }\ 549\ 550 inline const_reference operator*() const { return *mpPos; }\ 551 };\ 552\ 553protected:\ 554 \ 555 pointer mpStart;\ 556 pointer mpEnd;\ 557 pointer mpEndOfBuf;\ 558\ 559protected:\ 560\ 561 inline void quick_sort(int WXUNUSED(low), int WXUNUSED(hi)) \ 562 {\ 563 }\ 564\ 565 inline void DestructRange( iterator WXUNUSED(first), iterator WXUNUSED(last))\ 566 {\ 567 }\ 568\ 569 inline iterator DoInsert(iterator position, const value_type& x)\ 570 {\ 571 if ( mpEnd < mpEndOfBuf )\ 572 {\ 573 new (mpEnd) value_type(*(mpEnd-1) );\ 574 \ 575 CopyObjectsBack( position, mpEnd, position + 1 );\ 576 \ 577 *position = x;\ 578 \ 579 ++mpEnd;\ 580 \ 581 return position;\ 582 }\ 583 \ 584 size_type minBufLen = WXSTL_VECTOR_MIN_BUF_SIZE/sizeof(value_type);\ 585 \ 586 size_type doubledSize = size()*2;\ 587 \ 588 size_type newLen = ( doubledSize < minBufLen ) ? minBufLen : doubledSize;\ 589 \ 590 iterator pNewStart = (iterator)( new char[newLen*sizeof(value_type)] );\ 591 \ 592 PlacementCopy( mpStart, position, pNewStart );\ 593 \ 594 iterator atPosition = pNewStart + difference_type( position - mpStart );\ 595 \ 596 new (atPosition) value_type(x);\ 597 \ 598 iterator newPos = atPosition;\ 599 \ 600 ++atPosition;\ 601 \ 602 if ( mpStart ) \ 603 {\ 604 PlacementCopy( position, mpEnd, atPosition );\ 605 DestructRange( mpStart, mpEnd );\ 606 delete [](char*)mpStart;\ 607 }\ 608 \ 609 mpEnd = atPosition + difference_type( mpEnd - position );\ 610 \ 611 mpStart = pNewStart;\ 612 mpEndOfBuf = pNewStart + newLen;\ 613 \ 614 return newPos;\ 615 }\ 616\ 617public:\ 618\ 619 inline vectorClass() : mpStart(0), \ 620 mpEnd(0),\ 621 mpEndOfBuf(0)\ 622 {}\ 623\ 624 inline vectorClass( const_iterator first, const_iterator last )\ 625 : mpStart(0),\ 626 mpEnd(0),\ 627 mpEndOfBuf(0)\ 628 \ 629 { while( first != last ) push_back( *first++ ); }\ 630\ 631 inline vectorClass( size_type n, const value_type& value = value_type() )\ 632 : mpStart(0),\ 633 mpEnd(0),\ 634 mpEndOfBuf(0)\ 635 \ 636 { for( size_type i = 0; i != n; ++i ) push_back( value ); }\ 637\ 638 inline const vectorClass& operator=( const vectorClass& other )\ 639 {\ 640 if (mpStart) \ 641 {\ 642 DestructRange( begin(), end() );\ 643 delete [](char*)mpStart; \ 644 }\ 645\ 646 size_t newLen = difference_type( other.mpEndOfBuf - other.mpStart );\ 647\ 648 mpStart = (iterator)( new char[newLen*sizeof(value_type)] );\ 649\ 650 PlacementCopy( other.begin(), other.end(), mpStart );\ 651\ 652 mpEnd = mpStart + other.size();\ 653\ 654 mpEndOfBuf = mpStart + newLen;\ 655\ 656 return *this;\ 657 }\ 658\ 659 inline vectorClass( const vectorClass& other )\ 660 : mpStart(0),\ 661 mpEnd(0),\ 662 mpEndOfBuf(0)\ 663 {\ 664 this->operator=( other );\ 665 }\ 666\ 667 inline ~vectorClass() \ 668 { \ 669 if (mpStart) \ 670 {\ 671 DestructRange( begin(), end() );\ 672 delete [](char*)mpStart; \ 673 }\ 674 }\ 675\ 676 inline iterator begin() { return mpStart; }\ 677\ 678 inline const_iterator begin() const { return mpStart; }\ 679\ 680 inline iterator end() { return mpEnd; }\ 681\ 682 inline const_iterator end() const { return mpEnd; }\ 683\ 684 inline size_type size() const { return (size_type)difference_type(mpEnd-mpStart); }\ 685\ 686 inline size_type max_size() const { return UINT_MAX/sizeof(value_type); }\ 687\ 688 inline size_type capacity() const \ 689 { return difference_type(mpEndOfBuf-mpStart)/sizeof(value_type); }\ 690\ 691 inline int empty() const { return mpStart == mpEnd; }\ 692\ 693 inline reference operator[](size_type n) { return *(mpStart+n); }\ 694\ 695 inline const_reference operator[](size_type n) const { return *(mpStart+n); }\ 696\ 697 inline reference front() { return (*mpStart); }\ 698 \ 699 inline const_reference front() const { return (*mpStart); }\ 700\ 701 inline reference back() { return (*(mpEnd-1)); }\ 702\ 703 inline const_reference back() const { return (*(mpEnd-1)); }\ 704\ 705 inline void reserve(size_type WXUNUSED(n)) {}\ 706\ 707 inline void push_back(const value_type& x)\ 708 {\ 709 if ( mpEnd != mpEndOfBuf ) \ 710 {\ 711 new (mpEnd) value_type(x);\ 712 ++mpEnd;\ 713 }\ 714 else\ 715 DoInsert( mpEnd, x );\ 716 }\ 717\ 718 inline iterator insert(iterator position, const value_type& x = value_type())\ 719 {\ 720 if ( position == mpEnd && mpEnd != mpEndOfBuf )\ 721 {\ 722 new (mpEnd) value_type(x);\ 723 ++mpEnd;\ 724 return (mpEnd-1);\ 725 }\ 726 else return DoInsert( position, x );\ 727 }\ 728\ 729 inline void pop_back()\ 730 {\ 731 DestructRange( mpEnd-1, mpEnd );\ 732\ 733 --mpEnd;\ 734 }\ 735\ 736 inline void erase(iterator first, iterator last)\ 737 {\ 738 if ( last == mpEnd )\ 739 {\ 740 DestructRange( first, last );\ 741 mpEnd = first;\ 742 return;\ 743 }\ 744 \ 745 CopyObjects( last, last + difference_type( mpEnd - last ), first );\ 746 \ 747 iterator newEnd = mpEnd - difference_type( last - first );\ 748 DestructRange( newEnd, mpEnd );\ 749 \ 750 mpEnd = newEnd;\ 751 }\ 752\ 753 inline void erase( iterator position )\ 754 {\ 755 erase( position, position + 1 );\ 756 }\ 757\ 758 inline void sort()\ 759 {\ 760 if ( size() < 2 ) return;\ 761 quick_sort( 0, size()-1 );\ 762 }\ 763} 764 765 766 767// redefine below symbol to change the default allocation unit of vector content buffer 768#define WXSTL_VECTOR_MIN_BUF_SIZE 64 769 770// defines vector class, where objects are copied 771// using "deep-copy" sematics (i.e. by calling their copy constructors) 772 773#define WXSTL_VECTOR(ELEMENT_CLASS) \ 774__DEFINE_STL_VECTOR_DEEP(_WXSTL_VECTOR_##ELEMENT_CLASS, ELEMENT_CLASS) 775 776// defines vector class, where objects are copied 777// using "shallow-copy" sematics (i.e. instead of calling 778// their constructors, memcpy() and memmove() are used to copy their raw data) 779 780 781#define WXSTL_VECTOR_SHALLOW_COPY(ELEMENT_CLASS) __DEFINE_STL_VECTOR_SHALLOW(_WXSTL_VECTORSC_##ELEMENT_CLASS, ELEMENT_CLASS) 782 783#endif 784