// @(#)$Id: Set.C,v 1.3 1999/04/11 15:57:37 leavens Exp $

#include "Set.h"

// In this implemenation we have the following stronger rep invariant
// than claimed in the header file:
//     notNull(elems) /\ len(*elems) = size(A(*elems))
// so that there are no duplicates in the rep.

template <class T>
Set<T>::Set() throw()
 : elems(new Nil<T>())
{
}

template <class T>
Set<T>::Set(T e) throw() 
 : elems(new ImmutableList<T>(e, new Nil<T>())) 
{
}

template <class T>
void Set<T>::add(T e) throw() {
  if (!member(e)) {
    elems = new ImmutableList<T>(e, elems);
  }
}

template <class T>
void Set<T>::remove(T e) throw() {
  remove1st(elems, e);
}
 
template <class T>
bool Set<T>::member(T e) const throw() {
  return member(e, elems);
}

template <class T>
int Set<T>::size() const throw() {
  return elems->length();
}

template <class T>
bool Set<T>::isEmpty() const throw() {
  return elems->is_null();
}

template <class T>
T Set<T>::ident(choose)() const throw() {
  return elems->head();
}

template <class T>
bool subset(const Set<T>& s1, const Set<T>& s2) throw() {
  Set<T> s = s1;  // copy s1
  while (!isEmpty(s)) {
    T e = s.ident(choose)();
    if (!s2.member(e)) {
      return false;
    }
    s.remove(e);
  }
  return true;
}
  
template <class T>
bool operator == (const Set<T>& s1, const Set<T>& s2) throw() {
  return subset(s1, s2) && subset(s2, s1);
}

template <class T>
Set<T>& union_of(const Set<T>& s1, const Set<T>& s2) throw() {
  Set<T>& ret = *(new Set<T>(s2)); // allocate a new set that is a copy of s2
  Set<T> s = s1;  // copy s1
  while (!isEmpty(s)) {
    T e = s.ident(choose)();
    ret.add(e);
  }
  return ret;
}