Struct numerated::tree::IntervalsTree
source · pub struct IntervalsTree<T> { /* private fields */ }
Expand description
§Non overlapping intervals tree
Can be considered as set of points, but with possibility to work with
continuous sets of this points (the same as interval) as fast as with points.
Insert and remove operations has complexity between [O(log(n)), O(n)]
,
where n
is amount of intervals in tree.
So, even if you insert for example points from [0u64
] to u64::MAX
,
then removing all of them or any part of them is as fast as removing one point.
§Examples
use numerated::{tree::IntervalsTree, interval::Interval};
use std::collections::BTreeSet;
use std::ops::RangeInclusive;
let mut tree = IntervalsTree::new();
let mut set = BTreeSet::new();
tree.insert(1i32);
// now `tree` contains only one interval: [1..=1]
set.insert(1i32);
// `points_iter()` - is iterator over all points in `tree`.
assert_eq!(set, tree.points_iter().collect());
// We can insert points from 3 to 100_000 only by one insert operation.
// `try` is only for range check, that it has start ≤ end.
// After `tree` will contain two intervals: `[1..=1]` and `[3..=100_000]`.
tree.insert(Interval::try_from(3..=100_000).unwrap());
// For `set` insert complexity == `O(n)`, where n is amount of elements in range.
set.extend(3..=100_000);
assert_eq!(set, tree.points_iter().collect());
// We can remove points from 1 to 99_000 (not inclusive) only by one remove operation.
// `try` is only for range check, that it has start ≤ end.
// After `tree` will contain two intervals: [99_000..=100_000]
tree.remove(Interval::try_from(1..99_000).unwrap());
// For `set` insert complexity == O(n*log(m)),
// where `n` is amount of elements in range and `m` is len of `set`.
(1..99_000).for_each(|i| { set.remove(&i); });
assert_eq!(set, tree.points_iter().collect());
// Can insert or remove all possible points just by one operation:
tree.insert(..);
tree.remove(..);
// Iterate over voids (intervals between intervals in tree):
tree.insert(Interval::try_from(1..=3).unwrap());
tree.insert(Interval::try_from(5..=7).unwrap());
let voids = tree.voids(..).map(RangeInclusive::from).collect::<Vec<_>>();
assert_eq!(voids, vec![i32::MIN..=0, 4..=4, 8..=i32::MAX]);
// Difference iterator: iterate over intervals from `tree` which are not in `other_tree`.
let other_tree: IntervalsTree<i32> = [3, 4, 5, 7, 8, 9].into_iter().collect();
let difference: Vec<_> = tree.difference(&other_tree).map(RangeInclusive::from).collect();
assert_eq!(difference, vec![1..=2, 6..=6]);
§Possible panic cases
Using IntervalsTree
for type T: Numerated
cannot cause panics,
if implementation Numerated
, Copy
, Ord
, Eq
are correct for T
.
In other cases IntervalsTree
does not guarantees execution without panics.
Implementations§
source§impl<T: Copy> IntervalsTree<T>
impl<T: Copy> IntervalsTree<T>
sourcepub fn intervals_amount(&self) -> usize
pub fn intervals_amount(&self) -> usize
Returns amount of not empty intervals in tree.
Complexity: O(1).
source§impl<T: Copy + Ord> IntervalsTree<T>
impl<T: Copy + Ord> IntervalsTree<T>
source§impl<T: Numerated> IntervalsTree<T>
impl<T: Numerated> IntervalsTree<T>
sourcepub fn iter(&self) -> impl Iterator<Item = Interval<T>> + '_
pub fn iter(&self) -> impl Iterator<Item = Interval<T>> + '_
Returns iterator over all intervals in tree.
sourcepub fn contains<I: Into<IntervalIterator<T>>>(&self, interval: I) -> bool
pub fn contains<I: Into<IntervalIterator<T>>>(&self, interval: I) -> bool
Returns true if for each p
∈ interval
⇒ p
∈ self
, otherwise returns false.
sourcepub fn insert<I: Into<IntervalIterator<T>>>(&mut self, interval: I)
pub fn insert<I: Into<IntervalIterator<T>>>(&mut self, interval: I)
Insert interval into tree.
- if
interval
is empty, then nothing will be inserted. - if
interval
is not empty, then after insertion: for eachp
∈interval
⇒p
∈self
.
Complexity: O(m * log(n))
, where
n
is amount of intervals inself
m
is amount of intervals inself
⋂interval
sourcepub fn remove<I: Into<IntervalIterator<T>>>(&mut self, interval: I)
pub fn remove<I: Into<IntervalIterator<T>>>(&mut self, interval: I)
Remove interval
from tree.
- if
interval
is empty, then nothing will be removed. - if
interval
is not empty, then after removing: for eachp
∈interval
⇒p
∉self
.
Complexity: O(m * log(n))
, where
n
is amount of intervals inself
m
is amount of intervals inself
⋂interval
sourcepub fn voids<I: Into<IntervalIterator<T>>>(
&self,
interval: I
) -> VoidsIterator<T, impl Iterator<Item = Interval<T>> + '_> ⓘ
pub fn voids<I: Into<IntervalIterator<T>>>( &self, interval: I ) -> VoidsIterator<T, impl Iterator<Item = Interval<T>> + '_> ⓘ
Returns iterator over non empty intervals, that consist of points p: T
where each p
∉ self
and p
∈ interval
.
Intervals in iterator are sorted in ascending order.
Iterating complexity: O(log(n) + m)
, where
n
is amount of intervals inself
m
is amount of intervals inself
⋂interval
sourcepub fn difference<'a>(
&'a self,
other: &'a Self
) -> impl Iterator<Item = Interval<T>> + '_
pub fn difference<'a>( &'a self, other: &'a Self ) -> impl Iterator<Item = Interval<T>> + '_
Returns iterator over intervals, which consist of points p: T
,
where each p
∈ self
and p
∉ other
.
Iterating complexity: O(n + m)
, where
n
is amount of intervals inself
m
is amount of intervals inother
sourcepub fn points_amount(&self) -> Option<T::Distance>
pub fn points_amount(&self) -> Option<T::Distance>
Number of points in tree set.
Complexity: O(n)
, where n
is amount of intervals in self
.
sourcepub fn points_iter(&self) -> impl Iterator<Item = T> + '_
pub fn points_iter(&self) -> impl Iterator<Item = T> + '_
Iterator over all points in tree set.
sourcepub fn to_vec(&self) -> Vec<RangeInclusive<T>>
pub fn to_vec(&self) -> Vec<RangeInclusive<T>>
Convert tree to vector of inclusive ranges.
Trait Implementations§
source§impl<T: Clone> Clone for IntervalsTree<T>
impl<T: Clone> Clone for IntervalsTree<T>
source§fn clone(&self) -> IntervalsTree<T>
fn clone(&self) -> IntervalsTree<T>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<T> Decode for IntervalsTree<T>
impl<T> Decode for IntervalsTree<T>
source§fn decode<__CodecInputEdqy: Input>(
__codec_input_edqy: &mut __CodecInputEdqy
) -> Result<Self, Error>
fn decode<__CodecInputEdqy: Input>( __codec_input_edqy: &mut __CodecInputEdqy ) -> Result<Self, Error>
source§fn decode_into<I>(
input: &mut I,
dst: &mut MaybeUninit<Self>
) -> Result<DecodeFinished, Error>where
I: Input,
fn decode_into<I>(
input: &mut I,
dst: &mut MaybeUninit<Self>
) -> Result<DecodeFinished, Error>where
I: Input,
source§impl<T: Copy> Default for IntervalsTree<T>
impl<T: Copy> Default for IntervalsTree<T>
source§impl<T> Encode for IntervalsTree<T>
impl<T> Encode for IntervalsTree<T>
source§fn size_hint(&self) -> usize
fn size_hint(&self) -> usize
source§fn encode_to<__CodecOutputEdqy: Output + ?Sized>(
&self,
__codec_dest_edqy: &mut __CodecOutputEdqy
)
fn encode_to<__CodecOutputEdqy: Output + ?Sized>( &self, __codec_dest_edqy: &mut __CodecOutputEdqy )
source§fn using_encoded<__CodecOutputReturn, __CodecUsingEncodedCallback: FnOnce(&[u8]) -> __CodecOutputReturn>(
&self,
f: __CodecUsingEncodedCallback
) -> __CodecOutputReturn
fn using_encoded<__CodecOutputReturn, __CodecUsingEncodedCallback: FnOnce(&[u8]) -> __CodecOutputReturn>( &self, f: __CodecUsingEncodedCallback ) -> __CodecOutputReturn
source§fn encoded_size(&self) -> usize
fn encoded_size(&self) -> usize
source§impl<T: Numerated, D: Into<IntervalIterator<T>>> FromIterator<D> for IntervalsTree<T>
impl<T: Numerated, D: Into<IntervalIterator<T>>> FromIterator<D> for IntervalsTree<T>
source§fn from_iter<I: IntoIterator<Item = D>>(iter: I) -> Self
fn from_iter<I: IntoIterator<Item = D>>(iter: I) -> Self
source§impl<T: PartialEq> PartialEq for IntervalsTree<T>
impl<T: PartialEq> PartialEq for IntervalsTree<T>
source§fn eq(&self, other: &IntervalsTree<T>) -> bool
fn eq(&self, other: &IntervalsTree<T>) -> bool
self
and other
values to be equal, and is used
by ==
.