29 lines
983 B
OCaml
Executable File
29 lines
983 B
OCaml
Executable File
open General
|
|
|
|
|
|
module type Map = sig
|
|
(** The type of keys in the map. *)
|
|
type key
|
|
|
|
(** Purely functional map, parameterised by the values stored in the map (not the keys). *)
|
|
type 'v map
|
|
|
|
(** The empty map. *)
|
|
val empty : 'v map
|
|
|
|
(** Inserts the key-value pair into the map. If the key already exists, it is overwritten. Runs in O(log(n)). *)
|
|
val insert : key * 'v -> 'v map -> 'v map
|
|
|
|
(** Fetches a value from the map based on the key. Returns an option to handle cases where the key is not present. Runs in O(log(n)). *)
|
|
val fetch : key -> 'v map -> 'v option
|
|
end
|
|
|
|
module type MapSpecification = sig
|
|
(** The type of keys in the map. *)
|
|
type key
|
|
(** Comparison should return a value less than 0 for when the first value is smaller, greater than 0 for when the second is smaller, and 0 when they are equivalent. *)
|
|
val comparison : key -> key -> int
|
|
end
|
|
|
|
module RBTreeMap (M : MapSpecification) : Map with type key = M.key
|