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

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

#ifndef _SparseBitVector_h_included_
#define _SparseBitVector_h_included_

#include "Helpers.h"
#include "Iterator.h"

#include <vector>

namespace sps
{
	/*! \brief Implementation of the BitSet interface based on a sparse vector.
		
		In this implementation of the BitSet interface the data is stored in a
		sorted dynamic vector. Each node of the vector consists of an offset
		and an integer to store the actual bits.
		
		The runtime of Add, Remove and Contains is always in O(lg(n)), where n 
		is the 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::DenseBitVector
			- sps::RiceSet
		\sa
	*/
	class SparseBitVector
	{
	protected:
		struct Node
		{
			Node( size_t nOffset, size_t nBits )
			: m_nOffset( nOffset )
			, m_nBits( nBits )
			{
			}

			bool operator==( const Node& rOther ) const
			{
				return m_nOffset == rOther.m_nOffset && m_nBits == rOther.m_nBits;
			}
			
			size_t m_nOffset;
			size_t m_nBits;
		};
		typedef std::vector< Node > TBitsVector;

	public:
		/*! \brief Implementation of the sps::Iterator interface for a sps::SparseBitVector. 
			
			Example: 
			\code
			sps::SparseBitVector set;
			sps::SparseBitVector::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 SparseBitVector& 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::SparseBitVector.

				This method should be called before any other method of the Iterator
				is called. 
				The runtime of Begin() is in O(1).
			*/
			virtual void Begin();
			
			/*! \brief Sets the iterator to the next bit in the  sps::SparseBitVector.

				Don't call this method if HasMoreElements() returned false. 
				The runtime of Next() is in O(1).
			*/
			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 SparseBitVector* m_pBitVector;
			TBitsVector::const_iterator m_itCurrent;
			size_t m_nBit;
		};

		friend class Iterator;

