rangemap/
map.rs

1use super::range_wrapper::RangeStartWrapper;
2use crate::range_wrapper::RangeEndWrapper;
3use crate::std_ext::*;
4use alloc::collections::BTreeMap;
5use core::borrow::Borrow;
6use core::cmp::Ordering;
7use core::fmt::{self, Debug};
8use core::hash::Hash;
9use core::iter::{DoubleEndedIterator, FromIterator};
10use core::ops::{Bound, Range};
11use core::prelude::v1::*;
12
13#[cfg(feature = "serde1")]
14use core::marker::PhantomData;
15#[cfg(feature = "serde1")]
16use serde::{
17    de::{Deserialize, Deserializer, SeqAccess, Visitor},
18    ser::{Serialize, Serializer},
19};
20
21/// A map whose keys are stored as (half-open) ranges bounded
22/// inclusively below and exclusively above `(start..end)`.
23///
24/// Contiguous and overlapping ranges that map to the same value
25/// are coalesced into a single range.
26#[derive(Clone, Eq)]
27pub struct RangeMap<K, V> {
28    // Wrap ranges so that they are `Ord`.
29    // See `range_wrapper.rs` for explanation.
30    pub(crate) btm: BTreeMap<RangeStartWrapper<K>, V>,
31}
32
33impl<K, V> Default for RangeMap<K, V> {
34    fn default() -> Self {
35        Self {
36            btm: BTreeMap::default(),
37        }
38    }
39}
40
41impl<K, V> Hash for RangeMap<K, V>
42where
43    K: Hash,
44    V: Hash,
45{
46    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
47        state.write_usize(self.btm.len());
48        for elt in self.iter() {
49            elt.hash(state);
50        }
51    }
52}
53
54impl<K, V> PartialEq for RangeMap<K, V>
55where
56    K: PartialEq,
57    V: PartialEq,
58{
59    fn eq(&self, other: &RangeMap<K, V>) -> bool {
60        self.iter().eq(other.iter())
61    }
62}
63
64impl<K, V> PartialOrd for RangeMap<K, V>
65where
66    K: PartialOrd,
67    V: PartialOrd,
68{
69    #[inline]
70    fn partial_cmp(&self, other: &RangeMap<K, V>) -> Option<Ordering> {
71        self.expanded_iter().partial_cmp(other.expanded_iter())
72    }
73}
74
75impl<K, V> Ord for RangeMap<K, V>
76where
77    K: Ord,
78    V: Ord,
79{
80    #[inline]
81    fn cmp(&self, other: &RangeMap<K, V>) -> Ordering {
82        self.expanded_iter().cmp(other.expanded_iter())
83    }
84}
85
86#[cfg(feature = "quickcheck")]
87impl<K, V> quickcheck::Arbitrary for RangeMap<K, V>
88where
89    K: quickcheck::Arbitrary + Ord,
90    V: quickcheck::Arbitrary + PartialEq,
91{
92    fn arbitrary(g: &mut quickcheck::Gen) -> Self {
93        // REVISIT: allocation could be avoided if Gen::gen_size were public (https://github.com/BurntSushi/quickcheck/issues/326#issue-2653601170)
94        <alloc::vec::Vec<(Range<_>, _)>>::arbitrary(g)
95            .into_iter()
96            .filter(|(range, _)| !range.is_empty())
97            .collect()
98    }
99}
100
101impl<K, V> RangeMap<K, V> {
102    /// Makes a new empty `RangeMap`.
103    #[cfg(feature = "const_fn")]
104    pub const fn new() -> Self {
105        RangeMap {
106            btm: BTreeMap::new(),
107        }
108    }
109
110    /// Makes a new empty `RangeMap`.
111    #[cfg(not(feature = "const_fn"))]
112    pub fn new() -> Self {
113        RangeMap {
114            btm: BTreeMap::new(),
115        }
116    }
117
118    /// Gets an iterator over all pairs of key range and value,
119    /// ordered by key range.
120    ///
121    /// The iterator element type is `(&'a Range<K>, &'a V)`.
122    pub fn iter(&self) -> Iter<'_, K, V> {
123        Iter {
124            inner: self.btm.iter(),
125        }
126    }
127
128    /// Clears the map, removing all elements.
129    pub fn clear(&mut self) {
130        self.btm.clear();
131    }
132
133    /// Returns the number of elements in the map.
134    pub fn len(&self) -> usize {
135        self.btm.len()
136    }
137
138    /// Returns true if the map contains no elements.
139    pub fn is_empty(&self) -> bool {
140        self.btm.is_empty()
141    }
142
143    /// Returns an iterator that includes both ends of the key range.
144    ///
145    /// Mainly used for comparisons.
146    fn expanded_iter(&self) -> impl Iterator<Item = (&K, &K, &V)> {
147        self.btm.iter().map(|(k, v)| (&k.start, &k.end, v))
148    }
149}
150
151impl<K, V> RangeMap<K, V>
152where
153    K: Ord + Clone,
154{
155    /// Returns a reference to the value corresponding to the given key,
156    /// if the key is covered by any range in the map.
157    pub fn get(&self, key: &K) -> Option<&V> {
158        self.get_key_value(key).map(|(_range, value)| value)
159    }
160
161    /// Returns the range-value pair (as a pair of references) corresponding
162    /// to the given key, if the key is covered by any range in the map.
163    pub fn get_key_value(&self, key: &K) -> Option<(&Range<K>, &V)> {
164        // The only stored range that could contain the given key is the
165        // last stored range whose start is less than or equal to this key.
166        let key_as_start = RangeStartWrapper::new(key.clone()..key.clone());
167        self.btm
168            .range((Bound::Unbounded, Bound::Included(key_as_start)))
169            .next_back()
170            .filter(|(start_wrapper, _value)| {
171                // Does the only candidate range contain
172                // the requested key?
173                start_wrapper.end_wrapper.range.contains(key)
174            })
175            .map(|(start_wrapper, value)| (&start_wrapper.end_wrapper.range, value))
176    }
177
178    /// Returns `true` if any range in the map covers the specified key.
179    pub fn contains_key(&self, key: &K) -> bool {
180        self.get(key).is_some()
181    }
182
183    /// Gets an iterator over all the maximally-sized ranges
184    /// contained in `outer_range` that are not covered by
185    /// any range stored in the map.
186    ///
187    /// If the start and end of the outer range are the same
188    /// and it does not overlap any stored range, then a single
189    /// empty gap will be returned.
190    ///
191    /// The iterator element type is `Range<K>`.
192    pub fn gaps<'a>(&'a self, outer_range: &'a Range<K>) -> Gaps<'a, K, V> {
193        let overlap_iter = self.overlapping(outer_range);
194        Gaps {
195            candidate_start: &outer_range.start,
196            query_end: &outer_range.end,
197            btm_range_iter: overlap_iter.btm_range_iter,
198        }
199    }
200
201    /// Gets an iterator over all the stored ranges that are
202    /// either partially or completely overlapped by the given range.
203    pub fn overlapping<R: Borrow<Range<K>>>(&'_ self, range: R) -> Overlapping<'_, K, V, R> {
204        // Find the first matching stored range by its _end_,
205        // using sneaky layering and `Borrow` implementation. (See `range_wrappers` module.)
206        let start_sliver =
207            RangeEndWrapper::new(range.borrow().start.clone()..range.borrow().start.clone());
208        let btm_range_iter = self
209            .btm
210            .range::<RangeEndWrapper<K>, (Bound<&RangeEndWrapper<K>>, Bound<_>)>((
211                Bound::Excluded(&start_sliver),
212                Bound::Unbounded,
213            ));
214        Overlapping {
215            query_range: range,
216            btm_range_iter,
217        }
218    }
219
220    /// Returns `true` if any range in the map completely or partially
221    /// overlaps the given range.
222    pub fn overlaps(&self, range: &Range<K>) -> bool {
223        self.overlapping(range).next().is_some()
224    }
225
226    /// Returns the first range-value pair in this map, if one exists. The range in this pair is the
227    /// minimum range in the map.
228    pub fn first_range_value(&self) -> Option<(&Range<K>, &V)> {
229        self.btm
230            .first_key_value()
231            .map(|(range, value)| (&range.end_wrapper.range, value))
232    }
233
234    /// Returns the last range-value pair in this map, if one exists. The range in this pair is the
235    /// maximum range in the map.
236    pub fn last_range_value(&self) -> Option<(&Range<K>, &V)> {
237        self.btm
238            .last_key_value()
239            .map(|(range, value)| (&range.end_wrapper.range, value))
240    }
241}
242
243impl<K, V> RangeMap<K, V>
244where
245    K: Ord + Clone,
246    V: PartialEq + Clone,
247{
248    /// Insert a pair of key range and value into the map.
249    ///
250    /// If the inserted range partially or completely overlaps any
251    /// existing range in the map, then the existing range (or ranges) will be
252    /// partially or completely replaced by the inserted range.
253    ///
254    /// If the inserted range either overlaps or is immediately adjacent
255    /// any existing range _mapping to the same value_, then the ranges
256    /// will be coalesced into a single contiguous range.
257    ///
258    /// # Panics
259    ///
260    /// Panics if range `start >= end`.
261    pub fn insert(&mut self, range: Range<K>, value: V) {
262        // We don't want to have to make empty ranges make sense;
263        // they don't represent anything meaningful in this structure.
264        assert!(range.start < range.end);
265
266        // Wrap up the given range so that we can "borrow"
267        // it as a wrapper reference to either its start or end.
268        // See `range_wrapper.rs` for explanation of these hacks.
269        let mut new_start_wrapper: RangeStartWrapper<K> = RangeStartWrapper::new(range);
270        let new_value = value;
271
272        // Is there a stored range either overlapping the start of
273        // the range to insert or immediately preceding it?
274        //
275        // If there is any such stored range, it will be the last
276        // whose start is less than or equal to the start of the range to insert,
277        // or the one before that if both of the above cases exist.
278        let mut candidates = self
279            .btm
280            .range::<RangeStartWrapper<K>, (Bound<&RangeStartWrapper<K>>, Bound<&RangeStartWrapper<K>>)>((
281                Bound::Unbounded,
282                Bound::Included(&new_start_wrapper),
283            ))
284            .rev()
285            .take(2)
286            .filter(|(stored_start_wrapper, _stored_value)| {
287                // Does the candidate range either overlap
288                // or immediately precede the range to insert?
289                // (Remember that it might actually cover the _whole_
290                // range to insert and then some.)
291                stored_start_wrapper
292                    .end_wrapper
293                    .range
294                    .touches(&new_start_wrapper.end_wrapper.range)
295            });
296        if let Some(mut candidate) = candidates.next() {
297            // Or the one before it if both cases described above exist.
298            if let Some(another_candidate) = candidates.next() {
299                candidate = another_candidate;
300            }
301            let (stored_start_wrapper, stored_value) = (candidate.0.clone(), candidate.1.clone());
302            self.adjust_touching_ranges_for_insert(
303                stored_start_wrapper,
304                stored_value,
305                &mut new_start_wrapper.end_wrapper.range,
306                &new_value,
307            );
308        }
309
310        // Are there any stored ranges whose heads overlap or immediately
311        // follow the range to insert?
312        //
313        // If there are any such stored ranges (that weren't already caught above),
314        // their starts will fall somewhere after the start of the range to insert,
315        // and on or before its end.
316        //
317        // This time around, if the latter holds, it also implies
318        // the former so we don't need to check here if they touch.
319        //
320        // REVISIT: Possible micro-optimisation: `impl Borrow<T> for RangeStartWrapper<T>`
321        // and use that to search here, to avoid constructing another `RangeStartWrapper`.
322        let new_range_end_as_start = RangeStartWrapper::new(
323            new_start_wrapper.end_wrapper.range.end.clone()
324                ..new_start_wrapper.end_wrapper.range.end.clone(),
325        );
326        while let Some((stored_start_wrapper, stored_value)) = self
327            .btm
328            .range::<RangeStartWrapper<K>, (Bound<&RangeStartWrapper<K>>, Bound<&RangeStartWrapper<K>>)>((
329                Bound::Included(&new_start_wrapper),
330                Bound::Included(&new_range_end_as_start),
331            ))
332            .next()
333        {
334            // One extra exception: if we have different values,
335            // and the stored range starts at the end of the range to insert,
336            // then we don't want to keep looping forever trying to find more!
337            #[allow(clippy::suspicious_operation_groupings)]
338            if stored_start_wrapper.end_wrapper.range.start
339                == new_start_wrapper.end_wrapper.range.end
340                && *stored_value != new_value
341            {
342                // We're beyond the last stored range that could be relevant.
343                // Avoid wasting time on irrelevant ranges, or even worse, looping forever.
344                // (`adjust_touching_ranges_for_insert` below assumes that the given range
345                // is relevant, and behaves very poorly if it is handed a range that it
346                // shouldn't be touching.)
347                break;
348            }
349
350            let stored_start_wrapper = stored_start_wrapper.clone();
351            let stored_value = stored_value.clone();
352
353            self.adjust_touching_ranges_for_insert(
354                stored_start_wrapper,
355                stored_value,
356                &mut new_start_wrapper.end_wrapper.range,
357                &new_value,
358            );
359        }
360
361        // Insert the (possibly expanded) new range, and we're done!
362        self.btm.insert(new_start_wrapper, new_value);
363    }
364
365    /// Removes a range from the map, if all or any of it was present.
366    ///
367    /// If the range to be removed _partially_ overlaps any ranges
368    /// in the map, then those ranges will be contracted to no
369    /// longer cover the removed range.
370    ///
371    ///
372    /// # Panics
373    ///
374    /// Panics if range `start >= end`.
375    pub fn remove(&mut self, range: Range<K>) {
376        // We don't want to have to make empty ranges make sense;
377        // they don't represent anything meaningful in this structure.
378        assert!(range.start < range.end);
379
380        let start_wrapper: RangeStartWrapper<K> = RangeStartWrapper::new(range);
381        let range = &start_wrapper.end_wrapper.range;
382
383        // Is there a stored range overlapping the start of
384        // the range to insert?
385        //
386        // If there is any such stored range, it will be the last
387        // whose start is less than or equal to the start of the range to insert.
388        if let Some((stored_start_wrapper, stored_value)) = self
389            .btm
390            .range::<RangeStartWrapper<K>, (Bound<&RangeStartWrapper<K>>, Bound<&RangeStartWrapper<K>>)>((Bound::Unbounded, Bound::Included(&start_wrapper)))
391            .next_back()
392            .filter(|(stored_start_wrapper, _stored_value)| {
393                // Does the only candidate range overlap
394                // the range to insert?
395                stored_start_wrapper
396                    .end_wrapper
397                    .range
398                    .overlaps(range)
399            })
400            .map(|(stored_start_wrapper, stored_value)| {
401                (stored_start_wrapper.clone(), stored_value.clone())
402            })
403        {
404            self.adjust_overlapping_ranges_for_remove(
405                stored_start_wrapper,
406                stored_value,
407                range,
408            );
409        }
410
411        // Are there any stored ranges whose heads overlap the range to insert?
412        //
413        // If there are any such stored ranges (that weren't already caught above),
414        // their starts will fall somewhere after the start of the range to insert,
415        // and before its end.
416        //
417        // REVISIT: Possible micro-optimisation: `impl Borrow<T> for RangeStartWrapper<T>`
418        // and use that to search here, to avoid constructing another `RangeStartWrapper`.
419        let new_range_end_as_start = RangeStartWrapper::new(range.end.clone()..range.end.clone());
420        while let Some((stored_start_wrapper, stored_value)) = self
421            .btm
422            .range::<RangeStartWrapper<K>, (Bound<&RangeStartWrapper<K>>, Bound<&RangeStartWrapper<K>>)>((
423                Bound::Excluded(&start_wrapper),
424                Bound::Excluded(&new_range_end_as_start),
425            ))
426            .next()
427            .map(|(stored_start_wrapper, stored_value)| {
428                (stored_start_wrapper.clone(), stored_value.clone())
429            })
430        {
431            self.adjust_overlapping_ranges_for_remove(
432                stored_start_wrapper,
433                stored_value,
434                range,
435            );
436        }
437    }
438
439    fn adjust_touching_ranges_for_insert(
440        &mut self,
441        stored_start_wrapper: RangeStartWrapper<K>,
442        stored_value: V,
443        new_range: &mut Range<K>,
444        new_value: &V,
445    ) {
446        use core::cmp::{max, min};
447
448        if stored_value == *new_value {
449            // The ranges have the same value, so we can "adopt"
450            // the stored range.
451            //
452            // This means that no matter how big or where the stored range is,
453            // we will expand the new range's bounds to subsume it,
454            // and then delete the stored range.
455            new_range.start = min(&new_range.start, &stored_start_wrapper.start).clone();
456            new_range.end = max(&new_range.end, &stored_start_wrapper.end).clone();
457            self.btm.remove(&stored_start_wrapper);
458        } else {
459            // The ranges have different values.
460            if new_range.overlaps(&stored_start_wrapper.range) {
461                // The ranges overlap. This is a little bit more complicated.
462                // Delete the stored range, and then add back between
463                // 0 and 2 subranges at the ends of the range to insert.
464                self.btm.remove(&stored_start_wrapper);
465                if stored_start_wrapper.start < new_range.start {
466                    // Insert the piece left of the range to insert.
467                    self.btm.insert(
468                        RangeStartWrapper::new(
469                            stored_start_wrapper.end_wrapper.range.start..new_range.start.clone(),
470                        ),
471                        stored_value.clone(),
472                    );
473                }
474                if stored_start_wrapper.end_wrapper.range.end > new_range.end {
475                    // Insert the piece right of the range to insert.
476                    self.btm.insert(
477                        RangeStartWrapper::new(
478                            new_range.end.clone()..stored_start_wrapper.end_wrapper.range.end,
479                        ),
480                        stored_value,
481                    );
482                }
483            } else {
484                // No-op; they're not overlapping,
485                // so we can just keep both ranges as they are.
486            }
487        }
488    }
489
490    fn adjust_overlapping_ranges_for_remove(
491        &mut self,
492        stored: RangeStartWrapper<K>,
493        stored_value: V,
494        range_to_remove: &Range<K>,
495    ) {
496        // Delete the stored range, and then add back between
497        // 0 and 2 subranges at the ends of the range to insert.
498        self.btm.remove(&stored);
499        let stored_range = stored.end_wrapper;
500        if stored_range.start < range_to_remove.start {
501            // Insert the piece left of the range to insert.
502            self.btm.insert(
503                RangeStartWrapper::new(stored_range.range.start..range_to_remove.start.clone()),
504                stored_value.clone(),
505            );
506        }
507        if stored_range.range.end > range_to_remove.end {
508            // Insert the piece right of the range to insert.
509            self.btm.insert(
510                RangeStartWrapper::new(range_to_remove.end.clone()..stored_range.range.end),
511                stored_value,
512            );
513        }
514    }
515}
516
517/// An iterator over the entries of a `RangeMap`, ordered by key range.
518///
519/// The iterator element type is `(&'a Range<K>, &'a V)`.
520///
521/// This `struct` is created by the [`iter`] method on [`RangeMap`]. See its
522/// documentation for more.
523///
524/// [`iter`]: RangeMap::iter
525pub struct Iter<'a, K, V> {
526    inner: alloc::collections::btree_map::Iter<'a, RangeStartWrapper<K>, V>,
527}
528
529impl<'a, K, V> Iterator for Iter<'a, K, V>
530where
531    K: 'a,
532    V: 'a,
533{
534    type Item = (&'a Range<K>, &'a V);
535
536    fn next(&mut self) -> Option<Self::Item> {
537        self.inner
538            .next()
539            .map(|(by_start, v)| (&by_start.end_wrapper.range, v))
540    }
541
542    fn size_hint(&self) -> (usize, Option<usize>) {
543        self.inner.size_hint()
544    }
545}
546
547impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V>
548where
549    K: 'a,
550    V: 'a,
551{
552    fn next_back(&mut self) -> Option<Self::Item> {
553        self.inner
554            .next_back()
555            .map(|(range, value)| (&range.end_wrapper.range, value))
556    }
557}
558
559/// An owning iterator over the entries of a `RangeMap`, ordered by key range.
560///
561/// The iterator element type is `(Range<K>, V)`.
562///
563/// This `struct` is created by the [`into_iter`] method on [`RangeMap`]
564/// (provided by the `IntoIterator` trait). See its documentation for more.
565///
566/// [`into_iter`]: IntoIterator::into_iter
567pub struct IntoIter<K, V> {
568    inner: alloc::collections::btree_map::IntoIter<RangeStartWrapper<K>, V>,
569}
570
571impl<K, V> IntoIterator for RangeMap<K, V> {
572    type Item = (Range<K>, V);
573    type IntoIter = IntoIter<K, V>;
574    fn into_iter(self) -> Self::IntoIter {
575        IntoIter {
576            inner: self.btm.into_iter(),
577        }
578    }
579}
580
581impl<K, V> Iterator for IntoIter<K, V> {
582    type Item = (Range<K>, V);
583    fn next(&mut self) -> Option<(Range<K>, V)> {
584        self.inner
585            .next()
586            .map(|(by_start, v)| (by_start.end_wrapper.range, v))
587    }
588    fn size_hint(&self) -> (usize, Option<usize>) {
589        self.inner.size_hint()
590    }
591}
592
593impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
594    fn next_back(&mut self) -> Option<Self::Item> {
595        self.inner
596            .next_back()
597            .map(|(range, value)| (range.end_wrapper.range, value))
598    }
599}
600
601// We can't just derive this automatically, because that would
602// expose irrelevant (and private) implementation details.
603// Instead implement it in the same way that the underlying BTreeMap does.
604impl<K: Debug, V: Debug> Debug for RangeMap<K, V> {
605    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
606        f.debug_map().entries(self.iter()).finish()
607    }
608}
609
610impl<K, V> FromIterator<(Range<K>, V)> for RangeMap<K, V>
611where
612    K: Ord + Clone,
613    V: PartialEq + Clone,
614{
615    fn from_iter<T: IntoIterator<Item = (Range<K>, V)>>(iter: T) -> Self {
616        let mut range_map = RangeMap::new();
617        range_map.extend(iter);
618        range_map
619    }
620}
621
622impl<K, V> Extend<(Range<K>, V)> for RangeMap<K, V>
623where
624    K: Ord + Clone,
625    V: PartialEq + Clone,
626{
627    fn extend<T: IntoIterator<Item = (Range<K>, V)>>(&mut self, iter: T) {
628        iter.into_iter().for_each(move |(k, v)| {
629            self.insert(k, v);
630        })
631    }
632}
633
634#[cfg(feature = "serde1")]
635impl<K, V> Serialize for RangeMap<K, V>
636where
637    K: Serialize,
638    V: Serialize,
639{
640    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
641    where
642        S: Serializer,
643    {
644        use serde::ser::SerializeSeq;
645        let mut seq = serializer.serialize_seq(Some(self.btm.len()))?;
646        for (k, v) in self.iter() {
647            seq.serialize_element(&((&k.start, &k.end), &v))?;
648        }
649        seq.end()
650    }
651}
652
653#[cfg(feature = "serde1")]
654impl<'de, K, V> Deserialize<'de> for RangeMap<K, V>
655where
656    K: Ord + Clone + Deserialize<'de>,
657    V: PartialEq + Clone + Deserialize<'de>,
658{
659    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
660    where
661        D: Deserializer<'de>,
662    {
663        deserializer.deserialize_seq(RangeMapVisitor::new())
664    }
665}
666
667#[cfg(feature = "serde1")]
668struct RangeMapVisitor<K, V> {
669    marker: PhantomData<fn() -> RangeMap<K, V>>,
670}
671
672#[cfg(feature = "serde1")]
673impl<K, V> RangeMapVisitor<K, V> {
674    fn new() -> Self {
675        RangeMapVisitor {
676            marker: PhantomData,
677        }
678    }
679}
680
681#[cfg(feature = "serde1")]
682impl<'de, K, V> Visitor<'de> for RangeMapVisitor<K, V>
683where
684    K: Ord + Clone + Deserialize<'de>,
685    V: PartialEq + Clone + Deserialize<'de>,
686{
687    type Value = RangeMap<K, V>;
688
689    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
690        formatter.write_str("RangeMap")
691    }
692
693    fn visit_seq<A>(self, mut access: A) -> Result<Self::Value, A::Error>
694    where
695        A: SeqAccess<'de>,
696    {
697        let mut range_map = RangeMap::new();
698        while let Some(((start, end), value)) = access.next_element()? {
699            range_map.insert(start..end, value);
700        }
701        Ok(range_map)
702    }
703}
704
705/// An iterator over all ranges not covered by a `RangeMap`.
706///
707/// The iterator element type is `Range<K>`.
708///
709/// This `struct` is created by the [`gaps`] method on [`RangeMap`]. See its
710/// documentation for more.
711///
712/// [`gaps`]: RangeMap::gaps
713pub struct Gaps<'a, K, V> {
714    candidate_start: &'a K,
715    query_end: &'a K,
716    btm_range_iter: alloc::collections::btree_map::Range<'a, RangeStartWrapper<K>, V>,
717}
718
719// `Gaps` is always fused. (See definition of `next` below.)
720impl<'a, K, V> core::iter::FusedIterator for Gaps<'a, K, V> where K: Ord + Clone {}
721
722impl<'a, K, V> Iterator for Gaps<'a, K, V>
723where
724    K: Ord + Clone,
725{
726    type Item = Range<K>;
727
728    fn next(&mut self) -> Option<Self::Item> {
729        // Keep track of the next range in the map beyond the current returned range.
730        for overlap in self.btm_range_iter.by_ref() {
731            let overlap = &overlap.0.range;
732
733            // If the range in the map has advanced beyond the query range, return
734            // any tail gap.
735            if *self.query_end <= overlap.start {
736                break;
737            }
738
739            let original_start = core::mem::replace(&mut self.candidate_start, &overlap.end);
740
741            // The query range overhangs to the left, return a gap.
742            if *original_start < overlap.start {
743                let gap = original_start.clone()..overlap.start.clone();
744                return Some(gap);
745            }
746
747            // The remaining query range starts within the current
748            // mapped range.
749            self.candidate_start = &overlap.end;
750        }
751
752        // Now that we've run out of items, the only other possible
753        // gap is at the end of the query range.
754        if *self.candidate_start < *self.query_end {
755            let gap = self.candidate_start.clone()..self.query_end.clone();
756            self.candidate_start = self.query_end;
757            return Some(gap);
758        }
759
760        None
761    }
762}
763
764/// An iterator over all stored ranges partially or completely
765/// overlapped by a given range.
766///
767/// The iterator element type is `(&'a Range<K>, &'a V)`.
768///
769/// This `struct` is created by the [`overlapping`] method on [`RangeMap`]. See its
770/// documentation for more.
771///
772/// [`overlapping`]: RangeMap::overlapping
773pub struct Overlapping<'a, K, V, R: Borrow<Range<K>> = &'a Range<K>> {
774    query_range: R,
775    btm_range_iter: alloc::collections::btree_map::Range<'a, RangeStartWrapper<K>, V>,
776}
777
778// `Overlapping` is always fused. (See definition of `next` below.)
779impl<'a, K, V, R: Borrow<Range<K>>> core::iter::FusedIterator for Overlapping<'a, K, V, R> where
780    K: Ord
781{
782}
783
784impl<'a, K, V, R: Borrow<Range<K>>> Iterator for Overlapping<'a, K, V, R>
785where
786    K: Ord,
787{
788    type Item = (&'a Range<K>, &'a V);
789
790    fn next(&mut self) -> Option<Self::Item> {
791        if let Some((k, v)) = self.btm_range_iter.next() {
792            if k.start < self.query_range.borrow().end {
793                Some((&k.range, v))
794            } else {
795                // The rest of the items in the underlying iterator
796                // are past the query range. We can keep taking items
797                // from that iterator and this will remain true,
798                // so this is enough to make the iterator fused.
799                None
800            }
801        } else {
802            None
803        }
804    }
805}
806
807impl<'a, K, V, R: Borrow<Range<K>>> DoubleEndedIterator for Overlapping<'a, K, V, R>
808where
809    K: Ord,
810{
811    fn next_back(&mut self) -> Option<Self::Item> {
812        while let Some((k, v)) = self.btm_range_iter.next_back() {
813            if k.start < self.query_range.borrow().end {
814                return Some((&k.range, v));
815            }
816        }
817
818        None
819    }
820}
821
822impl<K: Ord + Clone, V: PartialEq + Clone, const N: usize> From<[(Range<K>, V); N]> for RangeMap<K, V> {
823    fn from(value: [(Range<K>, V); N]) -> Self {
824        let mut map = Self::new();
825        for (range, value) in IntoIterator::into_iter(value) {
826            map.insert(range, value);
827        }
828        map
829    }
830}
831
832/// Create a [`RangeMap`] from key-value pairs.
833///
834/// # Example
835///
836/// ```rust
837/// # use rangemap::range_map;
838/// let map = range_map!{
839///     0..100 => "abc",
840///     100..200 => "def",
841///     200..300 => "ghi"
842/// };
843/// ```
844#[macro_export]
845macro_rules! range_map {
846    ($($k:expr => $v:expr),* $(,)?) => {{
847        $crate::RangeMap::from([$(($k, $v)),*])
848    }};
849}
850
851#[cfg(test)]
852mod tests {
853    use super::*;
854    use alloc as std;
855    use alloc::{format, string::String, vec, vec::Vec};
856    use proptest::prelude::*;
857    use test_strategy::proptest;
858
859    impl<K, V> Arbitrary for RangeMap<K, V>
860    where
861        K: Ord + Clone + Debug + Arbitrary + 'static,
862        V: Clone + PartialEq + Arbitrary + 'static,
863    {
864        type Parameters = ();
865        type Strategy = BoxedStrategy<Self>;
866
867        fn arbitrary_with(_parameters: Self::Parameters) -> Self::Strategy {
868            any::<Vec<(Range<K>, V)>>()
869                .prop_map(|ranges| ranges.into_iter().collect::<RangeMap<K, V>>())
870                .boxed()
871        }
872    }
873
874    #[proptest]
875    fn test_first(set: RangeMap<u64, String>) {
876        assert_eq!(
877            set.first_range_value(),
878            set.iter().min_by_key(|(range, _)| range.start)
879        );
880    }
881
882    #[proptest]
883    #[allow(clippy::len_zero)]
884    fn test_len(mut map: RangeMap<u64, String>) {
885        assert_eq!(map.len(), map.iter().count());
886        assert_eq!(map.is_empty(), map.len() == 0);
887        map.clear();
888        assert_eq!(map.len(), 0);
889        assert!(map.is_empty());
890        assert_eq!(map.iter().count(), 0);
891    }
892
893    #[proptest]
894    fn test_last(set: RangeMap<u64, String>) {
895        assert_eq!(
896            set.last_range_value(),
897            set.iter().max_by_key(|(range, _)| range.end)
898        );
899    }
900
901    #[proptest]
902    fn test_iter_reversible(set: RangeMap<u64, String>) {
903        let forward: Vec<_> = set.iter().collect();
904        let mut backward: Vec<_> = set.iter().rev().collect();
905        backward.reverse();
906        assert_eq!(forward, backward);
907    }
908
909    #[proptest]
910    fn test_into_iter_reversible(set: RangeMap<u64, String>) {
911        let forward: Vec<_> = set.clone().into_iter().collect();
912        let mut backward: Vec<_> = set.into_iter().rev().collect();
913        backward.reverse();
914        assert_eq!(forward, backward);
915    }
916
917    #[proptest]
918    fn test_overlapping_reversible(set: RangeMap<u64, String>, range: Range<u64>) {
919        let forward: Vec<_> = set.overlapping(&range).collect();
920        let mut backward: Vec<_> = set.overlapping(&range).rev().collect();
921        backward.reverse();
922        assert_eq!(forward, backward);
923    }
924
925    #[proptest]
926    fn test_arbitrary_map_u8(ranges: Vec<(Range<u8>, String)>) {
927        let ranges: Vec<_> = ranges
928            .into_iter()
929            .filter(|(range, _value)| range.start != range.end)
930            .collect();
931        let set = ranges
932            .iter()
933            .fold(RangeMap::new(), |mut set, (range, value)| {
934                set.insert(range.clone(), value.clone());
935                set
936            });
937
938        for value in 0..u8::MAX {
939            assert_eq!(
940                set.get(&value),
941                ranges
942                    .iter()
943                    .rev()
944                    .find(|(range, _value)| range.contains(&value))
945                    .map(|(_range, value)| value)
946            );
947        }
948    }
949
950    #[proptest]
951    #[allow(deprecated)]
952    fn test_hash(left: RangeMap<u64, u64>, right: RangeMap<u64, u64>) {
953        use core::hash::{Hash, Hasher, SipHasher};
954
955        let hash = |set: &RangeMap<_, _>| {
956            let mut hasher = SipHasher::new();
957            set.hash(&mut hasher);
958            hasher.finish()
959        };
960
961        if left == right {
962            assert!(
963                hash(&left) == hash(&right),
964                "if two values are equal, their hash must be equal"
965            );
966        }
967
968        // if the hashes are equal the values might not be the same (collision)
969        if hash(&left) != hash(&right) {
970            assert!(
971                left != right,
972                "if two value's hashes are not equal, they must not be equal"
973            );
974        }
975    }
976
977    #[proptest]
978    fn test_ord(left: RangeMap<u64, u64>, right: RangeMap<u64, u64>) {
979        assert_eq!(
980            left == right,
981            left.cmp(&right).is_eq(),
982            "ordering and equality must match"
983        );
984        assert_eq!(
985            left.cmp(&right),
986            left.partial_cmp(&right).unwrap(),
987            "ordering is total for ordered parameters"
988        );
989    }
990
991    #[test]
992    fn test_from_array() {
993        let mut map = RangeMap::new();
994        map.insert(0..100, "hello");
995        map.insert(200..300, "world");
996        assert_eq!(
997            map,
998            RangeMap::from([(0..100, "hello"), (200..300, "world")])
999        );
1000    }
1001
1002    #[test]
1003    fn test_macro() {
1004        assert_eq!(range_map![], RangeMap::<i64, i64>::default());
1005        assert_eq!(
1006            range_map!(0..100 => "abc", 100..200 => "def", 200..300 => "ghi"),
1007            [(0..100, "abc"), (100..200, "def"), (200..300, "ghi")]
1008                .iter()
1009                .cloned()
1010                .collect(),
1011        );
1012    }
1013
1014    trait RangeMapExt<K, V> {
1015        fn to_vec(&self) -> Vec<(Range<K>, V)>;
1016    }
1017
1018    impl<K, V> RangeMapExt<K, V> for RangeMap<K, V>
1019    where
1020        K: Ord + Clone,
1021        V: PartialEq + Clone,
1022    {
1023        fn to_vec(&self) -> Vec<(Range<K>, V)> {
1024            self.iter().map(|(kr, v)| (kr.clone(), v.clone())).collect()
1025        }
1026    }
1027
1028    //
1029    // Insertion tests
1030    //
1031
1032    #[test]
1033    fn empty_map_is_empty() {
1034        let range_map: RangeMap<u32, bool> = RangeMap::new();
1035        assert_eq!(range_map.to_vec(), vec![]);
1036    }
1037
1038    #[test]
1039    fn insert_into_empty_map() {
1040        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1041        range_map.insert(0..50, false);
1042        assert_eq!(range_map.to_vec(), vec![(0..50, false)]);
1043    }
1044
1045    #[test]
1046    fn new_same_value_immediately_following_stored() {
1047        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1048        // 0 1 2 3 4 5 6 7 8 9
1049        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1050        range_map.insert(1..3, false);
1051        // 0 1 2 3 4 5 6 7 8 9
1052        // ◌ ◌ ◌ ●---◌ ◌ ◌ ◌ ◌
1053        range_map.insert(3..5, false);
1054        // 0 1 2 3 4 5 6 7 8 9
1055        // ◌ ●-------◌ ◌ ◌ ◌ ◌
1056        assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
1057    }
1058
1059    #[test]
1060    fn new_different_value_immediately_following_stored() {
1061        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1062        // 0 1 2 3 4 5 6 7 8 9
1063        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1064        range_map.insert(1..3, false);
1065        // 0 1 2 3 4 5 6 7 8 9
1066        // ◌ ◌ ◌ ◆---◇ ◌ ◌ ◌ ◌
1067        range_map.insert(3..5, true);
1068        // 0 1 2 3 4 5 6 7 8 9
1069        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1070        // ◌ ◌ ◌ ◆---◇ ◌ ◌ ◌ ◌
1071        assert_eq!(range_map.to_vec(), vec![(1..3, false), (3..5, true)]);
1072    }
1073
1074    #[test]
1075    fn new_same_value_overlapping_end_of_stored() {
1076        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1077        // 0 1 2 3 4 5 6 7 8 9
1078        // ◌ ●-----◌ ◌ ◌ ◌ ◌ ◌
1079        range_map.insert(1..4, false);
1080        // 0 1 2 3 4 5 6 7 8 9
1081        // ◌ ◌ ◌ ●---◌ ◌ ◌ ◌ ◌
1082        range_map.insert(3..5, false);
1083        // 0 1 2 3 4 5 6 7 8 9
1084        // ◌ ●-------◌ ◌ ◌ ◌ ◌
1085        assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
1086    }
1087
1088    #[test]
1089    fn new_different_value_overlapping_end_of_stored() {
1090        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1091        // 0 1 2 3 4 5 6 7 8 9
1092        // ◌ ●-----◌ ◌ ◌ ◌ ◌ ◌
1093        range_map.insert(1..4, false);
1094        // 0 1 2 3 4 5 6 7 8 9
1095        // ◌ ◌ ◌ ◆---◇ ◌ ◌ ◌ ◌
1096        range_map.insert(3..5, true);
1097        // 0 1 2 3 4 5 6 7 8 9
1098        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1099        // ◌ ◌ ◌ ◆---◇ ◌ ◌ ◌ ◌
1100        assert_eq!(range_map.to_vec(), vec![(1..3, false), (3..5, true)]);
1101    }
1102
1103    #[test]
1104    fn new_same_value_immediately_preceding_stored() {
1105        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1106        // 0 1 2 3 4 5 6 7 8 9
1107        // ◌ ◌ ◌ ●---◌ ◌ ◌ ◌ ◌
1108        range_map.insert(3..5, false);
1109        // 0 1 2 3 4 5 6 7 8 9
1110        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1111        range_map.insert(1..3, false);
1112        // 0 1 2 3 4 5 6 7 8 9
1113        // ◌ ●-------◌ ◌ ◌ ◌ ◌
1114        assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
1115    }
1116
1117    #[test]
1118    fn new_different_value_immediately_preceding_stored() {
1119        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1120        // 0 1 2 3 4 5 6 7 8 9
1121        // ◌ ◌ ◌ ◆---◇ ◌ ◌ ◌ ◌
1122        range_map.insert(3..5, true);
1123        // 0 1 2 3 4 5 6 7 8 9
1124        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1125        range_map.insert(1..3, false);
1126        // 0 1 2 3 4 5 6 7 8 9
1127        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1128        // ◌ ◌ ◌ ◆---◇ ◌ ◌ ◌ ◌
1129        assert_eq!(range_map.to_vec(), vec![(1..3, false), (3..5, true)]);
1130    }
1131
1132    #[test]
1133    fn new_same_value_wholly_inside_stored() {
1134        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1135        // 0 1 2 3 4 5 6 7 8 9
1136        // ◌ ●-------◌ ◌ ◌ ◌ ◌
1137        range_map.insert(1..5, false);
1138        // 0 1 2 3 4 5 6 7 8 9
1139        // ◌ ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1140        range_map.insert(2..4, false);
1141        // 0 1 2 3 4 5 6 7 8 9
1142        // ◌ ●-------◌ ◌ ◌ ◌ ◌
1143        assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
1144    }
1145
1146    #[test]
1147    fn new_different_value_wholly_inside_stored() {
1148        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1149        // 0 1 2 3 4 5 6 7 8 9
1150        // ◌ ◆-------◇ ◌ ◌ ◌ ◌
1151        range_map.insert(1..5, true);
1152        // 0 1 2 3 4 5 6 7 8 9
1153        // ◌ ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1154        range_map.insert(2..4, false);
1155        // 0 1 2 3 4 5 6 7 8 9
1156        // ◌ ●-◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌
1157        // ◌ ◌ ◆---◇ ◌ ◌ ◌ ◌ ◌
1158        // ◌ ◌ ◌ ◌ ●-◌ ◌ ◌ ◌ ◌
1159        assert_eq!(
1160            range_map.to_vec(),
1161            vec![(1..2, true), (2..4, false), (4..5, true)]
1162        );
1163    }
1164
1165    #[test]
1166    fn replace_at_end_of_existing_range_should_coalesce() {
1167        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1168        // 0 1 2 3 4 5 6 7 8 9
1169        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1170        range_map.insert(1..3, false);
1171        // 0 1 2 3 4 5 6 7 8 9
1172        // ◌ ◌ ◌ ●---◌ ◌ ◌ ◌ ◌
1173        range_map.insert(3..5, true);
1174        // 0 1 2 3 4 5 6 7 8 9
1175        // ◌ ◌ ◌ ●---◌ ◌ ◌ ◌ ◌
1176        range_map.insert(3..5, false);
1177        // 0 1 2 3 4 5 6 7 8 9
1178        // ◌ ●-------◌ ◌ ◌ ◌ ◌
1179        assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
1180    }
1181
1182    #[test]
1183    // Test every permutation of a bunch of touching and overlapping ranges.
1184    fn lots_of_interesting_ranges() {
1185        use crate::dense::DenseU32RangeMap;
1186        use permutator::Permutation;
1187
1188        let mut ranges_with_values = [
1189            (2..3, false),
1190            // A duplicate duplicates
1191            (2..3, false),
1192            // Almost a duplicate, but with a different value
1193            (2..3, true),
1194            // A few small ranges, some of them overlapping others,
1195            // some of them touching others
1196            (3..5, true),
1197            (4..6, true),
1198            (5..7, true),
1199            // A really big range
1200            (2..6, true),
1201        ];
1202
1203        ranges_with_values.permutation().for_each(|permutation| {
1204            let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1205            let mut dense: DenseU32RangeMap<bool> = DenseU32RangeMap::new();
1206
1207            for (k, v) in permutation {
1208                // Insert it into both maps.
1209                range_map.insert(k.clone(), v);
1210                // NOTE: Clippy's `range_minus_one` lint is a bit overzealous here,
1211                // because we _can't_ pass an open-ended range to `insert`.
1212                #[allow(clippy::range_minus_one)]
1213                dense.insert(k.start..=(k.end - 1), v);
1214
1215                // At every step, both maps should contain the same stuff.
1216                let sparse = range_map.to_vec();
1217                let dense = dense.to_end_exclusive_vec();
1218                assert_eq!(sparse, dense);
1219            }
1220        });
1221    }
1222
1223    //
1224    // Get* tests
1225    //
1226
1227    #[test]
1228    fn get() {
1229        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1230        range_map.insert(0..50, false);
1231        assert_eq!(range_map.get(&49), Some(&false));
1232        assert_eq!(range_map.get(&50), None);
1233    }
1234
1235    #[test]
1236    fn get_key_value() {
1237        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1238        range_map.insert(0..50, false);
1239        assert_eq!(range_map.get_key_value(&49), Some((&(0..50), &false)));
1240        assert_eq!(range_map.get_key_value(&50), None);
1241    }
1242
1243    //
1244    // Removal tests
1245    //
1246
1247    #[test]
1248    fn remove_from_empty_map() {
1249        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1250        range_map.remove(0..50);
1251        assert_eq!(range_map.to_vec(), vec![]);
1252    }
1253
1254    #[test]
1255    fn remove_non_covered_range_before_stored() {
1256        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1257        range_map.insert(25..75, false);
1258        range_map.remove(0..25);
1259        assert_eq!(range_map.to_vec(), vec![(25..75, false)]);
1260    }
1261
1262    #[test]
1263    fn remove_non_covered_range_after_stored() {
1264        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1265        range_map.insert(25..75, false);
1266        range_map.remove(75..100);
1267        assert_eq!(range_map.to_vec(), vec![(25..75, false)]);
1268    }
1269
1270    #[test]
1271    fn remove_overlapping_start_of_stored() {
1272        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1273        range_map.insert(25..75, false);
1274        range_map.remove(0..30);
1275        assert_eq!(range_map.to_vec(), vec![(30..75, false)]);
1276    }
1277
1278    #[test]
1279    fn remove_middle_of_stored() {
1280        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1281        range_map.insert(25..75, false);
1282        range_map.remove(30..70);
1283        assert_eq!(range_map.to_vec(), vec![(25..30, false), (70..75, false)]);
1284    }
1285
1286    #[test]
1287    fn remove_overlapping_end_of_stored() {
1288        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1289        range_map.insert(25..75, false);
1290        range_map.remove(70..100);
1291        assert_eq!(range_map.to_vec(), vec![(25..70, false)]);
1292    }
1293
1294    #[test]
1295    fn remove_exactly_stored() {
1296        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1297        range_map.insert(25..75, false);
1298        range_map.remove(25..75);
1299        assert_eq!(range_map.to_vec(), vec![]);
1300    }
1301
1302    #[test]
1303    fn remove_superset_of_stored() {
1304        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1305        range_map.insert(25..75, false);
1306        range_map.remove(0..100);
1307        assert_eq!(range_map.to_vec(), vec![]);
1308    }
1309
1310    // Gaps tests
1311
1312    #[test]
1313    fn whole_range_is_a_gap() {
1314        // 0 1 2 3 4 5 6 7 8 9
1315        // ◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌
1316        let range_map: RangeMap<u32, ()> = RangeMap::new();
1317        // 0 1 2 3 4 5 6 7 8 9
1318        // ◌ ◆-------------◇ ◌
1319        let outer_range = 1..8;
1320        let mut gaps = range_map.gaps(&outer_range);
1321        // Should yield the entire outer range.
1322        assert_eq!(gaps.next(), Some(1..8));
1323        assert_eq!(gaps.next(), None);
1324        // Gaps iterator should be fused.
1325        assert_eq!(gaps.next(), None);
1326        assert_eq!(gaps.next(), None);
1327    }
1328
1329    #[test]
1330    fn whole_range_is_covered_exactly() {
1331        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1332        // 0 1 2 3 4 5 6 7 8 9
1333        // ◌ ●---------◌ ◌ ◌ ◌
1334        range_map.insert(1..6, ());
1335        // 0 1 2 3 4 5 6 7 8 9
1336        // ◌ ◆---------◇ ◌ ◌ ◌
1337        let outer_range = 1..6;
1338        let mut gaps = range_map.gaps(&outer_range);
1339        // Should yield no gaps.
1340        assert_eq!(gaps.next(), None);
1341        // Gaps iterator should be fused.
1342        assert_eq!(gaps.next(), None);
1343        assert_eq!(gaps.next(), None);
1344    }
1345
1346    #[test]
1347    fn item_before_outer_range() {
1348        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1349        // 0 1 2 3 4 5 6 7 8 9
1350        // ◌ ●---◌ ◌ ◌ ◌ ◌ ◌ ◌
1351        range_map.insert(1..3, ());
1352        // 0 1 2 3 4 5 6 7 8 9
1353        // ◌ ◌ ◌ ◌ ◌ ◆-----◇ ◌
1354        let outer_range = 5..8;
1355        let mut gaps = range_map.gaps(&outer_range);
1356        // Should yield the entire outer range.
1357        assert_eq!(gaps.next(), Some(5..8));
1358        assert_eq!(gaps.next(), None);
1359        // Gaps iterator should be fused.
1360        assert_eq!(gaps.next(), None);
1361        assert_eq!(gaps.next(), None);
1362    }
1363
1364    #[test]
1365    fn item_touching_start_of_outer_range() {
1366        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1367        // 0 1 2 3 4 5 6 7 8 9
1368        // ◌ ●-------◌ ◌ ◌ ◌ ◌
1369        range_map.insert(1..5, ());
1370        // 0 1 2 3 4 5 6 7 8 9
1371        // ◌ ◌ ◌ ◌ ◌ ◆-----◇ ◌
1372        let outer_range = 5..8;
1373        let mut gaps = range_map.gaps(&outer_range);
1374        // Should yield the entire outer range.
1375        assert_eq!(gaps.next(), Some(5..8));
1376        assert_eq!(gaps.next(), None);
1377        // Gaps iterator should be fused.
1378        assert_eq!(gaps.next(), None);
1379        assert_eq!(gaps.next(), None);
1380    }
1381
1382    #[test]
1383    fn item_overlapping_start_of_outer_range() {
1384        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1385        // 0 1 2 3 4 5 6 7 8 9
1386        // ◌ ●---------◌ ◌ ◌ ◌
1387        range_map.insert(1..6, ());
1388        // 0 1 2 3 4 5 6 7 8 9
1389        // ◌ ◌ ◌ ◌ ◌ ◆-----◇ ◌
1390        let outer_range = 5..8;
1391        let mut gaps = range_map.gaps(&outer_range);
1392        // Should yield from the end of the stored item
1393        // to the end of the outer range.
1394        assert_eq!(gaps.next(), Some(6..8));
1395        assert_eq!(gaps.next(), None);
1396        // Gaps iterator should be fused.
1397        assert_eq!(gaps.next(), None);
1398        assert_eq!(gaps.next(), None);
1399    }
1400
1401    #[test]
1402    fn item_starting_at_start_of_outer_range() {
1403        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1404        // 0 1 2 3 4 5 6 7 8 9
1405        // ◌ ◌ ◌ ◌ ◌ ●-◌ ◌ ◌ ◌
1406        range_map.insert(5..6, ());
1407        // 0 1 2 3 4 5 6 7 8 9
1408        // ◌ ◌ ◌ ◌ ◌ ◆-----◇ ◌
1409        let outer_range = 5..8;
1410        let mut gaps = range_map.gaps(&outer_range);
1411        // Should yield from the item onwards.
1412        assert_eq!(gaps.next(), Some(6..8));
1413        assert_eq!(gaps.next(), None);
1414        // Gaps iterator should be fused.
1415        assert_eq!(gaps.next(), None);
1416        assert_eq!(gaps.next(), None);
1417    }
1418
1419    #[test]
1420    fn items_floating_inside_outer_range() {
1421        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1422        // 0 1 2 3 4 5 6 7 8 9
1423        // ◌ ◌ ◌ ◌ ◌ ●-◌ ◌ ◌ ◌
1424        range_map.insert(5..6, ());
1425        // 0 1 2 3 4 5 6 7 8 9
1426        // ◌ ◌ ◌ ●-◌ ◌ ◌ ◌ ◌ ◌
1427        range_map.insert(3..4, ());
1428        // 0 1 2 3 4 5 6 7 8 9
1429        // ◌ ◆-------------◇ ◌
1430        let outer_range = 1..8;
1431        let mut gaps = range_map.gaps(&outer_range);
1432        // Should yield gaps at start, between items,
1433        // and at end.
1434        assert_eq!(gaps.next(), Some(1..3));
1435        assert_eq!(gaps.next(), Some(4..5));
1436        assert_eq!(gaps.next(), Some(6..8));
1437        assert_eq!(gaps.next(), None);
1438        // Gaps iterator should be fused.
1439        assert_eq!(gaps.next(), None);
1440        assert_eq!(gaps.next(), None);
1441    }
1442
1443    #[test]
1444    fn item_ending_at_end_of_outer_range() {
1445        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1446        // 0 1 2 3 4 5 6 7 8 9
1447        // ◌ ◌ ◌ ◌ ◌ ◌ ◌ ●-◌ ◌
1448        range_map.insert(7..8, ());
1449        // 0 1 2 3 4 5 6 7 8 9
1450        // ◌ ◌ ◌ ◌ ◌ ◆-----◇ ◌
1451        let outer_range = 5..8;
1452        let mut gaps = range_map.gaps(&outer_range);
1453        // Should yield from the start of the outer range
1454        // up to the start of the stored item.
1455        assert_eq!(gaps.next(), Some(5..7));
1456        assert_eq!(gaps.next(), None);
1457        // Gaps iterator should be fused.
1458        assert_eq!(gaps.next(), None);
1459        assert_eq!(gaps.next(), None);
1460    }
1461
1462    #[test]
1463    fn item_overlapping_end_of_outer_range() {
1464        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1465        // 0 1 2 3 4 5 6 7 8 9
1466        // ◌ ◌ ◌ ◌ ●---◌ ◌ ◌ ◌
1467        range_map.insert(4..6, ());
1468        // 0 1 2 3 4 5 6 7 8 9
1469        // ◌ ◌ ◆-----◇ ◌ ◌ ◌ ◌
1470        let outer_range = 2..5;
1471        let mut gaps = range_map.gaps(&outer_range);
1472        // Should yield from the start of the outer range
1473        // up to the start of the stored item.
1474        assert_eq!(gaps.next(), Some(2..4));
1475        assert_eq!(gaps.next(), None);
1476        // Gaps iterator should be fused.
1477        assert_eq!(gaps.next(), None);
1478        assert_eq!(gaps.next(), None);
1479    }
1480
1481    #[test]
1482    fn item_touching_end_of_outer_range() {
1483        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1484        // 0 1 2 3 4 5 6 7 8 9
1485        // ◌ ◌ ◌ ◌ ●-------◌ ◌
1486        range_map.insert(4..8, ());
1487        // 0 1 2 3 4 5 6 7 8 9
1488        // ◌ ◆-----◇ ◌ ◌ ◌ ◌ ◌
1489        let outer_range = 1..4;
1490        let mut gaps = range_map.gaps(&outer_range);
1491        // Should yield the entire outer range.
1492        assert_eq!(gaps.next(), Some(1..4));
1493        assert_eq!(gaps.next(), None);
1494        // Gaps iterator should be fused.
1495        assert_eq!(gaps.next(), None);
1496        assert_eq!(gaps.next(), None);
1497    }
1498
1499    #[test]
1500    fn item_after_outer_range() {
1501        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1502        // 0 1 2 3 4 5 6 7 8 9
1503        // ◌ ◌ ◌ ◌ ◌ ◌ ●---◌ ◌
1504        range_map.insert(6..7, ());
1505        // 0 1 2 3 4 5 6 7 8 9
1506        // ◌ ◆-----◇ ◌ ◌ ◌ ◌ ◌
1507        let outer_range = 1..4;
1508        let mut gaps = range_map.gaps(&outer_range);
1509        // Should yield the entire outer range.
1510        assert_eq!(gaps.next(), Some(1..4));
1511        assert_eq!(gaps.next(), None);
1512        // Gaps iterator should be fused.
1513        assert_eq!(gaps.next(), None);
1514        assert_eq!(gaps.next(), None);
1515    }
1516
1517    #[test]
1518    fn empty_outer_range_with_items_away_from_both_sides() {
1519        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1520        // 0 1 2 3 4 5 6 7 8 9
1521        // ◌ ◆---◇ ◌ ◌ ◌ ◌ ◌ ◌
1522        range_map.insert(1..3, ());
1523        // 0 1 2 3 4 5 6 7 8 9
1524        // ◌ ◌ ◌ ◌ ◌ ◆---◇ ◌ ◌
1525        range_map.insert(5..7, ());
1526        // 0 1 2 3 4 5 6 7 8 9
1527        // ◌ ◌ ◌ ◌ ◆ ◌ ◌ ◌ ◌ ◌
1528        let outer_range = 4..4;
1529        let mut gaps = range_map.gaps(&outer_range);
1530        // Should not yield any gaps, because a zero-width outer range covers no values.
1531        assert_eq!(gaps.next(), None);
1532        // Gaps iterator should be fused.
1533        assert_eq!(gaps.next(), None);
1534    }
1535
1536    #[test]
1537    fn empty_outer_range_with_items_touching_both_sides() {
1538        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1539        // 0 1 2 3 4 5 6 7 8 9
1540        // ◌ ◌ ◆---◇ ◌ ◌ ◌ ◌ ◌ ◌
1541        range_map.insert(2..4, ());
1542        // 0 1 2 3 4 5 6 7 8 9
1543        // ◌ ◌ ◌ ◌ ◆---◇ ◌ ◌ ◌
1544        range_map.insert(4..6, ());
1545        // 0 1 2 3 4 5 6 7 8 9
1546        // ◌ ◌ ◌ ◌ ◆ ◌ ◌ ◌ ◌ ◌
1547        let outer_range = 4..4;
1548        let mut gaps = range_map.gaps(&outer_range);
1549        // Should yield no gaps.
1550        assert_eq!(gaps.next(), None);
1551        // Gaps iterator should be fused.
1552        assert_eq!(gaps.next(), None);
1553        assert_eq!(gaps.next(), None);
1554    }
1555
1556    #[test]
1557    fn empty_outer_range_with_item_straddling() {
1558        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1559        // 0 1 2 3 4 5 6 7 8 9
1560        // ◌ ◌ ◆-----◇ ◌ ◌ ◌ ◌ ◌
1561        range_map.insert(2..5, ());
1562        // 0 1 2 3 4 5 6 7 8 9
1563        // ◌ ◌ ◌ ◌ ◆ ◌ ◌ ◌ ◌ ◌
1564        let outer_range = 4..4;
1565        let mut gaps = range_map.gaps(&outer_range);
1566        // Should yield no gaps.
1567        assert_eq!(gaps.next(), None);
1568        // Gaps iterator should be fused.
1569        assert_eq!(gaps.next(), None);
1570        assert_eq!(gaps.next(), None);
1571    }
1572
1573    #[test]
1574    fn no_empty_gaps() {
1575        // Make two ranges different values so they don't
1576        // get coalesced.
1577        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1578        // 0 1 2 3 4 5 6 7 8 9
1579        // ◌ ◌ ◌ ◌ ●-◌ ◌ ◌ ◌ ◌
1580        range_map.insert(4..5, true);
1581        // 0 1 2 3 4 5 6 7 8 9
1582        // ◌ ◌ ◌ ●-◌ ◌ ◌ ◌ ◌ ◌
1583        range_map.insert(3..4, false);
1584        // 0 1 2 3 4 5 6 7 8 9
1585        // ◌ ◆-------------◇ ◌
1586        let outer_range = 1..8;
1587        let mut gaps = range_map.gaps(&outer_range);
1588        // Should yield gaps at start and end, but not between the
1589        // two touching items. (4 is covered, so there should be no gap.)
1590        assert_eq!(gaps.next(), Some(1..3));
1591        assert_eq!(gaps.next(), Some(5..8));
1592        assert_eq!(gaps.next(), None);
1593        // Gaps iterator should be fused.
1594        assert_eq!(gaps.next(), None);
1595        assert_eq!(gaps.next(), None);
1596    }
1597
1598    #[test]
1599    fn adjacent_small_items() {
1600        // Items two items next to each other at the start, and at the end.
1601        let mut range_map: RangeMap<u8, bool> = RangeMap::new();
1602        range_map.insert(0..1, false);
1603        range_map.insert(1..2, true);
1604        range_map.insert(253..254, false);
1605        range_map.insert(254..255, true);
1606
1607        let outer_range = 0..255;
1608        let mut gaps = range_map.gaps(&outer_range);
1609        // Should yield one big gap in the middle.
1610        assert_eq!(gaps.next(), Some(2..253));
1611        // Gaps iterator should be fused.
1612        assert_eq!(gaps.next(), None);
1613        assert_eq!(gaps.next(), None);
1614    }
1615
1616    // This test fails in v1.0.2
1617    #[test]
1618    fn outer_range_lies_within_first_of_two_stored_ranges() {
1619        let mut range_map: RangeMap<u64, ()> = RangeMap::new();
1620        // 0 1 2 3 4 5 6 7 8 9
1621        // ◆----------◇ ◌ ◌ ◌ ◌
1622        range_map.insert(0..5, ());
1623        // 0 1 2 3 4 5 6 7 8 9
1624        // ◌ ◌ ◌ ◌◌ ◌ ◆---◇ ◌
1625        range_map.insert(6..8, ());
1626        // 0 1 2 3 4 5 6 7 8 9
1627        // ◌ ◆--◇ ◌  ◌  ◌  ◌  ◌
1628        let outer_range: Range<u64> = 1..3;
1629        let mut gaps = range_map.gaps(&outer_range);
1630        assert_eq!(gaps.next(), None);
1631    }
1632
1633    // Overlapping tests
1634
1635    #[test]
1636    fn overlapping_with_empty_map() {
1637        // 0 1 2 3 4 5 6 7 8 9
1638        // ◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌
1639        let range_map: RangeMap<u32, ()> = RangeMap::new();
1640        // 0 1 2 3 4 5 6 7 8 9
1641        // ◌ ◆-------------◇ ◌
1642        let query_range = 1..8;
1643        let mut overlapping = range_map.overlapping(&query_range);
1644        // Should not yield any items.
1645        assert_eq!(overlapping.next(), None);
1646        // Gaps iterator should be fused.
1647        assert_eq!(overlapping.next(), None);
1648    }
1649
1650    #[test]
1651    fn overlapping_partial_edges_complete_middle() {
1652        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1653
1654        // 0 1 2 3 4 5 6 7 8 9
1655        // ●---◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌
1656        range_map.insert(0..2, ());
1657        // 0 1 2 3 4 5 6 7 8 9
1658        // ◌ ◌ ◌ ●-◌ ◌ ◌ ◌ ◌ ◌
1659        range_map.insert(3..4, ());
1660        // 0 1 2 3 4 5 6 7 8 9
1661        // ◌ ◌ ◌ ◌ ◌ ●---◌ ◌ ◌
1662        range_map.insert(5..7, ());
1663
1664        // 0 1 2 3 4 5 6 7 8 9
1665        // ◌ ◆---------◇ ◌ ◌ ◌
1666        let query_range = 1..6;
1667
1668        let mut overlapping = range_map.overlapping(&query_range);
1669
1670        // Should yield partially overlapped range at start.
1671        assert_eq!(overlapping.next(), Some((&(0..2), &())));
1672        // Should yield completely overlapped range in middle.
1673        assert_eq!(overlapping.next(), Some((&(3..4), &())));
1674        // Should yield partially overlapped range at end.
1675        assert_eq!(overlapping.next(), Some((&(5..7), &())));
1676        // Gaps iterator should be fused.
1677        assert_eq!(overlapping.next(), None);
1678        assert_eq!(overlapping.next(), None);
1679    }
1680
1681    #[test]
1682    fn overlapping_non_overlapping_edges_complete_middle() {
1683        let mut range_map: RangeMap<u32, ()> = RangeMap::new();
1684
1685        // 0 1 2 3 4 5 6 7 8 9
1686        // ●---◌ ◌ ◌ ◌ ◌ ◌ ◌ ◌
1687        range_map.insert(0..2, ());
1688        // 0 1 2 3 4 5 6 7 8 9
1689        // ◌ ◌ ◌ ●-◌ ◌ ◌ ◌ ◌ ◌
1690        range_map.insert(3..4, ());
1691        // 0 1 2 3 4 5 6 7 8 9
1692        // ◌ ◌ ◌ ◌ ◌ ●---◌ ◌ ◌
1693        range_map.insert(5..7, ());
1694
1695        // 0 1 2 3 4 5 6 7 8 9
1696        // ◌ ◌ ◆-----◇ ◌ ◌ ◌ ◌
1697        let query_range = 2..5;
1698
1699        let mut overlapping = range_map.overlapping(&query_range);
1700
1701        // Should only yield the completely overlapped range in middle.
1702        // (Not the ranges that are touched by not covered to either side.)
1703        assert_eq!(overlapping.next(), Some((&(3..4), &())));
1704        // Gaps iterator should be fused.
1705        assert_eq!(overlapping.next(), None);
1706        assert_eq!(overlapping.next(), None);
1707    }
1708
1709    ///
1710    /// impl Debug
1711    ///
1712
1713    #[test]
1714    fn map_debug_repr_looks_right() {
1715        let mut map: RangeMap<u32, ()> = RangeMap::new();
1716
1717        // Empty
1718        assert_eq!(format!("{:?}", map), "{}");
1719
1720        // One entry
1721        map.insert(2..5, ());
1722        assert_eq!(format!("{:?}", map), "{2..5: ()}");
1723
1724        // Many entries
1725        map.insert(6..7, ());
1726        map.insert(8..9, ());
1727        assert_eq!(format!("{:?}", map), "{2..5: (), 6..7: (), 8..9: ()}");
1728    }
1729
1730    // impl Default where T: ?Default
1731
1732    #[test]
1733    fn always_default() {
1734        struct NoDefault;
1735        RangeMap::<NoDefault, NoDefault>::default();
1736    }
1737
1738    // Iterator Tests
1739
1740    #[test]
1741    fn into_iter_matches_iter() {
1742        // Just use vec since that's the same implementation we'd expect
1743        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1744        range_map.insert(1..3, false);
1745        range_map.insert(3..5, true);
1746
1747        let cloned = range_map.to_vec();
1748        let consumed = range_map.into_iter().collect::<Vec<_>>();
1749
1750        // Correct value
1751        assert_eq!(cloned, vec![(1..3, false), (3..5, true)]);
1752
1753        // Equality
1754        assert_eq!(cloned, consumed);
1755    }
1756
1757    // Equality
1758    #[test]
1759    fn eq() {
1760        let mut a: RangeMap<u32, bool> = RangeMap::new();
1761        a.insert(1..3, false);
1762
1763        let mut b: RangeMap<u32, bool> = RangeMap::new();
1764        b.insert(1..4, false);
1765
1766        let mut c: RangeMap<u32, bool> = RangeMap::new();
1767        c.insert(1..3, false);
1768
1769        assert_ne!(a, b);
1770        assert_ne!(b, a);
1771
1772        assert_eq!(a, c);
1773        assert_eq!(c, a);
1774        assert_eq!(a, a);
1775    }
1776
1777    // Ord
1778    #[test]
1779    fn partial_ord() {
1780        let mut a: RangeMap<u32, bool> = RangeMap::new();
1781        a.insert(1..3, false);
1782
1783        let mut b: RangeMap<u32, bool> = RangeMap::new();
1784        b.insert(1..4, false);
1785
1786        assert_eq!(a.partial_cmp(&a), Some(Ordering::Equal));
1787
1788        assert_eq!(a.partial_cmp(&b), Some(Ordering::Less));
1789        assert_eq!(b.partial_cmp(&a), Some(Ordering::Greater));
1790    }
1791
1792    #[test]
1793    fn ord() {
1794        let mut a: RangeMap<u32, bool> = RangeMap::new();
1795        a.insert(1..3, false);
1796
1797        let mut b: RangeMap<u32, bool> = RangeMap::new();
1798        b.insert(1..4, false);
1799
1800        assert_eq!(a.cmp(&a), Ordering::Equal);
1801
1802        assert_eq!(a.cmp(&b), Ordering::Less);
1803        assert_eq!(b.cmp(&a), Ordering::Greater);
1804    }
1805
1806    // impl Serialize
1807
1808    #[cfg(feature = "serde1")]
1809    #[test]
1810    fn serialization() {
1811        let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1812        // 0 1 2 3 4 5 6 7 8 9
1813        // ◌ ◆---◇ ◌ ◌ ◌ ◌ ◌ ◌
1814        range_map.insert(1..3, false);
1815        // 0 1 2 3 4 5 6 7 8 9
1816        // ◌ ◌ ◌ ◌ ◌ ◆---◇ ◌ ◌
1817        range_map.insert(5..7, true);
1818        let output = serde_json::to_string(&range_map).expect("Failed to serialize");
1819        assert_eq!(output, "[[[1,3],false],[[5,7],true]]");
1820    }
1821
1822    // impl Deserialize
1823
1824    #[cfg(feature = "serde1")]
1825    #[test]
1826    fn deserialization() {
1827        let input = "[[[1,3],false],[[5,7],true]]";
1828        let range_map: RangeMap<u32, bool> =
1829            serde_json::from_str(input).expect("Failed to deserialize");
1830        let reserialized = serde_json::to_string(&range_map).expect("Failed to re-serialize");
1831        assert_eq!(reserialized, input);
1832    }
1833
1834    // const fn
1835
1836    #[cfg(feature = "const_fn")]
1837    const _MAP: RangeMap<u32, bool> = RangeMap::new();
1838
1839    #[cfg(feature = "quickcheck")]
1840    quickcheck::quickcheck! {
1841        fn prop(xs: RangeMap<usize, usize>) -> bool {
1842            xs == xs
1843        }
1844    }
1845}
rangemap/map.rs

rangemap/
map.rs
