iset/
set.rs

1//! `IntervalSet` implementation.
2
3use core::{
4    ops::{Range, RangeInclusive, RangeBounds, RangeFull, AddAssign, Sub},
5    fmt::{self, Debug, Formatter},
6    iter::{FromIterator, IntoIterator},
7};
8#[cfg(feature = "dot")]
9use std::io::{self, Write};
10#[cfg(feature = "serde")]
11use serde::{Serialize, Serializer, Deserialize, Deserializer};
12
13use super::IntervalMap;
14use super::ix::{IndexType, DefaultIx};
15use super::iter::*;
16
17/// Set with interval keys (ranges `x..y`). Newtype over `IntervalMap<T, ()>`.
18/// See [IntervalMap](../struct.IntervalMap.html) for more information.
19///
20/// ```rust
21/// use iset::interval_set;
22/// let mut set = interval_set!{ 0.4..1.5, 0.1..0.5, 5.0..7.0 };
23/// assert!(set.insert(-1.0..0.2));
24/// // false because the interval is already in the set.
25/// assert!(!set.insert(0.1..0.5));
26///
27/// assert!(set.contains(5.0..7.0));
28/// assert!(set.remove(5.0..7.0));
29///
30/// // Iterate over intervals that overlap `0.2..0.8`.
31/// let a: Vec<_> = set.iter(0.2..0.8).collect();
32/// assert_eq!(a, &[0.1..0.5, 0.4..1.5]);
33///
34/// // Iterate over intervals that overlap a point 0.5.
35/// let b: Vec<_> = set.overlap(0.5).collect();
36/// assert_eq!(b, &[0.4..1.5]);
37///
38/// // Will panic:
39/// // set.insert(0.0..core::f64::NAN);
40/// // set.overlap(core::f64::NAN);
41///
42/// // It is still possible to use infinity.
43/// const INF: f64 = core::f64::INFINITY;
44/// set.insert(0.0..INF);
45/// let c: Vec<_> = set.overlap(0.5).collect();
46/// assert_eq!(c, &[0.0..INF, 0.4..1.5]);
47///
48/// println!("{:?}", set);
49/// // {-1.0..0.2, 0.0..inf, 0.1..0.5, 0.4..1.5}
50/// assert_eq!(set.range().unwrap(), -1.0..INF);
51/// assert_eq!(set.smallest().unwrap(), -1.0..0.2);
52/// assert_eq!(set.largest().unwrap(), 0.4..1.5);
53/// ```
54///
55/// There are no mutable iterators over [IntervalSet](struct.IntervalSet.html) as keys should be immutable.
56///
57/// In contrast to the [IntervalMap](../struct.IntervalMap.html), `IntervalSet` does not have a
58/// [force_insert](../struct.IntervalMap.html#method.force_insert), and completely forbids duplicate intervals.
59#[derive(Clone)]
60pub struct IntervalSet<T, Ix: IndexType = DefaultIx> {
61    inner: IntervalMap<T, (), Ix>,
62}
63
64impl<T: PartialOrd + Copy> IntervalSet<T> {
65    /// Creates an empty [IntervalSet](struct.IntervalSet.html)
66    /// with default index type [DefaultIx](../ix/type.DefaultIx.html).
67    pub fn new() -> Self {
68        Self::default()
69    }
70}
71
72impl<T: PartialOrd + Copy, Ix: IndexType> Default for IntervalSet<T, Ix> {
73    fn default() -> Self {
74        Self {
75            inner: IntervalMap::default(),
76        }
77    }
78}
79
80impl<T: PartialOrd + Copy, Ix: IndexType> IntervalSet<T, Ix> {
81    /// Creates an empty [IntervalSet](struct.IntervalSet.html) with `capacity`.
82    pub fn with_capacity(capacity: usize) -> Self {
83        Self {
84            inner: IntervalMap::with_capacity(capacity),
85        }
86    }
87
88    /// Creates an interval set from a sorted iterator over intervals. Takes *O(N)*.
89    ///
90    /// Panics if the intervals are not sorted or if there are equal intervals.
91    pub fn from_sorted<I>(iter: I) -> Self
92    where I: Iterator<Item = Range<T>>,
93    {
94        Self {
95            inner: IntervalMap::from_sorted(iter.map(|range| (range, ()))),
96        }
97    }
98
99    /// Returns the number of elements in the set.
100    #[inline]
101    pub fn len(&self) -> usize {
102        self.inner.len()
103    }
104
105    /// Returns `true` if the set contains no elements.
106    #[inline]
107    pub fn is_empty(&self) -> bool {
108        self.inner.is_empty()
109    }
110
111    /// Clears the set, removing all values. This method has no effect on the allocated capacity.
112    #[inline]
113    pub fn clear(&mut self) {
114        self.inner.clear()
115    }
116
117    /// Shrinks inner contents.
118    #[inline]
119    pub fn shrink_to_fit(&mut self) {
120        self.inner.shrink_to_fit()
121    }
122
123    /// Inserts an interval `x..y` to the set. If the set did not have this interval present, true is returned.
124    /// Takes *O(log N)*.
125    ///
126    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
127    pub fn insert(&mut self, interval: Range<T>) -> bool {
128        self.inner.insert(interval, ()).is_none()
129    }
130
131    /// Check if the interval set contains `interval` (exact match). Takes *O(log N)*.
132    ///
133    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
134    pub fn contains(&self, interval: Range<T>) -> bool {
135        self.inner.contains(interval)
136    }
137
138    /// Removes the interval from the set. Returns true if the interval was present in the set. Takes *O(log N)*.
139    ///
140    /// Panics if `interval` is empty (`start >= end`) or contains a value that cannot be compared (such as `NAN`).
141    pub fn remove(&mut self, interval: Range<T>) -> bool {
142        self.inner.remove(interval).is_some()
143    }
144
145    /// Returns a range of interval keys in the set, takes *O(1)*. Returns `None` if the set is empty.
146    /// `out.start` is the minimal start of all intervals in the set,
147    /// and `out.end` is the maximal end of all intervals in the set.
148    #[inline]
149    pub fn range(&self) -> Option<Range<T>> {
150        self.inner.range()
151    }
152
153    /// Returns the smallest interval in the set (in lexicographical order).
154    /// Takes *O(log N)*. Returns `None` if the set is empty.
155    pub fn smallest(&self) -> Option<Range<T>> {
156        self.inner.smallest().map(|(interval, _)| interval)
157    }
158
159    /// Removes and returns the smallest interval in the set (in lexicographical order).
160    /// Takes *O(log N)*. Returns `None` if the set is empty.
161    pub fn remove_smallest(&mut self) -> Option<Range<T>> {
162        self.inner.remove_smallest().map(|(interval, _)| interval)
163    }
164
165    /// Returns the largest interval in the set (in lexicographical order).
166    /// Takes *O(log N)*. Returns `None` if the set is empty.
167    pub fn largest(&self) -> Option<Range<T>> {
168        self.inner.largest().map(|(interval, _)| interval)
169    }
170
171    /// Removes and returns the largest interval in the set (in lexicographical order).
172    /// Takes *O(log N)*. Returns `None` if the set is empty.
173    pub fn remove_largest(&mut self) -> Option<Range<T>> {
174        self.inner.remove_largest().map(|(interval, _)| interval)
175    }
176
177    /// Checks, if the query overlaps any intervals in the interval set.
178    /// Equivalent to `set.iter(query).next().is_some()`, but much faster.
179    #[inline]
180    pub fn has_overlap<R>(&self, query: R) -> bool
181    where R: RangeBounds<T>, {
182        self.inner.has_overlap(query)
183    }
184
185    /// Iterates over intervals `x..y` that overlap the `query`.
186    /// Takes *O(log N + K)* where *K* is the size of the output.
187    /// Output is sorted by intervals.
188    ///
189    /// Panics if `interval` is empty or contains a value that cannot be compared (such as `NAN`).
190    pub fn iter<'a, R>(&'a self, query: R) -> Intervals<'a, T, (), R, Ix>
191    where R: RangeBounds<T>,
192    {
193        self.inner.intervals(query)
194    }
195
196    /// Iterates over intervals `x..y` that overlap the `point`. Same as `iter(point..=point)`.
197    /// See [iter](#method.iter) for more details.
198    pub fn overlap<'a>(&'a self, point: T) -> Intervals<'a, T, (), RangeInclusive<T>, Ix> {
199        self.inner.intervals(point..=point)
200    }
201
202    /// Consumes [IntervalSet](struct.IntervalSet.html) and iterates over intervals `x..y` that overlap the `query`.
203    /// See [iter](#method.iter) for more details.
204    pub fn into_iter<R>(self, query: R) -> IntoIntervals<T, (), R, Ix>
205    where R: RangeBounds<T>,
206    {
207        IntoIntervals::new(self.inner, query)
208    }
209
210    /// Creates an unsorted iterator over all intervals `x..y`.
211    /// Slightly faster than the sorted iterator, although both take *O(N)*.
212    pub fn unsorted_iter<'a>(&'a self) -> UnsIntervals<'a, T, (), Ix> {
213        UnsIntervals::new(&self.inner)
214    }
215
216    /// Consumes `IntervalSet` and creates an unsorted iterator over all intervals `x..y`.
217    pub fn unsorted_into_iter(self) -> UnsIntoIntervals<T, (), Ix> {
218        UnsIntoIntervals::new(self.inner)
219    }
220}
221
222impl<T: PartialOrd + Copy, Ix: IndexType> IntoIterator for IntervalSet<T, Ix> {
223    type IntoIter = IntoIntervals<T, (), RangeFull, Ix>;
224    type Item = Range<T>;
225
226    fn into_iter(self) -> Self::IntoIter {
227        IntoIntervals::new(self.inner, ..)
228    }
229}
230
231/// Construct [IntervalSet](struct.IntervalSet.html) from ranges `x..y`.
232impl<T: PartialOrd + Copy> FromIterator<Range<T>> for IntervalSet<T> {
233    fn from_iter<I: IntoIterator<Item = Range<T>>>(iter: I) -> Self {
234        let mut set = IntervalSet::new();
235        for range in iter {
236            set.insert(range);
237        }
238        set
239    }
240}
241
242impl<T, Ix> IntervalSet<T, Ix>
243where T: PartialOrd + Copy + Default + AddAssign + Sub<Output = T>,
244      Ix: IndexType,
245{
246    /// Calculates the total length of the `query` that is covered by intervals in the map.
247    /// Takes *O(log N + K)* where *K* is the number of intervals that overlap `query`.
248    ///
249    /// See [IntervalMap::covered_len](../struct.IntervalMap.html#method.covered_len) for more details.
250    #[inline]
251    pub fn covered_len<R>(&self, query: R) -> T
252    where R: RangeBounds<T>
253    {
254        self.inner.covered_len(query)
255    }
256}
257
258#[cfg(feature = "dot")]
259impl<T: PartialOrd + Copy + core::fmt::Display, Ix: IndexType> IntervalSet<T, Ix> {
260    /// Writes dot file to `writer`. `T` should implement `Display`.
261    pub fn write_dot<W: Write>(&self, writer: W) -> io::Result<()> {
262        self.inner.write_dot_without_values(writer)
263    }
264}
265
266impl<T: PartialOrd + Copy + Debug, Ix: IndexType> Debug for IntervalSet<T, Ix> {
267    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
268        write!(f, "{{")?;
269        let mut need_comma = false;
270        for interval in self.iter(..) {
271            if need_comma {
272                write!(f, ", ")?;
273            } else {
274                need_comma = true;
275            }
276            write!(f, "{:?}", interval)?;
277        }
278        write!(f, "}}")
279    }
280}
281
282#[cfg(feature = "serde")]
283impl<T, Ix> Serialize for IntervalSet<T, Ix>
284where
285    T: PartialOrd + Copy + Serialize,
286    Ix: IndexType + Serialize,
287{
288    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
289        self.inner.serialize(serializer)
290    }
291}
292
293#[cfg(feature = "serde")]
294impl<'de, T, Ix> Deserialize<'de> for IntervalSet<T, Ix>
295where
296    T: PartialOrd + Copy + Deserialize<'de>,
297    Ix: IndexType + Deserialize<'de>,
298{
299    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
300        let inner = <IntervalMap<T, (), Ix>>::deserialize(deserializer)?;
301        Ok(IntervalSet { inner })
302    }
303}
iset/set.rs

iset/
set.rs
