span_map/
lib.rs

1//! `SpanMap` is a data structure that efficiently maps spans (ranges) to sets of values.
2//!
3//! `SpanMap` allows you to associate sets of values with potentially overlapping spans,
4//! where a span represents a continuous range with well-defined boundaries.
5//! It's particularly useful for scenarios where you need to:
6//!
7//! * Track multiple values across ranges
8//! * Efficiently query values at any given point
9//! * Manage overlapping ranges with set operations
10//!
11//! # Example
12//! ```
13//! # use span_map::SpanMap;
14//!
15//! let mut map = SpanMap::new();
16//! map.insert(0..10, "value1");
17//! map.insert(5..15, "value2");
18//!
19//! // Point 7 has both values
20//! let values: Vec<_> = map.get(&7).copied().collect();
21//! assert_eq!(values, vec!["value1", "value2"]);
22//! ```
23
24#[doc(hidden)]
25pub mod bounds;
26#[doc(hidden)]
27pub mod span;
28
29use std::collections::BTreeMap;
30use std::collections::BTreeSet;
31use std::ops::RangeBounds;
32
33use bounds::LeftBound;
34use span::Span;
35
36/// A map that associates spans (ranges) with sets of values.
37///
38/// `SpanMap` maintains a mapping between spans and sets of values, where:
39/// * Each span represents a continuous range with well-defined boundaries
40/// * Multiple values can be associated with the same span
41/// * Spans can overlap, resulting in points that contain multiple values
42/// * Queries at any point return all values associated with spans containing that point
43///
44/// The implementation uses a B-tree based data structure for efficient operations.
45///
46/// # Type Parameters
47///
48/// * `K`: The type of the keys defining span boundaries. Must implement `Clone` and `Ord`.
49/// * `V`: The type of values stored in the sets. Must implement `Clone` and `Ord`.
50#[derive(Debug, Clone, PartialEq, Eq)]
51pub struct SpanMap<K, V>
52where
53    K: Clone + Ord,
54    V: Clone + Ord,
55{
56    m: BTreeMap<LeftBound<K>, BTreeSet<V>>,
57}
58
59impl<K, V> Default for SpanMap<K, V>
60where
61    K: Clone + Ord,
62    V: Clone + Ord,
63{
64    fn default() -> Self {
65        Self::new()
66    }
67}
68
69impl<K, V> SpanMap<K, V>
70where
71    K: Clone + Ord,
72    V: Clone + Ord,
73{
74    /// Creates a new, empty `SpanMap`.
75    ///
76    /// The new map is initialized with an unbounded span containing an empty set.
77    pub fn new() -> Self {
78        let mut m = BTreeMap::new();
79        m.insert(LeftBound::Unbounded, BTreeSet::new());
80        Self { m }
81    }
82}
83
84impl<K, V> SpanMap<K, V>
85where
86    K: Clone + Ord,
87    V: Clone + Ord,
88{
89    /// Returns an iterator over all values associated with spans containing the given key.
90    pub fn get(&self, key: &K) -> impl Iterator<Item = &V> {
91        // Safe unwrap(): Unbounded is always present
92        let last_less_equal = self
93            .m
94            .range(..=LeftBound::Included(key.clone()))
95            .next_back()
96            .unwrap();
97
98        let (_bound, set) = last_less_equal;
99
100        set.iter()
101    }
102
103    #[allow(dead_code)]
104    pub(crate) fn values_vec<R>(&self, range: R) -> Vec<V>
105    where
106        R: RangeBounds<K>,
107    {
108        self.values(range).into_iter().cloned().collect()
109    }
110
111    /// Returns all unique values associated with spans that overlap the given range.
112    ///
113    /// This method collects all values from sets that are associated with spans
114    /// intersecting the input range. Values are deduplicated and returned in sorted order.
115    ///
116    /// # Examples
117    ///
118    /// ```
119    /// use span_map::SpanMap;
120    ///
121    /// let mut map = SpanMap::new();
122    /// map.insert(0..10, "a");
123    /// map.insert(5..15, "b");
124    /// map.insert(12..20, "c");
125    ///
126    /// let values: Vec<_> = map.values(5..12).into_iter().collect();
127    /// assert_eq!(values, vec![&"a", &"b"]);
128    /// ```
129    pub fn values<R>(&self, range: R) -> BTreeSet<&V>
130    where
131        R: RangeBounds<K>,
132    {
133        let span = Span::from_range(range);
134        let mut values = BTreeSet::new();
135
136        let last_less_equal = self.m.range(..=span.left.clone()).next_back();
137        if let Some((b, set)) = last_less_equal {
138            if *b == span.left {
139                // nothing to do
140            } else {
141                values.extend(set.iter());
142            }
143        }
144
145        for (b, set) in self.m.range(span.left..) {
146            if span.right < *b {
147                break;
148            }
149            values.extend(set.iter());
150        }
151
152        values
153    }
154
155    /// Inserts a value into all sets associated with spans overlapping the given range.
156    ///
157    /// Adjacent ranges with the same value are merged into a single range.
158    pub fn insert<R>(&mut self, range: R, value: V)
159    where
160        R: RangeBounds<K>,
161    {
162        self.insert_span(Span::from_range(range), value);
163    }
164
165    /// Removes a value from all sets associated with spans overlapping the given range.
166    ///
167    /// Adjacent ranges with the same value are merged into a single range.
168    pub fn remove<R>(&mut self, range: R, value: V)
169    where
170        R: RangeBounds<K>,
171    {
172        self.remove_span(Span::from_range(range), value);
173    }
174
175    #[doc(hidden)]
176    pub fn insert_span(&mut self, range: Span<K>, value: V) {
177        self.update_set_in_span(range, |set| {
178            set.insert(value.clone());
179        });
180    }
181
182    #[doc(hidden)]
183    pub fn remove_span(&mut self, range: Span<K>, value: V) {
184        self.update_set_in_span(range, |set| {
185            set.remove(&value);
186        });
187    }
188
189    fn update_set_in_span(&mut self, span: Span<K>, f: impl Fn(&mut BTreeSet<V>)) {
190        let start = span.left.clone();
191        self.ensure_boundary(start.clone());
192
193        let end = span.right.adjacent_left();
194        if let Some(end) = end.clone() {
195            self.ensure_boundary(end);
196        }
197
198        // At this point, `range.left` and `range.right` are ensured to be in the map
199
200        for (b, set) in self.m.range_mut(span.left..) {
201            if span.right < *b {
202                break;
203            }
204            f(set);
205        }
206
207        self.merge_adjacent_left(start);
208        if let Some(end) = end {
209            self.merge_adjacent_left(end);
210        }
211    }
212
213    /// Splits a range at the specified boundary point and ensures the boundary exists in the map.
214    fn ensure_boundary(&mut self, bound: LeftBound<K>) {
215        let last_less_equal = self.m.range(..=bound.clone()).next_back();
216        if let Some((b, set)) = last_less_equal {
217            if *b == bound {
218                // no need to split
219            } else {
220                self.m.insert(bound, set.clone());
221            }
222        } else {
223            // No bound <= bound, insert
224            self.m.insert(bound, BTreeSet::new());
225        }
226    }
227
228    /// Attempts to merge adjacent ranges by removing redundant boundaries.
229    ///
230    /// If the range to the left and the given one have identical value sets,
231    /// the boundary between them is removed to create a single continuous range.
232    fn merge_adjacent_left(&mut self, bound: LeftBound<K>) {
233        let mut it = self.m.range(..=bound.clone()).rev();
234
235        let Some((right_bound, right_set)) = it.next() else {
236            return;
237        };
238
239        let Some((_left_bound, left_set)) = it.next() else {
240            return;
241        };
242
243        if left_set == right_set {
244            let right_bound = right_bound.clone();
245            self.m.remove(&right_bound);
246        }
247    }
248}
249
250#[cfg(test)]
251mod tests {
252    use super::*;
253    use crate::bounds::RightBound;
254
255    // ===================== get
256
257    #[test]
258    fn test_get_empty_map() {
259        let map = SpanMap::<i32, i32>::new();
260
261        // Empty map should return empty iterator for any key
262        assert_eq!(map.get(&5).count(), 0);
263    }
264
265    #[test]
266    fn test_get_single_range() {
267        let mut map = SpanMap::<i32, i32>::new();
268
269        // [1, 5] -> {10}
270        map.insert_span(
271            Span::new(LeftBound::Included(1), RightBound::Included(5)),
272            10,
273        );
274
275        // Before range
276        assert_eq!(map.get(&0).count(), 0);
277
278        // Start of range
279        let values: Vec<_> = map.get(&1).collect();
280        assert_eq!(values, vec![&10]);
281
282        // Middle of range
283        let values: Vec<_> = map.get(&3).collect();
284        assert_eq!(values, vec![&10]);
285
286        // End of range
287        let values: Vec<_> = map.get(&5).collect();
288        assert_eq!(values, vec![&10]);
289
290        // After range
291        assert_eq!(map.get(&6).count(), 0);
292    }
293
294    #[test]
295    fn test_get_overlapping_ranges() {
296        let mut map = SpanMap::<i32, i32>::new();
297
298        // [1,   5] -> {10}
299        //    [3,   7] -> {20}
300        map.insert_span(
301            Span::new(LeftBound::Included(1), RightBound::Included(5)),
302            10,
303        );
304        map.insert_span(
305            Span::new(LeftBound::Included(3), RightBound::Included(7)),
306            20,
307        );
308
309        // Before first range
310        assert_eq!(map.get(&0).count(), 0);
311
312        // First range only
313        let values: Vec<_> = map.get(&2).collect();
314        assert_eq!(values, vec![&10]);
315
316        // Overlapping section
317        let mut values: Vec<_> = map.get(&4).collect();
318        values.sort(); // Order not guaranteed for BTreeSet iterator
319        assert_eq!(values, vec![&10, &20]);
320
321        let mut values: Vec<_> = map.get(&5).collect();
322        values.sort(); // Order not guaranteed for BTreeSet iterator
323        assert_eq!(values, vec![&10, &20]);
324
325        // Second range only
326        let values: Vec<_> = map.get(&6).collect();
327        assert_eq!(values, vec![&20]);
328
329        // After all ranges
330        assert_eq!(map.get(&8).count(), 0);
331    }
332
333    #[test]
334    fn test_get_multiple_values() {
335        let mut map = SpanMap::<i32, i32>::new();
336
337        // [1, 5] -> {10, 20, 30}
338        map.insert_span(
339            Span::new(LeftBound::Included(1), RightBound::Included(5)),
340            10,
341        );
342        map.insert_span(
343            Span::new(LeftBound::Included(1), RightBound::Included(5)),
344            20,
345        );
346        map.insert_span(
347            Span::new(LeftBound::Included(1), RightBound::Included(5)),
348            30,
349        );
350
351        let mut values: Vec<_> = map.get(&3).collect();
352        values.sort();
353        assert_eq!(values, vec![&10, &20, &30]);
354    }
355
356    #[test]
357    fn test_get_with_excluded_bounds() {
358        let mut map = SpanMap::<i32, i32>::new();
359
360        // (1, 5) -> {10}
361        map.insert_span(
362            Span::new(LeftBound::Excluded(1), RightBound::Excluded(5)),
363            10,
364        );
365
366        // At excluded bounds
367        assert_eq!(map.get(&1).count(), 0);
368        assert_eq!(map.get(&5).count(), 0);
369
370        // Inside range
371        let values: Vec<_> = map.get(&3).collect();
372        assert_eq!(values, vec![&10]);
373    }
374
375    #[test]
376    fn test_get_with_unbounded() {
377        let mut map = SpanMap::<i32, i32>::new();
378
379        // (-∞, 5] -> {10}
380        map.insert_span(Span::new(LeftBound::Unbounded, RightBound::Included(5)), 10);
381
382        // Values in unbounded region
383        let values: Vec<_> = map.get(&i32::MIN).collect();
384        assert_eq!(values, vec![&10]);
385
386        let values: Vec<_> = map.get(&0).collect();
387        assert_eq!(values, vec![&10]);
388
389        // After range
390        assert_eq!(map.get(&6).count(), 0);
391    }
392
393    #[test]
394    fn test_get_point_range() {
395        let mut map = SpanMap::<i32, i32>::new();
396
397        // [5, 5] -> {10}
398        map.insert_span(
399            Span::new(LeftBound::Included(5), RightBound::Included(5)),
400            10,
401        );
402
403        // Before point
404        assert_eq!(map.get(&4).count(), 0);
405
406        // At point
407        let values: Vec<_> = map.get(&5).collect();
408        assert_eq!(values, vec![&10]);
409
410        // After point
411        assert_eq!(map.get(&6).count(), 0);
412    }
413
414    // ===================== values
415
416    #[test]
417    fn test_values_empty_map() {
418        let map: SpanMap<i32, &str> = SpanMap::new();
419        assert!(map.values_vec(0..10).is_empty());
420    }
421
422    #[test]
423    fn test_values_vec_single_span() {
424        let mut map = SpanMap::new();
425        map.insert(0..10, "a");
426
427        assert_eq!(map.values_vec(-5..5), vec!["a"]);
428        assert_eq!(map.values_vec(0..5), vec!["a"]);
429        assert_eq!(map.values_vec(5..15), vec!["a"]);
430        assert_eq!(map.values_vec(10..15), Vec::<&'static str>::new());
431    }
432
433    #[test]
434    fn test_values_vec_overlapping_spans() {
435        let mut map = SpanMap::new();
436        map.insert(0..10, "a");
437        map.insert(5..15, "b");
438        map.insert(12..20, "c");
439
440        // Test different ranges
441        assert_eq!(map.values_vec(-5..0), Vec::<&'static str>::new());
442        assert_eq!(map.values_vec(0..5), vec!["a"]);
443        assert_eq!(map.values_vec(5..10), vec!["a", "b"]);
444        assert_eq!(map.values_vec(10..12), vec!["b"]);
445        assert_eq!(map.values_vec(12..15), vec!["b", "c"]);
446        assert_eq!(map.values_vec(15..20), vec!["c"]);
447        assert_eq!(map.values_vec(20..25), Vec::<&'static str>::new());
448
449        // Test ranges that span multiple sections
450        assert_eq!(map.values_vec(0..20), vec!["a", "b", "c"]);
451        assert_eq!(map.values_vec(5..15), vec!["a", "b", "c"]);
452    }
453
454    #[test]
455    fn test_values_vec_multiple_values_same_span() {
456        let mut map = SpanMap::new();
457        map.insert(0..10, "a");
458        map.insert(0..10, "b");
459        map.insert(5..15, "c");
460
461        assert_eq!(map.values_vec(0..5), vec!["a", "b"]);
462        assert_eq!(map.values_vec(5..10), vec!["a", "b", "c"]);
463        assert_eq!(map.values_vec(10..15), vec!["c"]);
464    }
465
466    #[test]
467    fn test_values_vec_point_ranges() {
468        let mut map = SpanMap::new();
469        map.insert(0..10, "a");
470        map.insert(5..15, "b");
471
472        // Test single point ranges
473        assert_eq!(map.values_vec(5..=5), vec!["a", "b"]);
474        assert_eq!(map.values_vec(0..=0), vec!["a"]);
475        assert_eq!(map.values_vec(15..=15), Vec::<&'static str>::new());
476    }
477
478    #[test]
479    fn test_values_vec_inclusive_ranges() {
480        let mut map = SpanMap::new();
481        map.insert(0..=10, "a");
482        map.insert(5..=15, "b");
483
484        assert_eq!(map.values_vec(0..=5), vec!["a", "b"]);
485        assert_eq!(map.values_vec(10..=15), vec!["a", "b"]);
486    }
487
488    #[test]
489    fn test_values_vec_unbounded_ranges() {
490        let mut map = SpanMap::new();
491        map.insert(0..10, "a");
492        map.insert(20..30, "b");
493
494        use std::ops::Bound::*;
495        assert_eq!(map.values_vec((Unbounded, Included(5))), vec!["a"]);
496        assert_eq!(map.values_vec((Included(15), Unbounded)), vec!["b"]);
497        assert_eq!(map.values_vec(..), vec!["a", "b"]);
498    }
499
500    // ===================== insert
501
502    #[test]
503    fn test_insert_std_range() {
504        let mut map = SpanMap::<i32, &str>::new();
505
506        // Test with standard ranges
507        map.insert(1..=5, "a");
508        map.insert(3..7, "b");
509
510        assert_eq!(map.get(&0).count(), 0);
511        assert_eq!(map.get(&1).copied().collect::<Vec<_>>(), vec!["a"]);
512        assert_eq!(map.get(&3).copied().collect::<Vec<_>>(), vec!["a", "b"]);
513        assert_eq!(map.get(&6).copied().collect::<Vec<_>>(), vec!["b"]);
514        assert_eq!(map.get(&7).count(), 0);
515    }
516
517    #[test]
518    fn test_insert_empty_map() {
519        let mut map = SpanMap::<i32, i32>::new();
520
521        map.insert_span(
522            Span::new(LeftBound::Included(1), RightBound::Included(5)),
523            10,
524        );
525
526        // Check boundaries exist
527        assert_eq!(map.m.len(), 3);
528        assert!(map.m.contains_key(&LeftBound::Included(1)));
529        assert!(map.m.contains_key(&LeftBound::Excluded(5))); // adjacent_left of Included(5)
530
531        // Check value is present in range
532        assert_eq!(
533            map.m.get(&LeftBound::Included(1)).unwrap(),
534            &BTreeSet::from([10])
535        );
536    }
537
538    #[test]
539    fn test_insert_overlapping_ranges() {
540        let mut map = SpanMap::<i32, i32>::new();
541
542        // [1,   5]
543        //    [3,   7]
544
545        // Insert first range
546        map.insert_span(
547            Span::new(LeftBound::Included(1), RightBound::Included(5)),
548            10,
549        );
550
551        // Insert overlapping range
552        map.insert_span(
553            Span::new(LeftBound::Included(3), RightBound::Included(7)),
554            20,
555        );
556
557        // Check values in different segments
558        assert_eq!(
559            map.m.get(&LeftBound::Included(1)).unwrap(),
560            &BTreeSet::from([10])
561        );
562        assert_eq!(
563            map.m.get(&LeftBound::Included(3)).unwrap(),
564            &BTreeSet::from([10, 20])
565        );
566        assert_eq!(
567            map.m.get(&LeftBound::Excluded(5)).unwrap(),
568            &BTreeSet::from([20])
569        );
570        assert_eq!(
571            map.m.get(&LeftBound::Excluded(7)).unwrap(),
572            &BTreeSet::from([])
573        );
574    }
575
576    #[test]
577    fn test_insert_adjacent_ranges() {
578        let mut map = SpanMap::<i32, i32>::new();
579
580        // Insert first range
581        map.insert_span(
582            Span::new(LeftBound::Included(1), RightBound::Included(5)),
583            10,
584        );
585
586        // Insert adjacent range with same value
587        map.insert_span(
588            Span::new(LeftBound::Excluded(5), RightBound::Included(10)),
589            10,
590        );
591
592        // Should merge into single range due to adjacent ranges with same value
593        assert_eq!(map.m.len(), 3); // Start and end boundaries
594        assert_eq!(
595            map.m.get(&LeftBound::Included(1)).unwrap(),
596            &BTreeSet::from([10])
597        );
598    }
599
600    #[test]
601    fn test_insert_with_excluded_bounds() {
602        let mut map = SpanMap::<i32, i32>::new();
603
604        map.insert_span(
605            Span::new(LeftBound::Excluded(1), RightBound::Excluded(5)),
606            10,
607        );
608
609        assert!(map.m.contains_key(&LeftBound::Excluded(1)));
610        assert!(map.m.contains_key(&LeftBound::Included(5)));
611    }
612
613    #[test]
614    fn test_insert_with_unbounded() {
615        let mut map = SpanMap::<i32, i32>::new();
616
617        // Test unbounded left
618        map.insert_span(Span::new(LeftBound::Unbounded, RightBound::Included(5)), 10);
619
620        assert!(map.m.contains_key(&LeftBound::Unbounded));
621        assert!(map.m.contains_key(&LeftBound::Excluded(5)));
622
623        // Test unbounded right
624        map.insert_span(
625            Span::new(LeftBound::Included(10), RightBound::Unbounded),
626            20,
627        );
628
629        assert!(map.m.contains_key(&LeftBound::Included(10)));
630    }
631
632    #[test]
633    fn test_insert_multiple_values() {
634        let mut map = SpanMap::<i32, i32>::new();
635
636        // Insert overlapping ranges with different values
637        map.insert_span(
638            Span::new(LeftBound::Included(1), RightBound::Included(10)),
639            10,
640        );
641        map.insert_span(
642            Span::new(LeftBound::Included(1), RightBound::Included(10)),
643            20,
644        );
645        map.insert_span(
646            Span::new(LeftBound::Included(1), RightBound::Included(10)),
647            30,
648        );
649
650        // Check all values present
651        assert_eq!(
652            map.m.get(&LeftBound::Included(1)).unwrap(),
653            &BTreeSet::from([10, 20, 30])
654        );
655    }
656
657    #[test]
658    fn test_insert_point_range() {
659        let mut map = SpanMap::<i32, i32>::new();
660
661        // Insert range with same start and end point
662        map.insert_span(
663            Span::new(LeftBound::Included(5), RightBound::Included(5)),
664            10,
665        );
666
667        assert!(map.m.contains_key(&LeftBound::Included(5)));
668        assert!(map.m.contains_key(&LeftBound::Excluded(5)));
669        assert_eq!(
670            map.m.get(&LeftBound::Included(5)).unwrap(),
671            &BTreeSet::from([10])
672        );
673    }
674
675    #[test]
676    fn test_insert_with_string_keys() {
677        let mut map = SpanMap::<String, i32>::new();
678
679        map.insert_span(
680            Span::new(
681                LeftBound::Included("a".to_string()),
682                RightBound::Included("c".to_string()),
683            ),
684            10,
685        );
686
687        assert!(map.m.contains_key(&LeftBound::Included("a".to_string())));
688        assert!(map.m.contains_key(&LeftBound::Excluded("c".to_string()))); // adjacent to "c"
689        assert_eq!(
690            map.m.get(&LeftBound::Included("a".to_string())).unwrap(),
691            &BTreeSet::from([10])
692        );
693    }
694
695    // ===================== remove
696
697    #[test]
698    fn test_remove_std_range() {
699        let mut map = SpanMap::<i32, &str>::new();
700
701        // Setup
702        map.insert(1..=10, "a");
703        map.insert(1..=10, "b");
704
705        // Remove one value from a range
706        map.remove(3..=7, "a");
707
708        assert_eq!(map.get(&2).copied().collect::<Vec<_>>(), vec!["a", "b"]);
709        assert_eq!(map.get(&5).copied().collect::<Vec<_>>(), vec!["b"]);
710        assert_eq!(map.get(&8).copied().collect::<Vec<_>>(), vec!["a", "b"]);
711    }
712
713    #[test]
714    fn test_remove_empty_map() {
715        let mut map = SpanMap::<i32, i32>::new();
716
717        // Removing from empty map should not panic
718        map.remove_span(
719            Span::new(LeftBound::Included(1), RightBound::Included(5)),
720            10,
721        );
722        assert_eq!(map.m.len(), 1); // Only boundary markers
723        assert_eq!(map.get(&1).collect::<Vec<_>>(), Vec::<&i32>::new());
724    }
725
726    #[test]
727    fn test_remove_single_value() {
728        let mut map = SpanMap::<i32, i32>::new();
729
730        // [1, 5] -> {10}
731        map.insert_span(
732            Span::new(LeftBound::Included(1), RightBound::Included(5)),
733            10,
734        );
735
736        map.remove_span(
737            Span::new(LeftBound::Included(1), RightBound::Included(5)),
738            10,
739        );
740
741        assert_eq!(map.m.get(&LeftBound::Included(1)), None);
742        assert_eq!(map.m.get(&LeftBound::Excluded(5)), None);
743    }
744
745    #[test]
746    fn test_remove_partial_range() {
747        let mut map = SpanMap::<i32, i32>::new();
748
749        // [1,     5] -> {10}
750        //   [2, 4]   Remove 10 here
751        map.insert_span(
752            Span::new(LeftBound::Included(1), RightBound::Included(5)),
753            10,
754        );
755
756        map.remove_span(
757            Span::new(LeftBound::Included(2), RightBound::Included(4)),
758            10,
759        );
760
761        // Check values in different segments
762        assert_eq!(
763            map.m.get(&LeftBound::Included(1)).unwrap(),
764            &BTreeSet::from([10])
765        );
766        assert_eq!(
767            map.m.get(&LeftBound::Included(2)).unwrap(),
768            &BTreeSet::new()
769        );
770        assert_eq!(
771            map.m.get(&LeftBound::Excluded(4)).unwrap(),
772            &BTreeSet::from([10])
773        );
774    }
775
776    #[test]
777    fn test_remove_from_multiple_values() {
778        let mut map = SpanMap::<i32, i32>::new();
779
780        // [1, 5] -> {10, 20, 30}
781        map.insert_span(
782            Span::new(LeftBound::Included(1), RightBound::Included(5)),
783            10,
784        );
785        map.insert_span(
786            Span::new(LeftBound::Included(1), RightBound::Included(5)),
787            20,
788        );
789        map.insert_span(
790            Span::new(LeftBound::Included(1), RightBound::Included(5)),
791            30,
792        );
793
794        // Remove one value
795        map.remove_span(
796            Span::new(LeftBound::Included(1), RightBound::Included(5)),
797            20,
798        );
799
800        assert_eq!(
801            map.m.get(&LeftBound::Included(1)).unwrap(),
802            &BTreeSet::from([10, 30])
803        );
804    }
805
806    #[test]
807    fn test_remove_overlapping_ranges() {
808        let mut map = SpanMap::<i32, i32>::new();
809
810        // [1,   5] -> {10}
811        //    [3,   7] -> {20}
812        map.insert_span(
813            Span::new(LeftBound::Included(1), RightBound::Included(5)),
814            10,
815        );
816        map.insert_span(
817            Span::new(LeftBound::Included(3), RightBound::Included(7)),
818            20,
819        );
820
821        // Remove value from first range
822        map.remove_span(
823            Span::new(LeftBound::Included(1), RightBound::Included(5)),
824            10,
825        );
826
827        assert_eq!(map.m.get(&LeftBound::Included(1)), None);
828        assert_eq!(
829            map.m.get(&LeftBound::Included(3)).unwrap(),
830            &BTreeSet::from([20])
831        );
832    }
833
834    #[test]
835    fn test_remove_with_excluded_bounds() {
836        let mut map = SpanMap::<i32, i32>::new();
837
838        // (1, 5) -> {10}
839        map.insert_span(
840            Span::new(LeftBound::Excluded(1), RightBound::Excluded(5)),
841            10,
842        );
843
844        map.remove_span(
845            Span::new(LeftBound::Excluded(1), RightBound::Excluded(5)),
846            10,
847        );
848
849        assert_eq!(map.m.get(&LeftBound::Excluded(1)), None);
850        assert_eq!(map.m.get(&LeftBound::Included(5)), None);
851    }
852
853    #[test]
854    fn test_remove_with_unbounded() {
855        let mut map = SpanMap::<i32, i32>::new();
856
857        // (-∞, 5] -> {10}
858        map.insert_span(Span::new(LeftBound::Unbounded, RightBound::Included(5)), 10);
859
860        map.remove_span(Span::new(LeftBound::Unbounded, RightBound::Included(5)), 10);
861
862        assert_eq!(map.m.get(&LeftBound::Unbounded).unwrap(), &BTreeSet::new());
863        assert_eq!(map.m.get(&LeftBound::Excluded(5)), None);
864    }
865
866    #[test]
867    fn test_remove_nonexistent_value() {
868        let mut map = SpanMap::<i32, i32>::new();
869
870        // [1, 5] -> {10}
871        map.insert_span(
872            Span::new(LeftBound::Included(1), RightBound::Included(5)),
873            10,
874        );
875
876        // Try to remove value that doesn't exist
877        map.remove_span(
878            Span::new(LeftBound::Included(1), RightBound::Included(5)),
879            20,
880        );
881
882        // Original value should still be present
883        assert_eq!(
884            map.m.get(&LeftBound::Included(1)).unwrap(),
885            &BTreeSet::from([10])
886        );
887    }
888
889    // ===================== ensure_boundary
890
891    #[test]
892    fn test_ensure_boundary_empty_map() {
893        use LeftBound::*;
894        let mut map = SpanMap::<i32, i32>::new();
895
896        // Test with empty map
897        map.ensure_boundary(Included(5));
898        assert_eq!(map.m.len(), 2);
899        assert!(map.m.contains_key(&Included(5)));
900        assert!(map.m.get(&Included(5)).unwrap().is_empty());
901    }
902
903    #[test]
904    fn test_ensure_boundary_existing_boundary() {
905        use LeftBound::*;
906        let mut map = SpanMap::<i32, i32>::new();
907
908        // Insert initial boundary
909        map.m.insert(Included(5), BTreeSet::from([1]));
910
911        // Ensure same boundary
912        map.ensure_boundary(Included(5));
913
914        // Verify no changes
915        assert_eq!(map.m.len(), 2);
916        assert_eq!(map.m.get(&Included(5)).unwrap(), &BTreeSet::from([1]));
917    }
918
919    #[test]
920    fn test_ensure_boundary_split_point() {
921        use LeftBound::*;
922        let mut map = SpanMap::<i32, i32>::new();
923
924        // Insert initial boundary
925        map.m.insert(Included(3), BTreeSet::from([1, 2]));
926
927        // Split at a higher point
928        map.ensure_boundary(Included(5));
929
930        // Verify split result
931        assert_eq!(map.m.len(), 3);
932        assert_eq!(map.m.get(&Unbounded).unwrap(), &BTreeSet::from([]));
933        assert_eq!(map.m.get(&Included(3)).unwrap(), &BTreeSet::from([1, 2]));
934        assert_eq!(map.m.get(&Included(5)).unwrap(), &BTreeSet::from([1, 2]));
935    }
936
937    #[test]
938    fn test_ensure_boundary_multiple_existing() {
939        use LeftBound::*;
940        let mut map = SpanMap::<i32, i32>::new();
941
942        // Insert multiple boundaries
943        map.m.insert(Included(1), BTreeSet::from([1]));
944        map.m.insert(Included(3), BTreeSet::from([2]));
945        map.m.insert(Included(5), BTreeSet::from([3]));
946
947        // Ensure boundary between existing ones
948        map.ensure_boundary(Included(2));
949
950        // Verify result
951        assert_eq!(map.m.len(), 5);
952        assert_eq!(map.m.get(&Unbounded).unwrap(), &BTreeSet::from([]));
953        assert_eq!(map.m.get(&Included(1)).unwrap(), &BTreeSet::from([1]));
954        assert_eq!(map.m.get(&Included(2)).unwrap(), &BTreeSet::from([1]));
955        assert_eq!(map.m.get(&Included(3)).unwrap(), &BTreeSet::from([2]));
956        assert_eq!(map.m.get(&Included(5)).unwrap(), &BTreeSet::from([3]));
957    }
958
959    #[test]
960    fn test_ensure_boundary_different_bound_types() {
961        use LeftBound::*;
962        let mut map = SpanMap::<i32, i32>::new();
963
964        // Test with excluded bound
965        map.ensure_boundary(Excluded(5));
966        assert!(map.m.contains_key(&Excluded(5)));
967
968        // Test with included bound after excluded
969        map.ensure_boundary(Included(5));
970        assert!(map.m.contains_key(&Included(5)));
971
972        assert_eq!(map.m.len(), 3);
973    }
974
975    #[test]
976    fn test_ensure_boundary_unbounded() {
977        use LeftBound::*;
978        let mut map = SpanMap::<i32, i32>::new();
979
980        // Test with unbounded
981        map.ensure_boundary(Unbounded);
982        assert!(map.m.contains_key(&Unbounded));
983        assert_eq!(map.m.len(), 1);
984
985        // Add another boundary after unbounded
986        map.ensure_boundary(Included(5));
987        assert_eq!(map.m.len(), 2);
988        assert!(map.m.contains_key(&Included(5)));
989    }
990
991    #[test]
992    fn test_ensure_boundary_ordering() {
993        use LeftBound::*;
994        let mut map = SpanMap::<i32, i32>::new();
995
996        // Insert boundaries in random order
997        map.ensure_boundary(Included(5));
998        map.ensure_boundary(Included(1));
999        map.ensure_boundary(Included(3));
1000
1001        // Verify correct ordering
1002        let keys: Vec<_> = map.m.keys().cloned().collect();
1003        assert_eq!(keys, vec![Unbounded, Included(1), Included(3), Included(5)]);
1004    }
1005
1006    #[test]
1007    fn test_ensure_boundary_with_string_keys() {
1008        use LeftBound::*;
1009        let mut map = SpanMap::<String, i32>::new();
1010
1011        map.ensure_boundary(Included("a".to_string()));
1012        assert!(map.m.contains_key(&Included("a".to_string())));
1013
1014        map.ensure_boundary(Included("b".to_string()));
1015        assert_eq!(map.m.len(), 3);
1016        assert!(map.m.contains_key(&Included("b".to_string())));
1017    }
1018
1019    // ===================== merge_adjacent_left
1020
1021    #[test]
1022    fn test_merge_adjacent_left() {
1023        use LeftBound::*;
1024
1025        let mut map = SpanMap::new();
1026        let set12: BTreeSet<i32> = vec![1, 2].into_iter().collect();
1027        let set23: BTreeSet<i32> = vec![2, 3].into_iter().collect();
1028
1029        // Test case 1: Merge identical adjacent sets
1030        map.m.insert(Unbounded, set12.clone());
1031        map.m.insert(Included(5), set12.clone());
1032        map.merge_adjacent_left(Included(5));
1033
1034        // Should only have one entry after merging
1035        assert_eq!(map.m.len(), 1);
1036        assert_eq!(map.m.get(&Unbounded), Some(&set12));
1037
1038        // Test case 2: Don't merge different sets
1039        let mut map = SpanMap::new();
1040        map.m.insert(Unbounded, set12.clone());
1041        map.m.insert(Included(5), set23.clone());
1042        map.merge_adjacent_left(Included(5));
1043
1044        // Should still have two entries
1045        assert_eq!(map.m.len(), 2);
1046        assert!(map.m.contains_key(&Included(5)));
1047
1048        // Test case 3: Single entry (no left adjacent range)
1049        let mut map = SpanMap::new();
1050        map.m.insert(Included(5), set12.clone());
1051        map.merge_adjacent_left(Included(5));
1052
1053        // Should remain unchanged
1054        assert_eq!(map.m.len(), 2);
1055        assert!(map.m.contains_key(&Included(5)));
1056
1057        // Test case 4: Empty map
1058        let mut map: SpanMap<i32, i32> = SpanMap::new();
1059        map.merge_adjacent_left(Included(5));
1060
1061        // Should remain empty
1062        assert_eq!(map.m.len(), 1);
1063
1064        // Test case 5: Multiple boundaries, merge middle
1065        let mut map = SpanMap::new();
1066        map.m.insert(Unbounded, set12.clone());
1067        map.m.insert(Included(5), set12.clone());
1068        map.m.insert(Included(10), set23);
1069        map.merge_adjacent_left(Included(5));
1070
1071        // Should have two entries after merging
1072        assert_eq!(map.m.len(), 2);
1073        assert!(!map.m.contains_key(&Included(5)));
1074        assert!(map.m.contains_key(&Included(10)));
1075    }
1076}
span_map/lib.rs

span_map/
lib.rs
