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#[derive(Clone, Eq)]
27pub struct RangeMap<K, V> {
28 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 #[cfg(feature = "const_fn")]
89 pub const fn new() -> Self {
90 RangeMap {
91 btm: BTreeMap::new(),
92 }
93 }
94
95 #[cfg(not(feature = "const_fn"))]
97 pub fn new() -> Self {
98 RangeMap {
99 btm: BTreeMap::new(),
100 }
101 }
102
103 pub fn iter(&self) -> Iter<'_, K, V> {
108 Iter {
109 inner: self.btm.iter(),
110 }
111 }
112
113 pub fn clear(&mut self) {
115 self.btm.clear();
116 }
117
118 pub fn len(&self) -> usize {
120 self.btm.len()
121 }
122
123 pub fn is_empty(&self) -> bool {
125 self.btm.is_empty()
126 }
127
128 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 pub fn get(&self, key: &K) -> Option<&V> {
143 self.get_key_value(key).map(|(_range, value)| value)
144 }
145
146 pub fn get_key_value(&self, key: &K) -> Option<(&Range<K>, &V)> {
149 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 start_wrapper.end_wrapper.range.contains(key)
159 })
160 .map(|(start_wrapper, value)| (&start_wrapper.end_wrapper.range, value))
161 }
162
163 pub fn contains_key(&self, key: &K) -> bool {
165 self.get(key).is_some()
166 }
167
168 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 candidate_start: &outer_range.start,
185 }
186 }
187
188 pub fn overlapping<R: Borrow<Range<K>>>(&self, range: R) -> Overlapping<K, V, R> {
191 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 pub fn overlaps(&self, range: &Range<K>) -> bool {
210 self.overlapping(range).next().is_some()
211 }
212
213 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 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 pub fn insert(&mut self, range: Range<K>, value: V) {
249 assert!(range.start < range.end);
252
253 let mut new_start_wrapper: RangeStartWrapper<K> = RangeStartWrapper::new(range);
257 let new_value = value;
258
259 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 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 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 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 #[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 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 self.btm.insert(new_start_wrapper, new_value);
350 }
351
352 pub fn remove(&mut self, range: Range<K>) {
363 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 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 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 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 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 if new_range.overlaps(&stored_start_wrapper.range) {
448 self.btm.remove(&stored_start_wrapper);
452 if stored_start_wrapper.start < new_range.start {
453 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 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 }
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 self.btm.remove(&stored);
486 let stored_range = stored.end_wrapper;
487 if stored_range.start < range_to_remove.start {
488 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 self.btm.insert(
497 RangeStartWrapper::new(range_to_remove.end.clone()..stored_range.range.end),
498 stored_value,
499 );
500 }
501 }
502}
503
504pub 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
546pub 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
588impl<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
692pub 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
706impl<'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 } else if range.start <= *self.candidate_start {
721 self.candidate_start = &range.end;
723 } else if range.start < self.outer_range.end {
724 let gap = self.candidate_start.clone()..range.start.clone();
727 self.candidate_start = &range.end;
728 return Some(gap);
729 }
730 }
731
732 if *self.candidate_start < self.outer_range.end {
735 let gap = self.candidate_start.clone()..self.outer_range.end.clone();
737 self.candidate_start = &self.outer_range.end;
739 Some(gap)
740 } else {
741 None
743 }
744 }
745}
746
747pub 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
761impl<'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 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#[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 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 #[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 range_map.insert(1..3, false);
1034 range_map.insert(3..5, false);
1037 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 range_map.insert(1..3, false);
1048 range_map.insert(3..5, true);
1051 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 range_map.insert(1..4, false);
1063 range_map.insert(3..5, false);
1066 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 range_map.insert(1..4, false);
1077 range_map.insert(3..5, true);
1080 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 range_map.insert(3..5, false);
1092 range_map.insert(1..3, false);
1095 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 range_map.insert(3..5, true);
1106 range_map.insert(1..3, false);
1109 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 range_map.insert(1..5, false);
1121 range_map.insert(2..4, false);
1124 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 range_map.insert(1..5, true);
1135 range_map.insert(2..4, false);
1138 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 range_map.insert(1..3, false);
1154 range_map.insert(3..5, true);
1157 range_map.insert(3..5, false);
1160 assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
1163 }
1164
1165 #[test]
1166 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 (2..3, false),
1175 (2..3, true),
1177 (3..5, true),
1180 (4..6, true),
1181 (5..7, true),
1182 (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 range_map.insert(k.clone(), v);
1193 #[allow(clippy::range_minus_one)]
1196 dense.insert(k.start..=(k.end - 1), v);
1197
1198 let sparse = range_map.to_vec();
1200 let dense = dense.to_end_exclusive_vec();
1201 assert_eq!(sparse, dense);
1202 }
1203 });
1204 }
1205
1206 #[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 #[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 #[test]
1296 fn whole_range_is_a_gap() {
1297 let range_map: RangeMap<u32, ()> = RangeMap::new();
1300 let outer_range = 1..8;
1303 let mut gaps = range_map.gaps(&outer_range);
1304 assert_eq!(gaps.next(), Some(1..8));
1306 assert_eq!(gaps.next(), None);
1307 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 range_map.insert(1..6, ());
1318 let outer_range = 1..6;
1321 let mut gaps = range_map.gaps(&outer_range);
1322 assert_eq!(gaps.next(), None);
1324 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 range_map.insert(1..3, ());
1335 let outer_range = 5..8;
1338 let mut gaps = range_map.gaps(&outer_range);
1339 assert_eq!(gaps.next(), Some(5..8));
1341 assert_eq!(gaps.next(), None);
1342 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 range_map.insert(1..5, ());
1353 let outer_range = 5..8;
1356 let mut gaps = range_map.gaps(&outer_range);
1357 assert_eq!(gaps.next(), Some(5..8));
1359 assert_eq!(gaps.next(), None);
1360 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 range_map.insert(1..6, ());
1371 let outer_range = 5..8;
1374 let mut gaps = range_map.gaps(&outer_range);
1375 assert_eq!(gaps.next(), Some(6..8));
1378 assert_eq!(gaps.next(), None);
1379 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 range_map.insert(5..6, ());
1390 let outer_range = 5..8;
1393 let mut gaps = range_map.gaps(&outer_range);
1394 assert_eq!(gaps.next(), Some(6..8));
1396 assert_eq!(gaps.next(), None);
1397 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 range_map.insert(5..6, ());
1408 range_map.insert(3..4, ());
1411 let outer_range = 1..8;
1414 let mut gaps = range_map.gaps(&outer_range);
1415 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 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 range_map.insert(7..8, ());
1432 let outer_range = 5..8;
1435 let mut gaps = range_map.gaps(&outer_range);
1436 assert_eq!(gaps.next(), Some(5..7));
1439 assert_eq!(gaps.next(), None);
1440 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 range_map.insert(4..6, ());
1451 let outer_range = 2..5;
1454 let mut gaps = range_map.gaps(&outer_range);
1455 assert_eq!(gaps.next(), Some(2..4));
1458 assert_eq!(gaps.next(), None);
1459 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 range_map.insert(4..8, ());
1470 let outer_range = 1..4;
1473 let mut gaps = range_map.gaps(&outer_range);
1474 assert_eq!(gaps.next(), Some(1..4));
1476 assert_eq!(gaps.next(), None);
1477 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 range_map.insert(6..7, ());
1488 let outer_range = 1..4;
1491 let mut gaps = range_map.gaps(&outer_range);
1492 assert_eq!(gaps.next(), Some(1..4));
1494 assert_eq!(gaps.next(), None);
1495 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 range_map.insert(1..3, ());
1506 range_map.insert(5..7, ());
1509 let outer_range = 4..4;
1512 let mut gaps = range_map.gaps(&outer_range);
1513 assert_eq!(gaps.next(), None);
1515 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 range_map.insert(2..4, ());
1525 range_map.insert(4..6, ());
1528 let outer_range = 4..4;
1531 let mut gaps = range_map.gaps(&outer_range);
1532 assert_eq!(gaps.next(), None);
1534 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 range_map.insert(2..5, ());
1545 let outer_range = 4..4;
1548 let mut gaps = range_map.gaps(&outer_range);
1549 assert_eq!(gaps.next(), None);
1551 assert_eq!(gaps.next(), None);
1553 assert_eq!(gaps.next(), None);
1554 }
1555
1556 #[test]
1557 fn no_empty_gaps() {
1558 let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1561 range_map.insert(4..5, true);
1564 range_map.insert(3..4, false);
1567 let outer_range = 1..8;
1570 let mut gaps = range_map.gaps(&outer_range);
1571 assert_eq!(gaps.next(), Some(1..3));
1574 assert_eq!(gaps.next(), Some(5..8));
1575 assert_eq!(gaps.next(), None);
1576 assert_eq!(gaps.next(), None);
1578 assert_eq!(gaps.next(), None);
1579 }
1580
1581 #[test]
1582 fn adjacent_small_items() {
1583 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 assert_eq!(gaps.next(), Some(2..253));
1594 assert_eq!(gaps.next(), None);
1596 assert_eq!(gaps.next(), None);
1597 }
1598
1599 #[test]
1601 fn outer_range_lies_within_first_of_two_stored_ranges() {
1602 let mut range_map: RangeMap<u64, ()> = RangeMap::new();
1603 range_map.insert(0..5, ());
1606 range_map.insert(6..8, ());
1609 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 #[test]
1619 fn overlapping_with_empty_map() {
1620 let range_map: RangeMap<u32, ()> = RangeMap::new();
1623 let query_range = 1..8;
1626 let mut overlapping = range_map.overlapping(&query_range);
1627 assert_eq!(overlapping.next(), None);
1629 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 range_map.insert(0..2, ());
1640 range_map.insert(3..4, ());
1643 range_map.insert(5..7, ());
1646
1647 let query_range = 1..6;
1650
1651 let mut overlapping = range_map.overlapping(&query_range);
1652
1653 assert_eq!(overlapping.next(), Some((&(0..2), &())));
1655 assert_eq!(overlapping.next(), Some((&(3..4), &())));
1657 assert_eq!(overlapping.next(), Some((&(5..7), &())));
1659 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 range_map.insert(0..2, ());
1671 range_map.insert(3..4, ());
1674 range_map.insert(5..7, ());
1677
1678 let query_range = 2..5;
1681
1682 let mut overlapping = range_map.overlapping(&query_range);
1683
1684 assert_eq!(overlapping.next(), Some((&(3..4), &())));
1687 assert_eq!(overlapping.next(), None);
1689 assert_eq!(overlapping.next(), None);
1690 }
1691
1692 #[test]
1697 fn map_debug_repr_looks_right() {
1698 let mut map: RangeMap<u32, ()> = RangeMap::new();
1699
1700 assert_eq!(format!("{:?}", map), "{}");
1702
1703 map.insert(2..5, ());
1705 assert_eq!(format!("{:?}", map), "{2..5: ()}");
1706
1707 map.insert(6..7, ());
1709 map.insert(8..9, ());
1710 assert_eq!(format!("{:?}", map), "{2..5: (), 6..7: (), 8..9: ()}");
1711 }
1712
1713 #[test]
1716 fn always_default() {
1717 struct NoDefault;
1718 RangeMap::<NoDefault, NoDefault>::default();
1719 }
1720
1721 #[test]
1724 fn into_iter_matches_iter() {
1725 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 assert_eq!(cloned, vec![(1..3, false), (3..5, true)]);
1735
1736 assert_eq!(cloned, consumed);
1738 }
1739
1740 #[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 #[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 #[cfg(feature = "serde1")]
1792 #[test]
1793 fn serialization() {
1794 let mut range_map: RangeMap<u32, bool> = RangeMap::new();
1795 range_map.insert(1..3, false);
1798 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 #[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 #[cfg(feature = "const_fn")]
1820 const _MAP: RangeMap<u32, bool> = RangeMap::new();
1821}