vsrg 0.6.0

use crate::notes::{Interval, NoteState};
use crate::{
    notes::relations::{AssignPartnersToNote, ChainCondition, LinkStorage},
    notes::{NotesStorage, NotesStorageEditHook},
    rhythm::ClockTime,
};

/// Links each note to its nearest note(s) that comes before it.
///
/// # Remarks
/// For each source note, it searches backward for the nearest note's time, and gather all notes
/// sharing the same time (within some tolerance). Notes that do not satisfy the provided
/// [`Self::condition`] are ignored even if they are closer to the source note by time.
///
/// By default, gaps are measured from the source note's source time to the target note's end time.
/// By toggling [`Self::start_time_only`], it insteads only measures by the notes' start time.
///
/// All times and and tolerances are independently rounded to 0.1 ms (halfway values round away
/// from zero) before comparison. Callbacks retain original precision.
pub struct ChainBackward<S: NotesStorage> {
    max_gap: ClockTime,
    tolerance: ClockTime,
    start_time_only: bool,

    condition: Option<ChainCondition<S>>,
    applicable_note_types: &'static [S::NoteTypeEnum],
    link: Option<AssignPartnersToNote<S>>,
    link_storage: Option<LinkStorage<S>>,
    clear_storage: Option<fn(&mut S)>,

    scratch_in_range: Vec<S::NoteSnapshotEnum>,
    scratch_callback_args: Vec<S::NoteSnapshotEnum>,
}

impl<S: NotesStorage> ChainBackward<S> {
    /// Creates an endpoint-based chain with 1 ms tolerance and no callbacks.
    pub fn new(max_gap: ClockTime, applicable_note_types: &'static [S::NoteTypeEnum]) -> Self {
        Self {
            max_gap,
            tolerance: ClockTime::from_duration(std::time::Duration::from_millis(1)),
            start_time_only: false,
            condition: None,
            applicable_note_types,
            link: None,
            link_storage: None,
            clear_storage: None,
            scratch_in_range: vec![],
            scratch_callback_args: vec![],
        }
    }
}

impl<S: NotesStorage> ChainBackward<S> {
    /// Sets the maximum backward gap, independently rounded to 0.1 ms.
    ///
    /// # Remarks
    /// Notes outside this range are discarded from search and will never be assigned.
    ///
    /// If there is no maximum gap, then you can provide [`ClockTime::INF`], but this will have
    /// significant impact on performance when editing charts with large number of notes.
    pub fn max_gap(mut self, value: ClockTime) -> Self {
        self.max_gap = value;
        self
    }

    /// Sets the inclusive tolerance.
    ///
    /// # Remarks
    /// When scanning for chainable notes, if a note has the minimum backward time plus an amount
    /// smaller than this tolerance, then they're still eligible for chaining.
    ///
    /// All times and and tolerances are independently rounded to 0.1 ms (halfway values round away
    /// from zero) before comparison. Callbacks retain original precision.
    pub fn tolerance(mut self, value: ClockTime) -> Self {
        self.tolerance = value;
        self
    }

    /// Sets the note types eligible as both sources and successors.
    ///
    /// # Remarks
    /// Restrict this relationship to only note types that you need, in order to speed up
    /// computation.
    pub fn applicable_note_types(mut self, value: &'static [S::NoteTypeEnum]) -> Self {
        self.applicable_note_types = value;
        self
    }

    /// Sets an additional ordered predicate over the source and successor.
    ///
    /// # Requirements
    /// The predicate returns whether two notes should be chained. If the predicate returns false,
    /// then the note is skipped. Only notes whose predicate returns true are used when searching
    /// for the minimum backward time.
    ///
    /// The condition is *not* commutative. The first argument is the later note, the second
    /// argument is the earlier note.
    pub fn condition(mut self, value: ChainCondition<S>) -> Self {
        self.condition = Some(value);
        self
    }

