/*
*	 Template class of super bitset in terms of stl::bitset
*    Copyright (C) 2007  Stone
*
*    This program is free software: you can redistribute it and/or modify
*    it under the terms of the GNU General Public License as published by
*    the Free Software Foundation, either version 3 of the License, or
*    (at your option) any later version.
*
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*
*    You should have received a copy of the GNU General Public License
*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*
*    Contact me by stoneyrh@163.com 
*
*/
#ifndef _SPBITSET_H
#define _SPBITSET_H


#include <bitset>
#include <string>
#include <iostream>

using std::bitset;
using std::string;
using std::basic_istream;
using std::basic_ostream;

template <size_t _Bits>
class spbitset
{
public:
	//friend functions
	template <class _Elem,class _Traits> friend basic_ostream<_Elem,_Traits>& operator<<(basic_ostream<_Elem,_Traits>& os,const spbitset<_Bits>& bs)
	{
		os << bs.set;
		return os;
	}
	template <class _Elem,class _Traits> friend basic_istream<_Elem,_Traits>& operator>>(basic_istream<_Elem,_Traits>& is,spbitset<_Bits>& bs)
	{
		is >> bs.set;
		return is;
	}

public:
	typedef bitset<_Bits> set_t;
	
	spbitset(unsigned _int64 val)
	{
		set = (unsigned _int32)(val >> 32);
		set <<= 32;
		set |= (unsigned _int32)val;
	}

	spbitset(const spbitset<_Bits>& rhs)
	{
		set = rhs.set;
	}

	~spbitset()
	{
	}

	const set_t& getset() const
	{
		return set;
	}

	spbitset<_Bits> operator<<(size_t pos) const
	{
		return (spbitset<_Bits>(*this) <<= pos);
	}

	spbitset<_Bits>& operator<<=(size_t pos)
	{
		set <<= pos;
		return *this;
	}

	spbitset<_Bits> operator>>(size_t pos) const
	{
		return (spbitset<_Bits>(*this) >>= pos);
	}

	spbitset<_Bits>& operator>>=(size_t pos)
	{
		set >>= pos;
		return *this;
	}

	spbitset<_Bits> operator^(const spbitset<_Bits>& rhs)
	{
		return (spbitset<_Bits>(*this) ^= rhs);
	}

	spbitset<_Bits>& operator^=(const spbitset<_Bits>& rhs)
	{
		set ^= rhs.set;
		return *this;
	}

	spbitset<_Bits>& operator=(const spbitset<_Bits>& rhs)
	{
		if (this != &rhs)
		{
			set = rhs.set;
		}
		return *this;
	}

	spbitset<_Bits> operator|(const spbitset<_Bits>& rhs)
	{
		return (spbitset<_Bits>(*this) |= rhs);
	}

	spbitset<_Bits>& operator|=(const spbitset<_Bits>& rhs)
	{
		set |= rhs.set;
		return *this;
	}

	spbitset<_Bits> operator&(const spbitset<_Bits>& rhs)
	{
		return (spbitset<_Bits>(*this) &= rhs);
	}

	spbitset<_Bits>& operator&=(const spbitset<_Bits>& rhs)
	{
		set &= rhs.set;
		return *this;
	}

	/*
	* set specified bit to specified value
	*/
	void setbit(size_t pos,bool bit)
	{
		set.set(pos,bit);
	}

	/*
	* get the value of specified bit
	*/
	bool getbit(size_t pos)
	{
		return set.test(pos);
	}

	/*
	* rotate shift left for one bit on bits between [pos1,pos2]
	*/
	void rotate_shift_left(size_t pos1,size_t pos2)
	{
		size_t lm = pos1 > pos2 ? pos2 : pos1;
		size_t rm = pos1 > pos2 ? pos1 : pos2;
		bool lbit = getbit(lm);
		for (size_t i = lm + 1; i <= rm; ++ i)
		{
			setbit(i - 1,getbit(i));
		}
		setbit(rm,lbit);
	}

	/*
	* rotate shift left for count bit on bits between [pos1,pos2]
	*/
	void rotate_shift_left(size_t pos1,size_t pos2,size_t count)
	{
		for (size_t i = 0; i < count; ++ i)
		{
			rotate_shift_left(pos1,pos2);
		}
	}

	/*
	* rotate shift right for count bit on bits between [pos1,pos2]
	*/
	void rotate_shift_right(size_t pos1,size_t pos2,size_t count)
	{
		for (size_t i = 0; i < count; ++ i)
		{
			rotate_shift_right(pos1,pos2);
		}
	}

	/*
	* rotate shift right for one bit on bits between [pos1,pos2]
	*/
	void rotate_shift_right(size_t pos1,size_t pos2)
	{
		size_t lm = pos1 > pos2 ? pos2 : pos1;
		size_t rm = pos1 > pos2 ? pos1 : pos2;
		bool rbit = getbit(rm);
		for (size_t i = rm - 1; i >= lm; -- i)
		{
			setbit(i + 1,getbit(i));
		}
		setbit(lm,rbit);
	}

	/*
	* rearrange bits according to the position array
	* pointed by poses
	*/
	void extract(size_t* poses,size_t count)
	{
		spbitset<_Bits> ns(*this);
		for (size_t i = 0; i < count; ++ i)
		{
			setbit(i,ns.getbit(poses[i] - 1));
		}
	}

	/*
	* turn the bits to unsigned _int64 value 
	* which has the same bits with the set
	* if the bits is more than or less than 64
	* it will cut it or pad it automatically
	*/
	unsigned _int64 to_ulonglong()
	{
		string ts = set.to_string();

		string::size_type tl = ts.length();
		//if less than 64 bits, pad it
		//if more than 64 bits, cut it
		//the high part is the front part

		if (tl > 64)
		{
			ts = ts.substr(tl - 64,64);
		}
		else if (tl < 64)
		{
			ts.insert(0,64 - tl,'0');
		}
		
		unsigned _int32 lo = (bitset<32>(ts.substr(32,32))).to_ulong();
		unsigned _int32 hi = (bitset<32>(ts.substr(0,32))).to_ulong();

		unsigned _int64 ull = hi;
		ull <<= 32;
		ull |= lo;
		return ull;
	}

private:
	set_t set;
};

#endif