vulture 0.17.0

//! [`Timetable`] implementation backed by a GTFS feed.
//!
//! Wraps a parsed [`Gtfs`] object and pre-computes lookup indices for
//! efficient route, stop, and trip queries.
//!
//! ## Loading sources
//!
//! The `Gtfs` value [`GtfsTimetable::new`] consumes can come from a local
//! path ([`Gtfs::new`]) or from any of the alternatives `gtfs-structures`
//! already exposes: `Gtfs::from_url` (sync HTTP fetch), `Gtfs::from_url_async`
//! (async), and `Gtfs::from_reader` for any `Read + Seek`.
//!
//! ## Synthetic routes
//!
//! A "RAPTOR route" is an equivalence class of trips with identical stop
//! sequences (the paper, §3.1). A GTFS `route_id` is *not* a RAPTOR route
//! – it routinely groups trips with different stop patterns
//! (short-turns, branching, deadheads). At construction time, this
//! adapter splits each `route_id` into one or more synthetic routes,
//! identified by [`RouteIdx`]. Trips on a synthetic route are
//! additionally split into non-overtaking sub-groups so that the
//! algorithm's binary-search-by-departure assumption holds.
//!
//! Use [`GtfsTimetable::route_id`] to recover the original GTFS
//! `route_id` for display, and [`GtfsTimetable::routes_for_gtfs_id`] to
//! enumerate every synthetic derived from a given GTFS route.

use std::collections::{HashMap, HashSet};

use chrono::{Datelike, NaiveDate, Weekday};
use gtfs_structures::{Availability, Exception, Gtfs, PickupDropOffType};
use jiff::civil::Date;
use rstar::{AABB, PointDistance, RTree, RTreeObject};
use smallvec::SmallVec;

use crate::{Duration, RouteIdx, SecondOfDay, StopIdx, Timetable, TripIdx};

/// Mean Earth radius in metres, used to project stop coordinates to a
/// local Cartesian frame for the `with_walking_footpaths` spatial query.
const EARTH_RADIUS_M: f64 = 6_371_000.0;

/// A stop projected to local Cartesian coordinates (metres) via an
/// equirectangular projection anchored at a reference latitude. Used as
/// the leaf type of the R-tree built by `with_walking_footpaths`.
#[derive(Clone, Copy, Debug)]
struct ProjectedStop {
    pos: [f64; 2],
    idx: StopIdx,
}

impl RTreeObject for ProjectedStop {
    type Envelope = AABB<[f64; 2]>;
    fn envelope(&self) -> Self::Envelope {
        AABB::from_point(self.pos)
    }
}

impl PointDistance for ProjectedStop {
    fn distance_2(&self, point: &[f64; 2]) -> f64 {
        let dx = self.pos[0] - point[0];
        let dy = self.pos[1] - point[1];
        dx * dx + dy * dy
    }
}

/// Returns true iff `service_id` is active on `date` per the GTFS feed's
/// `calendar.txt` and `calendar_dates.txt` rules.
///
/// Resolution order: an entry in `calendar_dates.txt` for the exact
/// date trumps `calendar.txt`. If `calendar_dates.txt` has no entry,
/// `calendar.txt` decides via the day-of-week flags constrained by
/// the service's `start_date`/`end_date` window. A service that
/// appears in neither file is considered inactive.
fn is_service_active(gtfs: &Gtfs, service_id: &str, date: NaiveDate) -> bool {
    if let Some(cdates) = gtfs.calendar_dates.get(service_id)
        && let Some(cd) = cdates.iter().find(|cd| cd.date == date)
    {
        return matches!(cd.exception_type, Exception::Added);
    }
    if let Some(cal) = gtfs.calendar.get(service_id) {
        if date < cal.start_date || date > cal.end_date {
            return false;
        }
        return match date.weekday() {
            Weekday::Mon => cal.monday,
            Weekday::Tue => cal.tuesday,
            Weekday::Wed => cal.wednesday,
            Weekday::Thu => cal.thursday,
            Weekday::Fri => cal.friday,
            Weekday::Sat => cal.saturday,
            Weekday::Sun => cal.sunday,
        };
    }
    false
}

/// Convert a `jiff::civil::Date` to `chrono::NaiveDate` at the GTFS
/// boundary. `gtfs-structures` exposes calendar dates as `chrono`; the
/// rest of this crate uses `jiff` so users only see one date type.
fn jiff_to_chrono(d: Date) -> NaiveDate {
    NaiveDate::from_ymd_opt(d.year() as i32, d.month() as u32, d.day() as u32)
        .expect("jiff::civil::Date guarantees a valid (year, month, day) triple")
}

const TYPICAL_ROUTES_PER_STOP: usize = 8;
const TYPICAL_TRANSFERS_PER_STOP: usize = 4;
const DEFAULT_TRANSFER_TIME: Duration = Duration(300);

/// Errors that can occur when constructing a [`GtfsTimetable`].
///
/// Every variant carries the offending trip's GTFS `route_id` (and the
/// route's `agency_id` when one is set) so a feed-validation report can
/// be filed against the right operator without further lookup.
#[derive(thiserror::Error, Debug)]
pub enum GtfsError {
    /// A stop referenced by a trip was not found in the feed's
    /// `stops.txt`.
    #[error(
        "stop {stop} (referenced by trip {trip} on route {route}, agency {}) not found",
        agency.as_deref().unwrap_or("?"),
    )]
    MissingStop {
        /// The unresolved stop ID.
        stop: String,
        /// The trip that referenced the stop.
        trip: String,
        /// The trip's GTFS `route_id`.
        route: String,
        /// The route's `agency_id`, when set.
        agency: Option<String>,
    },
    /// A trip has no stop times defined.
    #[error(
        "trip {trip} on route {route} (agency {}) has no stop_times",
        agency.as_deref().unwrap_or("?"),
    )]
    MissingStopTimes {
        /// The trip with no stop_times.
        trip: String,
        /// The trip's GTFS `route_id`.
        route: String,
        /// The route's `agency_id`, when set.
        agency: Option<String>,
    },
    /// A trip has a stop_time without a departure time, which the algorithm
    /// needs for binary-search ordering.
    #[error(
        "stop_time has no departure_time: trip {trip} on route {route} (agency {}), stop {stop}",
        agency.as_deref().unwrap_or("?"),
    )]
    MissingDepartureTime {
        /// The trip the stop_time belongs to.
        trip: String,
        /// The trip's GTFS `route_id`.
        route: String,
        /// The route's `agency_id`, when set.
        agency: Option<String>,
        /// The stop the stop_time refers to.
        stop: String,
    },
    /// `with_overnight_days(n)` would push the loaded date range past
    /// jiff's representable range. Only triggered by absurd `base + n`
    /// combinations near the year-9999 ceiling.
    #[error(
        "base_date + {days_added} days falls outside jiff's representable range (base = {base})"
    )]
    DateOutOfRange {
        /// The base service date the multi-day load was anchored at.
        base: Date,
        /// The day offset that overflowed.
        days_added: u32,
    },
}

