module Bounded_int_table

: sig

A Bounded_int_table is a table whose keys can be mapped to integers in a fixed range, 0 ... num_keys-1, where num_keys is specified at table-creation time. The purpose of Bounded_int_table is to be faster than Hashtbl in situations where one is willing to pay a space cost for the speed.

Bounded_int_table presents a subset of the Hashtbl interface. The key type can be any type, but table creation requires a key_to_int function, which will be used to extract the integer of all keys. If multiple keys map to the same integer, then only one of them can be in the table at a time. Any operation that supplies a key whose corresponding integer is outside the allowed range for the table will cause an exception.

A Bounded_int_table is implemented using two fixed size arrays of size num_keys, which are supplied at table-creation time. The space used does not depend on the length of the table but rather only on num_keys. Operations that deal with a single element (find, mem, add, remove, set) take constant time, and perform one or two array operations. Operations that deal with all of the keys defined in the table (data, fold, iter, iter_vals, keys, to_alist) take time proportional to the length of the table, not num_keys.

type ('key, 'data) t

type ('a, 'b) table = ('a, 'b) t

include Invariant.S2 with type ('a, 'b) t := ('a, 'b) t

include Equal.S2 with type ('a, 'b) t := ('a, 'b) t

val create : ?sexp_of_key:('key -> Std_internal.Sexp.t) -> num_keys:int -> key_to_int:('key -> int) -> unit -> ('key, 'data) t

create ~num_keys ~key_to_int returns a table where the keys can map to 0 .. num_keys-1, according to key_to_int. It is an error if num_keys < 0.

sexp_of_key, if supplied, will be used to display keys in error messages.

val keys : ('key, _) t -> 'key list

Standard hashtbl functions.

val data : (_, 'data) t -> 'data list

val find : ('key, 'data) t -> 'key -> 'data option

val find_exn : ('key, 'data) t -> 'key -> 'data

val find_or_add : ('key, 'data) t -> 'key -> default:(unit -> 'data) -> 'data

val fold : ('key, 'data) t -> init:'accum -> f:(key:'key -> data:'data -> 'accum -> 'accum) -> 'accum

val iter : ('key, 'data) t -> f:(key:'key -> data:'data -> unit) -> unit

val iter_vals : (_, 'data) t -> f:('data -> unit) -> unit

val filter_mapi : ('key, 'data1) t -> f:(key:'key -> data:'data1 -> 'data2 option) -> ('key, 'data2) t

val filter_map : ('key, 'data1) t -> f:('data1 -> 'data2 option) -> ('key, 'data2) t

val mapi : ('key, 'data1) t -> f:(key:'key -> data:'data1 -> 'data2) -> ('key, 'data2) t

val map : ('key, 'data1) t -> f:('data1 -> 'data2) -> ('key, 'data2) t

val for_alli : ('key, 'data) t -> f:(key:'key -> data:'data -> bool) -> bool

val existsi : ('key, 'data) t -> f:(key:'key -> data:'data -> bool) -> bool

val for_all : (_, 'data) t -> f:('data -> bool) -> bool

val exists : (_, 'data) t -> f:('data -> bool) -> bool

val length : (_, _) t -> int

val mem : ('key, _) t -> 'key -> bool

val remove : ('key, _) t -> 'key -> unit

val set : ('a, 'b) t -> key:'a -> data:'b -> unit

val add : ('a, 'b) t -> key:'a -> data:'b -> [

| `Ok

| `Duplicate of 'b

]

val add_exn : ('a, 'b) t -> key:'a -> data:'b -> unit

val to_alist : ('key, 'data) t -> ('key * 'data) list

module With_key : functor (Key : sig

type t

val to_int : t -> int

val t_of_sexp : Sexplib.Sexp.t -> t

val sexp_of_t : t -> Sexplib.Sexp.t

val bin_t : t Bin_prot.Type_class.t

val bin_read_t : t Bin_prot.Read.reader

val __bin_read_t__ : (int -> t) Bin_prot.Read.reader

val bin_reader_t : t Bin_prot.Type_class.reader

val bin_size_t : t Bin_prot.Size.sizer

val bin_write_t : t Bin_prot.Write.writer

val bin_writer_t : t Bin_prot.Type_class.writer

end

) -> sig

type 'data t = (Key.t, 'data) table

Serialization of a bounded int table using bin_io or sexp preserves num_keys, but only takes space proportional to the length of the table.

val create : num_keys:int -> 'data t

val of_alist : (Key.t * 'data) list -> 'data t Or_error.t

val of_alist_exn : (Key.t * 'data) list -> 'data t

val t_of_sexp : (Sexplib.Sexp.t -> 'data) -> Sexplib.Sexp.t -> 'data t

val sexp_of_t : ('data -> Sexplib.Sexp.t) -> 'data t -> Sexplib.Sexp.t

val bin_t : 'data Bin_prot.Type_class.t -> 'data t Bin_prot.Type_class.t

val bin_read_t : 'data Bin_prot.Read.reader -> 'data t Bin_prot.Read.reader

val __bin_read_t__ : 'data Bin_prot.Read.reader -> (int -> 'data t) Bin_prot.Read.reader

val bin_reader_t : 'data Bin_prot.Type_class.reader -> 'data t Bin_prot.Type_class.reader

val bin_size_t : 'data Bin_prot.Size.sizer -> 'data t Bin_prot.Size.sizer

val bin_write_t : 'data Bin_prot.Write.writer -> 'data t Bin_prot.Write.writer

val bin_writer_t : 'data Bin_prot.Type_class.writer -> 'data t Bin_prot.Type_class.writer

end

val debug : bool Pervasives.ref

set debug := true to turn on debugging, including potentially slow invariant checking.

val sexp_of_t : ('key -> Sexplib.Sexp.t) -> ('data -> Sexplib.Sexp.t) -> ('key, 'data) t -> Sexplib.Sexp.t

end