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
// src/lib.rs
use std::collections::HashMap;

pub struct IntervalMap<T> {
    intervals: Vec<(i64, i64, usize)>,
    values: Vec<T>,
    point_to_intervals: HashMap<i64, Vec<usize>>,
}

impl<T> IntervalMap<T> {
    pub fn new() -> Self {
        IntervalMap {
            intervals: Vec::new(),
            values: Vec::new(),
            point_to_intervals: HashMap::new(),
        }
    }

    pub fn insert(&mut self, start: i64, end: i64, value: T) {
        if start >= end {
            return;
        }

        self.values.push(value);
        let index = self.values.len() - 1;
        self.intervals.push((start, end, index));

        // Update point_to_intervals for the new interval
        for p in start..end {
            self.point_to_intervals
                .entry(p)
                .or_insert_with(Vec::new)
                .push(index);
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        self.point_to_intervals
            .get(&point)
            .and_then(|indices| {
                indices
                    .iter()
                    .rev()
                    .find_map(|&index| self.intervals.get(index).and_then(|(s, e, i)| {
                        if *s <= point && point < *e {
                            Some(&self.values[*i])
                        } else {
                            None
                        }
                    }))
            })
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        self.point_to_intervals
            .get(&point)
            .map(|indices| {
                indices
                    .iter()
                    .rev()
                    .filter_map(|&index| {
                        self.intervals.get(index).and_then(|(s, e, i)| {
                            if *s <= point && point < *e {
                                Some(&self.values[*i])
                            } else {
                                None
                            }
                        })
                    })
                    .collect()
            })
            .unwrap_or_default()
    }
}
```