type GtfsResult<T> = std::result::Result<T, GtfsError>;

/// A [`Timetable`] implementation that wraps a parsed GTFS feed.
///
/// Constructed via [`GtfsTimetable::new`], which validates the feed,
/// interns stops/routes/trips to dense `u32` indices, splits each GTFS
/// `route_id` into one or more [`RouteIdx`]s by stop pattern and
/// overtaking, and builds the lookup indices the algorithm requires.
///
/// ```no_run
/// use gtfs_structures::Gtfs;
/// use jiff::civil::date;
/// use vulture::{SecondOfDay, Timetable};
/// use vulture::gtfs::GtfsTimetable;
///
/// # fn ex() -> anyhow::Result<()> {
/// let gtfs = Gtfs::new("path/to/gtfs.zip")?;
/// let tt = GtfsTimetable::new(&gtfs, date(2026, 5, 4))?;
///
/// let start = tt.stop_idx("origin_id").expect("unknown stop");
/// let target = tt.stop_idx("target_id").expect("unknown stop");
///
/// let journeys = tt
///     .query()
///     .from(start)
///     .to(target)
///     .max_transfers(10)
///     .depart_at(SecondOfDay::hms(9, 0, 0))
///     .run();
/// # Ok(())
/// # }
/// ```
///
/// Common follow-on calls:
///
/// - [`GtfsTimetable::station_stops`] – expand a parent station to its
///   child platforms for multi-source / multi-target queries.
/// - [`GtfsTimetable::with_walking_footpaths`] – augment a sparse or
///   empty `transfers.txt` with coordinate-derived walking edges.
/// - [`GtfsTimetable::assert_footpaths_closed`] – opt into the
///   single-pass footpath relaxation when your `transfers.txt` is the
///   entire intended walking relation.
/// - [`GtfsTimetable::stop_id`] / [`GtfsTimetable::route_id`] – translate
///   `StopIdx` / `RouteIdx` values back to the original GTFS IDs.
/// - [`GtfsTimetable::routes_for_gtfs_id`] – enumerate the synthetic
///   [`RouteIdx`]s produced from a single GTFS `route_id` (one per
///   distinct, non-overtaking stop-pattern equivalence class).
pub struct GtfsTimetable<'gtfs> {
    // Forward tables: idx -> &'gtfs str (original GTFS IDs).
    stop_ids: Vec<&'gtfs str>,
    route_ids: Vec<&'gtfs str>,
    trip_ids: Vec<&'gtfs str>,

    // Reverse tables.
    stop_by_id: HashMap<&'gtfs str, StopIdx>,
    route_by_id: HashMap<&'gtfs str, RouteIdx>,
    routes_by_gtfs_id: HashMap<&'gtfs str, SmallVec<[RouteIdx; 2]>>,
    trip_by_id: HashMap<&'gtfs str, TripIdx>,

    // For each stop, the routes serving it paired with the *earliest*
    // position of the stop on that route. Each route appears at most once
    // per stop (loop routes that revisit the stop only get their earliest
    // position recorded).
    routes_for_stop: Vec<SmallVec<[(RouteIdx, u32); TYPICAL_ROUTES_PER_STOP]>>,
    stops_for_route: Vec<Vec<StopIdx>>,
    trips_for_route: Vec<Vec<TripIdx>>,
    /// arrival_times[route.idx()][stop_pos][trip_pos] = SecondOfDay
    arrival_times: Vec<Vec<Vec<SecondOfDay>>>,
    /// departure_times[route.idx()][stop_pos][trip_pos] = SecondOfDay
    departure_times: Vec<Vec<Vec<SecondOfDay>>>,
    /// route_for_trip[trip.idx()] = (route_idx, position-within-route)
    route_for_trip: Vec<(RouteIdx, usize)>,

    footpaths_for_stops: Vec<SmallVec<[StopIdx; TYPICAL_TRANSFERS_PER_STOP]>>,
    transfer_times: HashMap<(StopIdx, StopIdx), Duration>,

    /// `(trip, pos)` pairs where boarding is forbidden by GTFS
    /// `pickup_type = 1` (NotAvailable). Empty for typical metro feeds
    /// where every stop is regularly boardable.
    no_pickup: HashSet<(TripIdx, u32)>,
    /// `(trip, pos)` pairs where alighting is forbidden by GTFS
    /// `drop_off_type = 1` (NotAvailable). Same shape as `no_pickup`.
    no_drop_off: HashSet<(TripIdx, u32)>,

    /// Trips with `wheelchair_accessible = NotAvailable`. Sparse —
    /// most feeds either populate the flag rarely or not at all.
    inaccessible_trips: HashSet<TripIdx>,
    /// Stops with `wheelchair_boarding = NotAvailable`. Same shape.
    inaccessible_stops: HashSet<StopIdx>,

    /// User-asserted closure flag. Returned from
    /// [`Timetable::footpaths_are_transitively_closed`] so the algorithm
    /// can pick the single-pass relaxation. Set via
    /// [`GtfsTimetable::assert_footpaths_closed`]; reset to `false` by
    /// [`GtfsTimetable::with_walking_footpaths`] (which adds direct,
    /// non-closed edges).
    transfers_closed: bool,

    /// The base service date passed to [`GtfsTimetable::new`]. Retained
    /// so [`GtfsTimetable::with_overnight_days`] can rebuild the
    /// timetable starting from the same anchor.
    base_date: Date,
    /// Number of additional service days loaded after `base_date`. The
    /// timetable covers `base_date` through `base_date + n_overnight_days`
    /// inclusive. Default `0` (single-day operation).
    n_overnight_days: u8,

    /// For each parent-station GTFS id, the child platform `StopIdx`es
    /// (each paired with a default zero walk time, ready to pass to
    /// `Query::from` / `Query::to` as a multi-source/multi-target query).
    station_children: HashMap<&'gtfs str, Vec<(StopIdx, Duration)>>,
}

