Module Incremental__.Recompute_heap

type t
val sexp_of_t : t -> Ppx_sexp_conv_lib.Sexp.t
include Core_kernel.Invariant.S with type t := t
type t
val invariant : t Base__.Invariant_intf.inv
val create : max_height_allowed:int -> t
val length : t -> int
val max_height_allowed : t -> int

max_height_allowed is the maximum node.height allowed for node in t.

It is an error to call set_max_height_allowed t m if there is a node in t with node.height > m.

val set_max_height_allowed : t -> int -> unit
val min_height : t -> int

min_height t returns the smallest height of any element in t, or max_height_allowed + 1 if length t = 0.

val add : t -> _ Incremental__.Node.t -> unit

add t node should only be called iff:

not (Node.is_in_recompute_heap node)
&& Node.needs_to_be_computed node
&& node.height <= max_height_allowed t
val remove : t -> _ Incremental__.Node.t -> unit

remove t node should only be called iff:

Node.is_in_recompute_heap node
&& not (Node.needs_to_be_computed node)
val remove_min : t -> Incremental__.Node.Packed.t

remove_min t removes and returns a node in t with minimum height. remove_min should only be called if length t > 0.

val increase_height : t -> _ Incremental__.Node.t -> unit

increase_height t node should only be called when:

  • node.height > node.height_in_recompute_heap
  • node.height <= max_height_allowed t
  • Node.is_in_recompute_heap node

It changes node.height_in_recompute_heap to equal node.height and adjusts node's position in t.