/*! \file DenseBitVector.h
	\brief Declaration and implementation of the sps::DenseBitVector class. 

	Include this file if you want to use the sps::DenseBitVector class.
	
	\sa
	- BitList.h
	- BitTree.h
	- SparseBitVector.h
	- RiceSet.h
	\sa
*/

#ifndef _DenseBitVector_h_included_
#define _DenseBitVector_h_included_

#include "Helpers.h"
#include "Iterator.h"
#include <vector>

namespace sps
{
	/*! \brief Implementation of the BitSet interface based on a dynamic vector.
		
		In this implementation of the BitSet interface the data is stored in a
		simple dynamic vector. Each node of the vector holds an integer to
		store 32/64 bit (depending on the machine word length of your system).
		The position of each node in the vector is used to calculate the offset.
		E.g. for storing the single value of 32767, 1024 nodes are needed, 1023
		beeing empty (on 32 bit system).
		
		The runtime of Remove and Contains is always in O(1), the runtime of
		Add is in O(1) if no resizing of the vector is needed in O(n) otherwise,
		where n is the new size of the vector. The runtime of Union, Intersect
		and Difference is in O(n) where n is the vector size of the bigger of
		the two sets.

		\sa
			- sps::BitList
			- sps::BitTree
			- sps::SparseBitVector
			- sps::RiceSet
		\sa
	*/
	class DenseBitVector
	{
	public:
		/*! \brief Implementation of the sps::Iterator interface for a sps::DenseBitVector.
			
			Example: 
			\code
			sps::DenseBitVector set;
			sps::DenseBitVector::Iterator it = set.GetIterator();
			for ( it.Begin(); it.HasMoreElement(); it.Next() )
			{
				cout << *it << ", ";
			}
			\endcode
		*/
		class Iterator : public sps::Iterator
		{
		public:
			Iterator();

			/*! \brief Constructs an iterator for rBitVector. 
			*/
			Iterator( const DenseBitVector& rBitVector );
			
			/*! \brief Checks if there are elements left. 

				If this method returns true it's save to call operator*() and Next().
				The runtime of this method is in O(1).
			*/
			virtual bool HasMoreElements() const;
			
			/*! \brief Sets the iterator on the first bit in the sps::DenseBitVector.

				This method should be called before any other method of the Iterator
				is called. 
				In the worst case the runtime of Begin() is in O(n), where n is the
				vector size.
			*/
			virtual void Begin();
			
			/*! \brief Sets the iterator to the next bit in the sps::DenseBitVector.

				Don't call this method if HasMoreElements() returned false. 
				In the worst case the runtime of Begin() is in O(n), where n is the
				vector size.
			*/
			virtual void Next();
			
			/*! \brief Returns the current value(bit) the iterator points to.

				Don't call this method if HasMoreElements() returned false. 
				The runtime of operator*() is in O(1).
			*/
			virtual size_t operator*() const;

			/*! \brief Overwrites this instance of Iterator with a copy of \c rOther. 
			
				The runtime of this method is in O(1). 
			*/
			Iterator& operator=( const Iterator& rOther );

		private:
			const DenseBitVector* m_pBitVector;
			size_t m_nIndex;
			bool m_bEnd;
		};

		friend class Iterator;

		/*! \brief Adds bit \c nBit to the set.
		
			The runtime of this method is in O(1) if no resizing is necessary, in O(n) otherwise,
			where n is the new vector size.

			Example:
			\code
				DenseBitVector set;
				set.Add(3);
				set.Add(42); // the set now contains the elements 3, 42
			\endcode
		*/
		void Add( size_t nBit );

		/*! \brief Removes bit \c nBit from the set.
		
			The runtime of this method is in O(1).

			Example:
			\code
				DenseBitVector set;
				set.Add(3);
				set.Add(42); 
				set.Remove(3); // the set now contains only the element 42
			\endcode
		*/
		void Remove( size_t nBit );

		/*! \brief Checks if the set is empty.
		
			Returns true if the set contains no elements, false otherwise.
			The runtime of this method is in O(n), where n is the vector size.

			Example:
			\code
				DenseBitVector set;
				set.IsEmpty(); // will return true
				set.Add(3);
				set.Add(42); 
				set.IsEmpty(); // will return false
			\endcode
		*/
		bool IsEmpty() const;

		/*! \brief Checks if bit \c nBit is a member of the set.
		
			Returns true if the set contains \c nBit, false otherwise.
			The runtime of this method is in O(1).

			Example:
			\code
				DenseBitVector set;
				set.Add(3);
				set.Add(42); 
				set.Contains(42); // will return true
			\endcode
		*/
		bool Contains( size_t nBit ) const;

