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

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

#ifndef _BitList_h_included_
#define _BitList_h_included_

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

namespace sps
{
	/*! \brief Implementation of the BitSet interface based on a linked list.
		
		In this implementation of the BitSet interface the data is stored in a
		sorted linked list, each node consisting of an offset and an integer
		for storing the actual bits. Values in the range of \f$(0;2^n-1)\f$ can
		be stored, where n is the machine word length of your system. E.g. for
		a 32 bit system the highest possible value is \f$2^{32}-1\f$ and each
		node can store 32 bits.

		Due to the fact that this implementation is based on a sorted linked list
		the methods Add, Remove and Contains have all a runtime in O(n), rather
		the average runtime is proportional to n/2. The runtime of the Union, 
		Intersect and Difference methods are all in O(n).

		\sa
			- sps::BitTree
			- sps::DenseBitVector
			- sps::SparseBitVector
			- sps::RiceSet
		\sa
	*/
	class BitList
	{
	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::list< Node > TBitsList;

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

				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::BitList.

				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 BitList* m_pBitList;
			TBitsList::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(n). Where n is the number of nodes
			in the list.

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

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

			Example:
			\code
				BitList 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
				BitList 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 BitList& 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 lists.

			Example:
			\code
				BitList 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 BitList& 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 lists.

			Example:
			\code
				BitList 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 BitList& 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 lists.

			Example:
			\code
				BitList 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 BitList& 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 list.

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

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

	protected:
		// Linear search starting from rIt, returns true
		// if nOffset was found, rIt contains the result.
		bool FindNode( TBitsList::iterator& rIt, size_t nOffset );

		// Linear search starting from rIt, returns true
		// if nOffset was found, rIt contains the result.
		bool FindNode( TBitsList::const_iterator& rIt, size_t nOffset ) const;

	
		TBitsList m_listBits;
	};

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

		TBitsList::iterator it = m_listBits.begin();
		if ( FindNode( it, nOffset ) )
		{
			it->m_nBits |= nMask;
		}
		else
		{
			m_listBits.insert( it, Node( nOffset, nMask ) );
		}
	}

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

		TBitsList::iterator it = m_listBits.begin();
		if ( FindNode( it, nOffset ) )
		{
			it->m_nBits &= ~nMask;
			if ( it->m_nBits == 0 )
			{
				m_listBits.erase( it );
			}
		}
	}

	inline bool BitList::IsEmpty() const
	{
		return m_listBits.empty();
	}

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

		TBitsList::const_iterator it = m_listBits.begin();
		if ( FindNode( it, nOffset ) )
		{
			return ( it->m_nBits & nMask ) != 0;
		}

		return false;
	}

	inline bool BitList::IsEqual( const BitList& rOther ) const
	{
		return m_listBits == rOther.m_listBits;
	}

	inline void BitList::Union( const BitList& rOther )
	{
		TBitsList::const_iterator itOther = rOther.m_listBits.begin();
		TBitsList::const_iterator endOther = rOther.m_listBits.end();
		TBitsList::iterator itSelf = m_listBits.begin();

		for ( ; itOther != endOther; ++itOther )
		{
			if ( FindNode( itSelf, itOther->m_nOffset ) )
			{
				itSelf->m_nBits |= itOther->m_nBits;
			}
			else
			{
				m_listBits.insert( itSelf, *itOther );
			}
		}
	}

	inline void BitList::Intersect( const BitList& rOther )
	{
		TBitsList::iterator itSelf = m_listBits.begin();
		TBitsList::iterator endSelf = m_listBits.end();
		TBitsList::const_iterator itOther = rOther.m_listBits.begin();

		while ( itSelf != endSelf )
		{
			if ( rOther.FindNode( itOther, itSelf->m_nOffset ) )
			{
				itSelf->m_nBits &= itOther->m_nBits;
				if ( itSelf->m_nBits != 0 )
				{
					++itSelf;
					continue;
				}
			}

			itSelf = m_listBits.erase( itSelf );
		}
	}

	inline void BitList::Difference( const BitList& rOther )
	{
		TBitsList::iterator itSelf = m_listBits.begin();
		TBitsList::iterator endSelf = m_listBits.end();
		TBitsList::const_iterator itOther = rOther.m_listBits.begin();

		while ( itSelf != endSelf )
		{
			if ( rOther.FindNode( itOther, itSelf->m_nOffset ) )
			{
				itSelf->m_nBits &= ~itOther->m_nBits;
				if ( itSelf->m_nBits == 0 )
				{
					itSelf = m_listBits.erase( itSelf );
					continue;
				}
			}

			++itSelf;
		}
	}

	inline void BitList::Clear()
	{
		m_listBits.clear();
	}

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

	inline bool BitList::FindNode( TBitsList::iterator& rIt, size_t nOffset )
	{
		bool bFound = false;
		
		for ( ; rIt != m_listBits.end() ; ++rIt )
		{
			if ( nOffset <= rIt->m_nOffset )
			{
				bFound = nOffset == rIt->m_nOffset;
				break;
			}
		}
		
		return bFound;
	}

	inline bool BitList::FindNode( TBitsList::const_iterator& rIt, size_t nOffset ) const
	{
		bool bFound = false;
		
		for ( ; rIt != m_listBits.end() ; ++rIt )
		{
			if ( nOffset <= rIt->m_nOffset )
			{
				bFound = nOffset == rIt->m_nOffset;
				break;
			}
		}
		
		return bFound;
	}

	///////////////////////////////////////////////////////////////////////////
	// BitList::Iterator implementation
	///////////////////////////////////////////////////////////////////////////

	inline BitList::Iterator::Iterator()
	: m_pBitList( NULL )
	, m_nBit( 0 )
	{
	}

	inline BitList::Iterator::Iterator( const BitList& rBitList )
	: m_pBitList( &rBitList )
	, m_itCurrent( rBitList.m_listBits.end() )
	, m_nBit( 0 )
	{
	}

	inline bool BitList::Iterator::HasMoreElements() const
	{
		return m_itCurrent != m_pBitList->m_listBits.end();
	}

	inline void BitList::Iterator::Begin()
	{
		m_nBit = 0;
		m_itCurrent = m_pBitList->m_listBits.begin();
		if ( m_itCurrent != m_pBitList->m_listBits.end() && ( m_itCurrent->m_nBits & ( 1 << m_nBit ) ) == 0 )
		{
			Next();
		}
	}

	inline void BitList::Iterator::Next()
	{
		if ( m_itCurrent == m_pBitList->m_listBits.end() )
		{
			return;
		}

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

	inline size_t BitList::Iterator::operator*() const
	{
		if ( m_itCurrent == m_pBitList->m_listBits.end() )
		{
			return -1;
		}

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

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

#endif //_BitList_h_included_