package core_kernel

  1. Overview
  2. Docs
package core_kernel
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Bounded_int_tableSource

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, keys, to_alist) take time proportional to the length of the table, not num_keys.

Sourcetype ('key, 'data) t
Sourceval sexp_of_t : ('key -> Sexplib0.Sexp.t) -> ('data -> Sexplib0.Sexp.t) -> ('key, 'data) t -> Sexplib0.Sexp.t
Sourcetype ('a, 'b) table = ('a, 'b) t
include Core.Invariant.S2 with type ('a, 'b) t := ('a, 'b) t
Sourceval invariant : ('a -> unit) -> ('b -> unit) -> ('a, 'b) t -> unit

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.Equal.S2 with type ('a, 'b) t := ('a, 'b) t
Sourceval create : ?sexp_of_key:('key -> Core.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.

Sourceval num_keys : (_, _) t -> int
Sourceval is_empty : (_, _) t -> bool

Standard hashtbl functions

Sourceval keys : ('key, _) t -> 'key list
Sourceval data : (_, 'data) t -> 'data list
Sourceval find : ('key, 'data) t -> 'key -> 'data option
Sourceval find_exn : ('key, 'data) t -> 'key -> 'data
Sourceval find_or_add : ('key, 'data) t -> 'key -> default:(unit -> 'data) -> 'data
Sourceval fold : ('key, 'data) t -> init:'accum -> f:(key:'key -> data:'data -> 'accum -> 'accum) -> 'accum
Sourceval iter_keys : ('key, _) t -> f:('key -> unit) -> unit
Sourceval iter : (_, 'data) t -> f:('data -> unit) -> unit
Sourceval iteri : ('key, 'data) t -> f:(key:'key -> data:'data -> unit) -> unit
Sourceval filter_mapi : ('key, 'data1) t -> f:(key:'key -> data:'data1 -> 'data2 option) -> ('key, 'data2) t
Sourceval filter_map : ('key, 'data1) t -> f:('data1 -> 'data2 option) -> ('key, 'data2) t
Sourceval filter_keys : ('key, 'data1) t -> f:('key -> bool) -> ('key, 'data1) t
Sourceval filter : ('key, 'data1) t -> f:('data1 -> bool) -> ('key, 'data1) t
Sourceval filteri : ('key, 'data1) t -> f:(key:'key -> data:'data1 -> bool) -> ('key, 'data1) t
Sourceval mapi : ('key, 'data1) t -> f:(key:'key -> data:'data1 -> 'data2) -> ('key, 'data2) t
Sourceval map : ('key, 'data1) t -> f:('data1 -> 'data2) -> ('key, 'data2) t
Sourceval for_alli : ('key, 'data) t -> f:(key:'key -> data:'data -> bool) -> bool
Sourceval existsi : ('key, 'data) t -> f:(key:'key -> data:'data -> bool) -> bool
Sourceval for_all : (_, 'data) t -> f:('data -> bool) -> bool
Sourceval exists : (_, 'data) t -> f:('data -> bool) -> bool
Sourceval length : (_, _) t -> int
Sourceval mem : ('key, _) t -> 'key -> bool
Sourceval remove : ('key, _) t -> 'key -> unit
Sourceval set : ('a, 'b) t -> key:'a -> data:'b -> unit
Sourceval add : ('a, 'b) t -> key:'a -> data:'b -> [ `Ok | `Duplicate of 'b ]
Sourceval add_exn : ('a, 'b) t -> key:'a -> data:'b -> unit
Sourceval to_alist : ('key, 'data) t -> ('key * 'data) list
Sourceval clear : (_, _) t -> unit
Sourcemodule With_key (Key : sig ... end) : sig ... end
Sourceval debug : bool Core.ref

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