		/*! \brief Checks the two sets for equalness.
		
			Returns true if \c this and \c rOther contain exactly the same bits, false otherwise.
			The runtime of this method is in O(n). Where n is the vector size.

			Example:
			\code
				DenseBitVector set1, set2;
				set1.Add(3);
				set1.Add(42); 

				set2.Add(3);
				set1.IsEqual(set2); // will return false

				set2.Add(42);
				set1.IsEqual(set2); // will return true
			\endcode
		*/
		bool IsEqual( const DenseBitVector& rOther ) const;

		/*! \brief Builds the union of the two sets in place.
		
			The result set (\c this) will contain all bits that are set in \c this
			\b or in \c rOther.
			The runtime of this method is in O(n). Where n is the vector size.

			Example:
			\code
				DenseBitVector set1, set2;
				set1.Add(3);
				set1.Add(42); 

				set2.Add(3);
				set2.Add(43);

				set1.Union(set2); // set1 now contains 3, 42 and 43
			\endcode
		*/
		void Union( const DenseBitVector& rOther );

		/*! \brief Builds the intersection of the two sets in place.
		
			The result set (\c this) will contain all bits that are set in \c this
			\b and in \c rOther.
			The runtime of this method is in O(n). Where n is the vector size.

			Example:
			\code
				DenseBitVector set1, set2;
				set1.Add(3);
				set1.Add(42); 

				set2.Add(3);
				set2.Add(43);

				set1.Intersect(set2); // set1 now contains only 3
			\endcode
		*/
		void Intersect( const DenseBitVector& rOther );

		/*! \brief Builds the difference of the two sets in place.
		
			The result set (\c this) will contain all bits that are set in \c this
			\b and \b not set in \c rOther.
			The runtime of this method is in O(n). Where n is the vector size.

			Example:
			\code
				DenseBitVector set1, set2;
				set1.Add(3);
				set1.Add(42); 

				set2.Add(3);
				set2.Add(43);

				set1.Difference(set2); // set1 now contains only 42
			\endcode
		*/
		void Difference( const DenseBitVector& rOther );

		/*! \brief Clears the set.
		
			The result set (\c this) will be empty.
			The runtime of this method is in O(n). Where n is the number of nodes
			in the vector.

			Example:
			\code
				DenseBitVector set;
				set.Add(3);
				set.Add(42); 
				set.Clear(); // set is now empty
			\endcode
		*/
		void Clear();

		/*! \brief Creates an iterator for the set.
		
			An sps::DenseBitVector::Iterator for the members of this set is returned.
			The runtime of this method is in O(1).

			Example:
			\code
				DenseBitVector set;
				set.Add(3);
				set.Add(42); 
				DenseBitVector::Iterator it = set.GetIterator();
				for(it.Begin(); it.HasMoreElement(); it.Next() )
				{
					cout << *it << endl; 
				}
			\endcode
		*/
		Iterator GetIterator() const;

	protected:
		typedef std::vector< size_t > TBitsVector;
		TBitsVector m_arrBitsVector;
	};

	inline void DenseBitVector::Add( size_t nBit )
	{
		TBitsVector::size_type nIndex = nBit / sizeof_bits< size_t >();
		size_t nMask = 1 << ( nBit % sizeof_bits< size_t >() );

		if ( nIndex >= m_arrBitsVector.size() )
		{
			m_arrBitsVector.resize( nIndex + 1, 0 );
		}

		m_arrBitsVector[ nIndex ] |= nMask;
	}

	inline void DenseBitVector::Remove( size_t nBit )
	{
		TBitsVector::size_type nIndex = nBit / sizeof_bits< size_t >();
		size_t nMask = 1 << ( nBit % sizeof_bits< size_t >() );

		if ( nIndex < m_arrBitsVector.size() )
		{
			m_arrBitsVector[ nIndex ] &= ~nMask;
		}
	}

	inline bool DenseBitVector::IsEmpty() const
	{
		TBitsVector::const_iterator it = m_arrBitsVector.begin();
		TBitsVector::const_iterator itEnd = m_arrBitsVector.end();
		for ( ; it != itEnd; ++it )
		{
			if ( *it )
			{
				return false;
			}
		}
		return true;
	}

	inline bool DenseBitVector::Contains( size_t nBit ) const
	{
		TBitsVector::size_type nIndex = nBit / sizeof_bits< size_t >();
		size_t nMask = 1 << ( nBit % sizeof_bits< size_t >() );

		if ( nIndex < m_arrBitsVector.size() )
		{
			return ( m_arrBitsVector[ nIndex ] & nMask ) != 0;
		}

		return false;
	}

