segmap/map/
iterators.rs

1use core::{
2    fmt::{self, Debug},
3    iter::{FromIterator, FusedIterator},
4    ops::Bound::*,
5};
6
7use alloc::vec::Vec;
8
9use super::Key;
10use crate::{
11    segment::{End, Segment, Start},
12    RangeBounds, SegmentMap, SegmentSet,
13};
14
15// TODO: all doctests
16
17impl<K, V> SegmentMap<K, V> {
18    /// Returns the number of ranges in the map.
19    ///
20    /// # Examples
21    ///
22    /// Basic usage:
23    ///
24    /// ```
25    /// use std::collections::BTreeMap;
26    ///
27    /// let mut a = BTreeMap::new();
28    /// assert_eq!(a.len(), 0);
29    /// a.insert(1, "a");
30    /// assert_eq!(a.len(), 1);
31    /// ```
32    pub fn len(&self) -> usize {
33        self.map.len()
34    }
35
36    /// Returns `true` if the map contains no ranges.
37    ///
38    /// # Examples
39    ///
40    /// Basic usage:
41    ///
42    /// ```
43    /// use std::collections::BTreeMap;
44    ///
45    /// let mut a = BTreeMap::new();
46    /// assert!(a.is_empty());
47    /// a.insert(1, "a");
48    /// assert!(!a.is_empty());
49    /// ```
50    pub fn is_empty(&self) -> bool {
51        self.map.is_empty()
52    }
53
54    /// Converts the map into a [`Vec`] by chaining [`into_iter`] and [`collect`]
55    pub fn into_vec(self) -> Vec<(Segment<K>, V)> {
56        self.into_iter().collect()
57    }
58
59    /// Gets an iterator over the sorted ranges in the map.
60    ///
61    /// # Examples
62    ///
63    /// Basic usage:
64    ///
65    /// ```
66    /// # use segmap::*;
67    /// let mut map = SegmentMap::new();
68    /// map.insert(0..1, "a");
69    /// map.insert(1..2, "b");
70    /// map.insert(2..3, "c");
71    ///
72    /// let (first_range, first_value) = map.iter().next().unwrap();
73    /// assert_eq!((*first_range, *first_value), (Segment::from(0..1), "a"));
74    /// ```
75    pub fn iter(&self) -> Iter<'_, K, V> {
76        Iter(self.map.iter())
77    }
78
79    /// Gets an iterator over a subset of the sorted ranges in the map, bounded
80    /// by `range`.
81    pub fn iter_in<R>(&self, range: R) -> IterIn<'_, K, V>
82    where
83        R: RangeBounds<K>,
84        K: Clone + Ord,
85    {
86        IterIn {
87            iter: self.iter(),
88            range: Segment::from(&range),
89        }
90    }
91
92    /// Gets an iterator over the sorted ranges in the map, with mutable values
93    ///
94    /// Ranges are used as keys and therefore cannot be mutable. To manipulate
95    /// the bounds of stored ranges, they must be removed and re-inserted to
96    /// ensure bound integrity.
97    ///
98    /// # Examples
99    ///
100    /// Basic usage:
101    ///
102    /// ```
103    /// use std::collections::BTreeMap;
104    ///
105    /// let mut map = BTreeMap::new();
106    /// map.insert("a", 1);
107    /// map.insert("b", 2);
108    /// map.insert("c", 3);
109    ///
110    /// // add 10 to the value if the key isn't "a"
111    /// for (key, value) in map.iter_mut() {
112    ///     if key != &"a" {
113    ///         *value += 10;
114    ///     }
115    /// }
116    /// ```
117    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
118        IterMut(self.map.iter_mut())
119    }
120
121    /// Gets an iterator over the range keys of the map (similar to `BTreeMap::keys()`)
122    ///
123    /// # Examples
124    ///
125    /// Basic usage:
126    ///
127    /// ```
128    /// use std::collections::BTreeMap;
129    ///
130    /// let mut a = BTreeMap::new();
131    /// a.insert(2, "b");
132    /// a.insert(1, "a");
133    ///
134    /// let keys: Vec<_> = a.keys().cloned().collect();
135    /// assert_eq!(keys, [1, 2]);
136    /// ```
137    // pub fn keys(&self) -> Keys<'_, K, V> {
138    //     Keys(self.iter())
139    // }
140    pub fn ranges(&self) -> Ranges<'_, K, V> {
141        Ranges(self.iter())
142    }
143
144    /// Gets an iterator over the values of the map, in order by their range.
145    ///
146    /// # Examples
147    ///
148    /// Basic usage:
149    ///
150    /// ```
151    /// use std::collections::BTreeMap;
152    ///
153    /// let mut a = BTreeMap::new();
154    /// a.insert(1, "hello");
155    /// a.insert(2, "goodbye");
156    ///
157    /// let values: Vec<&str> = a.values().cloned().collect();
158    /// assert_eq!(values, ["hello", "goodbye"]);
159    /// ```
160    pub fn values(&self) -> Values<'_, K, V> {
161        Values(self.iter())
162    }
163
164    /// Gets a mutable iterator over the values of the map, in order by their
165    /// range.
166    ///
167    /// # Examples
168    ///
169    /// Basic usage:
170    ///
171    /// ```
172    /// use std::collections::BTreeMap;
173    ///
174    /// let mut a = BTreeMap::new();
175    /// a.insert(1, String::from("hello"));
176    /// a.insert(2, String::from("goodbye"));
177    ///
178    /// for value in a.values_mut() {
179    ///     value.push_str("!");
180    /// }
181    ///
182    /// let values: Vec<String> = a.values().cloned().collect();
183    /// assert_eq!(values, [String::from("hello!"),
184    ///                     String::from("goodbye!")]);
185    /// ```
186    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
187        ValuesMut(self.iter_mut())
188    }
189
190    // fn range_bounds(&self) -> R?
191
192    // TODO: remove K: Clone?
193    pub fn iter_subset<R>(&self, range: R) -> IterSubset<'_, K, V>
194    where
195        R: RangeBounds<K>,
196        K: Clone + Ord,
197    {
198        let range = Segment::new(range.start_bound(), range.end_bound()).cloned();
199        IterSubset(Some(match (&range.start, &range.end) {
200            (Start(Unbounded), End(Unbounded)) => IterSubsetInner::Full(self.iter()),
201            (Start(Unbounded), bounded_end) => IterSubsetInner::Partial {
202                before: None,
203                iter: self.map.range(..bounded_end.after().unwrap().cloned()),
204                range,
205            },
206            (bounded_start, End(Unbounded)) => IterSubsetInner::Partial {
207                before: Some(self.map.range(..bounded_start.clone())),
208                iter: self.map.range(bounded_start.clone()..),
209                range,
210            },
211            (bounded_start, bounded_end) => IterSubsetInner::Partial {
212                before: Some(self.map.range(..bounded_start.clone())),
213                iter: self
214                    .map
215                    .range(bounded_start.clone()..bounded_end.after().unwrap().cloned()),
216                range,
217            },
218        }))
219    }
220
221    /// Create a `SegmentMap` referencing a subset range in `self`
222    pub fn subset<R>(&self, range: R) -> SegmentMap<K, &V>
223    where
224        R: RangeBounds<K>,
225        K: Clone + Ord,
226    {
227        SegmentMap {
228            map: self.iter_subset(range).map(|(r, v)| (Key(r), v)).collect(),
229            store: alloc::vec::Vec::with_capacity(self.store.len()),
230        }
231    }
232
233    pub fn iter_complement(&self) -> IterComplement<'_, K, V> {
234        IterComplement(Some(ComplementInner::Before {
235            first: self.ranges().next(),
236            iter: self.iter(),
237        }))
238    }
239
240    pub fn complement(&self) -> SegmentSet<&K>
241    where
242        K: Ord,
243    {
244        SegmentSet {
245            map: SegmentMap {
246                map: self.iter_complement().map(|r| (Key(r), ())).collect(),
247                store: alloc::vec::Vec::with_capacity(self.store.len()),
248            },
249        }
250    }
251
252    /// Gets an iterator over all maximally-sized gaps between ranges in the map
253    ///
254    /// NOTE: Empty regions before and after those stored in this map (i.e.
255    /// before the first range and after the last range) will not be included
256    /// in this iterator
257    pub fn iter_gaps(&self) -> Gaps<'_, K, V> {
258        Gaps {
259            iter: self.iter(),
260            prev: None,
261        }
262    }
263
264    pub fn gaps(&self) -> SegmentSet<&K>
265    where
266        K: Ord,
267    {
268        SegmentSet {
269            map: SegmentMap {
270                map: self.iter_gaps().map(|r| (Key(r), ())).collect(),
271                store: alloc::vec::Vec::with_capacity(self.store.len()),
272            },
273        }
274    }
275
276    // /// Gets an iterator over all maximally-sized gaps between ranges in the map,
277    // /// further bounded by an outer range
278    // ///
279    // /// NOTE: Unlike [`gaps`], the iterator here WILL include regions before and
280    // /// after those stored in the map, so long as they are included in the outer
281    // /// range
282    // pub fn gaps_in<'a, R: 'a + core::ops::RangeBounds<K>>(
283    //     &'a self,
284    //     range: R,
285    // ) -> GapsIn<'a, K, V, R> {
286    //     // TODO: why can't we borrow start/end and make `bounds` a Range<&'a T>?
287    //     GapsIn {
288    //         iter: self.iter(),
289    //         prev: None,
290    //         bounds: range,
291    //     }
292    // }
293}
294
295impl<K, V> IntoIterator for SegmentMap<K, V> {
296    type Item = (Segment<K>, V);
297    type IntoIter = IntoIter<K, V>;
298    fn into_iter(self) -> Self::IntoIter {
299        IntoIter(self.map.into_iter())
300    }
301}
302impl<'a, K, V> IntoIterator for &'a SegmentMap<K, V> {
303    type Item = (&'a Segment<K>, &'a V);
304    type IntoIter = Iter<'a, K, V>;
305    fn into_iter(self) -> Iter<'a, K, V> {
306        self.iter()
307    }
308}
309impl<'a, K, V> IntoIterator for &'a mut SegmentMap<K, V> {
310    type Item = (&'a Segment<K>, &'a mut V);
311    type IntoIter = IterMut<'a, K, V>;
312    fn into_iter(self) -> IterMut<'a, K, V> {
313        self.iter_mut()
314    }
315}
316
317impl<R: core::ops::RangeBounds<K>, K: Clone + Ord, V: Clone + Eq> FromIterator<(R, V)>
318    for SegmentMap<K, V>
319{
320    fn from_iter<T: IntoIterator<Item = (R, V)>>(iter: T) -> Self {
321        let mut map = Self::new();
322        map.extend(iter);
323        map
324    }
325}
326
327impl<R, K, V> Extend<(R, V)> for SegmentMap<K, V>
328where
329    R: core::ops::RangeBounds<K>,
330    K: Clone + Ord,
331    V: Clone + Eq,
332{
333    #[inline]
334    fn extend<T: IntoIterator<Item = (R, V)>>(&mut self, iter: T) {
335        iter.into_iter().for_each(move |(k, v)| {
336            self.set(k, v);
337        });
338    }
339}
340
341/// An iterator over the entries of a `SegmentMap`.
342///
343/// This `struct` is created by the [`iter`] method on [`SegmentMap`]. See its
344/// documentation for more.
345///
346/// [`iter`]: SegmentMap::iter
347pub struct Iter<'a, K, V>(alloc::collections::btree_map::Iter<'a, Key<K>, V>);
348
349impl<K: Debug, V: Debug> Debug for Iter<'_, K, V> {
350    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
351        f.debug_list().entries(self.clone()).finish()
352    }
353}
354
355impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
356    type Item = (&'a Segment<K>, &'a V);
357    fn next(&mut self) -> Option<(&'a Segment<K>, &'a V)> {
358        self.0.next().map(|(wrapper, v)| (&wrapper.0, v))
359    }
360    fn size_hint(&self) -> (usize, Option<usize>) {
361        self.0.size_hint()
362    }
363    fn last(mut self) -> Option<(&'a Segment<K>, &'a V)> {
364        self.next_back()
365    }
366    fn min(mut self) -> Option<(&'a Segment<K>, &'a V)> {
367        self.next()
368    }
369    fn max(mut self) -> Option<(&'a Segment<K>, &'a V)> {
370        self.next_back()
371    }
372}
373impl<K, V> FusedIterator for Iter<'_, K, V> {}
374
375impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
376    fn next_back(&mut self) -> Option<(&'a Segment<K>, &'a V)> {
377        self.0.next_back().map(|(wrapper, v)| (&wrapper.0, v))
378    }
379}
380impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
381    fn len(&self) -> usize {
382        self.0.len()
383    }
384}
385impl<K, V> Clone for Iter<'_, K, V> {
386    fn clone(&self) -> Self {
387        Self(self.0.clone())
388    }
389}
390
391/// An iterator over the entries of a `SegmentMap`.
392///
393/// This `struct` is created by the [`iter`] method on [`SegmentMap`]. See its
394/// documentation for more.
395///
396/// [`iter`]: SegmentMap::iter
397pub struct IterIn<'a, K, V> {
398    iter: Iter<'a, K, V>,
399    range: Segment<K>,
400}
401
402impl<K: Clone + Ord + Debug, V: Debug> Debug for IterIn<'_, K, V> {
403    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
404        f.debug_list().entries(self.clone()).finish()
405    }
406}
407
408impl<'a, K: 'a + Ord, V: 'a> Iterator for IterIn<'a, K, V> {
409    type Item = (&'a Segment<K>, &'a V);
410    fn next(&mut self) -> Option<(&'a Segment<K>, &'a V)> {
411        loop {
412            let next = self.iter.next()?;
413            if next.0.overlaps(&self.range) {
414                return Some(next);
415            }
416        }
417    }
418    fn last(mut self) -> Option<(&'a Segment<K>, &'a V)> {
419        self.next_back()
420    }
421    fn min(mut self) -> Option<(&'a Segment<K>, &'a V)> {
422        self.next()
423    }
424    fn max(mut self) -> Option<(&'a Segment<K>, &'a V)> {
425        self.next_back()
426    }
427}
428impl<K: Ord, V> FusedIterator for IterIn<'_, K, V> {}
429
430impl<'a, K: 'a + Ord, V: 'a> DoubleEndedIterator for IterIn<'a, K, V> {
431    fn next_back(&mut self) -> Option<(&'a Segment<K>, &'a V)> {
432        loop {
433            let next = self.iter.next_back()?;
434            if next.0.overlaps(&self.range) {
435                return Some(next);
436            }
437        }
438    }
439}
440impl<K: Ord, V> ExactSizeIterator for IterIn<'_, K, V> {
441    fn len(&self) -> usize {
442        self.iter.len()
443    }
444}
445impl<K: Clone, V> Clone for IterIn<'_, K, V> {
446    fn clone(&self) -> Self {
447        Self {
448            iter: self.iter.clone(),
449            range: self.range.clone(),
450        }
451    }
452}
453
454/// A mutable iterator over the entries of a `SegmentMap`.
455///
456/// This `struct` is created by the [`iter_mut`] method on [`SegmentMap`]. See its
457/// documentation for more.
458///
459/// [`iter_mut`]: SegmentMap::iter_mut
460pub struct IterMut<'a, K: 'a, V: 'a>(alloc::collections::btree_map::IterMut<'a, Key<K>, V>);
461
462impl<K: Debug, V: Debug> Debug for IterMut<'_, K, V> {
463    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
464        self.0.fmt(f)
465    }
466}
467
468impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
469    type Item = (&'a Segment<K>, &'a mut V);
470
471    fn next(&mut self) -> Option<(&'a Segment<K>, &'a mut V)> {
472        self.0.next().map(|(wrapper, v)| (&wrapper.0, v))
473    }
474
475    fn size_hint(&self) -> (usize, Option<usize>) {
476        self.0.size_hint()
477    }
478
479    fn last(mut self) -> Option<(&'a Segment<K>, &'a mut V)> {
480        self.next_back()
481    }
482
483    fn min(mut self) -> Option<(&'a Segment<K>, &'a mut V)> {
484        self.next()
485    }
486
487    fn max(mut self) -> Option<(&'a Segment<K>, &'a mut V)> {
488        self.next_back()
489    }
490}
491
492impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
493    fn next_back(&mut self) -> Option<(&'a Segment<K>, &'a mut V)> {
494        self.0.next_back().map(|(wrapper, v)| (&wrapper.0, v))
495    }
496}
497
498impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
499    fn len(&self) -> usize {
500        self.0.len()
501    }
502}
503
504impl<K, V> FusedIterator for IterMut<'_, K, V> {}
505
506// impl<'a, K, V> IterMut<'a, K, V> {
507//     /// Returns an iterator of references over the remaining items.
508//     #[inline]
509//     pub(super) fn iter(&self) -> Iter<'_, K, V> {
510//         Iter(self.0.iter())
511//     }
512// }
513
514/// An owning iterator over the entries of a `SegmentMap`.
515///
516/// This `struct` is created by the [`into_iter`] method on [`SegmentMap`]
517/// (provided by the `IntoIterator` trait). See its documentation for more.
518///
519/// [`into_iter`]: IntoIterator::into_iter
520pub struct IntoIter<K, V>(alloc::collections::btree_map::IntoIter<Key<K>, V>);
521impl<K: Debug, V: Debug> Debug for IntoIter<K, V> {
522    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
523        self.0.fmt(f)
524    }
525}
526impl<K, V> Iterator for IntoIter<K, V> {
527    type Item = (Segment<K>, V);
528    fn next(&mut self) -> Option<(Segment<K>, V)> {
529        self.0.next().map(|(wrapper, v)| (wrapper.0, v))
530    }
531    fn size_hint(&self) -> (usize, Option<usize>) {
532        self.0.size_hint()
533    }
534}
535impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
536    fn next_back(&mut self) -> Option<(Segment<K>, V)> {
537        self.0.next_back().map(|(wrapper, v)| (wrapper.0, v))
538    }
539}
540impl<K, V> ExactSizeIterator for IntoIter<K, V> {
541    fn len(&self) -> usize {
542        self.0.len()
543    }
544}
545impl<K, V> FusedIterator for IntoIter<K, V> {}
546// impl<K, V> IntoIter<K, V> {
547//     #[inline]
548//     pub(super) fn iter(&self) -> Iter<'_, K, V> {
549//         Iter(self.)
550//     }
551// }
552
553/// An iterator over the keys of a `SegmentMap`.
554///
555/// This `struct` is created by the [`keys`] method on [`SegmentMap`]. See its
556/// documentation for more.
557///
558/// [`keys`]: SegmentMap::keys
559pub struct Ranges<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
560impl<K: Debug, V> Debug for Ranges<'_, K, V> {
561    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
562        f.debug_list().entries(self.clone()).finish()
563    }
564}
565impl<'a, K, V> Iterator for Ranges<'a, K, V> {
566    type Item = &'a Segment<K>;
567    fn next(&mut self) -> Option<&'a Segment<K>> {
568        self.0.next().map(|(k, _)| k)
569    }
570    fn size_hint(&self) -> (usize, Option<usize>) {
571        self.0.size_hint()
572    }
573    fn last(mut self) -> Option<&'a Segment<K>> {
574        self.next_back()
575    }
576    fn min(mut self) -> Option<&'a Segment<K>> {
577        self.next()
578    }
579    fn max(mut self) -> Option<&'a Segment<K>> {
580        self.next_back()
581    }
582}
583impl<'a, K, V> DoubleEndedIterator for Ranges<'a, K, V> {
584    fn next_back(&mut self) -> Option<&'a Segment<K>> {
585        self.0.next_back().map(|(k, _)| k)
586    }
587}
588impl<K, V> ExactSizeIterator for Ranges<'_, K, V> {
589    fn len(&self) -> usize {
590        self.0.len()
591    }
592}
593impl<K, V> FusedIterator for Ranges<'_, K, V> {}
594
595impl<K, V> Clone for Ranges<'_, K, V> {
596    fn clone(&self) -> Self {
597        Ranges(self.0.clone())
598    }
599}
600
601/// An iterator over the values of a `SegmentMap`.
602///
603/// This `struct` is created by the [`values`] method on [`SegmentMap`]. See its
604/// documentation for more.
605///
606/// [`values`]: SegmentMap::values
607#[derive(Clone)]
608pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
609
610// TODO: Debug Impl
611// impl<K, V: Debug> Debug for Values<'_, K, V> {
612//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
613//         f.debug_list().entries(self.clone()).finish()
614//     }
615// }
616
617impl<'a, K, V> Iterator for Values<'a, K, V> {
618    type Item = &'a V;
619    fn next(&mut self) -> Option<&'a V> {
620        self.0.next().map(|(_, v)| v)
621    }
622    fn size_hint(&self) -> (usize, Option<usize>) {
623        self.0.size_hint()
624    }
625    fn last(mut self) -> Option<&'a V> {
626        self.next_back()
627    }
628}
629impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
630    fn next_back(&mut self) -> Option<&'a V> {
631        self.0.next_back().map(|(_, v)| v)
632    }
633}
634impl<K, V> ExactSizeIterator for Values<'_, K, V> {
635    fn len(&self) -> usize {
636        self.0.len()
637    }
638}
639impl<K, V> FusedIterator for Values<'_, K, V> {}
640
641/// A mutable iterator over the values of a `SegmentMap`.
642///
643/// This `struct` is created by the [`values_mut`] method on [`SegmentMap`]. See its
644/// documentation for more.
645///
646/// [`values_mut`]: SegmentMap::values_mut
647pub struct ValuesMut<'a, K: 'a, V: 'a>(IterMut<'a, K, V>);
648
649// TODO: Debug Impl
650// impl<K, V: Debug> Debug for ValuesMut<'_, K, V> {
651//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
652//         f.debug_list()
653//             .entries(self.iter().map(|(_, val)| val))
654//             .finish()
655//     }
656// }
657
658impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
659    type Item = &'a mut V;
660    fn next(&mut self) -> Option<&'a mut V> {
661        self.0.next().map(|(_, v)| v)
662    }
663    fn size_hint(&self) -> (usize, Option<usize>) {
664        self.0.size_hint()
665    }
666    fn last(mut self) -> Option<&'a mut V> {
667        self.next_back()
668    }
669}
670impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
671    fn next_back(&mut self) -> Option<&'a mut V> {
672        self.0.next_back().map(|(_, v)| v)
673    }
674}
675impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
676    fn len(&self) -> usize {
677        self.0.len()
678    }
679}
680impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
681
682pub struct IterSubset<'a, K, V>(Option<IterSubsetInner<'a, K, V>>);
683
684enum IterSubsetInner<'a, K, V> {
685    Full(Iter<'a, K, V>),
686
687    Partial {
688        before: Option<alloc::collections::btree_map::Range<'a, Key<K>, V>>,
689        iter: alloc::collections::btree_map::Range<'a, Key<K>, V>,
690        range: Segment<K>,
691    },
692}
693
694impl<'a, K: Clone + Ord, V> Iterator for IterSubset<'a, K, V> {
695    type Item = (Segment<K>, &'a V);
696    fn next(&mut self) -> Option<Self::Item> {
697        match self.0.take()? {
698            IterSubsetInner::Full(mut iter) => {
699                let next = iter.next().map(|(r, v)| (r.clone(), v));
700                if next.is_some() {
701                    self.0.insert(IterSubsetInner::Full(iter));
702                }
703                next
704            }
705            IterSubsetInner::Partial {
706                mut before,
707                mut iter,
708                range,
709            } => {
710                // Check the first previous range from start to see if it
711                // overlaps the given outer range, consuming `before` as there
712                // will only be 1 options there
713                if let Some((Key(r), v)) = before.take().map(|mut x| x.next_back()).flatten() {
714                    let mut r = r.clone();
715
716                    // Check if this overlaps the outer range
717                    // (range iterator means this must start before range start)
718                    if r.end.cmp_start(&range.start).is_gt() {
719                        if r.start < range.start {
720                            r.start = range.start.clone();
721                        };
722
723                        self.0.insert(IterSubsetInner::Partial {
724                            before: None,
725                            iter,
726                            range,
727                        });
728                        return Some((r, v));
729                    }
730                }
731
732                // Otherwise, continue marching through `iter` until we reach
733                // `range.end`
734                let (Key(r), v) = iter.next()?;
735                let mut r = r.clone();
736
737                if r.start.as_ref() > range.end.after().unwrap() {
738                    // Finished!
739                    None
740                } else {
741                    if r.end > range.end {
742                        // If this extends past the end, it must be our last item
743                        r.end = range.end;
744                    } else {
745                        // Otherwise, save everything for next iteration
746                        self.0.insert(IterSubsetInner::Partial {
747                            before: None,
748                            iter,
749                            range,
750                        });
751                    }
752
753                    Some((r, v))
754                }
755            }
756        }
757    }
758}
759
760pub struct Gaps<'a, K, V> {
761    iter: Iter<'a, K, V>,
762    prev: Option<Segment<&'a K>>,
763}
764
765impl<'a, K, V> Iterator for Gaps<'a, K, V>
766where
767    K: Ord,
768{
769    type Item = Segment<&'a K>;
770    fn next(&mut self) -> Option<Self::Item> {
771        let next = self.iter.next()?.0.as_ref();
772
773        if let Some(prev) = self.prev.take() {
774            // Get the adjacent bound to the end of the previous range
775
776            let start = prev.bound_after()?.cloned(); // If none, no more gaps (this extends forwards to infinity)
777            let end = next
778                .bound_before()
779                .expect("Unbounded internal range in SegmentMap")
780                .cloned();
781            self.prev.insert(next);
782            Some(Segment { start, end })
783        } else {
784            // No previous bound means first gap
785
786            // Get the adjacent bound to the end of the first range
787            // If none, no more gaps (this extends forwards to infinity)
788            let start = next.borrow_bound_after()?;
789
790            // Check if we have another range, otherwise only one item (no gaps)
791            let next = self.iter.next()?.0.as_ref();
792
793            // Store the end of the next segment for next iteration
794            // This bound should always exist, because this is not the first
795            // range
796            let end = next.borrow_bound_before().unwrap();
797
798            // Hold on to next
799            self.prev = Some(next);
800            Some(Segment { start, end })
801        }
802    }
803}
804
805impl<K: Ord, V> FusedIterator for Gaps<'_, K, V> {}
806
807pub struct IterComplement<'a, K, V>(Option<ComplementInner<'a, K, V>>);
808enum ComplementInner<'a, K, V> {
809    Before {
810        first: Option<&'a Segment<K>>,
811        iter: Iter<'a, K, V>,
812    },
813    Gaps(Gaps<'a, K, V>), // TODO: make gaps generic over iterator? Then Before can use Peekable
814}
815
816impl<'a, K, V> Iterator for IterComplement<'a, K, V>
817where
818    K: Ord,
819{
820    type Item = Segment<&'a K>;
821    fn next(&mut self) -> Option<Self::Item> {
822        match self.0.take()? {
823            ComplementInner::Before { first, iter } => {
824                if let Some(first) = first {
825                    let mut gaps = Gaps { iter, prev: None };
826                    let out = first
827                        .bound_before()
828                        .map(|end| Segment {
829                            start: Start(Unbounded),
830                            end,
831                        })
832                        .or_else(|| gaps.next());
833
834                    self.0.insert(ComplementInner::Gaps(gaps));
835                    out
836                } else {
837                    None
838                }
839            }
840
841            // Use Gaps iterator to iterate all inner gaps
842            ComplementInner::Gaps(mut gaps) => {
843                if let Some(next) = gaps.next() {
844                    // In the gaps iterator
845                    self.0.insert(ComplementInner::Gaps(gaps));
846                    Some(next)
847                } else {
848                    // After the last item in gaps, try to use the `prev`
849                    // element to get the end bound, otherwise no more gaps!
850                    gaps.prev
851                        .map(|p| {
852                            p.borrow_bound_after().map(|start| Segment {
853                                start,
854                                end: End(Unbounded),
855                            })
856                        })
857                        .flatten()
858                }
859            }
860        }
861    }
862}
863
864// pub struct GapsIn<'a, K, V, R> {
865//     iter: Iter<'a, K, V>,
866//     prev: Option<&'a Range<K>>,
867//     bounds: R,
868// }
869
870// impl<'a, K, V, R> Iterator for GapsIn<'a, K, V, R>
871// where
872//     K: Ord,
873//     R: core::ops::RangeBounds<K>,
874// {
875//     type Item = Range<&'a K>;
876//     fn next(&mut self) -> Option<Self::Item> {
877//         todo!();
878
879//         // if let Some((next, _)) = self.iter.next() {
880//         //     if let Some(prev) = self.prev {
881//         //         // Get the adjacent bound to the end of the previous range
882
883//         //         let start = prev.bound_after()?.cloned(); // If none, no more gaps (this extends forwards to infinity)
884//         //         let end = next
885//         //             .bound_before()
886//         //             .expect("Unbounded internal range in SegmentMap")
887//         //             .cloned();
888//         //         self.prev = Some(next);
889//         //         Some(Range { start, end })
890//         //     } else {
891//         //         // No previous bound means first gap
892
893//         //         // Get the adjacent bound to the end of the first range
894//         //         let start = next.bound_after()?.cloned(); // If none, no more gaps (this extends forwards to infinity)
895
896//         //         // Check if we have another range
897//         //         if let Some((next, _)) = self.iter.next() {
898//         //             // Store the end of the next segment for next iteration
899//         //             let end = next
900//         //                 .bound_before()
901//         //                 .expect("Unbounded internal range in SegmentMap")
902//         //                 .cloned();
903
904//         //             self.prev = Some(next);
905//         //             Some(Range { start, end })
906//         //         } else {
907//         //             // Only one item (no gaps)
908//         //             None
909//         //         }
910//         //     }
911//         // } else {
912//         //     None
913//         // }
914//     }
915// }
916
917// impl<K: Clone + Ord, V, R: core::ops::RangeBounds<K>> FusedIterator for GapsIn<'_, K, V, R> {}
segmap/map/iterators.rs

segmap/map/
iterators.rs
