Hash chain simulation done!

Created test cases for the hash function. Tested the code by running the
main function without writting test cases. I wish the starter code was
written in a way that facilitated testing...

3 files changed, 144 insertions, 26 deletions

diff --git a/src/main/HashChains.java b/src/main/HashChains.java
new file mode 100644
index 0000000..f21d05d
--- /dev/null
+++ b/src/main/HashChains.java
@@ -0,0 +1,125 @@
+import java.io.*;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.StringTokenizer;
+
+public class HashChains {
+
+    private FastScanner in;
+    private PrintWriter out;
+    // store all strings in one list
+    private List<List<String>> elems;
+    // for hash function
+    int bucketCount;
+
+    public static void main(String[] args) throws IOException {
+        new HashChains().processQueries();
+    }
+
+    int hashFunc(String s) {
+        long hash = 0;
+        int prime = 1000000007;
+        int multiplier = 263;
+        for (int i = s.length() - 1; i >= 0; --i)
+            hash = (hash * multiplier + s.charAt(i)) % prime;
+        return (int) hash % bucketCount;
+    }
+
+    private Query readQuery() throws IOException {
+        String type = in.next();
+        if (!type.equals("check")) {
+            String s = in.next();
+            return new Query(type, s);
+        } else {
+            int ind = in.nextInt();
+            return new Query(type, ind);
+        }
+    }
+
+    private void writeSearchResult(boolean wasFound) {
+        out.println(wasFound ? "yes" : "no");
+        // Uncomment the following if you want to play with the program interactively.
+        // out.flush();
+    }
+
+    private void processQuery(Query query) {
+        int hashIndex;
+        switch (query.type) {
+            case "add":
+                hashIndex = hashFunc(query.s);
+                if (!elems.get(hashIndex).contains(query.s))
+                    elems.get(hashIndex).add(0, query.s);
+                break;
+            case "del":
+                hashIndex = hashFunc(query.s);
+                elems.get(hashIndex).remove(query.s);
+                break;
+            case "find":
+                hashIndex = hashFunc(query.s);
+                writeSearchResult(elems.get(hashIndex).contains(query.s));
+                break;
+            case "check":
+                for (String cur : elems.get(query.ind))
+                        out.print(cur + " ");
+                out.println();
+                // Uncomment the following if you want to play with the program interactively.
+                // out.flush();
+                break;
+            default:
+                throw new RuntimeException("Unknown query: " + query.type);
+        }
+    }
+
+    private void processQueries() throws IOException {
+        elems = new ArrayList<>();
+        in = new FastScanner();
+        out = new PrintWriter(new BufferedOutputStream(System.out));
+        bucketCount = in.nextInt();
+        for (int i = 0; i < bucketCount; i++) {
+            elems.add(new ArrayList<>());
+        }
+        int queryCount = in.nextInt();
+        for (int i = 0; i < queryCount; ++i) {
+            processQuery(readQuery());
+        }
+        out.close();
+    }
+
+    static class Query {
+        String type;
+        String s;
+        int ind;
+
+        Query(String type, String s) {
+            this.type = type;
+            this.s = s;
+        }
+
+        Query(String type, int ind) {
+            this.type = type;
+            this.ind = ind;
+        }
+    }
+
+    static class FastScanner {
+        private BufferedReader reader;
+        private StringTokenizer tokenizer;
+
+        FastScanner() {
+            reader = new BufferedReader(new InputStreamReader(System.in));
+            tokenizer = null;
+        }
+
+        String next() throws IOException {
+            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
+                tokenizer = new StringTokenizer(reader.readLine());
+            }
+            return tokenizer.nextToken();
+        }
+
+        int nextInt() throws IOException {
+            return Integer.parseInt(next());
+        }
+    }
+}
+
diff --git a/src/test/HashChainsTest.java b/src/test/HashChainsTest.java
new file mode 100644
index 0000000..9a7f192
--- /dev/null
+++ b/src/test/HashChainsTest.java
@@ -0,0 +1,19 @@
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class HashChainsTest {
+    @Test
+    void test(){
+        HashChains hc = new HashChains();
+        hc.bucketCount = 5;
+        assertEquals(4, hc.hashFunc("world"));
+        assertEquals(4, hc.hashFunc("HellO"));
+        assertEquals(2, hc.hashFunc("GooD"));
+        assertEquals(2, hc.hashFunc("luck"));
+
+        hc.bucketCount = 3;
+        assertEquals(1, hc.hashFunc("add"));
+        assertEquals(1, hc.hashFunc("help"));
+    }
+}
\ No newline at end of file
diff --git a/src/test/PhoneBookTest.java b/src/test/PhoneBookTest.java
deleted file mode 100644
index fb898f0..0000000
--- a/src/test/PhoneBookTest.java
+++ /dev/null
@@ -1,26 +0,0 @@
-import org.junit.jupiter.api.Test;
-
-import static org.junit.jupiter.api.Assertions.*;
-
-class PhoneBookTest {
-    @Test
-    void test() {
-        PhoneBook.add(911, "police");
-        PhoneBook.add(76213, "Mom");
-        PhoneBook.add(17239, "Bob");
-
-        assertEquals("Mom", PhoneBook.find(76213));
-        assertEquals("not found", PhoneBook.find(910));
-        assertEquals("police", PhoneBook.find(911));
-
-        PhoneBook.del(910);
-        PhoneBook.del(911);
-
-        assertEquals("not found", PhoneBook.find(911));
-        assertEquals("Mom", PhoneBook.find(76213));
-
-        PhoneBook.add(76213, "daddy");
-        assertEquals("daddy", PhoneBook.find(76213));
-    }
-
-}
\ No newline at end of file