/****************************************************************************** * 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)); } }