iset/
lib.rs

1//! This crates implements map and set with interval keys (ranges `x..y`).
2//!
3//! [IntervalMap](struct.IntervalMap.html) is implemented using red-black binary tree, where each node contains
4//! information about the smallest start and largest end in its subtree.
5//! The tree takes *O(N)* space and allows insertion, removal and search in *O(log N)*.
6//! [IntervalMap](struct.IntervalMap.html) allows to search for all entries overlapping a query (interval or a point,
7//! output would be sorted by keys) in *O(log N + K)* where *K* is the size of the output.
8//!
9//! [IntervalSet](struct.IntervalSet.html) is a newtype over [IntervalMap](struct.IntervalMap.html) with empty values.
10//!
11//! ## Features
12//! By default, `iset` is `no_std`.
13//! Three optional features are:
14//! - `std`: no additional effects,
15//! - `serde`: Serialization/Deserialization (requires `std` environment),
16//! - `dot`: allows to write interval maps and sets to .dot files (requires `std`).
17
18#![no_std]
19
20#[cfg(feature = "std")]
21extern crate std;
22extern crate alloc;
23
24pub mod ix;
25pub mod iter;
26pub mod set;
27pub mod entry;
28mod tree_rm;
29mod bitvec;
30
31#[cfg(all(test, feature = "std"))]
32mod tests;
33
34use alloc::vec::Vec;
35use core::{
36    ops::{Range, RangeFull, RangeInclusive, RangeBounds, Bound, AddAssign, Sub, Index},
37    fmt::{self, Debug, Display, Formatter},
38    cmp::Ordering,
39    iter::FromIterator,
40};
41#[cfg(feature = "dot")]
42use std::io::{self, Write};
43#[cfg(feature = "serde")]
44use {
45    core::marker::PhantomData,
46    serde::{Serialize, Serializer, Deserialize, Deserializer},
47    serde::ser::{SerializeTuple, SerializeSeq},
48    serde::de::{Visitor, SeqAccess},
49};
50
51use ix::IndexType;
52use iter::*;
53use bitvec::BitVec;
54
55pub use ix::DefaultIx;
56pub use set::IntervalSet;
57pub use entry::Entry;
58
59#[derive(Clone, Debug, PartialEq, PartialOrd)]
60struct Interval<T> {
61    start: T,
62    end: T,
63}
64
65impl<T: PartialOrd + Copy> Interval<T> {
66    fn new(range: &Range<T>) -> Self {
67        check_interval(range.start, range.end);
68        Interval {
69            start: range.start,
70            end: range.end,
71        }
72    }
73
74    fn intersects_range<R: RangeBounds<T>>(&self, range: &R) -> bool {
75        // Each match returns bool
76        (match range.end_bound() {
77            Bound::Included(&value) => self.start <= value,
78            Bound::Excluded(&value) => self.start < value,
79            Bound::Unbounded => true,
80        })
81            &&
82        (match range.start_bound() {
83            Bound::Included(&value) | Bound::Excluded(&value) => self.end > value,
84            Bound::Unbounded => true,
85        })
86    }
87
88    fn extend(&mut self, other: &Interval<T>) {
89        if other.start < self.start {
90            self.start = other.start;
91        }
92        if other.end > self.end {
93            self.end = other.end;
94        }
95    }
96
97    fn contains(&self, other: &Interval<T>) -> bool {
98        self.start <= other.start && other.end <= self.end
99    }
100}
101
102impl<T: Copy> Interval<T> {
103    #[inline]
104    fn to_range(&self) -> Range<T> {
105        self.start..self.end
106    }
107}
108
109impl<T: Display> Display for Interval<T> {
110    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
111        write!(f, "{}..{}", self.start, self.end)
112    }
113}
114
115impl<T: PartialOrd + Copy> Ord for Interval<T> {
116    fn cmp(&self, other: &Self) -> Ordering {
117        // Implement cmp by ourselves because T can be PartialOrd.
118        if self.start < other.start {
119            Ordering::Less
120        } else if self.start == other.start {
121            if self.end < other.end {
122                Ordering::Less
123            } else if self.end == other.end {
124                Ordering::Equal
125            } else {
126                Ordering::Greater
127            }
128        } else {
129            Ordering::Greater
130        }
131    }
132}
133
134impl<T: PartialOrd + Copy> Eq for Interval<T> { }
135
136#[cfg(feature = "serde")]
137impl<T: Serialize> Serialize for Interval<T> {
138    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
139        (&self.start, &self.end).serialize(serializer)
140    }
141}
142
143#[cfg(feature = "serde")]
144impl<'de, T: Deserialize<'de>> Deserialize<'de> for Interval<T> {
145    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
146        let (start, end) = <(T, T)>::deserialize(deserializer)?;
147        Ok(Interval { start, end })
148    }
149}
150
151#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
152#[derive(Debug, Clone)]
153struct Node<T, V, Ix> {
154    interval: Interval<T>,
155    subtree_interval: Interval<T>,
156    value: V,
157    left: Ix,
158    right: Ix,
159    parent: Ix,
160}
161
162impl<T: Copy, V, Ix: IndexType> Node<T, V, Ix> {
163    fn new(interval: Interval<T>, value: V) -> Self {
164        Node {
165            interval: interval.clone(),
166            subtree_interval: interval,
167            value,
168            left: Ix::MAX,
169            right: Ix::MAX,
170            parent: Ix::MAX,
171        }
172    }
173}
174
175impl<T, V, Ix: IndexType> Node<T, V, Ix> {
176    /// Swaps values and intervals between two mutable nodes.
177    fn swap_with(&mut self, other: &mut Self) {
178        core::mem::swap(&mut self.value, &mut other.value);
179        core::mem::swap(&mut self.interval, &mut other.interval);
180        core::mem::swap(&mut self.subtree_interval, &mut other.subtree_interval);
181    }
182}
183
184#[cfg(feature = "dot")]
185impl<T: Display, V: Display, Ix: IndexType> Node<T, V, Ix> {
186    fn write_dot<W: Write>(&self, index: usize, is_red: bool, mut writer: W) -> io::Result<()> {
187        writeln!(writer, "    {} [label=\"i={}\\n{}: {}\\nsubtree: {}\", fillcolor={}, style=filled]",
188            index, index, self.interval, self.value, self.subtree_interval, if is_red { "salmon" } else { "grey65" })?;
189        if self.left.defined() {
190            writeln!(writer, "    {} -> {} [label=\"L\"]", index, self.left)?;
191        }
192        if self.right.defined() {
193            writeln!(writer, "    {} -> {} [label=\"R\"]", index, self.right)?;
194        }
195        Ok(())
196    }
197}
198
199#[cfg(feature = "dot")]
200impl<T: Display, V, Ix: IndexType> Node<T, V, Ix> {
201    fn write_dot_without_values<W: Write>(&self, index: usize, is_red: bool, mut writer: W) -> io::Result<()> {
202        writeln!(writer, "    {} [label=\"i={}: {}\\nsubtree: {}\", fillcolor={}, style=filled]",
203            index, index, self.interval, self.subtree_interval, if is_red { "salmon" } else { "grey65" })?;
204        if self.left.defined() {
205            writeln!(writer, "    {} -> {} [label=\"L\"]", index, self.left)?;
206        }
207        if self.right.defined() {
208            writeln!(writer, "    {} -> {} [label=\"R\"]", index, self.right)?;
209        }
210        Ok(())
211    }
212}
213
214fn check_interval<T: PartialOrd + Copy>(start: T, end: T) {
215    if start < end {
216        assert!(end > start, "Interval cannot be ordered (`start < end` but not `end > start`)");
217    } else if end <= start {
218        panic!("Interval is empty (`start >= end`)");
219    } else {
220        panic!("Interval cannot be ordered (not `start < end` and not `end <= start`)");
221    }
222}
223
224fn check_interval_incl<T: PartialOrd + Copy>(start: T, end: T) {
225    if start <= end {
226        assert!(end >= start, "Interval cannot be ordered (`start < end` but not `end > start`)");
227    } else if end < start {
228        panic!("Interval is empty (`start > end`)");
229    } else {
230        panic!("Interval cannot be ordered (not `start <= end` and not `end < start`)");
231    }
232}
233
234fn check_ordered<T: PartialOrd, R: RangeBounds<T>>(range: &R) {
235    match (range.start_bound(), range.end_bound()) {
236        (_, Bound::Unbounded) | (Bound::Unbounded, _) => {},
237        (Bound::Included(a), Bound::Included(b)) => check_interval_incl(a, b),
238        (Bound::Included(a), Bound::Excluded(b))
239        | (Bound::Excluded(a), Bound::Included(b))
240        | (Bound::Excluded(a), Bound::Excluded(b)) => check_interval(a, b),
241    }
242}
243
244/// Map with interval keys (`x..y`).
245///
246/// Range bounds should implement `PartialOrd` and `Copy`, for example any
247/// integer or float types. However, you cannot use values that cannot be used in comparison (such as `NAN`),
248/// although infinity is allowed.
249/// There are no restrictions on values.
250///
251/// # Example
252///```rust
253/// let mut map = iset::interval_map!{ 20..30 => 'a', 15..25 => 'b', 10..20 => 'c' };
254/// assert_eq!(map.insert(10..20, 'd'), Some('c'));
255/// assert_eq!(map.insert(5..15, 'e'), None);
256///
257/// // Iterator over all pairs (range, value). Output is sorted.
258/// let a: Vec<_> = map.iter(..).collect();
259/// assert_eq!(a, &[(5..15, &'e'), (10..20, &'d'), (15..25, &'b'), (20..30, &'a')]);
260///
261/// // Iterate over intervals that overlap query (..20 here). Output is sorted.
262/// let b: Vec<_> = map.intervals(..20).collect();
263/// assert_eq!(b, &[5..15, 10..20, 15..25]);
264///
265/// assert_eq!(map[15..25], 'b');
266/// // Replace 15..25 => 'b' into 'z'.
267/// *map.get_mut(15..25).unwrap() = 'z';
268///
269/// // Iterate over values that overlap query (20.. here). Output is sorted by intervals.
270/// let c: Vec<_> = map.values(20..).collect();
271/// assert_eq!(c, &[&'z', &'a']);
272///
273/// // Remove 10..20 => 'd'.
274/// assert_eq!(map.remove(10..20), Some('d'));
275/// ```
276///
277/// # Insertion, search and removal
278///
279/// All three operations take *O(log N)*.
280/// By default, this crate does not allow duplicate keys, [insert](#method.insert) replaces and returns the old
281/// value if the interval was already present in the map.
282/// Note, that the key is not updated even if the value is replaced.
283/// This matters for types that can be `==` without being identical.
284///
285/// Search operations [contains](#method.contains), [get](#method.get) and [get_mut](#method.get_mut) is usually faster
286/// than insertion or removal, as the tree does not need to be rebalanced.
287///
288/// You can remove nodes from the tree using [remove](#method.remove) method given the interval key.
289/// Currently, it is not feasible to have a method that removes multiple nodes at once
290/// (for example based on a predicate).
291///
292/// It is possible to store entries with equal intervals by calling [force_insert](#method.force_insert).
293/// This method should be used with care, as methods [get](#method.get), [get_mut](#method.get_mut) and
294/// [remove](#method.remove) only return/remove a single entry (see [force_insert](#method.force_insert) for more details).
295/// Nevertheless, functions [values_at](#method.values_at) and [values_mut_at](#method.values_mut_at)
296/// allow to iterate over all values with exactly matching query,
297/// and [remove_where](#method.remove_where) allows to remove an entry with matching interval based on a predicate.
298///
299/// Additionally, it is possible to get or remove the entry with the smallest/largest interval in the map
300/// (in lexicographical order), see [smallest](#method.smallest), [largest](#method.largest), etc.
301/// These methods take *O(log N)* as well.
302///
303/// Method [range](#method.range) allows to extract interval range `(min_start, max_end)` in *O(1)*.
304/// Method [covered_len](#method.covered_len) is designed to calculate the total length of a query that is covered
305/// by the intervals in the map. Method [has_overlap](#method.has_overlap) allows to quickly find if the query overlaps
306/// any intervals in the map.
307///
308/// # Iteration
309///
310/// Interval map allows to quickly find all intervals that overlap a query interval in *O(log N + K)* where *K* is
311/// the size of the output. All iterators traverse entries in a sorted order
312/// (sorted lexicographically by intervals).
313/// Iteration methods include:
314/// - [iter](#method.iter): iterate over pairs `(x..y, &value)`,
315/// - [intervals](#method.intervals): iterate over interval keys `x..y`,
316/// - [values](#method.values): iterate over values `&value`,
317/// - Mutable iterators [iter_mut](#method.iter_mut) and [values_mut](#method.values_mut),
318/// - Into iterators [into_iter](#method.into_iter), [into_intervals](#method.into_intervals) and
319/// [into_values](#method.into_values),
320/// - Iterators over values with exactly matching intervals
321/// [values_at](#method.values_at) and [values_mut_at](#method.values_mut_at).
322///
323/// Additionally, most methods have their `unsorted_` counterparts
324/// (for example [unsorted_iter](#method.unsorted_iter)).
325/// These iterators traverse the whole map in an arbitrary *unsorted* order.
326/// Although both `map.iter(..)` and `map.unsorted_iter()` output all entries in the map and both take *O(N)*,
327/// unsorted iterator is slightly faster as it reads the memory consecutively instead of traversing the tree.
328///
329/// Methods `iter`, `intervals`, `values`, `iter_mut` and `values_mut` have alternatives [overlap](#method.overlap),
330/// [overlap_intervals](#method.overlap_intervals), ..., that allow to iterate over all entries that
331/// cover a single point `x` (same as `x..=x`).
332///
333/// # Index types
334///
335/// Every node in the tree stores three indices (to the parent and two children), and as a result, memory usage can be
336/// reduced by reducing index sizes. In most cases, number of items in the map does not exceed `u32::MAX`, therefore
337/// we store indices as `u32` numbers by default (`iset::DefaultIx = u32`).
338/// You can use four integer types (`u8`, `u16`, `u32` or `u64`) as index types.
339/// Number of elements in the interval map cannot exceed `IndexType::MAX - 1`: for example a map with `u8` indices
340/// can store up to 255 items.
341///
342/// Using smaller index types saves memory and may reduce running time.
343///
344/// # Interval map creation
345///
346/// An interval map can be created using the following methods:
347/// ```rust
348/// use iset::{interval_map, IntervalMap};
349///
350/// // Creates an empty interval map with the default index type (u32):
351/// let mut map = IntervalMap::new();
352/// map.insert(10..20, 'a');
353///
354/// // Creates an empty interval map and specifies index type (u16 here):
355/// let mut map = IntervalMap::<_, _, u16>::default();
356/// map.insert(10..20, 'a');
357///
358/// let mut map = IntervalMap::<_, _, u16>::with_capacity(10);
359/// map.insert(10..20, 'a');
360///
361/// // Creates an interval map with the default index type:
362/// let map = interval_map!{ 0..10 => 'a', 5..15 => 'b' };
363///
364/// // Creates an interval map and specifies index type:
365/// let map = interval_map!{ [u16] 0..10 => 'a', 5..15 => 'b' };
366///
367/// // Creates an interval map from a sorted iterator, takes O(N):
368/// let vec = vec![(0..10, 'b'), (5..15, 'a')];
369/// let map = IntervalMap::<_, _, u32>::from_sorted(vec.into_iter());
370///
371/// // Alternatively, you can use `.collect()` method that creates an interval map
372/// // with the default index size. `Collect` does not require sorted intervals,
373/// // but takes O(N log N).
374/// let vec = vec![(5..15, 'a'), (0..10, 'b')];
375/// let map: IntervalMap<_, _> = vec.into_iter().collect();
376/// ```
377///
378/// # Entry API
379/// IntervalMap implements [Entry](entry/enum.Entry.html), for updating and inserting values
380/// directly after search was made.
381/// ```
382/// let mut map = iset::IntervalMap::new();
383/// map.entry(0..100).or_insert("abc".to_string());
384/// map.entry(100..200).or_insert_with(|| "def".to_string());
385/// let val = map.entry(200..300).or_insert(String::new());
386/// *val += "ghi";
387/// map.entry(200..300).and_modify(|s| *s += "jkl").or_insert("xyz".to_string());
388///
389/// assert_eq!(map[0..100], "abc");
390/// assert_eq!(map[100..200], "def");
391/// assert_eq!(map[200..300], "ghijkl");
392/// ```
393///
394/// # Implementation, merge and split
395///
396/// To allow for fast retrieval of all intervals overlapping a query, we store the range of the subtree in each node
397/// of the tree. Additionally, each node stores indices to the parent and to two children.
398/// As a result, size of the map is approximately `n * (4 * sizeof(T) + sizeof(V) + 3 * sizeof(Ix))`,
399/// where `n` is the number of elements.
400///
401/// In order to reduce number of heap allocations and access memory consecutively, we store tree nodes in a vector.
402/// This does not impact time complexity of all methods except for *merge* and *split*.
403/// In a heap-allocated tree, merge takes *O(M log (N / M + 1))* where *M* is the size of the smaller tree.
404/// Here, we are required to merge sorted iterators and construct a tree using the sorted iterator as input,
405/// which takes *O(N + M)*.
406///
407/// Because of that, this crate does not implement merge or split, however, these procedures can be emulated using
408/// [from_sorted](#method.from_sorted), [itertools::merge](https://docs.rs/itertools/latest/itertools/fn.merge.html)
409/// and [Iterator::partition](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.partition) in linear time.
410#[derive(Clone)]
411pub struct IntervalMap<T, V, Ix: IndexType = DefaultIx> {
412    nodes: Vec<Node<T, V, Ix>>,
413    // true if the node is red, false if black.
414    colors: BitVec,
415    root: Ix,
416}
417
418impl<T: PartialOrd + Copy, V> IntervalMap<T, V> {
419    /// Creates an empty [IntervalMap](struct.IntervalMap.html)
420    /// with default index type [DefaultIx](ix/type.DefaultIx.html).
421    pub fn new() -> Self {
422        Self::default()
423    }
424}
425
426impl<T: PartialOrd + Copy, V, Ix: IndexType> Default for IntervalMap<T, V, Ix> {
427    fn default() -> Self {
428        Self {
429            nodes: Vec::new(),
430            colors: BitVec::new(),
431            root: Ix::MAX,
432        }
433    }
434}
435
436impl<T: PartialOrd + Copy, V, Ix: IndexType> IntervalMap<T, V, Ix> {
437    /// Creates an empty [IntervalMap](struct.IntervalMap.html) with `capacity`.
438    pub fn with_capacity(capacity: usize) -> Self {
439        Self {
440            nodes: Vec::with_capacity(capacity),
441            colors: BitVec::with_capacity(capacity),
442            root: Ix::MAX,
443        }
444    }
445
446    /// Initializes map within indices [start, end) in case of sorted nodes.
447    /// rev_depth: inverse depth (top recursion call has high rev_depth, lowest recursion call has rev_depth == 1).
448    fn init_from_sorted(&mut self, start: usize, end: usize, rev_depth: u16) -> Ix {
449        debug_assert!(start < end);
450        if start + 1 == end {
451            if rev_depth == 1 {
452                // Set red.
453                self.colors.set1(start);
454            }
455            return Ix::new(start).unwrap();
456        }
457
458        let center = (start + end) / 2;
459        let center_ix = Ix::new(center).unwrap();
460        if start < center {
461            let left_ix = self.init_from_sorted(start, center, rev_depth - 1);
462            self.nodes[center].left = left_ix;
463            self.nodes[left_ix.get()].parent = center_ix;
464        }
465        if center + 1 < end {
466            let right_ix = self.init_from_sorted(center + 1, end, rev_depth - 1);
467            self.nodes[center].right = right_ix;
468            self.nodes[right_ix.get()].parent = center_ix;
469        }
470        self.update_subtree_interval(center_ix);
471        center_ix
472    }
473
474    /// Creates an interval map from a sorted iterator over pairs `(range, value)`. Takes *O(N)*.
475    ///
476    /// Panics if the intervals are not sorted or if there are equal intervals.
477    pub fn from_sorted<I>(iter: I) -> Self
478    where I: Iterator<Item = (Range<T>, V)>,
479    {
480        let nodes: Vec<_> = iter.map(|(range, value)| Node::new(Interval::new(&range), value)).collect();
481        let n = nodes.len();
482        let mut map = Self {
483            nodes,
484            colors: BitVec::from_elem(n, false), // Start with all black nodes.
485            root: Ix::MAX,
486        };
487        for i in 1..n {
488            assert!(map.nodes[i - 1].interval < map.nodes[i].interval,
489                "Cannot construct interval map from sorted nodes: intervals at positions {} and {} are unordered!",
490                i, i + 1);
491        }
492        if n > 0 {
493            let max_depth = (usize::BITS - n.leading_zeros()) as u16;
494            map.root = map.init_from_sorted(0, n, max_depth);
495        }
496        map
497    }
498
499    /// Returns the number of elements in the map.
500    #[inline]
501    pub fn len(&self) -> usize {
502        self.nodes.len()
503    }
504
505    /// Returns `true` if the map contains no elements.
506    #[inline]
507    pub fn is_empty(&self) -> bool {
508        self.nodes.is_empty()
509    }
510
511    /// Clears the map, removing all values. This method has no effect on the allocated capacity.
512    pub fn clear(&mut self) {
513        self.nodes.clear();
514        self.colors.clear();
515        self.root = Ix::MAX;
516    }
517
518    /// Shrinks inner contents.
519    pub fn shrink_to_fit(&mut self) {
520        self.nodes.shrink_to_fit();
521        self.colors.shrink_to_fit();
522    }
523
524    #[inline]
525    fn is_red(&self, ix: Ix) -> bool {
526        self.colors.get(ix.get())
527    }
528
529    #[inline]
530    fn is_black(&self, ix: Ix) -> bool {
531        !self.colors.get(ix.get())
532    }
533
534    #[inline]
535    fn is_black_or_nil(&self, ix: Ix) -> bool {
536        !ix.defined() || !self.colors.get(ix.get())
537    }
538
539    #[inline]
540    fn set_red(&mut self, ix: Ix) {
541        self.colors.set1(ix.get());
542    }
543
544    #[inline]
545    fn set_black(&mut self, ix: Ix) {
546        self.colors.set0(ix.get());
547    }
548
549    fn update_subtree_interval(&mut self, index: Ix) {
550        let node = &self.nodes[index.get()];
551        let mut subtree_interval = node.interval.clone();
552        if node.left.defined() {
553            subtree_interval.extend(&self.nodes[node.left.get()].subtree_interval);
554        }
555        if node.right.defined() {
556            subtree_interval.extend(&self.nodes[node.right.get()].subtree_interval);
557        }
558        self.nodes[index.get()].subtree_interval = subtree_interval;
559    }
560
561    fn sibling(&self, index: Ix) -> Ix {
562        let parent = self.nodes[index.get()].parent;
563        if !parent.defined() {
564            Ix::MAX
565        } else if self.nodes[parent.get()].left == index {
566            self.nodes[parent.get()].right
567        } else {
568            self.nodes[parent.get()].left
569        }
570    }
571
572    fn rotate_left(&mut self, index: Ix) {
573        let prev_parent = self.nodes[index.get()].parent;
574        let prev_right = self.nodes[index.get()].right;
575        debug_assert!(prev_right.defined());
576
577        let new_right = self.nodes[prev_right.get()].left;
578        self.nodes[index.get()].right = new_right;
579        if new_right.defined() {
580            self.nodes[new_right.get()].parent = index;
581        }
582        self.update_subtree_interval(index);
583
584        self.nodes[prev_right.get()].left = index;
585        self.nodes[index.get()].parent = prev_right;
586        self.update_subtree_interval(prev_right);
587
588        if prev_parent.defined() {
589            if self.nodes[prev_parent.get()].left == index {
590                self.nodes[prev_parent.get()].left = prev_right;
591            } else {
592                self.nodes[prev_parent.get()].right = prev_right;
593            }
594            self.nodes[prev_right.get()].parent = prev_parent;
595            self.update_subtree_interval(prev_parent);
596        } else {
597            self.root = prev_right;
598            self.nodes[prev_right.get()].parent = Ix::MAX;
599        }
600    }
601
602    fn rotate_right(&mut self, index: Ix) {
603        let prev_parent = self.nodes[index.get()].parent;
604        let prev_left = self.nodes[index.get()].left;
605        debug_assert!(prev_left.defined());
606
607        let new_left = self.nodes[prev_left.get()].right;
608        self.nodes[index.get()].left = new_left;
609        if new_left.defined() {
610            self.nodes[new_left.get()].parent = index;
611        }
612        self.update_subtree_interval(index);
613
614        self.nodes[prev_left.get()].right = index;
615        self.nodes[index.get()].parent = prev_left;
616        self.update_subtree_interval(prev_left);
617
618        if prev_parent.defined() {
619            if self.nodes[prev_parent.get()].right == index {
620                self.nodes[prev_parent.get()].right = prev_left;
621            } else {
622                self.nodes[prev_parent.get()].left = prev_left;
623            }
624            self.nodes[prev_left.get()].parent = prev_parent;
625            self.update_subtree_interval(prev_parent);
626        } else {
627            self.root = prev_left;
628            self.nodes[prev_left.get()].parent = Ix::MAX;
629        }
630    }
631
632    fn insert_repair(&mut self, mut index: Ix) {
633        loop {
634            debug_assert!(self.is_red(index));
635            if index == self.root {
636                self.set_black(index);
637                return;
638            }
639
640            // parent should be defined
641            let parent = self.nodes[index.get()].parent;
642            if self.is_black(parent) {
643                return;
644            }
645
646            // parent is red
647            // grandparent should be defined
648            let grandparent = self.nodes[parent.get()].parent;
649            let uncle = self.sibling(parent);
650
651            if uncle.defined() && self.is_red(uncle) {
652                self.set_black(parent);
653                self.set_black(uncle);
654                self.set_red(grandparent);
655                index = grandparent;
656                continue;
657            }
658
659            if index == self.nodes[parent.get()].right && parent == self.nodes[grandparent.get()].left {
660                self.rotate_left(parent);
661                index = self.nodes[index.get()].left;
662            } else if index == self.nodes[parent.get()].left && parent == self.nodes[grandparent.get()].right {
663                self.rotate_right(parent);
664                index = self.nodes[index.get()].right;
665            }
666
667            let parent = self.nodes[index.get()].parent;
668            let grandparent = self.nodes[parent.get()].parent;
669            if index == self.nodes[parent.get()].left {
670                self.rotate_right(grandparent);
671            } else {
672                self.rotate_left(grandparent);
673            }
674            self.set_black(parent);
675            self.set_red(grandparent);
676            return;
677        }
678    }
679
680    fn fix_intervals_up(&mut self, mut ix: Ix) {
681        while ix.defined() {
682            self.update_subtree_interval(ix);
683            ix = self.nodes[ix.get()].parent;
684        }
685    }
686
687    /// Inserts pair `(interval, value)` as a child of `parent`. Left child if `left_child`, right child otherwise.
688    /// Returns mutable reference to the added value.
689    fn insert_at(&mut self, parent: Ix, left_child: bool, interval: Interval<T>, value: V) -> &mut V {
690        let mut new_node = Node::new(interval, value);
691        let new_index = Ix::new(self.nodes.len()).unwrap();
692
693        if !parent.defined() {
694            assert!(self.nodes.is_empty());
695            self.nodes.push(new_node);
696            // New node should be black.
697            self.colors.push(false);
698            self.root = new_index;
699            return &mut self.nodes[new_index.get()].value;
700        }
701
702        new_node.parent = parent;
703        self.nodes.push(new_node);
704        if left_child {
705            self.nodes[parent.get()].left = new_index;
706        } else {
707            self.nodes[parent.get()].right = new_index;
708        }
709        self.colors.push(true);
710        self.fix_intervals_up(parent);
711        self.insert_repair(new_index);
712        &mut self.nodes[new_index.get()].value
713    }
714
715    /// Insert pair `(interval, value)`.
716    /// If both `replace` and `interval` was already in the map, replacing the value and returns the old value.
717    /// Otherwise, inserts a new node and returns None.
718    fn insert_inner(&mut self, interval: Range<T>, value: V, replace: bool) -> Option<V> {
719        let interval = Interval::new(&interval);
720        let mut current = self.root;
721
722        if !current.defined() {
723            self.insert_at(current, true, interval, value);
724            return None;
725        }
726        loop {
727            let node = &mut self.nodes[current.get()];
728            let (child, left_side) = match interval.cmp(&node.interval) {
729                Ordering::Less => (node.left, true),
730                Ordering::Equal if replace => return Some(core::mem::replace(&mut node.value, value)),
731                Ordering::Equal | Ordering::Greater => (node.right, false),
732            };
733            if child.defined() {
734                current = child;
735            } else {
736                self.insert_at(current, left_side, interval, value);
737                return None;
738            }
739        }
740    }
741
742    /// Gets the given key's corresponding entry in the map for in-place manipulation.
743    /// ```
744    /// let mut counts = iset::IntervalMap::new();
745    /// for x in [0..5, 3..9, 2..6, 0..5, 2..6, 2..6] {
746    ///     counts.entry(x).and_modify(|curr| *curr += 1).or_insert(1);
747    /// }
748    /// assert_eq!(counts[0..5], 2);
749    /// assert_eq!(counts[3..9], 1);
750    /// assert_eq!(counts[2..6], 3);
751    /// ```
752    pub fn entry<'a>(&'a mut self, interval: Range<T>) -> Entry<'a, T, V, Ix> {
753        let interval = Interval::new(&interval);
754        let mut current = self.root;
755        if !current.defined() {
756            return Entry::Vacant(entry::VacantEntry::new(self, current, true, interval));
757        }
758        loop {
759            let node = &mut self.nodes[current.get()];
760            let (child, left_side) = match interval.cmp(&node.interval) {
761                Ordering::Less => (node.left, true),
762                Ordering::Greater => (node.right, false),
763                Ordering::Equal => return Entry::Occupied(entry::OccupiedEntry::new(self, current)),
764            };
765            if child.defined() {
766                current = child;
767            } else {
768                return Entry::Vacant(entry::VacantEntry::new(self, current, left_side, interval));
769            }
770        }
771    }
772
773    /// Inserts an interval `x..y` and its value into the map. Takes *O(log N)*.
774    ///
775    /// If the map did not contain the interval, returns `None`. Otherwise returns the old value.
776    ///
777    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
778    pub fn insert(&mut self, interval: Range<T>, value: V) -> Option<V> {
779        self.insert_inner(interval, value, true)
780    }
781
782    /// Inserts an interval `x..y` and its value into the map even if there was an entry with matching interval.
783    /// Takes *O(log N)*.
784    ///
785    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
786    ///
787    /// <div class="example-wrap" style="display:inline-block"><pre class="compile_fail" style="white-space:normal;font:inherit;">
788    ///
789    /// **Warning:** After `force_insert`, the map can contain several entries with equal intervals.
790    /// Calling [get](#method.get), [get_mut](#method.get_mut) or [remove](#method.remove)
791    /// will arbitrarily
792    /// return/remove only one of the entries.
793    ///
794    /// Various iterators will output all appropriate intervals, however the order of entries with equal intervals
795    /// will be arbitrary.
796    /// </pre></div>
797    ///
798    /// ```rust
799    /// let mut map = iset::interval_map!{};
800    /// map.force_insert(10..20, 1);
801    /// map.force_insert(15..25, 2);
802    /// map.force_insert(20..30, 3);
803    /// map.force_insert(15..25, 4);
804    ///
805    /// // Returns either 2 or 4.
806    /// assert!(map.get(15..25).unwrap() % 2 == 0);
807    /// // Removes either 15..25 => 2 or 15..25 => 4.
808    /// assert!(map.remove(15..25).unwrap() % 2 == 0);
809    /// println!("{:?}", map);
810    /// // {10..20 => 1, 15..25 => 4, 20..30 => 3} OR
811    /// // {10..20 => 1, 15..25 => 2, 20..30 => 3}
812    /// ```
813    pub fn force_insert(&mut self, interval: Range<T>, value: V) {
814        // Cannot be replaced with debug_assert.
815        assert!(self.insert_inner(interval, value, false).is_none(), "Force insert should always return None");
816    }
817
818    fn find_index(&self, interval: &Interval<T>) -> Ix {
819        let mut index = self.root;
820        while index.defined() {
821            let node = &self.nodes[index.get()];
822            match interval.cmp(&node.interval) {
823                Ordering::Less => index = node.left,
824                Ordering::Greater => index = node.right,
825                Ordering::Equal => return index,
826            }
827        }
828        index
829    }
830
831    /// Check if the interval map contains `interval` (exact match).
832    ///
833    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
834    pub fn contains(&self, interval: Range<T>) -> bool {
835        self.find_index(&Interval::new(&interval)).defined()
836    }
837
838    /// Returns value associated with `interval` (exact match).
839    /// If there is no such interval, returns `None`.
840    ///
841    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
842    pub fn get(&self, interval: Range<T>) -> Option<&V> {
843        let index = self.find_index(&Interval::new(&interval));
844        if index.defined() {
845            Some(&self.nodes[index.get()].value)
846        } else {
847            None
848        }
849    }
850
851    /// Returns mutable value associated with `interval` (exact match).
852    /// If there is no such interval, returns `None`.
853    ///
854    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
855    pub fn get_mut(&mut self, interval: Range<T>) -> Option<&mut V> {
856        let index = self.find_index(&Interval::new(&interval));
857        if index.defined() {
858            Some(&mut self.nodes[index.get()].value)
859        } else {
860            None
861        }
862    }
863
864    /// Removes an entry, associated with `interval` (exact match is required), takes *O(log N)*.
865    /// Returns value if the interval was present in the map, and None otherwise.
866    ///
867    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
868    pub fn remove(&mut self, interval: Range<T>) -> Option<V> {
869        self.remove_at(self.find_index(&Interval::new(&interval)))
870    }
871
872    /// Removes an entry, associated with `interval` (exact match is required),
873    /// where `predicate(&value)` returns true.
874    /// After `predicate` returns `true`, it is not invoked again.
875    /// Returns the value of the removed entry, if present, and None otherwise.
876    ///
877    /// Takes *O(log N + K)* where *K* is the number of entries with `interval`.
878    ///
879    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
880    ///
881    /// # Examples
882    /// ```rust
883    /// let mut map = iset::IntervalMap::new();
884    /// map.force_insert(5..15, 0);
885    /// map.force_insert(10..20, 1);
886    /// map.force_insert(10..20, 2);
887    /// map.force_insert(10..20, 3);
888    /// map.force_insert(10..20, 4);
889    /// map.force_insert(15..25, 5);
890    ///
891    /// // Remove an entry with an even value
892    /// let removed = map.remove_where(10..20, |&x| x % 2 == 0);
893    /// assert!(removed == Some(2) || removed == Some(4));
894    ///
895    /// // Remove the entry with the minimum value
896    /// let minimum = map.values_at(10..20).cloned().min().unwrap();
897    /// assert_eq!(minimum, 1);
898    /// let removed = map.remove_where(10..20, |&x| x == minimum);
899    /// assert_eq!(removed, Some(1));
900    /// assert_eq!(map.len(), 4);
901    /// ```
902    pub fn remove_where(&mut self, interval: Range<T>, mut predicate: impl FnMut(&V) -> bool) -> Option<V> {
903        let mut values_it = self.values_at(interval);
904        while let Some(val) = values_it.next() {
905            if predicate(val) {
906                return self.remove_at(values_it.index);
907            }
908        }
909        None
910    }
911
912    /// Returns a range of interval keys in the map, takes *O(1)*. Returns `None` if the map is empty.
913    /// `out.start` is the minimal start of all intervals in the map,
914    /// and `out.end` is the maximal end of all intervals in the map.
915    pub fn range(&self) -> Option<Range<T>> {
916        if self.root.defined() {
917            Some(self.nodes[self.root.get()].subtree_interval.to_range())
918        } else {
919            None
920        }
921    }
922
923    fn smallest_index(&self) -> Ix {
924        let mut index = self.root;
925        while self.nodes[index.get()].left.defined() {
926            index = self.nodes[index.get()].left;
927        }
928        index
929    }
930
931    fn largest_index(&self) -> Ix {
932        let mut index = self.root;
933        while self.nodes[index.get()].right.defined() {
934            index = self.nodes[index.get()].right;
935        }
936        index
937    }
938
939    /// Returns the pair `(x..y, &value)` with the smallest interval `x..y` (in lexicographical order).
940    /// Takes *O(log N)*. Returns `None` if the map is empty.
941    pub fn smallest(&self) -> Option<(Range<T>, &V)> {
942        if !self.root.defined() {
943            None
944        } else {
945            let node = &self.nodes[self.smallest_index().get()];
946            Some((node.interval.to_range(), &node.value))
947        }
948    }
949
950    /// Returns the pair `(x..y, &mut value)` with the smallest interval `x..y` (in lexicographical order).
951    /// Takes *O(log N)*. Returns `None` if the map is empty.
952    pub fn smallest_mut(&mut self) -> Option<(Range<T>, &mut V)> {
953        if !self.root.defined() {
954            None
955        } else {
956            let index = self.smallest_index();
957            let node = &mut self.nodes[index.get()];
958            Some((node.interval.to_range(), &mut node.value))
959        }
960    }
961
962    /// Removes the smallest interval `x..y` (in lexicographical order) from the map and returns pair `(x..y, value)`.
963    /// Takes *O(log N)*. Returns `None` if the map is empty.
964    pub fn remove_smallest(&mut self) -> Option<(Range<T>, V)> {
965        if !self.root.defined() {
966            None
967        } else {
968            let index = self.smallest_index();
969            let range = self.nodes[index.get()].interval.to_range();
970            Some((range, self.remove_at(index).unwrap()))
971        }
972    }
973
974    /// Returns the pair `(x..y, &value)` with the largest interval `x..y` (in lexicographical order).
975    /// Takes *O(log N)*. Returns `None` if the map is empty.
976    pub fn largest(&self) -> Option<(Range<T>, &V)> {
977        if !self.root.defined() {
978            None
979        } else {
980            let node = &self.nodes[self.largest_index().get()];
981            Some((node.interval.to_range(), &node.value))
982        }
983    }
984
985    /// Returns the pair `(x..y, &mut value)` with the largest interval `x..y` (in lexicographical order).
986    /// Takes *O(log N)*. Returns `None` if the map is empty.
987    pub fn largest_mut(&mut self) -> Option<(Range<T>, &mut V)> {
988        if !self.root.defined() {
989            None
990        } else {
991            let index = self.largest_index();
992            let node = &mut self.nodes[index.get()];
993            Some((node.interval.to_range(), &mut node.value))
994        }
995    }
996
997    /// Removes the largest interval `x..y` (in lexicographical order) from the map and returns pair `(x..y, value)`.
998    /// Takes *O(log N)*. Returns `None` if the map is empty.
999    pub fn remove_largest(&mut self) -> Option<(Range<T>, V)> {
1000        if !self.root.defined() {
1001            None
1002        } else {
1003            let index = self.largest_index();
1004            let range = self.nodes[index.get()].interval.to_range();
1005            Some((range, self.remove_at(index).unwrap()))
1006        }
1007    }
1008
1009    /// Checks, if the query overlaps any intervals in the interval map.
1010    /// Equivalent to `map.iter(query).next().is_some()`, but much faster.
1011    ///
1012    /// ```rust
1013    /// let map = iset::interval_map!{ 5..8 => 'a', 10..15 => 'b' };
1014    /// assert!(!map.has_overlap(8..10));
1015    /// assert!(map.has_overlap(8..=10));
1016    /// ```
1017    pub fn has_overlap<R>(&self, query: R) -> bool
1018    where R: RangeBounds<T>,
1019    {
1020        check_ordered(&query);
1021        if !self.root.defined() {
1022            return false;
1023        }
1024
1025        let mut queue = Vec::new();
1026        queue.push(self.root);
1027        while let Some(index) = queue.pop() {
1028            let node = &self.nodes[index.get()];
1029            let subtree_start = node.subtree_interval.start;
1030            let subtree_end = node.subtree_interval.end;
1031
1032            // Query start is less than the subtree interval start,
1033            let q_start_lt_start = match query.start_bound() {
1034                Bound::Unbounded => true,
1035                Bound::Included(&q_start) => {
1036                    if q_start < subtree_start {
1037                        true
1038                    } else if q_start == subtree_start {
1039                        // There is definitely an interval that starts at the same position as the query.
1040                        return true;
1041                    } else if q_start < subtree_end {
1042                        false
1043                    } else {
1044                        // The whole subtree lies to the left of the query.
1045                        continue;
1046                    }
1047                },
1048                Bound::Excluded(&q_start) => {
1049                    if q_start <= subtree_start {
1050                        true
1051                    } else if q_start < subtree_end {
1052                        false
1053                    } else {
1054                        // The whole subtree lies to the left of the query.
1055                        continue;
1056                    }
1057                },
1058            };
1059
1060            // Query end is greater than the subtree interval end.
1061            let q_end_gt_end = match query.end_bound() {
1062                Bound::Unbounded => true,
1063                Bound::Included(&q_end) => {
1064                    if q_end < subtree_start {
1065                        continue;
1066                    } else if q_end == subtree_start {
1067                        // There is definitely an interval that starts at the same position as the query ends.
1068                        return true;
1069                    } else {
1070                        q_end > subtree_end
1071                    }
1072                },
1073                Bound::Excluded(&q_end) => {
1074                    if q_end <= subtree_start {
1075                        continue;
1076                    } else {
1077                        q_end > subtree_end
1078                    }
1079                },
1080            };
1081            if q_start_lt_start || q_end_gt_end || node.interval.intersects_range(&query) {
1082                return true;
1083            }
1084            if node.left.defined() {
1085                queue.push(node.left);
1086            }
1087            if node.right.defined() {
1088                queue.push(node.right);
1089            }
1090        }
1091        false
1092    }
1093
1094    /// Iterates over pairs `(x..y, &value)` that overlap the `query`.
1095    /// Takes *O(log N + K)* where *K* is the size of the output.
1096    /// Output is sorted by intervals, but not by values.
1097    ///
1098    /// Panics if `interval` is empty or contains a value that cannot be compared (such as `NAN`).
1099    pub fn iter<'a, R>(&'a self, query: R) -> Iter<'a, T, V, R, Ix>
1100    where R: RangeBounds<T>,
1101    {
1102        Iter::new(self, query)
1103    }
1104
1105    /// Iterates over intervals `x..y` that overlap the `query`.
1106    /// See [iter](#method.iter) for more details.
1107    pub fn intervals<'a, R>(&'a self, query: R) -> Intervals<'a, T, V, R, Ix>
1108    where R: RangeBounds<T>,
1109    {
1110        Intervals::new(self, query)
1111    }
1112
1113    /// Iterates over values that overlap the `query`.
1114    /// See [iter](#method.iter) for more details.
1115    pub fn values<'a, R>(&'a self, query: R) -> Values<'a, T, V, R, Ix>
1116    where R: RangeBounds<T>,
1117    {
1118        Values::new(self, query)
1119    }
1120
1121    /// Iterator over pairs `(x..y, &mut value)` that overlap the `query`.
1122    /// See [iter](#method.iter) for more details.
1123    pub fn iter_mut<'a, R>(&'a mut self, query: R) -> IterMut<'a, T, V, R, Ix>
1124    where R: RangeBounds<T>,
1125    {
1126        IterMut::new(self, query)
1127    }
1128
1129    /// Iterator over *mutable* values that overlap the `query`.
1130    /// See [iter](#method.iter) for more details.
1131    pub fn values_mut<'a, R>(&'a mut self, query: R) -> ValuesMut<'a, T, V, R, Ix>
1132    where R: RangeBounds<T>,
1133    {
1134        ValuesMut::new(self, query)
1135    }
1136
1137    /// Consumes [IntervalMap](struct.IntervalMap.html) and
1138    /// iterates over pairs `(x..y, value)` that overlap the `query`.
1139    /// See [iter](#method.iter) for more details.
1140    pub fn into_iter<R>(self, query: R) -> IntoIter<T, V, R, Ix>
1141    where R: RangeBounds<T>,
1142    {
1143        IntoIter::new(self, query)
1144    }
1145
1146    /// Consumes [IntervalMap](struct.IntervalMap.html) and
1147    /// iterates over pairs `(x..y, value)` that overlap the `query`.
1148    /// See [iter](#method.iter) for more details.
1149    pub fn into_intervals<R>(self, query: R) -> IntoIntervals<T, V, R, Ix>
1150    where R: RangeBounds<T>,
1151    {
1152        IntoIntervals::new(self, query)
1153    }
1154
1155    /// Consumes [IntervalMap](struct.IntervalMap.html) and
1156    /// iterates over values, for which intervals that overlap the `query`.
1157    /// See [iter](#method.iter) for more details.
1158    pub fn into_values<R>(self, query: R) -> IntoValues<T, V, R, Ix>
1159    where R: RangeBounds<T>,
1160    {
1161        IntoValues::new(self, query)
1162    }
1163
1164    /// Iterates over pairs `(x..y, &value)` that overlap the `point`.
1165    /// See [iter](#method.iter) for more details.
1166    #[inline]
1167    pub fn overlap<'a>(&'a self, point: T) -> Iter<'a, T, V, RangeInclusive<T>, Ix> {
1168        Iter::new(self, point..=point)
1169    }
1170
1171    /// Iterates over intervals `x..y` that overlap the `point`.
1172    /// See [iter](#method.iter) for more details.
1173    #[inline]
1174    pub fn intervals_overlap<'a>(&'a self, point: T) -> Intervals<'a, T, V, RangeInclusive<T>, Ix> {
1175        Intervals::new(self, point..=point)
1176    }
1177
1178    /// Iterates over values that overlap the `point`.
1179    /// See [iter](#method.iter) for more details.
1180    #[inline]
1181    pub fn values_overlap<'a>(&'a self, point: T) -> Values<'a, T, V, RangeInclusive<T>, Ix> {
1182        Values::new(self, point..=point)
1183    }
1184
1185    /// Iterator over pairs `(x..y, &mut value)` that overlap the `point`.
1186    /// See [iter](#method.iter) for more details.
1187    #[inline]
1188    pub fn overlap_mut<'a>(&'a mut self, point: T) -> IterMut<'a, T, V, RangeInclusive<T>, Ix> {
1189        IterMut::new(self, point..=point)
1190    }
1191
1192    /// Iterates over *mutable* values that overlap the `point`.
1193    /// See [iter](#method.iter) for more details.
1194    #[inline]
1195    pub fn values_overlap_mut<'a>(&'a mut self, point: T) -> ValuesMut<'a, T, V, RangeInclusive<T>, Ix> {
1196        ValuesMut::new(self, point..=point)
1197    }
1198
1199    /// Iterates over all values (`&V`) with intervals that match `query` exactly.
1200    /// Takes *O(log N + K)* where *K* is the size of the output.
1201    pub fn values_at<'a>(&'a self, query: Range<T>) -> ValuesExact<'a, T, V, Ix> {
1202        ValuesExact::new(self, Interval::new(&query))
1203    }
1204
1205    /// Iterates over all mutable values (`&mut V`) with intervals that match `query` exactly.
1206    pub fn values_mut_at<'a>(&'a mut self, query: Range<T>) -> ValuesExactMut<'a, T, V, Ix> {
1207        ValuesExactMut::new(self, Interval::new(&query))
1208    }
1209
1210    /// Creates an unsorted iterator over all pairs `(x..y, &value)`.
1211    /// Slightly faster than the sorted iterator, although both take *O(N)*.
1212    pub fn unsorted_iter<'a>(&'a self) -> UnsIter<'a, T, V, Ix> {
1213        UnsIter::new(self)
1214    }
1215
1216    /// Creates an unsorted iterator over all intervals `x..y`.
1217    pub fn unsorted_intervals<'a>(&'a self) -> UnsIntervals<'a, T, V, Ix> {
1218        UnsIntervals::new(self)
1219    }
1220
1221    /// Creates an unsorted iterator over all values `&value`.
1222    pub fn unsorted_values<'a>(&'a self) -> UnsValues<'a, T, V, Ix> {
1223        UnsValues::new(self)
1224    }
1225
1226    /// Creates an unsorted iterator over all pairs `(x..y, &mut value)`.
1227    pub fn unsorted_iter_mut<'a>(&'a mut self) -> UnsIterMut<'a, T, V, Ix> {
1228        UnsIterMut::new(self)
1229    }
1230
1231    /// Creates an unsorted iterator over all mutable values `&mut value`.
1232    pub fn unsorted_values_mut<'a>(&'a mut self) -> UnsValuesMut<'a, T, V, Ix> {
1233        UnsValuesMut::new(self)
1234    }
1235
1236    /// Consumes `IntervalMap` and creates an unsorted iterator over all pairs `(x..y, value)`.
1237    pub fn unsorted_into_iter(self) -> UnsIntoIter<T, V, Ix> {
1238        UnsIntoIter::new(self)
1239    }
1240
1241    /// Consumes `IntervalMap` and creates an unsorted iterator over all intervals `x..y`.
1242    pub fn unsorted_into_intervals(self) -> UnsIntoIntervals<T, V, Ix> {
1243        UnsIntoIntervals::new(self)
1244    }
1245
1246    /// Consumes `IntervalMap` and creates an unsorted iterator over all values.
1247    pub fn unsorted_into_values(self) -> UnsIntoValues<T, V, Ix> {
1248        UnsIntoValues::new(self)
1249    }
1250}
1251
1252impl<T: PartialOrd + Copy, V, Ix: IndexType> IntoIterator for IntervalMap<T, V, Ix> {
1253    type IntoIter = IntoIter<T, V, RangeFull, Ix>;
1254    type Item = (Range<T>, V);
1255
1256    fn into_iter(self) -> Self::IntoIter {
1257        IntoIter::new(self, ..)
1258    }
1259}
1260
1261/// Construct [IntervalMap](struct.IntervalMap.html) from pairs `(x..y, value)`.
1262///
1263/// Panics, if the iterator contains duplicate intervals.
1264impl<T: PartialOrd + Copy, V> FromIterator<(Range<T>, V)> for IntervalMap<T, V> {
1265    fn from_iter<I>(iter: I) -> Self
1266    where I: IntoIterator<Item = (Range<T>, V)>
1267    {
1268        let mut map = IntervalMap::new();
1269        for (range, value) in iter {
1270            assert!(map.insert(range, value).is_none(), "Cannot collect IntervalMap with duplicate intervals!");
1271        }
1272        map
1273    }
1274}
1275
1276impl<T: PartialOrd + Copy, V, Ix: IndexType> Index<Range<T>> for IntervalMap<T, V, Ix> {
1277    type Output = V;
1278
1279    fn index(&self, range: Range<T>) -> &Self::Output {
1280        self.get(range).expect("No entry found for range")
1281    }
1282}
1283
1284impl<T, V, Ix> IntervalMap<T, V, Ix>
1285where T: PartialOrd + Copy + Default + AddAssign + Sub<Output = T>,
1286      Ix: IndexType,
1287{
1288    /// Calculates the total length of the `query` that is covered by intervals in the map.
1289    /// Takes *O(log N + K)* where *K* is the number of intervals that overlap `query`.
1290    ///
1291    /// This method makes two assumptions:
1292    /// - `T::default()` is equivalent to 0, which is true for numeric types,
1293    /// - Single-point intersections are irrelevant, for example intersection between *[0, 1]* and *[1, 2]* is zero,
1294    /// This also means that the size of the interval *(0, 1)* will be 1 even for integer types.
1295    ///
1296    /// ```rust
1297    /// let map = iset::interval_map!{ 0..10 => 'a', 4..8 => 'b', 12..15 => 'c' };
1298    /// assert_eq!(map.covered_len(2..14), 10);
1299    /// assert_eq!(map.covered_len(..), 13);
1300    /// ```
1301    pub fn covered_len<R>(&self, query: R) -> T
1302    where R: RangeBounds<T>,
1303    {
1304        let mut res = T::default();
1305        let start_bound = query.start_bound().cloned();
1306        let end_bound = query.end_bound().cloned();
1307
1308        let mut started = false;
1309        let mut curr_start = res; // T::default(), will not be used.
1310        let mut curr_end = res;
1311        for interval in self.intervals(query) {
1312            let start = match start_bound {
1313                Bound::Included(a) | Bound::Excluded(a) if a >= interval.start => a,
1314                _ => interval.start,
1315            };
1316            let end = match end_bound {
1317                Bound::Included(b) | Bound::Excluded(b) if b <= interval.end => b,
1318                _ => interval.end,
1319            };
1320            debug_assert!(end >= start);
1321
1322            if started {
1323                if start > curr_end {
1324                    res += curr_end - curr_start;
1325                    curr_start = start;
1326                    curr_end = end;
1327                } else if end > curr_end {
1328                    curr_end = end;
1329                }
1330            } else {
1331                curr_start = start;
1332                curr_end = end;
1333                started = true;
1334            }
1335        }
1336        if started {
1337            res += curr_end - curr_start;
1338        }
1339        res
1340    }
1341}
1342
1343#[cfg(feature = "dot")]
1344impl<T: PartialOrd + Copy + Display, V: Display, Ix: IndexType> IntervalMap<T, V, Ix> {
1345    /// Writes dot file to `writer`. `T` and `V` should implement `Display`.
1346    pub fn write_dot<W: Write>(&self, mut writer: W) -> io::Result<()> {
1347        writeln!(writer, "digraph {{")?;
1348        for i in 0..self.nodes.len() {
1349            self.nodes[i].write_dot(i, self.colors.get(i), &mut writer)?;
1350        }
1351        writeln!(writer, "}}")
1352    }
1353}
1354
1355#[cfg(feature = "dot")]
1356impl<T: PartialOrd + Copy + Display, V, Ix: IndexType> IntervalMap<T, V, Ix> {
1357    /// Writes dot file to `writer` without values. `T` should implement `Display`.
1358    pub fn write_dot_without_values<W: Write>(&self, mut writer: W) -> io::Result<()> {
1359        writeln!(writer, "digraph {{")?;
1360        for i in 0..self.nodes.len() {
1361            self.nodes[i].write_dot_without_values(i, self.colors.get(i), &mut writer)?;
1362        }
1363        writeln!(writer, "}}")
1364    }
1365}
1366
1367impl<T: PartialOrd + Copy + Debug, V: Debug, Ix: IndexType> Debug for IntervalMap<T, V, Ix> {
1368    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1369        write!(f, "{{")?;
1370        let mut need_comma = false;
1371        for (interval, value) in self.iter(..) {
1372            if need_comma {
1373                write!(f, ", ")?;
1374            } else {
1375                need_comma = true;
1376            }
1377            write!(f, "{:?} => {:?}", interval, value)?;
1378        }
1379        write!(f, "}}")
1380    }
1381}
1382
1383#[cfg(feature = "serde")]
1384impl<T, V, Ix> Serialize for IntervalMap<T, V, Ix>
1385    where
1386        T: PartialOrd + Copy + Serialize,
1387        V: Serialize,
1388        Ix: IndexType + Serialize,
1389{
1390    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
1391        // For some reason, Vec<Node> does not support serialization. Because of that we create a newtype.
1392        struct NodeVecSer<'a, T, V, Ix>(&'a Vec<Node<T, V, Ix>>)
1393            where
1394                T: PartialOrd + Copy + Serialize,
1395                V: Serialize,
1396                Ix: IndexType + Serialize;
1397
1398        impl<'a, T, V, Ix> Serialize for NodeVecSer<'a, T, V, Ix>
1399            where
1400                T: PartialOrd + Copy + Serialize,
1401                V: Serialize,
1402                Ix: IndexType + Serialize,
1403        {
1404            fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
1405                let mut seq = serializer.serialize_seq(Some(self.0.len()))?;
1406                for node in self.0.iter() {
1407                    seq.serialize_element(node)?;
1408                }
1409                seq.end()
1410            }
1411        }
1412
1413        let mut tup = serializer.serialize_tuple(2)?;
1414        tup.serialize_element(&NodeVecSer(&self.nodes))?;
1415        tup.serialize_element(&self.colors)?;
1416        tup.serialize_element(&self.root)?;
1417        tup.end()
1418    }
1419}
1420
1421// For some reason, Vec<Node> does not support deserialization. Because of that we create a newtype.
1422#[cfg(feature = "serde")]
1423struct NodeVecDe<T: PartialOrd + Copy, V, Ix: IndexType>(Vec<Node<T, V, Ix>>);
1424
1425#[cfg(feature = "serde")]
1426impl<'de, T, V, Ix> Deserialize<'de> for NodeVecDe<T, V, Ix>
1427    where
1428        T: PartialOrd + Copy + Deserialize<'de>,
1429        V: Deserialize<'de>,
1430        Ix: IndexType + Deserialize<'de>,
1431{
1432    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
1433        struct NodeVecVisitor<T: PartialOrd + Copy, V, Ix: IndexType> {
1434            marker: PhantomData<(T, V, Ix)>,
1435        }
1436
1437        impl<'de, T, V, Ix> Visitor<'de> for NodeVecVisitor<T, V, Ix>
1438        where
1439            T: PartialOrd + Copy + Deserialize<'de>,
1440            V: Deserialize<'de>,
1441            Ix: IndexType + Deserialize<'de>,
1442        {
1443            type Value = NodeVecDe<T, V, Ix>;
1444
1445            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
1446                formatter.write_str("a sequence of Node<T, V, Ix>")
1447            }
1448
1449            fn visit_seq<A: SeqAccess<'de>>(self, mut seq: A) -> Result<Self::Value, A::Error> {
1450                let mut nodes = Vec::new();
1451                while let Some(node) = seq.next_element()? {
1452                    nodes.push(node);
1453                }
1454                Ok(NodeVecDe(nodes))
1455            }
1456        }
1457
1458        let visitor = NodeVecVisitor {
1459            marker: PhantomData,
1460        };
1461        deserializer.deserialize_seq(visitor)
1462    }
1463}
1464
1465#[cfg(feature = "serde")]
1466impl<'de, T, V, Ix> Deserialize<'de> for IntervalMap<T, V, Ix>
1467where
1468    T: PartialOrd + Copy + Deserialize<'de>,
1469    V: Deserialize<'de>,
1470    Ix: IndexType + Deserialize<'de>,
1471{
1472    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
1473        let (node_vec, colors, root) = <(NodeVecDe<T, V, Ix>, BitVec, Ix)>::deserialize(deserializer)?;
1474        Ok(IntervalMap {
1475            nodes: node_vec.0,
1476            colors,
1477            root,
1478        })
1479    }
1480}
1481
1482/// Macros for [IntervalMap](struct.IntervalMap.html) creation.
1483/// ```rust
1484/// use iset::interval_map;
1485///
1486/// let map = interval_map!{ 0..10 => "a", 5..15 => "b", -5..20 => "c" };
1487/// let a: Vec<_> = map.iter(..).collect();
1488/// assert_eq!(a, &[(-5..20, &"c"), (0..10, &"a"), (5..15, &"b")]);
1489///
1490/// // Creates an interval map with `u8` index type (up to 255 values in the map).
1491/// let set = interval_map!{ [u8] 0..10 => "a", 5..15 => "b", -5..20 => "c" };
1492/// ```
1493///
1494/// Panics if there are duplicate intervals.
1495#[macro_export]
1496macro_rules! interval_map {
1497    // Create an empty interval map given the index type.
1498    ( [$ix:ty] $(,)? ) => ( $crate::IntervalMap::<_, _, $ix>::default() );
1499
1500    // Create an empty interval map given the default index type.
1501    ( () ) => ( $crate::IntervalMap::new() );
1502
1503    // Create a filled interval map given the index type.
1504    ( [$ix:ty] $(,)? $( $k:expr => $v:expr ),* $(,)? ) => {
1505        {
1506            let mut _temp_map = $crate::IntervalMap::<_, _, $ix>::default();
1507            $(
1508                assert!(_temp_map.insert($k, $v).is_none(),
1509                    "Cannot use interval_map!{{ ... }} with duplicate intervals");
1510            )*
1511            _temp_map
1512        }
1513    };
1514
1515    // Create a filled interval map with the default index type.
1516    ( $( $k:expr => $v:expr ),* $(,)? ) => {
1517        {
1518            let mut _temp_map = $crate::IntervalMap::new();
1519            $(
1520                assert!(_temp_map.insert($k, $v).is_none(),
1521                    "Cannot use interval_map!{{ ... }} with duplicate intervals");
1522            )*
1523            _temp_map
1524        }
1525    };
1526}
1527
1528/// Macros for [IntervalSet](set/struct.IntervalSet.html) creation.
1529/// ```rust
1530/// use iset::interval_set;
1531///
1532/// let set = interval_set!{ 100..210, 50..150 };
1533/// let a: Vec<_> = set.iter(..).collect();
1534/// assert_eq!(a, &[50..150, 100..210]);
1535///
1536/// // Creates an interval set with `u8` index type (up to 255 values in the set).
1537/// let set = interval_set!{ [u8] 100..210, 50..150 };
1538/// ```
1539#[macro_export]
1540macro_rules! interval_set {
1541    // Create an empty interval set given the index type.
1542    ( [$ix:ty] $(,)? ) => ( $crate::IntervalSet::<_, $ix>::default() );
1543
1544    // Create an empty interval set given with the default index type.
1545    ( () ) => ( $crate::IntervalSet::new() );
1546
1547    // Create a filled interval set given the index type.
1548    ( [$ix:ty] $(,)? $( $k:expr ),* $(,)? ) => {
1549        {
1550            let mut _temp_set = $crate::IntervalSet::<_, $ix>::default();
1551            $(
1552                _temp_set.insert($k);
1553            )*
1554            _temp_set
1555        }
1556    };
1557
1558    // Create a filled interval set with the default index type.
1559    ( $( $k:expr ),* $(,)? ) => {
1560        {
1561            let mut _temp_set = $crate::IntervalSet::new();
1562            $(
1563                _temp_set.insert($k);
1564            )*
1565            _temp_set
1566        }
1567    };
1568}
iset/lib.rs

iset/
lib.rs
