package algs35;
import stdlib.*;
import java.util.Iterator;
import java.util.Objects;
import java.util.SortedSet;
import java.util.TreeSet;
/* ***********************************************************************
 *  Compilation:  javac SET.java
 *  Execution:    java SET
 *
 *  Set implementation using Java's TreeSet library.
 *  Does not allow duplicates.
 *
 *  % java SET
 *  128.112.136.11
 *  208.216.181.15
 *  null
 *
 *  Remarks
 *  -------
 *   - The equals() method declares two empty sets to be equal
 *     even if they are parameterized by different generic types.
 *     This is consistent with the way equals() works with Java's
 *     Collections framework.
 *
 *************************************************************************/

/**
 *  The {@code SET} class represents an ordered set. It assumes that
 *  the elements are {@code Comparable}.
 *  It supports the usual <em>add</em>, <em>contains</em>, and <em>delete</em>
 *  methods. It also provides ordered methods for finding the <em>minimum</em>,
 *  <em>maximum</em>, <em>floor</em>, and <em>ceiling</em>.
 *  <p>
 *  This implementation uses a balanced binary search tree.
 *  The <em>add</em>, <em>contains</em>, <em>delete</em>, <em>minimum</em>,
 *  <em>maximum</em>, <em>ceiling</em>, and <em>floor</em> methods take
 *  logarithmic time.
 *  <p>
 *  For additional documentation, see <a href="/algs4/45applications">Section 4.5</a> of
 *  <i>Algorithms in Java, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 */

public class SET<K extends Comparable<? super K>> implements Iterable<K> {
  private final TreeSet<K> set;

  /**
   * Create an empty set.
   */
  public SET() {
    set = new TreeSet<>();
  }

  /**
   * Is this set empty?
   */
  public boolean isEmpty() { return set.isEmpty(); }

  /**
   * Add the key to this set.
   */
  public void add(K key) { set.add(key); }

  /**
   * Does this set contain the given key?
   */
  public boolean contains(K key) { return set.contains(key); }

  /**
   * Delete the given key from this set.
   */
  public void delete(K key) { set.remove(key); }

  /**
   * Return the number of keys in this set.
   */
  public int size() { return set.size(); }

  /**
   * Return an Iterator for this set.
   */
  public Iterator<K> iterator() { return set.iterator(); }

  /**
   * Return the key in this set with the maximum value.
   */
  public K max() { return set.last(); }

  /**
   * Return the key in this set with the minimum value.
   */
  public K min() { return set.first(); }

  /**
   * Return the smallest key in this set {@code >= k}.
   */
  public K ceil(K k) {
    SortedSet<K> tail = set.tailSet(k);
    if (tail.isEmpty()) return null;
    else return tail.first();
  }

  /**
   * Return the largest key in this set {@code <= k}.
   */
  public K floor(K k) {
    if (set.contains(k)) return k;

    // does not include key if present (!)
    SortedSet<K> head = set.headSet(k);
    if (head.isEmpty()) return null;
    else return head.last();
  }

  /**
   * Return the union of this set with that set.
   */
  public SET<K> union(SET<K> that) {
    SET<K> c = new SET<>();
    for (K x : this) { c.add(x); }
    for (K x : that) { c.add(x); }
    return c;
  }

  /**
   * Return the intersection of this set with that set.
   */
  public SET<K> intersects(SET<K> that) {
    SET<K> c = new SET<>();
    if (this.size() < that.size()) {
      for (K x : this) {
        if (that.contains(x)) c.add(x);
      }
    }
    else {
      for (K x : that) {
        if (this.contains(x)) c.add(x);
      }
    }
    return c;
  }

  /**
   * Does this SET equal that set.
   */
  @SuppressWarnings("unchecked")
  public boolean equals(Object y) {
    if (y == this) return true;
    if (y == null) return false;
    if (y.getClass() != this.getClass()) return false;
    SET<K> that = (SET<K>) y;
    if (this.size() != that.size()) return false;
    try {
      for (K k : this)
        if (!that.contains(k)) return false;
    }
    catch (ClassCastException exception) {
      return false;
    }
    return true;
  }

  // must override hashcode if you override equals
  // See Item 9 of Effective Java (2e) by Joshua Block
  // This code based on java.util.AbstractMap.java
  public int hashCode() {
    int h = 0;
    for (K k : this)
      h = 31*h + Objects.hashCode(k);
    return h;
  }

  /**
   * String represenation of this set.
   */
  public String toString() {
    StringBuilder s = new StringBuilder();
    for (K key : this)
      s.append(key + " ");
    return s.toString();
  }

  /* *********************************************************************
   * Test routine.
   **********************************************************************/
  public static void main(String[] args) {
    SET<String> set = new SET<>();


    // insert some keys
    set.add("www.cs.princeton.edu");
    set.add("www.cs.princeton.edu");    // overwrite old value
    set.add("www.princeton.edu");
    set.add("www.math.princeton.edu");
    set.add("www.yale.edu");
    set.add("www.amazon.com");
    set.add("www.simpsons.com");
    set.add("www.stanford.edu");
    set.add("www.google.com");
    set.add("www.ibm.com");
    set.add("www.apple.com");
    set.add("www.slashdot.com");
    set.add("www.whitehouse.gov");
    set.add("www.espn.com");
    set.add("www.snopes.com");
    set.add("www.movies.com");
    set.add("www.cnn.com");
    set.add("www.iitb.ac.in");


    StdOut.println(set.contains("www.cs.princeton.edu"));
    StdOut.println(!set.contains("www.harvardsucks.com"));
    StdOut.println(set.contains("www.simpsons.com"));
    StdOut.println();

    StdOut.println("ceil(www.simpsonr.com) = " + set.ceil("www.simpsonr.com"));
    StdOut.println("ceil(www.simpsons.com) = " + set.ceil("www.simpsons.com"));
    StdOut.println("ceil(www.simpsont.com) = " + set.ceil("www.simpsont.com"));
    StdOut.println("floor(www.simpsonr.com) = " + set.floor("www.simpsonr.com"));
    StdOut.println("floor(www.simpsons.com) = " + set.floor("www.simpsons.com"));
    StdOut.println("floor(www.simpsont.com) = " + set.floor("www.simpsont.com"));
    StdOut.println();


    // print out all keys in the set in lexicographic order
    for (String s : set) {
      StdOut.println(s);
    }

  }

}