//
//	simplified implementation of bitset data type
//
//	Described in Chapter 12 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//

//
//	bitset
//		set of integer values
//		assumes 32 bit integers

# include <vector.h>

template <int N>
class bitset {
public:
		// constructors
	bitset() : data ((N+31)/32, 0) { }
	bitset (bitset<N> & b) : data (b.data) { }

		// bit level operations
	void flip 	();
	void flip 	(int index);
	void reset	();
	void reset	(int index);
	void set  	();
	void set  	(int index);
	bool test 	(int index);

		// bit testing operations
	bool any  	();
	bool none 	();
	int  count	();

		// set operations
	void operator |= (bitset<N> & rhs);
	void operator &= (bitset<N> & rhs);
	void operator ^= (bitset<N> & rhs);
	bool operator == (bitset<N> & rhs);

		// other operations
	void operator << (int);
	void operator >> (int);
	string to_string ();

protected:
	vector<int>	data;
	int	indexValue (int index) { return index / 32; }
	int	mask (int index) { return 1 << (index % 32); }
};

template <int N> void bitset<N>::set(int index) 
	// set (to 1) the given bit value
{
	data[indexValue(index)] |= mask(index);
}

template <int N> void bitset<N>::set() 
	// set all values to 1
{
	int n = data.size();
	for (int i = 0; i < n; i++)
		data[i] = ~ 0;
}

template <int N> bool bitset<N>::test (int index)
	// test the indicated bit position
{
	return 0 != (data[indexValue(index)] & mask(index));
}

template <int N> void bitset<N>::reset (int index)
	// reset (to zero) the corresponding bit value
{
	data[indexValue(index)] &= ~ mask(index); 
}

template <int N> void bitset<N>::reset ()
	// reset all values to zero
{
	int n = data.size();
	for (int i = 0; i < n; i++)
		data[i] = 0;
}


template <int N> void bitset<N>::flip (int index)
	// flip the corresponding bit value
{
	data[indexValue(index)]] ^= mask(index);
}

template <int N> void bitset<N>::flip ()
	// flip all values
{
	int n = data.size();
	for (int i = 0; i < n; i++)
		data[i] = ~ data[i];
}

template <int N> void bitset<N>::operator |= (bitset<N> & rhs)
	// form the union of set with argument set
{
	int n = data.size();
	for (int i = 0; i < n; i++)
		data[i] |= rhs.data[i];
}

template <int N> void bitset<N>::operator &= (bitset<N> & rhs)
	// form the intersection of set with argument set
{
	int n = data.size();
	for (int i = 0; i < n; i++)
		data[i] &= rhs.data[i];
}

template <int N> bool bitset<N>::operator == (bitset<N> & rhs)
	// test to see if two sets are the same
{
	// test to see if every position is equal to the argument
	int n = data.size();
	for (int i = 0; i < n; i++)
		if (data[i] != rhs.data[i])
			return false;

	// all equal, two sets the same
	return true;
}