s2n_quic_core/interval_set/mod.rs
1// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
2// SPDX-License-Identifier: Apache-2.0
3
4#![forbid(unsafe_code)]
5
6mod insert;
7mod intersection;
8pub mod interval;
9mod remove;
10
11#[cfg(test)]
12mod tests;
13
14use alloc::collections::vec_deque::{self, VecDeque};
15use core::{
16 fmt,
17 iter::FromIterator,
18 num::NonZeroUsize,
19 ops::{Bound, Range, RangeBounds, RangeInclusive},
20};
21use insert::insert;
22pub use intersection::Intersection;
23pub use interval::*;
24use remove::remove;
25
26#[derive(Clone, Copy, Debug, PartialEq, PartialOrd, Eq, Ord, Hash)]
27pub enum IntervalSetError {
28 LimitExceeded,
29 InvalidInterval,
30}
31
32/// `IntervalSet` is an efficient structure for storing sets of consecutive numbers. Instead
33/// of storing an individual entry per value, only the lower and upper bounds (`Interval`) are stored.
34///
35/// ## Usage
36///
37/// ```rust,ignore
38/// use s2n_quic_transport::interval_set::IntervalSet;
39///
40/// let mut set = IntervalSet::new();
41///
42/// set.insert_value(0);
43/// set.insert_value(1);
44/// set.insert_value(2);
45/// set.insert_value(3);
46///
47/// // because 0 to 3 are consecutive, only a single interval is stored
48/// assert_eq!(set.interval_len(), 1);
49///
50/// set.insert_value(5);
51/// set.insert_value(6);
52///
53/// // 5 and 6 are not consecutive with 0 to 3 so a new entry is created
54/// assert_eq!(set.interval_len(), 2);
55///
56/// set.insert_value(4);
57///
58/// // inserting a 4 merges all of the intervals into a single entry
59/// assert_eq!(set.interval_len(), 1);
60///
61/// // ranges of numbers can be inserted at the same time
62/// set.insert(12..15);
63/// set.insert(18..=21);
64///
65/// assert_eq!(set.interval_len(), 3);
66///
67/// // ranges can also be removed
68/// set.remove(0..22);
69///
70/// assert_eq!(set.interval_len(), 0);
71/// ```
72#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
73pub struct IntervalSet<T> {
74 limit: Option<NonZeroUsize>,
75 intervals: VecDeque<Interval<T>>,
76}
77
78impl<T> Default for IntervalSet<T> {
79 fn default() -> Self {
80 Self {
81 limit: None,
82 intervals: VecDeque::new(),
83 }
84 }
85}
86
87impl<T> IntervalSet<T> {
88 /// Creates an empty `IntervalSet`
89 ///
90 /// # Examples
91 ///
92 /// ```ignore
93 /// # use s2n_quic_transport::interval_set::IntervalSet;
94 /// let mut set = IntervalSet::new();
95 /// assert!(set.insert(0..4).is_ok());
96 /// ```
97 #[inline]
98 pub fn new() -> IntervalSet<T> {
99 Self::default()
100 }
101
102 /// Creates an empty `IntervalSet` with a specific capacity.
103 /// This preallocates enough memory for `capacity` elements,
104 /// so that the `IntervalSet` does not have to be reallocated
105 /// until it contains at least that many values.
106 ///
107 /// # Examples
108 ///
109 /// ```ignore
110 /// # use s2n_quic_transport::interval_set::IntervalSet;
111 /// let mut set = IntervalSet::with_capacity(10);
112 /// assert!(set.insert(0..4).is_ok());
113 /// ```
114 #[inline]
115 pub fn with_capacity(capacity: usize) -> IntervalSet<T> {
116 let intervals = VecDeque::with_capacity(capacity);
117
118 IntervalSet {
119 limit: None,
120 intervals,
121 }
122 }
123
124 /// Creates an empty `IntervalSet` with a specific limit.
125 /// The number of elements in the set cannot exceed this
126 /// amount, otherwise `insert` calls will be rejected.
127 ///
128 /// # Examples
129 ///
130 /// ```ignore
131 /// # use s2n_quic_transport::interval_set::IntervalSet;
132 /// use core::num::NonZeroUsize;
133 /// let mut set = IntervalSet::with_limit(NonZeroUsize::new(1).unwrap());
134 /// assert!(set.insert(0..4).is_ok());
135 /// assert!(set.insert(12..16).is_err());
136 /// assert!(set.insert(4..12).is_ok());
137 /// assert!(set.insert(12..16).is_ok());
138 /// ```
139 #[inline]
140 pub fn with_limit(limit: NonZeroUsize) -> IntervalSet<T> {
141 let mut set = Self::default();
142 set.set_limit(limit);
143 set
144 }
145
146 /// Sets an element limit for the given `IntervalSet`.
147 /// The number of elements in the set cannot exceed this
148 /// amount, otherwise `insert` calls will be rejected
149 ///
150 /// Note: calling this will not drop existing intervals
151 /// that exceed the new limit and will only be
152 /// applied to later calls to `insert`.
153 ///
154 /// # Examples
155 ///
156 /// ```ignore
157 /// # use s2n_quic_transport::interval_set::IntervalSet;
158 /// use core::num::NonZeroUsize;
159 /// let mut set = IntervalSet::new();
160 /// assert!(set.insert(0..4).is_ok());
161 /// set.set_limit(NonZeroUsize::new(1).unwrap());
162 /// assert!(set.insert(4..8).is_ok());
163 /// assert!(set.insert(12..16).is_err());
164 /// ```
165 #[inline]
166 pub fn set_limit(&mut self, limit: NonZeroUsize) {
167 self.limit = Some(limit);
168 }
169
170 /// Removes the element limit for the given `IntervalSet`.
171 ///
172 /// # Examples
173 ///
174 /// ```ignore
175 /// # use s2n_quic_transport::interval_set::IntervalSet;
176 /// use core::num::NonZeroUsize;
177 /// let mut set = IntervalSet::with_limit(NonZeroUsize::new(1).unwrap());
178 /// assert!(set.insert(0..4).is_ok());
179 /// assert!(set.insert(4..8).is_ok());
180 /// assert!(set.insert(12..16).is_err());
181 /// set.remove_limit();
182 /// assert!(set.insert(12..16).is_ok());
183 /// ```
184 #[inline]
185 pub fn remove_limit(&mut self) {
186 self.limit = None;
187 }
188
189 /// Returns the number of intervals in `IntervalSet`.
190 ///
191 /// # Examples
192 ///
193 /// ```ignore
194 /// # use s2n_quic_transport::interval_set::IntervalSet;
195 /// let mut set = IntervalSet::new();
196 /// assert_eq!(set.interval_len(), 0);
197 /// assert!(set.insert(0..4).is_ok());
198 /// assert_eq!(set.interval_len(), 1);
199 /// ```
200 #[inline]
201 pub fn interval_len(&self) -> usize {
202 self.intervals.len()
203 }
204
205 /// Returns the allocated capacity of the `IntervalSet`.
206 ///
207 /// # Examples
208 ///
209 /// ```ignore
210 /// # use s2n_quic_transport::interval_set::IntervalSet;
211 /// let mut set = IntervalSet::with_capacity(1);
212 /// assert_eq!(set.capacity(), 1);
213 /// assert!(set.insert(0..4).is_ok());
214 /// assert!(set.insert(6..10).is_ok());
215 /// assert!(set.capacity() > 1);
216 /// ```
217 #[inline]
218 pub fn capacity(&self) -> usize {
219 self.intervals.capacity()
220 }
221
222 /// Clears all elements contained in the `IntervalSet`.
223 ///
224 /// # Examples
225 ///
226 /// ```ignore
227 /// # use s2n_quic_transport::interval_set::IntervalSet;
228 /// let mut set = IntervalSet::new();
229 /// assert!(set.insert(0..4).is_ok());
230 /// set.clear();
231 /// assert!(set.is_empty());
232 /// ```
233 #[inline]
234 pub fn clear(&mut self) {
235 self.intervals.clear()
236 }
237
238 /// Removes the lowest `Interval` in the set, if any
239 ///
240 /// # Examples
241 /// ```ignore
242 /// # use s2n_quic_transport::interval_set::IntervalSet;
243 /// let mut set = IntervalSet::new();
244 /// assert_eq!(set.pop_min(), None);
245 /// assert!(set.insert(0..4).is_ok());
246 /// assert_eq!(set.pop_min(), Some((0..4).into()));
247 /// ```
248 #[inline]
249 pub fn pop_min(&mut self) -> Option<Interval<T>> {
250 self.intervals.pop_front()
251 }
252}
253
254impl<T: IntervalBound> IntervalSet<T> {
255 /// Returns the number of elements in `IntervalSet`.
256 ///
257 /// # Examples
258 ///
259 /// ```ignore
260 /// # use s2n_quic_transport::interval_set::IntervalSet;
261 /// let mut set = IntervalSet::new();
262 /// assert_eq!(set.count(), 0);
263 /// assert!(set.insert(0..4).is_ok());
264 /// assert_eq!(set.count(), 4);
265 /// ```
266 #[inline]
267 pub fn count(&self) -> usize {
268 self.intervals.iter().map(|interval| interval.len()).sum()
269 }
270
271 /// Returns `true` if the `IntervalSet` has no intervals.
272 ///
273 /// # Examples
274 ///
275 /// ```ignore
276 /// # use s2n_quic_transport::interval_set::IntervalSet;
277 /// let mut set = IntervalSet::new();
278 /// assert!(set.is_empty());
279 /// assert!(set.insert(0..4).is_ok());
280 /// assert!(!set.is_empty());
281 /// ```
282 #[inline]
283 pub fn is_empty(&self) -> bool {
284 self.intervals.is_empty()
285 }
286
287 /// Inserts the supplied `interval` into the `IntervalSet`
288 ///
289 /// # Examples
290 ///
291 /// ```ignore
292 /// # use s2n_quic_transport::interval_set::IntervalSet;
293 /// let mut set = IntervalSet::new();
294 /// assert!(set.insert(0..4).is_ok());
295 /// assert!(set.contains(&3));
296 /// assert!(!set.contains(&5));
297 /// ```
298 #[inline]
299 pub fn insert<R: RangeBounds<T>>(&mut self, interval: R) -> Result<(), IntervalSetError> {
300 let interval = Interval::from_range_bounds(interval)?;
301
302 if self.intervals.is_empty() {
303 self.intervals.push_front(interval);
304 return Ok(());
305 }
306
307 let index = self.index_for(&interval);
308 insert(&mut self.intervals, interval, index, self.limit)?;
309
310 self.check_integrity();
311
312 Ok(())
313 }
314
315 /// Inserts the supplied `interval` at the beginning of the `IntervalSet`.
316 /// This method can be used to optimize insertion when the `interval` is less
317 /// than all of the current intervals.
318 ///
319 /// # Examples
320 ///
321 /// ```ignore
322 /// # use s2n_quic_transport::interval_set::IntervalSet;
323 /// let mut set = IntervalSet::new();
324 /// assert!(set.insert_front(0..4).is_ok());
325 /// assert!(set.contains(&3));
326 /// assert!(!set.contains(&5));
327 /// ```
328 #[inline]
329 pub fn insert_front<R: RangeBounds<T>>(&mut self, interval: R) -> Result<(), IntervalSetError> {
330 let interval = Interval::from_range_bounds(interval)?;
331
332 if self.intervals.is_empty() {
333 self.intervals.push_front(interval);
334 return Ok(());
335 }
336
337 insert(&mut self.intervals, interval, 0, self.limit)?;
338
339 self.check_integrity();
340
341 Ok(())
342 }
343
344 /// Inserts a single `value` into the `IntervalSet`
345 ///
346 /// # Examples
347 ///
348 /// ```ignore
349 /// # use s2n_quic_transport::interval_set::IntervalSet;
350 /// let mut set = IntervalSet::new();
351 /// assert!(set.insert_value(1).is_ok());
352 /// assert!(set.contains(&1));
353 /// assert!(!set.contains(&0));
354 /// assert!(!set.contains(&2));
355 /// ```
356 #[inline]
357 pub fn insert_value(&mut self, value: T) -> Result<(), IntervalSetError> {
358 self.insert((Bound::Included(value), Bound::Included(value)))
359 }
360
361 /// Performs a union, i.e., all the values in `self` or `other` will
362 /// be present in `self`
363 ///
364 /// # Examples
365 ///
366 /// ```ignore
367 /// # use s2n_quic_transport::interval_set::IntervalSet;
368 /// let mut a = IntervalSet::new();
369 /// assert!(a.insert(0..4).is_ok());
370 /// let mut b = IntervalSet::new();
371 /// assert!(b.insert(4..8).is_ok());
372 /// a.union(&b);
373 /// assert_eq!(a.iter().collect::<Vec<_>>(), (0..8).collect::<Vec<_>>());
374 /// ```
375 #[inline]
376 pub fn union(&mut self, other: &Self) -> Result<(), IntervalSetError> {
377 if self.intervals.is_empty() {
378 self.intervals.clone_from(&other.intervals);
379 return Ok(());
380 }
381
382 self.set_operation(other, insert)
383 }
384
385 /// Removes the supplied `interval` from the `IntervalSet`
386 ///
387 /// # Examples
388 ///
389 /// ```ignore
390 /// # use s2n_quic_transport::interval_set::IntervalSet;
391 /// let mut set = IntervalSet::new();
392 /// assert!(set.insert(1..3).is_ok());
393 /// assert!(set.remove(0..4).is_ok());
394 /// assert!(set.is_empty());
395 /// ```
396 #[inline]
397 pub fn remove<R: RangeBounds<T>>(&mut self, interval: R) -> Result<(), IntervalSetError> {
398 let interval = Interval::from_range_bounds(interval)?;
399
400 if self.intervals.is_empty() {
401 return Ok(());
402 }
403
404 let index = self.index_for(&interval);
405 remove(&mut self.intervals, interval, index, self.limit)?;
406
407 self.check_integrity();
408
409 Ok(())
410 }
411
412 /// Removes a single `value` from the `IntervalSet`
413 ///
414 /// # Examples
415 ///
416 /// ```ignore
417 /// # use s2n_quic_transport::interval_set::IntervalSet;
418 /// let mut set = IntervalSet::new();
419 /// assert!(set.insert_value(1).is_ok());
420 /// assert!(set.remove_value(1).is_ok());
421 /// assert!(!set.contains(&1));
422 /// ```
423 #[inline]
424 pub fn remove_value(&mut self, value: T) -> Result<(), IntervalSetError> {
425 self.remove((Bound::Included(value), Bound::Included(value)))
426 }
427
428 /// Performs a difference, i.e., all the values that are in `self` but not
429 /// in `other` will be present in `self`.
430 ///
431 /// # Examples
432 ///
433 /// ```ignore
434 /// # use s2n_quic_transport::interval_set::IntervalSet;
435 /// let mut set_a = IntervalSet::new();
436 /// assert!(set_a.insert(0..=10).is_ok());
437 /// let mut set_b = IntervalSet::new();
438 /// assert!(set_b.insert(4..=8).is_ok());
439 /// assert!(set_a.difference(&set_b).is_ok());
440 /// assert_eq!(set_a.iter().collect::<Vec<_>>(), vec![0, 1, 2, 3, 9, 10]);
441 /// ```
442 #[inline]
443 pub fn difference(&mut self, other: &Self) -> Result<(), IntervalSetError> {
444 if self.intervals.is_empty() {
445 return Ok(());
446 }
447
448 self.set_operation(other, remove)
449 }
450
451 /// Performs an intersection, i.e., all the values in both `self` and `other` will
452 /// be present in `self`.
453 ///
454 /// # Examples
455 ///
456 /// ```ignore
457 /// # use s2n_quic_transport::interval_set::IntervalSet;
458 /// let mut set_a = IntervalSet::new();
459 /// assert!(set_a.insert(0..=10).is_ok());
460 /// let mut set_b = IntervalSet::new();
461 /// assert!(set_b.insert(4..=8).is_ok());
462 /// assert!(set_a.intersection(&set_b).is_ok());
463 /// assert_eq!(set_a.iter().collect::<Vec<_>>(), vec![4, 5, 6, 7, 8]);
464 /// ```
465 #[inline]
466 pub fn intersection(&mut self, other: &Self) -> Result<(), IntervalSetError> {
467 intersection::apply(&mut self.intervals, &other.intervals);
468
469 Ok(())
470 }
471
472 /// Returns an iterator of `Intervals` over the intersection, i.e., all
473 /// the values in both `self` and `other` will be returned.
474 ///
475 /// # Examples
476 ///
477 /// ```ignore
478 /// # use s2n_quic_transport::interval_set::IntervalSet;
479 /// let mut set_a = IntervalSet::new();
480 /// assert!(set_a.insert(0..=10).is_ok());
481 /// let mut set_b = IntervalSet::new();
482 /// assert!(set_b.insert(4..=8).is_ok());
483 /// let intersection = set_a.intersection_iter(&set_b).flatten();
484 /// assert_eq!(intersection.collect::<Vec<_>>(), vec![4, 5, 6, 7, 8]);
485 /// ```
486 #[inline]
487 pub fn intersection_iter<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> {
488 Intersection::new(&self.intervals, &other.intervals)
489 }
490
491 /// Returns an iterator over all of the values contained in the given `IntervalSet`.
492 ///
493 /// # Examples
494 ///
495 /// ```ignore
496 /// # use s2n_quic_transport::interval_set::IntervalSet;
497 /// let mut set = IntervalSet::new();
498 /// assert!(set.insert(0..5).is_ok());
499 /// assert!(set.insert(10..15).is_ok());
500 /// let items: Vec<_> = set.iter().collect();
501 /// assert_eq!(vec![0, 1, 2, 3, 4, 10, 11, 12, 13, 14], items);
502 /// ```
503 #[inline]
504 pub fn iter(&self) -> Iter<T> {
505 Iter {
506 iter: self.intervals.iter(),
507 head: None,
508 tail: None,
509 }
510 }
511
512 /// Returns the smallest value in the given `IntervalSet`. If no items
513 /// are present in the set, `None` is returned.
514 ///
515 /// # Examples
516 ///
517 /// ```ignore
518 /// # use s2n_quic_transport::interval_set::IntervalSet;
519 /// let mut set = IntervalSet::new();
520 /// assert_eq!(set.min_value(), None);
521 /// assert!(set.insert(0..5).is_ok());
522 /// assert_eq!(set.min_value(), Some(0));
523 /// ```
524 #[inline]
525 pub fn min_value(&self) -> Option<T> {
526 let interval = self.intervals.front()?;
527 Some(interval.start)
528 }
529
530 /// Returns the largest value in the given `IntervalSet`. If no items
531 /// are present in the set, `None` is returned.
532 ///
533 /// # Examples
534 ///
535 /// ```ignore
536 /// # use s2n_quic_transport::interval_set::IntervalSet;
537 /// let mut set = IntervalSet::new();
538 /// assert_eq!(set.max_value(), None);
539 /// assert!(set.insert(0..5).is_ok());
540 /// assert_eq!(set.max_value(), Some(4));
541 /// ```
542 #[inline]
543 pub fn max_value(&self) -> Option<T> {
544 let interval = self.intervals.back()?;
545 Some(interval.end)
546 }
547
548 /// Returns `true` if the set contains a value
549 ///
550 /// # Examples
551 ///
552 /// ```ignore
553 /// # use s2n_quic_transport::interval_set::IntervalSet;
554 /// let mut set = IntervalSet::new();
555 /// assert_eq!(set.contains(&1), false);
556 /// assert!(set.insert(0..5).is_ok());
557 /// assert_eq!(set.contains(&1), true);
558 /// ```
559 #[inline]
560 pub fn contains(&self, value: &T) -> bool {
561 self.binary_search_with(value, |_index| true, |_index| false, |_index| false)
562 }
563
564 /// Internal function for applying set operations
565 #[inline]
566 fn set_operation<
567 F: Fn(
568 &mut VecDeque<Interval<T>>,
569 Interval<T>,
570 usize,
571 Option<NonZeroUsize>,
572 ) -> Result<usize, IntervalSetError>,
573 >(
574 &mut self,
575 other: &Self,
576 apply: F,
577 ) -> Result<(), IntervalSetError> {
578 let mut iter = other.intervals.iter();
579 let limit = self.limit;
580
581 // get the first interval in `other` and find the applicable
582 // index in `self`
583 let interval = if let Some(interval) = iter.next() {
584 interval
585 } else {
586 return Ok(());
587 };
588
589 let mut index = self.index_for(interval);
590
591 // apply the set operation for the interval above
592 index = apply(&mut self.intervals, *interval, index, limit)?;
593
594 // apply the set operation for the rest of the intervals
595 for interval in iter {
596 index = apply(&mut self.intervals, *interval, index, limit)?;
597 }
598
599 self.check_integrity();
600
601 Ok(())
602 }
603
604 /// Internal function for locating the optimal starting index for
605 /// interval comparison
606 #[inline]
607 fn index_for(&self, interval: &Interval<T>) -> usize {
608 // it's faster just to iterate through the set for smaller lengths
609 if self.interval_len() < 16 {
610 return 0;
611 }
612
613 self.binary_search_with(&interval.start, |index| index, |index| index, |index| index)
614 }
615
616 /// Internal function for searching for a value in the contained intervals
617 #[inline]
618 fn binary_search_with<
619 V,
620 EqualFn: Fn(usize) -> V,
621 GreaterFn: Fn(usize) -> V,
622 LessFn: Fn(usize) -> V,
623 >(
624 &self,
625 value: &T,
626 on_equal: EqualFn,
627 on_greater: GreaterFn,
628 on_less: LessFn,
629 ) -> V {
630 use core::cmp::Ordering::*;
631
632 let intervals = &self.intervals;
633
634 let mut size = intervals.len();
635 if size == 0 {
636 return on_greater(0);
637 }
638
639 let mut base = 0usize;
640 while size > 1 {
641 let half = size / 2;
642 let mid = base + half;
643 let subject = &intervals[mid];
644 match subject.partial_cmp(value) {
645 Some(Equal) => return on_equal(mid),
646 Some(Greater) => {}
647 Some(Less) => base = mid,
648 None => return on_greater(0),
649 };
650 size -= half;
651 }
652
653 let subject = &intervals[base];
654 match subject.partial_cmp(value) {
655 Some(Equal) => on_equal(base),
656 Some(Greater) => on_greater(base),
657 Some(Less) => on_less(base),
658 None => on_greater(0),
659 }
660 }
661
662 /// Internal check for integrity - only used when `cfg(test)` is enabled
663 #[inline]
664 fn check_integrity(&self) {
665 // When using this data structure outside of this crate, these checks are quite expensive.
666 // Rather than using `cfg(debug_assertions)`, we limit it to `cfg(test)`, which will just
667 // turn them on when testing this crate.
668 if cfg!(test) {
669 let mut prev_end: Option<T> = None;
670
671 for interval in self.intervals.iter() {
672 // make sure that a few items exist
673 for value in (*interval).take(3) {
674 assert!(self.contains(&value), "set should contain value");
675 }
676 for value in (*interval).rev().take(3) {
677 assert!(self.contains(&value), "set should contain value");
678 }
679
680 if let Some(prev_end) = prev_end.as_ref() {
681 assert!(
682 *prev_end < interval.start_exclusive(),
683 "the previous end should be less than the next start",
684 );
685 }
686
687 assert!(interval.is_valid(), "interval should be valid");
688
689 prev_end = Some(interval.end);
690 }
691 }
692 }
693}
694
695impl<T: Copy> IntervalSet<T> {
696 /// Returns an iterator of `Interval`s contained in the `IntervalSet`
697 ///
698 /// # Examples
699 ///
700 /// ```ignore
701 /// # use s2n_quic_transport::interval_set::IntervalSet;
702 /// let mut set = IntervalSet::new();
703 /// set.insert(0..=10);
704 /// assert_eq!(set.intervals().collect::<Vec<_>>(), vec![0..=10]);
705 /// ```
706 #[inline]
707 pub fn intervals(&self) -> IntervalIter<T> {
708 IntervalIter {
709 iter: self.intervals.iter(),
710 }
711 }
712
713 /// Returns an iterator of `Range`s contained in the `IntervalSet`
714 ///
715 /// # Examples
716 ///
717 /// ```ignore
718 /// # use s2n_quic_transport::interval_set::IntervalSet;
719 /// let mut set = IntervalSet::new();
720 /// set.insert(0..=10);
721 /// assert_eq!(set.ranges().collect::<Vec<_>>(), vec![0..11]);
722 /// ```
723 #[inline]
724 pub fn ranges(&self) -> RangeIter<T> {
725 RangeIter {
726 iter: self.intervals.iter(),
727 }
728 }
729
730 /// Returns an iterator of `RangeInclusive`s contained in the `IntervalSet`
731 ///
732 /// # Examples
733 ///
734 /// ```ignore
735 /// # use s2n_quic_transport::interval_set::IntervalSet;
736 /// let mut set = IntervalSet::new();
737 /// set.insert(0..=10);
738 /// assert_eq!(set.inclusive_ranges().collect::<Vec<_>>(), vec![0..=10]);
739 /// ```
740 #[inline]
741 pub fn inclusive_ranges(&self) -> RangeInclusiveIter<T> {
742 RangeInclusiveIter {
743 iter: self.intervals.iter(),
744 }
745 }
746}
747
748impl<T: Copy + fmt::Debug> fmt::Debug for IntervalSet<T> {
749 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
750 f.debug_set().entries(self.intervals.iter()).finish()
751 }
752}
753
754/// Iterator over all of the values contained in an `IntervalSet`
755pub struct Iter<'a, T> {
756 iter: vec_deque::Iter<'a, Interval<T>>,
757 head: Option<Interval<T>>,
758 tail: Option<Interval<T>>,
759}
760
761impl<T: IntervalBound> Iterator for Iter<'_, T> {
762 type Item = T;
763
764 #[inline]
765 fn next(&mut self) -> Option<T> {
766 loop {
767 if let Some(item) = self.head.as_mut().and_then(Iterator::next) {
768 return Some(item);
769 }
770
771 let item = self.iter.next().cloned().or_else(|| self.tail.take())?;
772 self.head = Some(item);
773 }
774 }
775
776 #[inline]
777 fn size_hint(&self) -> (usize, Option<usize>) {
778 let (lower, _) = self.iter.size_hint();
779 // Computing the upper length would require iterating through all of the ranges
780 let upper = None;
781 (lower, upper)
782 }
783}
784
785impl<T: IntervalBound> DoubleEndedIterator for Iter<'_, T> {
786 #[inline]
787 fn next_back(&mut self) -> Option<T> {
788 loop {
789 if let Some(item) = self.tail.as_mut().and_then(DoubleEndedIterator::next_back) {
790 return Some(item);
791 }
792
793 let item = self
794 .iter
795 .next_back()
796 .cloned()
797 .or_else(|| self.head.take())?;
798 self.tail = Some(item);
799 }
800 }
801}
802
803macro_rules! impl_iterator_conversions {
804 ($item:ident, $iter:ident) => {
805 #[derive(Clone, Debug)]
806 pub struct $iter<'a, T> {
807 iter: vec_deque::Iter<'a, Interval<T>>,
808 }
809
810 impl<'a, T: IntervalBound> Iterator for $iter<'a, T> {
811 type Item = $item<T>;
812
813 #[inline]
814 fn next(&mut self) -> Option<Self::Item> {
815 self.iter.next().map(|interval| interval.into())
816 }
817
818 #[inline]
819 fn size_hint(&self) -> (usize, Option<usize>) {
820 self.iter.size_hint()
821 }
822 }
823
824 impl<'a, T: IntervalBound> DoubleEndedIterator for $iter<'a, T> {
825 #[inline]
826 fn next_back(&mut self) -> Option<Self::Item> {
827 self.iter.next_back().map(|interval| interval.into())
828 }
829 }
830
831 impl<'a, T: IntervalBound> ExactSizeIterator for $iter<'a, T> where
832 vec_deque::Iter<'a, Interval<T>>: ExactSizeIterator
833 {
834 }
835
836 impl<T: IntervalBound> FromIterator<$item<T>> for IntervalSet<T> {
837 #[inline]
838 fn from_iter<I: IntoIterator<Item = $item<T>>>(intervals: I) -> Self {
839 let intervals = intervals.into_iter();
840 let mut set = Self::with_capacity(intervals.size_hint().0);
841 set.extend(intervals);
842 set
843 }
844 }
845
846 impl<'a, T: 'a + IntervalBound> FromIterator<&'a $item<T>> for IntervalSet<T> {
847 #[inline]
848 fn from_iter<I: IntoIterator<Item = &'a $item<T>>>(intervals: I) -> Self {
849 let intervals = intervals.into_iter();
850 let mut set = Self::with_capacity(intervals.size_hint().0);
851 set.extend(intervals);
852 set
853 }
854 }
855
856 impl<T: IntervalBound> Extend<$item<T>> for IntervalSet<T> {
857 #[inline]
858 fn extend<I: IntoIterator<Item = $item<T>>>(&mut self, intervals: I) {
859 for interval in intervals {
860 if self.insert(interval).is_err() {
861 return;
862 }
863 }
864 }
865 }
866
867 impl<'a, T: 'a + IntervalBound> Extend<&'a $item<T>> for IntervalSet<T> {
868 #[inline]
869 fn extend<I: IntoIterator<Item = &'a $item<T>>>(&mut self, intervals: I) {
870 for interval in intervals {
871 let interval: Interval<T> = interval.into();
872 if self.insert(interval).is_err() {
873 return;
874 }
875 }
876 }
877 }
878
879 impl<T: IntervalBound> From<$item<T>> for IntervalSet<T> {
880 #[inline]
881 fn from(interval: $item<T>) -> Self {
882 let mut set = Self::with_capacity(1);
883 let _ = set.insert(interval);
884 set
885 }
886 }
887 };
888}
889
890impl_iterator_conversions!(Interval, IntervalIter);
891impl_iterator_conversions!(Range, RangeIter);
892impl_iterator_conversions!(RangeInclusive, RangeInclusiveIter);
893
894impl<T: IntervalBound> FromIterator<T> for IntervalSet<T> {
895 #[inline]
896 fn from_iter<I: IntoIterator<Item = T>>(values: I) -> Self {
897 let values = values.into_iter();
898 let mut set = Self::with_capacity(values.size_hint().0);
899 for value in values {
900 if set.insert_value(value).is_err() {
901 break;
902 }
903 }
904 set
905 }
906}
907
908impl<'a, T: 'a + IntervalBound> FromIterator<&'a T> for IntervalSet<T> {
909 #[inline]
910 fn from_iter<I: IntoIterator<Item = &'a T>>(values: I) -> Self {
911 values.into_iter().cloned().collect()
912 }
913}