impl<'gtfs> GtfsTimetable<'gtfs> {
    /// Creates a new timetable from a parsed GTFS feed for a specific
    /// service date.
    ///
    /// Trips whose `service_id` is not active on `service_date` (per
    /// `calendar.txt` and `calendar_dates.txt`) are filtered out at
    /// construction. The returned timetable contains only trips that
    /// run on `service_date`.
    ///
    /// Validates that every trip references existing stops and has
    /// stop_times with departure times, then interns identifiers to dense
    /// `u32` indices and splits each GTFS `route_id` into synthetic
    /// [`RouteIdx`]s as described in the module docs.
    ///
    /// # Footpath assumptions
    ///
    /// The adapter passes `transfers.txt` entries through to the
    /// [`Timetable::get_footpaths_from`] return as-is, without computing
    /// the transitive closure. The [`Timetable`] trait requires the
    /// footpath relation to be transitively closed (see the trait-level
    /// docs).
    pub fn new(gtfs: &'gtfs Gtfs, service_date: Date) -> GtfsResult<Self> {
        Self::build(gtfs, service_date, 0)
    }

    /// Loads `n` additional service days *after* the original
    /// [`GtfsTimetable::new`] base date, so the algorithm can find
    /// journeys that depart late on day 0 and arrive on day 1
    /// (or later). Trips active on each subsequent day get their
    /// stop_times shifted by `day_offset × 86400` and inserted as
    /// additional trips on the same RAPTOR route as their day-0
    /// counterparts; the algorithm sees a single time axis monotone
    /// across `0..=n × 86400` seconds.
    ///
    /// `n = 0` is a no-op. `n = 1` is the typical "last train home"
    /// configuration. Larger values are unusual; memory and load time
    /// scale linearly.
    ///
    /// **Order of builder calls.** This method does a full rebuild
    /// from `gtfs`. Call it *before*
    /// [`GtfsTimetable::with_walking_footpaths`] and
    /// [`GtfsTimetable::assert_footpaths_closed`], whose effects it
    /// would otherwise discard.
    ///
    /// **Output semantics.** Returned arrival times can exceed
    /// 86 400 seconds. [`SecondOfDay`]'s `Display` impl formats them
    /// as `HH:MM:SS` with hours past 24 (e.g. `25:30:00`); divide by
    /// 86 400 to recover the day offset.
    /// [`Journey::with_timing`](crate::Journey::with_timing)'s
    /// [`TimedLeg`](crate::TimedLeg) entries carry the same shifted
    /// times.
    pub fn with_overnight_days(self, gtfs: &'gtfs Gtfs, n: u8) -> GtfsResult<Self> {
        if n == self.n_overnight_days {
            return Ok(self);
        }
        Self::build(gtfs, self.base_date, n)
    }

