1043 Intermediate

1043-interval-map — Interval Map

Functional Programming

Tutorial

The Problem

An interval map assigns values to non-overlapping ranges of a key space. Use cases: IP address routing tables (CIDR blocks), calendar scheduling (time ranges), tax brackets (income ranges), and memory segment descriptors in operating systems.

The canonical implementation uses a sorted BTreeMap<start, (end, value)> where each entry represents one interval. Lookup requires finding the largest start key that is ≤ the query point and verifying the end bound, which is O(log n) with BTreeMap::range.

🎯 Learning Outcomes

• Implement an interval map using BTreeMap<i64, (i64, V)>

• Handle interval insertion with overlap removal

• Perform O(log n) point queries

• Understand the design of sorted-key interval structures

• Connect this to std::collections::BTreeMap::range API

Code Example

#![allow(clippy::all)]
// 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"));
}

#[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"

Key Differences

Range queries: Rust uses map.range(..=point).next_back() to find the predecessor; OCaml uses Map.find_last_opt (fun k -> k <= point).

Overlap removal: Both use range iteration to find overlapping intervals, but Rust's BTreeMap::range is O(k + log n) where k is the number of overlapping intervals.

Mutability: Rust's BTreeMap is mutable (intervals removed in place); OCaml returns new map versions.

Production libraries: The nodit crate provides a production-grade interval map with richer APIs; OCaml's Interval_map library provides similar functionality.

OCaml Approach

OCaml's Map.Make enables the same approach:

module IntMap = Map.Make(Int)

type 'v interval_map = (int * 'v) IntMap.t  (* key=lo, value=(hi, v) *)

let query m point =
  match IntMap.find_last_opt (fun lo -> lo <= point) m with
  | None -> None
  | Some (lo, (hi, v)) -> if point < hi then Some v else None

Map.find_last_opt finds the largest key satisfying a predicate — the equivalent of Rust's range(..=point).next_back().

Full Source

#![allow(clippy::all)]
// 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"));
}

#[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"

✓ Tests Rust test suite

#[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"));
    }
}

Deep Comparison

Interval Map — Comparison

Core Insight

An interval map associates non-overlapping ranges with values. The key insight is using a sorted map keyed by interval start — point queries find the floor entry and check if the point falls within its range. Both languages use their sorted map (Map/BTreeMap).

OCaml Approach

• IntMap.t with (end, value) as stored value

• split for point queries: find largest start ≤ point

• filter to remove overlapping intervals on insert

• Immutable — returns new map on each operation

Rust Approach

• BTreeMap<i64, (i64, V)> — start → (end, value)

• range(..=point).next_back() for floor entry lookup

• range(..hi).filter() to find overlapping intervals

• Mutable with clean ownership semantics

• assert!(lo < hi) for invariant checking

Comparison Table

Feature	OCaml	Rust
Backing map	`IntMap.t`	`BTreeMap`
Point query	`split` + `max_binding_opt`	`range(..=p).next_back()`
Overlap removal	`filter`	`range` + collect + remove
Insert	Immutable rebuild	Mutable in-place
Interval repr	`(start, (end, value))`	`(start, (end, value))`
Complexity	O(log n) query	O(log n) query

Exercises

Add a gaps(lo: i64, hi: i64) -> Vec<(i64, i64)> method that returns all uncovered sub-intervals within the query range.

Implement an IP routing table using IntervalMap<String> with integer representations of IPv4 addresses and CIDR blocks.

Write a merge(other: IntervalMap<V>) method that inserts all intervals from another map, resolving overlaps.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust