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 crate::free::put_back;
9 use crate::structs::PutBack;
10
11 /// A type returned by the [`diff_with`] function.
12 ///
13 /// `Diff` represents the way in which the elements yielded by the iterator `I` differ to some
14 /// iterator `J`.
15 pub enum Diff<I, J>
16 where I: Iterator,
17 J: Iterator
18 {
19 /// The index of the first non-matching element along with both iterator's remaining elements
20 /// starting with the first mis-match.
21 FirstMismatch(usize, PutBack<I>, PutBack<J>),
22 /// The total number of elements that were in `J` along with the remaining elements of `I`.
23 Shorter(usize, PutBack<I>),
24 /// The total number of elements that were in `I` along with the remaining elements of `J`.
25 Longer(usize, PutBack<J>),
26 }
27
28 /// Compares every element yielded by both `i` and `j` with the given function in lock-step and
29 /// returns a [`Diff`] which describes how `j` differs from `i`.
30 ///
31 /// If the number of elements yielded by `j` is less than the number of elements yielded by `i`,
32 /// the number of `j` elements yielded will be returned along with `i`'s remaining elements as
33 /// `Diff::Shorter`.
34 ///
35 /// If the two elements of a step differ, the index of those elements along with the remaining
36 /// elements of both `i` and `j` are returned as `Diff::FirstMismatch`.
37 ///
38 /// If `i` becomes exhausted before `j` becomes exhausted, the number of elements in `i` along with
39 /// the remaining `j` elements will be returned as `Diff::Longer`.
diff_with<I, J, F>(i: I, j: J, is_equal: F) -> Option<Diff<I::IntoIter, J::IntoIter>> where I: IntoIterator, J: IntoIterator, F: Fn(&I::Item, &J::Item) -> bool40 pub fn diff_with<I, J, F>(i: I, j: J, is_equal: F)
41 -> Option<Diff<I::IntoIter, J::IntoIter>>
42 where I: IntoIterator,
43 J: IntoIterator,
44 F: Fn(&I::Item, &J::Item) -> bool
45 {
46 let mut i = i.into_iter();
47 let mut j = j.into_iter();
48 let mut idx = 0;
49 while let Some(i_elem) = i.next() {
50 match j.next() {
51 None => return Some(Diff::Shorter(idx, put_back(i).with_value(i_elem))),
52 Some(j_elem) => if !is_equal(&i_elem, &j_elem) {
53 let remaining_i = put_back(i).with_value(i_elem);
54 let remaining_j = put_back(j).with_value(j_elem);
55 return Some(Diff::FirstMismatch(idx, remaining_i, remaining_j));
56 },
57 }
58 idx += 1;
59 }
60 j.next().map(|j_elem| Diff::Longer(idx, put_back(j).with_value(j_elem)))
61 }
62