package base

We provide a sexp_of_t but not a t_of_sexp for this type because one needs to be explicit about the hash and comparison functions used when creating a hashtable. Note that Hashtbl.Poly.t does have [@@deriving sexp], and uses OCaml's built-in polymorphic comparison and and polymorphic hashing.

The module you pass to create must have a type that is hashable, sexpable, and comparable.

Example:

        Hashtbl.create (module Int);;
        - : (int, '_a) Hashtbl.t = <abstr>;;

Example:

         Hashtbl.of_alist (module Int) [(3, "something"); (2, "whatever")]
         - : [ `Duplicate_key of int | `Ok of (int, string) Hashtbl.t ] = `Ok <abstr>

Whereas of_alist will report Duplicate_key no matter how many dups there are in your list, of_alist_report_all_dups will report each and every duplicate entry.

For example:

        Hashtbl.of_alist (module Int) [(1, "foo"); (1, "bar"); (2, "foo"); (2, "bar")];;
        - : [ `Duplicate_key of int | `Ok of (int, string) Hashtbl.t ] = `Duplicate_key 1

        Hashtbl.of_alist_report_all_dups (module Int) [(1, "foo"); (1, "bar"); (2, "foo"); (2, "bar")];;
        - : [ `Duplicate_keys of int list | `Ok of (int, string) Hashtbl.t ] = `Duplicate_keys [1; 2]

Creates a "multi" hashtable, i.e., a hashtable where each key points to a list potentially containing multiple values. So instead of short-circuiting with a `Duplicate_key variant on duplicates, as in of_alist, of_alist_multi folds those values into a list for the given key:

      let h = Hashtbl.of_alist_multi (module Int) [(1, "a"); (1, "b"); (2, "c"); (2, "d")];;
      val h : (int, string list) Hashtbl.t = <abstr>

      Hashtbl.find_exn h 1;;
      - : string list = ["b"; "a"]

Applies the get_key and get_data functions to the 'r list to create the initial keys and values, respectively, for the new hashtable.

create_mapped get_key get_data [x1;...;xn]
= of_alist [get_key x1, get_data x1; ...; get_key xn, get_data xn]

Example:

        let h =
          Hashtbl.create_mapped (module Int)
            ~get_key:(fun x -> x)
            ~get_data:(fun x -> x + 1)
           [1; 2; 3];;
        val h : [ `Duplicate_keys of int list | `Ok of (int, int) Hashtbl.t ] = `Ok <abstr>

        let h =
          match h with
          | `Ok x -> x
          | `Duplicate_keys _ -> failwith ""
        in
        Hashtbl.find_exn h 1;;
        - : int = 2

create_with_key ~get_key [x1;...;xn]
= of_alist [get_key x1, x1; ...; get_key xn, xn] 

Like create_mapped, applies the get_key and get_data functions to the 'r list to create the initial keys and values, respectively, for the new hashtable -- and then, like add_multi, folds together values belonging to the same keys. Here, though, the function used for the folding is given by combine (instead of just being a cons).

Example:

         Hashtbl.group (module Int)
           ~get_key:(fun x -> x / 2)
           ~get_data:(fun x -> x)
           ~combine:(fun x y -> x * y)
            [ 1; 2; 3; 4]
         |> Hashtbl.to_alist;;
         - : (int * int) list = [(2, 4); (1, 6); (0, 1)]

Attempting to modify (set, remove, etc.) the hashtable during iteration (fold, iter, iter_keys, iteri) will raise an exception.

Iterates over both keys and values.

Example:

      let h = Hashtbl.of_alist_exn (module Int) [(1, 4); (5, 6)] in
      Hashtbl.iteri h ~f:(fun ~key ~data ->
        print_endline (Printf.sprintf "%d-%d" key data));;
      1-4
      5-6
      - : unit = ()

Sets the given key to data.

add and add_exn leave the table unchanged if the key was already present.

change t key ~f changes t's value for key to be f (find t key).

update t key ~f is change t key ~f:(fun o -> Some (f o)).

update_and_return t key ~f is update, but returns the result of f o.

map t f returns a new table with values replaced by the result of applying f to the current values.

Example:

      let h = Hashtbl.of_alist_exn (module Int) [(1, 4); (5, 6)] in
      let h' = Hashtbl.map h ~f:(fun x -> x * 2) in
      Hashtbl.to_alist h';;
      - : (int * int) list = [(5, 12); (1, 8)]

Like map, but the function f takes both key and data as arguments.

Returns a new table by filtering the given table's values by f: the keys for which f applied to the current value returns Some are kept, and those for which it returns None are discarded.

Example:

      let h = Hashtbl.of_alist_exn (module Int) [(1, 4); (5, 6)] in
      Hashtbl.filter_map h ~f:(fun x -> if x > 5 then Some x else None)
      |> Hashtbl.to_alist;;
      - : (int * int) list = [(5, 6)]

Like filter_map, but the function f takes both key and data as arguments.

Returns new tables with bound values partitioned by f applied to the bound values.

Like partition_map, but the function f takes both key and data as arguments.

Returns a pair of tables (t1, t2), where t1 contains all the elements of the initial table which satisfy the predicate f, and t2 contains the rest.

Like partition_tf, but the function f takes both key and data as arguments.

find_or_add t k ~default returns the data associated with key k if it is in the table t, and otherwise assigns k the value returned by default ().

Like find_or_add but default takes the key as an argument.

find t k returns Some (the current binding) of k in t, or None if no such binding exists.

find_exn t k returns the current binding of k in t, or raises Caml.Not_found or Not_found_s if no such binding exists.

find_and_call t k ~if_found ~if_not_found

is equivalent to:

match find t k with Some v -> if_found v | None -> if_not_found k

except that it doesn't allocate the option.

Just like find_and_call, but takes an extra argument which is passed to if_found and if_not_found, so that the client code can avoid allocating closures or using refs to pass this additional information. This function is only useful in code which tries to minimize heap allocation.

find_and_remove t k returns Some (the current binding) of k in t and removes it, or None is no such binding exists.

Merges two hashtables.

The result of merge f h1 h2 has as keys the set of all k in the union of the sets of keys of h1 and h2 for which d(k) is not None, where:

d(k) =

• f ~key:k (`Left d1) if k in h1 maps to d1, and h2 does not have data for k;

• f ~key:k (`Right d2) if k in h2 maps to d2, and h1 does not have data for k;

• f ~key:k (`Both (d1, d2)) otherwise, where k in h1 maps to d1 and k in h2 maps to d2.

Each key k is mapped to a single piece of data x, where d(k) = Some x.

Example:

      let h1 = Hashtbl.of_alist_exn (module Int) [(1, 5); (2, 3232)] in
      let h2 = Hashtbl.of_alist_exn (module Int) [(1, 3)] in
      Hashtbl.merge h1 h2 ~f:(fun ~key:_ -> function
        | `Left x -> Some (`Left x)
        | `Right x -> Some (`Right x)
        | `Both (x, y) -> if x=y then None else Some (`Both (x,y))
      ) |> Hashtbl.to_alist;;
      - : (int * [> `Both of int * int | `Left of int | `Right of int ]) list =
      [(2, `Left 3232); (1, `Both (5, 3))]

Every key in src will be removed or set in dst according to the return value of f.