Rust - Implementing interval or segment trees on top of sorted vectors

Implementing interval or segment trees can seem daunting, but Rust's robust system makes it easier to handle complexities with safety and speed. This article will guide you through implementing an interval tree on top of sorted vectors in Rust, providing a concise and highly performant solution for interval queries.

Introduction to Interval Trees

An interval tree is a data structure built to store intervals or segments, and it allows for efficient searching into which interval a particular point falls. This is particularly useful in various applications such as computational geometry, data retrieval, and network packet filtering.

Prerequisites

Before we start, ensure that you have Rust installed. You can install it from the official Rust website. Learn basic Rust syntax and ownership, as this tutorial requires an understanding of Rust's iterative nature and mutable borrowing.

Structure of the Implementation

Our implementation will consist of a basic vector operation where intervals are maintained in a sorted structure. We will define our Interval structure, functions to insert, delete, and query intervals, and utilize binary search for efficient retrieval.

Step 1: Setting Up Your Rust Project

First, create a new Rust project:

cargo new interval_tree

Navigate to the project directory:

cd interval_tree

Open src/main.rs in a code editor.

Step 2: Define the Interval

We'll first define the core structure, Interval, with two fields representing the start and end of the segment:

#[derive(Debug, Clone)]
struct Interval {
    start: i32,
    end: i32,
}

Implement the constructor for Interval:

impl Interval {
    fn new(start: i32, end: i32) -> Self {
        Interval { start, end }
    }
}

Step 3: Implement the Interval Tree

We will use a vector to store the intervals:

struct IntervalTree {
    intervals: Vec,
}

Implement the tree with functions for insertion and searching:

impl IntervalTree {
    fn new() -> Self {
        IntervalTree {
            intervals: Vec::new(),
        }
    }

    fn insert(&mut self, interval: Interval) {
        self.intervals.push(interval);
        self.intervals.sort_by(|a, b| a.start.cmp(&b.start));
    }

    fn search(&self, point: i32) -> Vec<&Interval> {
        self.intervals.iter()
            .filter(|interval| point >= interval.start && point <= interval.end)
            .collect()
    }
}

Step 4: Testing the Interval Tree

We will now test the implementation to ensure it works as intended. Add the following code to your main.rs:

fn main() {
    let mut tree = IntervalTree::new();

    tree.insert(Interval::new(1, 3));
    tree.insert(Interval::new(2, 5));
    tree.insert(Interval::new(6, 8));

    let results = tree.search(4);
    println!("Intervals containing point 4: {:?}", results);
}

This code should output intervals that contain the queried point. Adjust the logic if your output doesn’t match expectations, and use the documentation to understand Rust’s cmp and iterators more thoroughly.

Conclusion

You've implemented an interval tree in Rust! Using sorted vectors enables optimisation in search operations. While this is a simplistic model, it can be expanded further—for example, handling overlapping intervals or adding parallel processing for even faster query times, leveraging Rust's concurrency model.

Moving forward, consider digging deeper into Rust’s advanced features such as lifetime annotations, more comprehensive use of the std::cmp library, and exploring Rust's powerful pattern matching capabilities.