pub const fn curve(

        from: f32,

        to: f32,

        function: AnimationInterpolationFunction,

        duration_secs: f32,

    ) -> Self {

        Self {

            from,

            to,

            current: from,

            velocity: 0.0,

            elapsed_secs: 0.0,

            interp: Interp::Curve { function, duration_secs },

            finished: false,

        }

    }

    pub const fn spring(from: f32, to: f32, spring: Spring) -> Self {

        Self {

            from,

            to,

            current: from,

            velocity: 0.0,

            elapsed_secs: 0.0,

            interp: Interp::Spring(spring),

            finished: false,

        }

    }

    pub fn tick(&mut self, dt: f32) -> f32 {

        if self.finished {

            return self.current;

        }

        match self.interp {

            Interp::Curve { function, duration_secs } => {

                if duration_secs <= 0.0 {

                    self.current = self.to;

                    self.velocity = 0.0;

                    self.finished = true;

                    return self.current;

                }

                self.elapsed_secs += dt.max(0.0);

                let linear_t = (self.elapsed_secs / duration_secs).clamp(0.0, 1.0);

                let eased = ease(function, linear_t);

                let previous = self.current;

                {

                    self.current = self.from + (self.to - self.from) * eased;

                }

                self.velocity = if dt > 0.0 { (self.current - previous) / dt } else { 0.0 };

                if linear_t >= 1.0 {

                    self.current = self.to;

                    self.finished = true;

                }

            Interp::Spring(spring) => {

                let (value, velocity) = spring.step(self.current, self.to, self.velocity, dt);

                self.current = value;

                self.velocity = velocity;

                if spring.is_settled(value, self.to, velocity) {

                    self.current = self.to;

                    self.velocity = 0.0;

                    self.finished = true;

                }

        self.current

    }

    pub const fn is_finished(&self) -> bool {

        self.finished

    }

    pub fn retarget(&mut self, new_to: f32) {

        if (self.to - new_to).abs() < f32::EPSILON && !self.finished {

            return; // already heading there; do not restart the clock

        }

        self.from = self.current;

        self.to = new_to;

        self.elapsed_secs = 0.0;

        self.finished = false;

    }

pub fn ease(function: AnimationInterpolationFunction, t: f32) -> f32 {

    let t = t.clamp(0.0, 1.0);

    match function {

        AnimationInterpolationFunction::Linear => t,

        AnimationInterpolationFunction::Ease => cubic_bezier_y(0.25, 0.1, 0.25, 1.0, t),

        AnimationInterpolationFunction::EaseIn => cubic_bezier_y(0.42, 0.0, 1.0, 1.0, t),

        AnimationInterpolationFunction::EaseOut => cubic_bezier_y(0.0, 0.0, 0.58, 1.0, t),

            cubic_bezier_y(0.42, 0.0, 0.58, 1.0, t)

}

fn cubic_bezier_y(x1: f32, y1: f32, x2: f32, y2: f32, x: f32) -> f32 {

    let bezier = |a: f32, b: f32, t: f32| {

        let inv = 1.0 - t;

        3.0 * inv * inv * t * a + 3.0 * inv * t * t * b + t * t * t

    };

    let bezier_slope = |a: f32, b: f32, t: f32| {

        let inv = 1.0 - t;

        3.0 * inv * inv * a + 6.0 * inv * t * (b - a) + 3.0 * t * t * (1.0 - b)

    };

    if x <= 0.0 {

        return 0.0;

    }

    if x >= 1.0 {

        return 1.0;

    }

    let mut t = x;

    for _ in 0..NEWTON_ITERATIONS {

        let error = bezier(x1, x2, t) - x;

        if error.abs() < EPSILON {

            return bezier(y1, y2, t);

        }

        let slope = bezier_slope(x1, x2, t);

        if slope.abs() < EPSILON {

        }

        t -= error / slope;

}

    pub fn is_identity(&self) -> bool {

        self.translate_x.abs() < 0.01

            && self.translate_y.abs() < 0.01

            && (self.scale_x - 1.0).abs() < 0.001

            && (self.scale_y - 1.0).abs() < 0.001

    }

pub fn flip(first: LogicalRect, last: LogicalRect) -> FlipTransform {

    let _ = (first.size, last.size); // sizes are layout's job, not the animation's

    FlipTransform {

        translate_x: first.origin.x - last.origin.x,

        translate_y: first.origin.y - last.origin.y,

        scale_x: 1.0,

        scale_y: 1.0,

    }

}

    pub const fn move_from_flip(flip: FlipTransform, interp: Interp) -> Self {

        Self {

            class: AnimClass::Move,

            translate_x: channel(flip.translate_x, 0.0, interp),

            translate_y: channel(flip.translate_y, 0.0, interp),

            scale_x: channel(flip.scale_x, 1.0, interp),

            scale_y: channel(flip.scale_y, 1.0, interp),

            opacity: channel(1.0, 1.0, interp),

        }

    }

    pub const fn enter_slide(from_x: f32, from_y: f32, interp: Interp) -> Self {

        Self {

            class: AnimClass::Enter,

            translate_x: channel(from_x, 0.0, interp),

            translate_y: channel(from_y, 0.0, interp),

            scale_x: channel(1.0, 1.0, interp),

            scale_y: channel(1.0, 1.0, interp),

            opacity: channel(1.0, 1.0, interp),

        }

    }

    pub fn retarget_presence(&mut self, class: AnimClass, to_x: f32, to_y: f32) {

        self.class = class;

        self.translate_x.retarget(to_x);

        self.translate_y.retarget(to_y);

        self.scale_x.retarget(1.0);

        self.scale_y.retarget(1.0);

        self.opacity.retarget(1.0);

    }

    pub const fn exit_slide(to_x: f32, to_y: f32, interp: Interp) -> Self {

        Self {

            class: AnimClass::Exit,

            translate_x: channel(0.0, to_x, interp),

            translate_y: channel(0.0, to_y, interp),

            scale_x: channel(1.0, 1.0, interp),

            scale_y: channel(1.0, 1.0, interp),

            opacity: channel(1.0, 1.0, interp),

        }

    }

    pub fn tick(&mut self, dt: f32) {

        self.translate_x.tick(dt);

        self.translate_y.tick(dt);

        self.scale_x.tick(dt);

        self.scale_y.tick(dt);

        self.opacity.tick(dt);

    }

    pub const fn is_finished(&self) -> bool {

        self.translate_x.is_finished()

            && self.translate_y.is_finished()

            && self.scale_x.is_finished()

            && self.scale_y.is_finished()

            && self.opacity.is_finished()

    }

    pub const fn current_transform(&self) -> FlipTransform {

        FlipTransform {

            translate_x: self.translate_x.current,

            translate_y: self.translate_y.current,

            scale_x: self.scale_x.current,

            scale_y: self.scale_y.current,

        }

    }

    pub const fn current_opacity(&self) -> f32 {

        self.opacity.current

    }

    pub fn retarget_move(&mut self, flip: FlipTransform) {

        self.translate_x.retarget(0.0);

        self.translate_y.retarget(0.0);

        self.scale_x.retarget(1.0);

        self.scale_y.retarget(1.0);

        self.translate_x.current += flip.translate_x;

        self.translate_y.current += flip.translate_y;

    }

const fn channel(from: f32, to: f32, interp: Interp) -> AnimChannel {

    match interp {

        Interp::Curve { function, duration_secs } => {

            AnimChannel::curve(from, to, function, duration_secs)

        Interp::Spring(spring) => AnimChannel::spring(from, to, spring),

}

    pub const fn new() -> Self {

        Self { active: BTreeMap::new() }

    }

    pub fn len(&self) -> usize {

        self.active.len()

    }

    pub fn is_empty(&self) -> bool {

        self.active.is_empty()

    }

    pub fn start_or_retarget_move(&mut self, key: AnimKey, flip: FlipTransform, interp: Interp) {

        if let Some(existing) = self.active.get_mut(&key) {

            existing.retarget_move(flip);

        } else {

            self.active.insert(key, ActiveAnim::move_from_flip(flip, interp));

        }

    }

    pub fn start_enter(&mut self, key: AnimKey, from: (f32, f32), interp: Interp) {

        self.active

            .entry(key)

            .or_insert_with(|| ActiveAnim::enter_slide(from.0, from.1, interp));

    }

    pub fn start_exit(&mut self, key: AnimKey, to: (f32, f32), interp: Interp) {

        match self.active.get_mut(&key) {

            Some(anim) => anim.retarget_presence(AnimClass::Exit, to.0, to.1),

            None => {

                self.active.insert(key, ActiveAnim::exit_slide(to.0, to.1, interp));

            }

    }

    pub fn get_mut(&mut self, key: AnimKey) -> Option<&mut ActiveAnim> {

        self.active.get_mut(&key)

    }

    pub fn get(&self, key: AnimKey) -> Option<&ActiveAnim> {

        self.active.get(&key)

    }

    pub fn iter(&self) -> impl Iterator<Item = (AnimKey, &ActiveAnim)> {

        self.active.iter().map(|(k, v)| (*k, v))

    }

    pub fn tick(&mut self, dt: f32) -> Vec<AnimKey> {

        let mut finished = Vec::new();

        for (key, anim) in &mut self.active {

            anim.tick(dt);

            if anim.is_finished() {

                finished.push(*key);

            }

        for key in &finished {

            self.active.remove(key);

        }

        finished

    }

pub fn correspondences_from_moves<F, L>(

    node_moves: &[NodeMove],

    new_node_data: &[NodeData],

    new_hierarchy: &[NodeHierarchyItem],

    first_rect: F,

    last_rect: L,

) -> Vec<(AnimKey, LogicalRect, LogicalRect)>

where

    F: Fn(NodeId) -> Option<LogicalRect>,

    L: Fn(NodeId) -> Option<LogicalRect>,

    let mut out = Vec::new();

    for m in node_moves {

        let (Some(first), Some(last)) = (first_rect(m.old_node_id), last_rect(m.new_node_id))

            continue;

        if m.new_node_id.index() >= new_node_data.len() {

        }

        let key = AnimKey(calculate_reconciliation_key(

            new_node_data,

            new_hierarchy,

            m.new_node_id,

        ));

        out.push((key, first, last));

    out

}

pub fn anim_keys_for_moves(

    node_moves: &[NodeMove],

    new_node_data: &[NodeData],

    new_hierarchy: &[NodeHierarchyItem],

) -> Vec<(AnimKey, NodeId)> {

    node_moves

        .iter()

        .filter(|m| m.new_node_id.index() < new_node_data.len())

        .map(|m| {

            (

                AnimKey(calculate_reconciliation_key(

                    new_node_data,

                    new_hierarchy,

                    m.new_node_id,

                )),

                m.new_node_id,

            )

        })

        .collect()

}

pub fn seed_moves<I>(manager: &mut AnimationManager, correspondences: I, interp: Interp) -> usize

where

    I: IntoIterator<Item = (AnimKey, LogicalRect, LogicalRect)>,

    let mut seeded = 0;

    for (key, first, last) in correspondences {

        let transform = flip(first, last);

        if transform.is_identity() {

            continue;

        }

        manager.start_or_retarget_move(key, transform, interp);

        seeded += 1;

    seeded

}

    fn spring_is_a_first_class_interpolation_function() {

        let f = AnimationInterpolationFunction::Spring(Spring::SNAPPY);

        assert!(f.is_spring());

        assert!(!AnimationInterpolationFunction::EaseInOut.is_spring());

        assert_eq!(f.get_curve(), AnimationInterpolationFunction::EaseInOut.get_curve());

        for t in [0.0_f32, 0.25, 0.5, 0.75, 1.0] {

            assert!((ease(f, t) - ease(AnimationInterpolationFunction::EaseInOut, t)).abs() < 1e-6);

    }

    fn rect(x: f32, y: f32, w: f32, h: f32) -> LogicalRect {

        LogicalRect {

            origin: LogicalPosition::new(x, y),

            size: LogicalSize::new(w, h),

        }

    }

    fn flip_inverts_a_pure_translation() {

        let f = flip(rect(0.0, 0.0, 10.0, 10.0), rect(100.0, 50.0, 10.0, 10.0));

        assert_eq!(f.translate_x, -100.0);

        assert_eq!(f.translate_y, -50.0);

        assert_eq!(f.scale_x, 1.0);

        assert_eq!(f.scale_y, 1.0);

    }

    fn flip_never_scales_a_size_change() {

        let f = flip(rect(0.0, 0.0, 50.0, 20.0), rect(0.0, 0.0, 100.0, 40.0));

        assert_eq!(f.scale_x, 1.0);

        assert_eq!(f.scale_y, 1.0);

        assert!(f.is_identity(), "same origin, changed size: nothing to animate");

    }

    fn flip_of_an_unchanged_rect_is_identity() {

        let r = rect(12.0, 34.0, 56.0, 78.0);

        assert!(flip(r, r).is_identity());

    }

    fn flip_never_produces_a_non_finite_scale() {

        let f = flip(rect(0.0, 0.0, 10.0, 10.0), rect(0.0, 0.0, 0.0, 0.0));

        assert!(f.scale_x.is_finite() && f.scale_y.is_finite());

        assert_eq!(f.scale_x, 1.0);

        assert_eq!(f.scale_y, 1.0);

    }

    fn a_spring_settles_at_its_target() {

        let mut c = AnimChannel::spring(0.0, 100.0, Spring::SMOOTH);

        for _ in 0..600 {

            c.tick(1.0 / 60.0);

            if c.is_finished() {

                break;

            }

        assert!(c.is_finished(), "spring did not settle within 10s");

        assert_eq!(c.current, 100.0);

        assert_eq!(c.velocity, 0.0);

    }

    fn a_curve_reaches_its_target_at_the_duration() {

        let mut c = AnimChannel::curve(0.0, 10.0, AnimationInterpolationFunction::Linear, 1.0);

        for _ in 0..60 {

            c.tick(1.0 / 60.0);

        }

        assert!(

            (c.current - 10.0).abs() < 0.01,

        c.tick(1.0 / 60.0);

        assert!(c.is_finished(), "curve did not finish one frame past its duration");

        assert_eq!(c.current, 10.0, "a finished curve must land exactly on `to`");

    }

    fn retarget_preserves_position_and_velocity() {

        let mut c = AnimChannel::spring(0.0, 100.0, Spring::SMOOTH);

        for _ in 0..10 {

            c.tick(1.0 / 60.0);

        }

        let value_before = c.current;

        let velocity_before = c.velocity;

        assert!(value_before > 0.0 && velocity_before > 0.0, "should be mid-flight");

        c.retarget(-50.0);

        assert_eq!(c.current, value_before, "retarget must not move the value");

        assert_eq!(c.velocity, velocity_before, "retarget must not discard velocity");

        assert_eq!(c.from, value_before);

        assert_eq!(c.to, -50.0);

        assert!(!c.is_finished());

    }

    fn retargeting_to_the_same_target_does_not_restart_the_clock() {

        let mut c = AnimChannel::curve(0.0, 10.0, AnimationInterpolationFunction::Linear, 1.0);

        c.tick(0.5);

        let elapsed = c.elapsed_secs;

        c.retarget(10.0);

        assert_eq!(c.elapsed_secs, elapsed, "a no-op retarget restarted the animation");

    }

    fn a_settled_spring_can_be_woken_by_a_retarget() {

        let mut c = AnimChannel::spring(0.0, 1.0, Spring::SNAPPY);

        for _ in 0..600 {

            c.tick(1.0 / 60.0);

            if c.is_finished() {

                break;

            }

        assert!(c.is_finished());

        c.retarget(0.0);

        assert!(!c.is_finished(), "retarget must un-finish a settled channel");

        c.tick(1.0 / 60.0);

        assert!(c.current < 1.0, "woken channel did not move toward the new target");

    }

    fn a_huge_frame_gap_cannot_fling_a_spring() {

        let mut c = AnimChannel::spring(0.0, 1.0, Spring::SNAPPY);

        c.tick(10.0);

        assert!(c.current.is_finite());

        assert!(c.current.abs() < 100.0, "clamping failed: {}", c.current);

    }

    fn zero_duration_curves_apply_instantly() {

        let mut c = AnimChannel::curve(0.0, 42.0, AnimationInterpolationFunction::Ease, 0.0);

        c.tick(0.0);

        assert!(c.is_finished());

        assert_eq!(c.current, 42.0);

    }

    fn easing_curves_are_pinned_at_both_ends() {

        for f in [

            AnimationInterpolationFunction::Linear,

            AnimationInterpolationFunction::Ease,

            AnimationInterpolationFunction::EaseIn,

            AnimationInterpolationFunction::EaseOut,

            AnimationInterpolationFunction::EaseInOut,

            assert_eq!(ease(f, 0.0), 0.0, "{f:?} did not start at 0");

            assert_eq!(ease(f, 1.0), 1.0, "{f:?} did not end at 1");

            assert_eq!(ease(f, -1.0), 0.0);

            assert_eq!(ease(f, 2.0), 1.0);

    }

    fn ease_in_starts_slower_than_linear_and_ease_out_starts_faster() {

        let t = 0.25;

        let linear = ease(AnimationInterpolationFunction::Linear, t);

        assert!(ease(AnimationInterpolationFunction::EaseIn, t) < linear);

        assert!(ease(AnimationInterpolationFunction::EaseOut, t) > linear);

    }

    fn damping_ratio_identifies_the_regime() {

        let critical = Spring { stiffness: 100.0, damping: 20.0, mass: 1.0 };

        assert!((critical.damping_ratio() - 1.0).abs() < 1e-5);

        assert!(Spring { stiffness: 100.0, damping: 5.0, mass: 1.0 }.damping_ratio() < 1.0);

        assert!(Spring { stiffness: 100.0, damping: 40.0, mass: 1.0 }.damping_ratio() > 1.0);

    }

    fn a_degenerate_spring_snaps_instead_of_dividing_by_zero() {

        let s = Spring { stiffness: 100.0, damping: 10.0, mass: 0.0 };

        let (value, velocity) = s.step(0.0, 5.0, 0.0, 1.0 / 60.0);

        assert_eq!(value, 5.0);

        assert_eq!(velocity, 0.0);

    }

    fn the_manager_retargets_instead_of_stacking() {

        let mut m = AnimationManager::new();

        let key = AnimKey(7);

        let interp = Interp::Spring(Spring::SMOOTH);

        m.start_or_retarget_move(key, flip(rect(0.0, 0.0, 10.0, 10.0), rect(100.0, 0.0, 10.0, 10.0)), interp);

        assert_eq!(m.len(), 1);

        for _ in 0..10 {

            m.tick(1.0 / 60.0);

        }

        let mid = m.get(key).expect("still animating").current_transform();

        m.start_or_retarget_move(key, flip(rect(0.0, 0.0, 10.0, 10.0), rect(200.0, 0.0, 10.0, 10.0)), interp);

        assert_eq!(m.len(), 1, "retarget created a second animation");

        let after = m.get(key).expect("still animating").current_transform();

        assert_ne!(after.translate_x, mid.translate_x, "retarget did not fold in the new offset");

    }

    fn the_manager_reports_and_drops_finished_animations() {

        let mut m = AnimationManager::new();

        m.start_enter(AnimKey(1), (-120.0, 0.0), Interp::Curve {

            function: AnimationInterpolationFunction::Linear,

            duration_secs: 0.1,

        });

        assert_eq!(m.len(), 1);

        let mut finished = Vec::new();

        for _ in 0..20 {

            finished = m.tick(1.0 / 60.0);

            if !finished.is_empty() {

                break;

            }

        assert_eq!(finished, alloc::vec![AnimKey(1)]);

        assert!(m.is_empty(), "finished animation was not dropped");

    }

    fn an_exit_replaces_an_in_flight_move() {

        let mut m = AnimationManager::new();

        let key = AnimKey(3);

        let interp = Interp::Spring(Spring::SMOOTH);

        m.start_or_retarget_move(key, flip(rect(0.0, 0.0, 10.0, 10.0), rect(50.0, 0.0, 10.0, 10.0)), interp);

        assert_eq!(m.get(key).map(|a| a.class), Some(AnimClass::Move));

        m.start_exit(key, (-120.0, 0.0), interp);

        assert_eq!(m.get(key).map(|a| a.class), Some(AnimClass::Exit));

        assert_eq!(m.len(), 1);

    }

    fn the_anim_key_survives_a_node_id_change() {

        let tree_a = [NodeData::create_div().with_key("hero")];

        let tree_b = [

            NodeData::create_div().with_key("spacer"),

            NodeData::create_div().with_key("hero"),

        ];

        let key_a = AnimKey(calculate_reconciliation_key(&tree_a, &[], NodeId::ZERO));

        let key_b = AnimKey(calculate_reconciliation_key(

            &tree_b,

            &[],

            NodeId::new(1),

        ));

        assert_eq!(key_a, key_b, "the same keyed node got two different AnimKeys");

        let other = AnimKey(calculate_reconciliation_key(&tree_b, &[], NodeId::ZERO));

        assert_ne!(key_a, other);

    }

    fn correspondences_drop_pairs_with_no_geometry() {

        let new_data = [NodeData::create_div().with_key("a"), NodeData::create_div().with_key("b")];

        let moves = [

            NodeMove { old_node_id: NodeId::ZERO, new_node_id: NodeId::ZERO },

            NodeMove { old_node_id: NodeId::new(1), new_node_id: NodeId::new(1) },

        ];

        let r = rect(0.0, 0.0, 10.0, 10.0);

        let out = correspondences_from_moves(

            &moves,

            &new_data,

            &[],

            |id| (id == NodeId::ZERO).then_some(r),   // only node 0 existed before

            |_| Some(rect(5.0, 0.0, 10.0, 10.0)),

        assert_eq!(out.len(), 1, "a node with no previous geometry has nothing to fly from");

    }

    fn seed_moves_skips_nodes_that_did_not_move() {

        let mut m = AnimationManager::new();

        let stayed = rect(0.0, 0.0, 10.0, 10.0);

        let moved_first = rect(0.0, 0.0, 10.0, 10.0);

        let moved_last = rect(40.0, 0.0, 10.0, 10.0);

        let seeded = seed_moves(

            &mut m,

            [

                (AnimKey(1), stayed, stayed),

                (AnimKey(2), moved_first, moved_last),

            ],

            Interp::Spring(Spring::SMOOTH),

        assert_eq!(seeded, 1, "only the node that moved should animate");

        assert!(m.get(AnimKey(1)).is_none());

        assert!(m.get(AnimKey(2)).is_some());

    }

    fn seed_moves_retargets_a_key_that_is_already_animating() {

        let mut m = AnimationManager::new();

        let interp = Interp::Spring(Spring::SMOOTH);

        seed_moves(

            &mut m,

            [(AnimKey(9), rect(0.0, 0.0, 10.0, 10.0), rect(50.0, 0.0, 10.0, 10.0))],

            interp,

        for _ in 0..5 {

            m.tick(1.0 / 60.0);

        }

        let seeded = seed_moves(

            &mut m,

            [(AnimKey(9), rect(0.0, 0.0, 10.0, 10.0), rect(90.0, 0.0, 10.0, 10.0))],

            interp,

        assert_eq!(seeded, 1);

        assert_eq!(m.len(), 1, "a second produce stacked a second animation");

    }

    fn an_enter_does_not_clobber_an_animation_already_in_flight() {

        let mut m = AnimationManager::new();

        let key = AnimKey(5);

        let interp = Interp::Spring(Spring::SMOOTH);

        m.start_exit(key, (-120.0, 0.0), interp);

        m.start_enter(key, (-120.0, 0.0), interp);

        assert_eq!(m.get(key).map(|a| a.class), Some(AnimClass::Exit));

    }