| 1 |
use std::cmp::Ordering; |
| 2 |
use std::fmt; |
| 3 |
use std::iter::{Fuse, FusedIterator}; |
| 4 |
use std::marker::PhantomData; |
| 5 |
|
| 6 |
use either::Either; |
| 7 |
|
| 8 |
use super::adaptors::{put_back, PutBack}; |
| 9 |
use crate::either_or_both::EitherOrBoth; |
| 10 |
use crate::size_hint::{self, SizeHint}; |
| 11 |
#[cfg(doc)] |
| 12 |
use crate::Itertools; |
| 13 |
|
| 14 |
#[derive(Clone, Debug)] |
| 15 |
pub struct MergeLte; |
| 16 |
|
| 17 |
/// An iterator adaptor that merges the two base iterators in ascending order. |
| 18 |
/// If both base iterators are sorted (ascending), the result is sorted. |
| 19 |
/// |
| 20 |
/// Iterator element type is `I::Item`. |
| 21 |
/// |
| 22 |
/// See [`.merge()`](crate::Itertools::merge_by) for more information. |
| 23 |
pub type Merge<I, J> = MergeBy<I, J, MergeLte>; |
| 24 |
|
| 25 |
/// Create an iterator that merges elements in `i` and `j`. |
| 26 |
/// |
| 27 |
/// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge). |
| 28 |
/// |
| 29 |
/// ``` |
| 30 |
/// use itertools::merge; |
| 31 |
/// |
| 32 |
/// for elt in merge(&[1, 2, 3], &[2, 3, 4]) { |
| 33 |
/// /* loop body */ |
| 34 |
/// # let _ = elt; |
| 35 |
/// } |
| 36 |
/// ``` |
| 37 |
pub fn merge<I, J>( |
| 38 |
i: I, |
| 39 |
j: J, |
| 40 |
) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> |
| 41 |
where |
| 42 |
I: IntoIterator, |
| 43 |
J: IntoIterator<Item = I::Item>, |
| 44 |
I::Item: PartialOrd, |
| 45 |
{ |
| 46 |
merge_by_new(i, j, MergeLte) |
| 47 |
} |
| 48 |
|
| 49 |
/// An iterator adaptor that merges the two base iterators in ascending order. |
| 50 |
/// If both base iterators are sorted (ascending), the result is sorted. |
| 51 |
/// |
| 52 |
/// Iterator element type is `I::Item`. |
| 53 |
/// |
| 54 |
/// See [`.merge_by()`](crate::Itertools::merge_by) for more information. |
| 55 |
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 56 |
pub struct MergeBy<I: Iterator, J: Iterator, F> { |
| 57 |
left: PutBack<Fuse<I>>, |
| 58 |
right: PutBack<Fuse<J>>, |
| 59 |
cmp_fn: F, |
| 60 |
} |
| 61 |
|
| 62 |
/// Create a `MergeBy` iterator. |
| 63 |
pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F> |
| 64 |
where |
| 65 |
I: IntoIterator, |
| 66 |
J: IntoIterator<Item = I::Item>, |
| 67 |
{ |
| 68 |
MergeBy { |
| 69 |
left: put_back(a.into_iter().fuse()), |
| 70 |
right: put_back(b.into_iter().fuse()), |
| 71 |
cmp_fn: cmp, |
| 72 |
} |
| 73 |
} |
| 74 |
|
| 75 |
/// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order. |
| 76 |
/// |
| 77 |
/// [`IntoIterator`] enabled version of [`Itertools::merge_join_by`]. |
| 78 |
pub fn merge_join_by<I, J, F, T>( |
| 79 |
left: I, |
| 80 |
right: J, |
| 81 |
cmp_fn: F, |
| 82 |
) -> MergeJoinBy<I::IntoIter, J::IntoIter, F> |
| 83 |
where |
| 84 |
I: IntoIterator, |
| 85 |
J: IntoIterator, |
| 86 |
F: FnMut(&I::Item, &J::Item) -> T, |
| 87 |
{ |
| 88 |
MergeBy { |
| 89 |
left: put_back(left.into_iter().fuse()), |
| 90 |
right: put_back(right.into_iter().fuse()), |
| 91 |
cmp_fn: MergeFuncLR(cmp_fn, PhantomData), |
| 92 |
} |
| 93 |
} |
| 94 |
|
| 95 |
/// An iterator adaptor that merge-joins items from the two base iterators in ascending order. |
| 96 |
/// |
| 97 |
/// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information. |
| 98 |
pub type MergeJoinBy<I, J, F> = |
| 99 |
MergeBy<I, J, MergeFuncLR<F, <F as FuncLR<<I as Iterator>::Item, <J as Iterator>::Item>>::T>>; |
| 100 |
|
| 101 |
#[derive(Clone, Debug)] |
| 102 |
pub struct MergeFuncLR<F, T>(F, PhantomData<T>); |
| 103 |
|
| 104 |
pub trait FuncLR<L, R> { |
| 105 |
type T; |
| 106 |
} |
| 107 |
|
| 108 |
impl<L, R, T, F: FnMut(&L, &R) -> T> FuncLR<L, R> for F { |
| 109 |
type T = T; |
| 110 |
} |
| 111 |
|
| 112 |
pub trait OrderingOrBool<L, R> { |
| 113 |
type MergeResult; |
| 114 |
fn left(left: L) -> Self::MergeResult; |
| 115 |
fn right(right: R) -> Self::MergeResult; |
| 116 |
// "merge" never returns (Some(...), Some(...), ...) so Option<Either<I::Item, J::Item>> |
| 117 |
// is appealing but it is always followed by two put_backs, so we think the compiler is |
| 118 |
// smart enough to optimize it. Or we could move put_backs into "merge". |
| 119 |
fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult); |
| 120 |
fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint; |
| 121 |
} |
| 122 |
|
| 123 |
impl<L, R, F: FnMut(&L, &R) -> Ordering> OrderingOrBool<L, R> for MergeFuncLR<F, Ordering> { |
| 124 |
type MergeResult = EitherOrBoth<L, R>; |
| 125 |
fn left(left: L) -> Self::MergeResult { |
| 126 |
EitherOrBoth::Left(left) |
| 127 |
} |
| 128 |
fn right(right: R) -> Self::MergeResult { |
| 129 |
EitherOrBoth::Right(right) |
| 130 |
} |
| 131 |
fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult) { |
| 132 |
match self.0(&left, &right) { |
| 133 |
Ordering::Equal => (None, EitherOrBoth::Both(left, right)), |
| 134 |
Ordering::Less => (Some(Either::Right(right)), EitherOrBoth::Left(left)), |
| 135 |
Ordering::Greater => (Some(Either::Left(left)), EitherOrBoth::Right(right)), |
| 136 |
} |
| 137 |
} |
| 138 |
fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint { |
| 139 |
let (a_lower, a_upper) = left; |
| 140 |
let (b_lower, b_upper) = right; |
| 141 |
let lower = ::std::cmp::max(a_lower, b_lower); |
| 142 |
let upper = match (a_upper, b_upper) { |
| 143 |
(Some(x), Some(y)) => x.checked_add(y), |
| 144 |
_ => None, |
| 145 |
}; |
| 146 |
(lower, upper) |
| 147 |
} |
| 148 |
} |
| 149 |
|
| 150 |
impl<L, R, F: FnMut(&L, &R) -> bool> OrderingOrBool<L, R> for MergeFuncLR<F, bool> { |
| 151 |
type MergeResult = Either<L, R>; |
| 152 |
fn left(left: L) -> Self::MergeResult { |
| 153 |
Either::Left(left) |
| 154 |
} |
| 155 |
fn right(right: R) -> Self::MergeResult { |
| 156 |
Either::Right(right) |
| 157 |
} |
| 158 |
fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult) { |
| 159 |
if self.0(&left, &right) { |
| 160 |
(Some(Either::Right(right)), Either::Left(left)) |
| 161 |
} else { |
| 162 |
(Some(Either::Left(left)), Either::Right(right)) |
| 163 |
} |
| 164 |
} |
| 165 |
fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint { |
| 166 |
// Not ExactSizeIterator because size may be larger than usize |
| 167 |
size_hint::add(left, right) |
| 168 |
} |
| 169 |
} |
| 170 |
|
| 171 |
impl<T, F: FnMut(&T, &T) -> bool> OrderingOrBool<T, T> for F { |
| 172 |
type MergeResult = T; |
| 173 |
fn left(left: T) -> Self::MergeResult { |
| 174 |
left |
| 175 |
} |
| 176 |
fn right(right: T) -> Self::MergeResult { |
| 177 |
right |
| 178 |
} |
| 179 |
fn merge(&mut self, left: T, right: T) -> (Option<Either<T, T>>, Self::MergeResult) { |
| 180 |
if self(&left, &right) { |
| 181 |
(Some(Either::Right(right)), left) |
| 182 |
} else { |
| 183 |
(Some(Either::Left(left)), right) |
| 184 |
} |
| 185 |
} |
| 186 |
fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint { |
| 187 |
// Not ExactSizeIterator because size may be larger than usize |
| 188 |
size_hint::add(left, right) |
| 189 |
} |
| 190 |
} |
| 191 |
|
| 192 |
impl<T: PartialOrd> OrderingOrBool<T, T> for MergeLte { |
| 193 |
type MergeResult = T; |
| 194 |
fn left(left: T) -> Self::MergeResult { |
| 195 |
left |
| 196 |
} |
| 197 |
fn right(right: T) -> Self::MergeResult { |
| 198 |
right |
| 199 |
} |
| 200 |
fn merge(&mut self, left: T, right: T) -> (Option<Either<T, T>>, Self::MergeResult) { |
| 201 |
if left <= right { |
| 202 |
(Some(Either::Right(right)), left) |
| 203 |
} else { |
| 204 |
(Some(Either::Left(left)), right) |
| 205 |
} |
| 206 |
} |
| 207 |
fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint { |
| 208 |
// Not ExactSizeIterator because size may be larger than usize |
| 209 |
size_hint::add(left, right) |
| 210 |
} |
| 211 |
} |
| 212 |
|
| 213 |
impl<I, J, F> Clone for MergeBy<I, J, F> |
| 214 |
where |
| 215 |
I: Iterator, |
| 216 |
J: Iterator, |
| 217 |
PutBack<Fuse<I>>: Clone, |
| 218 |
PutBack<Fuse<J>>: Clone, |
| 219 |
F: Clone, |
| 220 |
{ |
| 221 |
clone_fields!(left, right, cmp_fn); |
| 222 |
} |
| 223 |
|
| 224 |
impl<I, J, F> fmt::Debug for MergeBy<I, J, F> |
| 225 |
where |
| 226 |
I: Iterator + fmt::Debug, |
| 227 |
I::Item: fmt::Debug, |
| 228 |
J: Iterator + fmt::Debug, |
| 229 |
J::Item: fmt::Debug, |
| 230 |
{ |
| 231 |
debug_fmt_fields!(MergeBy, left, right); |
| 232 |
} |
| 233 |
|
| 234 |
impl<I, J, F> Iterator for MergeBy<I, J, F> |
| 235 |
where |
| 236 |
I: Iterator, |
| 237 |
J: Iterator, |
| 238 |
F: OrderingOrBool<I::Item, J::Item>, |
| 239 |
{ |
| 240 |
type Item = F::MergeResult; |
| 241 |
|
| 242 |
fn next(&mut self) -> Option<Self::Item> { |
| 243 |
match (self.left.next(), self.right.next()) { |
| 244 |
(None, None) => None, |
| 245 |
(Some(left), None) => Some(F::left(left)), |
| 246 |
(None, Some(right)) => Some(F::right(right)), |
| 247 |
(Some(left), Some(right)) => { |
| 248 |
let (not_next, next) = self.cmp_fn.merge(left, right); |
| 249 |
match not_next { |
| 250 |
Some(Either::Left(l)) => { |
| 251 |
self.left.put_back(l); |
| 252 |
} |
| 253 |
Some(Either::Right(r)) => { |
| 254 |
self.right.put_back(r); |
| 255 |
} |
| 256 |
None => (), |
| 257 |
} |
| 258 |
|
| 259 |
Some(next) |
| 260 |
} |
| 261 |
} |
| 262 |
} |
| 263 |
|
| 264 |
fn fold<B, G>(mut self, init: B, mut f: G) -> B |
| 265 |
where |
| 266 |
Self: Sized, |
| 267 |
G: FnMut(B, Self::Item) -> B, |
| 268 |
{ |
| 269 |
let mut acc = init; |
| 270 |
let mut left = self.left.next(); |
| 271 |
let mut right = self.right.next(); |
| 272 |
|
| 273 |
loop { |
| 274 |
match (left, right) { |
| 275 |
(Some(l), Some(r)) => match self.cmp_fn.merge(l, r) { |
| 276 |
(Some(Either::Right(r)), x) => { |
| 277 |
acc = f(acc, x); |
| 278 |
left = self.left.next(); |
| 279 |
right = Some(r); |
| 280 |
} |
| 281 |
(Some(Either::Left(l)), x) => { |
| 282 |
acc = f(acc, x); |
| 283 |
left = Some(l); |
| 284 |
right = self.right.next(); |
| 285 |
} |
| 286 |
(None, x) => { |
| 287 |
acc = f(acc, x); |
| 288 |
left = self.left.next(); |
| 289 |
right = self.right.next(); |
| 290 |
} |
| 291 |
}, |
| 292 |
(Some(l), None) => { |
| 293 |
self.left.put_back(l); |
| 294 |
acc = self.left.fold(acc, |acc, x| f(acc, F::left(x))); |
| 295 |
break; |
| 296 |
} |
| 297 |
(None, Some(r)) => { |
| 298 |
self.right.put_back(r); |
| 299 |
acc = self.right.fold(acc, |acc, x| f(acc, F::right(x))); |
| 300 |
break; |
| 301 |
} |
| 302 |
(None, None) => { |
| 303 |
break; |
| 304 |
} |
| 305 |
} |
| 306 |
} |
| 307 |
|
| 308 |
acc |
| 309 |
} |
| 310 |
|
| 311 |
fn size_hint(&self) -> SizeHint { |
| 312 |
F::size_hint(self.left.size_hint(), self.right.size_hint()) |
| 313 |
} |
| 314 |
|
| 315 |
fn nth(&mut self, mut n: usize) -> Option<Self::Item> { |
| 316 |
loop { |
| 317 |
if n == 0 { |
| 318 |
break self.next(); |
| 319 |
} |
| 320 |
n -= 1; |
| 321 |
match (self.left.next(), self.right.next()) { |
| 322 |
(None, None) => break None, |
| 323 |
(Some(_left), None) => break self.left.nth(n).map(F::left), |
| 324 |
(None, Some(_right)) => break self.right.nth(n).map(F::right), |
| 325 |
(Some(left), Some(right)) => { |
| 326 |
let (not_next, _) = self.cmp_fn.merge(left, right); |
| 327 |
match not_next { |
| 328 |
Some(Either::Left(l)) => { |
| 329 |
self.left.put_back(l); |
| 330 |
} |
| 331 |
Some(Either::Right(r)) => { |
| 332 |
self.right.put_back(r); |
| 333 |
} |
| 334 |
None => (), |
| 335 |
} |
| 336 |
} |
| 337 |
} |
| 338 |
} |
| 339 |
} |
| 340 |
} |
| 341 |
|
| 342 |
impl<I, J, F> FusedIterator for MergeBy<I, J, F> |
| 343 |
where |
| 344 |
I: Iterator, |
| 345 |
J: Iterator, |
| 346 |
F: OrderingOrBool<I::Item, J::Item>, |
| 347 |
{ |
| 348 |
} |