Mojo struct
IntervalTree
struct IntervalTree[T: IntervalElement, U: Copyable & Movable & Stringable & EqualityComparable & LessThanComparable & GreaterThanComparable & LessThanOrEqualComparable & GreaterThanOrEqualComparable]
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&Movable&Stringable&EqualityComparable&LessThanComparable&GreaterThanComparable&LessThanOrEqualComparable&GreaterThanOrEqualComparable): The type of the associated data, must support string conversion and collection operations.
Implemented traits
AnyType,
Defaultable,
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): 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): 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:
String: A string representation of the interval tree.
__repr__
__repr__(self) -> String
Returns a string representation of the interval tree suitable for debugging.
Returns:
String: 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:
Int: 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): The node to transplant. - v (
UnsafePointer): The node to transplant to.
search
Was this page helpful?
Thank you! We'll create more content like this.
Thank you for helping us improve!