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
.
include sig ... end
val sexp_of_t : ('key ‑> Base.Sexp.t) ‑> ('data ‑> Base.Sexp.t) ‑> ('key, 'data) t ‑> Base.Sexp.t
include Core_kernel__.Import.Invariant.S2 with type (a, b) t := (a, b) t
val invariant : 'a Base__.Invariant_intf.inv ‑> 'b Base__.Invariant_intf.inv ‑> ('a, 'b) t Base__.Invariant_intf.inv
Equality only requires the keys and values to be the same, not the bin or sexp
formatting or the integers the keys correspond to (see key_to_int
).
include Core_kernel__.Import.Equal.S2 with type (a, b) t := (a, b) t
val equal : 'a Core_kernel__.Import.Equal.equal ‑> 'b Core_kernel__.Import.Equal.equal ‑> ('a, 'b) t Core_kernel__.Import.Equal.equal
val create : ?sexp_of_key:('key ‑> Sexp.t) ‑> num_keys:Core_kernel__.Import.int ‑> key_to_int:('key ‑> Core_kernel__.Import.int) ‑> Core_kernel__.Import.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 num_keys : (_, _) t ‑> Core_kernel__.Import.int
val keys : ('key, _) t ‑> 'key Core_kernel__.Import.list
val data : (_, 'data) t ‑> 'data Core_kernel__.Import.list
val find : ('key, 'data) t ‑> 'key ‑> 'data Core_kernel__.Import.option
val find_exn : ('key, 'data) t ‑> 'key ‑> 'data
val find_or_add : ('key, 'data) t ‑> 'key ‑> default:(Core_kernel__.Import.unit ‑> 'data) ‑> 'data
val fold : ('key, 'data) t ‑> init:'accum ‑> f:(key:'key ‑> data:'data ‑> 'accum ‑> 'accum) ‑> 'accum
val iter_keys : ('key, _) t ‑> f:('key ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.unit
val iter : (_, 'data) t ‑> f:('data ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.unit
val iteri : ('key, 'data) t ‑> f:(key:'key ‑> data:'data ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.unit
val iter_vals : (_, 'data) t ‑> f:('data ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.unit
val filter_mapi : ('key, 'data1) t ‑> f:(key:'key ‑> data:'data1 ‑> 'data2 Core_kernel__.Import.option) ‑> ('key, 'data2) t
val filter_map : ('key, 'data1) t ‑> f:('data1 ‑> 'data2 Core_kernel__.Import.option) ‑> ('key, 'data2) t
val filter_keys : ('key, 'data1) t ‑> f:('key ‑> Core_kernel__.Import.bool) ‑> ('key, 'data1) t
val filter : ('key, 'data1) t ‑> f:('data1 ‑> Core_kernel__.Import.bool) ‑> ('key, 'data1) t
val filteri : ('key, 'data1) t ‑> f:(key:'key ‑> data:'data1 ‑> Core_kernel__.Import.bool) ‑> ('key, 'data1) t
val for_alli : ('key, 'data) t ‑> f:(key:'key ‑> data:'data ‑> Core_kernel__.Import.bool) ‑> Core_kernel__.Import.bool
val existsi : ('key, 'data) t ‑> f:(key:'key ‑> data:'data ‑> Core_kernel__.Import.bool) ‑> Core_kernel__.Import.bool
val for_all : (_, 'data) t ‑> f:('data ‑> Core_kernel__.Import.bool) ‑> Core_kernel__.Import.bool
val exists : (_, 'data) t ‑> f:('data ‑> Core_kernel__.Import.bool) ‑> Core_kernel__.Import.bool
val length : (_, _) t ‑> Core_kernel__.Import.int
val mem : ('key, _) t ‑> 'key ‑> Core_kernel__.Import.bool
val remove : ('key, _) t ‑> 'key ‑> Core_kernel__.Import.unit
val set : ('a, 'b) t ‑> key:'a ‑> data:'b ‑> Core_kernel__.Import.unit
val add : ('a, 'b) t ‑> key:'a ‑> data:'b ‑> [ `Ok | `Duplicate of 'b ]
val add_exn : ('a, 'b) t ‑> key:'a ‑> data:'b ‑> Core_kernel__.Import.unit
val to_alist : ('key, 'data) t ‑> ('key * 'data) Core_kernel__.Import.list
val clear : (_, _) t ‑> Core_kernel__.Import.unit