001// Exercise 3.1.2 (Solution published at http://algs4.cs.princeton.edu/) 002package algs31; 003import stdlib.*; 004import algs13.Queue; 005/* *********************************************************************** 006 * Compilation: javac ArrayST.java 007 * Execution: java ArrayST < input.txt 008 * Dependencies: StdIn.java StdOut.java 009 * Data files: http://algs4.cs.princeton.edu/31elementary/tinyST.txt 010 * 011 * 012 * Symbol table implementation with unordered array. Uses repeated 013 * doubling to resize the array. 014 * 015 * % java ArrayST < tiny.txt 016 * S 0 017 * H 5 018 * X 7 019 * R 3 020 * C 4 021 * L 11 022 * A 8 023 * M 9 024 * P 10 025 * E 12 026 * 027 *************************************************************************/ 028 029public class ArrayST<K, V> { 030 private static final int INIT_SIZE = 8; 031 032 private V[] vals; // symbol table values 033 private K[] keys; // symbol table keys 034 private int N = 0; // number of elements in symbol table 035 036 @SuppressWarnings("unchecked") 037 public ArrayST() { 038 keys = (K[]) new Object[INIT_SIZE]; 039 vals = (V[]) new Object[INIT_SIZE]; 040 } 041 042 // return the number of key-value pairs in the symbol table 043 public int size() { return N; } 044 045 // is the symbol table empty? 046 public boolean isEmpty() { return size() == 0; } 047 048 // resize the parallel arrays to the given capacity 049 @SuppressWarnings("unchecked") 050 private void resize(int capacity) { 051 if (capacity <= N) throw new IllegalArgumentException (); 052 K[] tempk = (K[]) new Object[capacity]; 053 V[] tempv = (V[]) new Object[capacity]; 054 for (int i = 0; i < N; i++) tempk[i] = keys[i]; 055 for (int i = 0; i < N; i++) tempv[i] = vals[i]; 056 keys = tempk; 057 vals = tempv; 058 } 059 060 // insert the key-value pair into the symbol table 061 public void put(K key, V val) { 062 063 // to deal with duplicates 064 delete(key); 065 066 // double size of arrays if necessary 067 if (N >= vals.length) resize(2*N); 068 069 // add new key and value at the end of array 070 vals[N] = val; 071 keys[N] = key; 072 N++; 073 } 074 075 public boolean contains(K key) { return get(key) != null; } 076 public V get(K key) { 077 for (int i = 0; i < N; i++) 078 if (keys[i].equals(key)) return vals[i]; 079 return null; 080 } 081 082 public Iterable<K> keys() { 083 Queue<K> queue = new Queue<>(); 084 for (int i = 0; i < N; i++) 085 queue.enqueue(keys[i]); 086 return queue; 087 } 088 089 // remove given key (and associated value) 090 public void delete(K key) { 091 for (int i = 0; i < N; i++) { 092 if (key.equals(keys[i])) { 093 keys[i] = keys[N-1]; 094 vals[i] = vals[N-1]; 095 keys[N-1] = null; 096 vals[N-1] = null; 097 N--; 098 return; 099 } 100 } 101 } 102 103 104 105 106 /* ********************************************************************* 107 * Test routine. 108 **********************************************************************/ 109 public static void main(String[] args) { 110 StdIn.fromFile("data/tiny.txt"); 111 112 String[] a = StdIn.readAll().split("\\s+"); 113 int N = a.length; 114 ArrayST<String, Integer> st = new ArrayST<>(); 115 for (int i = 0; i < N; i++) 116 st.put(a[i], i); 117 for (String s : st.keys()) 118 StdOut.println(s + " " + st.get(s)); 119 } 120}