// 1043: Interval Map — BTreeMap-based Range Storage
// Map non-overlapping intervals [lo, hi) to values
use std::collections::BTreeMap;
/// Interval map: stores non-overlapping [lo, hi) -> value mappings
struct IntervalMap<V> {
// Key = interval start, Value = (end, mapped_value)
map: BTreeMap<i64, (i64, V)>,
}
impl<V: Clone> IntervalMap<V> {
fn new() -> Self {
IntervalMap { map: BTreeMap::new() }
}
/// Insert interval [lo, hi) -> value, removing overlapping intervals
fn insert(&mut self, lo: i64, hi: i64, value: V) {
assert!(lo < hi, "interval must be non-empty");
// Remove all intervals that overlap with [lo, hi)
let overlapping: Vec<i64> = self.map.range(..hi)
.filter(|(_, (end, _))| *end > lo)
.map(|(&start, _)| start)
.collect();
for start in overlapping {
self.map.remove(&start);
}
self.map.insert(lo, (hi, value));
}
/// Query: find value at a point
fn query(&self, point: i64) -> Option<&V> {
// Find the interval whose start <= point
self.map.range(..=point)
.next_back()
.and_then(|(_, (hi, v))| {
if point < *hi { Some(v) } else { None }
})
}
/// List all intervals as (start, end, value) triples
fn intervals(&self) -> Vec<(i64, i64, &V)> {
self.map.iter().map(|(&lo, (hi, v))| (lo, *hi, v)).collect()
}
fn len(&self) -> usize {
self.map.len()
}
}
fn basic_ops() {
let mut im = IntervalMap::new();
im.insert(0, 10, "low");
im.insert(10, 20, "mid");
im.insert(20, 30, "high");
assert_eq!(im.query(5), Some(&"low"));
assert_eq!(im.query(15), Some(&"mid"));
assert_eq!(im.query(25), Some(&"high"));
assert_eq!(im.query(30), None);
assert_eq!(im.query(-1), None);
assert_eq!(im.len(), 3);
}
fn overlap_test() {
let mut im = IntervalMap::new();
im.insert(0, 10, "a");
im.insert(5, 15, "b"); // overlaps with "a"
// "b" replaced "a"
assert_eq!(im.query(7), Some(&"b"));
assert_eq!(im.query(12), Some(&"b"));
}
fn intervals_listing() {
let mut im = IntervalMap::new();
im.insert(0, 5, "x");
im.insert(10, 20, "y");
let intervals = im.intervals();
assert_eq!(intervals.len(), 2);
assert_eq!(intervals[0], (0, 5, &"x"));
assert_eq!(intervals[1], (10, 20, &"y"));
}
fn main() {
basic_ops();
overlap_test();
intervals_listing();
println!("✓ All tests passed");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_basic() { basic_ops(); }
#[test]
fn test_overlap() { overlap_test(); }
#[test]
fn test_listing() { intervals_listing(); }
#[test]
fn test_boundary() {
let mut im = IntervalMap::new();
im.insert(0, 10, "a");
// Point at boundary: [0, 10) means 0 is in, 10 is out
assert_eq!(im.query(0), Some(&"a"));
assert_eq!(im.query(9), Some(&"a"));
assert_eq!(im.query(10), None);
}
#[test]
fn test_adjacent() {
let mut im = IntervalMap::new();
im.insert(0, 5, "a");
im.insert(5, 10, "b");
assert_eq!(im.query(4), Some(&"a"));
assert_eq!(im.query(5), Some(&"b"));
}
}
(* 1043: Interval Map — BTreeMap-based Range Storage *)
(* Map non-overlapping intervals to values *)
module IntMap = Map.Make(Int)
(* Store intervals as (start, (end, value)) in a sorted map *)
type 'a interval_map = (int * 'a) IntMap.t
let empty : 'a interval_map = IntMap.empty
(* Insert interval [lo, hi) -> value (overwrites overlapping ranges) *)
let insert lo hi value (im : 'a interval_map) : 'a interval_map =
(* Remove all intervals that overlap with [lo, hi) *)
let filtered = IntMap.filter (fun start (stop, _) ->
stop <= lo || start >= hi (* keep if completely before or after *)
) im in
IntMap.add lo (hi, value) filtered
(* Query: find value at point *)
let query point (im : 'a interval_map) : 'a option =
(* Find the largest start <= point *)
let (below, at_point, _) = IntMap.split point im in
match at_point with
| Some (hi, v) when point < hi -> Some v
| _ ->
match IntMap.max_binding_opt below with
| Some (_, (hi, v)) when point < hi -> Some v
| _ -> None
(* Approach 1: Basic interval operations *)
let basic_ops () =
let im = empty
|> insert 0 10 "low"
|> insert 10 20 "mid"
|> insert 20 30 "high"
in
assert (query 5 im = Some "low");
assert (query 15 im = Some "mid");
assert (query 25 im = Some "high");
assert (query 30 im = None);
assert (query (-1) im = None)
(* Approach 2: Overlapping insert *)
let overlap_test () =
let im = empty
|> insert 0 10 "a"
|> insert 5 15 "b" (* overlaps with "a" *)
in
(* "b" overwrites the overlapping portion *)
assert (query 7 im = Some "b");
assert (query 12 im = Some "b")
(* Approach 3: List all intervals *)
let to_list (im : 'a interval_map) =
IntMap.fold (fun start (stop, value) acc ->
(start, stop, value) :: acc
) im [] |> List.rev
let list_test () =
let im = empty
|> insert 0 5 "x"
|> insert 10 20 "y"
in
let intervals = to_list im in
assert (List.length intervals = 2);
let (s, e, v) = List.hd intervals in
assert (s = 0 && e = 5 && v = "x")
let () =
basic_ops ();
overlap_test ();
list_test ();
Printf.printf "✓ All tests passed\n"