prefix_trie/joint/map/iter.rs
1//! Module that contains the implementation for the iterators
2
3use crate::{
4 joint::JointPrefix,
5 trieview::{
6 union as trie_union, CoveringDifferenceView, DifferenceView, IntersectionView, TrieRef,
7 UnionView, ViewIter,
8 },
9};
10
11use super::JointPrefixMap;
12
13type MapView<'a, P, T> = TrieRef<'a, P, T>;
14type UnionInner<'a, P, L, R> = ViewIter<'a, UnionView<'a, MapView<'a, P, L>, MapView<'a, P, R>>>;
15type IntersectionInner<'a, P, L, R> =
16 ViewIter<'a, IntersectionView<'a, MapView<'a, P, L>, MapView<'a, P, R>>>;
17type DifferenceInner<'a, P, L, R> =
18 ViewIter<'a, DifferenceView<'a, MapView<'a, P, L>, MapView<'a, P, R>>>;
19type CoveringDifferenceInner<'a, P, L, R> =
20 ViewIter<'a, CoveringDifferenceView<'a, MapView<'a, P, L>, MapView<'a, P, R>>>;
21
22/// An iterator over all entries of a [`JointPrefixMap`] in lexicographic order.
23pub struct Iter<'a, P: JointPrefix, T> {
24 pub(crate) i1: Option<crate::map::Iter<'a, P::P1, T>>,
25 pub(crate) i2: Option<crate::map::Iter<'a, P::P2, T>>,
26}
27
28impl<P: JointPrefix, T> Default for Iter<'_, P, T> {
29 /// The default iterator is empty.
30 ///
31 /// ```
32 /// use prefix_trie::joint;
33 /// # #[cfg(feature = "ipnet")]
34 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
35 /// assert_eq!(joint::map::Iter::<ipnet::IpNet, usize>::default().count(), 0);
36 /// # Ok(())
37 /// # }
38 /// # #[cfg(not(feature = "ipnet"))]
39 /// # fn main() {}
40 /// ```
41 fn default() -> Self {
42 Self { i1: None, i2: None }
43 }
44}
45
46impl<P: JointPrefix, T> Clone for Iter<'_, P, T> {
47 /// You can clone an iterator, which maintains its state.
48 ///
49 /// ```
50 /// # use prefix_trie::joint::*;
51 /// # #[cfg(feature = "ipnet")]
52 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
53 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
54 /// pm.insert("2001::1:0:0/96".parse()?, 1);
55 /// pm.insert("192.168.0.0/22".parse()?, 2);
56 /// pm.insert("192.168.0.0/23".parse()?, 3);
57 /// let mut iter = pm.iter();
58 ///
59 /// assert_eq!(iter.next(), Some(("192.168.0.0/22".parse()?, &2)));
60 ///
61 /// let clone = iter.clone();
62 /// assert_eq!(
63 /// iter.collect::<Vec<_>>(),
64 /// vec![
65 /// ("192.168.0.0/23".parse()?, &3),
66 /// ("2001::1:0:0/96".parse()?, &1),
67 /// ]
68 /// );
69 /// assert_eq!(
70 /// clone.collect::<Vec<_>>(),
71 /// vec![
72 /// ("192.168.0.0/23".parse()?, &3),
73 /// ("2001::1:0:0/96".parse()?, &1),
74 /// ]
75 /// );
76 /// # Ok(())
77 /// # }
78 /// # #[cfg(not(feature = "ipnet"))]
79 /// # fn main() {}
80 /// ```
81 fn clone(&self) -> Self {
82 Self {
83 i1: self.i1.clone(),
84 i2: self.i2.clone(),
85 }
86 }
87}
88
89impl<'a, P: JointPrefix, T> Iterator for Iter<'a, P, T> {
90 type Item = (P, &'a T);
91
92 fn next(&mut self) -> Option<(P, &'a T)> {
93 if let Some(i1) = self.i1.as_mut() {
94 if let Some((p, t)) = i1.next() {
95 return Some((P::from_p1(&p), t));
96 }
97 // iterator 1 is empty
98 self.i1 = None;
99 }
100 if let Some(i2) = self.i2.as_mut() {
101 if let Some((p, t)) = i2.next() {
102 return Some((P::from_p2(&p), t));
103 }
104 // iterator 1 is empty
105 self.i2 = None;
106 }
107 None
108 }
109}
110
111/// An iterator over all prefixes of a [`JointPrefixMap`] in lexicographic order.
112#[derive(Clone, Default)]
113pub struct Keys<'a, P: JointPrefix, T> {
114 pub(crate) inner: Iter<'a, P, T>,
115}
116
117impl<P: JointPrefix, T> Iterator for Keys<'_, P, T> {
118 type Item = P;
119
120 fn next(&mut self) -> Option<P> {
121 self.inner.next().map(|(k, _)| k)
122 }
123}
124
125/// An iterator over all values of a [`JointPrefixMap`] in lexicographic order of their associated
126/// prefixes.
127#[derive(Clone, Default)]
128pub struct Values<'a, P: JointPrefix, T> {
129 pub(crate) inner: Iter<'a, P, T>,
130}
131
132impl<'a, P: JointPrefix, T> Iterator for Values<'a, P, T> {
133 type Item = &'a T;
134
135 fn next(&mut self) -> Option<&'a T> {
136 self.inner.next().map(|(_, v)| v)
137 }
138}
139
140/// An iterator over all owned entries of a [`JointPrefixMap`] in lexicographic order.
141#[derive(Clone)]
142pub struct IntoIter<P: JointPrefix, T> {
143 pub(crate) i1: Option<crate::map::IntoIter<P::P1, T>>,
144 pub(crate) i2: Option<crate::map::IntoIter<P::P2, T>>,
145}
146
147impl<P: JointPrefix, T> Iterator for IntoIter<P, T> {
148 type Item = (P, T);
149
150 fn next(&mut self) -> Option<(P, T)> {
151 if let Some(i1) = self.i1.as_mut() {
152 if let Some((p, t)) = i1.next() {
153 return Some((P::from_p1(&p), t));
154 }
155 // iterator 1 is empty
156 self.i1 = None;
157 }
158 if let Some(i2) = self.i2.as_mut() {
159 if let Some((p, t)) = i2.next() {
160 return Some((P::from_p2(&p), t));
161 }
162 // iterator 1 is empty
163 self.i2 = None;
164 }
165 None
166 }
167}
168
169/// An iterator over all prefixes of a [`JointPrefixMap`] in lexicographic order.
170#[derive(Clone)]
171pub struct IntoKeys<P: JointPrefix, T> {
172 pub(crate) inner: IntoIter<P, T>,
173}
174
175impl<P: JointPrefix, T> Iterator for IntoKeys<P, T> {
176 type Item = P;
177
178 fn next(&mut self) -> Option<P> {
179 self.inner.next().map(|(k, _)| k)
180 }
181}
182
183/// An iterator over all values of a [`JointPrefixMap`] in lexicographic order of their associated
184/// prefix.
185#[derive(Clone)]
186pub struct IntoValues<P: JointPrefix, T> {
187 pub(crate) inner: IntoIter<P, T>,
188}
189
190impl<P: JointPrefix, T> Iterator for IntoValues<P, T> {
191 type Item = T;
192
193 fn next(&mut self) -> Option<T> {
194 self.inner.next().map(|(_, v)| v)
195 }
196}
197
198impl<P: JointPrefix, T> IntoIterator for JointPrefixMap<P, T> {
199 type Item = (P, T);
200
201 type IntoIter = IntoIter<P, T>;
202
203 fn into_iter(self) -> Self::IntoIter {
204 IntoIter {
205 i1: Some(self.t1.into_iter()),
206 i2: Some(self.t2.into_iter()),
207 }
208 }
209}
210
211impl<'a, P: JointPrefix, T> IntoIterator for &'a JointPrefixMap<P, T> {
212 type Item = (P, &'a T);
213
214 type IntoIter = Iter<'a, P, T>;
215
216 fn into_iter(self) -> Self::IntoIter {
217 Iter {
218 i1: Some(self.t1.iter()),
219 i2: Some(self.t2.iter()),
220 }
221 }
222}
223
224/// A mutable iterator over a [`JointPrefixMap`]. This iterator yields elements in lexicographic order of
225/// their associated prefix.
226pub struct IterMut<'a, P: JointPrefix, T> {
227 pub(super) i1: Option<crate::map::IterMut<'a, P::P1, T>>,
228 pub(super) i2: Option<crate::map::IterMut<'a, P::P2, T>>,
229}
230
231impl<P: JointPrefix, T> Default for IterMut<'_, P, T> {
232 /// The default iterator is empty.
233 ///
234 /// ```
235 /// use prefix_trie::joint;
236 /// # #[cfg(feature = "ipnet")]
237 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
238 /// assert_eq!(joint::map::IterMut::<ipnet::IpNet, usize>::default().count(), 0);
239 /// # Ok(())
240 /// # }
241 /// # #[cfg(not(feature = "ipnet"))]
242 /// # fn main() {}
243 /// ```
244 fn default() -> Self {
245 Self { i1: None, i2: None }
246 }
247}
248
249impl<'a, P: JointPrefix, T> Iterator for IterMut<'a, P, T> {
250 type Item = (P, &'a mut T);
251
252 fn next(&mut self) -> Option<Self::Item> {
253 if let Some(i1) = self.i1.as_mut() {
254 if let Some((p, t)) = i1.next() {
255 return Some((P::from_p1(&p), t));
256 }
257 // iterator 1 is empty
258 self.i1 = None;
259 }
260 if let Some(i2) = self.i2.as_mut() {
261 if let Some((p, t)) = i2.next() {
262 return Some((P::from_p2(&p), t));
263 }
264 // iterator 1 is empty
265 self.i2 = None;
266 }
267 None
268 }
269}
270
271/// A mutable iterator over values of [`JointPrefixMap`]. This iterator yields elements in
272/// lexicographic order.
273#[derive(Default)]
274pub struct ValuesMut<'a, P: JointPrefix, T> {
275 // # Safety
276 // You must ensure that there only ever exists one such iterator for each tree. You may create
277 // multiple such iterators for the same tree if you start with distinct starting nodes! This
278 // ensures that any one iteration will never yield elements of the other iterator.
279 pub(crate) inner: IterMut<'a, P, T>,
280}
281
282impl<'a, P: JointPrefix, T> Iterator for ValuesMut<'a, P, T> {
283 type Item = &'a mut T;
284
285 fn next(&mut self) -> Option<Self::Item> {
286 self.inner.next().map(|(_, v)| v)
287 }
288}
289
290impl<P: JointPrefix, T> FromIterator<(P, T)> for JointPrefixMap<P, T> {
291 fn from_iter<I: IntoIterator<Item = (P, T)>>(iter: I) -> Self {
292 let mut map = Self::new();
293 iter.into_iter().for_each(|(p, v)| {
294 map.insert(p, v);
295 });
296 map
297 }
298}
299
300/// An iterator that yields all items in a `JointPrefixMap` that covers a given prefix (including
301/// the prefix itself if present). See [`crate::joint::JointPrefixMap::cover`] for how to create
302/// this iterator.
303pub enum Cover<'a, P: JointPrefix, T> {
304 /// Cover of the first prefix variant
305 P1(crate::map::Cover<'a, P::P1, T>),
306 /// Cover of the second prefix variant
307 P2(crate::map::Cover<'a, P::P2, T>),
308}
309
310impl<'a, P: JointPrefix, T: 'a> Iterator for Cover<'a, P, T> {
311 type Item = (P, &'a T);
312
313 fn next(&mut self) -> Option<Self::Item> {
314 match self {
315 Cover::P1(cover) => cover.next().map(|(p, t)| (P::from_p1(&p), t)),
316 Cover::P2(cover) => cover.next().map(|(p, t)| (P::from_p2(&p), t)),
317 }
318 }
319}
320
321/// An iterator that yields all keys (prefixes) in a `JointPrefixMap` that covers a given prefix
322/// (including the prefix itself if present). See [`crate::joint::JointPrefixMap::cover_keys`] for
323/// how to create this iterator.
324pub struct CoverKeys<'a, P: JointPrefix, T>(pub(crate) Cover<'a, P, T>);
325
326impl<'a, P: JointPrefix, T: 'a> Iterator for CoverKeys<'a, P, T> {
327 type Item = P;
328
329 fn next(&mut self) -> Option<Self::Item> {
330 self.0.next().map(|(p, _)| p)
331 }
332}
333
334/// An iterator that yields all values in a `JointPrefixMap` that covers a given prefix (including
335/// the prefix itself if present). See [`crate::joint::JointPrefixMap::cover_values`] for how to
336/// create this iterator.
337pub struct CoverValues<'a, P: JointPrefix, T>(pub(super) Cover<'a, P, T>);
338
339impl<'a, P: JointPrefix, T: 'a> Iterator for CoverValues<'a, P, T> {
340 type Item = &'a T;
341
342 fn next(&mut self) -> Option<Self::Item> {
343 self.0.next().map(|(_, t)| t)
344 }
345}
346
347/// An iterator over the union of two [`JointPrefixMap`]s. The iterator yields first prefixes of
348/// `P1`, followed by those of `P2`.
349pub struct Union<'a, P: JointPrefix, L, R> {
350 pub(crate) i1: Option<UnionInner<'a, P::P1, L, R>>,
351 pub(crate) i2: Option<UnionInner<'a, P::P2, L, R>>,
352}
353
354impl<'a, P: JointPrefix, L: 'a, R: 'a> Iterator for Union<'a, P, L, R> {
355 type Item = UnionItem<'a, P, L, R>;
356
357 fn next(&mut self) -> Option<Self::Item> {
358 if let Some(i1) = self.i1.as_mut() {
359 if let Some(next) = i1.next() {
360 return Some(UnionItem::from_p1(next));
361 }
362 self.i1 = None;
363 }
364 if let Some(i2) = self.i2.as_mut() {
365 if let Some(next) = i2.next() {
366 return Some(UnionItem::from_p2(next));
367 }
368 self.i2 = None;
369 }
370 None
371 }
372}
373
374/// An item of the [`Union`] iterator (over a [`JointPrefixMap`]).
375#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
376
377pub enum UnionItem<'a, P, L, R> {
378 /// The prefix is only present in the left TrieView (`self`).
379 Left {
380 /// The prefix of the element.
381 prefix: P,
382 /// The value of the element in the left TrieView (`self`).
383 left: &'a L,
384 /// No exact value from the right TrieView (`other`) for this prefix. This is always
385 /// `None` for the plain union iterator.
386 right: Option<(P, &'a R)>,
387 },
388
389 /// The prefix is only present in the right TrieView (`other`).
390 Right {
391 /// The prefix of the element.
392 prefix: P,
393 /// No exact value from the left TrieView (`self`) for this prefix. This is always `None`
394 /// for the plain union iterator.
395 left: Option<(P, &'a L)>,
396 /// The value of the element in the right TrieView (`other`).
397 right: &'a R,
398 },
399
400 /// The prefix is present in both TrieViews.
401 Both {
402 /// The prefix of the element.
403 prefix: P,
404 /// The value of the element in the left TrieView (`self`).
405 left: &'a L,
406 /// The value of the element in the right TrieView (`other`).
407 right: &'a R,
408 },
409}
410
411impl<'a, P, L, R> UnionItem<'a, P, L, R> {
412 /// Get the prefix of the current element (in the exact match).
413 ///
414 /// ```
415 /// # use prefix_trie::joint::*;
416 /// # use prefix_trie::joint::map::UnionItem;
417 /// # #[cfg(feature = "ipnet")]
418 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
419 ///
420 /// # #[cfg(feature = "ipnet")]
421 /// # {
422 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
423 /// (net!("2001::1:0:0/96"), 1),
424 /// (net!("192.168.0.0/22"), 2),
425 /// (net!("192.168.0.0/24"), 3),
426 /// ]);
427 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
428 /// (net!("192.168.0.0/22"), "a"),
429 /// (net!("192.168.0.0/23"), "b"),
430 /// ]);
431 /// assert_eq!(
432 /// map_a.union(&map_b).map(|x| *x.prefix()).collect::<Vec<_>>(),
433 /// vec![
434 /// net!("192.168.0.0/22"),
435 /// net!("192.168.0.0/23"),
436 /// net!("192.168.0.0/24"),
437 /// net!("2001::1:0:0/96"),
438 /// ]
439 /// );
440 /// # }
441 /// ```
442 pub fn prefix(&self) -> &P {
443 match self {
444 UnionItem::Left { prefix, .. }
445 | UnionItem::Right { prefix, .. }
446 | UnionItem::Both { prefix, .. } => prefix,
447 }
448 }
449
450 /// Get the prefix of the current element (in the exact match).
451 ///
452 /// ```
453 /// # use prefix_trie::joint::*;
454 /// # use prefix_trie::joint::map::UnionItem;
455 /// # #[cfg(feature = "ipnet")]
456 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
457 ///
458 /// # #[cfg(feature = "ipnet")]
459 /// # {
460 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
461 /// (net!("2001::1:0:0/96"), 1),
462 /// (net!("192.168.0.0/22"), 2),
463 /// (net!("192.168.0.0/24"), 3),
464 /// ]);
465 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
466 /// (net!("192.168.0.0/22"), "a"),
467 /// (net!("192.168.0.0/23"), "b"),
468 /// ]);
469 /// assert_eq!(
470 /// map_a.union(&map_b).map(|x| x.into_prefix()).collect::<Vec<_>>(),
471 /// vec![
472 /// net!("192.168.0.0/22"),
473 /// net!("192.168.0.0/23"),
474 /// net!("192.168.0.0/24"),
475 /// net!("2001::1:0:0/96"),
476 /// ]
477 /// );
478 /// # }
479 /// ```
480 pub fn into_prefix(self) -> P {
481 match self {
482 UnionItem::Left { prefix, .. }
483 | UnionItem::Right { prefix, .. }
484 | UnionItem::Both { prefix, .. } => prefix,
485 }
486 }
487
488 /// Get the element in both the left and right map, but only if they are both present. By
489 /// doing `a.union(b).filter_map(|x| x.both)`, you get an iterator that yields only elements
490 /// that are present in both tries.
491 ///
492 /// ```
493 /// # use prefix_trie::joint::*;
494 /// # use prefix_trie::joint::map::UnionItem;
495 /// # #[cfg(feature = "ipnet")]
496 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
497 ///
498 /// # #[cfg(feature = "ipnet")]
499 /// # {
500 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
501 /// (net!("2001::1:0:0/96"), 1),
502 /// (net!("192.168.0.0/22"), 2),
503 /// (net!("192.168.0.0/24"), 3),
504 /// ]);
505 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
506 /// (net!("192.168.0.0/22"), "a"),
507 /// (net!("192.168.0.0/23"), "b"),
508 /// ]);
509 /// assert_eq!(
510 /// map_a
511 /// .union(&map_b)
512 /// .filter_map(|x| x.both().map(|(p, l, r)| (*p, l, r)))
513 /// .collect::<Vec<_>>(),
514 /// vec![(net!("192.168.0.0/22"), &2, &"a")]
515 /// );
516 /// # }
517 /// ```
518 pub fn both(&self) -> Option<(&P, &'a L, &'a R)> {
519 match self {
520 UnionItem::Left { .. } | UnionItem::Right { .. } => None,
521 UnionItem::Both {
522 prefix,
523 left,
524 right,
525 } => Some((prefix, left, right)),
526 }
527 }
528
529 /// Get the element in both the left and right map, but only if they are both present. By
530 /// doing `a.union(b).filter_map(|x| x.both)`, you get an iterator that yields only elements
531 /// that are present in both tries.
532 ///
533 /// ```
534 /// # use prefix_trie::joint::*;
535 /// # use prefix_trie::joint::map::UnionItem;
536 /// # #[cfg(feature = "ipnet")]
537 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
538 ///
539 /// # #[cfg(feature = "ipnet")]
540 /// # {
541 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
542 /// (net!("2001::1:0:0/96"), 1),
543 /// (net!("192.168.0.0/22"), 2),
544 /// (net!("192.168.0.0/24"), 3),
545 /// ]);
546 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
547 /// (net!("192.168.0.0/22"), "a"),
548 /// (net!("192.168.0.0/23"), "b"),
549 /// ]);
550 /// assert_eq!(
551 /// map_a.union(&map_b).filter_map(|x| x.into_both()).collect::<Vec<_>>(),
552 /// vec![(net!("192.168.0.0/22"), &2, &"a")]
553 /// );
554 /// # }
555 /// ```
556 pub fn into_both(self) -> Option<(P, &'a L, &'a R)> {
557 match self {
558 UnionItem::Left { .. } | UnionItem::Right { .. } => None,
559 UnionItem::Both {
560 prefix,
561 left,
562 right,
563 } => Some((prefix, left, right)),
564 }
565 }
566
567 /// Get the value of the left item (`self`) when it is present exactly.
568 ///
569 /// ```
570 /// # use prefix_trie::joint::*;
571 /// # use prefix_trie::joint::map::UnionItem;
572 /// # #[cfg(feature = "ipnet")]
573 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
574 ///
575 /// # #[cfg(feature = "ipnet")]
576 /// # {
577 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
578 /// (net!("2001::1:0:0/96"), 1),
579 /// (net!("192.168.0.0/22"), 2),
580 /// (net!("192.168.0.0/24"), 3),
581 /// ]);
582 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
583 /// (net!("192.168.0.0/22"), "a"),
584 /// (net!("192.168.0.0/23"), "b"),
585 /// ]);
586 /// assert_eq!(
587 /// map_a
588 /// .union(&map_b)
589 /// .map(|x| x.left().map(|(p, l)| (*p, l)))
590 /// .collect::<Vec<_>>(),
591 /// vec![
592 /// Some((net!("192.168.0.0/22"), &2)),
593 /// None,
594 /// Some((net!("192.168.0.0/24"), &3)),
595 /// Some((net!("2001::1:0:0/96"), &1)),
596 /// ]
597 /// );
598 /// # }
599 /// ```
600 pub fn left(&self) -> Option<(&P, &'a L)> {
601 match self {
602 UnionItem::Right { left, .. } => left.as_ref().map(|(p, l)| (p, *l)),
603 UnionItem::Left { prefix, left, .. } | UnionItem::Both { prefix, left, .. } => {
604 Some((prefix, left))
605 }
606 }
607 }
608
609 /// Get the value of the left item (`self`) when it is present exactly.
610 ///
611 /// ```
612 /// # use prefix_trie::joint::*;
613 /// # use prefix_trie::joint::map::UnionItem;
614 /// # #[cfg(feature = "ipnet")]
615 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
616 ///
617 /// # #[cfg(feature = "ipnet")]
618 /// # {
619 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
620 /// (net!("2001::1:0:0/96"), 1),
621 /// (net!("2001::2:0:0/96"), 2),
622 /// (net!("2001::2:0:0/98"), 3),
623 /// ]);
624 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
625 /// (net!("2001::2:0:0/96"), "a"),
626 /// (net!("2001::2:0:0/97"), "b"),
627 /// ]);
628 /// assert_eq!(
629 /// map_a.union(&map_b).map(|x| x.into_left()).collect::<Vec<_>>(),
630 /// vec![
631 /// Some((net!("2001::1:0:0/96"), &1)),
632 /// Some((net!("2001::2:0:0/96"), &2)),
633 /// None,
634 /// Some((net!("2001::2:0:0/98"), &3)),
635 /// ]
636 /// );
637 /// # }
638 /// ```
639 pub fn into_left(self) -> Option<(P, &'a L)> {
640 match self {
641 UnionItem::Right { left, .. } => left,
642 UnionItem::Left { prefix, left, .. } | UnionItem::Both { prefix, left, .. } => {
643 Some((prefix, left))
644 }
645 }
646 }
647
648 /// Get the value of the right item (`other`) when it is present exactly.
649 ///
650 /// ```
651 /// # use prefix_trie::joint::*;
652 /// # use prefix_trie::joint::map::UnionItem;
653 /// # #[cfg(feature = "ipnet")]
654 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
655 ///
656 /// # #[cfg(feature = "ipnet")]
657 /// # {
658 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
659 /// (net!("2001::1:0:0/96"), 1),
660 /// (net!("192.168.0.0/22"), 2),
661 /// (net!("192.168.0.0/24"), 3),
662 /// ]);
663 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
664 /// (net!("192.168.0.0/22"), "a"),
665 /// (net!("192.168.0.0/23"), "b"),
666 /// ]);
667 /// assert_eq!(
668 /// map_a
669 /// .union(&map_b)
670 /// .map(|x| x.right().map(|(p, r)| (*p, r)))
671 /// .collect::<Vec<_>>(),
672 /// vec![
673 /// Some((net!("192.168.0.0/22"), &"a")),
674 /// Some((net!("192.168.0.0/23"), &"b")),
675 /// None,
676 /// None,
677 /// ]
678 /// );
679 /// # }
680 /// ```
681 pub fn right(&self) -> Option<(&P, &'a R)> {
682 match self {
683 UnionItem::Left { right, .. } => right.as_ref().map(|(p, r)| (p, *r)),
684 UnionItem::Right { prefix, right, .. } | UnionItem::Both { prefix, right, .. } => {
685 Some((prefix, right))
686 }
687 }
688 }
689
690 /// Get the value of the right item (`other`) when it is present exactly.
691 ///
692 /// ```
693 /// # use prefix_trie::joint::*;
694 /// # use prefix_trie::joint::map::UnionItem;
695 /// # #[cfg(feature = "ipnet")]
696 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
697 ///
698 /// # #[cfg(feature = "ipnet")]
699 /// # {
700 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
701 /// (net!("2001::1:0:0/96"), 1),
702 /// (net!("2001::2:0:0/96"), 2),
703 /// (net!("2001::2:0:0/98"), 3),
704 /// ]);
705 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
706 /// (net!("2001::2:0:0/96"), "a"),
707 /// (net!("2001::2:0:0/97"), "b"),
708 /// ]);
709 /// assert_eq!(
710 /// map_a.union(&map_b).map(|x| x.into_right()).collect::<Vec<_>>(),
711 /// vec![
712 /// None,
713 /// Some((net!("2001::2:0:0/96"), &"a")),
714 /// Some((net!("2001::2:0:0/97"), &"b")),
715 /// None,
716 /// ]
717 /// );
718 /// # }
719 /// ```
720 pub fn into_right(self) -> Option<(P, &'a R)> {
721 match self {
722 UnionItem::Left { right, .. } => right,
723 UnionItem::Right { prefix, right, .. } | UnionItem::Both { prefix, right, .. } => {
724 Some((prefix, right))
725 }
726 }
727 }
728}
729
730impl<'a, P: JointPrefix, L, R> UnionItem<'a, P, L, R> {
731 fn from_p1(value: (P::P1, trie_union::UnionItem<&'a L, &'a R>)) -> Self {
732 let (prefix, item) = value;
733 match item {
734 trie_union::UnionItem::Left(left) => UnionItem::Left {
735 prefix: P::from_p1(&prefix),
736 left,
737 right: None,
738 },
739 trie_union::UnionItem::Right(right) => UnionItem::Right {
740 prefix: P::from_p1(&prefix),
741 left: None,
742 right,
743 },
744 trie_union::UnionItem::Both(left, right) => UnionItem::Both {
745 prefix: P::from_p1(&prefix),
746 left,
747 right,
748 },
749 }
750 }
751
752 fn from_p2(value: (P::P2, trie_union::UnionItem<&'a L, &'a R>)) -> Self {
753 let (prefix, item) = value;
754 match item {
755 trie_union::UnionItem::Left(left) => UnionItem::Left {
756 prefix: P::from_p2(&prefix),
757 left,
758 right: None,
759 },
760 trie_union::UnionItem::Right(right) => UnionItem::Right {
761 prefix: P::from_p2(&prefix),
762 left: None,
763 right,
764 },
765 trie_union::UnionItem::Both(left, right) => UnionItem::Both {
766 prefix: P::from_p2(&prefix),
767 left,
768 right,
769 },
770 }
771 }
772}
773
774/// An iterator over the intersection of two [`JointPrefixMap`]s. The iterator yields first prefixes
775/// of `P1`, followed by those of `P2`.
776pub struct Intersection<'a, P: JointPrefix, L, R> {
777 pub(crate) i1: Option<IntersectionInner<'a, P::P1, L, R>>,
778 pub(crate) i2: Option<IntersectionInner<'a, P::P2, L, R>>,
779}
780
781impl<'a, P: JointPrefix, L: 'a, R: 'a> Iterator for Intersection<'a, P, L, R> {
782 type Item = (P, &'a L, &'a R);
783
784 fn next(&mut self) -> Option<Self::Item> {
785 if let Some(i1) = self.i1.as_mut() {
786 if let Some((p, (l, r))) = i1.next() {
787 return Some((P::from_p1(&p), l, r));
788 }
789 self.i1 = None;
790 }
791 if let Some(i2) = self.i2.as_mut() {
792 if let Some((p, (l, r))) = i2.next() {
793 return Some((P::from_p2(&p), l, r));
794 }
795 self.i2 = None;
796 }
797 None
798 }
799}
800
801/// An iterator over the difference of two [`JointPrefixMap`]s, i.e., prefixes that are in `self`
802/// but not in `other`. The iterator yields first prefixes of `P1`, followed by those of `P2`.
803pub struct Difference<'a, P: JointPrefix, L, R> {
804 pub(crate) i1: Option<DifferenceInner<'a, P::P1, L, R>>,
805 pub(crate) i2: Option<DifferenceInner<'a, P::P2, L, R>>,
806}
807
808impl<'a, P: JointPrefix, L: 'a, R: 'a> Iterator for Difference<'a, P, L, R> {
809 type Item = DifferenceItem<'a, P, L, R>;
810
811 fn next(&mut self) -> Option<Self::Item> {
812 if let Some(i1) = self.i1.as_mut() {
813 if let Some(next) = i1.next() {
814 return Some(DifferenceItem::from_p1(next));
815 }
816 self.i1 = None;
817 }
818 if let Some(i2) = self.i2.as_mut() {
819 if let Some(next) = i2.next() {
820 return Some(DifferenceItem::from_p2(next));
821 }
822 self.i2 = None;
823 }
824 None
825 }
826}
827
828/// An iterator over the covering difference of two [`JointPrefixMap`]s, i.e., prefixes of `self` that
829/// are not covered by `other`. The iterator yields first prefixes of `P1`, followed by those of
830/// `P2`.
831pub struct CoveringDifference<'a, P: JointPrefix, L, R> {
832 pub(crate) i1: Option<CoveringDifferenceInner<'a, P::P1, L, R>>,
833 pub(crate) i2: Option<CoveringDifferenceInner<'a, P::P2, L, R>>,
834}
835
836impl<'a, P: JointPrefix, L: 'a, R: 'a> Iterator for CoveringDifference<'a, P, L, R> {
837 type Item = (P, &'a L);
838
839 fn next(&mut self) -> Option<Self::Item> {
840 if let Some(i1) = self.i1.as_mut() {
841 if let Some((p, l)) = i1.next() {
842 return Some((P::from_p1(&p), l));
843 }
844 self.i1 = None;
845 }
846 if let Some(i2) = self.i2.as_mut() {
847 if let Some((p, l)) = i2.next() {
848 return Some((P::from_p2(&p), l));
849 }
850 self.i2 = None;
851 }
852 None
853 }
854}
855
856/// An item of the [`Difference`] iterator.
857#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
858pub struct DifferenceItem<'a, P, L, R> {
859 /// The prefix that is present in `self` but not in `other`.
860 pub prefix: P,
861 /// The value stored in `self`.
862 pub value: &'a L,
863 /// No matching right-side value is yielded by plain difference. This is always `None`.
864 pub right: Option<(P, &'a R)>,
865}
866
867impl<'a, P: JointPrefix, L, R> DifferenceItem<'a, P, L, R> {
868 fn from_p1(value: (P::P1, &'a L)) -> Self {
869 let (prefix, value) = value;
870 Self {
871 prefix: P::from_p1(&prefix),
872 value,
873 right: None,
874 }
875 }
876
877 fn from_p2(value: (P::P2, &'a L)) -> Self {
878 let (prefix, value) = value;
879 Self {
880 prefix: P::from_p2(&prefix),
881 value,
882 right: None,
883 }
884 }
885}