/**
 * Class representing sets of integers.
 * <p>CompSci 431: Homework #7 Solution
 * @author John Tang Boyland
 */
class IntSet {

  private Node root;

  /** Create an empty set of integers.
   */
  public IntSet() {
    root = null;
  }

  // NB: we avoid recursion for the most part.

  /** Determine whether the integer is in the set.
   * @param n integer to look up
   * @return true if in set
   */
  public boolean find(int n) {
    Node r = root;
    while (r != null) {
      if (r.key == n) return true;
      if (r.key < n) r = r.right;
      else r = r.left;
    }
    return false;
  }

  /** Add an integer to the set.
   * @param n integer to add to this set.
   */
  public void add(int n) {
    if (root == null) {
      root = new Node(n);
      return;
    }
    Node r = root;
    Node lag = null;
    while (r != null) {
      lag = r;
      if (r.key == n) return; // already in set
      if (r.key < n) r = r.right;
      else r = r.left;
    }
    if (lag.key < n) lag.right = new Node(n);
    else lag.left = new Node(n);
  }

  /** Return a string representation of the set.
   * It is a brace delimited, comma-separate series of numbers.
   * @return string for set
   */
  public String toString() {
    if (root == null) return "{}";
    return "{" + root + "}";
  }

  // This node class is treated for the most part as
  // a mere "structure"
  private class Node {
    public int key;
    public Node left, right;

    /** Create a Node with empty left and right subtrees
     * and the given key.
     * @param k key to insert in new node
     */
    public Node(int k) {
      key = k;
      left = right = null;
    }

    /** Return a comma-separated series of numbers. */
    public String toString() {
      return (left == null ? "" : left.toString()+",") +
	key + (right == null ? "" : ","+right.toString());
    }
  }
}