BTreeMap range queries

Given timestamped events, return the names that fall within a time window.

pub fn events_between(events: Vec<(i64, String)>, from: i64, to: i64) -> Vec<String>

Build a BTreeMap<i64, Vec<String>> keyed by timestamp, then query the half-open interval [from, to): include from and exclude to. Return names in ascending timestamp order. For events at the same timestamp, preserve their input order. Keep repeated names, and preserve each string exactly, including empty names.

Return an empty vector if from >= to, the input is empty, or no events fall within the window. These cases must not panic. Timestamps and bounds can be any i64; compare them directly rather than subtracting or adding one to a boundary.

For example, events [(2, "x"), (2, "y"), (1, "w"), (5, "z")] queried with [1, 5) produce ["w", "x", "y"].

Group events before querying

A map stores one value per key. Using Vec<String> as that value lets several events share a timestamp. Append each name to its timestamp's vector as you read the input; that preserves order within the group.

BTreeMap iterates in key order and supports querying a contiguous range of keys. These properties fit the two ordering requirements of this task. A HashMap does not provide ordered iteration or a key-range iterator; using one would require additional work to select and order the results.

Expressing the bounds

This complete example shows several queries over the same map:

use std::collections::BTreeMap;
use std::ops::Bound::{Excluded, Unbounded};

fn main() {
    let map = BTreeMap::from([(1, "a"), (3, "b"), (5, "c")]);

    let half_open: Vec<_> = map.range(1..5).map(|(&k, _)| k).collect();
    let inclusive: Vec<_> = map.range(1..=5).map(|(&k, _)| k).collect();
    let after_three: Vec<_> = map
        .range((Excluded(3), Unbounded))
        .map(|(&k, _)| k)
        .collect();

    assert_eq!(half_open, vec![1, 3]);
    assert_eq!(inclusive, vec![1, 3, 5]);
    assert_eq!(after_three, vec![5]);
}

Other useful forms are map.range(from..) for keys at least from, map.range(..to) for keys below to, and map.range(..) for all entries.

Check from >= to before querying. Reversed bounds violate range's documented preconditions and can panic. Equal half-open bounds describe an empty window. With explicit Bound values, equal endpoints that are both excluded are also documented to panic; that is a different case from a..a.

Why the starter does not compile

range borrows the map and yields references to each key and value. Here, each value is a Vec<String>. Flattening those borrowed vectors yields &String, but the function must return Vec<String>.

The resulting E0277 says that a vector of owned strings cannot be collected from an iterator of string references. For this borrowed query, add .cloned() to the iterator over names. It creates owned copies for the result while leaving the map's strings in place.

Cloning copies the selected text and normally allocates for nonempty strings. It is a consequence of this borrowing approach, not a requirement of returning Vec<String> in general. Because this function owns its map, a different approach could consume it and move strings into the result. For this exercise, practice the borrowed range API.

What the query costs

Let n be the number of input events and d the number of distinct timestamps. Building the index takes O(n log(d + 1)) time. Once built, finding a range and traversing its k timestamp groups takes O(log(d + 1) + k) time. Collecting the result also visits every selected name and copies its text, so the number and lengths of the names matter.

A full-map filter examines all d groups even for a narrow window. A range query can skip groups outside its bounds. The indexing cost still belongs to this function call, however: this exercise rebuilds the map for each query. Reusing an index is useful when querying the same events repeatedly.

Why keys need an order

Operations such as inserting and querying keys require Ord, which defines a total order. i64 provides it. f64 does not: ordinary floating-point comparisons leave NaN unordered. You can declare an empty BTreeMap<f64, String>, but inserting a floating-point key fails the Ord requirement.

For floating-point keys, choose a wrapper with a consistent total-order policy, or a suitable fixed-point integer representation. Using raw float bits as unsigned keys does not preserve numeric order, especially for negative values.

Submissions must compile, pass the tests and pass clippy -D warnings.