Struct IntervalsTree

pub struct IntervalsTree<T> { /* private fields */ }

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

impl<T: Copy> IntervalsTree<T>

pub const fn new() -> Self

Creates new empty intervals tree.

pub fn intervals_amount(&self) -> usize

Returns amount of not empty intervals in tree.

Complexity: O(1).

pub fn is_empty(&self) -> bool

Checks if the tree is empty. Returns true if the tree contains no elements.

impl<T: Copy + Ord> IntervalsTree<T>

pub fn end(&self) -> Option<T>

Returns the biggest point in tree.

pub fn start(&self) -> Option<T>

Returns the smallest point in tree.

impl<T: Numerated> IntervalsTree<T>

pub fn iter(&self) -> impl Iterator<Item = Interval<T>> + '_

Returns iterator over all intervals in tree.

pub fn contains<I: Into<IntervalIterator<T>>>(&self, interval: I) -> bool

Returns true if for each p ∈ interval ⇒ p ∈ self, otherwise returns false.

pub fn insert<I: Into<IntervalIterator<T>>>(&mut self, interval: I) -> bool

Insert interval into tree.

• if interval is empty, then nothing will be inserted.
• if interval is not empty, then after insertion: for each p ∈ interval ⇒ p ∈ self.

Complexity: O(m * log(n)), where

• n is amount of intervals in self
• m is amount of intervals in self ⋂ interval

Returns whether self has been changed.

pub fn remove<I: Into<IntervalIterator<T>>>(&mut self, interval: I) -> bool

Remove interval from tree.

• if interval is empty, then nothing will be removed.
• if interval is not empty, then after removing: for each p ∈ interval ⇒ p ∉ self.

Complexity: O(m * log(n)), where

• n is amount of intervals in self
• m is amount of intervals in self ⋂ interval

Returns whether self has been changed.

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 in self
• m is amount of intervals in self ⋂ interval

pub fn difference<'a>( &'a self, other: &'a Self, ) -> impl Iterator<Item = Interval<T>> + 'a

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 in self
• m is amount of intervals in other

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.

pub fn points_iter(&self) -> impl Iterator<Item = T> + '_

Iterator over all points in tree set.

pub fn to_vec(&self) -> Vec<RangeInclusive<T>>

Convert tree to vector of inclusive ranges.

Trait Implementations

impl<T: Clone> Clone for IntervalsTree<T>

fn clone(&self) -> IntervalsTree<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Numerated> Debug for IntervalsTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Decode for IntervalsTree<T>

where BTreeMap<T, T>: Decode,

fn decode<__CodecInputEdqy: Input>( __codec_input_edqy: &mut __CodecInputEdqy, ) -> Result<Self, Error>

Attempt to deserialise the value from input.

fn decode_into<I>( input: &mut I, dst: &mut MaybeUninit<Self>, ) -> Result<DecodeFinished, Error>

where I: Input,

Attempt to deserialize the value from input into a pre-allocated piece of memory.

fn skip<I>(input: &mut I) -> Result<(), Error>

where I: Input,

Attempt to skip the encoded value from input.

fn encoded_fixed_size() -> Option<usize>

Returns the fixed encoded size of the type.

impl<T: Copy> Default for IntervalsTree<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Encode for IntervalsTree<T>

where BTreeMap<T, T>: Encode,

fn size_hint(&self) -> usize

If possible give a hint of expected size of the encoding.

fn encode_to<__CodecOutputEdqy: Output + ?Sized>( &self, __codec_dest_edqy: &mut __CodecOutputEdqy, )

Convert self to a slice and append it to the destination.

fn encode(&self) -> Vec<u8>

Convert self to an owned vector.

fn using_encoded<__CodecOutputReturn, __CodecUsingEncodedCallback: FnOnce(&[u8]) -> __CodecOutputReturn>( &self, f: __CodecUsingEncodedCallback, ) -> __CodecOutputReturn

Convert self to a slice and then invoke the given closure with it.

fn encoded_size(&self) -> usize

Calculates the encoded size.

impl<T: Numerated, D: Into<IntervalIterator<T>>> FromIterator<D> for IntervalsTree<T>

fn from_iter<I: IntoIterator<Item = D>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: PartialEq> PartialEq for IntervalsTree<T>

fn eq(&self, other: &IntervalsTree<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> TypeInfo for IntervalsTree<T>

where BTreeMap<T, T>: TypeInfo + 'static, T: TypeInfo + 'static,

type Identity = IntervalsTree<T>

The type identifying for which type info is provided.

fn type_info() -> Type

Returns the static type identifier for Self.

impl<T> EncodeLike for IntervalsTree<T>

where BTreeMap<T, T>: Encode,

impl<T: Eq> Eq for IntervalsTree<T>

impl<T> StructuralPartialEq for IntervalsTree<T>