IMPORTANT: To view this page as Markdown, append `.md` to the URL (e.g. /docs/manual/basics.md). For the complete Mojo documentation index, see llms.txt.
Skip to main content
Version: 1.0
For the complete Mojo documentation index, see llms.txt. Markdown versions of all pages are available by appending .md to any URL (e.g. /docs/manual/basics.md).

IntervalTree

struct IntervalTree[T: IntervalElement, U: Copyable & Comparable & Writable]

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 (Copyable & Comparable & Writable): The type of the associated data, must support string conversion and collection operations.

Implemented traits​

AnyType, Defaultable, ImplicitlyDestructible, Writable

Methods​

__init__​

__init__(out self)

Initializes an empty IntervalTree.

__del__​

__del__(deinit self)

Destructor that frees the interval tree's memory.

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.

write_to​

write_to(self, mut writer: T)

Writes the interval tree to a writer.

Args:

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

write_repr_to​

write_repr_to(self, mut writer: T)

Write the repr of this IntervalTree to a writer.

Args:

  • ​writer (T): The object to write to.

depth​

depth(self) -> Int

Returns the depth of the interval tree.

Returns:

Int: The depth of the interval tree.

transplant​

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

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

Args:

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:

List[U]: A list of data associated with overlapping intervals.

Raises:

If the operation fails.

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

Searches for intervals overlapping with the given interval.

Args:

Returns:

List[U]: A list of data associated with overlapping intervals.

Raises:

If the operation fails.

View source