rs-06-interval-map

# Generic interval map

Implement the library file **`src/lib.rs`** exposing a generic structure that maps integer
intervals to values:

```rust
pub struct IntervalMap<T> { /* ... */ }

impl<T> IntervalMap<T> {
    pub fn new() -> Self;
    pub fn insert(&mut self, start: i64, end: i64, value: T);
    pub fn get(&self, point: i64) -> Option<&T>;
    pub fn get_all(&self, point: i64) -> Vec<&T>;
}
```

Intervals are **half-open**: `[start, end)` covers every `p` with `start <= p < end`.

- **`insert(start, end, value)`** records that the half-open interval `[start, end)` maps to
  `value`. If `start >= end` the range is empty and the call is a **no-op**. Intervals may overlap.
- **`get(point)`** returns the value of the **most recently inserted** interval that covers `point`,
  or `None` if no interval covers it. (Newest insert wins on overlap.)
- **`get_all(point)`** returns references to the values of **all** intervals covering `point`,
  ordered **most-recently-inserted first**. Empty `Vec` if none cover it.

The structure is generic over the value type `T` (no trait bounds required). Values are owned by the
map; `get`/`get_all` return borrows.

Tests live in `tests/` and use `challenge::IntervalMap`.

use challenge::IntervalMap;

#[test]
fn point_lookup_respects_half_open_bounds() {
    let mut m = IntervalMap::new();
    m.insert(0, 10, "a");
    assert_eq!(m.get(5), Some(&"a"));
    assert_eq!(m.get(0), Some(&"a")); // start is inclusive
    assert_eq!(m.get(10), None); // end is exclusive
    assert_eq!(m.get(-1), None);
}

#[test]
fn empty_map_returns_none() {
    let m: IntervalMap<i32> = IntervalMap::new();
    assert_eq!(m.get(0), None);
    assert_eq!(m.get_all(0), Vec::<&i32>::new());
}

#[test]
fn newest_insert_wins_on_overlap() {
    let mut m = IntervalMap::new();
    m.insert(0, 10, 1);
    m.insert(5, 15, 2);
    assert_eq!(m.get(2), Some(&1)); // only the first interval
    assert_eq!(m.get(7), Some(&2)); // overlap -> newest wins
    assert_eq!(m.get(12), Some(&2)); // only the second interval
}

#[test]
fn get_all_returns_all_covering_newest_first() {
    let mut m = IntervalMap::new();
    m.insert(0, 10, 1);
    m.insert(5, 15, 2);
    m.insert(6, 8, 3);
    assert_eq!(m.get_all(7), vec![&3, &2, &1]);
    assert_eq!(m.get_all(2), vec![&1]);
    assert_eq!(m.get_all(20), Vec::<&i32>::new());
}

#[test]
fn empty_or_reversed_ranges_are_ignored() {
    let mut m = IntervalMap::new();
    m.insert(5, 5, "empty");
    m.insert(8, 3, "reversed");
    assert_eq!(m.get(5), None);
    assert_eq!(m.get(4), None);
}

#[test]
fn works_with_owned_string_values() {
    let mut m = IntervalMap::new();
    m.insert(0, 100, String::from("x"));
    assert_eq!(m.get(50), Some(&String::from("x")));
}

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.

```rust
pub struct IntervalMap<T> {
    intervals: Vec<(i64, i64, T, usize)>,
}

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 {
            self.intervals.push((start, end, value, self.intervals.len()));
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        for &(start, end, ref value, _) in self.intervals.iter().rev() {
            if start <= point && point < end {
                return Some(value);
            }
        }
        None
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        let mut result = Vec::new();
        for &(start, end, ref value, _) in self.intervals.iter().rev() {
            if start <= point && point < end {
                result.push(value);
            }
        }
        result
    }
}
```

The user wants me to implement a generic interval map in Rust. Let me break down the requirements:

1. `IntervalMap<T>` - a generic structure that maps integer intervals to values
2. `new()` - creates a new empty map
3. `insert(start, end, value)` - inserts a half-open interval `[start, end)` mapping to `value`. If `start >= end`, it's a no-op. Intervals can overlap, and newer inserts win.
4. `get(point)` - returns the value of the most recently inserted interval covering `point`, or `None` if none cover it
5. `get_all(point)` - returns references to all values covering `point`, ordered most-recently-inserted first

Key considerations:
- Intervals are half-open: `[start, end)` means `start <= p < end`
- Overlapping intervals are allowed
- Newer insertions override older ones for `get()`
- `get_all()` should return all covering intervals in reverse insertion order (newest first)
- Generic over `T` with no trait bounds

For efficient implementation, I should consider:
- Storing intervals with their insertion order
- For `get()` and `get_all()`, I need to find all intervals where `start <= point < end`
- Since we need to return in insertion order (newest first), storing with insertion index would help

A simple approach:
- Store a vector of `(start, end, value, index)` where index is the insertion order
- For `get()` and `get_all()`, iterate through all intervals and check if they cover the point
- Return in reverse order of insertion index

This is O(n) per query, but for a library implementation without specific performance requirements, this is acceptable and simple.

Let me write the code:

```rust
pub struct IntervalMap<T> {
    intervals: Vec<(i64, i64, T, usize)>,
}

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 {
            self.intervals.push((start, end, value, self.intervals.len()));
        }
    }
    
    pub fn get(&self, point: i64) -> Option<&T> {
        for &(start, end, ref value, _) in self.intervals.iter().rev() {
            if start <= point && point < end {
                return Some(value);
            }
        }
        None
    }
    
    pub fn get_all(&self, point: i64) -> Vec<&T> {
        let mut result = Vec::new();
        for &(start, end, ref value, _) in self.intervals.iter().rev() {
            if start <= point && point < end {
                result.push(value);
            }
        }
        result
    }
}
```

I'm tracking the insertion order to ensure correct retrieval of intervals. The implementation uses a simple vector-based approach that maintains the insertion sequence for efficient querying.

The key strategy involves storing intervals with their insertion index, allowing precise control over interval matching and retrieval. By iterating in reverse, we prioritize newer interval insertions, which matches the problem's requirements.

The implementation handles half-open intervals carefully, ensuring point coverage is correctly determined through start and end boundary checks.

I'll focus on creating a robust solution that supports flexible interval mapping while maintaining clear, predictable behavior for interval queries.