Struct RangeTree 

pub struct RangeTree<T: RangeTreeKey> { /* private fields */ }

A b+tree stores range segment of [start, start+size)

Implementations

impl<T: RangeTreeKey> RangeTree<T>

pub fn new() -> Self

pub fn is_empty(&self) -> bool

pub fn get_space(&self) -> T

pub fn len(&self) -> usize

pub fn add(&mut self, start: T, size: T) -> Result<(), (T, T)>

Add range segment, merge with adjacent ranges, assuming no intersections.

Returns Ok(()) if there are no intersection; otherwise returns the overlapping range as Err((existing_start, existing_size)).

This equals to add + add_find_overlap in v0.1

pub fn add_with<O>( &mut self, start: T, size: T, ops: &mut O, ) -> Result<(), (T, T)>

where O: RangeTreeOps<T>,

pub fn add_abs(&mut self, start: T, end: T) -> Result<(), (T, T)>

Add to the tree with [start, end)

Returns Ok(()) if there are no intersection; otherwise returns the overlapping range as Err((existing_start, existing_size)).

This equals to add_abs in v0.1

pub fn add_loosely(&mut self, start: T, size: T)

Add range which may have multiple intersections with existing range, ensuring union result stores in the tree

pub fn remove(&mut self, start: T, size: T) -> Result<(), Option<(T, T)>>

Valid and remove specify range start:size

Return value

• Only return Ok(()) when there’s existing range equal to or contain the removal range in the tree,
• return Err(None) when not found,
• return Err(Some(start, size)) when a range intersect with the removal range, or when the removal range larger than existing range.

pub fn remove_with<O>( &mut self, start: T, size: T, ops: &mut O, ) -> Result<(), Option<(T, T)>>

where O: RangeTreeOps<T>,

Valid and remove specify range start:size

Return value

• Only return Ok(()) when there’s existing range equal to or contain the removal range in the tree,
• return Err(None) when not found,
• return Err(Some(start, size)) when a range intersect with the removal range, or when the removal range larger than existing range.

pub fn remove_loosely(&mut self, start: T, size: T) -> bool

Remove all the intersection ranges in the tree

Unlike the strict behavior of RangeTree::remove(), this function allows the removal range start:size to to be larger than the existing range.

Equals to remove_and_split in v0.1

return true if overlapping range found and removed. return false if overlapping range not found.

#[inline]

pub fn range<'a, R: RangeBounds<T>>(&'a self, r: R) -> RangeIter<'a, T>

return only when segment overlaps with start..end

NOTE

Be aware the first range may have _start < start, and the last range may have _start + _size > end

pub fn collect(&self) -> Vec<(T, T)>

pub fn iter(&self) -> Iter<'_, T>

pub fn validate(&self)

pub fn memory_used(&self) -> usize

Trait Implementations

impl<'a, T: RangeTreeKey> IntoIterator for &'a RangeTree<T>

type Item = (T, T)

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: RangeTreeKey> IntoIterator for RangeTree<T>

type Item = (T, T)

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.