001package algs35;
002import stdlib.*;
003import java.util.Iterator;
004import java.util.SortedMap;
005import java.util.TreeMap;
006/* ***********************************************************************
007 *  Compilation:  javac ST.java
008 *  Execution:    java ST
009 *
010 *  Sorted symbol table implementation using a java.util.TreeMap.
011 *  Does not allow duplicates.
012 *
013 *  % java ST
014 *
015 *************************************************************************/
016
017/**
018 *  This class represents an ordered symbol table. It assumes that
019 *  the keys are {@code Comparable}.
020 *  It supports the usual <em>put</em>, <em>get</em>, <em>contains</em>,
021 *  and <em>remove</em> methods.
022 *  It also provides ordered methods for finding the <em>minimum</em>,
023 *  <em>maximum</em>, <em>floor</em>, and <em>ceiling</em>.
024 *  <p>
025 *  The class implements the <em>associative array</em> abstraction: when associating
026 *  a value with a key that is already in the table, the convention is to replace
027 *  the old value with the new value.
028 *  The class also uses the convention that values cannot be null. Setting the
029 *  value associated with a key to null is equivalent to removing the key.
030 *  <p>
031 *  This class implements the Iterable interface for compatiblity with
032 *  the version from <em>Introduction to Programming in Java: An Interdisciplinary
033 *  Approach</em>.
034 *  <p>
035 *  This implementation uses a balanced binary search tree.
036 *  The <em>put</em>, <em>contains</em>, <em>remove</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="http://algs4.cs.princeton.edu/35applications">Section 4.5</a> of
041 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
042 */
043public class ST<K extends Comparable<? super K>, V> implements Iterable<K> {
044
045        private final TreeMap<K, V> st;
046
047        /**
048         * Create an empty symbol table.
049         */
050        public ST() {
051                st = new TreeMap<>();
052        }
053
054        /**
055         * Put key-value pair into the symbol table. Remove key from table if
056         * value is null.
057         */
058        public void put(K key, V val) {
059                if (val == null) st.remove(key);
060                else             st.put(key, val);
061        }
062
063        /**
064         * Return the value paired with given key; null if key is not in table.
065         */
066        public V get(K key) {
067                return st.get(key);
068        }
069
070        /**
071         * Delete the key (and paired value) from table.
072         * Return the value paired with given key; null if key is not in table.
073         */
074        public V delete(K key) {
075                return st.remove(key);
076        }
077
078        /**
079         * Is the key in the table?
080         */
081        public boolean contains(K key) {
082                return st.containsKey(key);
083        }
084
085        /**
086         * How many keys are in the table?
087         */
088        public int size() {
089                return st.size();
090        }
091
092        /**
093         * Return an {@code Iterable} for the keys in the table.
094         * To iterate over all of the keys in the symbol table {@code st}, use the
095         * foreach notation: {@code for (K key : st.keys())}.
096         */
097        public Iterable<K> keys() {
098                return st.keySet();
099        }
100
101        /**
102         * Return an {@code Iterator} for the keys in the table.
103         * To iterate over all of the keys in the symbol table {@code st}, use the
104         * foreach notation: {@code for (K key : st)}.
105         * This method is for backward compatibility with the version from <em>Introduction
106         * to Programming in Java: An Interdisciplinary Approach.</em>
107         */
108        public Iterator<K> iterator() {
109                return st.keySet().iterator();
110        }
111
112        /**
113         * Return the smallest key in the table.
114         */
115        public K min() {
116                return st.firstKey();
117        }
118
119        /**
120         * Return the largest key in the table.
121         */
122        public K max() {
123                return st.lastKey();
124        }
125
126
127        /**
128         * Return the smallest key in the table {@code >= k}.
129         */
130        public K ceil(K k) {
131                SortedMap<K, V> tail = st.tailMap(k);
132                if (tail.isEmpty()) return null;
133                else return tail.firstKey();
134        }
135
136        /**
137         * Return the largest key in the table {@code <= k}.
138         */
139        public K floor(K k) {
140                if (st.containsKey(k)) return k;
141
142                // does not include key if present (!)
143                SortedMap<K, V> head = st.headMap(k);
144                if (head.isEmpty()) return null;
145                else return head.lastKey();
146        }
147
148        /* *********************************************************************
149         * Test routine.
150         **********************************************************************/
151        public static void main(String[] args) {
152                ST<String, Integer> st = new ST<>();
153                for (int i = 0; !StdIn.isEmpty(); i++) {
154                        String key = StdIn.readString();
155                        st.put(key, i);
156                }
157                for (String s : st.keys())
158                        StdOut.println(s + " " + st.get(s));
159        }
160
161}