nested_containment_list/lib.rs
1//! Implementation of a Nested Containment List.
2//!
3//! A Nested Containment List is a data structure for storing types that implement the
4//! [`core::ops::RangeBounds`] trait. Elements stored in a [`NestedContainmentList`] are stored in a
5//! nested structure to allow for easy querying using other `RangeBounds` queries.
6//!
7//! ## Construction
8//!
9//! Construction of [`NestedContainmentList`]s can be done using either the [`new()`] or
10//! [`from_iter()`] methods. Construction from `from_iter()` has temporal complexity
11//! *O(n log(n))*, where *n* is the length of the slice.
12//!
13//! ```
14//! use nested_containment_list::NestedContainmentList;
15//! use std::ops::Range;
16//!
17//! let nclist = NestedContainmentList::<Range<usize>, usize>::new();
18//! ```
19//!
20//! ```
21//! use nested_containment_list::NestedContainmentList;
22//! use std::iter::FromIterator;
23//!
24//! let nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 5..7]);
25//! ```
26//!
27//! ## Mutation
28//!
29//! A [`NestedContainmentList`] allows for insertion and removal of [`RangeBounds`] types. Both of
30//! these methods have a temporal complexity of *O(log(n))*, where *n* is the number of
31//! `RangeBounds` stored in the data structure.
32//!
33//! ```
34//! use nested_containment_list::NestedContainmentList;
35//!
36//! let mut nclist = NestedContainmentList::new();
37//!
38//! nclist.insert(1..5);
39//! nclist.remove(&(1..5));
40//! ```
41//!
42//! ## Iteration
43//!
44//! Iterating over a [`NestedContainmentList`] is done in a nested manner. An [`Iterator`] is
45//! obtained from the [`overlapping()`] method. It is used to iterate directly over the top-most
46//! sublist, returning values which overlap with the query range, with nested intervals contained
47//! within the top-most elements being accessed through nested sublists.
48//!
49//! For example, iterating over all elements can be done as follows:
50//!
51//! ```
52//! use nested_containment_list::NestedContainmentList;
53//! use std::iter::FromIterator;
54//!
55//! let nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 6..7]);
56//! let mut sublist = nclist.overlapping(&(..));
57//!
58//! // The first element in the top-most sublist, 1..5.
59//! let first_element = sublist.next().unwrap();
60//! assert_eq!(first_element.value, &(1..5));
61//!
62//! // Contained inside the element's sublist is the interval 2..4.
63//! assert_eq!(first_element.sublist().next().unwrap().value, &(2..4));
64//!
65//! // The next element in the top-most sublist is 6..7, so it is obtained like the first element.
66//! let second_element = sublist.next().unwrap();
67//! assert_eq!(second_element.value, &(6..7));
68//! ```
69//!
70//! To remove a single level of nesting, one may use the [`Iterator::flatten()`] method.
71//!
72//! # no_std
73//! This crate is usable in
74//! [`no_std`](https://doc.rust-lang.org/1.7.0/book/using-rust-without-the-standard-library.html)
75//! environments when compiled on stable `rustc 1.36.0` or higher. The version limitation is due to
76//! the use of [`alloc`](https://doc.rust-lang.org/alloc/index.html), allowing for heap allocation
77//! without use of [`std`](https://doc.rust-lang.org/std/).
78//!
79//! [`from_iter()`]: NestedContainmentList::from_iter()
80//! [`new()`]: NestedContainmentList::new()
81//! [`overlapping()`]: NestedContainmentList::overlapping()
82//! [`Iterator`]: core::iter::Iterator
83//! [`Iterator::flatten()`]: core::iter::Iterator::flatten()
84//! [`RangeBounds`]: core::ops::RangeBounds
85
86#![warn(clippy::cargo, clippy::nursery, clippy::pedantic)]
87#![allow(clippy::doc_markdown, clippy::redundant_pub_crate)]
88#![cfg_attr(rustc_1_36, no_std)]
89
90#[cfg(rustc_1_36)]
91extern crate alloc;
92#[cfg(not(rustc_1_36))]
93extern crate std as alloc;
94#[cfg(not(rustc_1_36))]
95extern crate std as core;
96
97mod element;
98mod nestable;
99
100use crate::{
101 element::{Element, ParentElements},
102 nestable::Nestable,
103};
104use alloc::{borrow::ToOwned, collections::VecDeque, vec::Vec};
105use core::{
106 borrow::Borrow,
107 cmp::{min, Ordering},
108 hint::unreachable_unchecked,
109 iter::{once, Chain, FromIterator, FusedIterator, Iterator, Once},
110 marker::PhantomData,
111 mem,
112 num::NonZeroUsize,
113 ops::RangeBounds,
114};
115
116/// An element contained within an [`Overlapping`].
117///
118/// This element allows access to its contained value `I` and its sub-elements which also overlap
119/// with the query `S`.
120///
121/// An `OverlappingElement` is usually obtained from iterating over an `Overlapping`.
122///
123/// # Example
124/// ```
125/// use nested_containment_list::NestedContainmentList;
126/// use std::iter::FromIterator;
127///
128/// let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3]);
129/// let query = 2..4;
130/// let mut overlapping = nclist.overlapping(&query);
131///
132/// let overlapping_element = overlapping.next().unwrap();
133/// assert_eq!(overlapping_element.value, &(1..4));
134///
135/// let inner_overlapping_element = overlapping_element.sublist().next().unwrap();
136/// assert_eq!(inner_overlapping_element.value, &(2..3));
137/// ```
138#[derive(Debug)]
139pub struct OverlappingElement<'a, R, S, T>
140where
141 R: RangeBounds<T> + 'a,
142 S: RangeBounds<T> + 'a,
143 T: Ord + 'a,
144{
145 pub value: &'a R,
146 sublist_elements: &'a [Element<R, T>],
147 query: &'a S,
148 _marker: PhantomData<T>,
149}
150
151impl<'a, R, S, T> OverlappingElement<'a, R, S, T>
152where
153 R: RangeBounds<T>,
154 S: RangeBounds<T>,
155 T: Ord,
156{
157 /// Return an [`Overlapping`] [`Iterator`] over this element's contained sublist.
158 ///
159 /// # Example
160 /// ```
161 /// use nested_containment_list::NestedContainmentList;
162 /// use std::iter::FromIterator;
163 ///
164 /// let nclist = NestedContainmentList::from_iter(vec![1..5, 2..3, 3..4]);
165 /// let query = 2..4;
166 /// let mut overlapping = nclist.overlapping(&query);
167 ///
168 /// let overlapping_element = overlapping.next().unwrap();
169 /// assert_eq!(overlapping_element.value, &(1..5));
170 ///
171 /// let mut inner_overlapping = overlapping_element.sublist();
172 /// assert_eq!(inner_overlapping.next().unwrap().value, &(2..3));
173 /// assert_eq!(inner_overlapping.next().unwrap().value, &(3..4));
174 /// ```
175 ///
176 /// [`Iterator`]: core::iter::Iterator
177 #[must_use]
178 pub fn sublist(&self) -> Overlapping<'a, R, S, T> {
179 Overlapping::new(self.sublist_elements, self.query)
180 }
181}
182
183impl<'a, R, S, T> IntoIterator for OverlappingElement<'a, R, S, T>
184where
185 R: RangeBounds<T>,
186 S: RangeBounds<T>,
187 T: Ord,
188{
189 type Item = Self;
190 type IntoIter = Chain<Once<Self::Item>, Overlapping<'a, R, S, T>>;
191
192 /// Returns an [`Iterator`] over this element's `value`, followed by its `sublist()` elements
193 /// that overlap with the query `S`.
194 ///
195 /// This is useful if you want to iterate over all values including the enclosing value.
196 ///
197 /// # Example
198 /// ```
199 /// use nested_containment_list::NestedContainmentList;
200 /// use std::iter::FromIterator;
201 ///
202 /// let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3]);
203 /// let mut overlapping = nclist.overlapping(&(2..5));
204 /// let first_element = overlapping.next().unwrap();
205 /// let mut first_element_iter = first_element.into_iter();
206 ///
207 /// assert_eq!(first_element_iter.next().unwrap().value, &(1..4));
208 /// assert_eq!(first_element_iter.next().unwrap().value, &(2..3));
209 /// ```
210 ///
211 /// [`Iterator`]: core::iter::Iterator
212 #[must_use]
213 fn into_iter(self) -> Self::IntoIter {
214 once(Self {
215 value: self.value,
216 sublist_elements: &[],
217 query: self.query,
218 _marker: PhantomData,
219 })
220 .chain(self.sublist())
221 }
222}
223
224/// An [`Iterator`] over elements in a [`NestedContainmentList`] that overlap a query.
225///
226/// This [`Iterator`] is typically created from the [`NestedContainmentList::overlapping()`] method.
227///
228/// Iterates over all elements within the [`NestedContainmentList`] that overlap with the query
229/// interval. These elements are iterated in a nested structure, with all elements contained in
230/// other elements being accessed through those elements' [`sublist()`] methods.
231///
232/// # Example
233/// ```
234/// use nested_containment_list::NestedContainmentList;
235/// use std::iter::FromIterator;
236///
237/// let nclist = NestedContainmentList::from_iter(vec![1..5, 2..3, 2..4, 5..7]);
238/// let query = 3..6;
239/// let mut overlapping = nclist.overlapping(&query);
240///
241/// let first_element = overlapping.next().unwrap();
242/// let second_element = overlapping.next().unwrap();
243///
244/// // The outermost elements are accessed directly.
245/// assert_eq!(first_element.value, &(1..5));
246/// assert_eq!(second_element.value, &(5..7));
247///
248/// // Contained elements are accessed through their containing element's sublist.
249/// let mut inner_sublist = first_element.sublist();
250/// let inner_element = inner_sublist.next().unwrap();
251/// assert_eq!(inner_element.value, &(2..4));
252///
253/// // Note that 2..3 is not found within the nested iterators, since 2..3 does not overlap with 3..6.
254/// ```
255///
256/// [`sublist()`]: OverlappingElement::sublist()
257/// [`Iterator`]: core::iter::Iterator
258#[derive(Debug)]
259pub struct Overlapping<'a, R, S, T>
260where
261 R: RangeBounds<T> + 'a,
262 S: RangeBounds<T> + 'a,
263 T: Ord + 'a,
264{
265 elements: &'a [Element<R, T>],
266 query: &'a S,
267}
268
269impl<'a, R, S, T> Overlapping<'a, R, S, T>
270where
271 R: RangeBounds<T>,
272 S: RangeBounds<T>,
273 T: Ord,
274{
275 fn new(elements: &'a [Element<R, T>], query: &'a S) -> Self {
276 Overlapping { elements, query }
277 }
278}
279
280impl<'a, R, S, T> Iterator for Overlapping<'a, R, S, T>
281where
282 R: RangeBounds<T>,
283 S: RangeBounds<T>,
284 T: Ord,
285{
286 type Item = OverlappingElement<'a, R, S, T>;
287
288 /// Returns the next outer-most element.
289 ///
290 /// Note that any values contained within a returned element must be accessed through the
291 /// element's [`sublist()`] method.
292 ///
293 /// # Example
294 /// ```
295 /// use nested_containment_list::NestedContainmentList;
296 /// use std::iter::FromIterator;
297 ///
298 /// let nclist = NestedContainmentList::from_iter(vec![1..5]);
299 /// let query = 2..3;
300 /// let mut overlapping = nclist.overlapping(&query);
301 ///
302 /// assert_eq!(overlapping.next().unwrap().value, &(1..5));
303 /// assert!(overlapping.next().is_none());
304 /// ```
305 ///
306 /// [`sublist()`]: OverlappingElement::sublist()
307 fn next(&mut self) -> Option<Self::Item> {
308 while !self.elements.is_empty() {
309 let element = unsafe {
310 // SAFETY: Just checked that `self.elements` has at least one value.
311 self.elements.get_unchecked(0)
312 };
313 if element.value.overlapping(self.query) {
314 let sublist_elements = unsafe {
315 // SAFETY: `element.sublist_len` is invariantly guaranteed to only advance to a
316 // point within the bounds of `elements`. Therefore, this will never go out of
317 // bounds.
318 self.elements.get_unchecked(1..=element.sublist_len)
319 };
320 self.elements = unsafe {
321 // SAFETY: `element.sublist_len` will invariantly always be less than
322 // `elements.len()`, since the length of a sublist of an element never includes
323 // itself. Therefore, `element.sublist_len + 1 <= elements.len()`.
324 self.elements.get_unchecked((element.sublist_len + 1)..)
325 };
326 return Some(OverlappingElement {
327 value: &element.value,
328 sublist_elements,
329 query: self.query,
330 _marker: PhantomData,
331 });
332 }
333 match self.query.ordering(&element.value) {
334 // Have not yet chopped off the front elements.
335 Ordering::Greater | Ordering::Equal => {
336 // Custom version of a binary search.
337 let mut index = 0;
338 let mut size = self.elements.len();
339 if size != 0 {
340 while size > 1 {
341 let half = size / 2;
342 let mid = index + half;
343
344 let mid_element = unsafe {
345 // SAFETY: The maximum `mid` can be is bound above by
346 // `size / 2 + size / 4 + size / 8 + ...`
347 self.elements.top_most_parent_element(mid)
348 };
349
350 index = match if mid_element.value.overlapping(self.query) {
351 Ordering::Greater
352 } else {
353 mid_element.value.ordering(self.query)
354 } {
355 Ordering::Greater => index,
356 Ordering::Less | Ordering::Equal => mid,
357 };
358 size -= half;
359 }
360 let index_element = unsafe {
361 // SAFETY: Since `index` is obtained from the above binary search, where
362 // its max possible value is `size / 2 + size / 4 + size / 8 + ...`.
363 // Therefore it will be within the bounds of `self.elements`.
364 self.elements.get_unchecked(index)
365 };
366 match if index_element.value.overlapping(self.query) {
367 Ordering::Greater
368 } else {
369 index_element.value.ordering(self.query)
370 } {
371 Ordering::Less => {
372 index += 1;
373 }
374 Ordering::Greater | Ordering::Equal => {}
375 }
376 }
377 self.elements = unsafe {
378 // SAFETY: Since `index` is obtained from the above binary search, where its
379 // max possible value is `size / 2 + size / 4 + size / 8 + ... + 1`.
380 // Therefore it will be within the bounds of `self.elements`, being at most
381 // `self.elements.len()`.
382 self.elements.get_unchecked(index..)
383 };
384 }
385 // Have already emitted every overlapping element.
386 Ordering::Less => {
387 self.elements = &[];
388 }
389 }
390 }
391
392 None
393 }
394
395 /// Consumes the iterator, returning the last element.
396 ///
397 /// This method directly uses `next_back()` to jump straight to the end of the iterator.
398 ///
399 /// # Example
400 /// ```
401 /// use nested_containment_list::NestedContainmentList;
402 /// use std::iter::FromIterator;
403 ///
404 /// let nclist = NestedContainmentList::from_iter(vec![1..2, 3..4, 5..6]);
405 ///
406 /// let mut overlapping = nclist.overlapping(&(1..4));
407 /// assert_eq!(overlapping.last().unwrap().value, &(3..4));
408 /// ```
409 fn last(mut self) -> Option<Self::Item> {
410 self.next_back()
411 }
412
413 /// Returns the bounds on the remaining length of the iterator.
414 ///
415 /// The lower bound will always be `1` unless the iterator has been exhausted, in which case it
416 /// will be `0`. The upper bound will always be provided and will be the total count of
417 /// remaining elements to be iterated over, including those which are nested and those which may
418 /// not actually overlap with the query.
419 ///
420 /// # Example
421 /// ```
422 /// use nested_containment_list::NestedContainmentList;
423 /// use std::iter::FromIterator;
424 ///
425 /// let nclist = NestedContainmentList::from_iter(vec![1..5, 2..5, 6..7]);
426 /// let query = 2..4;
427 /// let overlapping = nclist.overlapping(&query);
428 ///
429 /// assert_eq!(overlapping.size_hint(), (1, Some(3)));
430 /// ```
431 fn size_hint(&self) -> (usize, Option<usize>) {
432 (min(1, self.elements.len()), Some(self.elements.len()))
433 }
434}
435
436impl<'a, R, S, T> DoubleEndedIterator for Overlapping<'a, R, S, T>
437where
438 R: RangeBounds<T>,
439 S: RangeBounds<T>,
440 T: Ord,
441{
442 fn next_back(&mut self) -> Option<Self::Item> {
443 while !self.elements.is_empty() {
444 // Find top level parent element.
445 let (element, index) = unsafe {
446 // SAFETY: `self.elements.len() - 1` wll always be less than `self.elements.len()`.
447 // Additionally, it is guaranteed to be at least `0`, because `self.elements` is not
448 // empty.
449 self.elements
450 .top_most_parent_element_with_index(self.elements.len() - 1)
451 };
452
453 if element.value.overlapping(self.query) {
454 let sublist_elements = unsafe {
455 // SAFETY: `index` is guaranteed to be at most `self.elements.len() - 1`, so
456 // this indexing will never be out of bounds.
457 self.elements.get_unchecked((index + 1)..)
458 };
459 self.elements = unsafe {
460 // SAFETY: `index` is guaranteed to be at most `self.elements.len() - 1`, so
461 // this indexing will never be out of bounds.
462 self.elements.get_unchecked(..index)
463 };
464 return Some(OverlappingElement {
465 value: &element.value,
466 sublist_elements,
467 query: self.query,
468 _marker: PhantomData,
469 });
470 }
471 match self.query.ordering(&element.value) {
472 // Have not yet chopped off the back elements.
473 Ordering::Less | Ordering::Equal => {
474 // Custom version of a binary search.
475 let mut index = 0;
476 let mut size = self.elements.len();
477 if size != 0 {
478 while size > 1 {
479 let half = size / 2;
480 let mid = index + half;
481
482 let mid_element = unsafe {
483 // SAFETY: The maximum `mid` can be is bound above by
484 // `size / 2 + size / 4 + size / 8 + ...`
485 self.elements.top_most_parent_element(mid)
486 };
487
488 index = match if mid_element.value.overlapping(self.query) {
489 Ordering::Less
490 } else {
491 mid_element.value.ordering(self.query)
492 } {
493 Ordering::Greater => index,
494 Ordering::Less | Ordering::Equal => mid,
495 };
496 size -= half;
497 }
498 let index_element = unsafe {
499 // SAFETY: Since `index` is obtained from the above binary search, where
500 // its max possible value is `size / 2 + size / 4 + size / 8 + ...`.
501 // Therefore it will be within the bounds of `self.elements`.
502 self.elements.get_unchecked(index)
503 };
504 match if index_element.value.overlapping(self.query) {
505 Ordering::Less
506 } else {
507 index_element.value.ordering(self.query)
508 } {
509 Ordering::Less => {
510 index += 1;
511 }
512 Ordering::Greater | Ordering::Equal => {}
513 }
514 }
515 self.elements = unsafe {
516 // SAFETY: Since `index` is obtained from the above binary search, where its
517 // max possible value is `size / 2 + size / 4 + size / 8 + ... + 1`.
518 // Therefore it will be within the bounds of `self.elements`, being at most
519 // `self.elements.len()`.
520 self.elements.get_unchecked(..index)
521 };
522 }
523 // Have already emitted every overlapping element.
524 Ordering::Greater => {
525 self.elements = &[];
526 }
527 }
528 }
529
530 None
531 }
532}
533
534impl<'a, R, S, T> FusedIterator for Overlapping<'a, R, S, T>
535where
536 R: RangeBounds<T>,
537 S: RangeBounds<T>,
538 T: Ord,
539{
540}
541
542/// An element obtained from [`Iter`].
543///
544/// This element allows access to its `value`, as well as providing an `Iterator` over all values
545/// nested within `value` through the `sublist()` method.
546///
547/// # Example
548/// ```
549/// use nested_containment_list::NestedContainmentList;
550/// use std::iter::FromIterator;
551///
552/// let nclist = NestedContainmentList::from_iter(vec![1..2]);
553///
554/// let mut iter = nclist.into_iter();
555/// assert_eq!(iter.next().unwrap().value, 1..2);
556/// ```
557#[derive(Debug)]
558pub struct IterElement<R, T>
559where
560 R: RangeBounds<T>,
561 T: Ord,
562{
563 pub value: R,
564 sublist_elements: VecDeque<Element<R, T>>,
565}
566
567impl<R, T> IterElement<R, T>
568where
569 R: RangeBounds<T>,
570 T: Ord,
571{
572 /// Returns an [`Iter`] [`Iterator`] over this element's sublist.
573 ///
574 /// Note that this method consumes the `IterElement`.
575 ///
576 /// # Example
577 /// ```
578 /// use nested_containment_list::NestedContainmentList;
579 /// use std::iter::FromIterator;
580 ///
581 /// let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3]);
582 ///
583 /// let mut iter = nclist.into_iter();
584 /// let mut sublist = iter.next().unwrap().sublist();
585 /// assert_eq!(sublist.next().unwrap().value, 2..3);
586 /// ```
587 ///
588 /// [`Iterator`]: core::iter::Iterator
589 pub fn sublist(self) -> Iter<R, T> {
590 Iter {
591 elements: self.sublist_elements,
592 }
593 }
594}
595
596impl<R, T> IntoIterator for IterElement<R, T>
597where
598 R: RangeBounds<T>,
599 T: Ord,
600{
601 type Item = Self;
602 type IntoIter = Chain<Once<Self::Item>, Iter<R, T>>;
603
604 /// Returns an [`Iterator`] over this element's `value`, followed by its `sublist()`.
605 ///
606 /// This is useful if you want to iterate over all values including the enclosing value.
607 ///
608 /// # Example
609 /// ```
610 /// use nested_containment_list::NestedContainmentList;
611 /// use std::iter::FromIterator;
612 ///
613 /// let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3]);
614 /// let mut iter = nclist.into_iter();
615 /// let first_element = iter.next().unwrap();
616 /// let mut first_element_iter = first_element.into_iter();
617 ///
618 /// assert_eq!(first_element_iter.next().unwrap().value, 1..4);
619 /// assert_eq!(first_element_iter.next().unwrap().value, 2..3);
620 /// ```
621 ///
622 /// [`Iterator`]: core::iter::Iterator
623 fn into_iter(self) -> Self::IntoIter {
624 once(Self {
625 value: self.value,
626 sublist_elements: VecDeque::new(),
627 })
628 .chain(Iter {
629 elements: self.sublist_elements,
630 })
631 }
632}
633
634/// An [`Iterator`] over all elements in a [`NestedContainmentList`].
635///
636/// This `Iterator` proceeds in a nested fashion, meaning it only yields the outer-most nested
637/// elements. To access the inner elements, call [`sublist()`] on the outer elements.
638///
639/// # Example
640///
641/// ```
642/// use nested_containment_list::NestedContainmentList;
643/// use std::iter::FromIterator;
644///
645/// let nclist = NestedContainmentList::from_iter(vec![1..2]);
646///
647/// let mut iter = nclist.into_iter();
648/// assert_eq!(iter.next().unwrap().value, 1..2);
649/// ```
650///
651/// [`Iterator`]: core::iter::Iterator
652/// [`sublist()`]: IterElement::sublist()
653#[derive(Debug)]
654pub struct Iter<R, T>
655where
656 R: RangeBounds<T>,
657 T: Ord,
658{
659 elements: VecDeque<Element<R, T>>,
660}
661
662impl<R, T> Iterator for Iter<R, T>
663where
664 R: RangeBounds<T>,
665 T: Ord,
666{
667 type Item = IterElement<R, T>;
668
669 /// Yield the next outer-most element.
670 ///
671 /// # Example
672 /// ```
673 /// use nested_containment_list::NestedContainmentList;
674 /// use std::iter::FromIterator;
675 ///
676 /// let nclist = NestedContainmentList::from_iter(vec![1..2]);
677 ///
678 /// let mut iter = nclist.into_iter();
679 /// assert_eq!(iter.next().unwrap().value, 1..2);
680 /// ```
681 fn next(&mut self) -> Option<Self::Item> {
682 if self.elements.is_empty() {
683 return None;
684 }
685
686 let element = self.elements.pop_front().unwrap();
687 let remaining_elements = self.elements.split_off(element.sublist_len);
688
689 Some(IterElement {
690 value: element.value,
691 sublist_elements: mem::replace(&mut self.elements, remaining_elements),
692 })
693 }
694
695 /// Consumes the iterator, returning the last element.
696 ///
697 /// This method directly uses `next_back()` to jump straight to the end of the iterator.
698 ///
699 /// # Example
700 /// ```
701 /// use nested_containment_list::NestedContainmentList;
702 /// use std::iter::FromIterator;
703 ///
704 /// let nclist = NestedContainmentList::from_iter(vec![1..2, 3..4]);
705 ///
706 /// let mut iter = nclist.into_iter();
707 /// assert_eq!(iter.last().unwrap().value, 3..4);
708 /// ```
709 fn last(mut self) -> Option<Self::Item> {
710 self.next_back()
711 }
712
713 /// Returns the bounds on the remaining length of the iterator.
714 ///
715 /// The lower bound will always be `1` unless the iterator has been exhausted, in which case it
716 /// will be `0`. The upper bound will always be provided and will be the total count of
717 /// remaining elements to be iterated over, including those which are nested.
718 ///
719 /// # Example
720 /// ```
721 /// use nested_containment_list::NestedContainmentList;
722 /// use std::iter::FromIterator;
723 ///
724 /// let nclist = NestedContainmentList::from_iter(vec![1..5, 2..5, 6..7]);
725 /// let iter = nclist.into_iter();
726 ///
727 /// assert_eq!(iter.size_hint(), (1, Some(3)));
728 /// ```
729 fn size_hint(&self) -> (usize, Option<usize>) {
730 (min(1, self.elements.len()), Some(self.elements.len()))
731 }
732}
733
734impl<R, T> DoubleEndedIterator for Iter<R, T>
735where
736 R: RangeBounds<T>,
737 T: Ord,
738{
739 fn next_back(&mut self) -> Option<Self::Item> {
740 if self.elements.is_empty() {
741 return None;
742 }
743
744 let mut sublist_elements = VecDeque::new();
745 let element = loop {
746 let parent_element = self.elements.pop_back().unwrap();
747 if let Some(offset) = parent_element.parent_offset {
748 if offset.get() > self.elements.len() {
749 // The parent element exists outside of the scope of this iterator.
750 break parent_element;
751 }
752 sublist_elements.push_front(parent_element);
753 self.elements
754 .split_off(self.elements.len() - offset.get() + 1)
755 .into_iter()
756 .for_each(|element| sublist_elements.push_front(element));
757 } else {
758 // This is the top-most element, since it has no parent offset.
759 break parent_element;
760 }
761 };
762
763 Some(IterElement {
764 value: element.value,
765 sublist_elements,
766 })
767 }
768}
769
770impl<R, T> FusedIterator for Iter<R, T>
771where
772 R: RangeBounds<T>,
773 T: Ord,
774{
775}
776
777/// Data structure for efficient storage and querying of [`RangeBounds`].
778///
779/// # Usage
780///
781/// A `NestedContainmentList` is a collection of [`RangeBounds`], and can be used similar to other
782/// collections. It has a [`len()`] and a [`capacity()`], allows for mutation through [`insert()`]
783/// and [`remove()`]. A main difference between `NestedContainmentList` and other Rust collections
784/// is how its contents are accessed: they may be iterated over through [`overlapping()`]. For
785/// further details, see [Data Access](#data-access).
786///
787/// ## Construction
788///
789/// A `NestedContainmentList` stores [`RangeBounds`] in a nested structure to allow for fast querying.
790/// Construction of a `NestedContainmentList` has temporal complexity *O(n log(n))*, where *n* is
791/// the number of [`RangeBounds`] being stored. Both insertion and removal, with [`insert()`] and
792/// [`remove()`] respectively, into a `NestedContainmentList` has temporal complexity *O(log(n))*,
793/// where *n* is the number of [`RangeBounds`] currently stored.
794///
795/// ### Example
796/// Construction of a `NestedContainmentList` can be done as follows:
797///
798/// ```
799/// use nested_containment_list::NestedContainmentList;
800/// use std::iter::FromIterator;
801///
802/// let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 5..7]);
803/// ```
804///
805/// ## Data Access
806///
807/// When data is stored within a `NestedContainmentList`, it is typically accessed by querying for
808/// [`RangeBounds`] overlapping another [`RangeBounds`], using the [`overlapping()`] method.
809///
810/// Both methods return a nested [`Iterator`] structure, with the difference being that access
811/// through [`overlapping()`] only iterates over [`RangeBounds`] that overlap with the query
812/// value. For details on the [`Iterator`]s returned by these methods, see the documentation for
813/// [`Overlapping`].
814///
815/// Querying using [`overlapping()`] has temporal complexity *O(n + log(N))*, where *N* is the
816/// number of [`RangeBounds`] stored, and *n* is the number of intervals overlapping with the query
817/// value.
818///
819/// ### Example
820/// Access using either method can be done as follows:
821///
822/// ```
823/// use nested_containment_list::NestedContainmentList;
824/// use std::iter::FromIterator;
825///
826/// let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 5..7]);
827///
828/// // Creates a Sublist Iterator.
829/// let mut sublist = nclist.overlapping(&(..));
830///
831/// // Creates an Overlapping Iterator.
832/// let query = 4..6;
833/// let mut overlapping = nclist.overlapping(&query);
834/// ```
835///
836/// [`capacity()`]: Self::capacity()
837/// [`insert()`]: Self::insert()
838/// [`len()`]: Self::len()
839/// [`overlapping()`]: Self::overlapping()
840/// [`remove()`]: Self::remove()
841/// [`Iterator`]: core::iter::Iterator
842/// [`RangeBounds`]: core::ops::RangeBounds
843#[derive(Debug)]
844pub struct NestedContainmentList<R, T>
845where
846 R: RangeBounds<T>,
847 T: Ord,
848{
849 elements: Vec<Element<R, T>>,
850}
851
852impl<R, T> NestedContainmentList<R, T>
853where
854 R: RangeBounds<T>,
855 T: Ord,
856{
857 /// Construct an empty `NestedContainmentList`.
858 ///
859 /// # Example
860 /// The following example constructs a new `NestedContainmentList` to hold elements of type
861 /// [`Range<usize>`].
862 /// ```
863 /// use nested_containment_list::NestedContainmentList;
864 /// use std::ops::Range;
865 ///
866 /// let nclist = NestedContainmentList::<Range<usize>, usize>::new();
867 /// ```
868 ///
869 /// [`Range<usize>`]: core::ops::Range
870 #[must_use]
871 pub fn new() -> Self {
872 Self {
873 elements: Vec::new(),
874 }
875 }
876
877 /// Construct an empty `NestedContainmentList` with the specified capacity.
878 ///
879 /// The `NestedContainmentList` will be able to hold exactly `capacity` [`RangeBounds`] without
880 /// reallocating. If `capacity` is `0`, the `NestedContainmentList` will not allocate.
881 ///
882 /// Note that `capacity` is not the same as `len`. `len` is how many elements are actually
883 /// contained, while `capacity` is how many could be contained given the current allocation.
884 ///
885 /// # Example
886 /// ```
887 /// use nested_containment_list::NestedContainmentList;
888 ///
889 /// let mut nclist = NestedContainmentList::with_capacity(5);
890 ///
891 /// nclist.insert(1..2); // Does not reallocate, since capacity is available.
892 /// ```
893 #[must_use]
894 pub fn with_capacity(capacity: usize) -> Self {
895 Self {
896 elements: Vec::with_capacity(capacity),
897 }
898 }
899
900 /// Returns the number of elements contained in the `NestedContainmentList`, also referred to as
901 /// its 'length'.
902 ///
903 /// # Example
904 /// ```
905 /// use nested_containment_list::NestedContainmentList;
906 ///
907 /// let mut nclist = NestedContainmentList::new();
908 /// assert_eq!(nclist.len(), 0);
909 ///
910 /// nclist.insert(1..5);
911 /// assert_eq!(nclist.len(), 1);
912 /// ```
913 #[must_use]
914 pub fn len(&self) -> usize {
915 self.elements.len()
916 }
917
918 /// Returns `true` if the `NestedContainmentList` contains no elements.
919 ///
920 /// # Example
921 /// ```
922 /// use nested_containment_list::NestedContainmentList;
923 ///
924 /// let mut nclist = NestedContainmentList::new();
925 /// assert!(nclist.is_empty());
926 ///
927 /// nclist.insert(1..5);
928 /// assert!(!nclist.is_empty());
929 /// ```
930 #[must_use]
931 pub fn is_empty(&self) -> bool {
932 self.elements.is_empty()
933 }
934
935 /// Returns the number of elements the `NestedContainmentList` can hold without reallocating.
936 ///
937 /// # Example
938 /// ```
939 /// use nested_containment_list::NestedContainmentList;
940 /// use std::ops::Range;
941 ///
942 /// let nclist = NestedContainmentList::<Range<usize>, usize>::with_capacity(10);
943 /// assert_eq!(nclist.capacity(), 10);
944 /// ```
945 #[must_use]
946 pub fn capacity(&self) -> usize {
947 self.elements.capacity()
948 }
949
950 /// Returns an [`Overlapping`] [`Iterator`] over all elements within the
951 /// `NestedContainmentList`.
952 ///
953 /// The [`Overlapping`] is a nested [`Iterator`] over all values contained in the
954 /// `NestedContainmentList` that overlap with the `query` [`RangeBounds`]. All [`RangeBounds`]
955 /// contained within other [`RangeBounds`] in the collection that also overlap with the `query`
956 /// are accessed as nested [`Overlapping`]s under their outer-most values.
957 ///
958 /// # Example
959 /// ```
960 /// use nested_containment_list::NestedContainmentList;
961 /// use std::iter::FromIterator;
962 ///
963 /// let nclist = NestedContainmentList::from_iter(vec![1..5, 2..3, 2..4, 5..7]);
964 /// let query = 3..6;
965 /// let mut overlapping = nclist.overlapping(&query);
966 ///
967 /// let first_element = overlapping.next().unwrap();
968 /// let second_element = overlapping.next().unwrap();
969 ///
970 /// // The outermost elements are accessed directly.
971 /// assert_eq!(first_element.value, &(1..5));
972 /// assert_eq!(second_element.value, &(5..7));
973 ///
974 /// // Contained elements are accessed through their containing element's sublist.
975 /// let mut inner_sublist = first_element.sublist();
976 /// let inner_element = inner_sublist.next().unwrap();
977 /// assert_eq!(inner_element.value, &(2..4));
978 ///
979 /// // Note that 2..3 is not found within the nested iterators, since 2..3 does not overlap with 3..6.
980 /// ```
981 ///
982 /// [`Iterator`]: core::iter::Iterator
983 #[must_use]
984 pub fn overlapping<'a, S>(&'a self, query: &'a S) -> Overlapping<'a, R, S, T>
985 where
986 S: RangeBounds<T>,
987 {
988 Overlapping::new(&self.elements, query)
989 }
990
991 fn insert_at(&mut self, index: usize, value: R) {
992 // Find the length of the value's sublist.
993 let mut len = 0;
994 let mut inner_indices = index..self.elements.len();
995 while let Some(inner_index) = inner_indices.next() {
996 let inner_element = unsafe {
997 // SAFETY: `inner_index` is guaranteed to be less than `self.elements.len()`, due to
998 // being obtained from the range `index..self.elements.len()`.
999 self.elements.get_unchecked_mut(inner_index)
1000 };
1001 if Nestable::contains(&value, &inner_element.value) {
1002 len += inner_element.sublist_len + 1;
1003 inner_element.parent_offset = Some(unsafe {
1004 // SAFETY: `inner_index` will never be less than `index`, and adding one to the
1005 // value will guarantee it is not zero.
1006 NonZeroUsize::new_unchecked(inner_index - index + 1)
1007 });
1008 if inner_element.sublist_len > 0 {
1009 inner_indices.nth(inner_element.sublist_len - 1);
1010 }
1011 } else {
1012 break;
1013 }
1014 }
1015
1016 // Handle parent elements.
1017 let mut direct_parent_index = None;
1018 if index > 0 {
1019 let mut parent_index = index - 1;
1020 loop {
1021 let parent_element = unsafe { self.elements.get_unchecked_mut(parent_index) };
1022 let current_parent_offset = parent_element.parent_offset;
1023 if Nestable::contains(&parent_element.value, &value) {
1024 // Store the value's direct parent.
1025 if direct_parent_index.is_none() {
1026 direct_parent_index = Some(parent_index);
1027 }
1028 // Lengthen the parent element's sublist, since value is being added to it.
1029 let current_parent_sublist_len = parent_element.sublist_len;
1030 parent_element.sublist_len += 1;
1031 // Lengthen the parent offset of every direct child element after the inserted
1032 // element.
1033 let mut child_index = index;
1034 while child_index <= parent_index + current_parent_sublist_len {
1035 let child_element = unsafe {
1036 // SAFETY: `child_index` will invariantly be within the bounds of
1037 // `self.elements`, since it is within the parent element's sublist.
1038 self.elements.get_unchecked_mut(child_index)
1039 };
1040 child_element.parent_offset = Some(unsafe {
1041 // SAFETY: `child_element` is guaranteed to have a `parent_offset`, and
1042 // therefore adding one to its value will also be non-zero.
1043 NonZeroUsize::new_unchecked(
1044 child_element.parent_offset.unwrap().get() + 1,
1045 )
1046 });
1047 child_index += child_element.sublist_len + 1;
1048 }
1049 }
1050 // Advance to next parent element.
1051 if let Some(offset) = current_parent_offset {
1052 parent_index -= offset.get();
1053 } else {
1054 break;
1055 }
1056 }
1057 }
1058
1059 // Insert the element.
1060 self.elements.insert(
1061 index,
1062 Element {
1063 value,
1064 sublist_len: len,
1065 parent_offset: direct_parent_index.map(|parent_index| unsafe {
1066 // SAFETY: `index` is always guaranteed to be strictly greater than
1067 // `parent_index`, as `parent_index` is at most `index - 1`.
1068 NonZeroUsize::new_unchecked(index - parent_index)
1069 }),
1070 _marker: PhantomData,
1071 },
1072 );
1073 }
1074
1075 /// Insert a new value into the `NestedContainmentList`.
1076 ///
1077 /// This insertion preserves the internal nested structure of the container, and has temporal
1078 /// complexity of *O(log(n))*.
1079 ///
1080 /// If the `NestedContainmentList`'s `capacity` is not large enough, the `NestedContainmentList`
1081 /// will reallocate.
1082 ///
1083 /// # Example
1084 /// ```
1085 /// use nested_containment_list::NestedContainmentList;
1086 ///
1087 /// let mut nclist = NestedContainmentList::new();
1088 /// nclist.insert(1..2);
1089 /// ```
1090 pub fn insert(&mut self, value: R) {
1091 // Binary search insertion.
1092 let index = match self
1093 .elements
1094 .binary_search_by(|element| element.value.ordering(&value))
1095 {
1096 Ok(index) | Err(index) => index,
1097 };
1098
1099 self.insert_at(index, value);
1100 }
1101
1102 /// Remove the specified value from the `NestedContainmentList`.
1103 ///
1104 /// This removal preserves the internal nested structure of the container, and has temporal
1105 /// complexity *O(log(n))*.
1106 ///
1107 /// # Example
1108 /// ```
1109 /// use nested_containment_list::NestedContainmentList;
1110 /// use std::iter::FromIterator;
1111 ///
1112 /// let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 3..4]);
1113 /// assert!(nclist.remove(&(2..4)));
1114 /// ```
1115 pub fn remove<Q>(&mut self, value: &Q) -> bool
1116 where
1117 Q: RangeBounds<T>,
1118 R: Borrow<Q>,
1119 {
1120 // Binary search removal.
1121 match self
1122 .elements
1123 .binary_search_by(|element| element.value.ordering(Borrow::borrow(value)))
1124 {
1125 Ok(index) => {
1126 // Correct all child elements' parent_offset values.
1127 let removed_element = unsafe {
1128 // SAFETY: Since `index` was obtained from the binary search, we can be sure it
1129 // is within the bounds of `self.elements`.
1130 self.elements.get_unchecked(index)
1131 };
1132 let removed_element_sublist_len = removed_element.sublist_len;
1133 let removed_element_parent_offset = removed_element.parent_offset;
1134 let mut child_index = index + 1;
1135 while child_index <= index + removed_element_sublist_len {
1136 let child_element = unsafe {
1137 // SAFETY: `child_index` is guaranteed to be less than
1138 // `self.elements.len()`, as it is less than `index +
1139 // removed_element_sublist_len` which is invariantly guaranteed to be within
1140 // the bounds of `self.elements`.
1141 self.elements.get_unchecked_mut(child_index)
1142 };
1143 child_element.parent_offset =
1144 removed_element_parent_offset.map(|offset| unsafe {
1145 // SAFETY: Both `offset` and `child_element.parent_offset` are
1146 // guaranteed to be non-zero, so subtracting one from their sum is also
1147 // guaranteed to be non-zero.
1148 NonZeroUsize::new_unchecked(
1149 offset.get() + child_element.parent_offset.unwrap().get() - 1,
1150 )
1151 });
1152 child_index += child_element.sublist_len + 1;
1153 }
1154
1155 // Shorten the sublist of every parent element.
1156 if let Some(offset) = removed_element_parent_offset {
1157 let mut parent_index = index - offset.get();
1158 loop {
1159 let parent_element = unsafe {
1160 // SAFETY: `parent_index` is invariantly guaranteed to be within the
1161 // bounds of `self.elements`.
1162 self.elements.get_unchecked_mut(parent_index)
1163 };
1164 parent_element.sublist_len -= 1;
1165 if let Some(parent_offset) = parent_element.parent_offset {
1166 parent_index -= parent_offset.get();
1167 } else {
1168 break;
1169 }
1170 }
1171 }
1172
1173 // Remove the element.
1174 self.elements.remove(index);
1175
1176 true
1177 }
1178 Err(_) => false,
1179 }
1180 }
1181}
1182
1183impl<R, T> FromIterator<R> for NestedContainmentList<R, T>
1184where
1185 R: RangeBounds<T>,
1186 T: Ord,
1187{
1188 /// Construct a `NestedContainmentList` from an [`Iterator`].
1189 ///
1190 /// This construction has temporal complexity of *O(n log(n))*, where *n* is the length of the
1191 /// `Iterator`.
1192 ///
1193 /// # Example
1194 /// ```
1195 /// use nested_containment_list::NestedContainmentList;
1196 /// use std::iter::FromIterator;
1197 ///
1198 /// let nclist = NestedContainmentList::from_iter(vec![1..5, 3..4, 2..4, 6..7]);
1199 /// ```
1200 ///
1201 /// [`Iterator`]: core::iter::Iterator
1202 fn from_iter<I>(iter: I) -> Self
1203 where
1204 I: IntoIterator<Item = R>,
1205 {
1206 // Sort the elements.
1207 let mut values = iter.into_iter().collect::<Vec<_>>();
1208 values.sort_unstable_by(Nestable::ordering);
1209
1210 // Depth-first construction.
1211 let mut elements: Vec<Element<R, T>> = Vec::with_capacity(values.len());
1212 let mut sublist_indices: Vec<usize> = Vec::with_capacity(values.len());
1213 for index in 0..values.len() {
1214 let value = values.remove(0);
1215 while !sublist_indices.is_empty() {
1216 let sublist_index = sublist_indices.pop().unwrap_or_else(|| {
1217 if cfg!(debug_assertions) {
1218 unreachable!()
1219 } else {
1220 unsafe { unreachable_unchecked() }
1221 }
1222 });
1223
1224 let mut sublist_element = unsafe {
1225 // SAFETY: `sublist_index` is always guaranteed to be less than the current
1226 // `index`, and since we push a new element with every `index`, `sublist_index`
1227 // is guaranteed to be within the bounds of `elements`.
1228 elements.get_unchecked_mut(sublist_index)
1229 };
1230 if Nestable::contains(&sublist_element.value, &value) {
1231 // We are within the previous sublist.
1232 sublist_indices.push(sublist_index);
1233 break;
1234 }
1235 // We are no longer within the previous sublist.
1236 let len = index - sublist_index - 1;
1237 sublist_element.sublist_len = len;
1238 }
1239
1240 elements.push(Element {
1241 value,
1242 sublist_len: 0,
1243 parent_offset: sublist_indices.last().map(|sublist_index| unsafe {
1244 // SAFETY: `index` is always guaranteed to be strictly greater than
1245 // `sublist_index`, as `sublist_index` is obtained from `sublist_indices`, which
1246 // only consists of values from `0..values.len()`, which is ascending, and
1247 // `index` hasn't yet been pushed to `sublist_indices`.
1248 NonZeroUsize::new_unchecked(index - sublist_index)
1249 }),
1250 _marker: PhantomData,
1251 });
1252 sublist_indices.push(index);
1253 }
1254
1255 // Clean up remaining sublist indices.
1256 for sublist_index in sublist_indices {
1257 let len = elements.len() - sublist_index - 1;
1258 unsafe {
1259 // SAFETY: Since we have iterated through every `index`, then `elements` is the same
1260 // length as `values`. Since each `sublist_index` is an index less than
1261 // `values.len()`, each `sublist_index` will always be within the bounds of
1262 // `elements`.
1263 elements.get_unchecked_mut(sublist_index)
1264 }
1265 .sublist_len = len;
1266 }
1267
1268 Self { elements }
1269 }
1270}
1271
1272impl<R, T> IntoIterator for NestedContainmentList<R, T>
1273where
1274 R: RangeBounds<T>,
1275 T: Ord,
1276{
1277 type Item = IterElement<R, T>;
1278 type IntoIter = Iter<R, T>;
1279
1280 fn into_iter(self) -> Self::IntoIter {
1281 Iter {
1282 elements: VecDeque::from(self.elements),
1283 }
1284 }
1285}
1286
1287impl<R, T> Extend<R> for NestedContainmentList<R, T>
1288where
1289 R: RangeBounds<T>,
1290 T: Ord,
1291{
1292 fn extend<I>(&mut self, iter: I)
1293 where
1294 I: IntoIterator<Item = R>,
1295 {
1296 // Sort the new values.
1297 let mut values: Vec<_> = iter.into_iter().collect();
1298 values.sort_unstable_by(Nestable::ordering);
1299
1300 let mut index = 0;
1301 for value in values {
1302 let prev_index = index;
1303 // Each subsequent value must belong after the previously inserted value.
1304 index = match self.elements[index..]
1305 .binary_search_by(|element| element.value.ordering(&value))
1306 {
1307 Ok(index) | Err(index) => index,
1308 };
1309 self.insert_at(prev_index + index, value);
1310 // The just-inserted value doesn't need to be included in the next iteration's search.
1311 index += 1;
1312 }
1313 }
1314}
1315
1316impl<R, T> From<Vec<R>> for NestedContainmentList<R, T>
1317where
1318 R: RangeBounds<T>,
1319 T: Ord,
1320{
1321 #[inline]
1322 fn from(v: Vec<R>) -> Self {
1323 Self::from_iter(v)
1324 }
1325}
1326
1327impl<R, T> From<&'_ [R]> for NestedContainmentList<R, T>
1328where
1329 R: RangeBounds<T> + Clone,
1330 T: Ord,
1331{
1332 #[inline]
1333 fn from(s: &[R]) -> Self {
1334 Self::from_iter(s.to_owned())
1335 }
1336}
1337
1338#[cfg(rustc_1_41)]
1339/// Due to orphaning rules, this implementation is only available in `rustc 1.41.0` and above. On
1340/// earlier `rustc` versions, a direct implementation of [`Into`] is provided instead, so that the
1341/// following example will still work:
1342///
1343/// ```
1344/// use nested_containment_list::NestedContainmentList;
1345///
1346/// let nclist = NestedContainmentList::from(vec![2..3, 1..4, 3..5]);
1347/// let vec: Vec<_> = nclist.into();
1348/// ```
1349///
1350/// See
1351/// [Implementing `Into` for conversions to external types in old versions of Rust](https://doc.rust-lang.org/nightly/core/convert/trait.Into.html#implementing-into-for-conversions-to-external-types-in-old-versions-of-rust)
1352/// for more information.
1353///
1354/// [`Into`]: core::convert::Into
1355#[cfg_attr(feature = "doc_item", doc_item::since(content="1.41.0"))]
1356impl<R, T> From<NestedContainmentList<R, T>> for Vec<R>
1357where
1358 R: RangeBounds<T>,
1359 T: Ord,
1360{
1361 #[inline]
1362 fn from(nclist: NestedContainmentList<R, T>) -> Self {
1363 nclist
1364 .elements
1365 .into_iter()
1366 .map(|element| element.value)
1367 .collect()
1368 }
1369}
1370
1371#[cfg(not(rustc_1_41))]
1372impl<R, T> Into<Vec<R>> for NestedContainmentList<R, T>
1373where
1374 R: RangeBounds<T>,
1375 T: Ord,
1376{
1377 #[inline]
1378 fn into(self) -> Vec<R> {
1379 self.elements
1380 .into_iter()
1381 .map(|element| element.value)
1382 .collect()
1383 }
1384}
1385
1386impl<R, T> Default for NestedContainmentList<R, T>
1387where
1388 R: RangeBounds<T>,
1389 T: Ord,
1390{
1391 /// Constructs a new, empty `NestedContainmentList`. Equivalent to [`new()`].
1392 ///
1393 /// # Example
1394 /// ```
1395 /// use nested_containment_list::NestedContainmentList;
1396 /// use std::ops::Range;
1397 ///
1398 /// let nclist = NestedContainmentList::<Range<usize>, usize>::default();
1399 /// ```
1400 ///
1401 /// [`new()`]: Self::new()
1402 fn default() -> Self {
1403 Self::new()
1404 }
1405}
1406
1407#[cfg(test)]
1408mod tests {
1409 use crate::NestedContainmentList;
1410 use alloc::{vec, vec::Vec};
1411 use claim::assert_none;
1412 use core::{iter::FromIterator, ops::Range};
1413
1414 #[test]
1415 fn new() {
1416 let nclist = NestedContainmentList::<Range<usize>, usize>::new();
1417
1418 // Check that the sublist is empty.
1419 assert_none!(nclist.overlapping(&(..)).next());
1420 }
1421
1422 #[test]
1423 fn default() {
1424 let nclist = NestedContainmentList::<Range<usize>, usize>::default();
1425
1426 // Check that the sublist is empty.
1427 assert_none!(nclist.overlapping(&(..)).next());
1428 }
1429
1430 #[test]
1431 fn len() {
1432 let mut nclist = NestedContainmentList::new();
1433
1434 assert_eq!(nclist.len(), 0);
1435
1436 nclist.insert(1..5);
1437
1438 assert_eq!(nclist.len(), 1);
1439 }
1440
1441 #[test]
1442 fn is_empty() {
1443 assert!(NestedContainmentList::<Range<usize>, usize>::new().is_empty());
1444 }
1445
1446 #[test]
1447 fn is_not_empty() {
1448 assert!(!NestedContainmentList::from_iter(vec![1..2]).is_empty());
1449 }
1450
1451 #[test]
1452 fn capacity() {
1453 let nclist = NestedContainmentList::<Range<usize>, usize>::with_capacity(10);
1454
1455 assert_eq!(nclist.capacity(), 10);
1456 }
1457
1458 #[test]
1459 fn insert_on_empty() {
1460 let mut nclist = NestedContainmentList::new();
1461
1462 nclist.insert(1..5);
1463
1464 let mut sublist = nclist.overlapping(&(..));
1465 assert_eq!(sublist.next().unwrap().value, &(1..5));
1466 assert_none!(sublist.next());
1467 }
1468
1469 #[test]
1470 fn insert_contained() {
1471 let mut nclist = NestedContainmentList::new();
1472
1473 nclist.insert(1..5);
1474 nclist.insert(2..4);
1475
1476 let mut sublist = nclist.overlapping(&(..));
1477 let sublist_first_element = sublist.next().unwrap();
1478 assert_eq!(sublist_first_element.value, &(1..5));
1479 let mut sublist_first_element_sublist = sublist_first_element.sublist();
1480 assert_eq!(sublist_first_element_sublist.next().unwrap().value, &(2..4));
1481 assert_none!(sublist_first_element_sublist.next());
1482 assert_none!(sublist.next());
1483 }
1484
1485 #[test]
1486 fn insert_containing() {
1487 let mut nclist = NestedContainmentList::new();
1488
1489 nclist.insert(2..4);
1490 nclist.insert(1..5);
1491
1492 let mut sublist = nclist.overlapping(&(..));
1493 let first_sublist_element = sublist.next().unwrap();
1494 assert_eq!(first_sublist_element.value, &(1..5));
1495 let mut first_sublist_element_sublist = first_sublist_element.sublist();
1496 assert_eq!(first_sublist_element_sublist.next().unwrap().value, &(2..4));
1497 assert_none!(first_sublist_element_sublist.next());
1498 assert_none!(sublist.next());
1499 }
1500
1501 #[test]
1502 fn insert_contained_not_at_end() {
1503 let mut nclist = NestedContainmentList::new();
1504
1505 nclist.insert(1..5);
1506 nclist.insert(6..10);
1507 nclist.insert(2..4);
1508
1509 let mut sublist = nclist.overlapping(&(..));
1510 let first_sublist_element = sublist.next().unwrap();
1511 assert_eq!(first_sublist_element.value, &(1..5));
1512 let mut first_sublist_element_sublist = first_sublist_element.sublist();
1513 assert_eq!(first_sublist_element_sublist.next().unwrap().value, &(2..4));
1514 assert_none!(first_sublist_element_sublist.next());
1515 assert_eq!(sublist.next().unwrap().value, &(6..10));
1516 assert_none!(sublist.next());
1517 }
1518
1519 #[test]
1520 fn insert_contained_and_containing() {
1521 let mut nclist = NestedContainmentList::new();
1522
1523 nclist.insert(1..5);
1524 nclist.insert(3..4);
1525 nclist.insert(2..4);
1526
1527 let mut sublist = nclist.overlapping(&(..));
1528 let first_sublist_element = sublist.next().unwrap();
1529 assert_eq!(first_sublist_element.value, &(1..5));
1530 let mut first_sublist_element_sublist = first_sublist_element.sublist();
1531 let second_sublist_element = first_sublist_element_sublist.next().unwrap();
1532 assert_eq!(second_sublist_element.value, &(2..4));
1533 let mut second_sublist_element_sublist = second_sublist_element.sublist();
1534 assert_eq!(
1535 second_sublist_element_sublist.next().unwrap().value,
1536 &(3..4)
1537 );
1538 assert_none!(first_sublist_element_sublist.next());
1539 assert_none!(sublist.next());
1540 }
1541
1542 #[test]
1543 fn insert_equal() {
1544 let mut nclist = NestedContainmentList::new();
1545
1546 nclist.insert(1..5);
1547 nclist.insert(1..5);
1548
1549 let mut sublist = nclist.overlapping(&(..));
1550 let first_sublist_element = sublist.next().unwrap();
1551 assert_eq!(first_sublist_element.value, &(1..5));
1552 let mut first_sublist_element_sublist = first_sublist_element.sublist();
1553 assert_eq!(first_sublist_element_sublist.next().unwrap().value, &(1..5));
1554 assert_none!(first_sublist_element_sublist.next());
1555 assert_none!(sublist.next());
1556 }
1557
1558 #[test]
1559 fn insert_disjoint() {
1560 let mut nclist = NestedContainmentList::new();
1561
1562 nclist.insert(1..5);
1563 nclist.insert(6..10);
1564
1565 let mut sublist = nclist.overlapping(&(..));
1566 assert_eq!(sublist.next().unwrap().value, &(1..5));
1567 assert_eq!(sublist.next().unwrap().value, &(6..10));
1568 assert_none!(sublist.next());
1569 }
1570
1571 #[test]
1572 fn insert_into_second_sublist() {
1573 let mut nclist = NestedContainmentList::from_iter(vec![1..4, 2..3, 5..9]);
1574
1575 nclist.insert(6..8);
1576
1577 let mut sublist = nclist.overlapping(&(..));
1578 assert_eq!(sublist.next().unwrap().value, &(1..4));
1579 let second_element = sublist.next().unwrap();
1580 assert_eq!(second_element.value, &(5..9));
1581 assert_eq!(second_element.sublist().next().unwrap().value, &(6..8));
1582 assert_none!(sublist.next());
1583 }
1584
1585 #[test]
1586 fn remove_from_empty() {
1587 let mut nclist = NestedContainmentList::<Range<usize>, usize>::new();
1588
1589 assert!(!nclist.remove(&(1..5)));
1590 }
1591
1592 #[test]
1593 fn remove() {
1594 let mut nclist = NestedContainmentList::from_iter(vec![1..5]);
1595
1596 assert!(nclist.remove(&(1..5)));
1597 }
1598
1599 #[test]
1600 fn remove_not_found() {
1601 let mut nclist = NestedContainmentList::from_iter(vec![1..5, 6..7]);
1602
1603 assert!(!nclist.remove(&(1..4)));
1604 }
1605
1606 #[test]
1607 fn remove_contained() {
1608 let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4]);
1609
1610 assert!(nclist.remove(&(2..4)));
1611
1612 let mut sublist = nclist.overlapping(&(..));
1613 let first_element = sublist.next().unwrap();
1614 assert_eq!(first_element.value, &(1..5));
1615 assert_none!(first_element.sublist().next());
1616 assert_none!(sublist.next());
1617 }
1618
1619 #[test]
1620 fn remove_containing() {
1621 let mut nclist = NestedContainmentList::from_iter(vec![1..5, 0..6]);
1622
1623 assert!(nclist.remove(&(0..6)));
1624
1625 let mut sublist = nclist.overlapping(&(..));
1626 let first_element = sublist.next().unwrap();
1627 assert_eq!(first_element.value, &(1..5));
1628 assert_none!(first_element.sublist().next());
1629 assert_none!(sublist.next());
1630 }
1631
1632 #[test]
1633 fn remove_contained_and_containing() {
1634 let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 3..4]);
1635
1636 assert!(nclist.remove(&(2..4)));
1637
1638 let mut sublist = nclist.overlapping(&(..));
1639 let first_sublist_element = sublist.next().unwrap();
1640 assert_eq!(first_sublist_element.value, &(1..5));
1641 let mut first_sublist_element_sublist = first_sublist_element.sublist();
1642 assert_eq!(first_sublist_element_sublist.next().unwrap().value, &(3..4));
1643 assert_none!(first_sublist_element_sublist.next());
1644 assert_none!(sublist.next());
1645 }
1646
1647 #[test]
1648 fn remove_from_second_sublist() {
1649 let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 6..7]);
1650
1651 assert!(nclist.remove(&(6..7)));
1652 }
1653
1654 #[test]
1655 fn overlapping() {
1656 let nclist = NestedContainmentList::from_iter(vec![1..5, 3..4, 2..4, 6..7]);
1657
1658 let query = 4..7;
1659 let mut overlapping = nclist.overlapping(&query);
1660
1661 let first_element = overlapping.next().unwrap();
1662 assert_eq!(first_element.value, &(1..5));
1663 assert_none!(first_element.sublist().next());
1664 let second_element = overlapping.next().unwrap();
1665 assert_eq!(second_element.value, &(6..7));
1666 assert_none!(second_element.sublist().next());
1667 assert_none!(overlapping.next());
1668 }
1669
1670 #[test]
1671 fn overlapping_skip_first() {
1672 let nclist = NestedContainmentList::from_iter(vec![1..2, 3..4]);
1673
1674 let query = 3..4;
1675 let mut overlapping = nclist.overlapping(&query);
1676
1677 let first_element = overlapping.next().unwrap();
1678 assert_eq!(first_element.value, &(3..4));
1679 assert_none!(first_element.sublist().next());
1680 assert_none!(overlapping.next());
1681 }
1682
1683 #[test]
1684 fn overlapping_contained() {
1685 let nclist = NestedContainmentList::from_iter(vec![1..5]);
1686
1687 let query = 2..3;
1688 let mut overlapping = nclist.overlapping(&query);
1689
1690 let first_element = overlapping.next().unwrap();
1691 assert_eq!(first_element.value, &(1..5));
1692 assert_none!(first_element.sublist().next());
1693 assert_none!(overlapping.next());
1694 }
1695
1696 #[test]
1697 fn overlapping_starts_at_topmost_element() {
1698 let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3]);
1699 let query = 2..4;
1700 let mut overlapping = nclist.overlapping(&query);
1701
1702 let overlapping_element = overlapping.next().unwrap();
1703 assert_eq!(overlapping_element.value, &(1..4));
1704
1705 let inner_overlapping_element = overlapping_element.sublist().next().unwrap();
1706 assert_eq!(inner_overlapping_element.value, &(2..3));
1707 }
1708
1709 #[test]
1710 fn overlapping_stops_early() {
1711 let nclist = NestedContainmentList::from_iter(vec![1..4, 2..5]);
1712 let query = 1..2;
1713 let mut overlapping = nclist.overlapping(&query);
1714
1715 assert_eq!(overlapping.next().unwrap().value, &(1..4));
1716 assert_none!(overlapping.next());
1717 }
1718
1719 #[test]
1720 fn overlapping_with_inner_not_overlapping() {
1721 let nclist = NestedContainmentList::from(vec![1..5, 1..2, 2..3, 4..5, 0..0]);
1722 let mut overlapping = nclist.overlapping(&(2..3));
1723
1724 let element = overlapping.next().unwrap();
1725 assert_eq!(element.value, &(1..5));
1726 assert_eq!(element.sublist().next().unwrap().value, &(2..3));
1727 }
1728
1729 #[test]
1730 fn overlapping_last() {
1731 let nclist = NestedContainmentList::from_iter(vec![1..2, 2..5, 3..4, 6..7]);
1732
1733 let last = nclist.overlapping(&(1..4)).last().unwrap();
1734
1735 assert_eq!(last.value, &(2..5));
1736 assert_eq!(last.sublist().next().unwrap().value, &(3..4));
1737 }
1738
1739 #[test]
1740 fn overlapping_size_hint() {
1741 let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3, 4..7]);
1742 let query = 1..3;
1743 let overlapping = nclist.overlapping(&query);
1744
1745 assert_eq!(overlapping.size_hint(), (1, Some(3)));
1746 }
1747
1748 #[test]
1749 fn overlapping_size_hint_empty() {
1750 let nclist = NestedContainmentList::<Range<usize>, usize>::new();
1751 let query = 1..3;
1752 let overlapping = nclist.overlapping(&query);
1753
1754 assert_eq!(overlapping.size_hint(), (0, Some(0)));
1755 }
1756
1757 #[test]
1758 fn overlapping_size_hint_after_iterating() {
1759 let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3, 4..7]);
1760 let query = 1..5;
1761 let mut overlapping = nclist.overlapping(&query);
1762 overlapping.next();
1763
1764 assert_eq!(overlapping.size_hint(), (1, Some(1)));
1765 }
1766
1767 #[test]
1768 fn overlapping_element_into_iter() {
1769 let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3]);
1770 let mut overlapping = nclist.overlapping(&(2..5));
1771 let first_element = overlapping.next().unwrap();
1772 let mut first_element_iter = first_element.into_iter();
1773
1774 assert_eq!(first_element_iter.next().unwrap().value, &(1..4));
1775 assert_eq!(first_element_iter.next().unwrap().value, &(2..3));
1776 }
1777
1778 #[test]
1779 fn overlapping_next_back() {
1780 let nclist = NestedContainmentList::from_iter(vec![0..1, 1..2, 2..5, 2..4, 6..7]);
1781 let mut overlapping = nclist.overlapping(&(1..4));
1782
1783 let second_element = overlapping.next_back().unwrap();
1784 assert_eq!(second_element.value, &(2..5));
1785 let mut second_element_sublist = second_element.sublist();
1786 assert_eq!(second_element_sublist.next_back().unwrap().value, &(2..4));
1787 assert_none!(second_element_sublist.next_back());
1788 let first_element = overlapping.next_back().unwrap();
1789 assert_eq!(first_element.value, &(1..2));
1790 assert_none!(first_element.sublist().next_back());
1791 assert_none!(overlapping.next_back());
1792 }
1793
1794 #[test]
1795 fn from_iter() {
1796 let nclist = NestedContainmentList::from_iter(vec![1..5, 3..4, 2..4, 6..7]);
1797
1798 let mut sublist = nclist.overlapping(&(..));
1799 let first_sublist_element = sublist.next().unwrap();
1800 assert_eq!(first_sublist_element.value, &(1..5));
1801 let mut first_sublist_element_sublist = first_sublist_element.sublist();
1802 let second_sublist_element = first_sublist_element_sublist.next().unwrap();
1803 assert_eq!(second_sublist_element.value, &(2..4));
1804 let mut second_sublist_element_sublist = second_sublist_element.sublist();
1805 assert_eq!(
1806 second_sublist_element_sublist.next().unwrap().value,
1807 &(3..4)
1808 );
1809 assert_none!(first_sublist_element_sublist.next());
1810 assert_eq!(sublist.next().unwrap().value, &(6..7));
1811 assert_none!(sublist.next());
1812 }
1813
1814 #[test]
1815 fn into_iter() {
1816 let nclist = NestedContainmentList::from_iter(vec![1..5, 3..4, 2..4, 6..7]);
1817
1818 let mut iter = nclist.into_iter();
1819 let first_sublist_element = iter.next().unwrap();
1820 assert_eq!(first_sublist_element.value, 1..5);
1821 let mut first_sublist_element_sublist = first_sublist_element.sublist();
1822 let second_sublist_element = first_sublist_element_sublist.next().unwrap();
1823 assert_eq!(second_sublist_element.value, 2..4);
1824 let mut second_sublist_element_sublist = second_sublist_element.sublist();
1825 assert_eq!(second_sublist_element_sublist.next().unwrap().value, 3..4);
1826 assert_none!(first_sublist_element_sublist.next());
1827 assert_eq!(iter.next().unwrap().value, 6..7);
1828 assert_none!(iter.next());
1829 }
1830
1831 #[test]
1832 fn iter_last() {
1833 let nclist = NestedContainmentList::from_iter(vec![1..2, 2..5, 3..4]);
1834
1835 let last = nclist.into_iter().last().unwrap();
1836
1837 assert_eq!(last.value, 2..5);
1838 assert_eq!(last.sublist().next().unwrap().value, 3..4);
1839 }
1840
1841 #[test]
1842 fn iter_size_hint() {
1843 let nclist = NestedContainmentList::from_iter(vec![1..5, 2..5, 6..7]);
1844 let iter = nclist.into_iter();
1845
1846 assert_eq!(iter.size_hint(), (1, Some(3)));
1847 }
1848
1849 #[test]
1850 fn iter_size_hint_empty() {
1851 let nclist = NestedContainmentList::<Range<usize>, usize>::new();
1852 let iter = nclist.into_iter();
1853
1854 assert_eq!(iter.size_hint(), (0, Some(0)));
1855 }
1856
1857 #[test]
1858 fn iter_size_hint_after_iterating() {
1859 let nclist = NestedContainmentList::from_iter(vec![1..5, 2..5, 6..7]);
1860 let mut iter = nclist.into_iter();
1861 iter.next();
1862
1863 assert_eq!(iter.size_hint(), (1, Some(1)));
1864 }
1865
1866 #[test]
1867 fn iter_next_back() {
1868 let nclist = NestedContainmentList::from_iter(vec![1..5, 3..4, 2..4, 6..7]);
1869 let mut iter = nclist.into_iter();
1870
1871 let second_element = iter.next_back().unwrap();
1872 assert_eq!(second_element.value, 6..7);
1873 assert_none!(second_element.sublist().next_back());
1874 let first_element = iter.next_back().unwrap();
1875 assert_eq!(first_element.value, 1..5);
1876 let mut first_element_sublist = first_element.sublist();
1877 let second_sublist_element = first_element_sublist.next_back().unwrap();
1878 assert_eq!(second_sublist_element.value, 2..4);
1879 let mut second_sublist_element_sublist = second_sublist_element.sublist();
1880 assert_eq!(
1881 second_sublist_element_sublist.next_back().unwrap().value,
1882 3..4
1883 );
1884 assert_none!(second_sublist_element_sublist.next_back());
1885 assert_none!(first_element_sublist.next_back());
1886 assert_none!(iter.next_back());
1887 }
1888
1889 #[test]
1890 fn iter_element_into_iter() {
1891 let nclist = NestedContainmentList::from_iter(vec![1..4, 2..3]);
1892 let mut iter = nclist.into_iter();
1893 let first_element = iter.next().unwrap();
1894 let mut first_element_iter = first_element.into_iter();
1895
1896 assert_eq!(first_element_iter.next().unwrap().value, 1..4);
1897 assert_eq!(first_element_iter.next().unwrap().value, 2..3);
1898 }
1899
1900 #[test]
1901 fn extend() {
1902 let mut nclist = NestedContainmentList::from(vec![2..3, 1..4, 7..8]);
1903
1904 nclist.extend(vec![0..5, 6..7, 7..9, 10..11]);
1905
1906 assert_eq!(
1907 Into::<Vec<_>>::into(nclist),
1908 vec![0..5, 1..4, 2..3, 6..7, 7..9, 7..8, 10..11]
1909 );
1910 }
1911
1912 #[test]
1913 fn from_vec() {
1914 let nclist = NestedContainmentList::from(vec![2..3, 1..4, 5..6]);
1915
1916 assert_eq!(Into::<Vec<_>>::into(nclist), vec![1..4, 2..3, 5..6]);
1917 }
1918
1919 #[test]
1920 fn from_slice() {
1921 let slice = &[2..3, 1..4, 5..6][..];
1922 let nclist = NestedContainmentList::from(slice);
1923 let mut iter = nclist.into_iter();
1924
1925 let first_element = iter.next().unwrap();
1926 assert_eq!(first_element.value, 1..4);
1927 assert_eq!(first_element.sublist().next().unwrap().value, 2..3);
1928 let second_element = iter.next().unwrap();
1929 assert_eq!(second_element.value, 5..6);
1930 }
1931
1932 #[test]
1933 fn into_vec() {
1934 let vec: Vec<_> = NestedContainmentList::from_iter(vec![2..3, 1..4, 5..6]).into();
1935
1936 let nclist: NestedContainmentList<_, _> = vec.into();
1937 let mut iter = nclist.into_iter();
1938
1939 let first_element = iter.next().unwrap();
1940 assert_eq!(first_element.value, 1..4);
1941 assert_eq!(first_element.sublist().next().unwrap().value, 2..3);
1942 let second_element = iter.next().unwrap();
1943 assert_eq!(second_element.value, 5..6);
1944 }
1945}