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.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: Comparable & Writable & Copyable & Deinitable]

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

Implemented traits​

AnyType, Defaultable, Deinitable, Movable, Writable

Methods​

__init__​

def __init__(out self)

Initializes an empty IntervalTree.

__deinit__​

def __deinit__(deinit self)

Destructor that frees the interval tree's memory.

insert​

def 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.

def 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​

def 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​

def 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​

def depth(self) -> Int

Returns the depth of the interval tree.

Returns:

Int: The depth of the interval tree.

transplant​

def transplant(mut self, mut u: Optional[Pointer[_IntervalNode[T, U], MutUntrackedOrigin]], mut v: Optional[Pointer[_IntervalNode[T, U], MutUntrackedOrigin]])

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

Args:

def 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.

def 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