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}