Struct nodit::zosdit::map::ZosditMap

pub struct ZosditMap<I, K, V> { /* private fields */ }

A Zero Overlap Sequential Discrete Interval Tree Map Data-Structure based off BTreeMap and SmallVec

See the zosdit module documentation for a more detailed explanation of how this data-structure works.

I is the generic type parameter for the Ord type the K type is a interval over.

K is the generic type parameter for the interval type stored as the keys in the map.

V is the generic type parameter for the values associated with the keys in the map.

Phrasing it another way: I is the point type, K is the interval type, and V is the value type.

Examples

use nodit::interval::ie;
use nodit::ZosditMap;

// Make a map of intervals to booleans
let mut map = ZosditMap::from_slice_strict_back([
	(ie(4, 8), false),
	(ie(8, 18), true),
	(ie(20, 100), false),
])
.unwrap();

// Iterate over the entries in the map
for (interval, value) in map.iter() {
	println!("{interval:?}, {value:?}");
}

Implementations

impl<I, K, V> ZosditMap<I, K, V>

where I: PointType, K: IntervalType<I>,

pub fn new() -> Self

Makes a new, empty ZosditMap.

Examples

use nodit::{Interval, ZosditMap};

let map: ZosditMap<i8, Interval<i8>, bool> = ZosditMap::new();

pub fn len(&self) -> usize

See NoditMap::len() for more details.

pub fn is_empty(&self) -> bool

See NoditMap::is_empty() for more details.

pub fn first_key_value(&self) -> Option<(&K, &V)>

Returns the first key-value pair in the map.

Examples

use nodit::interval::ii;
use nodit::ZosditMap;

let map = ZosditMap::from_slice_strict_back([
	(ii(0, 4), -2),
	(ii(4, 4), -4),
	(ii(4, 4), -8),
])
.unwrap();

assert_eq!(
	map.first_key_value(),
	Some((&ii(0, 4), &-2))
);

pub fn last_key_value(&self) -> Option<(&K, &V)>

Returns the last key-value pair in the map.

Examples

use nodit::interval::ii;
use nodit::ZosditMap;

let map = ZosditMap::from_slice_strict_back([
	(ii(0, 4), -2),
	(ii(4, 4), -4),
	(ii(4, 4), -8),
])
.unwrap();

assert_eq!(
	map.last_key_value(),
	Some((&ii(4, 4), &-8))
);

pub fn get_last_value_at_point(&self, point: I) -> Option<&V>

Gets the last value stored in the SmallVec for the interval(s) that contain that point.

Examples

use nodit::interval::ii;
use nodit::ZosditMap;

let map = ZosditMap::from_slice_strict_back([
	(ii(0, 4), -2),
	(ii(4, 4), -4),
	(ii(4, 4), -8),
	(ii(4, 8), -10),
])
.unwrap();

assert_eq!(map.get_last_value_at_point(0), Some(&-2));
assert_eq!(map.get_last_value_at_point(4), Some(&-10));
assert_eq!(map.get_last_value_at_point(10), None);

pub fn remove_last_value_at_point(&mut self, point: I) -> Option<V>

Removes the last value stored in the SmallVec for the interval(s) that contain that point.

Examples

use nodit::interval::ii;
use nodit::ZosditMap;

let mut map = ZosditMap::from_slice_strict_back([
	(ii(0, 4), -2),
	(ii(4, 4), -4),
	(ii(4, 4), -8),
	(ii(4, 8), -10),
])
.unwrap();

assert_eq!(map.get_last_value_at_point(4), Some(&-10));
assert_eq!(map.remove_last_value_at_point(4), Some(-10));

assert_eq!(map.get_last_value_at_point(4), Some(&-8));
assert_eq!(map.remove_last_value_at_point(4), Some(-8));

assert_eq!(map.get_last_value_at_point(4), Some(&-4));
assert_eq!(map.remove_last_value_at_point(4), Some(-4));