    fn build(gtfs: &'gtfs Gtfs, base_date: Date, n_overnight_days: u8) -> GtfsResult<Self> {
        // Build a small lookup of day_offset -> NaiveDate so the
        // service-day check is one cheap call per (trip, day) pair.
        let mut day_dates: Vec<NaiveDate> = Vec::with_capacity(usize::from(n_overnight_days) + 1);
        for d in 0..=n_overnight_days {
            let day = base_date
                .checked_add(jiff::Span::new().days(i64::from(d)))
                .map_err(|_| GtfsError::DateOutOfRange {
                    base: base_date,
                    days_added: u32::from(d),
                })?;
            day_dates.push(jiff_to_chrono(day));
        }

        // 1. Intern stops in iteration order.
        let mut stop_ids: Vec<&'gtfs str> = Vec::with_capacity(gtfs.stops.len());
        let mut stop_by_id: HashMap<&'gtfs str, StopIdx> = HashMap::with_capacity(gtfs.stops.len());
        let mut inaccessible_stops: HashSet<StopIdx> = HashSet::new();
        for (stop_id, stop) in &gtfs.stops {
            let idx = StopIdx::new(stop_ids.len() as u32);
            stop_ids.push(stop_id.as_str());
            stop_by_id.insert(stop_id.as_str(), idx);
            if matches!(stop.wheelchair_boarding, Availability::NotAvailable) {
                inaccessible_stops.insert(idx);
            }
        }

        // 2. For each service day in the loaded range, validate trips
        //    active on that day and group by (route_id, stop_sequence).
        //    A trip active on multiple days gets multiple entries in
        //    its group, distinguished by `day_offset`. Phase 3 shifts
        //    each entry's times by `day_offset × 86400` so day-d trips
        //    sit strictly after all day-(d-1) trips on the same route.
        type GroupKey<'g> = (&'g str, Vec<StopIdx>);
        type GroupEntries<'g> = Vec<(&'g str, u8)>;
        let mut groups: std::collections::BTreeMap<GroupKey<'gtfs>, GroupEntries<'gtfs>> =
            std::collections::BTreeMap::new();
        for (day_offset, &day_chrono) in day_dates.iter().enumerate() {
            let day_offset = day_offset as u8;
            for (trip_id, trip) in &gtfs.trips {
                if !is_service_active(gtfs, &trip.service_id, day_chrono) {
                    continue;
                }
                // Lift route + agency once per trip so the per-stop
                // error paths don't re-look-up under every stop_time.
                let route_id = trip.route_id.clone();
                let agency_id = gtfs
                    .routes
                    .get(&trip.route_id)
                    .and_then(|r| r.agency_id.clone());
                if trip.stop_times.is_empty() {
                    return Err(GtfsError::MissingStopTimes {
                        trip: trip_id.clone(),
                        route: route_id,
                        agency: agency_id,
                    });
                }
                let mut stop_seq: Vec<StopIdx> = Vec::with_capacity(trip.stop_times.len());
                for st in &trip.stop_times {
                    let raw_id = st.stop.id.as_str();
                    let stop_idx =
                        *stop_by_id
                            .get(raw_id)
                            .ok_or_else(|| GtfsError::MissingStop {
                                stop: raw_id.to_owned(),
                                trip: trip_id.clone(),
                                route: route_id.clone(),
                                agency: agency_id.clone(),
                            })?;
                    if st.departure_time.is_none() {
                        return Err(GtfsError::MissingDepartureTime {
                            trip: trip_id.clone(),
                            route: route_id.clone(),
                            agency: agency_id.clone(),
                            stop: raw_id.to_owned(),
                        });
                    }
                    stop_seq.push(stop_idx);
                }
                groups
                    .entry((trip.route_id.as_str(), stop_seq))
                    .or_default()
                    .push((trip_id.as_str(), day_offset));
            }
        }

        // 3. For each (route_id, stop_seq) group, sort trips by first-stop
        //    departure and split into non-overtaking sub-groups. Each
        //    sub-group becomes a synthetic RouteIdx; trips become TripIdxs
        //    in synthetic-route order.
        let mut route_ids: Vec<&'gtfs str> = Vec::new();
        let mut stops_for_route: Vec<Vec<StopIdx>> = Vec::new();
        let mut trips_for_route: Vec<Vec<TripIdx>> = Vec::new();
        let mut arrival_times: Vec<Vec<Vec<SecondOfDay>>> = Vec::new();
        let mut departure_times: Vec<Vec<Vec<SecondOfDay>>> = Vec::new();
        let mut route_for_trip: Vec<(RouteIdx, usize)> = Vec::with_capacity(gtfs.trips.len());
        let mut no_pickup: HashSet<(TripIdx, u32)> = HashSet::new();
        let mut no_drop_off: HashSet<(TripIdx, u32)> = HashSet::new();
        let mut inaccessible_trips: HashSet<TripIdx> = HashSet::new();
        let mut trip_ids: Vec<&'gtfs str> = Vec::new();
        let mut trip_by_id: HashMap<&'gtfs str, TripIdx> = HashMap::new();
        let mut route_by_id: HashMap<&'gtfs str, RouteIdx> = HashMap::new();
        let mut routes_by_gtfs_id: HashMap<&'gtfs str, SmallVec<[RouteIdx; 2]>> = HashMap::new();
        let mut routes_for_stop: Vec<SmallVec<[(RouteIdx, u32); TYPICAL_ROUTES_PER_STOP]>> =
            vec![SmallVec::new(); stop_ids.len()];

        for ((gtfs_route_id, stop_seq), trips) in groups {
            // Resolve schedules and tag each entry with its day_offset.
            // Sort first by shifted first-stop departure (= day_offset *
            // 86400 + raw departure) so day-d trips appear strictly after
            // day-(d-1) trips on the same route.
            let mut trips_with_schedules: Vec<(&'gtfs str, u8, &'gtfs [gtfs_structures::StopTime])> =
                trips
                    .into_iter()
                    .map(|(trip_id, day_offset)| {
                        let trip = gtfs.get_trip(trip_id).expect(
                            "trip_id is a key in gtfs.trips (groups was built by iterating gtfs.trips earlier in new())",
                        );
                        (trip_id, day_offset, trip.stop_times.as_slice())
                    })
                    .collect();
            trips_with_schedules.sort_by_key(|(_, day_offset, st)| {
                let raw_dep = st[0].departure_time.expect(
                    "first stop_time.departure_time is required by the GtfsError::MissingDepartureTime check earlier in new()",
                );
                shift_dep(raw_dep, *day_offset)
            });

            for sub_group in split_non_overtaking(&trips_with_schedules) {
                let route_idx = RouteIdx::new(route_ids.len() as u32);
                route_ids.push(gtfs_route_id);
                stops_for_route.push(stop_seq.clone());

                let mut sub_trip_idxs: Vec<TripIdx> = Vec::with_capacity(sub_group.len());
                for (trip_id, _day_offset) in &sub_group {
                    let trip_idx = TripIdx::new(trip_ids.len() as u32);
                    trip_ids.push(trip_id);
                    // trip_by_id maps to the FIRST occurrence (lowest
                    // day_offset) so external `tt.trip_idx(id)` lookups
                    // are deterministic when a trip is active on
                    // multiple days. Subsequent days' instances are
                    // reachable via `route_for_trip` / `trips_for_route`.
                    trip_by_id.entry(trip_id).or_insert(trip_idx);
                    sub_trip_idxs.push(trip_idx);
                    debug_assert_eq!(route_for_trip.len(), trip_idx.idx());
                    route_for_trip.push((route_idx, sub_trip_idxs.len() - 1));
                }

                // Per-route arrival/departure tables: shape [stop_pos][trip_pos].
                // Single per-trip pass that also captures pickup/drop-off
                // and wheelchair flags, so we look up each trip once.
                let n_stops_in_route = stop_seq.len();
                let n_trips_in_route = sub_group.len();
                let mut arr_table: Vec<Vec<SecondOfDay>> =
                    vec![vec![SecondOfDay::MAX; n_trips_in_route]; n_stops_in_route];
                let mut dep_table: Vec<Vec<SecondOfDay>> =
                    vec![vec![SecondOfDay::MAX; n_trips_in_route]; n_stops_in_route];
                for (trip_pos, (trip_id, day_offset)) in sub_group.iter().enumerate() {
                    let trip = gtfs.get_trip(trip_id).expect(
                        "trip_id originated from gtfs.trips and survived service-day filtering",
                    );
                    let trip_idx = sub_trip_idxs[trip_pos];
                    if matches!(trip.wheelchair_accessible, Availability::NotAvailable) {
                        inaccessible_trips.insert(trip_idx);
                    }
                    for (stop_pos, st) in trip.stop_times.iter().enumerate() {
                        if let Some(a) = st.arrival_time {
                            arr_table[stop_pos][trip_pos] = shift_dep(a, *day_offset);
                        }
                        let d = st.departure_time.expect(
                            "stop_time.departure_time is required by the GtfsError::MissingDepartureTime check earlier in new()",
                        );
                        dep_table[stop_pos][trip_pos] = shift_dep(d, *day_offset);
                        if matches!(st.pickup_type, PickupDropOffType::NotAvailable) {
                            no_pickup.insert((trip_idx, stop_pos as u32));
                        }
                        if matches!(st.drop_off_type, PickupDropOffType::NotAvailable) {
                            no_drop_off.insert((trip_idx, stop_pos as u32));
                        }
                    }
                }
                arrival_times.push(arr_table);
                departure_times.push(dep_table);
                trips_for_route.push(sub_trip_idxs);

                route_by_id.entry(gtfs_route_id).or_insert(route_idx);
                routes_by_gtfs_id
                    .entry(gtfs_route_id)
                    .or_default()
                    .push(route_idx);

                for (pos, &stop_idx) in stop_seq.iter().enumerate() {
                    let entry = &mut routes_for_stop[stop_idx.idx()];
                    if !entry.iter().any(|(r, _)| *r == route_idx) {
                        entry.push((route_idx, pos as u32));
                    }
                }
            }
        }

        // 4. Footpaths and transfer times.
        let mut footpaths_for_stops: Vec<SmallVec<[StopIdx; TYPICAL_TRANSFERS_PER_STOP]>> =
            vec![SmallVec::new(); stop_ids.len()];
        let mut transfer_times: HashMap<(StopIdx, StopIdx), Duration> = HashMap::new();
        for (stop_id, stop) in &gtfs.stops {
            if stop.transfers.is_empty() {
                continue;
            }
            let from_idx = *stop_by_id
                .get(stop_id.as_str())
                .expect("every stop_id was interned by the stops loop at the start of new()");
            for t in &stop.transfers {
                let Some(&to_idx) = stop_by_id.get(t.to_stop_id.as_str()) else {
                    continue;
                };
                footpaths_for_stops[from_idx.idx()].push(to_idx);
                if let Some(min) = t.min_transfer_time {
                    transfer_times.insert((from_idx, to_idx), Duration(min));
                }
            }
        }

        // 5. Group child stops by their parent_station, so that callers
        //    can later query "all platforms of station X" with one lookup.
        let mut station_children: HashMap<&'gtfs str, Vec<(StopIdx, Duration)>> = HashMap::new();
        for (stop_id, stop) in &gtfs.stops {
            if let Some(parent) = stop.parent_station.as_deref()
                && let Some(&child_idx) = stop_by_id.get(stop_id.as_str())
            {
                // Resolve `parent` against gtfs.stops to find its &'gtfs str
                // key (so the map's key has the right lifetime).
                if let Some((parent_key, _)) = gtfs.stops.get_key_value(parent) {
                    station_children
                        .entry(parent_key.as_str())
                        .or_default()
                        .push((child_idx, Duration::ZERO));
                }
            }
        }

        Ok(Self {
            stop_ids,
            route_ids,
            trip_ids,
            stop_by_id,
            route_by_id,
            routes_by_gtfs_id,
            trip_by_id,
            routes_for_stop,
            stops_for_route,
            trips_for_route,
            arrival_times,
            departure_times,
            route_for_trip,
            footpaths_for_stops,
            transfer_times,
            transfers_closed: false,
            station_children,
            no_pickup,
            no_drop_off,
            inaccessible_trips,
            inaccessible_stops,
            base_date,
            n_overnight_days,
        })
    }

    /// Asserts that the current footpath relation is transitively
    /// closed and instructs the algorithm to use the single-pass
    /// `O(E)` relaxation instead of multi-source Dijkstra. Returns
    /// `self` for chaining.
    ///
    /// A relation is *transitively closed* when every reachable walk
    /// is already a single direct edge – `A → B` and `B → C` implies
    /// `A → C` is in the relation too. See the [`Timetable`] trait's
    /// Footpaths section for the full discussion and the soundness
    /// contract.
    ///
    /// Use when you know the underlying `transfers.txt` (or any
    /// pre-processing you've applied) is closed – typically true for
    /// publisher-curated feeds like Berlin VBB or Paris IDFM.
    ///
    /// **Soundness**: asserting closure on a non-closed relation will
    /// cause the algorithm to miss journeys whose optimal path
    /// requires chaining direct walks within a round. If unsure,
    /// don't call this – the Dijkstra fallback is always sound.
    ///
    /// [`GtfsTimetable::with_walking_footpaths`] resets this flag,
    /// because coordinate-derived edges are not closed by construction.
    pub fn assert_footpaths_closed(mut self) -> Self {
        self.transfers_closed = true;
        self
    }

    /// Returns the child platforms of a parent station as a slice ready
    /// to pass to [`Query::from`] / [`Query::to`] as origins or targets.
    ///
    /// [`Query::from`]: crate::Query::from
    /// [`Query::to`]: crate::Query::to
    ///
    /// Each entry is `(platform_stop_idx, walk_time)` where `walk_time`
    /// defaults to 0 (the user is willing to use any platform without
    /// further wait). Returns an empty slice if `parent_id` is not the
    /// GTFS id of a parent station, or if the station has no children.
    pub fn station_stops(&self, parent_id: &str) -> &[(StopIdx, Duration)] {
        self.station_children
            .get(parent_id)
            .map(|v| v.as_slice())
            .unwrap_or(&[])
    }

    /// Augments the footpath graph with bidirectional walking edges
    /// between every pair of stops within `max_distance_m` straight-line
    /// distance, computed via an equirectangular projection anchored at
    /// the feed's mean latitude (accurate to ~0.5% at city scale).
    ///
    /// Walk time per edge = `distance_m / walking_speed_m_per_s`,
    /// rounded up. Existing transfers from `transfers.txt` are preserved
    /// – coordinate-derived edges are only added where no explicit
    /// transfer between the pair already exists.
    ///
    /// The algorithm chains walks within a round (footpath relaxation
    /// runs to a fixed point), so the graph does not need to be
    /// transitively closed; pairs beyond `max_distance_m` that are
    /// reachable via a chain of shorter walks are still found.
    ///
    /// Typical values: `max_distance_m = 500` (covers same-block
    /// interchanges), `walking_speed_m_per_s = 1.4` (≈ 5 km/h, the
    /// standard pedestrian rate). Returns `self` so the call chains
    /// after [`GtfsTimetable::new`].
    pub fn with_walking_footpaths(
        mut self,
        gtfs: &'gtfs Gtfs,
        max_distance_m: f64,
        walking_speed_m_per_s: f64,
    ) -> Self {
        // Reference latitude: mean across stops with valid coords.
        let mut sum_lat = 0.0;
        let mut n_with_coords = 0usize;
        for stop in gtfs.stops.values() {
            if let (Some(lat), Some(_)) = (stop.latitude, stop.longitude) {
                sum_lat += lat;
                n_with_coords += 1;
            }
        }
        if n_with_coords == 0 {
            return self;
        }
        let mean_lat_rad = (sum_lat / n_with_coords as f64).to_radians();
        let lon_scale = mean_lat_rad.cos() * EARTH_RADIUS_M;
        let lat_scale = EARTH_RADIUS_M;

        // Project every stop into local Cartesian metres.
        let mut projected: Vec<ProjectedStop> = Vec::with_capacity(n_with_coords);
        for (stop_id, stop) in &gtfs.stops {
            if let (Some(lat), Some(lon)) = (stop.latitude, stop.longitude)
                && let Some(&idx) = self.stop_by_id.get(stop_id.as_str())
            {
                let x = lon.to_radians() * lon_scale;
                let y = lat.to_radians() * lat_scale;
                projected.push(ProjectedStop { pos: [x, y], idx });
            }
        }

        let tree = RTree::bulk_load(projected.clone());
        let r2 = max_distance_m * max_distance_m;

        for from in &projected {
            for near in tree.locate_within_distance(from.pos, r2) {
                if near.idx == from.idx {
                    continue;
                }
                // Skip if an explicit transfers.txt entry already covers
                // this directed pair – keep the publisher's value.
                if self.transfer_times.contains_key(&(from.idx, near.idx)) {
                    continue;
                }
                let dx = from.pos[0] - near.pos[0];
                let dy = from.pos[1] - near.pos[1];
                let dist_m = (dx * dx + dy * dy).sqrt();
                let walk_time = Duration((dist_m / walking_speed_m_per_s).ceil() as u32);

                self.footpaths_for_stops[from.idx.idx()].push(near.idx);
                self.transfer_times.insert((from.idx, near.idx), walk_time);
            }
        }

        // Coordinate-derived edges are direct only – closure is not
        // preserved. Drop any prior closure assertion.
        self.transfers_closed = false;
        self
    }

    /// Number of trips active on the timetable's service date (i.e. the
    /// trips that survived calendar filtering at construction).
    pub fn n_trips(&self) -> usize {
        self.trip_ids.len()
    }

    /// Returns the original GTFS `stop_id` for the given index.
    pub fn stop_id(&self, stop: StopIdx) -> &'gtfs str {
        self.stop_ids[stop.idx()]
    }

    /// Returns the original GTFS `route_id` for the given synthetic route.
    /// Several `RouteIdx`s may map to the same GTFS `route_id`.
    pub fn route_id(&self, route: RouteIdx) -> &'gtfs str {
        self.route_ids[route.idx()]
    }

    /// Returns the original GTFS `trip_id` for the given index.
    pub fn trip_id(&self, trip: TripIdx) -> &'gtfs str {
        self.trip_ids[trip.idx()]
    }

    /// Looks up the index of a stop by its GTFS `stop_id`.
    pub fn stop_idx(&self, id: &str) -> Option<StopIdx> {
        self.stop_by_id.get(id).copied()
    }

    /// Looks up the *first* synthetic route derived from a GTFS
    /// `route_id`. Use [`routes_for_gtfs_id`](Self::routes_for_gtfs_id) to
    /// enumerate every synthetic.
    pub fn route_idx(&self, id: &str) -> Option<RouteIdx> {
        self.route_by_id.get(id).copied()
    }

    /// Returns every synthetic route derived from a given GTFS `route_id`.
    pub fn routes_for_gtfs_id(&self, id: &str) -> &[RouteIdx] {
        self.routes_by_gtfs_id
            .get(id)
            .map(|sv| sv.as_slice())
            .unwrap_or(&[])
    }

    /// Looks up the index of a trip by its GTFS `trip_id`.
    pub fn trip_idx(&self, id: &str) -> Option<TripIdx> {
        self.trip_by_id.get(id).copied()
    }
}

