Abstract

Eytzinger tree-based key-value maps.

Requires an ordering on the elements to provide relatively efficient lookups.

Synopsis

module type eytzinger_unlifted = {
type key
type ctx
type map 'ctx [n] [f] 'v
val member [n] [f] 'v: ctx -> key -> map ctx [n] [f] v -> bool
val not_member [n] [f] 'v: ctx -> key -> map ctx [n] [f] v -> bool
val lookup [n] [f] 'v: ctx -> key -> map ctx [n] [f] v -> opt v
val from_array [u] 'v: ctx -> [u](key, v) -> ?[n][f].map ctx [n] [f] v
val from_array_rep [u] 'v: ctx -> [u]key -> v -> ?[n][f].map ctx [n] [f] v
val from_array_hist [u] 'v: ctx -> (v -> v -> v) -> v -> [u](key, v) -> ?[n][f].map ctx [n] [f] v
val from_array_nodup [n] 'v: ctx -> [n](key, v) -> ?[f].map ctx [n] [f] v
val from_array_rep_nodup [n] 'v: ctx -> [n]key -> v -> ?[f].map ctx [n] [f] v
val adjust [n] [f] [u] 'v: (v -> v -> v) -> v -> map ctx [n] [f] v -> [u](key, v) -> map ctx [n] [f] v
val map [n] [f] 'v 't: (g: (v -> t)) -> map ctx [n] [f] v -> map ctx [n] [f] t
val map_with_key [n] [f] 'v 't: (g: (key -> v -> t)) -> map ctx [n] [f] v -> map ctx [n] [f] t
val to_array [n] [f] 'v: map ctx [n] [f] v -> [n](key, v)
val update [n] [f] [u] 'v: map ctx [n] [f] v -> [u](key, v) -> map ctx [n] [f] v
val size [n] [f] 'v: map ctx [n] [f] v -> i64
val context [n] [f] 'v: map ctx [n] [f] v -> ctx
val insert [n] [f] [u] 'v: ctx -> map ctx [n] [f] v -> [u](key, v) -> ?[n'][f'].map ctx [n'] [f'] v
val insert_with [n] [f] [u] 'v: ctx -> (v -> v -> v) -> v -> map ctx [n] [f] v -> [u](key, v) -> ?[n'][f'].map ctx [n'] [f'] v
}
module mk_eytzinger_unlifted: (K: ordkey) -> eytzinger_unlifted with key = K.key with ctx = K.ctx
module mk_eytzinger: (K: ordkey) -> map with key = K.key with ctx = K.ctx

Description

↑module type eytzinger_unlifted
↑type key
↑type ctx
↑type map 'ctx [n] [f] 'v
↑val member [n] [f] 'v: ctx -> key -> map ctx [n] [f] v -> bool
↑val not_member [n] [f] 'v: ctx -> key -> map ctx [n] [f] v -> bool
↑val lookup [n] [f] 'v: ctx -> key -> map ctx [n] [f] v -> opt v
↑val from_array [u] 'v: ctx -> [u](key, v) -> ?[n][f].map ctx [n] [f] v
↑val from_array_rep [u] 'v: ctx -> [u]key -> v -> ?[n][f].map ctx [n] [f] v
↑val from_array_hist [u] 'v: ctx -> (v -> v -> v) -> v -> [u](key, v) -> ?[n][f].map ctx [n] [f] v
↑val from_array_nodup [n] 'v: ctx -> [n](key, v) -> ?[f].map ctx [n] [f] v
↑val from_array_rep_nodup [n] 'v: ctx -> [n]key -> v -> ?[f].map ctx [n] [f] v
↑val adjust [n] [f] [u] 'v: (v -> v -> v) -> v -> map ctx [n] [f] v -> [u](key, v) -> map ctx [n] [f] v
↑val map [n] [f] 'v 't: (g: (v -> t)) -> map ctx [n] [f] v -> map ctx [n] [f] t
↑val map_with_key [n] [f] 'v 't: (g: (key -> v -> t)) -> map ctx [n] [f] v -> map ctx [n] [f] t
↑val to_array [n] [f] 'v: map ctx [n] [f] v -> [n](key, v)
↑val update [n] [f] [u] 'v: map ctx [n] [f] v -> [u](key, v) -> map ctx [n] [f] v
↑val size [n] [f] 'v: map ctx [n] [f] v -> i64
↑val context [n] [f] 'v: map ctx [n] [f] v -> ctx
↑val insert [n] [f] [u] 'v: ctx -> map ctx [n] [f] v -> [u](key, v) -> ?[n'][f'].map ctx [n'] [f'] v
↑val insert_with [n] [f] [u] 'v: ctx -> (v -> v -> v) -> v -> map ctx [n] [f] v -> [u](key, v) -> ?[n'][f'].map ctx [n'] [f'] v
↑module mk_eytzinger_unlifted

A map that uses a eytzinger tree to represent the mapping.

↑module mk_eytzinger