Commits

Kelvin Jin committed ad0a15b

Added most hashtable functions

Comments (1)

Files changed (1)

-type ('a, 'b) t
-
-let create capacity hash = 
-  failwith "Die monster. You don't belong in this world!"
-
-let add table key value = 
-  failwith "It was not by my hand that I am once again given flesh. I was called here by humans, who wish to pay me tribute."
-
-let find table key = failwith "Tribute? You steal men's souls, and make them your slaves."
-
-let mem table key = failwith "Perhaps the same could be said of all religions."
-
-let remove table key = failwith "Your words are as empty as your soul. Mankind ill needs a savior such as you."
-
-let iter f table = failwith "What is a man?! A miserable little pile of secrets! But enough talk, have at you!"
+exception Not_found of string
+
+type ('a, 'b) t = ('b list) array * ('a -> int) * int
+
+let create capacity hash =
+  let init_fun a = [] in
+  (Array.init capacity init_fun, hash)
+
+let add table key value =
+  let (hash_table, hash_function, length) = table in
+  let capacity = Array.length hash_table in
+  let index = hash_function key mod capacity in
+  let val_list = Array.get hash_table index in
+  length = length + 1; Array.set hash_table index (value::val_list)
+
+let find table key =
+  let (hash_table, hash_function, length) = table in
+  let capacity = Array.length hash_table in
+  let index = hash_function key mod capacity in
+  let val_list = Array.get hash_table index in
+  match val_list with
+  | [] -> raise (Not_found "no binding for key")
+  | h::_ -> h
+
+let mem table key =
+  let (hash_table, hash_function, length) = table in
+  let capacity = Array.length hash_table in
+  let index = hash_function key mod capacity in
+  let val_list = Array.get hash_table index in
+  match val_list with
+  | [] -> false
+  | h::_ -> true
+
+let remove table key =
+  let (hash_table, hash_function, length) = table in
+  let capacity = Array.length hash_table in
+  let index = hash_function key mod capacity in
+  let val_list = Array.get hash_table index in
+  match val_list with
+  | [] -> ()
+  | _::t -> Array.set hash_table index t
+
+let iter f table =
+  let (hash_table, hash_function, length) = table in
+  let length = Array.length hash_table in
+  for index = 0 to length do
+    let current_list = Array.get hash_table index in
+    let helper lst lst2 = [] in
+    let new_reversed_list = List.fold_left helper [] current_list in
+    let new_list = List.rev new_reversed_list in
+    Array.set hash_table index new_list
+    done
 
 let fold f table init = failwith "(The battle rages)"
 
-let length table = failwith "No! This cannot be! AAAAAAAAAH!!!"
+let length table = let (_, _, length) = table in length