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}