	inline bool DenseBitVector::IsEqual( const DenseBitVector& rOther ) const
	{
		TBitsVector::const_iterator it = m_arrBitsVector.begin();
		TBitsVector::const_iterator itEnd = m_arrBitsVector.end();
		TBitsVector::const_iterator itOther = m_arrBitsVector.begin();
		TBitsVector::const_iterator itOtherEnd = m_arrBitsVector.end();
		for ( ; ( it != itEnd && itOther != itOtherEnd ); ++it, ++itOther )
		{
			if ( *it != *itOther )
			{
				return false;
			}
		}

		for ( ; it != itEnd; ++it )
		{
			if ( *it )
			{
				return false;
			}
		}

		for ( ; itOther != itOtherEnd; ++it )
		{
			if ( *itOther )
			{
				return false;
			}
		}

		return true;
	}

	inline void DenseBitVector::Union( const DenseBitVector& rOther )
	{
		TBitsVector::const_iterator itOther = rOther.m_arrBitsVector.begin();
		TBitsVector::const_iterator endOther = rOther.m_arrBitsVector.end();
		TBitsVector::iterator itSelf = m_arrBitsVector.begin();
		TBitsVector::iterator endSelf = m_arrBitsVector.end();

		for ( ; ( itOther != endOther && itSelf != endSelf ) ; ++itOther, ++itSelf )
		{
			*itSelf |= *itOther;
		}

		for ( ; itOther != endOther; ++itOther )
		{
			m_arrBitsVector.push_back( *itOther );
		}
	}

	inline void DenseBitVector::Intersect( const DenseBitVector& rOther )
	{
		TBitsVector::const_iterator itOther = rOther.m_arrBitsVector.begin();
		TBitsVector::const_iterator endOther = rOther.m_arrBitsVector.end();
		TBitsVector::iterator itSelf = m_arrBitsVector.begin();
		TBitsVector::iterator endSelf = m_arrBitsVector.end();

		for ( ; ( itOther != endOther && itSelf != endSelf ) ; ++itOther, ++itSelf )
		{
			*itSelf &= *itOther;
		}

		m_arrBitsVector.erase( itSelf, endSelf );
	}

	inline void DenseBitVector::Difference( const DenseBitVector& rOther )
	{
		TBitsVector::const_iterator itOther = rOther.m_arrBitsVector.begin();
		TBitsVector::const_iterator endOther = rOther.m_arrBitsVector.end();
		TBitsVector::iterator itSelf = m_arrBitsVector.begin();
		TBitsVector::iterator endSelf = m_arrBitsVector.end();

		for ( ; ( itOther != endOther && itSelf != endSelf ) ; ++itOther, ++itSelf )
		{
			*itSelf &= ~( *itOther );
		}
	}

	inline void DenseBitVector::Clear()
	{
		m_arrBitsVector.clear();
	}

	inline DenseBitVector::Iterator DenseBitVector::GetIterator() const
	{
		return DenseBitVector::Iterator( *this );
	}


	///////////////////////////////////////////////////////////////////////////
	// DenseBitVector::Iterator implementation
	///////////////////////////////////////////////////////////////////////////

	inline DenseBitVector::Iterator::Iterator()
	: m_pBitVector( NULL )
	, m_nIndex( 0 )
	, m_bEnd( true )
	{
	}

	inline DenseBitVector::Iterator::Iterator( const DenseBitVector& rBitVector )
	: m_pBitVector( &rBitVector )
	, m_nIndex( 0 )
	, m_bEnd( true )
	{
	}

	inline bool DenseBitVector::Iterator::HasMoreElements() const
	{
		return !m_bEnd;
	}

	inline void DenseBitVector::Iterator::Begin()
	{
		m_nIndex = 0;
		m_bEnd = false;
		if ( !m_pBitVector->Contains( m_nIndex ) )
		{
			Next();
		}
	}

	inline void DenseBitVector::Iterator::Next()
	{
		m_bEnd = true;

		while ( m_nIndex / sizeof_bits< size_t >() < m_pBitVector->m_arrBitsVector.size() )
		{
			++m_nIndex;
			
			if ( m_nIndex == 0 )
			{
				break;
			}
			
			if ( m_pBitVector->Contains( m_nIndex ) )
			{
				m_bEnd = false;
				break;
			}
		}
	}

	inline size_t DenseBitVector::Iterator::operator*() const
	{
		return m_nIndex;
	}

	inline DenseBitVector::Iterator& DenseBitVector::Iterator::operator=( const Iterator& rOther )
	{
		m_bEnd = rOther.m_bEnd;
		m_nIndex = rOther.m_nIndex;
		m_pBitVector = rOther.m_pBitVector;
		return *this;
	}
}

#endif //_DenseBitVector_h_included_