Std.IntervalTree

13 public declarations

• emptyStd.IntervalTree.IntervalTree

  Creates an empty interval tree.

  fn
• findOverlaps&Std.IntervalTree.IntervalTree -> Std.IntervalTree.Interval -> Array[Std.IntervalTree.Interval]

  Finds all intervals in the tree that overlap with the query interval.

  fn
• fromIntervals&Array[Std.IntervalTree.Interval] -> Std.IntervalTree.IntervalTree

  Builds a balanced interval tree from an array of intervals in O(n log n) time.

  fn
• hasOverlap&Std.IntervalTree.IntervalTree -> Std.IntervalTree.Interval -> Bool

  Tests whether any interval in the tree overlaps with the query interval.

  fn
• insert&Std.IntervalTree.IntervalTree -> Std.IntervalTree.Interval -> Std.IntervalTree.IntervalTree

  Inserts an interval into the tree and updates subtree maximum endpoints.

  fn
• intervalInt -> Int -> Option[Std.IntervalTree.Interval]

  Validates and constructs an interval where low <= high.

  fn
• Interval

  Closed 1D interval where low <= high.

  type
• IntervalNode

  Internal interval tree node storing subtree maximum endpoint.

  type
• IntervalTree

  Augmented Interval Tree indexing closed 1D intervals with O(log n + k) queries.

  type
• isEmpty&Std.IntervalTree.IntervalTree -> Bool

  Returns whether the tree contains no intervals.

  fn
• pointQuery&Std.IntervalTree.IntervalTree -> Int -> Array[Std.IntervalTree.Interval]

  Stabbing query finding all intervals containing the given point.

  fn
• size&Std.IntervalTree.IntervalTree -> Int

  Returns the number of intervals stored in the tree.

  fn
• toIntervals&Std.IntervalTree.IntervalTree -> Array[Std.IntervalTree.Interval]

  Materializes all intervals sorted by low endpoint in O(n) time.

  fn