Skip to main content

/

Docs

Nightly

v25.1

Log in

Mojo struct

IntervalTree

struct IntervalTree[T: IntervalElement, U: IntervalPayload]

An interval tree data structure for efficient range queries.

Parameters​

  • ​T (IntervalElement): The type of the interval bounds, must support subtraction, integer conversion, string conversion, comparison and collection operations.
  • ​U (IntervalPayload): The type of the associated data, must support string conversion and collection operations.

Implemented traits​

AnyType, UnknownDestructibility, Writable

Methods​

__init__​

__init__(out self)

Initializes an empty IntervalTree.

insert​

insert(mut self, interval: Tuple[T, T], data: U)

Insert a new interval into the tree using a tuple representation.

Args:

  • ​interval (Tuple[T, T]): A tuple containing the start and end values of the interval.
  • ​data (U): The data value to associate with this interval.

insert(mut self, interval: Interval[T], data: U)

Insert a new interval into the tree.

This method inserts a new interval and its associated data into the interval tree. It maintains the binary search tree property based on interval start times and updates the tree structure to preserve red-black tree properties.

Args:

  • ​interval (Interval[T]): The interval to insert into the tree.
  • ​data (U): The data value to associate with this interval.

__str__​

__str__(self) -> String

Returns a string representation of the interval tree.

Returns:

A string representation of the interval tree.

__repr__​

__repr__(self) -> String

Returns a string representation of the interval tree suitable for debugging.

Returns:

A string representation of the interval tree.

write_to​

write_to[w: Writer](self, mut writer: w)

Writes the interval tree to a writer.

Parameters:

  • ​w (Writer): The writer type that implements the Writer trait.

Args:

  • ​writer (w): The writer to write the interval tree to.

depth​

depth(self) -> Int

Returns the depth of the interval tree.

Returns:

The depth of the interval tree.

transplant​

transplant(mut self, mut u: UnsafePointer[_IntervalNode[T, U]], mut v: UnsafePointer[_IntervalNode[T, U]])

Transplants the subtree rooted at node u with the subtree rooted at node v.

Args:

  • ​u (UnsafePointer[_IntervalNode[T, U]]): The node to transplant.
  • ​v (UnsafePointer[_IntervalNode[T, U]]): The node to transplant to.

search(self, interval: Tuple[T, T]) -> List[U]

Searches for intervals overlapping with the given tuple.

Args:

  • ​interval (Tuple[T, T]): The interval tuple (start, end).

Returns:

A list of data associated with overlapping intervals.

search(self, interval: Interval[T]) -> List[U]

Searches for intervals overlapping with the given interval.

Args:

  • ​interval (Interval[T]): The interval to search.

Returns:

A list of data associated with overlapping intervals.