    /// Links later notes to an earlier note.
    ///
    /// # Remarks
    /// The note can copy any data from the partner notes as needed. For example, in cases where you
    /// need to draw a connection to the partner notes, then caching the partner's position in the
    /// note's runtime state may be a good idea.
    ///
    /// The slice contains the note's current direct matches, excluding the note itself. Empty slice
    /// means deactivating the relationship or unlinking the note from their partners.
    ///
    /// # Requirements
    /// - This operation must be *stateless*: how it writes should not depend on the current runtime
    ///   state of the note.
    /// - This operation must be *idempotent*: multiple applications of this callback on the same note
    ///   is the same as only one application.
    ///
    /// Effectively, it should sets the partners rather than appending the partners to the note.
    pub fn link(mut self, callback: AssignPartnersToNote<S>) -> Self {
        self.link = Some(callback);
        self
    }

    /// Add a link between notes to the notes storage.
    ///
    /// # Remarks
    /// The notes storage itself generated by [`crate::generate_notes_storage`] allows storing
    /// additional user-provided fields. For use cases where relationship state does not belong to any
    /// single note, then it may be stored in such user-provided field instead.
    ///
    /// # Requirements
    /// This callback should updates auxiliary storage fields for a refreshed source and its successors.
    /// Empty slices clear all links to a source note.
    pub fn link_storage(mut self, callback: LinkStorage<S>) -> Self {
        self.link_storage = Some(callback);
        self
    }

    /// Clear this relationship's auxiliary links before rebuilding, including stale source ids.
    pub fn clear_storage(mut self, callback: fn(&mut S)) -> Self {
        self.clear_storage = Some(callback);
        self
    }

    /// When true, it always measures gaps from the note's start instead of its end.
    pub fn start_time_only(mut self, value: bool) -> Self {
        self.start_time_only = value;
        self
    }
}

fn timing_ticks(time: ClockTime) -> f64 {
    (time.seconds() * 10_000.0).round()
}

// Indexes retain unrounded times. Include the rounding bins and round
// outward when converting query bounds back to seconds.
fn query_window(start: f64, end: f64) -> Interval<ClockTime> {
    Interval::new(
        ClockTime::from_seconds(((start - 1.0) / 10_000.0).next_down())
            .unwrap_or(ClockTime::ZERO - ClockTime::INF),
        ClockTime::from_seconds(((end + 1.0) / 10_000.0).next_up()).unwrap_or(ClockTime::INF),
    )
}

impl<S: NotesStorage> ChainBackward<S> {
    // Recompute each source from its full backward window, excluding the
    // entire pending removal/replacement batch before choosing the nearest end.
    fn refresh(
        &mut self,
        storage: &mut S,
        source: &S::NoteSnapshotEnum,
        excluded: &impl Fn(u64, S::NoteTypeEnum) -> bool,
    ) {
        let source_type = S::NoteTypeEnum::from(source);
        let start = timing_ticks(source.clock_time_interval().start());
        let tolerance = timing_ticks(self.tolerance);
        let lower = start - timing_ticks(self.max_gap) - tolerance;
        let source_note = S::NoteEnum::from(source);
        let start_only = self.start_time_only;
        let endpoint = |note: &S::NoteSnapshotEnum| {
            let interval = note.clock_time_interval();
            timing_ticks(if start_only {
                interval.start()
            } else {
                interval.end()
            })
        };
        self.scratch_callback_args.clear();
        self.scratch_callback_args.extend(
            storage
                .notes_overlapping_range(query_window(lower, start + tolerance))
                .filter(|target| {
                    let target_type = S::NoteTypeEnum::from(target);
                    let end = endpoint(target);
                    (source.id() != target.id() || source_type != target_type)
                        && self.applicable_note_types.contains(&target_type)
                        && !excluded(target.id(), target_type)
                        && end >= lower
                        && end <= start + tolerance
                        && self.condition.is_none_or(|condition| {
                            condition(&S::NoteEnum::from(target), &source_note)
                        })
                }),
        );
        if let Some(nearest) = self
            .scratch_callback_args
            .iter()
            .map(&endpoint)
            .reduce(f64::max)
        {
            self.scratch_callback_args
                .retain(|target| endpoint(target) >= nearest - tolerance);
        }
        if let Some(link) = self.link {
            storage.query_notes_mut([(source.id(), source_type)].into_iter(), |state| {
                link(state, &self.scratch_callback_args)
            });
        }
        if let Some(link) = self.link_storage {
            link(storage, source, &self.scratch_callback_args);
        }
    }

