/******************************************************************************
* Compilation: javac SET.java
* Execution: java SET
* Dependencies: StdOut.java
*
* Set implementation using Java's TreeSet library.
* Does not allow duplicates.
*
* % java SET
* 128.112.136.11
* 208.216.181.15
* null
*
******************************************************************************/
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.TreeSet;
/**
* The {@code SET} class represents an ordered set of comparable keys.
* It supports the usual add, contains, and delete
* methods. It also provides ordered methods for finding the minimum,
* maximum, floor, and ceiling and set methods
* for union, intersection, and equality.
*
* Even though this implementation include the method {@code equals()}, it
* does not support the method {@code hashCode()} because sets are mutable.
*
* This implementation uses a balanced binary search tree. It requires that
* the key type implements the {@code Comparable} interface and calls the
* {@code compareTo()} and method to compare two keys. It does not call either
* {@code equals()} or {@code hashCode()}.
* The add, contains, delete, minimum,
* maximum, ceiling, and floor methods take
* logarithmic time in the worst case.
* The size, and is-empty operations take constant time.
* Construction takes constant time.
*
* For additional documentation, see
* Section 3.5 of
* Algorithms in Java, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*
* @param the generic type of each key in this set
*/
public class SET> implements Iterable {
private TreeSet set;
/**
* Initializes an empty set.
*/
public SET() {
set = new TreeSet();
}
/**
* Initializes a new set that is an independent copy of the specified set.
*
* @param x the set to copy
*/
public SET(SET x) {
set = new TreeSet(x.set);
}
/**
* Adds the key to this set (if it is not already present).
*
* @param key the key to add
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public void add(Key key) {
if (key == null) throw new IllegalArgumentException("called add() with a null key");
set.add(key);
}
/**
* Returns true if this set contains the given key.
*
* @param key the key
* @return {@code true} if this set contains {@code key};
* {@code false} otherwise
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public boolean contains(Key key) {
if (key == null) throw new IllegalArgumentException("called contains() with a null key");
return set.contains(key);
}
/**
* Removes the specified key from this set (if the set contains the specified key).
* This is equivalent to {@code remove()}, but we plan to deprecate {@code delete()}.
*
* @param key the key
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("called delete() with a null key");
set.remove(key);
}
/**
* Removes the specified key from this set (if the set contains the specified key).
* This is equivalent to {@code delete()}, but we plan to deprecate {@code delete()}.
*
* @param key the key
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public void remove(Key key) {
if (key == null) throw new IllegalArgumentException("called remove() with a null key");
set.remove(key);
}
/**
* Returns the number of keys in this set.
*
* @return the number of keys in this set
*/
public int size() {
return set.size();
}
/**
* Returns true if this set is empty.
*
* @return {@code true} if this set is empty;
* {@code false} otherwise
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns all of the keys in this set, as an iterator.
* To iterate over all of the keys in a set named {@code set}, use the
* foreach notation: {@code for (Key key : set)}.
*
* @return an iterator to all of the keys in this set
*/
public Iterator iterator() {
return set.iterator();
}
/**
* Returns the largest key in this set.
*
* @return the largest key in this set
* @throws NoSuchElementException if this set is empty
*/
public Key max() {
if (isEmpty()) throw new NoSuchElementException("called max() with empty set");
return set.last();
}
/**
* Returns the smallest key in this set.
*
* @return the smallest key in this set
* @throws NoSuchElementException if this set is empty
*/
public Key min() {
if (isEmpty()) throw new NoSuchElementException("called min() with empty set");
return set.first();
}
/**
* Returns the smallest key in this set greater than or equal to {@code key}.
*
* @param key the key
* @return the smallest key in this set greater than or equal to {@code key}
* @throws IllegalArgumentException if {@code key} is {@code null}
* @throws NoSuchElementException if there is no such key
*/
public Key ceiling(Key key) {
if (key == null) throw new IllegalArgumentException("called ceiling() with a null key");
Key k = set.ceiling(key);
if (k == null) throw new NoSuchElementException("all keys are less than " + key);
return k;
}
/**
* Returns the largest key in this set less than or equal to {@code key}.
*
* @param key the key
* @return the largest key in this set table less than or equal to {@code key}
* @throws IllegalArgumentException if {@code key} is {@code null}
* @throws NoSuchElementException if there is no such key
*/
public Key floor(Key key) {
if (key == null) throw new IllegalArgumentException("called floor() with a null key");
Key k = set.floor(key);
if (k == null) throw new NoSuchElementException("all keys are greater than " + key);
return k;
}
/**
* Returns the union of this set and that set.
*
* @param that the other set
* @return the union of this set and that set
* @throws IllegalArgumentException if {@code that} is {@code null}
*/
public SET union(SET that) {
if (that == null) throw new IllegalArgumentException("called union() with a null argument");
SET c = new SET();
for (Key x : this) {
c.add(x);
}
for (Key x : that) {
c.add(x);
}
return c;
}
/**
* Returns the intersection of this set and that set.
*
* @param that the other set
* @return the intersection of this set and that set
* @throws IllegalArgumentException if {@code that} is {@code null}
*/
public SET intersects(SET that) {
if (that == null) throw new IllegalArgumentException("called intersects() with a null argument");
SET c = new SET();
if (this.size() < that.size()) {
for (Key x : this) {
if (that.contains(x)) c.add(x);
}
}
else {
for (Key x : that) {
if (this.contains(x)) c.add(x);
}
}
return c;
}
/**
* Compares this set to the specified set.
*
* Note that this method declares two empty sets to be equal
* even if they are parameterized by different generic types.
* This is consistent with the behavior of {@code equals()}
* within Java's Collections framework.
*
* @param other the other set
* @return {@code true} if this set equals {@code other};
* {@code false} otherwise
*/
@Override
public boolean equals(Object other) {
if (other == this) return true;
if (other == null) return false;
if (other.getClass() != this.getClass()) return false;
SET that = (SET) other;
return this.set.equals(that.set);
}
/**
* This operation is not supported because sets are mutable.
*
* @return does not return a value
* @throws UnsupportedOperationException if called
*/
@Override
public int hashCode() {
throw new UnsupportedOperationException("hashCode() is not supported because sets are mutable");
}
/**
* Returns a string representation of this set.
*
* @return a string representation of this set, enclosed in curly braces,
* with adjacent keys separated by a comma and a space
*/
@Override
public String toString() {
String s = set.toString();
return "{ " + s.substring(1, s.length() - 1) + " }";
}
/**
* Unit tests the {@code SET} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
SET set = new SET();
StdOut.println("set = " + 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("ceiling(www.simpsonr.com) = " + set.ceiling("www.simpsonr.com"));
StdOut.println("ceiling(www.simpsons.com) = " + set.ceiling("www.simpsons.com"));
StdOut.println("ceiling(www.simpsont.com) = " + set.ceiling("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();
StdOut.println("set = " + set);
StdOut.println();
// print out all keys in this set in lexicographic order
for (String s : set) {
StdOut.println(s);
}
StdOut.println();
SET set2 = new SET(set);
StdOut.println(set.equals(set2));
}
}