stringHashAndMore4.ml

module type SIn =
sig

  type key
  type value

  val arr_size: int
  val k_compare: key -> key -> int
  val v_compare: value -> value -> int
  val genHash: key -> int

end

module type SOut =
sig

  type key
  type value

  type hash

  val create: unit -> hash
  val display: hash -> (key -> string) -> (value -> string) -> unit
  val add: hash -> key -> value -> unit
  val find: hash -> key -> value option
  val remove: hash -> key -> unit

end


module Make(E:SIn):(SOut with type key := E.key with type value := E.value) =
struct

  type key = E.key
  type value = E.value

  type collisions = (key * value) list
  type node = (key * value * collisions) option
  type hash = node array

  let genHash k = E.genHash k

  let create ():(hash) =
    Array.init E.arr_size (fun _ -> None)

  let display (ht:hash) sKey sValue =
    Array.iter (
      fun e ->
        match e with
        | None -> print_endline "[Nothing here]"
        | Some (k, v, lst) ->
          Printf.printf "->%s=>%s\n" (sKey k) (sValue v);
          List.iter (
            fun (kl, vl) ->
              Printf.printf "--->%s=>%s\n" (sKey kl) (sValue vl);
          ) lst
    ) ht

  let rec add_list lst key value =
    match lst with
    | [] -> (key, value)::[]
    | (k, v)::tl ->
      if (E.k_compare k key) = 0 && (E.v_compare v value) = 0
      then
        (k, v)::tl
      else if (E.k_compare k key) = 0
      then
        (k, value)::tl
      else
        (k, v)::add_list tl key value


  let add ht key value =
    let hv = genHash key in
    let arr_node = Array.get ht hv in
    match arr_node with
    | None -> Array.set ht hv (Some (key, value, []))
    | Some (k, v, lst) when (E.k_compare k key) = 0 && (E.v_compare v value) != 0 ->
      Array.set ht hv (Some (k, value, lst))
    | Some (k, v, lst) when (E.k_compare k key) = 0 && (E.v_compare v value) = 0 ->
      ()
    | Some (k, v, lst) -> Array.set ht hv (Some(k, v, (add_list lst key value)))

  let rec find_list lst key =
    match lst with
    | [] -> None
    | (k, v)::tl ->
      if (E.k_compare key k) = 0
      then
        Some v
      else
        find_list tl key

  let find (ht:hash) key =
    let hv = genHash key in
    let arr_node = Array.get ht hv in
    match arr_node with
    | None -> None
    | Some (k, v, _) when (E.k_compare k key) = 0 -> Some v
    | Some (_, _, lst) -> find_list lst key

  let rec remove_list lst key =
    match lst with
    | [] -> []
    | (k, v)::tl ->
      if (E.k_compare key k) = 0
      then
        tl
      else
        (k, v)::remove_list tl key

  let remove (ht:hash) key =
    let hv = genHash key in
    let arr_node = Array.get ht hv in
    match arr_node with
    | None -> ()
    | Some (k, _, []) when (E.k_compare k key) = 0 -> Array.set ht hv None
    | Some (k, v, lst) when (E.k_compare k key) = 0 ->
      let (kl, vl) = List.hd lst in
      Array.set ht hv (Some(kl, vl, (List.tl lst)))
    | Some (k, v, lst) -> Array.set ht hv (Some(k, v, remove_list lst key))

end

(***************************************************************************)


let strs =
  [
    ("Salty", 1);
    ("Cracker", 2);
    ("Emily", 3);
    ("Angela", 4);
    ("Richard", 5);
    ("John", 6);
    ("Betty", 7);
    ("Zebra", 8);
    ("Bobby", 9);
    ("Kenny", 10);
    ("Brenda", 11);
    ("Dart", 12);
    ("Cat", 13);
    ("Dog", 14);
    ("Bird", 15);
    ("Lion", 16);
    ("Tweety", 17);
    ("Tank", 18);
    ("Car", 19);
    ("Gun", 20);
    ("Apple", 21);
    ("Plum", 22);
    ("Run", 23);
    ("Peel", 24);
    ("See", 25);
    ("Sun", 26);
    ("Mouse", 27);
    ("Speaker", 28);
    ("Key", 29);
    ("Song", 30);
    ("Switch", 31);
    ("On", 32);
    ("Gun", 33);
    ("Apple", 34);
    ("Switch", 35);
    ("Lion", 36);
    ("Gun", 37);
    ("Gun", 38);
  ]

module MyHashStrInt =
struct

  type key = string
  type value = int

  let arr_size = 24
  let k_compare = String.compare
  let v_compare = Int.compare
  let genHash str =
    let hash = 5381 in
    (Seq.fold_left
       (
         fun a d ->
           ((Int.shift_left a 5) + a) + (Char.code d)
       )
       hash
       (String.to_seq(str))) mod arr_size

end

module HashSI = Myhash.Make(MyHashStrInt)

let ht = HashSI.create()

let () =
  List.iter (
    fun (k, v) ->
      HashSI.add ht k v
  ) strs

let () = HashSI.display ht (fun t -> t) string_of_int

let () = print_endline "\n\n"

let () =
  List.iter (
    fun k ->
      HashSI.remove ht k
  ) ["Lion"; "Switch"; "Apple"; "Gun"; ]

let () = HashSI.display ht (fun t -> t) string_of_int

let () = print_endline "\n\n"

let ans = HashSI.find ht "Angela"

let () =
  match ans with
  | None -> print_endline "Nothing found!"
  | Some v -> Printf.printf "Found: %d\n" v