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