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}