Struct IntervalTree

pub struct IntervalTree<T: Clone> { /* private fields */ }

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

impl<T: Clone> IntervalTree<T>

pub fn new() -> Self

Creates an empty interval tree.

pub fn size(&self) -> usize

pub fn insert<F: Fn(T, T) -> T>( &mut self, key: impl Into<TextRange>, val: T, merge_fn: F, ) -> Option<&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.

pub fn get(&self, key: impl Into<TextRange>) -> Option<T>

Finds the node with key key in the tree and returns its value if found.

Arguments

• key - The text range representing the interval to search for.

Returns

An optional value associated with the node if it exists, None otherwise.

pub fn get_node_mut( &mut self, key: impl Into<TextRange>, ) -> Option<&mut Node<T>>

pub fn delete_exact(&mut self, key: impl Into<TextRange>) -> MaybeNode<T>

Delete the node with key key from the tree. The key must excatly match an interval in 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.

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>

pub fn delete(&mut self, range: impl Into<TextRange>, del_extend: bool)

Deletes intervals from the tree that intersect with the given range.

The behavior depends on the del_extend parameter:

• If true, deletes all intervals that intersect with the range
• If false, only deletes the intersecting portions of intervals, preserving non-intersecting parts by splitting them into new intervals

Arguments

• range - The range to delete (can be any type that converts to TextRange)
• del_extend - Whether to delete entire intersecting intervals or just the overlapping portions

Examples

use interval_tree::{IntervalTree, TextRange};

let mut tree = IntervalTree::new();
tree.insert(TextRange::new(0, 10), 1, |a, _| a);

// Delete only overlapping portion
tree.delete(TextRange::new(5, 15), false);
assert_eq!(tree.find_intersects(TextRange::new(0, 10)).collect::<Vec<_>>().len(), 1);

let mut tree = IntervalTree::new();
tree.insert(TextRange::new(0, 10), 1, |a, _| a);

// Delete entire intersecting interval
tree.delete(TextRange::new(5, 15), true);
assert!(tree.find_intersects(TextRange::new(0, 10)).next().is_none());

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.

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.

pub fn find_intersects( &self, range: impl Into<TextRange>, ) -> impl Iterator<Item = &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.

pub fn find_intersect_min( &self, range: impl Into<TextRange>, ) -> Option<&Node<T>>

Finds the node with the minimum key that intersects with the given range.

This function searches for the leftmost node in the tree whose interval overlaps with the specified range. It’s useful for finding the first intersecting interval in sorted order.

Arguments

• range - The range to search for intersections (can be any type that converts to TextRange)

Returns

An optional reference to the node with the minimum intersecting key, or None if no intersection is found.

Examples

use interval_tree::{IntervalTree, TextRange};

let mut tree = IntervalTree::new();
tree.insert(TextRange::new(0, 5), 1, |a, _| a);
tree.insert(TextRange::new(5, 10), 2, |a, _| a);

let node = tree.find_intersect_min(TextRange::new(3, 7));
assert_eq!(node.unwrap().key, TextRange::new(0, 5));

pub fn find_intersect_max( &self, range: impl Into<TextRange>, ) -> Option<&Node<T>>

Like find_intersect_min, but finds the maximum key.

pub fn min(&self) -> Option<&Node<T>>

Return the minimum node in the tree, or None if the tree is empty.

pub fn clean<F: Fn(&T, &T) -> bool, G: Fn(&T) -> bool>( &mut self, eq: F, empty: G, )

Cleans the interval tree by:

1. Removing empty intervals or intervals with empty values
2. Merging adjacent intervals with equal values

This function iterates through the tree in order and:

• Removes any node where the interval is empty or the value is considered empty
• Merges adjacent nodes when their values are considered equal

Arguments

• eq - A closure that determines if two values should be considered equal
• empty - A closure that determines if a value should be considered empty

Examples

use interval_tree::{IntervalTree, TextRange};

let mut tree = IntervalTree::new();
tree.insert(TextRange::new(0, 5), 1, |a, _| a);
tree.insert(TextRange::new(5, 10), 1, |a, _| a);
tree.insert(TextRange::new(10, 15), 2, |a, _| a);
tree.insert(TextRange::new(15, 20), 0, |a, _| a); // Empty value

// Clean the tree, merging equal values and removing empty ones
tree.clean(|a, b| a == b, |v| *v == 0);

assert_eq!(tree.find_intersects(TextRange::new(0, 20)).collect::<Vec<_>>().len(), 2);

pub fn clean_from<F: Fn(&T, &T) -> bool, G: Fn(&T) -> bool>( &mut self, start: TextRange, eq: F, empty: G, )

pub fn merge<F: Fn(&T, &T) -> bool>(&mut self, eq: 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 returns true if they are considered equal, false otherwise.

pub fn apply<F: FnMut(&T)>(&self, f: &mut F)

pub fn apply_mut<F: FnMut(&mut Node<T>)>(&mut self, f: &mut F)

pub fn apply_with_split<F: Fn(T) -> Option<T>>( &mut self, f: F, range: impl Into<TextRange>, )

Applies a transformation function to intervals that intersect with the given range, splitting intervals as needed to apply the function only to the intersecting portions.

The function f takes the current value of an interval and returns:

• Some(new_value) to update the interval’s value
• None to remove the interval entirely

If an interval only partially intersects with the range, it will be split into non-intersecting and intersecting parts, with f only applied to the intersecting part.

Arguments

• f - Transformation function to apply to intersecting intervals
• range - The range to check for intersections (can be any type that converts to TextRange)

Examples

use interval_tree::{IntervalTree, TextRange};

let mut tree = IntervalTree::new();
tree.insert(TextRange::new(0, 10), 1, |a, _| a);

// Double values in range 5-15
tree.apply_with_split(|val| Some(val * 2), TextRange::new(5, 15));

// Remove intervals in range 7-8
tree.apply_with_split(|_| None, TextRange::new(7, 8));

impl<T: Clone + Debug> IntervalTree<T>

pub fn print(&self)

Recursively print out the tree, for debugging purposes. The output format is not guaranteed to be stable.

Trait Implementations

impl<T: Clone + Clone> Clone for IntervalTree<T>

fn clone(&self) -> IntervalTree<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Clone + Debug> Debug for IntervalTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default + Clone> Default for IntervalTree<T>

fn default() -> IntervalTree<T>

Returns the “default value” for a type.