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 add, contains, and delete
* methods. It also provides ordered methods for finding the minimum,
* maximum, floor, and ceiling.
*
* This implementation uses a balanced binary search tree.
* The add, contains, delete, minimum,
* maximum, ceiling, and floor methods take
* logarithmic time.
*
* For additional documentation, see Section 4.5 of
* Algorithms in Java, 4th Edition by Robert Sedgewick and Kevin Wayne.
*/
public class SET> implements Iterable {
private final TreeSet 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 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 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 head = set.headSet(k);
if (head.isEmpty()) return null;
else return head.last();
}
/**
* Return the union of this set with that set.
*/
public SET union(SET that) {
SET 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 intersects(SET that) {
SET 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 that = (SET) 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 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);
}
}
}