// File:            bitset.cpp
// ----------------------------------------------------------------------
// Author:          Computer Science S-111 staff
// Modified by:     Russell Lowke, lowke@fas.harvard.edu
// TF:              Francis Crick
// Date modified:   7/24/2002
// Version:			1
//
// Description:
//     Implementation of the bitset class, which can be used to represent 
//     sets containing integer values from 0 to some maximum value.
//
// Computer Science S-111, Harvard University
//

#include <cassert>
#include <cstring>
#include <iostream>
#include "bitset.hpp"


////////////////////////
////  PRIVATE METHODS





// Russell 7/24/2002
//
// adds values i through j to a set
//
void
bitset::include(int i, int j)
{
	int low = i, high = j;
	
	// assert valid values for i and j
	assert(i >= 0);
	assert(j >= 0);
	assert(i <= size);
	assert(j <= size);

	if (i > j) {		// check high parameter
		high = i;		// and assign
		low  = j;
	}
	
	// set values via standard include
	for (int counter = low; counter <= high; counter++) {
		include(counter);
	}
}

// Russell 7/24/2002
//
// returns the number of members
//
int
bitset::cardinality()
{
	int memberCount = 0;
	
    for (int i = 0 ; i < size; i++) {
		if (member(i)) {			// count each member
	    	memberCount++;
	    }
    }
    
	return memberCount;
}

// Russell 7/24/2002
//
// inverts all bits in a set
//
void
bitset::invert()
{
    for (int i = 0 ; i < size; i++) {
		if (member(i)) {
	    	exclude(i);				// exclude those found
	    } else {
	    	include(i);				// include those missing
	    }
    }
}


//
// set_bit: sets to 1 the bit at the given offset from the start of
// the bits array.
//
void
bitset::set_bit(int offset)
{
    // Determine the correct byte and the correct bit within that byte.
    int q = offset / 8;
    int r = offset % 8;

    bits[q] |= (1 << r);
}

//
// get_bit: returns the value of the bit at the given offset from
// the start of the bits array. 
//
bool
bitset::get_bit(int offset) const
{
    // Determine the correct byte and the correct bit within that byte.
    int q = offset / 8;
    int r = offset % 8;

    return (bits[q] & (1 << r));
}

//
// clear_bit: clears the bit at the given offset from the start of the
// bits array.
//
void
bitset::clear_bit(int offset)
{
    // Determine the correct byte and the correct bit within that byte.
    int q = offset / 8;
    int r = offset % 8;

    bits[q] &= ((1 << r) ^ 255);
}


///////////////////////
////  PUBLIC METHODS

//
// Default constructor
//
bitset::bitset()
{
    size = 0;
    bits = NULL;
    nbyte = 0;
}

//
// Primary constructor
//
bitset::bitset(int size)
{
    bits = NULL;
    set_size(size);
}


// Russell 7/24/2002
//
// constructs a set of size s, 
// in which elemets i through j inclusive are in the set
//
bitset::bitset(int s, int i, int j)
{
	bits = NULL;
    set_size(s);
	include(i, j);
}


//
// Copy constructor -- performs a *deep* copy
//
bitset::bitset(const bitset& seta)
{
    size = seta.size;
    nbyte = seta.nbyte;
    bits = new char[nbyte];

    for (int i = 0; i < nbyte; i++)
	bits[i] = seta.bits[i];
}

//
// Destructor
//
bitset::~bitset()
{
    if (bits != NULL)
	delete [] bits;
    bits = NULL;
}

//
// clear: clears all bits in the bitset, creating the empty set
//
void
bitset::clear()
{
    assert(bits != NULL);
    for (int i = 0; i < nbyte; i++)
	bits[i] = 0;
}

//
// set_size: initializes or resizes a set, clearing it of any old
// contents and creating the empty set
//
void
bitset::set_size(int s)
{
    assert(s > 0);

    // If there's an existing array, free the memory allocated for it.
    if (bits != NULL)
	delete [] bits;

    size = s;
    nbyte = (size + 7)/8;
    bits = new char[nbyte];

    clear();
}

//
// include: adds the specified value to the set
//
void
bitset::include(int value)
{
    assert(value >= 0  &&  value < size);
    set_bit(value);
}

//
// exclude: removes the specified value from the set
//
void
bitset::exclude(int value)
{
	assert(value >= 0  &&  value < size);
	clear_bit(value);
}


//
// member: determines whether the specified value is in the set
//
bool
bitset::member(int value) const
{
    if (value < 0  ||  value >= size)
	return false;

    //
    // Will return 1 (true) if the value is in the set, and 0 (false)
    // if the value is not in the set.
    //
    return (get_bit(value));
}


//
// is_null: tests if the set is empty
//
bool
bitset::is_null() const
{
    for (int i = 0; i < nbyte; i++)
	if (bits[i] != 0)
	    return false;

    // If we've made it here, all of the bytes are empty.
    return true;
}


