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 : int) (hash : 'a -> int) : ('a, 'b) t =
  let init_fun a : ('a * 'b) list = [] in
  (Array.init capacity init_fun, hash, ref 0)

let add (table : ('a, 'b) t) (key : 'a) (value : 'b) : unit =
  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 : ('a, 'b) t) (key : 'a) : 'b =
  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 : ('a, 'b) t) (key : 'a) : bool =
  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 : ('a, 'b) t) (key : 'a) : unit =
  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 : 'a -> 'b -> unit) (table : ('a, 'b) t) : unit =
  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 : 'a -> 'b -> 'c -> 'c) (table : ('a, 'b) t) (init : 'c) : 'c =
    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 : ('a, 'b) t) : int = let (_, _, length) = table in !length