		/*! \brief Adds bit \c nBit to the set.
		
			The runtime of this method is in O(lg(n)). Where n is the number of nodes
			in the vector.

			Example:
			\code
				SparseBitVector 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(lg(n)). Where n is the number of nodes
			in the vector.

			Example:
			\code
				SparseBitVector 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(1). 

			Example:
			\code
				SparseBitVector 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(lg(n)). Where n is the number of nodes
			in the vector.

			Example:
			\code
				SparseBitVector 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 number of nodes
			in the list.

			Example:
			\code
				SparseBitVector 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 SparseBitVector& 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 number of nodes
			in the bigger of the two vectors.

			Example:
			\code
				SparseBitVector 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 SparseBitVector& 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 number of nodes
			in the bigger of the two vectors.

			Example:
			\code
				SparseBitVector 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 SparseBitVector& 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 number of nodes
			in the bigger of the two vectors.

			Example:
			\code
				SparseBitVector 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 SparseBitVector& 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
			of the vector.

			Example:
			\code
				SparseBitVector 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::SparseBitVector::Iterator for the members of this set is returned.
			The runtime of this method is in O(1).

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

	protected:

		// Does a binary search for nOffset in m_arrBits.
		// The starting range (indices to m_arrBits) can be
		// defined using nLower and nUpper. rnResultIndex contains
		// the index to the result-node (if nOffset isn't found
		// the index to the next greater node).
		// Returns true if nOffset is found, false otherwise.
		bool SparseBitVector::BinarySearch( 
			size_t& rnResultIndex, 
			size_t nLower, 
			size_t nUpper, 
			size_t nOffset 
		) const;

		TBitsVector m_arrBits;
	};


	inline void SparseBitVector::Add( size_t nBit )
	{
		size_t nOffset = nBit / sizeof_bits< size_t >();
		size_t nMask = 1 << ( nBit % sizeof_bits< size_t >() );

		size_t nIndex = 0;
		if ( BinarySearch( nIndex, 0, m_arrBits.size(), nOffset ) )
		{
			Node& rNode = m_arrBits[ nIndex ];
			rNode.m_nBits |= nMask;
		}
		else
		{
			m_arrBits.insert( m_arrBits.begin() + nIndex, Node( nOffset, nMask ) );
		}
	}

	inline void SparseBitVector::Remove( size_t nBit )
	{
		size_t nOffset = nBit / sizeof_bits< size_t >();
		size_t nMask = 1 << ( nBit % sizeof_bits< size_t >() );

		size_t nIndex = 0;
		if ( BinarySearch( nIndex, 0, m_arrBits.size(), nOffset ) )
		{
			TBitsVector::iterator it = m_arrBits.begin() + nIndex;
			
			Node& rNode = *it;
			rNode.m_nBits &= ~nMask;

			if ( rNode.m_nBits == 0 )
			{
				m_arrBits.erase( it );
			}
		}
	}

	inline bool SparseBitVector::IsEmpty() const
	{
		return m_arrBits.empty();
	}

	inline bool SparseBitVector::Contains( size_t nBit ) const
	{
		size_t nOffset = nBit / sizeof_bits< size_t >();
		size_t nMask = 1 << ( nBit % sizeof_bits< size_t >() );

		size_t nIndex = 0;
		if ( BinarySearch( nIndex, 0, m_arrBits.size(), nOffset ) )
		{
			return ( m_arrBits[ nIndex ].m_nBits & nMask ) != 0;
		}

		return false;
	}

	inline bool SparseBitVector::IsEqual( const SparseBitVector& rOther ) const
	{
		return m_arrBits == rOther.m_arrBits;
	}

	inline void SparseBitVector::Union( const SparseBitVector& rOther )
	{
		TBitsVector::const_iterator itOther = rOther.m_arrBits.begin();
		TBitsVector::const_iterator endOther = rOther.m_arrBits.end();
		size_t nIndexSelf = 0;

		for ( ; itOther != endOther; ++itOther )
		{
			if ( BinarySearch( nIndexSelf, nIndexSelf, m_arrBits.size(), itOther->m_nOffset ) )
			{
				m_arrBits[ nIndexSelf ].m_nBits |= itOther->m_nBits;
			}
			else
			{
				m_arrBits.insert( m_arrBits.begin() + nIndexSelf, *itOther );
			}
		}
	}

	inline void SparseBitVector::Intersect( const SparseBitVector& rOther )
	{
		TBitsVector::iterator itSelf = m_arrBits.begin();
		size_t nIndexOther = 0;

		while ( itSelf != m_arrBits.end() )
		{
			if ( rOther.BinarySearch( nIndexOther, nIndexOther, rOther.m_arrBits.size(), itSelf->m_nOffset ) )
			{
				itSelf->m_nBits &= rOther.m_arrBits[ nIndexOther ].m_nBits;
				if ( itSelf->m_nBits != 0 )
				{
					++itSelf;
					continue;
				}
			}

			itSelf = m_arrBits.erase( itSelf );
		}
	}

	inline void SparseBitVector::Difference( const SparseBitVector& rOther )
	{
		TBitsVector::iterator itSelf = m_arrBits.begin();
		size_t nIndexOther = 0;

		while ( itSelf != m_arrBits.end() )
		{
			if ( rOther.BinarySearch( nIndexOther, nIndexOther, rOther.m_arrBits.size(), itSelf->m_nOffset ) )
			{
				itSelf->m_nBits &= ~rOther.m_arrBits[ nIndexOther ].m_nBits;
				if ( itSelf->m_nBits == 0 )
				{
					itSelf = m_arrBits.erase( itSelf );
					continue;
				}
			}

			++itSelf;
		}
	}

	inline void SparseBitVector::Clear()
	{
		m_arrBits.clear();
	}

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

	inline bool SparseBitVector::BinarySearch( 
		size_t& rnResultIndex, 
		size_t nLower, 
		size_t nUpper, 
		size_t nOffset 
	) const
	{
		rnResultIndex = ( nLower + nUpper ) / 2;

		while ( nLower < nUpper )
		{
			const Node& rNode = m_arrBits[ rnResultIndex ];

			if ( nOffset < rNode.m_nOffset )
			{
				nUpper = rnResultIndex;
			}
			else if ( nOffset > rNode.m_nOffset )
			{
				nLower = rnResultIndex + 1;
			}
			else
			{
				return true;
			}
			
			rnResultIndex = ( nLower + nUpper ) / 2;
		}
		
		return false;
	}

	///////////////////////////////////////////////////////////////////////////
	// SparseBitVector::Iterator implementation
	///////////////////////////////////////////////////////////////////////////
	inline SparseBitVector::Iterator::Iterator()
	: m_pBitVector( NULL )
	, m_nBit( 0 )
	{
	}

	inline SparseBitVector::Iterator::Iterator( const SparseBitVector& rBitVector )
	: m_pBitVector( &rBitVector )
	, m_itCurrent( rBitVector.m_arrBits.end() )
	, m_nBit( 0 )
	{
	}

	inline bool SparseBitVector::Iterator::HasMoreElements() const
	{
		return m_pBitVector && m_itCurrent != m_pBitVector->m_arrBits.end();
	}

	inline void SparseBitVector::Iterator::Begin()
	{
		if ( !m_pBitVector )
		{
			return;
		}

		m_nBit = 0;
		m_itCurrent = m_pBitVector->m_arrBits.begin();
		if ( m_itCurrent != m_pBitVector->m_arrBits.end() && ( m_itCurrent->m_nBits & ( 1 << m_nBit ) ) == 0 )
		{
			Next();
		}
	}

	inline void SparseBitVector::Iterator::Next()
	{
		if ( !m_pBitVector || m_itCurrent == m_pBitVector->m_arrBits.end() )
		{
			return;
		}

		do
		{
			++m_nBit;
			if ( m_nBit >= sizeof_bits< size_t >() )
			{
				m_nBit = 0;
				++m_itCurrent;
			}
		} while ( m_itCurrent != m_pBitVector->m_arrBits.end() && ( m_itCurrent->m_nBits & ( 1 << m_nBit ) ) == 0 );
	}

	inline size_t SparseBitVector::Iterator::operator*() const
	{
		if ( m_itCurrent == m_pBitVector->m_arrBits.end() )
		{
			return -1;
		}

		return m_itCurrent->m_nOffset * sizeof_bits< size_t >() + m_nBit;
	}

	inline SparseBitVector::Iterator& SparseBitVector::Iterator::operator=( const SparseBitVector::Iterator& rOther )
	{
		m_itCurrent = rOther.m_itCurrent;
		m_nBit = rOther.m_nBit;
		m_pBitVector = rOther.m_pBitVector;
		return *this;
	}
}

#endif //_SparseBitVector_h_included_