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

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

#ifndef _RiceSet_h_included_
#define _RiceSet_h_included_

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

#include <vector>

namespace sps
{
	/// Implementation of the BitSet interface based on the method of Preston
	/// Briggs and Linda Torczon (Rice University) - ACM Letters on Programming
	/// Languages and Sy<stems, Vol. 2, Nos. 1-4, March-December 1993, Pages 
	/// 59-69.
	
	/*! \brief Implementation of the BitSet interface based on the sparse set representation 
		by Preston Briggs and Linda Torczon (Rice University).

		The sparse set representation was published in "ACM Letters on Programming
		Languages and Systems", Vol. 2, Nos. 1-4, March-December 1993, Pages 59-69.

		Two vectors - a sparse and a dense one - are used to store the members of the
		set. Each node of the sparse vector links to a node of the dense vector and vice versa.

		The method of Briggs and Torczon is explicitly designed for a fixed size universy, and 
		thus static vectors can be used as underlying data structures. To achieve compatibility
		to the other BitSet implementations and to satisfy the requirements of the actual
		use case for the BitSets implemented in this library, the original method was changed
		to use dynamic vectors as underlying data structure. This has an negative impact on
		the performance.

		The runtime of Remove and Contains is in O(1). The runtime of Add is in O(1) if no
		vector resizing is necessary, in O(v) (where v is the value of the member) otherwise.
		The Intersect and Difference methods have all runtime in O(n) (where n is the
		number of members in the set). The Union method has also a runtime of O(n), but only
		if no resizing is necessary, in the worst case the runtime is in O(v*n) where v is
		the biggest value added to the set.

		\sa
			- sps::BitList
			- sps::BitTree
			- sps::DenseBitVector
			- sps::SparseBitVector
		\sa
	*/
	class RiceSet
	{
	public:
		/*! \brief Implementation of the sps::Iterator interface for a sps::RiceSet. 
			
			Example: 
			\code
			sps::RiceSet set;
			sps::RiceSet::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 rRiceset. 
			*/
			Iterator( const RiceSet& rRiceSet );
			
			/*! \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::RiceSet.

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

				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 RiceSet* m_pRiceSet;
			size_t m_nIndex;
		};

		friend class Iterator;

		RiceSet();

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

			Example:
			\code
				RiceSet 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
				RiceSet 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
				RiceSet 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
				RiceSet 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 set.

			Example:
			\code
				RiceSet 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 RiceSet& 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 sets.

			Example:
			\code
				RiceSet 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 RiceSet& 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 sets.

			Example:
			\code
				RiceSet 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 RiceSet& 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 sets.

			Example:
			\code
				RiceSet 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 RiceSet& rOther );

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

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

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

	protected:
		typedef std::vector< size_t > TIndexVector;



		TIndexVector m_arrSparseVector;
		TIndexVector m_arrDenseVector;
		size_t m_nMembers;
	};

	inline RiceSet::RiceSet()
	: m_nMembers( 0 )
	{
	}

	inline void RiceSet::Add( size_t nBit )
	{
		if ( !Contains( nBit ) )
		{
			if ( m_arrSparseVector.size() <= m_nMembers + 1 )
			{
				m_arrSparseVector.resize( m_nMembers + 1 );
			}
			m_arrSparseVector[ m_nMembers ] = nBit;
			if ( m_arrDenseVector.size() <= nBit + 1 )
			{
				m_arrDenseVector.resize( nBit + 1 );
			}
			m_arrDenseVector[ nBit ] = m_nMembers;
			++m_nMembers;
		}
	}

	inline void RiceSet::Remove( size_t nBit )
	{
		if ( Contains( nBit ) )
		{
			--m_nMembers;
			size_t nSparseIndex = m_arrDenseVector[ nBit ];
			if ( nSparseIndex < m_nMembers )
			{
				m_arrSparseVector[ nSparseIndex ] = m_arrSparseVector[ m_nMembers ];
				m_arrDenseVector[ m_arrSparseVector[ nSparseIndex ] ] = nSparseIndex;
			}
		}
	}

	inline bool RiceSet::IsEmpty() const
	{
		return m_nMembers == 0;
	}

	inline bool RiceSet::Contains( size_t nBit ) const
	{
		if ( m_arrDenseVector.size() > nBit )
		{
			size_t nSparseIndex = m_arrDenseVector[ nBit ];
			if ( nSparseIndex < m_nMembers )
			{
				return m_arrSparseVector[ nSparseIndex ] == nBit;
			}
		}
		return false;
	}

	inline bool RiceSet::IsEqual( const RiceSet& rOther ) const
	{
		if ( m_nMembers == rOther.m_nMembers )
		{
			Iterator it = GetIterator();
			for ( it.Begin(); it.HasMoreElements(); it.Next() )
			{
				if ( !rOther.Contains( *it ) )
				{
					return false;
				}
			}
			return true;
		}
		return false;
	}

	inline void RiceSet::Union( const RiceSet& rOther )
	{
		Iterator itOther = rOther.GetIterator();
		for ( itOther.Begin(); itOther.HasMoreElements(); itOther.Next() )
		{
			Add( *itOther );
		}
	}

	inline void RiceSet::Intersect( const RiceSet& rOther )
	{
		size_t nIndex = 0;
		while ( nIndex < m_nMembers )
		{
			size_t nBit = m_arrSparseVector[ nIndex ];
			if ( !rOther.Contains( nBit ) )
			{
				Remove( nBit );
			}
			else
			{
				++nIndex;
			}
		}
	}

	inline void RiceSet::Difference( const RiceSet& rOther )
	{
		Iterator itOther = rOther.GetIterator();
		for ( itOther.Begin(); itOther.HasMoreElements(); itOther.Next() )
		{
			Remove( *itOther );
		}
	}

	inline void RiceSet::Clear()
	{
		m_nMembers = 0;
	}

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


	///////////////////////////////////////////////////////////////////////////
	// RiceSet::Iterator implementation
	///////////////////////////////////////////////////////////////////////////
	inline RiceSet::Iterator::Iterator()
	: m_pRiceSet( NULL )
	, m_nIndex( 0 )
	{
	}

	inline RiceSet::Iterator::Iterator( const RiceSet& rRiceSet )
	: m_pRiceSet( &rRiceSet )
	, m_nIndex( 0 )
	{
	}

	inline bool RiceSet::Iterator::HasMoreElements() const
	{
		return m_pRiceSet && m_nIndex < m_pRiceSet->m_nMembers;
	}

	inline void RiceSet::Iterator::Begin()
	{
		m_nIndex = 0;
	}

	inline void RiceSet::Iterator::Next()
	{
		++m_nIndex;
	}

	inline size_t RiceSet::Iterator::operator*() const
	{
		if ( !m_pRiceSet || m_nIndex >= m_pRiceSet->m_nMembers )
		{
			return -1;
		}
		return m_pRiceSet->m_arrSparseVector[ m_nIndex ];
	}

	inline RiceSet::Iterator& RiceSet::Iterator::operator=( const RiceSet::Iterator& rOther )
	{
		m_pRiceSet = rOther.m_pRiceSet;
		m_nIndex = rOther.m_nIndex;
		return *this;
	}
}

#endif //_RiceSet_h_included_