1 //! "Diff"ing iterators for caching elements to sequential collections without requiring the new
2 //! elements' iterator to be `Clone`.
3 //!
4 //! - [`Diff`] (produced by the [`diff_with`] function)
5 //! describes the difference between two non-`Clone` iterators `I` and `J` after breaking ASAP from
6 //! a lock-step comparison.
7
8 use std::fmt;
9
10 use crate::free::put_back;
11 use crate::structs::PutBack;
12
13 /// A type returned by the [`diff_with`] function.
14 ///
15 /// `Diff` represents the way in which the elements yielded by the iterator `I` differ to some
16 /// iterator `J`.
17 pub enum Diff<I, J>
18 where
19 I: Iterator,
20 J: Iterator,
21 {
22 /// The index of the first non-matching element along with both iterator's remaining elements
23 /// starting with the first mis-match.
24 FirstMismatch(usize, PutBack<I>, PutBack<J>),
25 /// The total number of elements that were in `J` along with the remaining elements of `I`.
26 Shorter(usize, PutBack<I>),
27 /// The total number of elements that were in `I` along with the remaining elements of `J`.
28 Longer(usize, PutBack<J>),
29 }
30
31 impl<I, J> fmt::Debug for Diff<I, J>
32 where
33 I: Iterator,
34 J: Iterator,
35 PutBack<I>: fmt::Debug,
36 PutBack<J>: fmt::Debug,
37 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result38 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
39 match self {
40 Self::FirstMismatch(idx, i, j) => f
41 .debug_tuple("FirstMismatch")
42 .field(idx)
43 .field(i)
44 .field(j)
45 .finish(),
46 Self::Shorter(idx, i) => f.debug_tuple("Shorter").field(idx).field(i).finish(),
47 Self::Longer(idx, j) => f.debug_tuple("Longer").field(idx).field(j).finish(),
48 }
49 }
50 }
51
52 impl<I, J> Clone for Diff<I, J>
53 where
54 I: Iterator,
55 J: Iterator,
56 PutBack<I>: Clone,
57 PutBack<J>: Clone,
58 {
clone(&self) -> Self59 fn clone(&self) -> Self {
60 match self {
61 Self::FirstMismatch(idx, i, j) => Self::FirstMismatch(*idx, i.clone(), j.clone()),
62 Self::Shorter(idx, i) => Self::Shorter(*idx, i.clone()),
63 Self::Longer(idx, j) => Self::Longer(*idx, j.clone()),
64 }
65 }
66 }
67
68 /// Compares every element yielded by both `i` and `j` with the given function in lock-step and
69 /// returns a [`Diff`] which describes how `j` differs from `i`.
70 ///
71 /// If the number of elements yielded by `j` is less than the number of elements yielded by `i`,
72 /// the number of `j` elements yielded will be returned along with `i`'s remaining elements as
73 /// `Diff::Shorter`.
74 ///
75 /// If the two elements of a step differ, the index of those elements along with the remaining
76 /// elements of both `i` and `j` are returned as `Diff::FirstMismatch`.
77 ///
78 /// If `i` becomes exhausted before `j` becomes exhausted, the number of elements in `i` along with
79 /// the remaining `j` elements will be returned as `Diff::Longer`.
diff_with<I, J, F>(i: I, j: J, mut is_equal: F) -> Option<Diff<I::IntoIter, J::IntoIter>> where I: IntoIterator, J: IntoIterator, F: FnMut(&I::Item, &J::Item) -> bool,80 pub fn diff_with<I, J, F>(i: I, j: J, mut is_equal: F) -> Option<Diff<I::IntoIter, J::IntoIter>>
81 where
82 I: IntoIterator,
83 J: IntoIterator,
84 F: FnMut(&I::Item, &J::Item) -> bool,
85 {
86 let mut i = i.into_iter();
87 let mut j = j.into_iter();
88 let mut idx = 0;
89 while let Some(i_elem) = i.next() {
90 match j.next() {
91 None => return Some(Diff::Shorter(idx, put_back(i).with_value(i_elem))),
92 Some(j_elem) => {
93 if !is_equal(&i_elem, &j_elem) {
94 let remaining_i = put_back(i).with_value(i_elem);
95 let remaining_j = put_back(j).with_value(j_elem);
96 return Some(Diff::FirstMismatch(idx, remaining_i, remaining_j));
97 }
98 }
99 }
100 idx += 1;
101 }
102 j.next()
103 .map(|j_elem| Diff::Longer(idx, put_back(j).with_value(j_elem)))
104 }
105