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`. |

40 | 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 |