    fn collect_successors(&mut self, storage: &S, target: &S::NoteSnapshotEnum) {
        let interval = target.clock_time_interval();
        let endpoint = timing_ticks(if self.start_time_only {
            interval.start()
        } else {
            interval.end()
        });
        let tolerance = timing_ticks(self.tolerance);
        let lower = endpoint - tolerance;
        let upper = endpoint + timing_ticks(self.max_gap) + tolerance;
        self.scratch_in_range.clear();
        self.scratch_in_range.extend(
            storage
                .notes_overlapping_range(query_window(lower, upper))
                .filter(|source| {
                    let start = timing_ticks(source.clock_time_interval().start());
                    self.applicable_note_types
                        .contains(&S::NoteTypeEnum::from(source))
                        && start >= lower
                        && start <= upper
                }),
        );
    }
    fn post_add_one(&mut self, storage: &mut S, note_type: S::NoteTypeEnum, id: u64) {
        if (self.link.is_none() && self.link_storage.is_none())
            || !self.applicable_note_types.contains(&note_type)
        {
            return;
        }
        let Some(added) = storage.query_notes([(id, note_type)].into_iter()).next() else {
            return;
        };
        self.collect_successors(storage, &added);
        for index in 0..self.scratch_in_range.len() {
            let source = self.scratch_in_range[index].clone();
            if source.id() != id || S::NoteTypeEnum::from(&source) != note_type {
                self.refresh(storage, &source, &|_, _| false);
            }
        }
        self.refresh(storage, &added, &|_, _| false);
    }

    fn pre_remove_one(
        &mut self,
        storage: &mut S,
        note_type: S::NoteTypeEnum,
        id: u64,
        excluded: impl Fn(u64, S::NoteTypeEnum) -> bool,
    ) {
        if (self.link.is_none() && self.link_storage.is_none())
            || !self.applicable_note_types.contains(&note_type)
        {
            return;
        }
        let Some(removed) = storage.query_notes([(id, note_type)].into_iter()).next() else {
            return;
        };
        self.collect_successors(storage, &removed);
        for index in 0..self.scratch_in_range.len() {
            let source = self.scratch_in_range[index].clone();
            if !excluded(source.id(), S::NoteTypeEnum::from(&source)) {
                self.refresh(storage, &source, &excluded);
            }
        }
    }

    fn post_update_one(
        &mut self,
        storage: &mut S,
        _before: &S::NoteSnapshotEnum,
        after: &S::NoteSnapshotEnum,
    ) {
        self.post_add_one(storage, S::NoteTypeEnum::from(after), after.id());
    }
}
impl<S: NotesStorage> NotesStorageEditHook<S> for ChainBackward<S> {
    fn post_rebuild_clock_time(&mut self, storage: &mut S) {
        if let Some(clear) = self.clear_storage {
            clear(storage);
        } else if let Some(link) = self.link_storage {
            self.scratch_in_range.clear();
            self.scratch_in_range.extend(storage.all_notes());
            for note in &self.scratch_in_range {
                link(storage, note, &[]);
            }
        }
        let notes: Vec<_> = storage
            .all_notes()
            .filter(|note| {
                self.applicable_note_types
                    .contains(&S::NoteTypeEnum::from(note))
            })
            .collect();
        for note in notes {
            self.refresh(storage, &note, &|_, _| false);
        }
    }