assert_eq!(map.get_last_value_at_point(4), Some(&-2));
assert_eq!(map.remove_last_value_at_point(4), Some(-2));

assert_eq!(map.get_last_value_at_point(4), None);
assert_eq!(map.remove_last_value_at_point(4), None);

pub fn insert_strict_back( &mut self, interval: K, value: V ) -> Result<(), NonZeroOverlapError<V>>

Appends the value to the SmallVec corresponding to the interval.

If the given interval non-zero-overlaps one or more intervals already in the map, then an NonZeroOverlapError is returned and the map is not updated.

If the given interval is singular and there is an identical singular interval entry already in the map then the value is appended to the back on the internal SmallVec.

Panics

Panics if the given interval is an invalid interval. See Invalid Intervals for more details.

Examples

use nodit::interval::ii;
use nodit::ZosditMap;

let mut map = ZosditMap::new();

assert_eq!(map.insert_strict_back(ii(0, 10), -2), Ok(()));
assert_eq!(map.insert_strict_back(ii(10, 10), -4), Ok(()));
assert_eq!(map.insert_strict_back(ii(10, 10), -6), Ok(()));

assert_eq!(
	map.into_iter().collect::<Vec<_>>(),
	[(ii(0, 10), -2), (ii(10, 10), -4), (ii(10, 10), -6)]
);

pub fn is_zero_overlap<Q>(&self, interval: Q) -> bool

where Q: IntervalType<I>,

Returns true if the given interval zero-overlaps the intervals in the map, and false if not.

Panics

Panics if the given interval is an invalid interval. See Invalid Intervals for more details.

Examples

use nodit::interval::ii;
use nodit::ZosditMap;

let mut map = ZosditMap::new();

assert_eq!(map.insert_strict_back(ii(0, 10), -2), Ok(()));
assert_eq!(map.insert_strict_back(ii(10, 10), -4), Ok(()));
assert_eq!(map.insert_strict_back(ii(10, 10), -6), Ok(()));

assert_eq!(map.is_zero_overlap(ii(0, 0)), true);
assert_eq!(map.is_zero_overlap(ii(10, 10)), true);
assert_eq!(map.is_zero_overlap(ii(10, 12)), true);
assert_eq!(map.is_zero_overlap(ii(10, 12)), true);

assert_eq!(map.is_zero_overlap(ii(0, 2)), false);
assert_eq!(map.is_zero_overlap(ii(4, 4)), false);
assert_eq!(map.is_zero_overlap(ii(4, 12)), false);

pub fn cut<'a, Q>(&'a mut self, interval: Q) -> impl Iterator<Item = (K, V)>

where Q: IntervalType<I> + 'a, V: Clone,

The same as NoditMap::cut() except it flattens the SmallVecs of values into the returned iterator.

See NoditMap::cut() for more details.

Panics

Panics if the given interval is an invalid interval. See Invalid Intervals for more details.

Examples

use nodit::interval::{ee, ii};
use nodit::ZosditMap;

let mut base = ZosditMap::from_slice_strict_back([
	(ii(0, 4), -2),
	(ii(4, 4), -4),
	(ii(4, 4), -6),
	(ii(4, 8), -8),
])
.unwrap();

assert_eq!(base.len(), 4);

let after_cut = ZosditMap::from_slice_strict_back([
	(ii(0, 2), -2),
	(ii(6, 8), -8),
])
.unwrap();

assert_eq!(
	base.cut(ee(2, 6)).collect::<Vec<_>>(),
	[
		(ii(3, 4), -2),
		(ii(4, 4), -4),
		(ii(4, 4), -6),
		(ii(4, 5), -8)
	]
);
assert_eq!(base.len(), 2);
assert_eq!(base, after_cut);

pub fn overlapping<Q>(&self, interval: Q) -> impl Iterator<Item = (&K, &V)>

where Q: IntervalType<I>,

The same as NoditMap::overlapping() except it flattens the SmallVecs of values into the returned iterator.

