001// Exercise 3.1.5 (Solution published at http://algs4.cs.princeton.edu/)
002package algs31;
003import stdlib.*;
004import algs13.Queue;
005/* ***********************************************************************
006 *  Compilation:  javac SequentialSearchST.java
007 *  Execution:    java SequentialSearchST
008 *  Dependencies: StdIn.java StdOut.java
009 *  Data files:   http://algs4.cs.princeton.edu/31elementary/tinyST.txt
010 *
011 *  Symbol table implementation with sequential search in an
012 *  unordered linked list of key-value pairs.
013 *
014 *  % more tinyST.txt
015 *  S E A R C H E X A M P L E
016 *
017 *  % java SequentialSearchST < tiny.txt
018 *  L 11
019 *  P 10
020 *  M 9
021 *  X 7
022 *  H 5
023 *  C 4
024 *  R 3
025 *  A 8
026 *  E 12
027 *  S 0
028 *
029 *************************************************************************/
030
031public class SequentialSearchST<K, V> {
032        private int N;           // number of key-value pairs
033        private Node<K,V> first;      // the linked list of key-value pairs
034
035        // a helper linked list data type
036        private static class Node<K,V> {
037                public final K key;
038                public V val;
039                public Node<K,V> next;
040
041                public Node(K key, V val, Node<K,V> next)  {
042                        this.key  = key;
043                        this.val  = val;
044                        this.next = next;
045                }
046        }
047
048        // return number of key-value pairs
049        public int size() { return N; }
050
051        // is the symbol table empty?
052        public boolean isEmpty() { return size() == 0; }
053
054        // does this symbol table contain the given key?
055        public boolean contains(K key) {
056                return get(key) != null;
057        }
058
059        // return the value associated with the key, or null if the key is not present
060        public V get(K key) {
061                for (Node<K,V> x = first; x != null; x = x.next) {
062                        if (key.equals(x.key)) return x.val;
063                }
064                return null;
065        }
066        public V getR(K key) {
067                return getR(key, first);
068        }
069        private V getR(K key, Node<K,V> x) {
070                if (x == null) return null;
071                if (key.equals (x.key)) return x.val;
072                return getR(key, x.next);
073        }
074
075        // add a key-value pair, replacing old key-value pair if key is already present
076        public void put(K key, V val) {
077                if (val == null) { delete(key); return; }
078                for (Node<K,V> x = first; x != null; x = x.next)
079                        if (key.equals(x.key)) { x.val = val; return; }
080                first = new Node<>(key, val, first);
081                N++;
082        }
083
084        // remove key-value pair with given key (if it's in the table)
085        public void delete(K key) {
086                first = delete(first, key);
087        }
088
089        // delete key in linked list beginning at Node<K,V> x
090        // warning: function call stack too large if table is large
091        private Node<K,V> delete(Node<K,V> x, K key) {
092                if (x == null) return null;
093                if (key.equals(x.key)) { N--; return x.next; }
094                x.next = delete(x.next, key);
095                return x;
096        }
097
098
099        // return all keys as an Iterable
100        public Iterable<K> keys()  {
101                Queue<K> queue = new Queue<>();
102                for (Node<K,V> x = first; x != null; x = x.next)
103                        queue.enqueue(x.key);
104                return queue;
105        }
106
107
108
109
110        /* *********************************************************************
111         * Test client
112         **********************************************************************/
113        public static void main(String[] args) {
114                StdIn.fromString ("S E A R C H E X A M P L E");
115                SequentialSearchST<String, Integer> st = new SequentialSearchST<>();
116                for (int i = 0; !StdIn.isEmpty(); i++) {
117                        String key = StdIn.readString();
118                        st.put(key, i);
119                }
120                for (String s : st.keys())
121                        StdOut.println(s + " " + st.get(s));
122        }
123}