| 113 | } |
| 114 | |
| 115 | pub(crate) fn lcs< |
| 116 | 'a, |
| 117 | T: Same, |
| 118 | I: DoubleEndedIterator<Item = T>, |
| 119 | J: DoubleEndedIterator<Item = T>, |
| 120 | >( |
| 121 | x: impl Fn() -> I, |
| 122 | y: impl Fn() -> J, |
| 123 | x_len: usize, |
| 124 | y_len: usize, |
| 125 | ) -> impl Iterator<Item = Edit<T>> { |
| 126 | let (prefix_eq, c, suffix_eq) = c_matrix(&x, &y, x_len, y_len); |
| 127 | |
| 128 | x().zip(y()) |
| 129 | .take(prefix_eq) |
| 130 | .map(|(x, y)| Edit::Same(x, y)) |
| 131 | .chain(lcs_base( |
| 132 | c, |
| 133 | itertools::put_back( |
| 134 | x().rev() |
| 135 | .skip(suffix_eq) |
| 136 | .take(x_len.saturating_sub(prefix_eq + suffix_eq)), |
| 137 | ), |
| 138 | itertools::put_back( |
| 139 | y().rev() |
| 140 | .skip(suffix_eq) |
| 141 | .take(y_len.saturating_sub(prefix_eq + suffix_eq)), |
| 142 | ), |
| 143 | )) |
| 144 | .chain( |
| 145 | x().skip(x_len - suffix_eq) |
| 146 | .zip(y().skip(y_len - suffix_eq)) |
| 147 | .map(|(x, y)| Edit::Same(x, y)), |
| 148 | ) |
| 149 | } |
| 150 | |
| 151 | // FIXME move out from lcs |
| 152 | pub(crate) fn lcs_post_change<'a, T: Same + Diffable<'a> + ?Sized + 'a>( |