package hw2;

/** * The {@code SequentialSearchST} class represents an (unordered) * symbol table of generic key-value pairs. * It supports the usual put, get, contains, * delete, size, and is-empty methods. * It also provides a keys method for iterating over all of the keys. * A symbol table implements the associative array abstraction: * when associating a value with a key that is already in the symbol table, * the convention is to replace the old value with the new value. * The class also uses the convention that values cannot be {@code null}. Setting the * value associated with a key to {@code null} is equivalent to deleting the key * from the symbol table. *

* This implementation uses a singly-linked list and sequential search. * It relies on the {@code equals()} method to test whether two keys * are equal. It does not call either the {@code compareTo()} or * {@code hashCode()} method. * The put and delete operations take linear time; the * get and contains operations takes linear time in the worst case. * The size, and is-empty operations take constant time. * Construction takes constant time. *

* For additional documentation, see Section 3.1 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */

import java.util.LinkedList;

public class RSequentialSearchST, Value> { private int n; // number of key-value pairs private Node first; // the linked list of key-value pairs

// a helper linked list data type private class Node { private Key key; private Value val; private Node next;

public Node(Key key, Value val, Node next) { this.key = key; this.val = val; this.next = next; } }

/** * Initializes an empty symbol table. */ public RSequentialSearchST() { }

/** * 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 n; }

/** * Returns true if this symbol table is empty. * * @return {@code true} if this symbol table is empty; * {@code false} otherwise */ public boolean isEmpty() { return size() == 0; }

/** * Returns true if this symbol table contains the specified key. * * @param key the key * @return {@code true} if this symbol table contains {@code key}; * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */ public boolean contains(Key key) { if (key == null) throw new IllegalArgumentException("argument to contains() is null"); return get(key) != null; }

/** * Returns all keys in the symbol table as an {@code Iterable}. * To iterate over all of the keys in the symbol table named {@code st}, * use the foreach notation: {@code for (Key key : st.keys())}. * * NOTE: Java's LinkedList was use in place of the book's Queue class. * * @return all keys in the symbol table */ public Iterable keys() { LinkedList queue = new LinkedList(); for (Node x = first; x != null; x = x.next) queue.add(x.key); return queue; }

/** * Returns the value associated with the given key in this symbol table. * Takes advantage of the fact that the keys appear in increasing order to terminate * early when possible. * * @param key the key * @return the value associated with the given key if the key is in the symbol table * and {@code null} if the key is not in the symbol table * @throws IllegalArgumentException if {@code key} is {@code null} */

public Value get(Key key) { // TODO // Change this code to make use of the fact the list is sorted to terminate early // when possible. Also, solve this using recursion. To do this, you will need to // add a recursive helper function that takes the front of a list (Node) as an argument // and returns the correct value. if (key == null) throw new IllegalArgumentException("argument to get() is null"); for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) return x.val; } return null; }

/** * Inserts the specified key-value pair into the symbol table while maintaining the * ordering of keys. Overwrites 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) { // TODO // Change this code to make sure the list remains sorted! Also, solve this using recursion. // To do this, you will need to add a recursive helper function that takes the front of a // list (Node) as an argument and returns the front of the modified list (Node). if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { delete(key); return; }

for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) { x.val = val; return; } } first = new Node(key, val, first); n++; }

/** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). Takes advantage of the fact that the * keys appear in increasing order to terminate` early when possible. * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */ public void delete(Key key) { // TODO // Change this code to make use of the fact that the list is sorted to // terminate early when possible. // As this code already uses recursion, the private helper function is // already present below, but it will need to be changed to terminate // early when appropriate. if (key == null) throw new IllegalArgumentException("argument to delete() is null"); first = delete(first, key); }

// delete key in linked list beginning at Node x // warning: function call stack too large if table is large private Node delete(Node x, Key key) { // TODO // Modify this to terminate early when possible. if (x == null) return null; if (key.equals(x.key)) { n--; return x.next; } x.next = delete(x.next, key); return x; } }