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)>,
}

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));
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        self.intervals.iter().rev().find_map(|(start, end, value)| {
            if *start <= point && point < *end {
                Some(value)
            } else {
                None
            }
        })
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        self.intervals.iter().rev().filter_map(|(start, end, value)| {
            if *start <= point && point < *end {
                Some(value)
            } else {
                None
            }
        }).collect()
    }
}
```

The problem asks us to implement a generic `IntervalMap<T>` that maps integer intervals `[start, end)` to values of type `T`.

Key requirements:
- Intervals are half-open: `[start, end)`.
- `insert(start, end, value)`:
  - No-op if `start >= end`.
  - Intervals can overlap.
- `get(point)`:
  - Returns the value of the most recently inserted interval covering `point`.
  - Returns `None` if no interval covers `point`.
- `get_all(point)`:
  - Returns all values of intervals covering `point`, ordered most-recently-inserted first.
  - Returns empty `Vec` if none cover it.
- Generic over `T` with no trait bounds.
- Values are owned by the map; `get`/`get_all` return references.

Let's think about the data structure.

We need to store intervals and their insertion order. Since we need to find the most recently inserted interval covering a point, we could store intervals in a list/vector and iterate backwards. However, this would be O(n) for `get` and `get_all`, which might be acceptable depending on constraints, but usually interval maps use more efficient structures.

But wait, the problem doesn't specify performance requirements. Let's check if there are any hints. The problem says "Implement the library file src/lib.rs exposing a generic structure". It doesn't mention performance constraints. However, for a proper interval map, we should consider efficiency.

Let's think about possible approaches:

1. **Simple vector approach**: Store `(start, end, value, insertion_order)` in a `Vec`. For `get`, iterate backwards and return the first match. For `get_all`, iterate backwards and collect all matches.
   - Pros: Simple, correct.
   - Cons: O(n) for queries.

2. **Tree-based approach**: Use a balanced BST or interval tree.
   - Pros: O(log n) for queries.
   - Cons: More complex to implement.

3. **Segment tree**: Could work but might be overkill and requires coordinate compression or dynamic nodes.

Given that this is a coding challenge and no performance constraints are specified, the simple vector approach might be acceptable. However, let's think about whether there's a more efficient approach that's still relatively simple.

Actually, let's reconsider. The problem says "Intervals may overlap" and "Newest insert wins on overlap". This suggests we need to track insertion order.

Let's go with the simple vector approach first, as it's correct and straightforward. If performance is an issue, we can optimize later.

Wait, but there's a subtlety: `get_all` needs to return values in most-recently-inserted first order. With a vector, we can just iterate backwards.

Let's implement the simple approach:

```rust
pub struct IntervalMap<T> {
    intervals: Vec<(i64, i64, 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 {
            self.intervals.push((start, end, value));
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        self.intervals.iter().rev().find_map(|(start, end, value)| {
            if *start <= point && point < *end {
                Some(value)
            } else {
                None
            }
        })
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        self.intervals.iter().rev().filter_map(|(start, end, value)| {
            if *start <= point && point < *end {
                Some(value)
            } else {
                None
            }
        }).collect()
    }
}
```

This is simple and correct. Let's verify:
- `insert`: Pushes to the end if `start < end`. Later inserts are at higher indices.
- `get`: Iterates backwards (from most recent to oldest), returns the first match.
- `get_all`: Iterates backwards, collects all matches in order.

This should work. Let's double-check the requirements:
- Half-open intervals: `[start, end)` - yes, `start <= point && point < end`.
- `start >= end` is no-op - yes, checked.
- Intervals may overlap - yes, we store all of them.
- `get` returns most recently inserted - yes, we iterate backwards.
- `get_all` returns all in most-recently-inserted first order - yes, we iterate backwards and collect.
- Generic over `T` with no trait bounds - yes.
- Values are owned, `get`/`get_all` return references - yes.

This looks correct. Let's write the final solution.

Actually, wait. Let me reconsider if there's any edge case or issue.

What about very large intervals or many intervals? The simple approach is O(n) for queries, which might be slow for large inputs. But without performance constraints, this should be fine.

Let me think if there's a more efficient approach that's still simple.

One idea: Use a `BTreeMap` or similar to store intervals in a way that allows efficient querying. But this is more complex.

Another idea: Use a segment tree or interval tree. But this is also more complex.

Given the problem statement doesn't mention performance, I'll stick with the simple vector approach. It's correct and easy to understand.

Let me write the final solution:

```rust
pub struct IntervalMap<T> {
    intervals: Vec<(i64, i64, 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 {
            self.intervals.push((start, end, value));
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        self.intervals.iter().rev().find_map(|(start, end, value)| {
            if *start <= point && point < *end {
                Some(value)
            } else {
                None
            }
        })
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        self.intervals.iter().rev().filter_map(|(start, end, value)| {
            if *start <= point && point < *end {
                Some(value)
            } else {
                None
            }
        }).collect()
    }
}
```

This looks good. Let me verify once more:
- `new()`: Creates an empty map.
- `insert(start, end, value)`: Adds interval if
…[308 chars elided]…
erted first". With `iter().rev()`, we iterate from the end of the vector (most recent) to the beginning (oldest), so the order should be correct.

Let me trace through an example:
- Insert [0, 10) with value A.
- Insert [5, 15) with value B.
- Insert [2, 8) with value C.

Vector: [(0, 10, A), (5, 15, B), (2, 8, C)]

`get_all(6)`:
- Iterate backwards: C (covers 6), B (covers 6), A (covers 6).
- Result: [C, B, A].

This is correct: C was inserted last, then B, then A.

`get(6)`:
- Iterate backwards: C (covers 6), return C.

This is correct: C is the most recent.

Looks good. I'll finalize this solution.

Wait, I should also consider if there are any memory or performance concerns with storing all intervals. But again, without constraints, this should be fine.

One more thing: The problem says "Tests live in tests/ and use challenge::IntervalMap." This suggests the crate name is `challenge`, and our `IntervalMap` should be public. Our implementation has `pub struct IntervalMap<T>`, so that's correct.

Let me write the final solution:

```rust
pub struct IntervalMap<T> {
    intervals: Vec<(i64, i64, 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 {
            self.intervals.push((start, end, value));
        }
    }

    pub fn get(&self, point: i64) -> Option<&T> {
        self.intervals.iter().rev().find_map(|(start, end, value)| {
            if *start <= point && point < *end {
                Some(value)
            } else {
                None
            }
        })
    }

    pub fn get_all(&self, point: i64) -> Vec<&T> {
        self.intervals.iter().rev().filter_map(|(start, end, value)| {
            if *start <= point && point < *end {
                Some(value)
            } else {
                None
            }
        }).collect()
    }
}
```

This is the final solution. It's simple, correct, and meets all the requirements.