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<Interval<T>>,
}

struct Interval<T> {
    start: i64,
    end: i64,
    value: T,
}

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

    pub fn insert(&mut self, start: i64, end: i64, value: T) {
        if start < end {
            self.intervals.push(Interval { start, end, value });
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        self.intervals
            .iter()
            .rev()
            .find(|iv| point >= iv.start && point < iv.end)
            .map(|iv| &iv.value)
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        self.intervals
            .iter()
            .rev()
            .filter(|iv| point >= iv.start && point < iv.end)
            .map(|iv| &iv.value)
            .collect()
    }
}
```

The user wants a generic interval map in Rust.
The structure should map integer intervals `[start, end)` to values of type `T`.
It needs to support:
- `new()`: create empty map
- `insert(start, end, value)`: insert interval. If `start >= end`, no-op. Overlaps allowed.
- `get(point)`: returns `Option<&T>` for the most recently inserted interval covering `point`.
- `get_all(point)`: returns `Vec<&T>` of all intervals covering `point`, ordered most-recently-inserted first.

Constraints:
- Generic over `T` with no trait bounds.
- Values are owned by the map.
- `get`/`get_all` return borrows.
- Intervals are half-open `[start, end)`.
- `start` and `end` are `i64`.

Let's think about the data structure.
Since we need to query by point and return intervals covering it, and we need to maintain insertion order for "most recently inserted", a simple list of intervals might work, but querying could be O(N). Given it's a coding challenge, maybe O(N) is acceptable, or we can use a more efficient structure. But the problem doesn't specify performance constraints. I'll stick to a simple `Vec` of intervals for now, unless there's a reason to optimize. Wait, `get_all` needs to return references ordered by insertion time (newest first). If we store intervals in a `Vec` in insertion order, we can just iterate backwards.

Let's define an internal struct:
```rust
struct Interval<T> {
    start: i64,
    end: i64,
    value: T,
}
```

`IntervalMap<T>` will contain a `Vec<Interval<T>>`.

`insert`:
```rust
pub fn insert(&mut self, start: i64, end: i64, value: T) {
    if start < end {
        self.intervals.push(Interval { start, end, value });
    }
}
```

`get`:
```rust
pub fn get(&self, point: i64) -> Option<&T> {
    self.intervals.iter().rev().find(|iv| point >= iv.start && point < iv.end).map(|iv| &iv.value)
}
```

`get_all`:
```rust
pub fn get_all(&self, point: i64) -> Vec<&T> {
    self.intervals.iter().rev().filter(|iv| point >= iv.start && point < iv.end).map(|iv| &iv.value).collect()
}
```

This is O(N) per query. Is that acceptable? Usually for these challenges, unless specified, O(N) is fine. But maybe we can do better? The problem says "Generic interval map", often implies something like a segment tree or interval tree, but with `i64` coordinates, a dynamic segment tree or coordinate compression might be needed. However, `i64` range is huge, so coordinate compression or a balanced BST of intervals is typical. But given the simplicity of the API and no performance constraints mentioned, a `Vec` is probably intended. Also, `get_all` returning all overlapping intervals suggests that overlaps can be many, so O(N) might be unavoidable in worst case anyway.

Wait, let's consider if there's any hidden trap. "Values are owned by the map; `get`/`get_all` return borrows." - handled.
"Intervals may overlap." - handled.
"Newest insert wins on overlap." - handled by iterating backwards.
"Empty Vec if none cover it." - handled.

One thing: `get_all` returns `Vec<&T>`. The lifetime of the references will be tied to `&self`. That's fine.

Let's check the exact signatures:
```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>;
}
```

I'll implement it exactly like that.

Is there any reason to use a more complex structure? Sometimes these challenges are from platforms like Exercism or similar, where O(N) is perfectly fine. I'll stick with `Vec`.

Wait, could there be a requirement for efficiency? The problem statement doesn't mention performance. I'll keep it simple.

Let's write out the full code.

```rust
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 {
        Self {
            intervals: Vec::new(),
        }
    }

    pub fn insert(&mut self, start: i64, end: i64, value: T) {
        if start < end {
            self.intervals.push(Interval { start, end, value });
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        self.intervals
            .iter()
            .rev()
            .find(|iv| point >= iv.start && point < iv.end)
            .map(|iv| &iv.value)
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        self.intervals
            .iter()
            .rev()
            .filter(|iv| point >= iv.start && point < iv.end)
            .map(|iv| &iv.value)
            .collect()
    }
}
```

Wait, `Interval` doesn't need to be public. I'll keep it private.
The struct definition in the prompt is `pub struct IntervalMap<T> { /* ... */ }`. I'll match that.

Let's double check the constraints.
- `start >= end` -> no-op. Handled.
- `get` returns most recently inserted. Handled by `rev()`.
- `get_all` returns all, ordered most-recently-inserted first. Handled by `rev()`.
- Generic over `T` with no trait bounds. Handled.
- Values owned, returns borrows. Handled.

One minor point: `get_all` returns `Vec<&T>`. The lifetime elision will work correctly: `fn get_all(&self, point: i64) -> Vec<&T>` implies `Vec<&'a T>` where `'a` is the lifetime of `&self`. This is standard.

Is there any edge case? `point` can be negative. `i64` handles that.
`start` and `end` can be negative. `i64` handles that.
`start < end` check handles empty intervals.

What about memory/performance? If this is for a competitive programming or interview setting, O(N) might be too slow if N is large. But without constraints, it's fine. If they wanted a balanced tree, they'd usually specify or give large test cases. I'll stick with Vec.

Actually, I can make it slightly more robust by using a `Vec` but it's fine.

Wait, is there any chance they expect `IntervalMap` to be defined exactly as:
```rust
pub struct IntervalMap<T> {
    intervals: Vec<(i64, i64, T)>,
}
```
Using a tuple is simpler. I'll use a struct for clarity, or tuple. Doesn't matter.

Let's stick to the struct for readability.

One thing: `get_all` returns 
…[2712 chars elided]…
on `T`.
Everything matches.

I will write the code now. 
One minor point: `Vec<&T>` might cause lifetime issues if not careful, but with `&self` it's fine. The compiler will infer `Vec<&'a T>` where `'a` is the lifetime of `&self`.

Code:
```rust
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 {
        Self {
            intervals: Vec::new(),
        }
    }

    pub fn insert(&mut self, start: i64, end: i64, value: T) {
        if start < end {
            self.intervals.push(Interval { start, end, value });
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        self.intervals
            .iter()
            .rev()
            .find(|iv| point >= iv.start && point < iv.end)
            .map(|iv| &iv.value)
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        self.intervals
            .iter()
            .rev()
            .filter(|iv| point >= iv.start && point < iv.end)
            .map(|iv| &iv.value)
            .collect()
    }
}
```

This looks complete and correct. I'll output it. 
One thing: the prompt says `pub struct IntervalMap<T> { /* ... */ }`. I'll make sure the struct is public. The inner `Interval` can be private.
All good.
Output matches. 
Proceeds. 
[Done] 
Output Generation. 
(Self-Correction/Refinement during generation prep)
Wait, should I include `#[derive(Debug)]` or anything? Not needed.
The code is minimal and correct.
I will present it inside the requested block.
All set. 
Output matches response. 
Proceeds. 
[Final Check]
- `new()` -> `Self`
- `insert(&mut self, start: i64, end: i64, value: T)`
- `get(&self, point: i64) -> Option<&T>`
- `get_all(&self, point: i64) -> Vec<&T>`
- Half-open `[start, end)`
- `start >= end` no-op
- Newest wins
- `get_all` ordered newest first
- Generic `T` no bounds
- Values owned, returns borrows
All constraints met.
Code is ready. 
Output matches. 
Done. 
[Output Generation] -> *Proceeds*