Skip to main content

day_core/
tween.rs

1// Copyright © The Daybrite Project
2// SPDX-License-Identifier: MPL-2.0
3
4//! Interpolation for self-drawn content (docs/tween.md): what a canvas animation needs to say
5//! what the in-between picture is.
6//!
7//! [`with_animation`](crate::with_animation) hands native widgets *intent* and lets each toolkit
8//! animate on its own compositor. A canvas has no compositor to hand anything to: it re-records a
9//! display list, so something has to decide, frame by frame, what the in-between picture is.
10//! [`motion`](crate::motion) moves the values ([`Animated`](crate::motion::Animated),
11//! [`Animation`](crate::motion::Animation)); this module says what lies between two of them:
12//!
13//! * [`Lerp`]: how a value moves between two states. Numbers, points, rects, tuples, arrays,
14//!   vectors, and colors (blended in OKLab, so a heat map's mid-transition cells are the colors in
15//!   between rather than a muddy detour through gray).
16//! * [`stagger`]: one [`AnimSpec`] per item, each delayed a little more, for sequences (bars
17//!   rising left to right).
18//! * [`Pairs`]: the step before either when what changed is a *collection*. It matches the
19//!   items of two states by key, gives the ones only one side has somewhere to come from or go
20//!   to, and interpolates the lot, so bars that trade places slide and a new one grows out of
21//!   its neighbor instead of the whole picture cross-fading.
22//!
23//! An `AnimSpec`'s timeline as a function of elapsed time is [`AnimSpec::sample`].
24
25use std::collections::{HashMap, VecDeque};
26use std::hash::Hash;
27
28use day_spec::{Angle, AnimSpec, Color, Ink, Palette, Point, Rect, Size};
29
30/// A value that can be interpolated: `a.lerp(&b, 0.0)` is `a`, `a.lerp(&b, 1.0)` is `b`.
31///
32/// `t` may leave `0..=1`: an under-damped spring overshoots, and a numeric value follows it past
33/// the target and back. Implementations that cannot extrapolate (a color's alpha, a count) clamp
34/// the parts that must stay in range.
35pub trait Lerp: Clone {
36    #[must_use]
37    fn lerp(&self, to: &Self, t: f64) -> Self;
38}
39
40/// `a + (b - a) * t`, the scalar every other implementation is built from.
41#[inline]
42#[must_use]
43pub fn lerp(a: f64, b: f64, t: f64) -> f64 {
44    a + (b - a) * t
45}
46
47impl Lerp for f64 {
48    fn lerp(&self, to: &Self, t: f64) -> Self {
49        lerp(*self, *to, t)
50    }
51}
52
53impl Lerp for f32 {
54    fn lerp(&self, to: &Self, t: f64) -> Self {
55        lerp(f64::from(*self), f64::from(*to), t) as f32
56    }
57}
58
59impl Lerp for Point {
60    fn lerp(&self, to: &Self, t: f64) -> Self {
61        Point::new(lerp(self.x, to.x, t), lerp(self.y, to.y, t))
62    }
63}
64
65impl Lerp for Size {
66    fn lerp(&self, to: &Self, t: f64) -> Self {
67        Size::new(
68            lerp(self.width, to.width, t).max(0.0),
69            lerp(self.height, to.height, t).max(0.0),
70        )
71    }
72}
73
74impl Lerp for Rect {
75    fn lerp(&self, to: &Self, t: f64) -> Self {
76        Rect {
77            origin: self.origin.lerp(&to.origin, t),
78            size: self.size.lerp(&to.size, t),
79        }
80    }
81}
82
83/// Colors blend in OKLab (Björn Ottosson's perceptual space), alpha linearly: the midpoint of blue
84/// and yellow is a clean mid-lightness color rather than sRGB's dim gray, and a sequential scale's
85/// in-between cells read as in-between values. The endpoints are exact.
86impl Lerp for Color {
87    fn lerp(&self, to: &Self, t: f64) -> Self {
88        mix_oklab(*self, *to, t)
89    }
90}
91
92/// An angle moves along the number line, not the short way round: from 350° to 10° is a turn of
93/// 340° backwards, which is what a spinner counting down means. Normalize first for the short arc.
94impl Lerp for Angle {
95    fn lerp(&self, to: &Self, t: f64) -> Self {
96        Angle::deg(lerp(self.degrees(), to.degrees(), t))
97    }
98}
99
100/// Inks blend per appearance (docs/color.md "Inks in motion"). Two fixed colors or two light/dark
101/// pairs blend each side in OKLab, so the in-between value still follows an appearance switch. A
102/// [`SystemColor`](day_spec::SystemColor) role has no color of its own until the toolkit answers
103/// it, so a blend that involves one resolves the role against [`Palette::both`] and blends the
104/// pair.
105/// The endpoints are exact: `t == 1` is `to` itself, role and all, so the settled value follows
106/// the platform again.
107impl Lerp for Ink {
108    #[expect(
109        clippy::float_cmp,
110        reason = "the exact endpoints are the contract, so exact comparison is the point"
111    )]
112    fn lerp(&self, to: &Self, t: f64) -> Self {
113        if t == 0.0 {
114            return *self;
115        }
116        if t == 1.0 {
117            return *to;
118        }
119        if let (Ink::Fixed(a), Ink::Fixed(b)) = (self, to) {
120            return Ink::Fixed(mix_oklab(*a, *b, t));
121        }
122        let (light, dark) = Palette::both();
123        let (a_light, a_dark) = self.pair(&light, &dark);
124        let (b_light, b_dark) = to.pair(&light, &dark);
125        Ink::adaptive(mix_oklab(a_light, b_light, t), mix_oklab(a_dark, b_dark, t))
126    }
127}
128
129impl<A: Lerp, B: Lerp> Lerp for (A, B) {
130    fn lerp(&self, to: &Self, t: f64) -> Self {
131        (self.0.lerp(&to.0, t), self.1.lerp(&to.1, t))
132    }
133}
134
135impl<A: Lerp, B: Lerp, C: Lerp> Lerp for (A, B, C) {
136    fn lerp(&self, to: &Self, t: f64) -> Self {
137        (
138            self.0.lerp(&to.0, t),
139            self.1.lerp(&to.1, t),
140            self.2.lerp(&to.2, t),
141        )
142    }
143}
144
145impl<T: Lerp, const N: usize> Lerp for [T; N] {
146    fn lerp(&self, to: &Self, t: f64) -> Self {
147        std::array::from_fn(|i| self[i].lerp(&to[i], t))
148    }
149}
150
151/// Element-wise over the common prefix; the target's extra elements (or the source's missing ones)
152/// take the target's values, so a series that grew draws its new tail where it is headed. A caller
153/// that wants entering elements to grow in matches them up first; `Vec` has no idea what they mean.
154impl<T: Lerp> Lerp for Vec<T> {
155    fn lerp(&self, to: &Self, t: f64) -> Self {
156        to.iter()
157            .enumerate()
158            .map(|(i, b)| match self.get(i) {
159                Some(a) => a.lerp(b, t),
160                None => b.clone(),
161            })
162            .collect()
163    }
164}
165
166/// Both present: interpolate. Otherwise there is nothing to move between, so the value switches at
167/// the midpoint.
168impl<T: Lerp> Lerp for Option<T> {
169    fn lerp(&self, to: &Self, t: f64) -> Self {
170        match (self, to) {
171            (Some(a), Some(b)) => Some(a.lerp(b, t)),
172            _ if t < 0.5 => self.clone(),
173            _ => to.clone(),
174        }
175    }
176}
177
178// --- OKLab ------------------------------------------------------------------------------------
179
180fn to_linear(c: f64) -> f64 {
181    if c <= 0.04045 {
182        c / 12.92
183    } else {
184        ((c + 0.055) / 1.055).powf(2.4)
185    }
186}
187
188fn to_srgb(c: f64) -> f64 {
189    if c <= 0.003_130_8 {
190        c * 12.92
191    } else {
192        1.055 * c.powf(1.0 / 2.4) - 0.055
193    }
194}
195
196fn oklab(c: Color) -> [f64; 3] {
197    let (r, g, b) = (to_linear(c.r), to_linear(c.g), to_linear(c.b));
198    let l = (0.412_221_470_8 * r + 0.536_332_536_3 * g + 0.051_445_992_9 * b).cbrt();
199    let m = (0.211_903_498_2 * r + 0.680_699_545_1 * g + 0.107_396_956_6 * b).cbrt();
200    let s = (0.088_302_461_9 * r + 0.281_718_837_6 * g + 0.629_978_700_5 * b).cbrt();
201    [
202        0.210_454_255_3 * l + 0.793_617_785_0 * m - 0.004_072_046_8 * s,
203        1.977_998_495_1 * l - 2.428_592_205_0 * m + 0.450_593_709_9 * s,
204        0.025_904_037_1 * l + 0.782_771_766_2 * m - 0.808_675_766_0 * s,
205    ]
206}
207
208fn from_oklab([l, a, b]: [f64; 3], alpha: f64) -> Color {
209    let l_ = l + 0.396_337_777_4 * a + 0.215_803_757_3 * b;
210    let m_ = l - 0.105_561_345_8 * a - 0.063_854_172_8 * b;
211    let s_ = l - 0.089_484_177_5 * a - 1.291_485_548_0 * b;
212    let (l3, m3, s3) = (l_ * l_ * l_, m_ * m_ * m_, s_ * s_ * s_);
213    let r = 4.076_741_662_1 * l3 - 3.307_711_591_3 * m3 + 0.230_969_929_2 * s3;
214    let g = -1.268_438_004_6 * l3 + 2.609_757_401_1 * m3 - 0.341_319_396_5 * s3;
215    let bl = -0.004_196_086_3 * l3 - 0.703_418_614_7 * m3 + 1.707_614_701_0 * s3;
216    let ch = |v: f64| to_srgb(v.max(0.0)).clamp(0.0, 1.0);
217    Color::rgba(ch(r), ch(g), ch(bl), alpha.clamp(0.0, 1.0))
218}
219
220/// Blend two colors in OKLab by `t`, alpha linearly. `t` outside `0..=1` extrapolates the
221/// lightness and hue axes and clamps the result into gamut.
222#[expect(
223    clippy::float_cmp,
224    reason = "exactly 0.0 and 1.0 select the endpoints unchanged"
225)]
226pub fn mix_oklab(a: Color, b: Color, t: f64) -> Color {
227    // The endpoints are the endpoints, not a round trip through two color spaces.
228    if t == 0.0 {
229        return a;
230    }
231    if t == 1.0 {
232        return b;
233    }
234    let (p, q) = (oklab(a), oklab(b));
235    from_oklab(
236        [
237            lerp(p[0], q[0], t),
238            lerp(p[1], q[1], t),
239            lerp(p[2], q[2], t),
240        ],
241        lerp(a.a, b.a, t),
242    )
243}
244
245// --- Staggering ------------------------------------------------------------------------------
246
247/// `spec`, delayed for item `index` of `count` so the items start `spread_ms` apart in total:
248/// the first starts on time, the last `spread_ms` later. Bars rising left to right, points popping
249/// in along a line: a sequence is one spec per item, and this is the arithmetic.
250pub fn stagger(spec: AnimSpec, index: usize, count: usize, spread_ms: u32) -> AnimSpec {
251    let step = if count > 1 {
252        f64::from(spread_ms) / (count - 1) as f64
253    } else {
254        0.0
255    };
256    AnimSpec {
257        delay_ms: spec.delay_ms + (step * index as f64).round() as u32,
258        ..spec
259    }
260}
261
262// ---------------------------------------------------------------------------
263// Pairs: matching two collections
264// ---------------------------------------------------------------------------
265
266/// Which side of a change an item of a [`Pairs`] is on.
267#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
268pub enum Change {
269    /// In both states: it moves from where it was to where it is.
270    Kept,
271    /// Only in the new state: it arrives from a stand-in the caller chose.
272    Entering,
273    /// Only in the old state: it departs toward a stand-in the caller chose, and is gone once the
274    /// transition ends.
275    Leaving,
276}
277
278/// One item of a transition between two collections: where it starts, where it ends, and why.
279#[derive(Clone, Debug, PartialEq)]
280pub struct Pair<T> {
281    pub from: T,
282    pub to: T,
283    pub change: Change,
284}
285
286impl<T: Lerp> Pair<T> {
287    /// The item `t` of the way along.
288    pub fn at(&self, t: f64) -> T {
289        self.from.lerp(&self.to, t)
290    }
291}
292
293/// Two states of a collection, matched item by item, ready to be sampled at any `t`.
294///
295/// Built once per change, sampled once per frame: matching is the part that costs something and
296/// it does not depend on `t`. [`Pairs::by_key`] matches by an identity the caller derives; a
297/// caller whose own rules already know what moved where (a sliding-tile game knows which tiles
298/// merged) collects its [`Pair`]s directly (`Pairs: FromIterator`).
299///
300/// ```
301/// use day_core::tween::{Change, Lerp, Pairs, lerp};
302///
303/// #[derive(Clone, Debug, PartialEq)]
304/// struct Bar { name: &'static str, height: f64 }
305///
306/// impl Lerp for Bar {
307///     fn lerp(&self, to: &Self, t: f64) -> Self {
308///         Bar { name: to.name, height: lerp(self.height, to.height, t) }
309///     }
310/// }
311///
312/// let bar = |name, height| Bar { name, height };
313/// // "b" shrinks, "c" grows out of nothing, "a" collapses away.
314/// let before = [bar("a", 3.0), bar("b", 5.0)];
315/// let after = [bar("b", 1.0), bar("c", 4.0)];
316/// let pairs = Pairs::by_key(&before, &after, |b| b.name, |b, _| bar(b.name, 0.0));
317/// assert_eq!(pairs.at(0.5), vec![bar("b", 3.0), bar("c", 2.0), bar("a", 1.5)]);
318/// assert_eq!(pairs[2].change, Change::Leaving);
319/// ```
320#[derive(Clone, Debug, PartialEq)]
321pub struct Pairs<T> {
322    items: Vec<Pair<T>>,
323}
324
325impl<T> Default for Pairs<T> {
326    fn default() -> Self {
327        Pairs { items: Vec::new() }
328    }
329}
330
331impl<T: Clone> Pairs<T> {
332    /// Match `from` with `to` by `key`.
333    ///
334    /// * An item whose key is on both sides is [`Change::Kept`]. Keys may repeat: the *n*th item
335    ///   with a key on one side matches the *n*th with that key on the other, so identical tokens
336    ///   (three red gems in a column) pair up in order rather than all with the first.
337    /// * An item only in `to` is [`Change::Entering`]; `absent(item, Change::Entering)` says where
338    ///   it starts. An item only in `from` is [`Change::Leaving`]; `absent(item, Change::Leaving)`
339    ///   says where it ends. That stand-in is the whole of what entering and leaving mean: grown
340    ///   from a baseline, faded out, slid in from a neighbor. The caller decides; the match does
341    ///   not.
342    ///
343    /// The result is in `to`'s order, then the leaving items in `from`'s order, so a renderer
344    /// drawing in sequence draws the arriving picture's order, with what is departing on top.
345    pub fn by_key<K: Eq + Hash>(
346        from: &[T],
347        to: &[T],
348        mut key: impl FnMut(&T) -> K,
349        mut absent: impl FnMut(&T, Change) -> T,
350    ) -> Self {
351        let mut waiting: HashMap<K, VecDeque<usize>> = HashMap::with_capacity(from.len());
352        for (i, item) in from.iter().enumerate() {
353            waiting.entry(key(item)).or_default().push_back(i);
354        }
355        let mut matched = vec![false; from.len()];
356        let mut items = Vec::with_capacity(from.len().max(to.len()));
357        for item in to {
358            let found = waiting.get_mut(&key(item)).and_then(VecDeque::pop_front);
359            items.push(match found {
360                Some(i) => {
361                    matched[i] = true;
362                    Pair {
363                        from: from[i].clone(),
364                        to: item.clone(),
365                        change: Change::Kept,
366                    }
367                }
368                None => Pair {
369                    from: absent(item, Change::Entering),
370                    to: item.clone(),
371                    change: Change::Entering,
372                },
373            });
374        }
375        for (item, _) in from.iter().zip(&matched).filter(|(_, m)| !**m) {
376            items.push(Pair {
377                from: item.clone(),
378                to: absent(item, Change::Leaving),
379                change: Change::Leaving,
380            });
381        }
382        Pairs { items }
383    }
384}
385
386impl<T> Pairs<T> {
387    /// Every item `t` of the way along, in order, through `f`: for items whose in-between depends
388    /// on more than the two ends (a chart mark needs both charts' scales to place itself).
389    pub fn at_with<U>(&self, t: f64, mut f: impl FnMut(&Pair<T>, f64) -> U) -> Vec<U> {
390        self.items.iter().map(|p| f(p, t)).collect()
391    }
392
393    /// Each item at its own progress: `progress(index, pair)` gives the `t` for that item, for
394    /// sequences that do not move in lockstep (cards dealt one after another, see [`stagger`]).
395    pub fn at_each<U>(
396        &self,
397        mut progress: impl FnMut(usize, &Pair<T>) -> f64,
398        mut f: impl FnMut(&Pair<T>, f64) -> U,
399    ) -> Vec<U> {
400        self.items
401            .iter()
402            .enumerate()
403            .map(|(i, p)| f(p, progress(i, p)))
404            .collect()
405    }
406
407    /// The arriving state: every item that is not leaving, at its end. What to draw once the
408    /// transition is over.
409    pub fn settled(&self) -> impl Iterator<Item = &T> {
410        self.items
411            .iter()
412            .filter(|p| p.change != Change::Leaving)
413            .map(|p| &p.to)
414    }
415
416    /// How many items of each kind of [`Change`] there are: `(kept, entering, leaving)`.
417    #[must_use]
418    pub fn counts(&self) -> (usize, usize, usize) {
419        self.items
420            .iter()
421            .fold((0, 0, 0), |(k, e, l), p| match p.change {
422                Change::Kept => (k + 1, e, l),
423                Change::Entering => (k, e + 1, l),
424                Change::Leaving => (k, e, l + 1),
425            })
426    }
427
428    pub fn iter(&self) -> std::slice::Iter<'_, Pair<T>> {
429        self.items.iter()
430    }
431
432    #[must_use]
433    pub fn len(&self) -> usize {
434        self.items.len()
435    }
436
437    #[must_use]
438    pub fn is_empty(&self) -> bool {
439        self.items.is_empty()
440    }
441}
442
443impl<T: Lerp> Pairs<T> {
444    /// Every item `t` of the way along, in order. Leaving items are included until the caller
445    /// stops sampling: at `t = 1` they sit at their stand-ins.
446    #[must_use]
447    pub fn at(&self, t: f64) -> Vec<T> {
448        self.items.iter().map(|p| p.at(t)).collect()
449    }
450}
451
452impl<T> std::ops::Index<usize> for Pairs<T> {
453    type Output = Pair<T>;
454    fn index(&self, i: usize) -> &Pair<T> {
455        &self.items[i]
456    }
457}
458
459impl<T> FromIterator<Pair<T>> for Pairs<T> {
460    fn from_iter<I: IntoIterator<Item = Pair<T>>>(iter: I) -> Self {
461        Pairs {
462            items: iter.into_iter().collect(),
463        }
464    }
465}
466
467impl<T> IntoIterator for Pairs<T> {
468    type Item = Pair<T>;
469    type IntoIter = std::vec::IntoIter<Pair<T>>;
470    fn into_iter(self) -> Self::IntoIter {
471        self.items.into_iter()
472    }
473}
474
475impl<'a, T> IntoIterator for &'a Pairs<T> {
476    type Item = &'a Pair<T>;
477    type IntoIter = std::slice::Iter<'a, Pair<T>>;
478    fn into_iter(self) -> Self::IntoIter {
479        self.items.iter()
480    }
481}
482
483#[cfg(test)]
484mod tests {
485    use super::*;
486    use std::cell::Cell;
487
488    fn near(a: f64, b: f64) -> bool {
489        (a - b).abs() < 1e-9
490    }
491
492    #[test]
493    fn stagger_spreads_delays_across_the_items() {
494        let s = AnimSpec::linear(300);
495        assert_eq!(stagger(s, 0, 5, 400).delay_ms, 0);
496        assert_eq!(stagger(s, 2, 5, 400).delay_ms, 200);
497        assert_eq!(stagger(s, 4, 5, 400).delay_ms, 400);
498        assert_eq!(stagger(s, 0, 1, 400).delay_ms, 0);
499    }
500
501    #[test]
502    fn values_interpolate_and_colors_keep_their_endpoints() {
503        assert!(near(10.0.lerp(&20.0, 0.25), 12.5));
504        let r = Rect::new(0.0, 0.0, 10.0, 10.0).lerp(&Rect::new(10.0, 10.0, 30.0, 10.0), 0.5);
505        assert_eq!(r, Rect::new(5.0, 5.0, 20.0, 10.0));
506        let (blue, yellow) = (Color::rgb(0.0, 0.0, 1.0), Color::rgb(1.0, 1.0, 0.0));
507        let a = blue.lerp(&yellow, 0.0);
508        let b = blue.lerp(&yellow, 1.0);
509        assert_eq!(a, blue);
510        assert_eq!(b, yellow);
511        // The OKLab midpoint of blue and yellow is lighter than sRGB's gray (0.5, 0.5, 0.5).
512        let mid = blue.lerp(&yellow, 0.5);
513        assert!(mid.r + mid.g + mid.b > 1.6, "{mid:?}");
514        assert_eq!(
515            vec![0.0, 1.0].lerp(&vec![2.0, 3.0, 9.0], 0.5),
516            vec![1.0, 2.0, 9.0]
517        );
518        assert_eq!(Some(1.0).lerp(&None, 0.4), Some(1.0));
519        assert_eq!(Some(1.0).lerp(&None, 0.6), None);
520    }
521
522    // --- Pairs -----------------------------------------------------------------------------
523
524    /// A keyed value, the shape most callers pair: an identity and something that moves.
525    #[derive(Clone, Debug, PartialEq)]
526    struct Item {
527        key: &'static str,
528        at: f64,
529    }
530
531    impl Lerp for Item {
532        fn lerp(&self, to: &Self, t: f64) -> Self {
533            Item {
534                key: to.key,
535                at: lerp(self.at, to.at, t),
536            }
537        }
538    }
539
540    fn item(key: &'static str, at: f64) -> Item {
541        Item { key, at }
542    }
543
544    /// Stand-ins at zero, the way a bar grows from its baseline.
545    fn from_zero(i: &Item, _: Change) -> Item {
546        item(i.key, 0.0)
547    }
548
549    fn by_key(from: &[Item], to: &[Item]) -> Pairs<Item> {
550        Pairs::by_key(from, to, |i| i.key, from_zero)
551    }
552
553    fn changes(p: &Pairs<Item>) -> Vec<(&'static str, Change)> {
554        p.iter().map(|p| (p.to.key, p.change)).collect()
555    }
556
557    #[test]
558    fn items_are_kept_entering_or_leaving_in_arriving_order_then_leaving() {
559        let p = by_key(
560            &[item("a", 1.0), item("b", 2.0), item("c", 3.0)],
561            &[item("c", 30.0), item("d", 40.0), item("a", 10.0)],
562        );
563        assert_eq!(
564            changes(&p),
565            vec![
566                ("c", Change::Kept),
567                ("d", Change::Entering),
568                ("a", Change::Kept),
569                ("b", Change::Leaving),
570            ]
571        );
572        assert_eq!(p.counts(), (2, 1, 1));
573        // A kept item starts where it was, an entering one at its stand-in, a leaving one where
574        // it was and ends at its stand-in.
575        assert_eq!((p[0].from.at, p[0].to.at), (3.0, 30.0));
576        assert_eq!((p[1].from.at, p[1].to.at), (0.0, 40.0));
577        assert_eq!((p[2].from.at, p[2].to.at), (1.0, 10.0));
578        assert_eq!((p[3].from.at, p[3].to.at), (2.0, 0.0));
579    }
580
581    #[test]
582    fn the_stand_in_is_asked_for_with_the_item_and_its_side() {
583        let mut asked = Vec::new();
584        let p = Pairs::by_key(
585            &[item("gone", 5.0), item("stays", 1.0)],
586            &[item("stays", 2.0), item("new", 7.0)],
587            |i| i.key,
588            |i, change| {
589                asked.push((i.key, i.at, change));
590                // Entering items come from below their target, leaving ones go above.
591                match change {
592                    Change::Entering => item(i.key, i.at - 100.0),
593                    Change::Leaving => item(i.key, i.at + 100.0),
594                    Change::Kept => unreachable!("a kept item has both ends"),
595                }
596            },
597        );
598        assert_eq!(
599            asked,
600            vec![
601                ("new", 7.0, Change::Entering),
602                ("gone", 5.0, Change::Leaving)
603            ]
604        );
605        assert_eq!(p[1].from.at, -93.0);
606        assert_eq!(p[2].to.at, 105.0);
607    }
608
609    #[test]
610    fn repeated_keys_pair_in_order_and_the_surplus_enters_or_leaves() {
611        // Three red gems become two: the first two pair with the first two, the third leaves.
612        let p = by_key(
613            &[item("red", 1.0), item("red", 2.0), item("red", 3.0)],
614            &[item("red", 10.0), item("red", 20.0)],
615        );
616        assert_eq!(p.counts(), (2, 0, 1));
617        assert_eq!((p[0].from.at, p[1].from.at), (1.0, 2.0));
618        assert_eq!((p[2].from.at, p[2].change), (3.0, Change::Leaving));
619        // And the other way: the extra one enters.
620        let p = by_key(&[item("red", 1.0)], &[item("red", 10.0), item("red", 20.0)]);
621        assert_eq!(p.counts(), (1, 1, 0));
622        assert_eq!((p[0].from.at, p[1].change), (1.0, Change::Entering));
623    }
624
625    #[test]
626    fn an_empty_side_makes_everything_enter_or_leave() {
627        let some = [item("a", 1.0), item("b", 2.0)];
628        let arriving = by_key(&[], &some);
629        assert_eq!(arriving.counts(), (0, 2, 0));
630        assert_eq!(arriving.at(0.0), vec![item("a", 0.0), item("b", 0.0)]);
631        let departing = by_key(&some, &[]);
632        assert_eq!(departing.counts(), (0, 0, 2));
633        assert_eq!(departing.at(1.0), vec![item("a", 0.0), item("b", 0.0)]);
634        assert!(by_key(&[], &[]).is_empty());
635        assert!(Pairs::<Item>::default().is_empty());
636    }
637
638    #[test]
639    fn a_permutation_keeps_everything_and_follows_the_new_order() {
640        let from = [item("a", 0.0), item("b", 1.0), item("c", 2.0)];
641        let to = [item("c", 0.0), item("a", 1.0), item("b", 2.0)];
642        let p = by_key(&from, &to);
643        assert_eq!(p.counts(), (3, 0, 0));
644        assert_eq!(
645            p.at(0.0),
646            vec![item("c", 2.0), item("a", 0.0), item("b", 1.0)]
647        );
648        assert_eq!(p.at(1.0), to.to_vec());
649    }
650
651    #[test]
652    fn sampling_runs_from_the_old_state_to_the_new_one_and_past_it() {
653        let p = by_key(&[item("a", 0.0), item("b", 8.0)], &[item("a", 10.0)]);
654        assert_eq!(p.at(0.0), vec![item("a", 0.0), item("b", 8.0)]);
655        assert_eq!(p.at(0.25), vec![item("a", 2.5), item("b", 6.0)]);
656        // At the end the leaving item sits at its stand-in; the caller drops it when done.
657        assert_eq!(p.at(1.0), vec![item("a", 10.0), item("b", 0.0)]);
658        // A spring's overshoot carries the values past their targets.
659        assert_eq!(p.at(1.1)[0].at, 11.0);
660        assert_eq!(
661            p.settled().cloned().collect::<Vec<_>>(),
662            vec![item("a", 10.0)]
663        );
664    }
665
666    #[test]
667    fn at_with_hands_each_pair_and_t_to_the_caller() {
668        let p = by_key(&[item("a", 0.0)], &[item("a", 4.0), item("b", 2.0)]);
669        let got = p.at_with(0.5, |pair, t| (pair.change, pair.at(t).at));
670        assert_eq!(got, vec![(Change::Kept, 2.0), (Change::Entering, 1.0)]);
671    }
672
673    #[test]
674    fn at_each_gives_every_item_its_own_progress() {
675        // Dealt one after another: item i starts i quarters later.
676        let to: Vec<Item> = ["a", "b", "c"].iter().map(|k| item(k, 10.0)).collect();
677        let p = by_key(&[], &to);
678        let elapsed = 0.5;
679        let got = p.at_each(
680            |i, _| ((elapsed - i as f64 * 0.25) / 0.5).clamp(0.0, 1.0),
681            |pair, t| pair.at(t).at,
682        );
683        assert_eq!(got, vec![10.0, 5.0, 0.0]);
684    }
685
686    #[test]
687    fn pairs_collected_directly_may_share_a_destination() {
688        // Two tiles merging into one cell: the rules know it, and a key match could not say it.
689        let p: Pairs<Point> = [
690            (Point::new(0.0, 0.0), Point::new(3.0, 0.0)),
691            (Point::new(1.0, 0.0), Point::new(3.0, 0.0)),
692        ]
693        .into_iter()
694        .map(|(from, to)| Pair {
695            from,
696            to,
697            change: Change::Kept,
698        })
699        .collect();
700        assert_eq!(p.len(), 2);
701        let mid = p.at(0.5);
702        assert_eq!(mid, vec![Point::new(1.5, 0.0), Point::new(2.0, 0.0)]);
703        assert_eq!(p.at(1.0), vec![Point::new(3.0, 0.0); 2]);
704    }
705
706    #[test]
707    fn pairs_of_library_types_interpolate_with_their_own_lerp() {
708        let (red, blue) = (Color::rgb(1.0, 0.0, 0.0), Color::rgb(0.0, 0.0, 1.0));
709        let from = [(1u8, Rect::new(0.0, 0.0, 10.0, 10.0), red)];
710        let to = [(1u8, Rect::new(20.0, 0.0, 10.0, 30.0), blue)];
711        let p = Pairs::by_key(
712            &from.map(|(_, r, c)| (r, c)),
713            &to.map(|(_, r, c)| (r, c)),
714            |_| 1u8,
715            |x, _| *x,
716        );
717        let (rect, color) = p.at(0.5)[0];
718        assert_eq!(rect, Rect::new(10.0, 0.0, 10.0, 20.0));
719        assert!(color != red && color != blue);
720        assert_eq!(p.at(1.0)[0].1, blue);
721    }
722
723    #[test]
724    fn keys_are_derived_once_per_item() {
725        let calls = Cell::new(0);
726        let from = [item("a", 0.0), item("b", 0.0), item("c", 0.0)];
727        let to = [item("b", 0.0), item("d", 0.0)];
728        let _ = Pairs::by_key(
729            &from,
730            &to,
731            |i| {
732                calls.set(calls.get() + 1);
733                i.key
734            },
735            from_zero,
736        );
737        assert_eq!(calls.get(), from.len() + to.len());
738    }
739
740    #[test]
741    fn iteration_and_indexing_see_the_same_pairs() {
742        let p = by_key(&[item("a", 1.0)], &[item("a", 2.0), item("b", 3.0)]);
743        let by_ref: Vec<_> = (&p).into_iter().map(|p| p.to.key).collect();
744        let by_iter: Vec<_> = p.iter().map(|p| p.to.key).collect();
745        assert_eq!(by_ref, by_iter);
746        assert_eq!(p[1].to.key, "b");
747        let owned: Vec<Pair<Item>> = p.clone().into_iter().collect();
748        assert_eq!(owned.len(), p.len());
749        assert_eq!(owned[0], p[0]);
750    }
751
752    /// For random collections with repeated keys, the match accounts for every item exactly
753    /// once: each arriving item is the end of exactly one non-leaving pair (in its order), each
754    /// departing item the start of exactly one kept or leaving pair, and the number kept is the
755    /// size of the keys' multiset intersection.
756    #[test]
757    fn every_item_is_accounted_for_exactly_once() {
758        const KEYS: [&str; 5] = ["a", "b", "c", "d", "e"];
759        let mut seed = 0x9E37_79B9_7F4A_7C15u64;
760        let mut next = move |n: usize| {
761            seed ^= seed << 13;
762            seed ^= seed >> 7;
763            seed ^= seed << 17;
764            (seed % n as u64) as usize
765        };
766        for round in 0..200 {
767            let len_a = next(9);
768            let len_b = next(9);
769            // Distinct positions so each item can be recognized after matching.
770            let from: Vec<Item> = (0..len_a)
771                .map(|i| item(KEYS[next(KEYS.len())], i as f64))
772                .collect();
773            let to: Vec<Item> = (0..len_b)
774                .map(|i| item(KEYS[next(KEYS.len())], 100.0 + i as f64))
775                .collect();
776            let p = Pairs::by_key(
777                &from,
778                &to,
779                |i| i.key,
780                |i, c| match c {
781                    Change::Entering => item(i.key, -1.0),
782                    _ => item(i.key, -2.0),
783                },
784            );
785            let arriving: Vec<&Item> = p.settled().collect();
786            assert_eq!(arriving, to.iter().collect::<Vec<_>>(), "round {round}");
787            let mut starts: Vec<f64> = p
788                .iter()
789                .filter(|p| p.change != Change::Entering)
790                .map(|p| p.from.at)
791                .collect();
792            starts.sort_by(f64::total_cmp);
793            let all: Vec<f64> = from.iter().map(|i| i.at).collect();
794            assert_eq!(starts, all, "round {round}");
795            let kept = KEYS
796                .iter()
797                .map(|k| {
798                    let a = from.iter().filter(|i| i.key == *k).count();
799                    let b = to.iter().filter(|i| i.key == *k).count();
800                    a.min(b)
801                })
802                .sum::<usize>();
803            let (k, e, l) = p.counts();
804            assert_eq!(
805                (k, e, l),
806                (kept, len_b - kept, len_a - kept),
807                "round {round}"
808            );
809            for pair in &p {
810                match pair.change {
811                    Change::Kept => assert_eq!(pair.from.key, pair.to.key),
812                    Change::Entering => assert_eq!(pair.from.at, -1.0),
813                    Change::Leaving => assert_eq!(pair.to.at, -2.0),
814                }
815            }
816        }
817    }
818}