001package algs35; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.Objects; 005import java.util.SortedSet; 006import java.util.TreeSet; 007/* *********************************************************************** 008 * Compilation: javac SET.java 009 * Execution: java SET 010 * 011 * Set implementation using Java's TreeSet library. 012 * Does not allow duplicates. 013 * 014 * % java SET 015 * 128.112.136.11 016 * 208.216.181.15 017 * null 018 * 019 * Remarks 020 * ------- 021 * - The equals() method declares two empty sets to be equal 022 * even if they are parameterized by different generic types. 023 * This is consistent with the way equals() works with Java's 024 * Collections framework. 025 * 026 *************************************************************************/ 027 028/** 029 * The {@code SET} class represents an ordered set. It assumes that 030 * the elements are {@code Comparable}. 031 * It supports the usual <em>add</em>, <em>contains</em>, and <em>delete</em> 032 * methods. It also provides ordered methods for finding the <em>minimum</em>, 033 * <em>maximum</em>, <em>floor</em>, and <em>ceiling</em>. 034 * <p> 035 * This implementation uses a balanced binary search tree. 036 * The <em>add</em>, <em>contains</em>, <em>delete</em>, <em>minimum</em>, 037 * <em>maximum</em>, <em>ceiling</em>, and <em>floor</em> methods take 038 * logarithmic time. 039 * <p> 040 * For additional documentation, see <a href="/algs4/45applications">Section 4.5</a> of 041 * <i>Algorithms in Java, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 042 */ 043 044public class SET<K extends Comparable<? super K>> implements Iterable<K> { 045 private final TreeSet<K> set; 046 047 /** 048 * Create an empty set. 049 */ 050 public SET() { 051 set = new TreeSet<>(); 052 } 053 054 /** 055 * Is this set empty? 056 */ 057 public boolean isEmpty() { return set.isEmpty(); } 058 059 /** 060 * Add the key to this set. 061 */ 062 public void add(K key) { set.add(key); } 063 064 /** 065 * Does this set contain the given key? 066 */ 067 public boolean contains(K key) { return set.contains(key); } 068 069 /** 070 * Delete the given key from this set. 071 */ 072 public void delete(K key) { set.remove(key); } 073 074 /** 075 * Return the number of keys in this set. 076 */ 077 public int size() { return set.size(); } 078 079 /** 080 * Return an Iterator for this set. 081 */ 082 public Iterator<K> iterator() { return set.iterator(); } 083 084 /** 085 * Return the key in this set with the maximum value. 086 */ 087 public K max() { return set.last(); } 088 089 /** 090 * Return the key in this set with the minimum value. 091 */ 092 public K min() { return set.first(); } 093 094 /** 095 * Return the smallest key in this set {@code >= k}. 096 */ 097 public K ceil(K k) { 098 SortedSet<K> tail = set.tailSet(k); 099 if (tail.isEmpty()) return null; 100 else return tail.first(); 101 } 102 103 /** 104 * Return the largest key in this set {@code <= k}. 105 */ 106 public K floor(K k) { 107 if (set.contains(k)) return k; 108 109 // does not include key if present (!) 110 SortedSet<K> head = set.headSet(k); 111 if (head.isEmpty()) return null; 112 else return head.last(); 113 } 114 115 /** 116 * Return the union of this set with that set. 117 */ 118 public SET<K> union(SET<K> that) { 119 SET<K> c = new SET<>(); 120 for (K x : this) { c.add(x); } 121 for (K x : that) { c.add(x); } 122 return c; 123 } 124 125 /** 126 * Return the intersection of this set with that set. 127 */ 128 public SET<K> intersects(SET<K> that) { 129 SET<K> c = new SET<>(); 130 if (this.size() < that.size()) { 131 for (K x : this) { 132 if (that.contains(x)) c.add(x); 133 } 134 } 135 else { 136 for (K x : that) { 137 if (this.contains(x)) c.add(x); 138 } 139 } 140 return c; 141 } 142 143 /** 144 * Does this SET equal that set. 145 */ 146 @SuppressWarnings("unchecked") 147 public boolean equals(Object y) { 148 if (y == this) return true; 149 if (y == null) return false; 150 if (y.getClass() != this.getClass()) return false; 151 SET<K> that = (SET<K>) y; 152 if (this.size() != that.size()) return false; 153 try { 154 for (K k : this) 155 if (!that.contains(k)) return false; 156 } 157 catch (ClassCastException exception) { 158 return false; 159 } 160 return true; 161 } 162 163 // must override hashcode if you override equals 164 // See Item 9 of Effective Java (2e) by Joshua Block 165 // This code based on java.util.AbstractMap.java 166 public int hashCode() { 167 int h = 0; 168 for (K k : this) 169 h = 31*h + Objects.hashCode(k); 170 return h; 171 } 172 173 /** 174 * String represenation of this set. 175 */ 176 public String toString() { 177 StringBuilder s = new StringBuilder(); 178 for (K key : this) 179 s.append(key + " "); 180 return s.toString(); 181 } 182 183 /* ********************************************************************* 184 * Test routine. 185 **********************************************************************/ 186 public static void main(String[] args) { 187 SET<String> set = new SET<>(); 188 189 190 // insert some keys 191 set.add("www.cs.princeton.edu"); 192 set.add("www.cs.princeton.edu"); // overwrite old value 193 set.add("www.princeton.edu"); 194 set.add("www.math.princeton.edu"); 195 set.add("www.yale.edu"); 196 set.add("www.amazon.com"); 197 set.add("www.simpsons.com"); 198 set.add("www.stanford.edu"); 199 set.add("www.google.com"); 200 set.add("www.ibm.com"); 201 set.add("www.apple.com"); 202 set.add("www.slashdot.com"); 203 set.add("www.whitehouse.gov"); 204 set.add("www.espn.com"); 205 set.add("www.snopes.com"); 206 set.add("www.movies.com"); 207 set.add("www.cnn.com"); 208 set.add("www.iitb.ac.in"); 209 210 211 StdOut.println(set.contains("www.cs.princeton.edu")); 212 StdOut.println(!set.contains("www.harvardsucks.com")); 213 StdOut.println(set.contains("www.simpsons.com")); 214 StdOut.println(); 215 216 StdOut.println("ceil(www.simpsonr.com) = " + set.ceil("www.simpsonr.com")); 217 StdOut.println("ceil(www.simpsons.com) = " + set.ceil("www.simpsons.com")); 218 StdOut.println("ceil(www.simpsont.com) = " + set.ceil("www.simpsont.com")); 219 StdOut.println("floor(www.simpsonr.com) = " + set.floor("www.simpsonr.com")); 220 StdOut.println("floor(www.simpsons.com) = " + set.floor("www.simpsons.com")); 221 StdOut.println("floor(www.simpsont.com) = " + set.floor("www.simpsont.com")); 222 StdOut.println(); 223 224 225 // print out all keys in the set in lexicographic order 226 for (String s : set) { 227 StdOut.println(s); 228 } 229 230 } 231 232}