1 ///////////////////////////////////////////////////////////////////////////// 2 // Copyright (c) Electronic Arts Inc. All rights reserved. 3 ///////////////////////////////////////////////////////////////////////////// 4 5 /////////////////////////////////////////////////////////////////////////////// 6 // Implements a bit vector, which is essentially a vector of bool but which 7 // uses bits instead of bytes. It is thus similar to the original std::vector<bool>. 8 /////////////////////////////////////////////////////////////////////////////// 9 10 /////////////////////////////////////////////////////////////////////////////// 11 // Note: This code is not yet complete: it isn't tested and doesn't yet 12 // support containers other than vector. 13 /////////////////////////////////////////////////////////////////////////////// 14 15 16 #ifndef EASTL_BITVECTOR_H 17 #define EASTL_BITVECTOR_H 18 19 20 #include <EASTL/internal/config.h> 21 #include <EASTL/vector.h> 22 #include <EASTL/algorithm.h> 23 #include <EASTL/bitset.h> 24 25 #ifdef _MSC_VER 26 #pragma warning(push) 27 #pragma warning(disable: 4480) // nonstandard extension used: specifying underlying type for enum 28 #endif 29 30 #if defined(EA_PRAGMA_ONCE_SUPPORTED) 31 #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result. 32 #endif 33 34 35 36 namespace eastl 37 { 38 39 /// EASTL_BITVECTOR_DEFAULT_NAME 40 /// 41 /// Defines a default container name in the absence of a user-provided name. 42 /// 43 #ifndef EASTL_BITVECTOR_DEFAULT_NAME 44 #define EASTL_BITVECTOR_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " bitvector" // Unless the user overrides something, this is "EASTL bitvector". 45 #endif 46 47 /// EASTL_BITVECTOR_DEFAULT_ALLOCATOR 48 /// 49 #ifndef EASTL_BITVECTOR_DEFAULT_ALLOCATOR 50 #define EASTL_BITVECTOR_DEFAULT_ALLOCATOR allocator_type(EASTL_BITVECTOR_DEFAULT_NAME) 51 #endif 52 53 54 55 /// BitvectorWordType 56 /// Defines the integral data type used by bitvector. 57 typedef EASTL_BITSET_WORD_TYPE_DEFAULT BitvectorWordType; 58 59 60 template <typename Element> 61 class bitvector_const_iterator; 62 63 64 template <typename Element> 65 class bitvector_reference 66 { 67 public: 68 typedef eastl_size_t size_type; 69 bitvector_reference(Element* ptr, eastl_size_t i); 70 71 bitvector_reference& operator=(bool value); 72 bitvector_reference& operator=(const bitvector_reference& rhs); 73 74 operator bool() const // Defined here because some compilers fail otherwise. 75 { return (*mpBitWord & (Element(1) << mnBitIndex)) != 0; } 76 77 protected: 78 friend class bitvector_const_iterator<Element>; 79 80 Element* mpBitWord; 81 size_type mnBitIndex; 82 bitvector_reference()83 bitvector_reference() {} 84 void CopyFrom(const bitvector_reference& rhs); 85 }; 86 87 88 89 template <typename Element> 90 class bitvector_const_iterator 91 { 92 public: 93 typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category; 94 typedef bitvector_const_iterator<Element> this_type; 95 typedef bool value_type; 96 typedef bitvector_reference<Element> reference_type; 97 typedef ptrdiff_t difference_type; 98 typedef Element element_type; 99 typedef element_type* pointer; // This is wrong. It needs to be someting that acts as a pointer to a bit. 100 typedef element_type& reference; // This is not right. It needs to be someting that acts as a pointer to a bit. 101 typedef eastl_size_t size_type; 102 103 protected: 104 reference_type mReference; 105 106 enum 107 { 108 kBitCount = (8 * sizeof(Element)) 109 }; 110 111 public: 112 bool operator*() const; 113 bool operator[](difference_type n) const; 114 115 bitvector_const_iterator(); 116 bitvector_const_iterator(const element_type* p, eastl_size_t i); 117 bitvector_const_iterator(const reference_type& referenceType); 118 119 bitvector_const_iterator& operator++(); 120 bitvector_const_iterator operator++(int); 121 bitvector_const_iterator& operator--(); 122 bitvector_const_iterator operator--(int); 123 124 bitvector_const_iterator& operator+=(difference_type dist); 125 bitvector_const_iterator& operator-=(difference_type dist); 126 bitvector_const_iterator operator+ (difference_type dist) const; 127 bitvector_const_iterator operator- (difference_type dist) const; 128 129 difference_type operator-(const this_type& rhs) const; 130 131 bitvector_const_iterator& operator= (const this_type& rhs); 132 133 bool operator==(const this_type& rhs) const; 134 bool operator!=(const this_type& rhs) const; 135 136 bool operator< (const this_type& rhs) const; 137 bool operator<=(const this_type& rhs) const; 138 bool operator> (const this_type& rhs) const; 139 bool operator>=(const this_type& rhs) const; 140 141 int validate(const element_type* pStart, const element_type* pEnd, eastl_size_t nExtraBits) const; 142 143 protected: 144 template <typename, typename, typename> 145 friend class bitvector; 146 get_reference_type()147 reference_type& get_reference_type() { return mReference; } 148 }; 149 150 151 152 template <typename Element> 153 class bitvector_iterator : public bitvector_const_iterator<Element> 154 { 155 public: 156 typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category; 157 typedef bitvector_iterator this_type; 158 typedef bitvector_const_iterator<Element> base_type; 159 typedef bool value_type; 160 typedef bitvector_reference<Element> reference_type; 161 typedef ptrdiff_t difference_type; 162 typedef Element element_type; 163 typedef element_type* pointer; // This is wrong. It needs to be someting that acts as a pointer to a bit. 164 typedef element_type& reference; // This is not right. It needs to be someting that acts as a pointer to a bit. 165 166 public: 167 reference_type operator*() const; 168 reference_type operator[](difference_type n) const; 169 170 bitvector_iterator(); 171 bitvector_iterator(element_type* p, eastl_size_t i); 172 bitvector_iterator(reference_type& referenceType); 173 174 bitvector_iterator& operator++() { base_type::operator++(); return *this; } 175 bitvector_iterator& operator--() { base_type::operator--(); return *this; } 176 bitvector_iterator operator++(int); 177 bitvector_iterator operator--(int); 178 179 bitvector_iterator& operator+=(difference_type dist) { base_type::operator+=(dist); return *this; } 180 bitvector_iterator& operator-=(difference_type dist) { base_type::operator-=(dist); return *this; } 181 bitvector_iterator operator+ (difference_type dist) const; 182 bitvector_iterator operator- (difference_type dist) const; 183 184 // We need this here because we are overloading operator-, so for some reason the 185 // other overload of the function can't be found unless it's explicitly specified. 186 difference_type operator-(const base_type& rhs) const { return base_type::operator-(rhs); } 187 }; 188 189 190 191 /// bitvector 192 /// 193 /// Implements an array of bits treated as boolean values. 194 /// bitvector is similar to vector<bool> but uses bits instead of bytes and 195 /// allows the user to use other containers such as deque instead of vector. 196 /// bitvector is different from bitset in that bitset is less flexible but 197 /// uses less memory and has higher performance. 198 /// 199 /// To consider: Rename the Element template parameter to WordType, for 200 /// consistency with bitset. 201 /// 202 template <typename Allocator = EASTLAllocatorType, 203 typename Element = BitvectorWordType, 204 typename Container = eastl::vector<Element, Allocator> > 205 class bitvector 206 { 207 public: 208 typedef bitvector<Allocator, Element> this_type; 209 typedef bool value_type; 210 typedef bitvector_reference<Element> reference; 211 typedef bool const_reference; 212 typedef bitvector_iterator<Element> iterator; 213 typedef bitvector_const_iterator<Element> const_iterator; 214 typedef eastl::reverse_iterator<iterator> reverse_iterator; 215 typedef eastl::reverse_iterator<const_iterator> const_reverse_iterator; 216 typedef Allocator allocator_type; 217 typedef Element element_type; 218 typedef Container container_type; 219 typedef eastl_size_t size_type; 220 typedef ptrdiff_t difference_type; 221 222 #if defined(_MSC_VER) && (_MSC_VER >= 1400) && (_MSC_VER <= 1600) && !EASTL_STD_CPP_ONLY // _MSC_VER of 1400 means VS2005, 1600 means VS2010. VS2012 generates errors with usage of enum:size_type. 223 enum : size_type { // Use Microsoft enum language extension, allowing for smaller debug symbols than using a static const. Users have been affected by this. 224 npos = container_type::npos, 225 kMaxSize = container_type::kMaxSize 226 }; 227 #else 228 static const size_type npos = container_type::npos; /// 'npos' means non-valid position or simply non-position. 229 static const size_type kMaxSize = container_type::kMaxSize; /// -1 is reserved for 'npos'. It also happens to be slightly beneficial that kMaxSize is a value less than -1, as it helps us deal with potential integer wraparound issues. 230 #endif 231 232 enum 233 { 234 kBitCount = 8 * sizeof(Element) 235 }; 236 237 protected: 238 container_type mContainer; 239 size_type mFreeBitCount; // Unused bits in the last word of mContainer. 240 241 public: 242 bitvector(); 243 explicit bitvector(const allocator_type& allocator); 244 explicit bitvector(size_type n, const allocator_type& allocator = EASTL_BITVECTOR_DEFAULT_ALLOCATOR); 245 bitvector(size_type n, value_type value, const allocator_type& allocator = EASTL_BITVECTOR_DEFAULT_ALLOCATOR); 246 bitvector(const bitvector& copy); 247 248 template <typename InputIterator> 249 bitvector(InputIterator first, InputIterator last); 250 251 bitvector& operator=(const bitvector& x); 252 void swap(this_type& x); 253 254 template <typename InputIterator> 255 void assign(InputIterator first, InputIterator last); 256 257 iterator begin() EA_NOEXCEPT; 258 const_iterator begin() const EA_NOEXCEPT; 259 const_iterator cbegin() const EA_NOEXCEPT; 260 261 iterator end() EA_NOEXCEPT; 262 const_iterator end() const EA_NOEXCEPT; 263 const_iterator cend() const EA_NOEXCEPT; 264 265 reverse_iterator rbegin() EA_NOEXCEPT; 266 const_reverse_iterator rbegin() const EA_NOEXCEPT; 267 const_reverse_iterator crbegin() const EA_NOEXCEPT; 268 269 reverse_iterator rend() EA_NOEXCEPT; 270 const_reverse_iterator rend() const EA_NOEXCEPT; 271 const_reverse_iterator crend() const EA_NOEXCEPT; 272 273 bool empty() const EA_NOEXCEPT; 274 size_type size() const EA_NOEXCEPT; 275 size_type capacity() const EA_NOEXCEPT; 276 277 void resize(size_type n, value_type value); 278 void resize(size_type n); 279 void reserve(size_type n); 280 void set_capacity(size_type n = npos); // Revises the capacity to the user-specified value. Resizes the container to match the capacity if the requested capacity n is less than the current size. If n == npos then the capacity is reallocated (if necessary) such that capacity == size. 281 282 void push_back(); 283 void push_back(value_type value); 284 void pop_back(); 285 286 reference front(); 287 const_reference front() const; 288 reference back(); 289 const_reference back() const; 290 291 bool test(size_type n, bool defaultValue) const; // Returns true if the bit index is < size() and set. Returns defaultValue if the bit is >= size(). 292 void set(size_type n, bool value); // Resizes the container to accomodate n if necessary. 293 294 reference at(size_type n); // throws an out_of_range exception if n is invalid. 295 const_reference at(size_type n) const; 296 297 reference operator[](size_type n); // behavior is undefined if n is invalid. 298 const_reference operator[](size_type n) const; 299 300 /* 301 Work in progress: 302 template <bool value = true> iterator find_first(); // Finds the lowest "on" bit. 303 template <bool value = true> iterator find_next(const_iterator it); // Finds the next lowest "on" bit after it. 304 template <bool value = true> iterator find_last(); // Finds the index of the last "on" bit, returns size if none are set. 305 template <bool value = true> iterator find_prev(const_iterator it); // Finds the index of the last "on" bit before last_find, returns size if none are set. 306 307 template <bool value = true> const_iterator find_first() const; // Finds the lowest "on" bit. 308 template <bool value = true> const_iterator find_next(const_iterator it) const; // Finds the next lowest "on" bit after it. 309 template <bool value = true> const_iterator find_last() const; // Finds the index of the last "on" bit, returns size if none are set. 310 template <bool value = true> const_iterator find_prev(const_iterator it) const; // Finds the index of the last "on" bit before last_find, returns size if none are set. 311 */ 312 313 element_type* data() EA_NOEXCEPT; 314 const element_type* data() const EA_NOEXCEPT; 315 316 iterator insert(const_iterator position, value_type value); 317 void insert(const_iterator position, size_type n, value_type value); 318 319 // template <typename InputIterator> Not yet implemented. See below for disabled definition. 320 // void insert(const_iterator position, InputIterator first, InputIterator last); 321 322 iterator erase(const_iterator position); 323 iterator erase(const_iterator first, const_iterator last); 324 325 reverse_iterator erase(const_reverse_iterator position); 326 reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last); 327 328 void clear(); 329 void reset_lose_memory(); // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs. 330 331 container_type& get_container(); 332 const container_type& get_container() const; 333 334 bool validate() const; 335 int validate_iterator(const_iterator i) const; 336 }; 337 338 339 340 341 /////////////////////////////////////////////////////////////////////// 342 // bitvector_reference 343 /////////////////////////////////////////////////////////////////////// 344 345 template <typename Element> bitvector_reference(Element * p,eastl_size_t i)346 bitvector_reference<Element>::bitvector_reference(Element* p, eastl_size_t i) 347 : mpBitWord(p), 348 mnBitIndex(i) 349 { 350 } 351 352 353 template <typename Element> 354 bitvector_reference<Element>& 355 bitvector_reference<Element>::operator=(bool value) 356 { 357 const Element mask = (Element)(Element(1) << mnBitIndex); 358 359 if(value) 360 *mpBitWord |= mask; 361 else 362 *mpBitWord &= ~mask; 363 364 return *this; 365 } 366 367 368 template <typename Element> 369 bitvector_reference<Element>& 370 bitvector_reference<Element>::operator=(const bitvector_reference& rhs) 371 { 372 return (*this = (bool)rhs); 373 } 374 375 376 template <typename Element> CopyFrom(const bitvector_reference & rhs)377 void bitvector_reference<Element>::CopyFrom(const bitvector_reference& rhs) 378 { 379 mpBitWord = rhs.mpBitWord; 380 mnBitIndex = rhs.mnBitIndex; 381 } 382 383 384 385 386 /////////////////////////////////////////////////////////////////////// 387 // bitvector_const_iterator 388 /////////////////////////////////////////////////////////////////////// 389 390 template <typename Element> bitvector_const_iterator()391 bitvector_const_iterator<Element>::bitvector_const_iterator() 392 : mReference(0, 0) 393 { 394 } 395 396 397 template <typename Element> bitvector_const_iterator(const Element * p,eastl_size_t i)398 bitvector_const_iterator<Element>::bitvector_const_iterator(const Element* p, eastl_size_t i) 399 : mReference(const_cast<Element*>(p), i) // const_cast is safe here because we never let mReference leak and we don't modify it. 400 { 401 } 402 403 404 template <typename Element> bitvector_const_iterator(const reference_type & reference)405 bitvector_const_iterator<Element>::bitvector_const_iterator(const reference_type& reference) 406 : mReference(reference) 407 { 408 } 409 410 411 template <typename Element> 412 bitvector_const_iterator<Element>& 413 bitvector_const_iterator<Element>::operator++() 414 { 415 ++mReference.mnBitIndex; 416 417 if(mReference.mnBitIndex == kBitCount) 418 { 419 ++mReference.mpBitWord; 420 mReference.mnBitIndex = 0; 421 } 422 423 return *this; 424 } 425 426 427 template <typename Element> 428 bitvector_const_iterator<Element>& 429 bitvector_const_iterator<Element>::operator--() 430 { 431 if(mReference.mnBitIndex == 0) 432 { 433 --mReference.mpBitWord; 434 mReference.mnBitIndex = kBitCount; 435 } 436 437 --mReference.mnBitIndex; 438 return *this; 439 } 440 441 442 template <typename Element> 443 bitvector_const_iterator<Element> 444 bitvector_const_iterator<Element>::operator++(int) 445 { 446 bitvector_const_iterator copy(*this); 447 ++*this; 448 return copy; 449 } 450 451 452 template <typename Element> 453 bitvector_const_iterator<Element> 454 bitvector_const_iterator<Element>::operator--(int) 455 { 456 bitvector_const_iterator copy(*this); 457 --*this; 458 return copy; 459 } 460 461 462 template <typename Element> 463 bitvector_const_iterator<Element>& 464 bitvector_const_iterator<Element>::operator+=(difference_type n) 465 { 466 n += mReference.mnBitIndex; 467 468 if(n >= difference_type(0)) 469 { 470 mReference.mpBitWord += n / kBitCount; 471 mReference.mnBitIndex = (size_type)(n % kBitCount); 472 } 473 else 474 { 475 // backwards is tricky 476 // figure out how many full words backwards we need to move 477 // n = [-1..-32] => 1 478 // n = [-33..-64] => 2 479 const size_type backwards = (size_type)(-n + kBitCount - 1); 480 mReference.mpBitWord -= backwards / kBitCount; 481 482 // -1 => 31; backwards = 32; 31 - (backwards % 32) = 31 483 // -2 => 30; backwards = 33; 31 - (backwards % 32) = 30 484 // -3 => 29; backwards = 34 485 // .. 486 // -32 => 0; backwards = 63; 31 - (backwards % 32) = 0 487 // -33 => 31; backwards = 64; 31 - (backwards % 32) = 31 488 mReference.mnBitIndex = (kBitCount - 1) - (backwards % kBitCount); 489 } 490 491 return *this; 492 } 493 494 495 template <typename Element> 496 bitvector_const_iterator<Element>& 497 bitvector_const_iterator<Element>::operator-=(difference_type n) 498 { 499 return (*this += -n); 500 } 501 502 503 template <typename Element> 504 bitvector_const_iterator<Element> 505 bitvector_const_iterator<Element>::operator+(difference_type n) const 506 { 507 bitvector_const_iterator copy(*this); 508 copy += n; 509 return copy; 510 } 511 512 513 template <typename Element> 514 bitvector_const_iterator<Element> 515 bitvector_const_iterator<Element>::operator-(difference_type n) const 516 { 517 bitvector_const_iterator copy(*this); 518 copy -= n; 519 return copy; 520 } 521 522 523 template <typename Element> 524 typename bitvector_const_iterator<Element>::difference_type 525 bitvector_const_iterator<Element>::operator-(const this_type& rhs) const 526 { 527 return ((mReference.mpBitWord - rhs.mReference.mpBitWord) * kBitCount) + mReference.mnBitIndex - rhs.mReference.mnBitIndex; 528 } 529 530 531 template <typename Element> 532 bool bitvector_const_iterator<Element>::operator==(const this_type& rhs) const 533 { 534 return (mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex == rhs.mReference.mnBitIndex); 535 } 536 537 538 template <typename Element> 539 bool bitvector_const_iterator<Element>::operator!=(const this_type& rhs) const 540 { 541 return !(*this == rhs); 542 } 543 544 545 template <typename Element> 546 bool bitvector_const_iterator<Element>::operator<(const this_type& rhs) const 547 { 548 return (mReference.mpBitWord < rhs.mReference.mpBitWord) || 549 ((mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex < rhs.mReference.mnBitIndex)); 550 } 551 552 553 template <typename Element> 554 bool bitvector_const_iterator<Element>::operator<=(const this_type& rhs) const 555 { 556 return (mReference.mpBitWord < rhs.mReference.mpBitWord) || 557 ((mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex <= rhs.mReference.mnBitIndex)); 558 } 559 560 561 template <typename Element> 562 bool bitvector_const_iterator<Element>::operator>(const this_type& rhs) const 563 { 564 return !(*this <= rhs); 565 } 566 567 568 template <typename Element> 569 bool bitvector_const_iterator<Element>::operator>=(const this_type& rhs) const 570 { 571 return !(*this < rhs); 572 } 573 574 575 template <typename Element> 576 bool bitvector_const_iterator<Element>::operator*() const 577 { 578 return mReference; 579 } 580 581 582 template <typename Element> 583 bool bitvector_const_iterator<Element>::operator[](difference_type n) const 584 { 585 return *(*this + n); 586 } 587 588 589 template <typename Element> 590 bitvector_const_iterator<Element>& bitvector_const_iterator<Element>::operator= (const this_type& rhs) 591 { 592 mReference.CopyFrom(rhs.mReference); 593 return *this; 594 } 595 596 597 template <typename Element> validate(const Element * pStart,const Element * pEnd,eastl_size_t nExtraBits)598 int bitvector_const_iterator<Element>::validate(const Element* pStart, const Element* pEnd, eastl_size_t nExtraBits) const 599 { 600 const Element* const pCurrent = mReference.mpBitWord; 601 602 if(pCurrent >= pStart) 603 { 604 if(nExtraBits == 0) 605 { 606 if(pCurrent == pEnd && mReference) 607 return eastl::isf_valid | eastl::isf_current; 608 else if(pCurrent < pEnd) 609 return eastl::isf_valid | eastl::isf_current | eastl::isf_can_dereference; 610 } 611 else if(pCurrent == (pEnd - 1)) 612 { 613 const size_type bit = mReference.mnBitIndex; 614 const size_type lastbit = kBitCount - nExtraBits; 615 616 if(bit == lastbit) 617 return eastl::isf_valid | eastl::isf_current; 618 else if(bit < lastbit) 619 return eastl::isf_valid | eastl::isf_current | eastl::isf_can_dereference; 620 } 621 else if(pCurrent < pEnd) 622 { 623 return eastl::isf_valid | eastl::isf_current | eastl::isf_can_dereference; 624 } 625 } 626 627 return eastl::isf_none; 628 } 629 630 631 632 /////////////////////////////////////////////////////////////////////// 633 // bitvector_iterator 634 /////////////////////////////////////////////////////////////////////// 635 636 template <typename Element> bitvector_iterator()637 bitvector_iterator<Element>::bitvector_iterator() 638 : base_type() 639 { 640 } 641 642 template <typename Element> bitvector_iterator(Element * p,eastl_size_t i)643 bitvector_iterator<Element>::bitvector_iterator(Element* p, eastl_size_t i) 644 : base_type(p, i) 645 { 646 } 647 648 649 template <typename Element> bitvector_iterator(reference_type & reference)650 bitvector_iterator<Element>::bitvector_iterator(reference_type& reference) 651 : base_type(reference) 652 { 653 } 654 655 656 template <typename Element> 657 typename bitvector_iterator<Element>::reference_type 658 bitvector_iterator<Element>::operator*() const 659 { 660 return base_type::mReference; 661 } 662 663 664 template <typename Element> 665 typename bitvector_iterator<Element>::reference_type 666 bitvector_iterator<Element>::operator[](difference_type n) const 667 { 668 return *(*this + n); 669 } 670 671 672 template <typename Element> MoveBits(bitvector_iterator<Element> start,bitvector_iterator<Element> end,bitvector_iterator<Element> dest)673 void MoveBits(bitvector_iterator<Element> start, 674 bitvector_iterator<Element> end, 675 bitvector_iterator<Element> dest) 676 { 677 // Slow implemenation; could optimize by moving a word at a time. 678 if(dest <= start) 679 { 680 while(start != end) 681 { 682 *dest = *start; 683 ++dest; 684 ++start; 685 } 686 } 687 else 688 { 689 // Need to move backwards 690 dest += (end - start); 691 692 while(start != end) 693 { 694 --dest; 695 --end; 696 *dest = *end; 697 } 698 } 699 } 700 701 702 template <typename Element> 703 bitvector_iterator<Element> 704 bitvector_iterator<Element>::operator++(int) 705 { 706 bitvector_iterator copy(*this); 707 ++*this; 708 return copy; 709 } 710 711 712 template <typename Element> 713 bitvector_iterator<Element> 714 bitvector_iterator<Element>::operator--(int) 715 { 716 bitvector_iterator copy(*this); 717 --*this; 718 return copy; 719 } 720 721 722 template <typename Element> 723 bitvector_iterator<Element> 724 bitvector_iterator<Element>::operator+(difference_type n) const 725 { 726 bitvector_iterator copy(*this); 727 copy += n; 728 return copy; 729 } 730 731 732 template <typename Element> 733 bitvector_iterator<Element> 734 bitvector_iterator<Element>::operator-(difference_type n) const 735 { 736 bitvector_iterator copy(*this); 737 copy -= n; 738 return copy; 739 } 740 741 742 743 744 /////////////////////////////////////////////////////////////////////// 745 // bitvector 746 /////////////////////////////////////////////////////////////////////// 747 748 template <typename Allocator, typename Element, typename Container> 749 template <typename InputIterator> assign(InputIterator first,InputIterator last)750 void bitvector<Allocator, Element, Container>::assign(InputIterator first, InputIterator last) 751 { 752 // To consider: We can maybe specialize this on bitvector_iterator to do a fast bitwise copy. 753 // We can also specialize for random access iterators to figure out the size & reserve first. 754 755 clear(); 756 757 while(first != last) 758 { 759 push_back(*first); 760 ++first; 761 } 762 } 763 764 765 template <typename Allocator, typename Element, typename Container> 766 typename bitvector<Allocator, Element, Container>::iterator begin()767 bitvector<Allocator, Element, Container>::begin() EA_NOEXCEPT 768 { 769 return iterator(&mContainer[0], 0); 770 } 771 772 773 template <typename Allocator, typename Element, typename Container> 774 typename bitvector<Allocator, Element, Container>::const_iterator begin()775 bitvector<Allocator, Element, Container>::begin() const EA_NOEXCEPT 776 { 777 return const_iterator(&mContainer[0], 0); 778 } 779 780 781 template <typename Allocator, typename Element, typename Container> 782 typename bitvector<Allocator, Element, Container>::const_iterator cbegin()783 bitvector<Allocator, Element, Container>::cbegin() const EA_NOEXCEPT 784 { 785 return const_iterator(&mContainer[0], 0); 786 } 787 788 789 template <typename Allocator, typename Element, typename Container> 790 typename bitvector<Allocator, Element, Container>::iterator end()791 bitvector<Allocator, Element, Container>::end() EA_NOEXCEPT 792 { 793 return iterator(mContainer.end(), 0) - mFreeBitCount; 794 } 795 796 797 template <typename Allocator, typename Element, typename Container> 798 typename bitvector<Allocator, Element, Container>::const_iterator end()799 bitvector<Allocator, Element, Container>::end() const EA_NOEXCEPT 800 { 801 return const_iterator(mContainer.end(), 0) - mFreeBitCount; 802 } 803 804 805 template <typename Allocator, typename Element, typename Container> 806 typename bitvector<Allocator, Element, Container>::const_iterator cend()807 bitvector<Allocator, Element, Container>::cend() const EA_NOEXCEPT 808 { 809 return const_iterator(mContainer.end(), 0) - mFreeBitCount; 810 } 811 812 813 template <typename Allocator, typename Element, typename Container> empty()814 bool bitvector<Allocator, Element, Container>::empty() const EA_NOEXCEPT 815 { 816 return mContainer.empty(); 817 } 818 819 820 template <typename Allocator, typename Element, typename Container> 821 typename bitvector<Allocator, Element, Container>::size_type size()822 bitvector<Allocator, Element, Container>::size() const EA_NOEXCEPT 823 { 824 return (mContainer.size() * kBitCount) - mFreeBitCount; 825 } 826 827 828 template <typename Allocator, typename Element, typename Container> 829 typename bitvector<Allocator, Element, Container>::size_type capacity()830 bitvector<Allocator, Element, Container>::capacity() const EA_NOEXCEPT 831 { 832 return mContainer.capacity() * kBitCount; 833 } 834 835 836 template <typename Allocator, typename Element, typename Container> set_capacity(size_type n)837 void bitvector<Allocator, Element, Container>::set_capacity(size_type n) 838 { 839 if(n == npos) 840 mContainer.set_capacity(npos); 841 else 842 mContainer.set_capacity((n + kBitCount - 1) / kBitCount); 843 } 844 845 846 template <typename Allocator, typename Element, typename Container> 847 typename bitvector<Allocator, Element, Container>::reverse_iterator rbegin()848 bitvector<Allocator, Element, Container>::rbegin() EA_NOEXCEPT 849 { 850 return reverse_iterator(end()); 851 } 852 853 854 template <typename Allocator, typename Element, typename Container> 855 typename bitvector<Allocator, Element, Container>::const_reverse_iterator rbegin()856 bitvector<Allocator, Element, Container>::rbegin() const EA_NOEXCEPT 857 { 858 return const_reverse_iterator(end()); 859 } 860 861 862 template <typename Allocator, typename Element, typename Container> 863 typename bitvector<Allocator, Element, Container>::const_reverse_iterator crbegin()864 bitvector<Allocator, Element, Container>::crbegin() const EA_NOEXCEPT 865 { 866 return const_reverse_iterator(end()); 867 } 868 869 870 template <typename Allocator, typename Element, typename Container> 871 typename bitvector<Allocator, Element, Container>::reverse_iterator rend()872 bitvector<Allocator, Element, Container>::rend() EA_NOEXCEPT 873 { 874 return reverse_iterator(begin()); 875 } 876 877 878 template <typename Allocator, typename Element, typename Container> 879 typename bitvector<Allocator, Element, Container>::const_reverse_iterator rend()880 bitvector<Allocator, Element, Container>::rend() const EA_NOEXCEPT 881 { 882 return const_reverse_iterator(begin()); 883 } 884 885 886 template <typename Allocator, typename Element, typename Container> 887 typename bitvector<Allocator, Element, Container>::const_reverse_iterator crend()888 bitvector<Allocator, Element, Container>::crend() const EA_NOEXCEPT 889 { 890 return const_reverse_iterator(begin()); 891 } 892 893 894 template <typename Allocator, typename Element, typename Container> 895 typename bitvector<Allocator, Element, Container>::reference front()896 bitvector<Allocator, Element, Container>::front() 897 { 898 EASTL_ASSERT(!empty()); 899 return reference(&mContainer[0], 0); 900 } 901 902 903 template <typename Allocator, typename Element, typename Container> 904 typename bitvector<Allocator, Element, Container>::const_reference front()905 bitvector<Allocator, Element, Container>::front() const 906 { 907 EASTL_ASSERT(!empty()); 908 909 // To consider: make a better solution to this than const_cast. 910 return reference(const_cast<Element*>(&mContainer[0]), 0); 911 } 912 913 914 template <typename Allocator, typename Element, typename Container> 915 typename bitvector<Allocator, Element, Container>::reference back()916 bitvector<Allocator, Element, Container>::back() 917 { 918 EASTL_ASSERT(!empty()); 919 return *(--end()); 920 } 921 922 923 template <typename Allocator, typename Element, typename Container> 924 typename bitvector<Allocator, Element, Container>::const_reference back()925 bitvector<Allocator, Element, Container>::back() const 926 { 927 EASTL_ASSERT(!empty()); 928 return *(--end()); 929 } 930 931 932 template <typename Allocator, typename Element, typename Container> push_back()933 void bitvector<Allocator, Element, Container>::push_back() 934 { 935 if(!mFreeBitCount) 936 { 937 mContainer.push_back(); 938 mFreeBitCount = kBitCount; 939 } 940 941 --mFreeBitCount; 942 } 943 944 945 template <typename Allocator, typename Element, typename Container> push_back(value_type value)946 void bitvector<Allocator, Element, Container>::push_back(value_type value) 947 { 948 push_back(); 949 *--end() = value; 950 } 951 952 953 template <typename Allocator, typename Element, typename Container> pop_back()954 void bitvector<Allocator, Element, Container>::pop_back() 955 { 956 EASTL_ASSERT(!empty()); 957 958 if(++mFreeBitCount == kBitCount) 959 { 960 mContainer.pop_back(); 961 mFreeBitCount = 0; 962 } 963 } 964 965 966 template <typename Allocator, typename Element, typename Container> reserve(size_type n)967 void bitvector<Allocator, Element, Container>::reserve(size_type n) 968 { 969 const size_type wordCount = (n + kBitCount - 1) / kBitCount; 970 mContainer.reserve(wordCount); 971 } 972 973 974 template <typename Allocator, typename Element, typename Container> resize(size_type n)975 void bitvector<Allocator, Element, Container>::resize(size_type n) 976 { 977 const size_type wordCount = (n + kBitCount - 1) / kBitCount; 978 const size_type extra = (wordCount * kBitCount) - n; 979 980 mContainer.resize(wordCount); 981 mFreeBitCount = extra; 982 } 983 984 985 template <typename Allocator, typename Element, typename Container> resize(size_type n,value_type value)986 void bitvector<Allocator, Element, Container>::resize(size_type n, value_type value) 987 { 988 const size_type s = size(); 989 if(n < s) 990 resize(n); 991 992 // Fill up to the end of a word 993 size_type newbits = n - s; 994 995 while(mFreeBitCount && newbits) 996 { 997 push_back(value); 998 --newbits; 999 } 1000 1001 // Fill the rest a word at a time 1002 if(newbits) 1003 { 1004 element_type element(0); 1005 if(value) 1006 element = ~element; 1007 1008 const size_type words = (n + kBitCount - 1) / kBitCount; 1009 const size_type extra = words * kBitCount - n; 1010 mContainer.resize(words, element); 1011 mFreeBitCount = extra; 1012 } 1013 } 1014 1015 1016 template <typename Allocator, typename Element, typename Container> test(size_type n,bool defaultValue)1017 bool bitvector<Allocator, Element, Container>::test(size_type n, bool defaultValue) const 1018 { 1019 if(n < size()) 1020 return *(begin() + (difference_type)n); 1021 1022 return defaultValue; 1023 } 1024 1025 1026 template <typename Allocator, typename Element, typename Container> set(size_type n,bool value)1027 void bitvector<Allocator, Element, Container>::set(size_type n, bool value) 1028 { 1029 if(EASTL_UNLIKELY(n >= size())) 1030 resize(n + 1); 1031 1032 *(begin() + (difference_type)n) = value; 1033 } 1034 1035 1036 template <typename Allocator, typename Element, typename Container> 1037 typename bitvector<Allocator, Element, Container>::reference at(size_type n)1038 bitvector<Allocator, Element, Container>::at(size_type n) 1039 { 1040 // The difference between at and operator[] is that at signals 1041 // if the requested position is out of range by throwing an 1042 // out_of_range exception. 1043 1044 #if EASTL_EXCEPTIONS_ENABLED 1045 if(EASTL_UNLIKELY(n >= size())) 1046 throw std::out_of_range("bitvector::at -- out of range"); 1047 #elif EASTL_ASSERT_ENABLED 1048 if(EASTL_UNLIKELY(n >= size())) 1049 EASTL_FAIL_MSG("bitvector::at -- out of range"); 1050 #endif 1051 1052 return *(begin() + (difference_type)n); 1053 } 1054 1055 1056 template <typename Allocator, typename Element, typename Container> 1057 typename bitvector<Allocator, Element, Container>::const_reference at(size_type n)1058 bitvector<Allocator, Element, Container>::at(size_type n) const 1059 { 1060 #if EASTL_EXCEPTIONS_ENABLED 1061 if(EASTL_UNLIKELY(n >= size())) 1062 throw std::out_of_range("bitvector::at -- out of range"); 1063 #elif EASTL_ASSERT_ENABLED 1064 if(EASTL_UNLIKELY(n >= size())) 1065 EASTL_FAIL_MSG("bitvector::at -- out of range"); 1066 #endif 1067 1068 return *(begin() + (difference_type)n); 1069 } 1070 1071 1072 template <typename Allocator, typename Element, typename Container> 1073 typename bitvector<Allocator, Element, Container>::reference 1074 bitvector<Allocator, Element, Container>::operator[](size_type n) 1075 { 1076 return *(begin() + (difference_type)n); 1077 } 1078 1079 1080 template <typename Allocator, typename Element, typename Container> 1081 typename bitvector<Allocator, Element, Container>::const_reference 1082 bitvector<Allocator, Element, Container>::operator[](size_type n) const 1083 { 1084 return *(begin() + (difference_type)n); 1085 } 1086 1087 1088 /* 1089 template <typename Allocator, typename Element, typename Container> 1090 template <bool value> 1091 typename bitvector<Allocator, Element, Container>::iterator 1092 bitvector<Allocator, Element, Container>::find_first() 1093 { 1094 return begin(); 1095 } 1096 1097 template <bool value> iterator find_next(const_iterator it); 1098 template <bool value> iterator find_last(); 1099 template <bool value> iterator find_prev(const_iterator it); 1100 1101 template <bool value> const_iterator find_first() const; 1102 template <bool value> const_iterator find_next(const_iterator it) const; 1103 template <bool value> const_iterator find_last() const; 1104 template <bool value> const_iterator find_prev(const_iterator it) const; 1105 */ 1106 1107 1108 1109 1110 template <typename Allocator, typename Element, typename Container> 1111 inline typename bitvector<Allocator, Element, Container>::container_type& get_container()1112 bitvector<Allocator, Element, Container>::get_container() 1113 { 1114 return mContainer; 1115 } 1116 1117 1118 template <typename Allocator, typename Element, typename Container> 1119 inline const typename bitvector<Allocator, Element, Container>::container_type& get_container()1120 bitvector<Allocator, Element, Container>::get_container() const 1121 { 1122 return mContainer; 1123 } 1124 1125 1126 template <typename Allocator, typename Element, typename Container> validate()1127 bool bitvector<Allocator, Element, Container>::validate() const 1128 { 1129 if(!mContainer.validate()) 1130 return false; 1131 1132 if((unsigned)mFreeBitCount >= kBitCount) 1133 return false; 1134 1135 return true; 1136 } 1137 1138 1139 template <typename Allocator, typename Element, typename Container> validate_iterator(const_iterator i)1140 int bitvector<Allocator, Element, Container>::validate_iterator(const_iterator i) const 1141 { 1142 return i.validate(mContainer.begin(), mContainer.end(), mFreeBitCount); 1143 } 1144 1145 1146 template <typename Allocator, typename Element, typename Container> 1147 typename bitvector<Allocator, Element, Container>::element_type* data()1148 bitvector<Allocator, Element, Container>::data() EA_NOEXCEPT 1149 { 1150 return mContainer.data(); 1151 } 1152 1153 1154 template <typename Allocator, typename Element, typename Container> 1155 const typename bitvector<Allocator, Element, Container>::element_type* data()1156 bitvector<Allocator, Element, Container>::data() const EA_NOEXCEPT 1157 { 1158 return mContainer.data(); 1159 } 1160 1161 1162 template <typename Allocator, typename Element, typename Container> 1163 typename bitvector<Allocator, Element, Container>::iterator insert(const_iterator position,value_type value)1164 bitvector<Allocator, Element, Container>::insert(const_iterator position, value_type value) 1165 { 1166 iterator iPosition(position.get_reference_type()); // This is just a non-const version of position. 1167 1168 #if EASTL_ASSERT_ENABLED 1169 if(EASTL_UNLIKELY(validate_iterator(iPosition) & eastl::isf_valid) == 0) 1170 EASTL_FAIL_MSG("bitvector::insert -- invalid iterator"); 1171 #endif 1172 1173 // Save because we might reallocate 1174 const typename iterator::difference_type n = iPosition - begin(); 1175 push_back(); 1176 iPosition = begin() + n; 1177 1178 MoveBits(iPosition, --end(), ++iterator(iPosition)); 1179 *iPosition = value; 1180 1181 return iPosition; 1182 } 1183 1184 1185 template <typename Allocator, typename Element, typename Container> insert(const_iterator position,size_type n,value_type value)1186 void bitvector<Allocator, Element, Container>::insert(const_iterator position, size_type n, value_type value) 1187 { 1188 iterator iPosition(position.get_reference_type()); // This is just a non-const version of position. 1189 1190 #if EASTL_ASSERT_ENABLED 1191 if(EASTL_UNLIKELY(validate_iterator(iPosition) & eastl::isf_valid) == 0) 1192 EASTL_FAIL_MSG("bitvector::insert -- invalid iterator"); 1193 #endif 1194 1195 // Save because we might reallocate. 1196 const typename iterator::difference_type p = iPosition - begin(); 1197 resize(size() + n); 1198 iPosition = begin() + p; 1199 1200 iterator insert_end = iPosition + n; 1201 MoveBits(iPosition, end() - n, insert_end); 1202 1203 // To do: Optimize this to word-at-a-time for large inserts 1204 while(iPosition != insert_end) 1205 { 1206 *iPosition = value; 1207 ++iPosition; 1208 } 1209 } 1210 1211 1212 /* 1213 The following is a placeholder for a future implementation. It turns out that a correct implementation of 1214 insert(pos, first, last) is a non-trivial exercise that would take a few hours to implement and test. 1215 The reasons why involve primarily the problem of handling the case where insertion source comes from 1216 within the container itself, and the case that first and last (note they are templated) might not refer 1217 to iterators might refer to a value/count pair. The C++ Standard requires you to handle this case and 1218 I (Paul Pedriana) believe that it applies even for a bitvector, given that bool is an integral type. 1219 So you have to set up a compile-time type traits function chooser. See vector, for example. 1220 1221 template <typename Allocator, typename Element, typename Container> 1222 template <typename InputIterator> 1223 void bitvector<Allocator, Element, Container>::insert(const_iterator position, InputIterator first, InputIterator last) 1224 { 1225 iterator iPosition(position.get_reference_type()); // This is just a non-const version of position. 1226 1227 // This implementation is probably broken due to not handling insertion into self. 1228 // To do: Make a more efficient version of this. 1229 difference_type distance = (iPosition - begin()); 1230 1231 while(first != last) 1232 { 1233 insert(iPosition, *first); 1234 iPosition = begin() + ++distance; 1235 ++first; 1236 } 1237 } 1238 */ 1239 1240 1241 template <typename Allocator, typename Element, typename Container> 1242 typename bitvector<Allocator, Element, Container>::iterator erase(const_iterator position)1243 bitvector<Allocator, Element, Container>::erase(const_iterator position) 1244 { 1245 iterator iPosition(position.get_reference_type()); // This is just a non-const version of position. 1246 1247 #if EASTL_ASSERT_ENABLED 1248 if(EASTL_UNLIKELY(validate_iterator(iPosition) & eastl::isf_can_dereference) == 0) 1249 EASTL_FAIL_MSG("bitvector::erase -- invalid iterator"); 1250 #endif 1251 1252 MoveBits(++iterator(iPosition), end(), iPosition); 1253 resize(size() - 1); 1254 1255 // Verify that no reallocation occurred. 1256 EASTL_ASSERT(validate_iterator(iPosition) & eastl::isf_valid); 1257 return iPosition; 1258 } 1259 1260 1261 template <typename Allocator, typename Element, typename Container> 1262 typename bitvector<Allocator, Element, Container>::iterator erase(const_iterator first,const_iterator last)1263 bitvector<Allocator, Element, Container>::erase(const_iterator first, const_iterator last) 1264 { 1265 iterator iFirst(first.get_reference_type()); // This is just a non-const version of first. 1266 iterator iLast(last.get_reference_type()); // This is just a non-const version of last. 1267 1268 #if EASTL_ASSERT_ENABLED 1269 if(EASTL_UNLIKELY(validate_iterator(iLast) & eastl::isf_valid) == 0) 1270 EASTL_FAIL_MSG("bitvector::erase -- invalid iterator"); 1271 #endif 1272 1273 if(!(iFirst == iLast)) 1274 { 1275 #if EASTL_ASSERT_ENABLED 1276 if(EASTL_UNLIKELY(validate_iterator(iFirst) & eastl::isf_can_dereference) == 0) 1277 EASTL_FAIL_MSG("bitvector::erase -- invalid iterator"); 1278 #endif 1279 1280 const size_type eraseCount = (size_type)(iLast - iFirst); 1281 MoveBits(iLast, end(), iFirst); 1282 resize(size() - eraseCount); 1283 1284 // Verify that no reallocation occurred. 1285 #if EASTL_ASSERT_ENABLED 1286 if(EASTL_UNLIKELY(validate_iterator(iFirst) & eastl::isf_valid) == 0) 1287 EASTL_FAIL_MSG("bitvector::erase -- invalid iterator"); 1288 #endif 1289 } 1290 1291 return iFirst; 1292 } 1293 1294 1295 template <typename Allocator, typename Element, typename Container> 1296 typename bitvector<Allocator, Element, Container>::reverse_iterator erase(const_reverse_iterator position)1297 bitvector<Allocator, Element, Container>::erase(const_reverse_iterator position) 1298 { 1299 return reverse_iterator(erase((++position).base())); 1300 } 1301 1302 1303 template <typename Allocator, typename Element, typename Container> 1304 typename bitvector<Allocator, Element, Container>::reverse_iterator erase(const_reverse_iterator first,const_reverse_iterator last)1305 bitvector<Allocator, Element, Container>::erase(const_reverse_iterator first, const_reverse_iterator last) 1306 { 1307 // Version which erases in order from first to last. 1308 // difference_type i(first.base() - last.base()); 1309 // while(i--) 1310 // first = erase(first); 1311 // return first; 1312 1313 // Version which erases in order from last to first, but is slightly more efficient: 1314 return reverse_iterator(erase(last.base(), first.base())); 1315 } 1316 1317 1318 template <typename Allocator, typename Element, typename Container> swap(this_type & rhs)1319 void bitvector<Allocator, Element, Container>::swap(this_type& rhs) 1320 { 1321 mContainer.swap(rhs.mContainer); 1322 eastl::swap(mFreeBitCount, rhs.mFreeBitCount); 1323 } 1324 1325 1326 template <typename Allocator, typename Element, typename Container> reset_lose_memory()1327 void bitvector<Allocator, Element, Container>::reset_lose_memory() 1328 { 1329 mContainer.reset_lose_memory(); // intentional memory leak. 1330 mFreeBitCount = 0; 1331 } 1332 1333 1334 template <typename Allocator, typename Element, typename Container> clear()1335 void bitvector<Allocator, Element, Container>::clear() 1336 { 1337 mContainer.clear(); 1338 mFreeBitCount = 0; 1339 } 1340 1341 1342 template <typename Allocator, typename Element, typename Container> 1343 bitvector<Allocator, Element, Container>& 1344 bitvector<Allocator, Element, Container>::operator=(const bitvector& rhs) 1345 { 1346 // The following is OK if (&rhs == this) 1347 mContainer = rhs.mContainer; 1348 mFreeBitCount = rhs.mFreeBitCount; 1349 1350 return *this; 1351 } 1352 1353 1354 template <typename Allocator, typename Element, typename Container> bitvector()1355 bitvector<Allocator, Element, Container>::bitvector() 1356 : mContainer(), 1357 mFreeBitCount(0) 1358 { 1359 } 1360 1361 1362 template <typename Allocator, typename Element, typename Container> bitvector(const allocator_type & allocator)1363 bitvector<Allocator, Element, Container>::bitvector(const allocator_type& allocator) 1364 : mContainer(allocator), 1365 mFreeBitCount(0) 1366 { 1367 } 1368 1369 1370 template <typename Allocator, typename Element, typename Container> bitvector(size_type n,const allocator_type & allocator)1371 bitvector<Allocator, Element, Container>::bitvector(size_type n, const allocator_type& allocator) 1372 : mContainer((n + kBitCount - 1) / kBitCount, allocator) 1373 { 1374 mFreeBitCount = kBitCount - (n % kBitCount); 1375 1376 if(mFreeBitCount == kBitCount) 1377 mFreeBitCount = 0; 1378 } 1379 1380 1381 template <typename Allocator, typename Element, typename Container> bitvector(size_type n,value_type value,const allocator_type & allocator)1382 bitvector<Allocator, Element, Container>::bitvector(size_type n, value_type value, const allocator_type& allocator) 1383 : mContainer((n + kBitCount - 1) / kBitCount, value ? ~element_type(0) : element_type(0), allocator) 1384 { 1385 mFreeBitCount = kBitCount - (n % kBitCount); 1386 1387 if(mFreeBitCount == kBitCount) 1388 mFreeBitCount = 0; 1389 } 1390 1391 1392 template <typename Allocator, typename Element, typename Container> bitvector(const bitvector & copy)1393 bitvector<Allocator, Element, Container>::bitvector(const bitvector& copy) 1394 : mContainer(copy.mContainer), 1395 mFreeBitCount(copy.mFreeBitCount) 1396 { 1397 } 1398 1399 1400 template <typename Allocator, typename Element, typename Container> 1401 template <typename InputIterator> bitvector(InputIterator first,InputIterator last)1402 bitvector<Allocator, Element, Container>::bitvector(InputIterator first, InputIterator last) 1403 : mContainer(), 1404 mFreeBitCount(0) 1405 { 1406 assign(first, last); 1407 } 1408 1409 1410 1411 /////////////////////////////////////////////////////////////////////// 1412 // global operators 1413 /////////////////////////////////////////////////////////////////////// 1414 1415 template <typename Allocator, typename Element, typename Container> 1416 inline bool operator==(const bitvector<Allocator, Element, Container>& a, 1417 const bitvector<Allocator, Element, Container>& b) 1418 { 1419 // To do: Replace this with a smart compare implementation. This is much slower than it needs to be. 1420 return ((a.size() == b.size()) && equal(a.begin(), a.end(), b.begin())); 1421 } 1422 1423 1424 template <typename Allocator, typename Element, typename Container> 1425 inline bool operator!=(const bitvector<Allocator, Element, Container>& a, 1426 const bitvector<Allocator, Element, Container>& b) 1427 { 1428 return !operator==(a, b); 1429 } 1430 1431 1432 template <typename Allocator, typename Element, typename Container> 1433 inline bool operator<(const bitvector<Allocator, Element, Container>& a, 1434 const bitvector<Allocator, Element, Container>& b) 1435 { 1436 // To do: Replace this with a smart compare implementation. This is much slower than it needs to be. 1437 return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); 1438 } 1439 1440 1441 template <typename Allocator, typename Element, typename Container> 1442 inline bool operator>(const bitvector<Allocator, Element, Container>& a, 1443 const bitvector<Allocator, Element, Container>& b) 1444 { 1445 return b < a; 1446 } 1447 1448 1449 template <typename Allocator, typename Element, typename Container> 1450 inline bool operator<=(const bitvector<Allocator, Element, Container>& a, 1451 const bitvector<Allocator, Element, Container>& b) 1452 { 1453 return !(b < a); 1454 } 1455 1456 1457 template <typename Allocator, typename Element, typename Container> 1458 inline bool operator>=(const bitvector<Allocator, Element, Container>& a, 1459 const bitvector<Allocator, Element, Container>& b) 1460 { 1461 return !(a < b); 1462 } 1463 1464 template <typename Allocator, typename Element, typename Container> swap(bitvector<Allocator,Element,Container> & a,bitvector<Allocator,Element,Container> & b)1465 inline void swap(bitvector<Allocator, Element, Container>& a, 1466 bitvector<Allocator, Element, Container>& b) 1467 { 1468 a.swap(b); 1469 } 1470 1471 1472 } // namespace eastl 1473 1474 1475 #ifdef _MSC_VER 1476 #pragma warning(pop) 1477 #endif 1478 1479 1480 #endif // Header include guard 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493