pub struct IntervalTree<T: Clone> { /* private fields */ }Expand description
A interval tree using red-black tree, whereas keys are intervals, and values are plists in elisp.
All intervals are half-opened intervals, i.e. I = [start, end).These intervals
are sorted by their starting point, then their ending point.
NOTE When inserting an interval I, if I intersects with some existing interval J but I != J, then we split & merge I and J into sub-intervals. Thus all intervals inside a interval tree will not overlap. Adjacant intervals with identical props should be merged afterwards, maybe during redisplay.
Implementations§
Source§impl<T: Clone> IntervalTree<T>
impl<T: Clone> IntervalTree<T>
Sourcepub fn insert<'a, F: Fn(T, T) -> T>(
&'a mut self,
key: impl Into<TextRange>,
val: T,
merge_fn: F,
) -> Option<&'a mut Box<Node<T>>>
pub fn insert<'a, F: Fn(T, T) -> T>( &'a mut self, key: impl Into<TextRange>, val: T, merge_fn: F, ) -> Option<&'a mut Box<Node<T>>>
Inserts a new interval with the specified key and val into the interval tree.
If the interval key is degenerate (i.e., its start equals its end), the function
returns None as such intervals are not allowed in the tree. Otherwise, it delegates
the insertion to the underlying node structure.
§Arguments
key- The text range representing the interval to insert.val- The value associated with the interval.merge- A closure that specifies how to merge intervals if they overlap
§Returns
An optional mutable reference to the newly inserted node, or None if the interval is
degenerate.
Sourcepub fn delete(&mut self, key: impl Into<TextRange>) -> MaybeNode<T>
pub fn delete(&mut self, key: impl Into<TextRange>) -> MaybeNode<T>
Delete the node with key key from the tree.
If the root node is the only black node, then we have to make it red before deleting. Otherwise, the tree would become unbalanced.
After deleting, we make sure the root node is black again.
Sourcepub fn delete_min(&mut self) -> MaybeNode<T>
pub fn delete_min(&mut self) -> MaybeNode<T>
Deletes the node with the minimum key from the interval tree.
If the root node is the only black node, it is temporarily colored red to maintain tree balance during deletion. After deletion, the root node is recolored black to ensure the red-black tree properties are preserved.
§Returns
An optional Node<T> representing the removed node, or None if
the tree is empty.
pub fn delete_max(&mut self) -> MaybeNode<T>
Sourcepub fn advance(&mut self, position: usize, length: usize)
pub fn advance(&mut self, position: usize, length: usize)
Advances all intervals in the tree by length, starting at
position. This is typically used to implement operations that insert
or delete text in a buffer.
Sourcepub fn find(&self, position: usize) -> Option<&Node<T>>
pub fn find(&self, position: usize) -> Option<&Node<T>>
Find the node whose interval contains the given position. If no interval
contains the position, returns None.
Sourcepub fn find_intersects(&self, range: TextRange) -> Vec<&Node<T>>
pub fn find_intersects(&self, range: TextRange) -> Vec<&Node<T>>
Find all nodes in the tree whose intervals intersect the given
range. The result is a vector of references to the found nodes.
Sourcepub fn min(&self) -> Option<&Node<T>>
pub fn min(&self) -> Option<&Node<T>>
Return the minimum node in the tree, or None if the tree is empty.
Sourcepub fn merge<F: Fn(&T, &T) -> bool>(&mut self, equal: F)
pub fn merge<F: Fn(&T, &T) -> bool>(&mut self, equal: F)
Merges adjacent intervals in the tree that have equal properties.
This function iterates over the nodes in the interval tree, starting from
the minimum node. It checks if the current node’s end equals the next node’s
start and if their values are considered equal by the provided equal
function. If both conditions are met, it merges the intervals by extending
the current node’s end to the next node’s end and deletes the next node.
§Arguments
equal- A closure that takes references to two values and returnstrueif they are considered equal,falseotherwise.