/// Greedily split a departure-sorted list of trips on a shared stop
/// sequence into sub-groups within which no trip overtakes any earlier
/// trip in the same sub-group.
///
/// Insertion order: each trip is appended to the first sub-group whose
/// last trip it does not overtake; otherwise a new sub-group is opened.
/// Within a sub-group "doesn't overtake the last trip" extends to the
/// whole sub-group by transitivity (all members are pairwise
/// non-overtaking and times are monotone over the sequence).
fn split_non_overtaking<'gtfs>(
    trips: &[(&'gtfs str, u8, &'gtfs [gtfs_structures::StopTime])],
) -> Vec<Vec<(&'gtfs str, u8)>> {
    let mut sub_groups: Vec<Vec<(&'gtfs str, u8, &'gtfs [gtfs_structures::StopTime])>> = Vec::new();
    'outer: for &entry in trips {
        for sub_group in &mut sub_groups {
            let (_, last_day, last_st) = *sub_group
                .last()
                .expect("sub_groups are seeded with vec![entry] and only ever grown");
            if !overtakes(last_st, last_day, entry.2, entry.1) {
                sub_group.push(entry);
                continue 'outer;
            }
        }
        sub_groups.push(vec![entry]);
    }
    sub_groups
        .into_iter()
        .map(|g| {
            g.into_iter()
                .map(|(id, day_offset, _)| (id, day_offset))
                .collect()
        })
        .collect()
}

