Commits

Kelvin Jin  committed 6cb0f1b

Updated Hashtable. iter still doesn't work, but fold does. each entry is now a key-value pair

  • Participants
  • Parent commits facd5ef

Comments (0)

Files changed (1)

File shared/hashtable.ml

 exception Not_found of string
 
-type ('a, 'b) t = ('b list) array * ('a -> int) * int
+type ('a, 'b) t = (('a * 'b) list) array * ('a -> int) * int ref
 
 let create capacity hash =
   let init_fun a = [] in
-  (Array.init capacity init_fun, hash)
+  (Array.init capacity init_fun, hash, ref 0)
 
 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 filter lst (k, v) =
+    if v = value then (length := !length - 1; lst)
+    else (k, v)::lst in
+  let processed_val_list = List.rev (List.fold_left filter [] val_list) in
+  length := !length + 1;
+  Array.set hash_table index ((key, value)::processed_val_list)
 
 let find table key =
-  let (hash_table, hash_function, length) = table in
+  let (hash_table, hash_function, _) = 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
+  | h::_ -> snd h
 
 let mem table key =
-  let (hash_table, hash_function, length) = table in
+  let (hash_table, hash_function, _) = 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
   let val_list = Array.get hash_table index in
   match val_list with
   | [] -> ()
-  | _::t -> Array.set hash_table index t
+  | _::t -> length := !length - 1; 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 (hash_table, hash_function, _) = table in
+  let size = Array.length hash_table in
+  for index = 0 to size - 1 do
     let current_list = Array.get hash_table index in
-    let helper lst lst2 = [] in
+    let helper lst (k, v) = (f k v)::lst 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
+  done
 
-let fold f table init = failwith "(The battle rages)"
+let fold f table init =
+    let (hash_table, hash_function, _) = table in
+  let size = Array.length hash_table in
+  let x = ref init in
+  let helper acc (k, v) = f k v acc in
+  for index = 0 to size - 1 do
+    let current_list = List.rev (Array.get hash_table index) in
+    x := List.fold_left helper !x current_list
+  done; !x
 
 let length table = let (_, _, length) = table in length