Interval_tree (bap.Bap.Std.Interval

Module Std.Interval_tree

Balanced Interval Tree.

Interval trees are used to build efficient mappings from intervals to arbitrary data.

The interval tree may contain overlapping intervals and allows inserting and removing elements.

The interval tree is implemented using AVL trees.

since 1.4

Abstract Interval.

Abstractly an interval is a pair of points, with one point being the lower bound and another is the upper bound. The upper bound shall be greater or equal than the lower bound, i.e., compare (lower x) (upper x) <= 0 for all intervals x.

The interval x represents a set of points that are greater or equal than the lower x and less than or equal than upper x. (Thus, empty intervals are not representable).

module type Interval = sig ... end

module type S = sig ... end

The Interval Tree Interface.

module Make
  (Interval : Interval) : 
  S with type key := Interval.t and type point := Interval.point

Make(Interval) create an abstract interval tree data type that uses abstract Interval.

module type Interval_binable = sig ... end

Binable Abstract Interval.

module type S_binable = sig ... end

Binable Interval Tree.

module Make_binable
  (Interval : Interval_binable) : 
  S_binable with type key := Interval.t and type point := Interval.point

Make_binable(Interval) create an abstract interval tree data type that uses abstract Interval and can be serialized via the Binable interface.