See NoditMap::overlapping() for more details.

Panics

Panics if the given interval is an invalid interval. See Invalid Intervals for more details.

Examples

use nodit::interval::{ee, ii};
use nodit::ZosditMap;

let mut base = ZosditMap::from_slice_strict_back([
	(ii(0, 4), -2),
	(ii(4, 4), -4),
	(ii(4, 4), -6),
	(ii(4, 8), -8),
	(ii(8, 12), -10),
])
.unwrap();

assert_eq!(
	base.overlapping(ii(4, 4)).collect::<Vec<_>>(),
	[
		(&ii(0, 4), &-2),
		(&ii(4, 4), &-4),
		(&ii(4, 4), &-6),
		(&ii(4, 8), &-8),
	]
);

pub fn iter(&self) -> impl DoubleEndedIterator<Item = (&K, &V)>

Returns an iterator over every entry in the map in ascending order.

Examples

use nodit::interval::ie;
use nodit::ZosditMap;

let map = ZosditMap::from_slice_strict_back([
	(ie(1, 4), -2),
	(ie(4, 8), -4),
	(ie(8, 100), -6),
])
.unwrap();

let mut iter = map.iter();

assert_eq!(iter.next(), Some((&ie(1, 4), &-2)));
assert_eq!(iter.next(), Some((&ie(4, 8), &-4)));
assert_eq!(iter.next(), Some((&ie(8, 100), &-6)));
assert_eq!(iter.next(), None);

pub fn from_slice_strict_back<const N: usize>( slice: [(K, V); N] ) -> Result<ZosditMap<I, K, V>, NonZeroOverlapError<V>>

Allocates a ZosditMap and moves the given entries from the given slice into the map using ZosditMap::insert_strict_back().

May return an Err while inserting. See NoditMap::insert_strict() for details.

Panics

Panics if the given interval is an invalid interval. See Invalid Intervals for more details.

Examples

use nodit::interval::ie;
use nodit::ZosditMap;

let map = ZosditMap::from_slice_strict_back([
	(ie(1, 4), -2),
	(ie(4, 8), -4),
	(ie(8, 100), -6),
])
.unwrap();

pub fn from_iter_strict_back( iter: impl Iterator<Item = (K, V)> ) -> Result<ZosditMap<I, K, V>, NonZeroOverlapError<V>>

Collects a ZosditMap from an iterator of (interval, value) tuples using ZosditMap::insert_strict_back().

May return an Err while inserting. See ZosditMap::insert_strict_back() for details.

Panics

Panics if the given interval is an invalid interval. See Invalid Intervals for more details.

Examples

use nodit::interval::ie;
use nodit::ZosditMap;

let slice = [(ie(1, 4), -2), (ie(4, 8), -4), (ie(8, 100), -6)];

let map: ZosditMap<_, _, _> = ZosditMap::from_iter_strict_back(
	slice
		.into_iter()
		.filter(|(interval, _)| interval.start() > 2),
)
.unwrap();

Trait Implementations

impl<I: Clone, K: Clone, V: Clone> Clone for ZosditMap<I, K, V>

fn clone(&self) -> ZosditMap<I, K, V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<I: Debug, K: Debug, V: Debug> Debug for ZosditMap<I, K, V>

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

Formats the value using the given formatter.

impl<I, K, V> Default for ZosditMap<I, K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<I, K, V> IntoIterator for ZosditMap<I, K, V>

where I: PointType + 'static, K: IntervalType<I> + 'static, V: 'static,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = Box<dyn Iterator<Item = (K, V)>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<I: PartialEq, K: PartialEq, V: PartialEq> PartialEq for ZosditMap<I, K, V>

fn eq(&self, other: &ZosditMap<I, K, V>) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<I: Eq, K: Eq, V: Eq> Eq for ZosditMap<I, K, V>

impl<I, K, V> StructuralPartialEq for ZosditMap<I, K, V>