package sets;

import java.util.Iterator;

public class LinkedSet<E> implements Set<E> {
  private LinkedNode<E> head = null;

  // Constructors
  public LinkedSet() {
  }

  public LinkedSet(E e) {
    this.head = new LinkedNode<E>(e, null);
  }

  private LinkedSet(LinkedNode<E> head) {
    this.head = head;
  }

  // size : returns the number of elements in the set
  // consumes nothing and produces an int
  @Override
  public int size() {
	  int iterations = 0;
	  Iterator<E> iter = iterator() ;
	  while (iter.hasNext()) {
		  iterations++ ;
	  }
	  return iterations;
  }

  // isEmpty() : Returns true if this set contains no elements.
  // consumes nothing and produces a boolean
  @Override
  public boolean isEmpty() {
	return (head == null) ;
  }

  // iterator() : Returns an iterator over the elements in this set.
  // consumes nothing and produces an Iterator<E>
  @Override
  public Iterator<E> iterator() {
    return new LinkedNodeIterator<E>(this.head);
  }

  // contains() : Returns true if this set contains the specified element.
  // consumes an object and produces a boolean
  @Override
  public boolean contains(Object o) {
	Iterator<E> iter = iterator() ;
	boolean answer = false ;
	while (iter.hasNext()) {
		if (iter.next().equals(o)) {
			answer = true ;
		}
	}
    return answer ;
  }

  // isSubset() : Returns true if this set is a subset (or equal to) the given set.
  // consumes a Set<E> and produces a boolean
  @Override
  public boolean isSubset(Set<E> that) {
	boolean answer = true ;
	Iterator<E> iter = iterator();
	while (iter.hasNext()) {
		if (!that.contains(iter.next())) answer = false ;
	}
    return answer ;
  }

  // isSuperset() : Returns true if this set is a superset (or equal to) the given set
  // consumes a Set<E> and produces a boolean
  @Override
  public boolean isSuperset(Set<E> that) {
	boolean answer = true ;
    return that.isSubset(this) ;
  }

  // adjoin(): Returns a new Set containing all of the elements of this set and
  // also the specified new element.  If the specified element is
  // already in the set then returns the original Set.
  // consumes an object E and produces a set
  @Override
  public Set<E> adjoin(E e) {
	  LinkedSet<E> set = new LinkedSet(head) ;
	  if (contains(e)) return set ;
	  else {
		  LinkedNode<E> addition = new LinkedNode(e, head) ;
		  set = new LinkedSet(addition) ;
		  return set ;
	  }
  }

  // union() : Returns a new <code>Set</code> that is the union of <code>this Set</code> and <code>that Set</code>.
  // consumes a set and produces a set
  @Override
  public Set<E> union(Set<E> that) {
	Iterator<E> iter = that.iterator() ;
	LinkedSet<E> set = new LinkedSet(this.head) ;
	while(iter.hasNext()) {
		set = (LinkedSet<E>) set.adjoin(iter.next()) ;
	}
    return set;
  }

  // intersect() : Returns a new <code>Set</code> that is the intersection of <code>this Set</code> and <code>that Set</code>.
  // consumes a set and produces a set
  @Override
  public Set<E> intersect(Set<E> that) {
	Iterator<E> iter = iterator() ;
	LinkedSet<E> set = null ;
	if (isSubset(that)) {
		set = this ;
	}
	else if (isSuperset(that)) {
		set = (LinkedSet<E>) that ;
	}
	else {
		while (iter.hasNext()) {
			E temp = iter.next() ;
			if (that.contains(temp)) {
				if (set == null){
					set = new LinkedSet<E>(temp) ;
				}
				set = (LinkedSet<E>) set.adjoin(temp) ;
			}
		}
	}
    return set;
  }

  // subtract() : Returns a new <code>Set</code> that is the difference of
  // <code>this Set</code> and <code>that Set</code>, i.e., <code>
  // this - that</code>.
  // consumes a set and produces a set
  @Override
  public Set<E> subtract(Set<E> that) {
	  Iterator iter = iterator() ;
	  LinkedSet<E> set = new LinkedSet<E>() ;
	  if (!isSubset(that)) {
		  while (iter.hasNext()) {
			  E element = (E) iter.next() ;
			  if (!that.contains(element)) {
				  set = (LinkedSet<E>) set.adjoin(element) ;
			  }
		  }
	  }
	  return set ;
  }

  // remove() : Returns a new <code>Set</code> that is the same as
  // <code>this</code> except that it does not contain the specified
  // element.
  // consumes an object e and produces a set
  @Override
  public Set<E> remove(E e) {
	Iterator iter = iterator() ;
	LinkedSet<E> set = null ;
	while (iter.hasNext()) {
		E temp = (E) iter.next();
		if (!temp.equals(e)) {
			if (set == null){
				set = new LinkedSet<E>(temp) ;
			}
			set = (LinkedSet<E>) set.adjoin(temp) ;
		}
	}
    return set;
  }

  @Override
  @SuppressWarnings("unchecked")
  public boolean equals(Object o) {
    if (! (o instanceof Set)) {
      return false;
    }
    Set<E> that = (Set<E>)o;
    return this.isSubset(that) && that.isSubset(this);
  }

  @Override
    public int hashCode() {
    int result = 0;
    for (E e : this) {
      result += e.hashCode();
    }
    return result;
  }
}