rs-06-interval-map
1.000
Proposed solution
I'll implement a generic interval map that stores integer intervals and maps them to values. Here's my solution:
```rust
// src/lib.rs
pub struct IntervalMap<T> {
intervals: Vec<Interval<T>>,
}
struct Interval<T> {
start: i64,
end: i64,
value: T,
}
impl<T> IntervalMap<T> {
pub fn new() -> Self {
IntervalMap { intervals: Vec::new() }
}
pub fn insert(&mut self, start: i64, end: i64, value: T) {
if start >= end {
return;
}
self.intervals.push(Interval {
start,
end,
value,
});
}
pub fn get(&self, point: i64) -> Option<&T> {
// Search from the end (most recent) to find the first interval that covers the point
for interval in self.intervals.iter().rev() {
if interval.start <= point && point < interval.end {
return Some(&interval.value);
}
}
None
}
pub fn get_all(&self, point: i64) -> Vec<&T> {
let mut result = Vec::new();
// Search from the end (most recent) to collect all intervals covering the point
for interval in self.intervals.iter().rev() {
if interval.start <= point && point < interval.end {
result.push(&interval.value);
}
}
result
}
}
```
This implementation:
1. Uses a `Vec` to store intervals in insertion order, which allows us to efficiently handle the "newest insert wins" behavior for `get()`.
2. For `insert()`, it simply adds the interval to the vector if it's valid (start < end).
3. For `get()`, it searches from the end of the vector backwards to find the first interval that covers the point, which gives us the most recently inserted one.
4. For `get_all()`, it collects all intervals that cover the point in reverse order (most recent first).
The time complexity is O(n) for both `get()` and `get_all()` where n is the number of intervals, which is acceptable for a simple implementation. The space complexity is O(n) to store the intervals.Test output (stdout)
running 0 tests test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 6 tests ...... test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 0 tests test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.