// Set implementation
// Matt Perry (mjperry2@uiuc.edu)

#include "set.h"

Set::Set() {}

Set::Set(const Set& s) : elements(s.elements) {}

Set::iterator Set::begin()
{
    return elements.begin();
}

Set::const_iterator Set::begin() const
{
    return elements.begin();
}

Set::iterator Set::end()
{
    return elements.end();
}

Set::const_iterator Set::end() const
{
    return elements.end();
}

void Set::erase(iterator it)
{
    elements.erase(it);
}

void Set::clear()
{
    elements.clear();
}

int Set::size() const
{
    return elements.size();
}

// add an element to a set. if the element is a set itself, insert it in
// the set sorted by size of the element.
void Set::insert(const Element& e)
{
    iterator it;
    if (contains(e))
	return;

    if (e.type == Element::SET) {
        for (it = begin(); it != end(); it++) {
	    if ((*it).type == Element::SET && (*it).set->size() > e.set->size())
		break;
	}
    }
    else
	it = end();

    elements.insert(it, e);
}

bool Set::contains(const Element& e) const
{
    for (const_iterator it = begin(); it != end(); it++) {
	if (e == *it)
	    return true;
    }
    return false;
}

Set& Set::operator=(const Set& s)
{
    elements = s.elements;
    return *this;
}

const Element& Set::operator[](int n) const
{
    return elements[n];
}

// returns a set which is the union of two sets.
// first initialize the new set to the copy of one set, then add all
// elements from set b.
Set set_union(const Set& a, const Set& b)
{
    Set s(a);

    for (int i = 0; i < b.size(); i++) {
	s.insert(b[i]);
    }

    return s;
}

// returns a set which is the intersection of two sets.
// go through each element from a, and if it also exists in b, add it.
Set set_intersection(const Set& a, const Set& b)
{
    Set s;

    for (int i = 0; i < a.size(); i++) {
	if (b.contains(a[i]))
	    s.insert(a[i]);
    }

    return s;
}

// returns a set which is the difference of two sets.
// go through each element in a, and if it's not in b, add it.
Set set_difference(const Set& a, const Set& b)
{
    Set s;

    for (int i = 0; i < a.size(); i++) {
	if (!b.contains(a[i]))
	    s.insert(a[i]);
    }

    return s;
}

// returns a set which is the symmetric difference of two sets.
// go through a, adding all elements that do not also occur in b. then go
// through b, adding all elements that do not also occur in a.
Set set_symmetric_difference(const Set& a, const Set& b)
{
    Set s;

    for (int i = 0; i < a.size(); i++) {
	if (!b.contains(a[i]))
	    s.insert(a[i]);
    }
    for (int i = 0; i < b.size(); i++) {
	if (!a.contains(b[i]))
	    s.insert(b[i]);
    }

    return s;
}

// returns a set which is the powerset of a set.
// handled recursively, using 3 cases:
// the set has size 0: return the null set.
// the set has size 1: return the set containing the null set and the
//	original set itself.
// the set has size N>=2: create all possible sets of N-1 elements by
//	removing a single element from the original set.  then add the
//	powerset of each subset to the final set.  return the final set
//	when done.
Set set_powerset(const Set& s)
{
    Set p, t;
    Set::iterator it;

    if (s.size() == 0) {
	return Set();
    }
    if (s.size() == 1) {
	t.insert(s[0]);
	p.insert(Set());
	p.insert(t);
	return p;
    }

    for (int i = s.size()-1; i >= 0; i--) {
	for (int j = 0; j < s.size(); j++) {
	    if (j != i)
		t.insert(s[j]);
	}
	p = set_union(p, set_powerset(t));
	t.clear();
    }

    p.insert(s);

    return p;
}

// returns 1 if a is a subset of b, 0 otherwise.
// go through each element in a, and check if it's in b. if not, return 0.
int test_subset(const Set& a, const Set& b)
{
    for (int i = 0; i < a.size(); i++) {
	if (!b.contains(a[i]))
	    return 0;
    }
    return 1;
}

// returns 1 if a is a proper subset of b, 0 otherwise.
// if a is subset of b and differs in size, then it is a proper subset.
int test_proper_subset(const Set& a, const Set& b)
{
    if (test_subset(a, b) && a.size() != b.size())
	return 1;
    return 0;
}

// returns 1 if a an equal set to b, 0 otherwise.
// if a is a subset of b and has the same size, then it is equal.
int test_equal(const Set& a, const Set& b)
{
    if (test_subset(a, b) && a.size() == b.size())
	return 1;
    return 0;
}

// returns 1 if element e is in set s.
int test_in_set(const Element& e, const Set& s)
{
    return s.contains(e);
}

ostream& operator<<(ostream& os, const Set& s)
{
    Set::const_iterator it = s.begin();

    os << "{";

    if (it != s.end()) {
	os << *it;
	it++;
    }
    
    for (; it != s.end(); it++) {
	os << ", " << *it;
    }
    os << "}";

    return os;
}