    fn post_add(&mut self, storage: &mut S, notes: &[(u64, S::NoteTypeEnum)]) {
        for &(id, ty) in notes {
            self.post_add_one(storage, ty, id);
        }
    }
    fn pre_remove(&mut self, storage: &mut S, notes: &[S::NoteSnapshotEnum]) {
        for note in notes {
            self.pre_remove_one(storage, S::NoteTypeEnum::from(note), note.id(), |id, ty| {
                notes
                    .iter()
                    .any(|removed| removed.id() == id && S::NoteTypeEnum::from(removed) == ty)
            });
        }
    }
    fn pre_update(&mut self, storage: &mut S, notes: &mut [(u64, S::NoteEnum)]) {
        for (id, note) in notes.iter() {
            self.pre_remove_one(storage, S::NoteTypeEnum::from(note), *id, |id, ty| {
                notes.iter().any(|(replacing_id, replacement)| {
                    *replacing_id == id && S::NoteTypeEnum::from(replacement) == ty
                })
            });
        }
    }
    fn post_update(
        &mut self,
        storage: &mut S,
        notes: &[(S::NoteSnapshotEnum, S::NoteSnapshotEnum)],
    ) {
        for (before, after) in notes {
            self.post_update_one(storage, before, after);
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::notes::relations::test_common::{
        RelLong, RelShort, World, clock_time, long_at, short_at,
    };
    use crate::notes::{LongNoteTypeStorage, ShortNoteTypeStorage};
    use proptest::prelude::*;

    // Both fixtures use the same lane predicate and record the complete outgoing
    // adjacency list, so an incorrect partner cannot pass as merely "chained".
    macro_rules! fixture {
        ($start_only:expr) => {
            crate::generate_notes_storage! {
                enum Kind,
                enum Note,
                enum Snapshot,
                enum NoteRef,
                enum NoteMut,
                struct Storage {
                    note_type Short(RelShort) => shorts: ShortNoteTypeStorage<RelShort>,
                    note_type Long(RelLong) => longs: LongNoteTypeStorage<RelLong>,
                    edit_hook ChainBackward::<Storage>::new(clock_time(25.049), &[Kind::Short, Kind::Long])
                        .tolerance(clock_time(1.049))
                        .start_time_only($start_only)
                        .condition(|a, b| position(a) == position(b))
                        .link(|note, partners| {
                            let mut ids: Vec<_> = partners.iter().map(key).collect();
                            ids.sort_unstable();
                            match note {
                                NoteMut::Short(n) => {
                                    *n.runtime_data.chained = !ids.is_empty();
                                    *n.runtime_data.matching_ids = ids;
                                }
                                NoteMut::Long(n) => {
                                    *n.runtime_data.chained = !ids.is_empty();
                                    *n.runtime_data.matching_ids = ids;
                                }
                            }
                        }),
                }
            }

            #[test]
            fn rebuild_restores_cleared_relationships() {
                let (mut world, mut storage) = setup(vec![long(0.0, 10.0, 0), short(10.0, 0),
                    long(30.0, 10.0, 0), short(40.0, 1), short(500.0, 0)]);
                for ty in [Kind::Short, Kind::Long] {
                    storage.all_notes_mut_of_type(ty, |note| match note {
                        NoteMut::Short(n) => {
                            n.runtime_data.matching_ids.clear();
                            *n.runtime_data.chained = false;
                        }
                        NoteMut::Long(n) => {
                            n.runtime_data.matching_ids.clear();
                            *n.runtime_data.chained = false;
                        }
                    });
                }
                for _ in 0..2 {
                    storage.rebuild_clock_time(
                        &mut world.note_groups,
                        &mut world.tempo_tracks,
                        &mut world.scroll_tracks,
                    );
                    assert_matches_scan(&storage);
                }
                let mut empty_world = World::new(0);
                let mut empty = Storage::new();
                empty.rebuild_clock_time(
                    &mut empty_world.note_groups,
                    &mut empty_world.tempo_tracks,
                    &mut empty_world.scroll_tracks,
                );
                assert_matches_scan(&empty);
            }

            fn position(note: &Note) -> u32 {
                match note {
                    Note::Short(n) => n.pos,
                    Note::Long(n) => n.pos,
                }
            }

            fn key(note: &Snapshot) -> (u64, bool) {
                (note.id(), matches!(note, Snapshot::Short(_)))
            }

            fn short(t: f64, lane: u32) -> Note {
                Note::Short(short_at(-t, lane))
            }
            fn long(t: f64, len: f64, lane: u32) -> Note {
                Note::Long(long_at(if $start_only { -t } else { -t - len }, len, lane))
            }

            fn setup(notes: Vec<Note>) -> (World, Storage) {
                let mut world = World::new(0);
                let storage = Storage::with_notes(
                    notes,
                    &mut world.note_groups,
                    &mut world.tempo_tracks,
                    &mut world.scroll_tracks,
                );
                (world, storage)
            }

            fn add(world: &mut World, storage: &mut Storage, note: Note) {
                storage.add_note(
                    &mut world.note_groups,
                    &mut world.tempo_tracks,
                    &mut world.scroll_tracks,
                    note,
                );
            }

            fn replace(world: &mut World, storage: &mut Storage, id: u64, note: Note) {
                storage.replace_note(
                    &mut world.note_groups,
                    &mut world.tempo_tracks,
                    &mut world.scroll_tracks,
                    id,
                    note,
                );
            }

            fn links(storage: &Storage, id: u64, kind: Kind) -> Vec<(u64, bool)> {
                match storage
                    .query_notes_ref([(id, kind)].into_iter())
                    .next()
                    .unwrap()
                {
                    NoteRef::Short(n) => n.runtime_data.matching_ids.clone(),
                    NoteRef::Long(n) => n.runtime_data.matching_ids.clone(),
                }
            }

            // Scan reflected times independently: the nearest backward endpoint becomes
            // the nearest forward start. Fixtures below reflect each scenario around zero.
            fn assert_matches_scan(storage: &Storage) {
                let notes: Vec<_> = storage
                    .all_notes_of_type(Kind::Short)
                    .chain(storage.all_notes_of_type(Kind::Long))
                    .collect();
                for source in &notes {
                    let endpoint = -(source.clock_time_interval().start().seconds() * 10_000.0).round() as i64;
                    let reflected_start = |note: &Snapshot| {
                        let interval = note.clock_time_interval();
                        let time = if $start_only { interval.start() } else { interval.end() };
                        -(time.seconds() * 10_000.0).round() as i64
                    };
                    let eligible: Vec<_> = notes
                        .iter()
                        .filter(|target| {
                            let start = reflected_start(target);
                            key(source) != key(target)
                                && position(&Note::from(source)) == position(&Note::from(*target))
                                && start >= endpoint - 10
                                && start <= endpoint + 260
                        })
                        .collect();
                    let nearest = eligible
                        .iter()
                        .map(|n| {
                            reflected_start(n)
                        })
                        .min();
                    let mut expected: Vec<_> = eligible
                        .into_iter()
                        .filter(|n| {
                            nearest.is_some_and(|t| {
                                reflected_start(n)
                                    <= t + 10
                            })
                        })
                        .map(key)
                        .collect();
                    expected.sort_unstable();
                    let kind = Kind::from(source);
                    assert_eq!(
                        links(storage, source.id(), kind),
                        expected,
                        "outgoing links for {:?}",
                        key(source)
                    );
                    let chained = match storage
                        .query_notes_ref([(source.id(), kind)].into_iter())
                        .next()
                        .unwrap()
                    {
                        NoteRef::Short(n) => *n.runtime_data.chained,
                        NoteRef::Long(n) => *n.runtime_data.chained,
                    };
                    assert_eq!(chained, !expected.is_empty());
                }
                storage.shorts.health_check();
                storage.longs.health_check();
            }
        };
    }

    mod endpoints {
        use super::*;
        fixture!(false);

        #[test]
        fn condition_receives_predecessor_before_source() {
            // Use real (unreflected) chart times to verify callback direction.
            let (_, mut storage) = setup(vec![
                Note::Long(long_at(0.0, 100.0, 1)),
                Note::Short(short_at(110.0, 2)),
            ]);
            let mut hook =
                ChainBackward::<Storage>::new(clock_time(25.0), &[Kind::Short, Kind::Long])
                    .condition(|earlier, later| position(earlier) + 1 == position(later))
                    .link(|source, predecessors| {
                        if let NoteMut::Short(source) = source {
                            *source.runtime_data.matching_ids =
                                predecessors.iter().map(key).collect();
                        }
                    });
            hook.post_add(&mut storage, &[(1, Kind::Short)]);
            assert_eq!(links(&storage, 1, Kind::Short), vec![(1, false)]);
            // Rejecting the ordered pair must clear the previously assigned link.
            hook = hook.condition(|earlier, later| position(earlier) == position(later) + 1);
            hook.post_add(&mut storage, &[(1, Kind::Short)]);
            assert!(links(&storage, 1, Kind::Short).is_empty());
        }
        #[test]
        fn rounded_gap_boundaries_work_in_both_insertion_orders() {
            // Both endpoints round independently; the raw gaps differ by
            // almost 0.1 ms from the rounded comparison.
            for (source, target, expected) in [
                (-0.049, 26.049, true),
                (-0.051, 26.049, false),
                (0.049, -1.049, true),
                (0.051, -1.049, false),
            ] {
                for target_first in [false, true] {
                    let (mut world, mut storage) = setup(vec![]);
                    let notes = if target_first {
                        vec![short(target, 0), long(source - 10.0, 10.0, 0)]
                    } else {
                        vec![long(source - 10.0, 10.0, 0), short(target, 0)]
                    };
                    for note in notes {
                        add(&mut world, &mut storage, note);
                    }
                    assert_eq!(!links(&storage, 1, Kind::Long).is_empty(), expected);
                    assert_matches_scan(&storage);
                    storage.remove_note(Kind::Short, 1);
                    assert_matches_scan(&storage);
                }
            }
        }

        #[test]
        fn predecessor_grouping_uses_rounded_endpoints() {
            let (_, storage) = setup(vec![
                long(-10.0, 10.0, 0),
                short(10.049, 0),
                short(11.049, 0),
                short(11.051, 0),
            ]);
            assert_eq!(links(&storage, 1, Kind::Long), vec![(1, true), (2, true)]);
            assert_matches_scan(&storage);
        }

        #[test]
        fn changing_lane_clears_the_replaced_notes_outgoing_links() {
            let (mut world, mut storage) = setup(vec![short(0.0, 0), short(10.0, 0)]);
            assert_eq!(links(&storage, 1, Kind::Short), vec![(2, true)]);
            replace(&mut world, &mut storage, 1, short(0.0, 1));
            assert!(links(&storage, 1, Kind::Short).is_empty());
            assert_matches_scan(&storage);
        }

        proptest! {
            #[test]
            fn fractional_endpoints_match_rounded_scan(
                source in -100_000i32..100_000,
                gap in -2_000i32..28_000,
            ) {
                let source = source as f64 / 1000.0;
                let target = source + gap as f64 / 1000.0;
                let (mut world, mut storage) = setup(vec![short(target, 0)]);
                add(&mut world, &mut storage, long(source - 10.0, 10.0, 0));
                assert_matches_scan(&storage);
                replace(&mut world, &mut storage, 1, short(target + 0.051, 0));
                assert_matches_scan(&storage);
                storage.remove_note(Kind::Short, 1);
                assert_matches_scan(&storage);
            }
        }
        #[test]
        fn two_notes_chain_at_the_long_note_endpoint() {
            let (_, storage) = setup(vec![long(0.0, 100.0, 0), short(110.0, 0)]);
            assert_eq!(links(&storage, 1, Kind::Long), vec![(1, true)]);
            assert_matches_scan(&storage);
        }

        #[test]
        fn two_notes_outside_the_gap_or_condition_do_not_chain() {
            for target in [short(40.0, 0), short(10.0, 1)] {
                let (_, storage) = setup(vec![short(0.0, 0), target]);
                assert!(links(&storage, 1, Kind::Short).is_empty());
                assert_matches_scan(&storage);
            }
        }

        #[test]
        fn three_notes_chain_back_to_back() {
            let (_, storage) = setup(vec![
                long(0.0, 10.0, 0),
                long(10.0, 10.0, 0),
                short(20.0, 0),
            ]);
            assert_eq!(links(&storage, 1, Kind::Long), vec![(2, false)]);
            assert_eq!(links(&storage, 2, Kind::Long), vec![(1, true)]);
            assert_matches_scan(&storage);
        }

        #[test]
        fn adding_a_successor_links_it_to_two_existing_notes() {
            let (mut world, mut storage) = setup(vec![short(20.0, 0), long(20.0, 5.0, 0)]);
            add(&mut world, &mut storage, long(0.0, 10.0, 0));
            assert_eq!(links(&storage, 2, Kind::Long), vec![(1, false), (1, true)]);
            assert_matches_scan(&storage);
        }

        #[test]
        fn adding_a_predecessor_links_two_existing_successors() {
            let (mut world, mut storage) = setup(vec![long(0.0, 10.0, 0), long(5.0, 5.0, 0)]);
            add(&mut world, &mut storage, short(20.0, 0));
            assert_eq!(links(&storage, 1, Kind::Long), vec![(1, true)]);
            assert_eq!(links(&storage, 2, Kind::Long), vec![(1, true)]);
            assert_matches_scan(&storage);
        }

        // The comments list the preceding scenario twice; exercise the reverse
        // insertion order as well.
        #[test]
        fn adding_successors_after_their_shared_predecessor() {
            let (mut world, mut storage) = setup(vec![short(20.0, 0)]);
            add(&mut world, &mut storage, long(0.0, 10.0, 0));
            add(&mut world, &mut storage, long(5.0, 5.0, 0));
            assert_eq!(links(&storage, 1, Kind::Long), vec![(1, true)]);
            assert_eq!(links(&storage, 2, Kind::Long), vec![(1, true)]);
            assert_matches_scan(&storage);
        }

        #[test]
        fn removing_middle_unchains_endpoints_when_gap_is_too_large() {
            let (_, mut storage) = setup(vec![
                short(0.0, 0),
                short(20.0, 0),
                short(40.0, 0),
                short(0.0, 1),
                short(20.0, 1),
                short(40.0, 1),
            ]);
            assert_matches_scan(&storage);
            storage.remove_note(Kind::Short, 2);
            assert!(links(&storage, 1, Kind::Short).is_empty());
            assert_eq!(links(&storage, 4, Kind::Short), vec![(5, true)]);
            assert_eq!(links(&storage, 5, Kind::Short), vec![(6, true)]);
            assert_matches_scan(&storage);
        }

        #[test]
        fn removing_middle_relinks_endpoints_and_preserves_other_chain() {
            let (_, mut storage) = setup(vec![
                short(0.0, 0),
                short(10.0, 0),
                short(20.0, 0),
                short(0.0, 1),
                short(10.0, 1),
                short(20.0, 1),
            ]);
            assert_matches_scan(&storage);
            storage.remove_note(Kind::Short, 2);
            assert_eq!(links(&storage, 1, Kind::Short), vec![(3, true)]);
            assert_eq!(links(&storage, 4, Kind::Short), vec![(5, true)]);
            assert_eq!(links(&storage, 5, Kind::Short), vec![(6, true)]);
            assert_matches_scan(&storage);
        }

        #[test]
        fn removing_both_middle_notes_relinks_endpoints() {
            let (_, mut storage) = setup(vec![
                short(0.0, 0),
                short(10.0, 0),
                short(10.0, 0),
                short(20.0, 0),
            ]);
            assert_matches_scan(&storage);
            storage.remove_notes(vec![(2, Kind::Short), (3, Kind::Short)]);
            assert_eq!(links(&storage, 1, Kind::Short), vec![(4, true)]);
            assert_matches_scan(&storage);
        }

        #[test]
        fn replacing_middle_moves_it_to_a_different_chain() {
            let (mut world, mut storage) = setup(vec![
                short(0.0, 0),
                short(20.0, 0),
                short(40.0, 0),
                short(100.0, 0),
                short(140.0, 0),
            ]);
            assert_matches_scan(&storage);
            replace(&mut world, &mut storage, 2, short(120.0, 0));
            assert!(links(&storage, 1, Kind::Short).is_empty());
            assert_eq!(links(&storage, 4, Kind::Short), vec![(2, true)]);
            assert_eq!(links(&storage, 2, Kind::Short), vec![(5, true)]);
            assert_matches_scan(&storage);
        }

        proptest! {
            #[test]
            fn random_edits_match_manual_scan(
                ops in prop::collection::vec(
                    (0u8..5, 0usize..30, -5i32..15, 0u32..3, any::<bool>()), 1..40)
            ) {
                let (mut world, mut storage) = setup(vec![]);
                for (op, index, time, lane, is_long) in ops {
                    let note = if is_long { long(time as f64 * 10.0, 10.0, lane) }
                        else { short(time as f64 * 10.0, lane) };
                    let kind = Kind::from(&note);
                    let ids: Vec<_> = storage.all_notes_of_type(kind).map(|n| n.id()).collect();
                    if op == 0 || ids.is_empty() {
                        add(&mut world, &mut storage, note);
                    } else if op == 1 {
                        storage.remove_note(kind, ids[index % ids.len()]);
                    } else if op == 2 {
                        replace(&mut world, &mut storage, ids[index % ids.len()], note);
                    } else if op == 3 {
                        storage.remove_notes(ids.into_iter().take(2).map(|id| (id, kind)).collect());
                    } else {
                        storage.replace_notes(
                            &world.note_groups,
                            &world.tempo_tracks,
                            &world.scroll_tracks,
                            ids.into_iter().take(2).map(|id| (id, note.clone())).collect(),
                        );
                    }
                    assert_matches_scan(&storage);
                }
            }
        }
    }

    mod starts {
        use super::*;
        fixture!(true);

        #[test]
        fn rounded_start_boundaries_ignore_long_note_ends() {
            for (target, expected) in [(26.049, true), (26.051, false)] {
                for target_first in [false, true] {
                    let (mut world, mut storage) = setup(vec![]);
                    let notes = if target_first {
                        vec![short(target, 0), long(-0.049, 100.0, 0)]
                    } else {
                        vec![long(-0.049, 100.0, 0), short(target, 0)]
                    };
                    for note in notes {
                        add(&mut world, &mut storage, note);
                    }
                    assert_eq!(!links(&storage, 1, Kind::Long).is_empty(), expected);
                    assert_matches_scan(&storage);
                    // Changing only duration must preserve start-based links.
                    replace(&mut world, &mut storage, 1, long(-0.049, 200.0, 0));
                    assert_matches_scan(&storage);
                    storage.remove_note(Kind::Short, 1);
                    assert_matches_scan(&storage);
                }
            }
        }
        #[test]
        fn two_start_time_chains_survive_add_update_remove_and_replace() {
            // Long durations deliberately overlap later starts: using endpoints
            // instead of starts must fail this fixture.
            let (mut world, mut storage) = setup(vec![
                long(0.0, 100.0, 0),
                long(20.0, 100.0, 0),
                long(40.0, 100.0, 0),
                long(0.0, 100.0, 1),
                long(20.0, 100.0, 1),
                long(40.0, 100.0, 1),
            ]);
            assert_matches_scan(&storage);
            add(&mut world, &mut storage, short(60.0, 0));
            assert_matches_scan(&storage);
            replace(&mut world, &mut storage, 2, long(15.0, 200.0, 0));
            assert_matches_scan(&storage);
            storage.remove_note(Kind::Long, 2);
            assert_matches_scan(&storage);
            replace(&mut world, &mut storage, 5, long(120.0, 100.0, 1));
            assert_matches_scan(&storage);
        }
        proptest! {
            #[test]
            fn random_edits_match_manual_scan(
                ops in prop::collection::vec(
                    (0u8..5, 0usize..30, -50_000i32..150_000, 0u32..3, any::<bool>()), 1..40)
            ) {
                let (mut world, mut storage) = setup(vec![]);
                for (op, index, time, lane, is_long) in ops {
                    let note = if is_long { long(time as f64 / 1000.0, 100.0, lane) }
                        else { short(time as f64 / 1000.0, lane) };
                    let kind = Kind::from(&note);
                    let ids: Vec<_> = storage.all_notes_of_type(kind).map(|n| n.id()).collect();
                    if op == 0 || ids.is_empty() {
                        add(&mut world, &mut storage, note);
                    } else if op == 1 {
                        storage.remove_note(kind, ids[index % ids.len()]);
                    } else if op == 2 {
                        replace(&mut world, &mut storage, ids[index % ids.len()], note);
                    } else if op == 3 {
                        storage.remove_notes(ids.into_iter().take(2).map(|id| (id, kind)).collect());
                    } else {
                        storage.replace_notes(
                            &world.note_groups,
                            &world.tempo_tracks,
                            &world.scroll_tracks,
                            ids.into_iter().take(2).map(|id| (id, note.clone())).collect()
                        );
                    }
                    assert_matches_scan(&storage);
                }
            }
        }
    }
}