////////////////////////////
////  OVERLOADED OPERATORS


// Russell 7/24/2002
//
// returns bool indicating whether the first parameter is a subset 
// of the second.  By convention, any set is a subset of itself,
// and the null set is a subset of any set
//								  	
bool operator < ( const bitset& seta, const bitset& setb)
{	
	if ( seta.bits == NULL ) {
		return true;						// null subset (uninitialized)
	} else if ( seta.is_null() ) {
		return true;						// null subset (initialized)
		
	} else if ( seta.size > setb.size ) {	// ensure subset smaller
		return false;
	} else {
		
		for (int i = 0 ; i < seta.size; i++) {
		
			if ( seta.member(i) && ! setb.member(i) ) {
				return false;
			}
		
			/* Old code for use when member() is not const
			q = i / 8;
			r = i % 8;
		
			if ( (seta.bits[q] & (1 << r)) && // check these bits
			   ! (setb.bits[q] & (1 << r)) ) {
				return false;
		 	}
		 	*/
		}
	}
	
	return true;							// must be true
}
    
    
    
    
const bitset&
bitset::operator =(const bitset& seta)
{
    // Make sure not to erase a set when we try to assign it to itself.
    if (&seta != this) {
	// Reinitialize the set, possibly enlarging it.
	set_size(seta.size);

	// Copy the contents of each byte.
	for (int i = 0; i < seta.nbyte; i++)
	    bits[i] = seta.bits[i];
    }
    
    return *this;
}

//
// Note that the rest of the overloaded operators are friend functions,
// not member functions.
//

//
// set union
//
bitset
operator +(const bitset& seta, const bitset& setb)
{
    bitset temp;

    //
    // Begin by assigning the value of the larger of the two sets.
    // If one of the sets is bigger, then we won't have to touch
    // its extra bytes in the code below; they will automatically
    // be included.
    //
    temp = (seta.size > setb.size ? seta : setb);

    // Now OR the pairs of corresponding bytes from the two sets.
    int bytes_in_both = (seta.nbyte < setb.nbyte ? seta.nbyte : setb.nbyte);
    for (int i = 0; i < bytes_in_both; i++)
	temp.bits[i] = seta.bits[i] | setb.bits[i];

    return temp;
}

//
// set difference - create a set containing all elements that are
// in A and not in B
//
bitset
operator -(const bitset& seta, const bitset& setb)
{
    //
    // Start by including all of seta.  If seta is bigger than setb,
    // then we won't have to touch its extra bytes in the code below;
    // they will automatically be included.
    //
    bitset temp = seta;
    
    // Now perform set differences on the pairs of corresponding bytes.
    int bytes_in_both = (seta.nbyte < setb.nbyte ? seta.nbyte : setb.nbyte);
    for (int i = 0; i < bytes_in_both; i++)
	temp.bits[i] = seta.bits[i] & (setb.bits[i] ^ 255);

    return temp;
}

//
// set intersection
//
bitset
operator *(const bitset& seta, const bitset& setb)
{
    // The new bitset must be able to hold the larger of seta and setb.
    bitset temp(seta.size > setb.size ? seta.size : setb.size);

    // AND the pairs of corresponding bytes.
    int bytes_in_both = (seta.nbyte < setb.nbyte ? seta.nbyte : setb.nbyte);
    for (int i = 0; i < bytes_in_both; i++)
	temp.bits[i] = seta.bits[i] & setb.bits[i];

    return temp;
}

bool
operator ==(const bitset& seta, const bitset& setb)
{
    // Check that pairs of corresponding bytes match.
    int bytes_in_both = seta.nbyte < setb.nbyte ? seta.nbyte : setb.nbyte;
    for (int i = 0; i < bytes_in_both; i++)
        if (seta.bits[i] != setb.bits[i])
            return false;

    // If one set is larger, check its extra bytes.  If any of them
    // are non-empty, the sets don't match.
    if (seta.nbyte > bytes_in_both) {
	for (int i = bytes_in_both; i < seta.nbyte; i++)
	    if (seta.bits[i] != 0)
	        return false;
    }
    if (setb.nbyte > bytes_in_both) {
	for (int i = bytes_in_both; i < setb.nbyte; i++)
	    if (setb.bits[i] != 0)
	        return false;
    }

    return true;
}

istream&
operator >>(istream& is, bitset& s)
{  
    s.clear();

    do {
        int i;
        is >> i;
	if (i >= 0 && i < s.size)
	    s.include(i);
    } while (is.peek() != '\n');

    return is;
}

ostream&
operator <<(ostream& os, bitset s)
{  
    os << "{  ";
    for (int i = 0 ; i < s.size; i++) {
		if (s.member(i))
	    	os << i << "  ";
    }
    os << "}\n";

    return os;
}
