1use std::collections::{HashMap, VecDeque};
26use std::hash::Hash;
27
28use day_spec::{Angle, AnimSpec, Color, Ink, Palette, Point, Rect, Size};
29
30pub trait Lerp: Clone {
36 #[must_use]
37 fn lerp(&self, to: &Self, t: f64) -> Self;
38}
39
40#[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
83impl Lerp for Color {
87 fn lerp(&self, to: &Self, t: f64) -> Self {
88 mix_oklab(*self, *to, t)
89 }
90}
91
92impl Lerp for Angle {
95 fn lerp(&self, to: &Self, t: f64) -> Self {
96 Angle::deg(lerp(self.degrees(), to.degrees(), t))
97 }
98}
99
100impl 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
151impl<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
166impl<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
178fn 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#[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 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
245pub 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#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
268pub enum Change {
269 Kept,
271 Entering,
273 Leaving,
276}
277
278#[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 pub fn at(&self, t: f64) -> T {
289 self.from.lerp(&self.to, t)
290 }
291}
292
293#[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 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 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 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 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 #[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 #[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 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 #[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 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 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 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 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 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 assert_eq!(p.at(1.0), vec![item("a", 10.0), item("b", 0.0)]);
658 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 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 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 #[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 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}