/// Shift a raw GTFS departure / arrival time (seconds since the
/// service-day's anchor) by `day_offset × 86 400` so day-`d` trips
/// sit strictly after day-`(d-1)` trips on the same RAPTOR route.
fn shift_dep(raw: u32, day_offset: u8) -> SecondOfDay {
    SecondOfDay(raw.saturating_add(u32::from(day_offset) * 86_400))
}

/// Returns true if `later` overtakes `earlier` at any stop, comparing
/// times *after* the per-trip day-offset shift. Both schedules are
/// assumed to share a stop sequence and to have departure times at
/// every stop (validated at construction).
fn overtakes(
    earlier: &[gtfs_structures::StopTime],
    earlier_day: u8,
    later: &[gtfs_structures::StopTime],
    later_day: u8,
) -> bool {
    earlier.iter().zip(later).any(|(es, ls)| {
        let e_dep = shift_dep(
            es.departure_time.expect(
                "stop_time.departure_time is required by the GtfsError::MissingDepartureTime check earlier in GtfsTimetable::new()",
            ),
            earlier_day,
        );
        let l_dep = shift_dep(
            ls.departure_time.expect(
                "stop_time.departure_time is required by the GtfsError::MissingDepartureTime check earlier in GtfsTimetable::new()",
            ),
            later_day,
        );
        if l_dep < e_dep {
            return true;
        }
        // A later trip whose arrival at some stop is earlier than the
        // earlier trip's arrival is also overtaking.
        matches!(
            (es.arrival_time, ls.arrival_time),
            (Some(e_arr), Some(l_arr)) if shift_dep(l_arr, later_day) < shift_dep(e_arr, earlier_day)
        )
    })
}

impl<'gtfs> Timetable for GtfsTimetable<'gtfs> {
    fn n_stops(&self) -> usize {
        self.stop_ids.len()
    }

    fn n_routes(&self) -> usize {
        self.route_ids.len()
    }

    fn get_routes_serving_stop(&self, stop: StopIdx) -> &[(RouteIdx, u32)] {
        self.routes_for_stop[stop.idx()].as_slice()
    }

    fn get_stops_after(&self, route: RouteIdx, pos: u32) -> &[StopIdx] {
        let stops = &self.stops_for_route[route.idx()];
        &stops[pos as usize..]
    }

    fn stop_at(&self, route: RouteIdx, pos: u32) -> StopIdx {
        self.stops_for_route[route.idx()][pos as usize]
    }

    fn get_earliest_trip(&self, route: RouteIdx, at: SecondOfDay, pos: u32) -> Option<TripIdx> {
        let trips = &self.trips_for_route[route.idx()];
        let dep_row = &self.departure_times[route.idx()][pos as usize];
        let idx = dep_row.partition_point(|&dep| dep < at);
        // Common case (no_pickup empty for metro feeds): a single read.
        if self.no_pickup.is_empty() {
            return trips.get(idx).copied();
        }
        let mut idx = idx;
        while let Some(&trip) = trips.get(idx) {
            if !self.no_pickup.contains(&(trip, pos)) {
                return Some(trip);
            }
            idx += 1;
        }
        None
    }

    fn get_arrival_time(&self, trip: TripIdx, pos: u32) -> SecondOfDay {
        let (route_idx, trip_pos) = self.route_for_trip[trip.idx()];
        self.arrival_times[route_idx.idx()][pos as usize][trip_pos]
    }

