Module Incremental_kernel__.Recompute_heap

A module internal to Incremental. Users should see Incremental_intf.

The recompute heap holds the set of nodes such that Node.needs_to_be_computed. It is used during stabilization to visit the nodes that need to be computed in topological order, using the recompute heap to visit them in increasing order of height.

type t
include sig ... end
val sexp_of_t : t ‑> Base.Sexp.t
include Core_kernel.Invariant.S with type t := t
type t
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_kernel__.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_kernel__.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_kernel__.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_kernel__.Node.t ‑> unit

increase_height t node should only be called when:

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