import java.util.NoSuchElementException;
import java.util.Iterator;

public class SimpleTreeSet<E extends Comparable<? super E>> implements Iterable<E>{
    private TreeNode<E> root;
    private int nodeCount = 0;
    
    public SimpleTreeSet() {
        this.root = null;
    }
    
    public int size() {
        return this.nodeCount;
    }
    
    public void clear() {
        this.root = null;
        this.nodeCount = 0;
    }
    
    public boolean contains(E value) {
        return (BST.findNode(this.root, value) != null);
    }
    
    public boolean add(E value) {
        if (this.contains(value)) {
            return false;
        }
        
        this.root = BST.add(this.root, value);
        this.nodeCount++;
        return true;
    }
    
    public boolean remove(E value) {
        if (!this.contains(value)) {
            return false;
        }
        
        root = BST.remove(root, value);
        this.nodeCount--;
        return true;
    }

    public E first() {
        if (this.root == null) {
            throw new NoSuchElementException();
        }
        
        return BST.firstNode(this.root).getData();
    }

    public E last() {
        if (this.root == null) {
            throw new NoSuchElementException();
        }
        
        return BST.lastNode(this.root).getData();
    }

    public String toString() {
        return BST.toString(this.root);
    }
 
    private class TreeIterator implements Iterator<E> {
        private TreeNode<E> nextNode;
        
        public TreeIterator() {
            this.nextNode = BST.firstNode(SimpleTreeSet.this.root);
        }
        
        public boolean hasNext() {
            return this.nextNode != null;    
        }
        
        public E next() {
           if (!this.hasNext()) {
               throw new NoSuchElementException();
           }
           
           E returnValue = this.nextNode.getData();
                      
           if (this.nextNode.getRight() != null) {
               this.nextNode = BST.firstNode(this.nextNode.getRight());
           }
           else {
               TreeNode<E> parent = null;
               TreeNode<E> stepper = SimpleTreeSet.this.root;
               while (stepper != this.nextNode) {
                   if (this.nextNode.getData().compareTo(stepper.getData()) < 0) {
                       parent = stepper;
                       stepper = stepper.getLeft();
                   }
                   else {
                       stepper = stepper.getRight();
                   }
               }
               this.nextNode = parent;
           }
           
           return returnValue;
        }
        
        public void remove() {
            // TO BE IMPLEMENTED
        }
    }
    
   public Iterator<E> iterator() {
       return new TreeIterator();
   }
}