Source

OCaml Map Reduce Project / shared / hashtable.ml

Full commit
exception Not_found of string

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, 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
  let filter lst (k, v) =
    if k = key 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, _) = 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::_ -> snd h

let mem table key =
  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
  | [] -> 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 -> length := !length - 1; Array.set hash_table index t

let iter f table =
  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 (k, v) = f k v in
    List.fold_left helper () current_list
  done

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