    fn get_departure_time(&self, trip: TripIdx, pos: u32) -> SecondOfDay {
        let (route_idx, trip_pos) = self.route_for_trip[trip.idx()];
        self.departure_times[route_idx.idx()][pos as usize][trip_pos]
    }

    fn get_footpaths_from(&self, stop: StopIdx) -> &[StopIdx] {
        self.footpaths_for_stops[stop.idx()].as_slice()
    }

    fn get_transfer_time(&self, from: StopIdx, to: StopIdx) -> Duration {
        self.transfer_times
            .get(&(from, to))
            .copied()
            .unwrap_or(DEFAULT_TRANSFER_TIME)
    }

    fn pickup_allowed(&self, trip: TripIdx, pos: u32) -> bool {
        // is_empty() short-circuit: typical metro feeds have no
        // pickup_type=1 entries at all, so we skip the hash entirely.
        self.no_pickup.is_empty() || !self.no_pickup.contains(&(trip, pos))
    }

    fn drop_off_allowed(&self, trip: TripIdx, pos: u32) -> bool {
        self.no_drop_off.is_empty() || !self.no_drop_off.contains(&(trip, pos))
    }

    fn trip_wheelchair_accessible(&self, trip: TripIdx) -> bool {
        self.inaccessible_trips.is_empty() || !self.inaccessible_trips.contains(&trip)
    }

    fn stop_wheelchair_accessible(&self, stop: StopIdx) -> bool {
        self.inaccessible_stops.is_empty() || !self.inaccessible_stops.contains(&stop)
    }

