207 lines
7.1 KiB
Java
207 lines
7.1 KiB
Java
import edu.princeton.cs.algs4.StdIn;
|
|
import edu.princeton.cs.algs4.StdOut;
|
|
import java.util.Iterator;
|
|
import java.util.NoSuchElementException;
|
|
import java.util.TreeMap;
|
|
|
|
/**
|
|
* For additional documentation, see
|
|
* <a href="https://algs4.cs.princeton.edu/35applications">Section 3.5</a> of
|
|
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
|
|
*
|
|
* @author Robert Sedgewick
|
|
* @author Kevin Wayne
|
|
*
|
|
* @param <Key> the generic type of keys in this symbol table
|
|
* @param <Value> the generic type of values in this symbol table
|
|
*/
|
|
public class ST<Key extends Comparable<Key>, Value> implements Iterable<Key> {
|
|
|
|
private TreeMap<Key, Value> st;
|
|
|
|
/**
|
|
* Initializes an empty symbol table.
|
|
*/
|
|
public ST() {
|
|
st = new TreeMap<Key, Value>();
|
|
}
|
|
|
|
|
|
/**
|
|
* Returns the value associated with the given key in this symbol table.
|
|
*
|
|
* @param key the key
|
|
* @return the value associated with the given key if the key is in this symbol table;
|
|
* {@code null} if the key is not in this symbol table
|
|
* @throws IllegalArgumentException if {@code key} is {@code null}
|
|
*/
|
|
public Value get(Key key) {
|
|
if (key == null) throw new IllegalArgumentException("calls get() with null key");
|
|
return st.get(key);
|
|
}
|
|
|
|
/**
|
|
* Inserts the specified key-value pair into the symbol table, overwriting the old
|
|
* value with the new value if the symbol table already contains the specified key.
|
|
* Deletes the specified key (and its associated value) from this symbol table
|
|
* if the specified value is {@code null}.
|
|
*
|
|
* @param key the key
|
|
* @param val the value
|
|
* @throws IllegalArgumentException if {@code key} is {@code null}
|
|
*/
|
|
public void put(Key key, Value val) {
|
|
if (key == null) throw new IllegalArgumentException("calls put() with null key");
|
|
if (val == null) st.remove(key);
|
|
else st.put(key, val);
|
|
}
|
|
|
|
/**
|
|
* Removes the specified key and its associated value from this symbol table
|
|
* (if the key is in this symbol table).
|
|
* 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("calls delete() with null key");
|
|
st.remove(key);
|
|
}
|
|
|
|
/**
|
|
* Removes the specified key and its associated value from this symbol table
|
|
* (if the key is in this symbol table).
|
|
* 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("calls remove() with null key");
|
|
st.remove(key);
|
|
}
|
|
|
|
/**
|
|
* Returns true if this symbol table contain the given key.
|
|
*
|
|
* @param key the key
|
|
* @return {@code true} if this symbol table contains {@code key} and
|
|
* {@code false} otherwise
|
|
* @throws IllegalArgumentException if {@code key} is {@code null}
|
|
*/
|
|
public boolean contains(Key key) {
|
|
if (key == null) throw new IllegalArgumentException("calls contains() with null key");
|
|
return st.containsKey(key);
|
|
}
|
|
|
|
/**
|
|
* Returns the number of key-value pairs in this symbol table.
|
|
*
|
|
* @return the number of key-value pairs in this symbol table
|
|
*/
|
|
public int size() {
|
|
return st.size();
|
|
}
|
|
|
|
/**
|
|
* Returns true if this symbol table is empty.
|
|
*
|
|
* @return {@code true} if this symbol table is empty and {@code false} otherwise
|
|
*/
|
|
public boolean isEmpty() {
|
|
return size() == 0;
|
|
}
|
|
|
|
/**
|
|
* Returns all keys in this symbol table in ascending order,
|
|
* as an {@code Iterable}.
|
|
* <p>
|
|
* To iterate over all of the keys in the symbol table named {@code st},
|
|
* use the foreach notation: {@code for (Key key : st.keys())}.
|
|
*
|
|
* @return all keys in this symbol table in ascending order
|
|
*/
|
|
public Iterable<Key> keys() {
|
|
return st.keySet();
|
|
}
|
|
|
|
/**
|
|
* Returns all keys in this symbol table in ascending order.
|
|
* To iterate over all of the keys in a symbol table named {@code st}, use the
|
|
* foreach notation: {@code for (Key key : st)}.
|
|
* <p>
|
|
* This method is provided for backward compatibility with the version from
|
|
* <em>Introduction to Programming in Java: An Interdisciplinary Approach.</em>
|
|
*
|
|
* @return all keys in this symbol table in ascending order
|
|
* @deprecated Replaced by {@link #keys()}.
|
|
*/
|
|
@Deprecated
|
|
public Iterator<Key> iterator() {
|
|
return st.keySet().iterator();
|
|
}
|
|
|
|
/**
|
|
* Returns the smallest key in this symbol table.
|
|
*
|
|
* @return the smallest key in this symbol table
|
|
* @throws NoSuchElementException if this symbol table is empty
|
|
*/
|
|
public Key min() {
|
|
if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
|
|
return st.firstKey();
|
|
}
|
|
|
|
/**
|
|
* Returns the largest key in this symbol table.
|
|
*
|
|
* @return the largest key in this symbol table
|
|
* @throws NoSuchElementException if this symbol table is empty
|
|
*/
|
|
public Key max() {
|
|
if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
|
|
return st.lastKey();
|
|
}
|
|
|
|
/**
|
|
* Returns the smallest key in this symbol table greater than or equal to {@code key}.
|
|
*
|
|
* @param key the key
|
|
* @return the smallest key in this symbol table greater than or equal to {@code key}
|
|
* @throws NoSuchElementException if there is no such key
|
|
* @throws IllegalArgumentException if {@code key} is {@code null}
|
|
*/
|
|
public Key ceiling(Key key) {
|
|
if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
|
|
Key k = st.ceilingKey(key);
|
|
if (k == null) throw new NoSuchElementException("argument to ceiling() is too large");
|
|
return k;
|
|
}
|
|
|
|
/**
|
|
* Returns the largest key in this symbol table less than or equal to {@code key}.
|
|
*
|
|
* @param key the key
|
|
* @return the largest key in this symbol table less than or equal to {@code key}
|
|
* @throws NoSuchElementException if there is no such key
|
|
* @throws IllegalArgumentException if {@code key} is {@code null}
|
|
*/
|
|
public Key floor(Key key) {
|
|
if (key == null) throw new IllegalArgumentException("argument to floor() is null");
|
|
Key k = st.floorKey(key);
|
|
if (k == null) throw new NoSuchElementException("argument to floor() is too small");
|
|
return k;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
ST<String, Integer> st = new ST<String, Integer>();
|
|
for (int i = 0; !StdIn.isEmpty(); i++) {
|
|
String key = StdIn.readString();
|
|
st.put(key, i);
|
|
}
|
|
for (String s : st.keys())
|
|
StdOut.println(s + " " + st.get(s));
|
|
}
|
|
}
|