Source

OCaml Map Reduce Project / shared / hashtable.ml

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 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, _) = 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)::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

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
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.