aboutsummaryrefslogtreecommitdiff
path: root/include/EASTL/bitvector.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/EASTL/bitvector.h')
-rw-r--r--include/EASTL/bitvector.h1474
1 files changed, 0 insertions, 1474 deletions
diff --git a/include/EASTL/bitvector.h b/include/EASTL/bitvector.h
deleted file mode 100644
index ade6782..0000000
--- a/include/EASTL/bitvector.h
+++ /dev/null
@@ -1,1474 +0,0 @@
-/////////////////////////////////////////////////////////////////////////////
-// Copyright (c) Electronic Arts Inc. All rights reserved.
-/////////////////////////////////////////////////////////////////////////////
-
-///////////////////////////////////////////////////////////////////////////////
-// Implements a bit vector, which is essentially a vector of bool but which
-// uses bits instead of bytes. It is thus similar to the original std::vector<bool>.
-///////////////////////////////////////////////////////////////////////////////
-
-///////////////////////////////////////////////////////////////////////////////
-// Note: This code is not yet complete: it isn't tested and doesn't yet
-// support containers other than vector.
-///////////////////////////////////////////////////////////////////////////////
-
-
-#ifndef EASTL_BITVECTOR_H
-#define EASTL_BITVECTOR_H
-
-
-#include <EASTL/internal/config.h>
-#include <EASTL/vector.h>
-#include <EASTL/algorithm.h>
-#include <EASTL/bitset.h>
-
-EA_DISABLE_VC_WARNING(4480); // nonstandard extension used: specifying underlying type for enum
-
-#if defined(EA_PRAGMA_ONCE_SUPPORTED)
- #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.
-#endif
-
-
-
-namespace eastl
-{
-
- /// EASTL_BITVECTOR_DEFAULT_NAME
- ///
- /// Defines a default container name in the absence of a user-provided name.
- ///
- #ifndef EASTL_BITVECTOR_DEFAULT_NAME
- #define EASTL_BITVECTOR_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " bitvector" // Unless the user overrides something, this is "EASTL bitvector".
- #endif
-
- /// EASTL_BITVECTOR_DEFAULT_ALLOCATOR
- ///
- #ifndef EASTL_BITVECTOR_DEFAULT_ALLOCATOR
- #define EASTL_BITVECTOR_DEFAULT_ALLOCATOR allocator_type(EASTL_BITVECTOR_DEFAULT_NAME)
- #endif
-
-
-
- /// BitvectorWordType
- /// Defines the integral data type used by bitvector.
- typedef EASTL_BITSET_WORD_TYPE_DEFAULT BitvectorWordType;
-
-
- template <typename Element>
- class bitvector_const_iterator;
-
-
- template <typename Element>
- class bitvector_reference
- {
- public:
- typedef eastl_size_t size_type;
- bitvector_reference(Element* ptr, eastl_size_t i);
-
- bitvector_reference& operator=(bool value);
- bitvector_reference& operator=(const bitvector_reference& rhs);
-
- operator bool() const // Defined here because some compilers fail otherwise.
- { return (*mpBitWord & (Element(1) << mnBitIndex)) != 0; }
-
- protected:
- friend class bitvector_const_iterator<Element>;
-
- Element* mpBitWord;
- size_type mnBitIndex;
-
- bitvector_reference() {}
- void CopyFrom(const bitvector_reference& rhs);
- };
-
-
-
- template <typename Element>
- class bitvector_const_iterator
- {
- public:
- typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category;
- typedef bitvector_const_iterator<Element> this_type;
- typedef bool value_type;
- typedef bitvector_reference<Element> reference_type;
- typedef ptrdiff_t difference_type;
- typedef Element element_type;
- typedef element_type* pointer; // This is wrong. It needs to be someting that acts as a pointer to a bit.
- typedef element_type& reference; // This is not right. It needs to be someting that acts as a pointer to a bit.
- typedef eastl_size_t size_type;
-
- protected:
- reference_type mReference;
-
- enum
- {
- kBitCount = (8 * sizeof(Element))
- };
-
- public:
- bool operator*() const;
- bool operator[](difference_type n) const;
-
- bitvector_const_iterator();
- bitvector_const_iterator(const element_type* p, eastl_size_t i);
- bitvector_const_iterator(const reference_type& referenceType);
-
- bitvector_const_iterator& operator++();
- bitvector_const_iterator operator++(int);
- bitvector_const_iterator& operator--();
- bitvector_const_iterator operator--(int);
-
- bitvector_const_iterator& operator+=(difference_type dist);
- bitvector_const_iterator& operator-=(difference_type dist);
- bitvector_const_iterator operator+ (difference_type dist) const;
- bitvector_const_iterator operator- (difference_type dist) const;
-
- difference_type operator-(const this_type& rhs) const;
-
- bitvector_const_iterator& operator= (const this_type& rhs);
-
- bool operator==(const this_type& rhs) const;
- bool operator!=(const this_type& rhs) const;
-
- bool operator< (const this_type& rhs) const;
- bool operator<=(const this_type& rhs) const;
- bool operator> (const this_type& rhs) const;
- bool operator>=(const this_type& rhs) const;
-
- int validate(const element_type* pStart, const element_type* pEnd, eastl_size_t nExtraBits) const;
-
- protected:
- template <typename, typename, typename>
- friend class bitvector;
-
- reference_type& get_reference_type() { return mReference; }
- };
-
-
-
- template <typename Element>
- class bitvector_iterator : public bitvector_const_iterator<Element>
- {
- public:
- typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category;
- typedef bitvector_iterator this_type;
- typedef bitvector_const_iterator<Element> base_type;
- typedef bool value_type;
- typedef bitvector_reference<Element> reference_type;
- typedef ptrdiff_t difference_type;
- typedef Element element_type;
- typedef element_type* pointer; // This is wrong. It needs to be someting that acts as a pointer to a bit.
- typedef element_type& reference; // This is not right. It needs to be someting that acts as a pointer to a bit.
-
- public:
- reference_type operator*() const;
- reference_type operator[](difference_type n) const;
-
- bitvector_iterator();
- bitvector_iterator(element_type* p, eastl_size_t i);
- bitvector_iterator(reference_type& referenceType);
-
- bitvector_iterator& operator++() { base_type::operator++(); return *this; }
- bitvector_iterator& operator--() { base_type::operator--(); return *this; }
- bitvector_iterator operator++(int);
- bitvector_iterator operator--(int);
-
- bitvector_iterator& operator+=(difference_type dist) { base_type::operator+=(dist); return *this; }
- bitvector_iterator& operator-=(difference_type dist) { base_type::operator-=(dist); return *this; }
- bitvector_iterator operator+ (difference_type dist) const;
- bitvector_iterator operator- (difference_type dist) const;
-
- // We need this here because we are overloading operator-, so for some reason the
- // other overload of the function can't be found unless it's explicitly specified.
- difference_type operator-(const base_type& rhs) const { return base_type::operator-(rhs); }
- };
-
-
-
- /// bitvector
- ///
- /// Implements an array of bits treated as boolean values.
- /// bitvector is similar to vector<bool> but uses bits instead of bytes and
- /// allows the user to use other containers such as deque instead of vector.
- /// bitvector is different from bitset in that bitset is less flexible but
- /// uses less memory and has higher performance.
- ///
- /// To consider: Rename the Element template parameter to WordType, for
- /// consistency with bitset.
- ///
- template <typename Allocator = EASTLAllocatorType,
- typename Element = BitvectorWordType,
- typename Container = eastl::vector<Element, Allocator> >
- class bitvector
- {
- public:
- typedef bitvector<Allocator, Element> this_type;
- typedef bool value_type;
- typedef bitvector_reference<Element> reference;
- typedef bool const_reference;
- typedef bitvector_iterator<Element> iterator;
- typedef bitvector_const_iterator<Element> const_iterator;
- typedef eastl::reverse_iterator<iterator> reverse_iterator;
- typedef eastl::reverse_iterator<const_iterator> const_reverse_iterator;
- typedef Allocator allocator_type;
- typedef Element element_type;
- typedef Container container_type;
- typedef eastl_size_t size_type;
- typedef ptrdiff_t difference_type;
-
- #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.
- enum : size_type { // Use Microsoft enum language extension, allowing for smaller debug symbols than using a static const. Users have been affected by this.
- npos = container_type::npos,
- kMaxSize = container_type::kMaxSize
- };
- #else
- static const size_type npos = container_type::npos; /// 'npos' means non-valid position or simply non-position.
- 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.
- #endif
-
- enum
- {
- kBitCount = 8 * sizeof(Element)
- };
-
- protected:
- container_type mContainer;
- size_type mFreeBitCount; // Unused bits in the last word of mContainer.
-
- public:
- bitvector();
- explicit bitvector(const allocator_type& allocator);
- explicit bitvector(size_type n, const allocator_type& allocator = EASTL_BITVECTOR_DEFAULT_ALLOCATOR);
- bitvector(size_type n, value_type value, const allocator_type& allocator = EASTL_BITVECTOR_DEFAULT_ALLOCATOR);
- bitvector(const bitvector& copy);
-
- template <typename InputIterator>
- bitvector(InputIterator first, InputIterator last);
-
- bitvector& operator=(const bitvector& x);
- void swap(this_type& x);
-
- template <typename InputIterator>
- void assign(InputIterator first, InputIterator last);
-
- iterator begin() EA_NOEXCEPT;
- const_iterator begin() const EA_NOEXCEPT;
- const_iterator cbegin() const EA_NOEXCEPT;
-
- iterator end() EA_NOEXCEPT;
- const_iterator end() const EA_NOEXCEPT;
- const_iterator cend() const EA_NOEXCEPT;
-
- reverse_iterator rbegin() EA_NOEXCEPT;
- const_reverse_iterator rbegin() const EA_NOEXCEPT;
- const_reverse_iterator crbegin() const EA_NOEXCEPT;
-
- reverse_iterator rend() EA_NOEXCEPT;
- const_reverse_iterator rend() const EA_NOEXCEPT;
- const_reverse_iterator crend() const EA_NOEXCEPT;
-
- bool empty() const EA_NOEXCEPT;
- size_type size() const EA_NOEXCEPT;
- size_type capacity() const EA_NOEXCEPT;
-
- void resize(size_type n, value_type value);
- void resize(size_type n);
- void reserve(size_type n);
- 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.
-
- void push_back();
- void push_back(value_type value);
- void pop_back();
-
- reference front();
- const_reference front() const;
- reference back();
- const_reference back() const;
-
- 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().
- void set(size_type n, bool value); // Resizes the container to accomodate n if necessary.
-
- reference at(size_type n); // throws an out_of_range exception if n is invalid.
- const_reference at(size_type n) const;
-
- reference operator[](size_type n); // behavior is undefined if n is invalid.
- const_reference operator[](size_type n) const;
-
- /*
- Work in progress:
- template <bool value = true> iterator find_first(); // Finds the lowest "on" bit.
- template <bool value = true> iterator find_next(const_iterator it); // Finds the next lowest "on" bit after it.
- template <bool value = true> iterator find_last(); // Finds the index of the last "on" bit, returns size if none are set.
- 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.
-
- template <bool value = true> const_iterator find_first() const; // Finds the lowest "on" bit.
- template <bool value = true> const_iterator find_next(const_iterator it) const; // Finds the next lowest "on" bit after it.
- template <bool value = true> const_iterator find_last() const; // Finds the index of the last "on" bit, returns size if none are set.
- 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.
- */
-
- element_type* data() EA_NOEXCEPT;
- const element_type* data() const EA_NOEXCEPT;
-
- iterator insert(const_iterator position, value_type value);
- void insert(const_iterator position, size_type n, value_type value);
-
- // template <typename InputIterator> Not yet implemented. See below for disabled definition.
- // void insert(const_iterator position, InputIterator first, InputIterator last);
-
- iterator erase(const_iterator position);
- iterator erase(const_iterator first, const_iterator last);
-
- reverse_iterator erase(const_reverse_iterator position);
- reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last);
-
- void clear();
- void reset_lose_memory(); // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs.
-
- container_type& get_container();
- const container_type& get_container() const;
-
- bool validate() const;
- int validate_iterator(const_iterator i) const;
- };
-
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // bitvector_reference
- ///////////////////////////////////////////////////////////////////////
-
- template <typename Element>
- bitvector_reference<Element>::bitvector_reference(Element* p, eastl_size_t i)
- : mpBitWord(p),
- mnBitIndex(i)
- {
- }
-
-
- template <typename Element>
- bitvector_reference<Element>&
- bitvector_reference<Element>::operator=(bool value)
- {
- const Element mask = (Element)(Element(1) << mnBitIndex);
-
- if(value)
- *mpBitWord |= mask;
- else
- *mpBitWord &= ~mask;
-
- return *this;
- }
-
-
- template <typename Element>
- bitvector_reference<Element>&
- bitvector_reference<Element>::operator=(const bitvector_reference& rhs)
- {
- return (*this = (bool)rhs);
- }
-
-
- template <typename Element>
- void bitvector_reference<Element>::CopyFrom(const bitvector_reference& rhs)
- {
- mpBitWord = rhs.mpBitWord;
- mnBitIndex = rhs.mnBitIndex;
- }
-
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // bitvector_const_iterator
- ///////////////////////////////////////////////////////////////////////
-
- template <typename Element>
- bitvector_const_iterator<Element>::bitvector_const_iterator()
- : mReference(0, 0)
- {
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>::bitvector_const_iterator(const Element* p, eastl_size_t i)
- : mReference(const_cast<Element*>(p), i) // const_cast is safe here because we never let mReference leak and we don't modify it.
- {
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>::bitvector_const_iterator(const reference_type& reference)
- : mReference(reference)
- {
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>&
- bitvector_const_iterator<Element>::operator++()
- {
- ++mReference.mnBitIndex;
-
- if(mReference.mnBitIndex == kBitCount)
- {
- ++mReference.mpBitWord;
- mReference.mnBitIndex = 0;
- }
-
- return *this;
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>&
- bitvector_const_iterator<Element>::operator--()
- {
- if(mReference.mnBitIndex == 0)
- {
- --mReference.mpBitWord;
- mReference.mnBitIndex = kBitCount;
- }
-
- --mReference.mnBitIndex;
- return *this;
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>
- bitvector_const_iterator<Element>::operator++(int)
- {
- bitvector_const_iterator copy(*this);
- ++*this;
- return copy;
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>
- bitvector_const_iterator<Element>::operator--(int)
- {
- bitvector_const_iterator copy(*this);
- --*this;
- return copy;
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>&
- bitvector_const_iterator<Element>::operator+=(difference_type n)
- {
- n += mReference.mnBitIndex;
-
- if(n >= difference_type(0))
- {
- mReference.mpBitWord += n / kBitCount;
- mReference.mnBitIndex = (size_type)(n % kBitCount);
- }
- else
- {
- // backwards is tricky
- // figure out how many full words backwards we need to move
- // n = [-1..-32] => 1
- // n = [-33..-64] => 2
- const size_type backwards = (size_type)(-n + kBitCount - 1);
- mReference.mpBitWord -= backwards / kBitCount;
-
- // -1 => 31; backwards = 32; 31 - (backwards % 32) = 31
- // -2 => 30; backwards = 33; 31 - (backwards % 32) = 30
- // -3 => 29; backwards = 34
- // ..
- // -32 => 0; backwards = 63; 31 - (backwards % 32) = 0
- // -33 => 31; backwards = 64; 31 - (backwards % 32) = 31
- mReference.mnBitIndex = (kBitCount - 1) - (backwards % kBitCount);
- }
-
- return *this;
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>&
- bitvector_const_iterator<Element>::operator-=(difference_type n)
- {
- return (*this += -n);
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>
- bitvector_const_iterator<Element>::operator+(difference_type n) const
- {
- bitvector_const_iterator copy(*this);
- copy += n;
- return copy;
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>
- bitvector_const_iterator<Element>::operator-(difference_type n) const
- {
- bitvector_const_iterator copy(*this);
- copy -= n;
- return copy;
- }
-
-
- template <typename Element>
- typename bitvector_const_iterator<Element>::difference_type
- bitvector_const_iterator<Element>::operator-(const this_type& rhs) const
- {
- return ((mReference.mpBitWord - rhs.mReference.mpBitWord) * kBitCount) + mReference.mnBitIndex - rhs.mReference.mnBitIndex;
- }
-
-
- template <typename Element>
- bool bitvector_const_iterator<Element>::operator==(const this_type& rhs) const
- {
- return (mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex == rhs.mReference.mnBitIndex);
- }
-
-
- template <typename Element>
- bool bitvector_const_iterator<Element>::operator!=(const this_type& rhs) const
- {
- return !(*this == rhs);
- }
-
-
- template <typename Element>
- bool bitvector_const_iterator<Element>::operator<(const this_type& rhs) const
- {
- return (mReference.mpBitWord < rhs.mReference.mpBitWord) ||
- ((mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex < rhs.mReference.mnBitIndex));
- }
-
-
- template <typename Element>
- bool bitvector_const_iterator<Element>::operator<=(const this_type& rhs) const
- {
- return (mReference.mpBitWord < rhs.mReference.mpBitWord) ||
- ((mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex <= rhs.mReference.mnBitIndex));
- }
-
-
- template <typename Element>
- bool bitvector_const_iterator<Element>::operator>(const this_type& rhs) const
- {
- return !(*this <= rhs);
- }
-
-
- template <typename Element>
- bool bitvector_const_iterator<Element>::operator>=(const this_type& rhs) const
- {
- return !(*this < rhs);
- }
-
-
- template <typename Element>
- bool bitvector_const_iterator<Element>::operator*() const
- {
- return mReference;
- }
-
-
- template <typename Element>
- bool bitvector_const_iterator<Element>::operator[](difference_type n) const
- {
- return *(*this + n);
- }
-
-
- template <typename Element>
- bitvector_const_iterator<Element>& bitvector_const_iterator<Element>::operator= (const this_type& rhs)
- {
- mReference.CopyFrom(rhs.mReference);
- return *this;
- }
-
-
- template <typename Element>
- int bitvector_const_iterator<Element>::validate(const Element* pStart, const Element* pEnd, eastl_size_t nExtraBits) const
- {
- const Element* const pCurrent = mReference.mpBitWord;
-
- if(pCurrent >= pStart)
- {
- if(nExtraBits == 0)
- {
- if(pCurrent == pEnd && mReference)
- return eastl::isf_valid | eastl::isf_current;
- else if(pCurrent < pEnd)
- return eastl::isf_valid | eastl::isf_current | eastl::isf_can_dereference;
- }
- else if(pCurrent == (pEnd - 1))
- {
- const size_type bit = mReference.mnBitIndex;
- const size_type lastbit = kBitCount - nExtraBits;
-
- if(bit == lastbit)
- return eastl::isf_valid | eastl::isf_current;
- else if(bit < lastbit)
- return eastl::isf_valid | eastl::isf_current | eastl::isf_can_dereference;
- }
- else if(pCurrent < pEnd)
- {
- return eastl::isf_valid | eastl::isf_current | eastl::isf_can_dereference;
- }
- }
-
- return eastl::isf_none;
- }
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // bitvector_iterator
- ///////////////////////////////////////////////////////////////////////
-
- template <typename Element>
- bitvector_iterator<Element>::bitvector_iterator()
- : base_type()
- {
- }
-
- template <typename Element>
- bitvector_iterator<Element>::bitvector_iterator(Element* p, eastl_size_t i)
- : base_type(p, i)
- {
- }
-
-
- template <typename Element>
- bitvector_iterator<Element>::bitvector_iterator(reference_type& reference)
- : base_type(reference)
- {
- }
-
-
- template <typename Element>
- typename bitvector_iterator<Element>::reference_type
- bitvector_iterator<Element>::operator*() const
- {
- return base_type::mReference;
- }
-
-
- template <typename Element>
- typename bitvector_iterator<Element>::reference_type
- bitvector_iterator<Element>::operator[](difference_type n) const
- {
- return *(*this + n);
- }
-
-
- template <typename Element>
- void MoveBits(bitvector_iterator<Element> start,
- bitvector_iterator<Element> end,
- bitvector_iterator<Element> dest)
- {
- // Slow implemenation; could optimize by moving a word at a time.
- if(dest <= start)
- {
- while(start != end)
- {
- *dest = *start;
- ++dest;
- ++start;
- }
- }
- else
- {
- // Need to move backwards
- dest += (end - start);
-
- while(start != end)
- {
- --dest;
- --end;
- *dest = *end;
- }
- }
- }
-
-
- template <typename Element>
- bitvector_iterator<Element>
- bitvector_iterator<Element>::operator++(int)
- {
- bitvector_iterator copy(*this);
- ++*this;
- return copy;
- }
-
-
- template <typename Element>
- bitvector_iterator<Element>
- bitvector_iterator<Element>::operator--(int)
- {
- bitvector_iterator copy(*this);
- --*this;
- return copy;
- }
-
-
- template <typename Element>
- bitvector_iterator<Element>
- bitvector_iterator<Element>::operator+(difference_type n) const
- {
- bitvector_iterator copy(*this);
- copy += n;
- return copy;
- }
-
-
- template <typename Element>
- bitvector_iterator<Element>
- bitvector_iterator<Element>::operator-(difference_type n) const
- {
- bitvector_iterator copy(*this);
- copy -= n;
- return copy;
- }
-
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // bitvector
- ///////////////////////////////////////////////////////////////////////
-
- template <typename Allocator, typename Element, typename Container>
- template <typename InputIterator>
- void bitvector<Allocator, Element, Container>::assign(InputIterator first, InputIterator last)
- {
- // To consider: We can maybe specialize this on bitvector_iterator to do a fast bitwise copy.
- // We can also specialize for random access iterators to figure out the size & reserve first.
-
- clear();
-
- while(first != last)
- {
- push_back(*first);
- ++first;
- }
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::iterator
- bitvector<Allocator, Element, Container>::begin() EA_NOEXCEPT
- {
- return iterator(mContainer.begin(), 0);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_iterator
- bitvector<Allocator, Element, Container>::begin() const EA_NOEXCEPT
- {
- return const_iterator(mContainer.begin(), 0);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_iterator
- bitvector<Allocator, Element, Container>::cbegin() const EA_NOEXCEPT
- {
- return const_iterator(mContainer.begin(), 0);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::iterator
- bitvector<Allocator, Element, Container>::end() EA_NOEXCEPT
- {
- return iterator(mContainer.end(), 0) - mFreeBitCount;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_iterator
- bitvector<Allocator, Element, Container>::end() const EA_NOEXCEPT
- {
- return const_iterator(mContainer.end(), 0) - mFreeBitCount;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_iterator
- bitvector<Allocator, Element, Container>::cend() const EA_NOEXCEPT
- {
- return const_iterator(mContainer.end(), 0) - mFreeBitCount;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bool bitvector<Allocator, Element, Container>::empty() const EA_NOEXCEPT
- {
- return mContainer.empty();
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::size_type
- bitvector<Allocator, Element, Container>::size() const EA_NOEXCEPT
- {
- return (mContainer.size() * kBitCount) - mFreeBitCount;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::size_type
- bitvector<Allocator, Element, Container>::capacity() const EA_NOEXCEPT
- {
- return mContainer.capacity() * kBitCount;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::set_capacity(size_type n)
- {
- if(n == npos)
- mContainer.set_capacity(npos);
- else
- mContainer.set_capacity((n + kBitCount - 1) / kBitCount);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::reverse_iterator
- bitvector<Allocator, Element, Container>::rbegin() EA_NOEXCEPT
- {
- return reverse_iterator(end());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_reverse_iterator
- bitvector<Allocator, Element, Container>::rbegin() const EA_NOEXCEPT
- {
- return const_reverse_iterator(end());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_reverse_iterator
- bitvector<Allocator, Element, Container>::crbegin() const EA_NOEXCEPT
- {
- return const_reverse_iterator(end());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::reverse_iterator
- bitvector<Allocator, Element, Container>::rend() EA_NOEXCEPT
- {
- return reverse_iterator(begin());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_reverse_iterator
- bitvector<Allocator, Element, Container>::rend() const EA_NOEXCEPT
- {
- return const_reverse_iterator(begin());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_reverse_iterator
- bitvector<Allocator, Element, Container>::crend() const EA_NOEXCEPT
- {
- return const_reverse_iterator(begin());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::reference
- bitvector<Allocator, Element, Container>::front()
- {
- EASTL_ASSERT(!empty());
- return reference(&mContainer[0], 0);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_reference
- bitvector<Allocator, Element, Container>::front() const
- {
- EASTL_ASSERT(!empty());
-
- // To consider: make a better solution to this than const_cast.
- return reference(const_cast<Element*>(&mContainer[0]), 0);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::reference
- bitvector<Allocator, Element, Container>::back()
- {
- EASTL_ASSERT(!empty());
- return *(--end());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_reference
- bitvector<Allocator, Element, Container>::back() const
- {
- EASTL_ASSERT(!empty());
- return *(--end());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::push_back()
- {
- if(!mFreeBitCount)
- {
- mContainer.push_back();
- mFreeBitCount = kBitCount;
- }
-
- --mFreeBitCount;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::push_back(value_type value)
- {
- push_back();
- *--end() = value;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::pop_back()
- {
- EASTL_ASSERT(!empty());
-
- if(++mFreeBitCount == kBitCount)
- {
- mContainer.pop_back();
- mFreeBitCount = 0;
- }
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::reserve(size_type n)
- {
- const size_type wordCount = (n + kBitCount - 1) / kBitCount;
- mContainer.reserve(wordCount);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::resize(size_type n)
- {
- const size_type wordCount = (n + kBitCount - 1) / kBitCount;
- const size_type extra = (wordCount * kBitCount) - n;
-
- mContainer.resize(wordCount);
- mFreeBitCount = extra;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::resize(size_type n, value_type value)
- {
- const size_type s = size();
- if(n < s)
- resize(n);
-
- // Fill up to the end of a word
- size_type newbits = n - s;
-
- while(mFreeBitCount && newbits)
- {
- push_back(value);
- --newbits;
- }
-
- // Fill the rest a word at a time
- if(newbits)
- {
- element_type element(0);
- if(value)
- element = ~element;
-
- const size_type words = (n + kBitCount - 1) / kBitCount;
- const size_type extra = words * kBitCount - n;
- mContainer.resize(words, element);
- mFreeBitCount = extra;
- }
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bool bitvector<Allocator, Element, Container>::test(size_type n, bool defaultValue) const
- {
- if(n < size())
- return *(begin() + (difference_type)n);
-
- return defaultValue;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::set(size_type n, bool value)
- {
- if(EASTL_UNLIKELY(n >= size()))
- resize(n + 1);
-
- *(begin() + (difference_type)n) = value;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::reference
- bitvector<Allocator, Element, Container>::at(size_type n)
- {
- // The difference between at and operator[] is that at signals
- // if the requested position is out of range by throwing an
- // out_of_range exception.
-
- #if EASTL_EXCEPTIONS_ENABLED
- if(EASTL_UNLIKELY(n >= size()))
- throw std::out_of_range("bitvector::at -- out of range");
- #elif EASTL_ASSERT_ENABLED
- if(EASTL_UNLIKELY(n >= size()))
- EASTL_FAIL_MSG("bitvector::at -- out of range");
- #endif
-
- return *(begin() + (difference_type)n);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_reference
- bitvector<Allocator, Element, Container>::at(size_type n) const
- {
- #if EASTL_EXCEPTIONS_ENABLED
- if(EASTL_UNLIKELY(n >= size()))
- throw std::out_of_range("bitvector::at -- out of range");
- #elif EASTL_ASSERT_ENABLED
- if(EASTL_UNLIKELY(n >= size()))
- EASTL_FAIL_MSG("bitvector::at -- out of range");
- #endif
-
- return *(begin() + (difference_type)n);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::reference
- bitvector<Allocator, Element, Container>::operator[](size_type n)
- {
- return *(begin() + (difference_type)n);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::const_reference
- bitvector<Allocator, Element, Container>::operator[](size_type n) const
- {
- return *(begin() + (difference_type)n);
- }
-
-
-/*
- template <typename Allocator, typename Element, typename Container>
- template <bool value>
- typename bitvector<Allocator, Element, Container>::iterator
- bitvector<Allocator, Element, Container>::find_first()
- {
- return begin();
- }
-
- template <bool value> iterator find_next(const_iterator it);
- template <bool value> iterator find_last();
- template <bool value> iterator find_prev(const_iterator it);
-
- template <bool value> const_iterator find_first() const;
- template <bool value> const_iterator find_next(const_iterator it) const;
- template <bool value> const_iterator find_last() const;
- template <bool value> const_iterator find_prev(const_iterator it) const;
-*/
-
-
-
-
- template <typename Allocator, typename Element, typename Container>
- inline typename bitvector<Allocator, Element, Container>::container_type&
- bitvector<Allocator, Element, Container>::get_container()
- {
- return mContainer;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- inline const typename bitvector<Allocator, Element, Container>::container_type&
- bitvector<Allocator, Element, Container>::get_container() const
- {
- return mContainer;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bool bitvector<Allocator, Element, Container>::validate() const
- {
- if(!mContainer.validate())
- return false;
-
- if((unsigned)mFreeBitCount >= kBitCount)
- return false;
-
- return true;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- int bitvector<Allocator, Element, Container>::validate_iterator(const_iterator i) const
- {
- return i.validate(mContainer.begin(), mContainer.end(), mFreeBitCount);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::element_type*
- bitvector<Allocator, Element, Container>::data() EA_NOEXCEPT
- {
- return mContainer.data();
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- const typename bitvector<Allocator, Element, Container>::element_type*
- bitvector<Allocator, Element, Container>::data() const EA_NOEXCEPT
- {
- return mContainer.data();
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::iterator
- bitvector<Allocator, Element, Container>::insert(const_iterator position, value_type value)
- {
- iterator iPosition(position.get_reference_type()); // This is just a non-const version of position.
-
- #if EASTL_ASSERT_ENABLED
- if(EASTL_UNLIKELY(validate_iterator(iPosition) & eastl::isf_valid) == 0)
- EASTL_FAIL_MSG("bitvector::insert -- invalid iterator");
- #endif
-
- // Save because we might reallocate
- const typename iterator::difference_type n = iPosition - begin();
- push_back();
- iPosition = begin() + n;
-
- MoveBits(iPosition, --end(), ++iterator(iPosition));
- *iPosition = value;
-
- return iPosition;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::insert(const_iterator position, size_type n, value_type value)
- {
- iterator iPosition(position.get_reference_type()); // This is just a non-const version of position.
-
- #if EASTL_ASSERT_ENABLED
- if(EASTL_UNLIKELY(validate_iterator(iPosition) & eastl::isf_valid) == 0)
- EASTL_FAIL_MSG("bitvector::insert -- invalid iterator");
- #endif
-
- // Save because we might reallocate.
- const typename iterator::difference_type p = iPosition - begin();
- resize(size() + n);
- iPosition = begin() + p;
-
- iterator insert_end = iPosition + n;
- MoveBits(iPosition, end() - n, insert_end);
-
- // To do: Optimize this to word-at-a-time for large inserts
- while(iPosition != insert_end)
- {
- *iPosition = value;
- ++iPosition;
- }
- }
-
-
- /*
- The following is a placeholder for a future implementation. It turns out that a correct implementation of
- insert(pos, first, last) is a non-trivial exercise that would take a few hours to implement and test.
- The reasons why involve primarily the problem of handling the case where insertion source comes from
- within the container itself, and the case that first and last (note they are templated) might not refer
- to iterators might refer to a value/count pair. The C++ Standard requires you to handle this case and
- I (Paul Pedriana) believe that it applies even for a bitvector, given that bool is an integral type.
- So you have to set up a compile-time type traits function chooser. See vector, for example.
-
- template <typename Allocator, typename Element, typename Container>
- template <typename InputIterator>
- void bitvector<Allocator, Element, Container>::insert(const_iterator position, InputIterator first, InputIterator last)
- {
- iterator iPosition(position.get_reference_type()); // This is just a non-const version of position.
-
- // This implementation is probably broken due to not handling insertion into self.
- // To do: Make a more efficient version of this.
- difference_type distance = (iPosition - begin());
-
- while(first != last)
- {
- insert(iPosition, *first);
- iPosition = begin() + ++distance;
- ++first;
- }
- }
- */
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::iterator
- bitvector<Allocator, Element, Container>::erase(const_iterator position)
- {
- iterator iPosition(position.get_reference_type()); // This is just a non-const version of position.
-
- #if EASTL_ASSERT_ENABLED
- if(EASTL_UNLIKELY(validate_iterator(iPosition) & eastl::isf_can_dereference) == 0)
- EASTL_FAIL_MSG("bitvector::erase -- invalid iterator");
- #endif
-
- MoveBits(++iterator(iPosition), end(), iPosition);
- resize(size() - 1);
-
- // Verify that no reallocation occurred.
- EASTL_ASSERT(validate_iterator(iPosition) & eastl::isf_valid);
- return iPosition;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::iterator
- bitvector<Allocator, Element, Container>::erase(const_iterator first, const_iterator last)
- {
- iterator iFirst(first.get_reference_type()); // This is just a non-const version of first.
- iterator iLast(last.get_reference_type()); // This is just a non-const version of last.
-
- #if EASTL_ASSERT_ENABLED
- if(EASTL_UNLIKELY(validate_iterator(iLast) & eastl::isf_valid) == 0)
- EASTL_FAIL_MSG("bitvector::erase -- invalid iterator");
- #endif
-
- if(!(iFirst == iLast))
- {
- #if EASTL_ASSERT_ENABLED
- if(EASTL_UNLIKELY(validate_iterator(iFirst) & eastl::isf_can_dereference) == 0)
- EASTL_FAIL_MSG("bitvector::erase -- invalid iterator");
- #endif
-
- const size_type eraseCount = (size_type)(iLast - iFirst);
- MoveBits(iLast, end(), iFirst);
- resize(size() - eraseCount);
-
- // Verify that no reallocation occurred.
- #if EASTL_ASSERT_ENABLED
- if(EASTL_UNLIKELY(validate_iterator(iFirst) & eastl::isf_valid) == 0)
- EASTL_FAIL_MSG("bitvector::erase -- invalid iterator");
- #endif
- }
-
- return iFirst;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::reverse_iterator
- bitvector<Allocator, Element, Container>::erase(const_reverse_iterator position)
- {
- return reverse_iterator(erase((++position).base()));
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- typename bitvector<Allocator, Element, Container>::reverse_iterator
- bitvector<Allocator, Element, Container>::erase(const_reverse_iterator first, const_reverse_iterator last)
- {
- // Version which erases in order from first to last.
- // difference_type i(first.base() - last.base());
- // while(i--)
- // first = erase(first);
- // return first;
-
- // Version which erases in order from last to first, but is slightly more efficient:
- return reverse_iterator(erase(last.base(), first.base()));
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::swap(this_type& rhs)
- {
- mContainer.swap(rhs.mContainer);
- eastl::swap(mFreeBitCount, rhs.mFreeBitCount);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::reset_lose_memory()
- {
- mContainer.reset_lose_memory(); // intentional memory leak.
- mFreeBitCount = 0;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- void bitvector<Allocator, Element, Container>::clear()
- {
- mContainer.clear();
- mFreeBitCount = 0;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bitvector<Allocator, Element, Container>&
- bitvector<Allocator, Element, Container>::operator=(const bitvector& rhs)
- {
- // The following is OK if (&rhs == this)
- mContainer = rhs.mContainer;
- mFreeBitCount = rhs.mFreeBitCount;
-
- return *this;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bitvector<Allocator, Element, Container>::bitvector()
- : mContainer(),
- mFreeBitCount(0)
- {
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bitvector<Allocator, Element, Container>::bitvector(const allocator_type& allocator)
- : mContainer(allocator),
- mFreeBitCount(0)
- {
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bitvector<Allocator, Element, Container>::bitvector(size_type n, const allocator_type& allocator)
- : mContainer((n + kBitCount - 1) / kBitCount, allocator)
- {
- mFreeBitCount = kBitCount - (n % kBitCount);
-
- if(mFreeBitCount == kBitCount)
- mFreeBitCount = 0;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bitvector<Allocator, Element, Container>::bitvector(size_type n, value_type value, const allocator_type& allocator)
- : mContainer((n + kBitCount - 1) / kBitCount, value ? ~element_type(0) : element_type(0), allocator)
- {
- mFreeBitCount = kBitCount - (n % kBitCount);
-
- if(mFreeBitCount == kBitCount)
- mFreeBitCount = 0;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- bitvector<Allocator, Element, Container>::bitvector(const bitvector& copy)
- : mContainer(copy.mContainer),
- mFreeBitCount(copy.mFreeBitCount)
- {
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- template <typename InputIterator>
- bitvector<Allocator, Element, Container>::bitvector(InputIterator first, InputIterator last)
- : mContainer(),
- mFreeBitCount(0)
- {
- assign(first, last);
- }
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // global operators
- ///////////////////////////////////////////////////////////////////////
-
- template <typename Allocator, typename Element, typename Container>
- inline bool operator==(const bitvector<Allocator, Element, Container>& a,
- const bitvector<Allocator, Element, Container>& b)
- {
- // To do: Replace this with a smart compare implementation. This is much slower than it needs to be.
- return ((a.size() == b.size()) && eastl::equal(a.begin(), a.end(), b.begin()));
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- inline bool operator!=(const bitvector<Allocator, Element, Container>& a,
- const bitvector<Allocator, Element, Container>& b)
- {
- return !operator==(a, b);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- inline bool operator<(const bitvector<Allocator, Element, Container>& a,
- const bitvector<Allocator, Element, Container>& b)
- {
- // To do: Replace this with a smart compare implementation. This is much slower than it needs to be.
- return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- inline bool operator>(const bitvector<Allocator, Element, Container>& a,
- const bitvector<Allocator, Element, Container>& b)
- {
- return b < a;
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- inline bool operator<=(const bitvector<Allocator, Element, Container>& a,
- const bitvector<Allocator, Element, Container>& b)
- {
- return !(b < a);
- }
-
-
- template <typename Allocator, typename Element, typename Container>
- inline bool operator>=(const bitvector<Allocator, Element, Container>& a,
- const bitvector<Allocator, Element, Container>& b)
- {
- return !(a < b);
- }
-
- template <typename Allocator, typename Element, typename Container>
- inline void swap(bitvector<Allocator, Element, Container>& a,
- bitvector<Allocator, Element, Container>& b)
- {
- a.swap(b);
- }
-
-
-} // namespace eastl
-
-
-EA_RESTORE_VC_WARNING();
-
-#endif // Header include guard