    fn footpaths_are_transitively_closed(&self) -> bool {
        self.transfers_closed
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use gtfs_structures::{Calendar, CalendarDate, StopTime};

    fn st(arr: u32, dep: u32) -> StopTime {
        StopTime {
            arrival_time: Some(arr),
            departure_time: Some(dep),
            ..Default::default()
        }
    }

    /// Build a minimal `Gtfs` with one calendar entry running Mon-Fri
    /// throughout 2026 for service "weekday".
    fn weekday_only_feed() -> Gtfs {
        let mut g = Gtfs::default();
        g.calendar.insert(
            "weekday".into(),
            Calendar {
                id: "weekday".into(),
                monday: true,
                tuesday: true,
                wednesday: true,
                thursday: true,
                friday: true,
                saturday: false,
                sunday: false,
                start_date: NaiveDate::from_ymd_opt(2026, 1, 1).unwrap(),
                end_date: NaiveDate::from_ymd_opt(2026, 12, 31).unwrap(),
            },
        );
        g
    }

    fn ymd(y: i32, m: u32, d: u32) -> NaiveDate {
        NaiveDate::from_ymd_opt(y, m, d).unwrap()
    }

    #[test]
    fn calendar_active_on_weekday_inside_window() {
        let gtfs = weekday_only_feed();
        // 2026-05-04 is a Monday inside the window.
        assert!(is_service_active(&gtfs, "weekday", ymd(2026, 5, 4)));
    }

    #[test]
    fn calendar_inactive_on_weekend_inside_window() {
        let gtfs = weekday_only_feed();
        // 2026-05-02 is a Saturday – flag is false.
        assert!(!is_service_active(&gtfs, "weekday", ymd(2026, 5, 2)));
    }

    #[test]
    fn calendar_inactive_outside_date_window() {
        let gtfs = weekday_only_feed();
        // 2025-12-31 is a Wednesday but before start_date.
        assert!(!is_service_active(&gtfs, "weekday", ymd(2025, 12, 31)));
        // 2027-01-04 is a Monday but after end_date.
        assert!(!is_service_active(&gtfs, "weekday", ymd(2027, 1, 4)));
    }

    #[test]
    fn calendar_dates_added_overrides_calendar_inactive() {
        let mut gtfs = weekday_only_feed();
        // Add a Saturday exception.
        gtfs.calendar_dates.insert(
            "weekday".into(),
            vec![CalendarDate {
                service_id: "weekday".into(),
                date: ymd(2026, 5, 2),
                exception_type: Exception::Added,
            }],
        );
        assert!(is_service_active(&gtfs, "weekday", ymd(2026, 5, 2)));
    }

    #[test]
    fn calendar_dates_deleted_overrides_calendar_active() {
        let mut gtfs = weekday_only_feed();
        // Cancel the Monday 2026-05-04 service.
        gtfs.calendar_dates.insert(
            "weekday".into(),
            vec![CalendarDate {
                service_id: "weekday".into(),
                date: ymd(2026, 5, 4),
                exception_type: Exception::Deleted,
            }],
        );
        assert!(!is_service_active(&gtfs, "weekday", ymd(2026, 5, 4)));
    }

    #[test]
    fn unknown_service_id_is_inactive() {
        let gtfs = weekday_only_feed();
        assert!(!is_service_active(
            &gtfs,
            "no-such-service",
            ymd(2026, 5, 4)
        ));
    }

    #[test]
    fn overtakes_detects_arrival_inversion() {
        // Two stops; later trip arrives before earlier trip at the second stop.
        let earlier = vec![st(0, 0), st(20, 20)];
        let later = vec![st(5, 5), st(15, 15)];
        assert!(overtakes(&earlier, 0, &later, 0));
    }

    #[test]
    fn overtakes_detects_departure_inversion() {
        // Later trip's departure precedes earlier's at the second stop.
        let earlier = vec![st(0, 0), st(10, 30)];
        let later = vec![st(5, 5), st(10, 20)];
        assert!(overtakes(&earlier, 0, &later, 0));
    }

    #[test]
    fn non_overtaking_pair_is_clean() {
        let earlier = vec![st(0, 0), st(10, 10)];
        let later = vec![st(5, 5), st(15, 15)];
        assert!(!overtakes(&earlier, 0, &later, 0));
    }

    #[test]
    fn equal_schedules_do_not_overtake() {
        // Two trips with identical schedules don't overtake each other.
        let a = vec![st(0, 0), st(10, 10)];
        let b = vec![st(0, 0), st(10, 10)];
        assert!(!overtakes(&a, 0, &b, 0));
    }

    #[test]
    fn day_offset_keeps_overlapping_schedules_non_overtaking() {
        // Two trips with the same raw schedule but different day_offset
        // values are *not* overtaking — day-1 starts strictly after
        // day-0 ends thanks to the +86400 shift.
        let day0 = vec![st(0, 0), st(10, 10)];
        let day1 = vec![st(0, 0), st(10, 10)];
        assert!(!overtakes(&day0, 0, &day1, 1));
        // The reverse direction *is* overtaking — day-0 trip would
        // arrive long before the day-1 trip if treated as `later`.
        assert!(overtakes(&day1, 1, &day0, 0));
    }

    #[test]
    fn split_keeps_non_overtaking_trips_in_one_group() {
        let t1 = vec![st(0, 0), st(10, 10)];
        let t2 = vec![st(5, 5), st(15, 15)];
        let t3 = vec![st(10, 10), st(20, 20)];
        let trips = vec![
            ("t1", 0u8, t1.as_slice()),
            ("t2", 0u8, t2.as_slice()),
            ("t3", 0u8, t3.as_slice()),
        ];
        let groups = split_non_overtaking(&trips);
        assert_eq!(groups, vec![vec![("t1", 0), ("t2", 0), ("t3", 0)]]);
    }

    #[test]
    fn split_separates_overtaking_trips() {
        // t1 departs first but is overtaken by t2 (the express).
        let t1_local = vec![st(0, 0), st(60, 60)];
        let t2_express = vec![st(10, 10), st(20, 20)];
        let t3_local = vec![st(70, 70), st(130, 130)];
        let trips = vec![
            ("t1", 0u8, t1_local.as_slice()),
            ("t2", 0u8, t2_express.as_slice()),
            ("t3", 0u8, t3_local.as_slice()),
        ];
        let groups = split_non_overtaking(&trips);
        // Two non-overtaking sub-groups: {t1, t3} (locals) and {t2} (express).
        // Greedy insertion places t2 in a new sub-group when it overtakes t1,
        // then t3 lands in the t1 sub-group since it doesn't overtake t1.
        assert_eq!(groups.len(), 2);
        assert_eq!(groups[0], vec![("t1", 0), ("t3", 0)]);
        assert_eq!(groups[1], vec![("t2", 0)]);
    }

    #[test]
    fn gtfs_error_messages_carry_route_and_agency() {
        let with_agency = GtfsError::MissingStopTimes {
            trip: "t-42".into(),
            route: "r-7".into(),
            agency: Some("a-99".into()),
        };
        let msg = with_agency.to_string();
        assert!(msg.contains("t-42"), "missing trip id in {msg}");
        assert!(msg.contains("r-7"), "missing route id in {msg}");
        assert!(msg.contains("a-99"), "missing agency id in {msg}");

        let without_agency = GtfsError::MissingStop {
            stop: "s-1".into(),
            trip: "t-42".into(),
            route: "r-7".into(),
            agency: None,
        };
        let msg = without_agency.to_string();
        assert!(msg.contains("s-1"));
        assert!(msg.contains("t-42"));
        assert!(msg.contains("r-7"));
        assert!(
            msg.contains("agency ?"),
            "missing agency placeholder in {msg}"
        );
    }

    /// Build a synthetic single-route Gtfs: stops A, B; route R; one trip
    /// per day under the supplied service id, departing 06:00 → 06:30.
    fn synthetic_overnight_feed() -> Gtfs {
        use gtfs_structures::{Route, Stop, Trip};
        use std::sync::Arc;

        let mut g = weekday_only_feed();
        let stop_a = Arc::new(Stop {
            id: "A".into(),
            ..Default::default()
        });
        let stop_b = Arc::new(Stop {
            id: "B".into(),
            ..Default::default()
        });
        g.stops.insert("A".into(), Arc::clone(&stop_a));
        g.stops.insert("B".into(), Arc::clone(&stop_b));

        g.routes.insert(
            "R".into(),
            Route {
                id: "R".into(),
                ..Default::default()
            },
        );

        let trip = Trip {
            id: "T".into(),
            service_id: "weekday".into(),
            route_id: "R".into(),
            stop_times: vec![
                StopTime {
                    arrival_time: Some(6 * 3600),
                    departure_time: Some(6 * 3600),
                    stop: Arc::clone(&stop_a),
                    ..Default::default()
                },
                StopTime {
                    arrival_time: Some(6 * 3600 + 30 * 60),
                    departure_time: Some(6 * 3600 + 30 * 60),
                    stop: Arc::clone(&stop_b),
                    ..Default::default()
                },
            ],
            ..Default::default()
        };
        g.trips.insert("T".into(), trip);
        g
    }

    #[test]
    fn with_overnight_days_loads_next_day_trip() {
        // A 23:00 query on Mon 2026-05-04 cannot catch a single 06:00
        // trip that departs the same morning. Loading n=1 overnight
        // days makes the next morning's instance available, shifted
        // by 86 400 s, and the query finds it.
        use crate::{Duration, RaptorCache, SecondOfDay, Timetable};
        use jiff::civil::date;

        let g = synthetic_overnight_feed();

        // Single-day timetable: no journey from a 23:00 query.
        let tt = GtfsTimetable::new(&g, date(2026, 5, 4)).unwrap();
        let a = tt.stop_idx("A").unwrap();
        let b = tt.stop_idx("B").unwrap();
        let mut cache = RaptorCache::for_timetable(&tt);
        let journeys = tt
            .query()
            .from(a)
            .to(b)
            .max_transfers(1)
            .depart_at(SecondOfDay::hms(23, 0, 0))
            .run_with_cache(&mut cache);
        assert!(
            journeys.iter().all(|j| j.plan.is_empty()),
            "no journey expected without overnight load"
        );

        // Multi-day timetable: the next morning's trip is shifted to
        // 30:00, well after the 23:00 departure, and the journey is
        // found.
        let tt = GtfsTimetable::new(&g, date(2026, 5, 4))
            .unwrap()
            .with_overnight_days(&g, 1)
            .unwrap();
        let a = tt.stop_idx("A").unwrap();
        let b = tt.stop_idx("B").unwrap();
        let mut cache = RaptorCache::for_timetable(&tt);
        let journeys = tt
            .query()
            .from(&[(a, Duration::ZERO)])
            .to(&[(b, Duration::ZERO)])
            .max_transfers(1)
            .depart_at(SecondOfDay::hms(23, 0, 0))
            .run_with_cache(&mut cache);
        let best = journeys
            .iter()
            .filter(|j| !j.plan.is_empty())
            .min_by_key(|j| j.arrival())
            .expect("overnight journey should exist");
        // 86 400 (next day) + 6 * 3600 + 30 * 60 = 109 800
        assert_eq!(best.arrival(), SecondOfDay(86_400 + 6 * 3600 + 30 * 60));
    }

    #[test]
    fn with_overnight_days_zero_is_a_noop() {
        // Loading zero extra days is a no-op; the resulting timetable
        // is byte-equivalent to one built without the call.
        let g = synthetic_overnight_feed();
        let tt = GtfsTimetable::new(&g, ymd_jiff(2026, 5, 4))
            .unwrap()
            .with_overnight_days(&g, 0)
            .unwrap();
        assert_eq!(tt.n_overnight_days, 0);
    }

    fn ymd_jiff(y: i16, m: i8, d: i8) -> Date {
        Date::new(y, m, d).unwrap()
    }
}