add initial files l8

1 files changed, 296 insertions, 0 deletions

diff --git a/labb8/lib/StanfordCPPLib/hashmap.cpp b/labb8/lib/StanfordCPPLib/hashmap.cpp
new file mode 100755
index 0000000..4dd77d6
--- /dev/null
+++ b/labb8/lib/StanfordCPPLib/hashmap.cpp
@@ -0,0 +1,296 @@
+/*
+ * File: hashmap.cpp
+ * -----------------
+ * This file contains the hash functions that are used in conjunction
+ * with the HashMap class.
+ */
+
+#include <iostream>
+#include <string>
+#include "hashmap.h"
+#include "hashset.h"
+#include "lexicon.h"
+#include "queue.h"
+#include "set.h"
+#include "stack.h"
+#include "vector.h"
+using namespace std;
+
+/*
+ * Implementation notes: hashCode
+ * ------------------------------
+ * This function takes a string key and uses it to derive a hash code,
+ * which is a nonnegative integer related to the key by a deterministic
+ * function that distributes keys well across the space of integers.
+ * The general method is called linear congruence, which is also used
+ * in random-number generators.  The specific algorithm used here is
+ * called djb2 after the initials of its inventor, Daniel J. Bernstein,
+ * Professor of Mathematics at the University of Illinois at Chicago.
+ */
+
+const int HASH_SEED = 5381;               /* Starting point for first cycle */
+const int HASH_MULTIPLIER = 33;           /* Multiplier for each cycle      */
+const int HASH_MASK = unsigned(-1) >> 1;  /* All 1 bits except the sign     */
+
+int hashCode(const string & str) {
+   unsigned hash = HASH_SEED;
+   int n = str.length();
+   for (int i = 0; i < n; i++) {
+      hash = HASH_MULTIPLIER * hash + str[i];
+   }
+   return int(hash & HASH_MASK);
+}
+
+int hashCode(int key) {
+   return key & HASH_MASK;
+}
+
+int hashCode(char key) {
+   return key;
+}
+
+int hashCode(long key) {
+   return int(key) & HASH_MASK;
+}
+
+int hashCode(double key) {
+    char* byte = (char*) &key;
+    unsigned hash = HASH_SEED;
+    for (int i = 0; i < (int) sizeof(double); i++) {
+        hash = HASH_MULTIPLIER * hash + (int) *byte++;
+    }
+    return hash & HASH_MASK;
+}
+
+
+// hashCode functions for various collections;
+// added by Marty Stepp to allow compound collections.
+// I'm a bit ashamed to have to rewrite so many prototypes, one for each
+// element type; but I can't get it to compile with a template.
+int hashCode(const HashSet<int>& s) {
+    int code = HASH_SEED;
+    foreach (int n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const HashSet<double>& s) {
+    int code = HASH_SEED;
+    foreach (double n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const HashSet<char>& s) {
+    int code = HASH_SEED;
+    foreach (char n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const HashSet<long>& s) {
+    int code = HASH_SEED;
+    foreach (long n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const HashSet<std::string>& s) {
+    int code = HASH_SEED;
+    foreach (std::string n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Lexicon& l) {
+    int code = HASH_SEED;
+    foreach (std::string n in l) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Queue<int>& q) {
+    int code = HASH_SEED;
+    Queue<int> backup = q;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.dequeue());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Queue<double>& q) {
+    int code = HASH_SEED;
+    Queue<double> backup = q;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.dequeue());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Queue<char>& q) {
+    int code = HASH_SEED;
+    Queue<char> backup = q;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.dequeue());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Queue<long>& q) {
+    int code = HASH_SEED;
+    Queue<long> backup = q;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.dequeue());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Queue<std::string>& q) {
+    int code = HASH_SEED;
+    Queue<std::string> backup = q;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.dequeue());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Set<int>& s) {
+    int code = HASH_SEED;
+    foreach (int n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Set<double>& s) {
+    int code = HASH_SEED;
+    foreach (double n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Set<char>& s) {
+    int code = HASH_SEED;
+    foreach (char n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Set<long>& s) {
+    int code = HASH_SEED;
+    foreach (long n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Set<std::string>& s) {
+    int code = HASH_SEED;
+    foreach (std::string n in s) {
+        code = HASH_MULTIPLIER * code + hashCode(n);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Stack<int>& s) {
+    int code = HASH_SEED;
+    Stack<int> backup = s;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.pop());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Stack<double>& s) {
+    int code = HASH_SEED;
+    Stack<double> backup = s;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.pop());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Stack<char>& s) {
+    int code = HASH_SEED;
+    Stack<char> backup = s;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.pop());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Stack<long>& s) {
+    int code = HASH_SEED;
+    Stack<long> backup = s;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.pop());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Stack<std::string>& s) {
+    int code = HASH_SEED;
+    Stack<std::string> backup = s;
+    while (!backup.isEmpty()) {
+        code = HASH_MULTIPLIER * code + hashCode(backup.pop());
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Vector<int>& v) {
+    int code = HASH_SEED;
+    for (int i = 0, size = v.size(); i < size; i++) {
+        code = HASH_MULTIPLIER * code + hashCode(v[i]);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Vector<double>& v) {
+    int code = HASH_SEED;
+    for (int i = 0, size = v.size(); i < size; i++) {
+        code = HASH_MULTIPLIER * code + hashCode(v[i]);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Vector<char>& v) {
+    int code = HASH_SEED;
+    for (int i = 0, size = v.size(); i < size; i++) {
+        code = HASH_MULTIPLIER * code + hashCode(v[i]);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Vector<long>& v) {
+    int code = HASH_SEED;
+    for (int i = 0, size = v.size(); i < size; i++) {
+        code = HASH_MULTIPLIER * code + hashCode(v[i]);
+    }
+    return int(code & HASH_MASK);
+}
+
+int hashCode(const Vector<std::string>& v) {
+    int code = HASH_SEED;
+    for (int i = 0, size = v.size(); i < size; i++) {
+        code = HASH_MULTIPLIER * code + hashCode(v[i]);
+    }
+    return int(code & HASH_MASK);
+}
+
+//template <typename ValueType>
+//int hashCode(const Vector<ValueType>& v) {
+//    int code = 0;
+//    for (int i = 0, size = v.size(); i < size; i++) {
+//        code = 31 * code + hashCode(v[i]);
+//    }
+//    return code;
+//}
+