[−][src]Struct unbounded_interval_tree::IntervalTree
The interval tree storing all the underlying intervals.
Methods
impl<Q> IntervalTree<Q> where
Q: Ord + Clone,
[src]
Q: Ord + Clone,
ⓘImportant traits for IntervalTreeIter<'a, Q>pub fn iter<'a>(&'a self) -> IntervalTreeIter<'a, Q>
[src]
Produces an inorder iterator for the interval tree.
Examples
use std::ops::Bound::Included; let mut tree = unbounded_interval_tree::IntervalTree::default(); tree.insert((Included(0), Included(10))); tree.insert((Included(-5), Included(-1))); tree.insert((Included(20), Included(30))); let mut iter = tree.iter(); assert_eq!(iter.next(), Some(&(Included(-5), Included(-1)))); assert_eq!(iter.next(), Some(&(Included(0), Included(10)))); assert_eq!(iter.next(), Some(&(Included(20), Included(30)))); assert_eq!(iter.next(), None);
pub fn insert(&mut self, range: (Bound<Q>, Bound<Q>))
[src]
Inserts an interval range
into the interval tree. Insertions respect the
binary search properties of this tree. An improvement to come is to rebalance
the tree (following an AVL or a red-black scheme).
Examples
use std::ops::Bound::{Included, Excluded, Unbounded}; let mut int_tree = unbounded_interval_tree::IntervalTree::default(); int_tree.insert((Included(5), Excluded(9))); int_tree.insert((Unbounded, Included(10))); let mut str_tree = unbounded_interval_tree::IntervalTree::default(); str_tree.insert((Included("Noria"), Unbounded));
pub fn contains_point(&self, q: &Q) -> bool
[src]
A "stabbing query" in the jargon: returns whether or not a point q
is contained in any of the intervals stored in the tree.
Examples
use std::ops::Bound::{Excluded, Unbounded}; let mut int_tree = unbounded_interval_tree::IntervalTree::default(); int_tree.insert((Excluded(5), Unbounded)); assert!(int_tree.contains_point(&100)); assert!(!int_tree.contains_point(&5));
Note that we can work with any type that implements the Ord+Clone
traits, so
we are not limited to just integers.
use std::ops::Bound::{Excluded, Unbounded}; let mut str_tree = unbounded_interval_tree::IntervalTree::default(); str_tree.insert((Excluded("Noria"), Unbounded)); assert!(str_tree.contains_point(&"Zebra")); assert!(!str_tree.contains_point(&"Noria"));
pub fn contains_interval(&self, q: &(Bound<Q>, Bound<Q>)) -> bool
[src]
An alternative "stabbing query": returns whether or not an interval q
is fully covered by the intervals stored in the tree.
Examples
use std::ops::Bound::{Included, Excluded, Unbounded}; let mut tree = unbounded_interval_tree::IntervalTree::default(); tree.insert((Included(20), Included(30))); tree.insert((Excluded(30), Excluded(50))); assert!(tree.contains_interval(&(Included(20), Included(40)))); assert!(!tree.contains_interval(&(Included(30), Included(50))));
pub fn get_interval_overlaps(
&self,
q: &(Bound<Q>, Bound<Q>)
) -> Vec<&(Bound<Q>, Bound<Q>)>
[src]
&self,
q: &(Bound<Q>, Bound<Q>)
) -> Vec<&(Bound<Q>, Bound<Q>)>
Returns the inorder list of all intervals stored in the tree that overlaps
with a given range q
(partially or completely).
Examples
use std::ops::Bound::{Included, Excluded, Unbounded}; let mut tree = unbounded_interval_tree::IntervalTree::default(); tree.insert((Included(0), Included(5))); tree.insert((Included(7), Excluded(10))); assert_eq!(tree.get_interval_overlaps(&(Included(-5), Excluded(7))), vec![&(Included(0), Included(5))]); assert!(tree.get_interval_overlaps(&(Included(10), Unbounded)).is_empty());
pub fn get_interval_difference<'a>(
&'a self,
q: &'a (Bound<Q>, Bound<Q>)
) -> Vec<(Bound<&'a Q>, Bound<&'a Q>)>
[src]
&'a self,
q: &'a (Bound<Q>, Bound<Q>)
) -> Vec<(Bound<&'a Q>, Bound<&'a Q>)>
Returns the ordered list of subintervals in q
that are not covered by the tree.
This is useful to compute what subsegments of q
that are not covered by the intervals
stored in the tree.
Examples
use std::ops::Bound::{Included, Excluded, Unbounded}; let mut tree = unbounded_interval_tree::IntervalTree::default(); tree.insert((Included(0), Excluded(10))); tree.insert((Excluded(10), Included(30))); tree.insert((Excluded(50), Unbounded)); assert_eq!(tree.get_interval_difference(&(Included(-5), Included(30))), vec![(Included(&-5), Excluded(&0)), (Included(&10), Included(&10))]); assert_eq!(tree.get_interval_difference(&(Unbounded, Excluded(10))), vec![(Unbounded, Excluded(&0))]); assert!(tree.get_interval_difference(&(Included(100), Unbounded)).is_empty());
Trait Implementations
impl<Q: Clone + Ord> Clone for IntervalTree<Q>
[src]
fn clone(&self) -> IntervalTree<Q>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<Q> Default for IntervalTree<Q> where
Q: Ord + Clone,
[src]
Q: Ord + Clone,
fn default() -> IntervalTree<Q>
[src]
Auto Trait Implementations
impl<Q> Send for IntervalTree<Q> where
Q: Send,
Q: Send,
impl<Q> Sync for IntervalTree<Q> where
Q: Sync,
Q: Sync,
impl<Q> Unpin for IntervalTree<Q>
impl<Q> UnwindSafe for IntervalTree<Q> where
Q: UnwindSafe,
Q: UnwindSafe,
impl<Q> RefUnwindSafe for IntervalTree<Q> where
Q: RefUnwindSafe,
Q: RefUnwindSafe,
Blanket Implementations
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From<T> for T
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,