Struct nodit::gqdit::Gqdit

pub struct Gqdit<I, K, D> { /* private fields */ }

The Gqdit is a Gap Query Discrete Interval Tree, it is designed for the storage of multiple sets of discrete non-overlapping intervalts with each set assigned a unique identifier. Then once this data-structure is created it can be gap-queried to find gaps between all the sets efficiently. Optionally, you can also search for gaps with an identifier which sort of ignores any intervals associated with that identifier when doing the gap-search which is often useful.

Importantly, overlapping is allowed between different identifiers’ intervals but not within the intervals of the same identifier.

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 in the data-structure.

D is the generic type parameter for the identifiers associated with the interval sets in the data-structure.

Phrasing it another way: I is the point type, K is the interval type, and D is the identifier type.

Developed for the paper (includes more in depth description of how this data-structure is implemented):

Guaranteed, Predictable, Polynomial AGV Time-Pathing
James Forster
October 2023
https://doi.org/10.48550/arXiv.2310.12006
https://arxiv.org/abs/2310.12006

Examples

use std::collections::BTreeSet;

use nodit::interval::{ii, iu};
use nodit::Gqdit;

let mut map = Gqdit::new();

map.insert(BTreeSet::from([0_u8]), ii(0, 4));
map.insert(BTreeSet::from([2_u8]), ii(2, 6));
map.insert(BTreeSet::from([4_u8]), ii(10, 40));

assert_eq!(
	map.gaps_no_identifier(ii(0, 100)),
	[ii(7, 9), iu(41)]
);

Implementations

impl<I, K, D> Gqdit<I, K, D>

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

pub fn new() -> Self

Makes a new, empty Gqdit.

Examples

use nodit::{Gqdit, Interval};

let map: Gqdit<i8, Interval<i8>, u8> = Gqdit::new();

pub fn gaps_no_identifier<Q>(&self, interval: Q) -> Vec<K>

where Q: IntervalType<I>,

Returns a Vec of intervals which are equivalent to those found by finding the gaps in the discrete interval tree formed by the intersection of all the intervals associated with every identifier inside the structure except the given identifier whose intervals are ignored.

See Gqdit::gaps_no_identifier to not ignore any identifiers.

Panics

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

Examples

use std::collections::BTreeSet;

use nodit::interval::{ii, iu};
use nodit::Gqdit;

let mut map = Gqdit::new();

map.insert(BTreeSet::from([0_u8]), ii(0, 4));
map.insert(BTreeSet::from([2_u8]), ii(2, 6));
map.insert(BTreeSet::from([4_u8]), ii(10, 40));

assert_eq!(
	map.gaps_no_identifier(ii(0, 100)),
	[ii(7, 9), iu(41)]
);

pub fn gaps_with_identifier<Q>(&self, identifier: D, interval: Q) -> Vec<K>

where Q: IntervalType<I>,

Returns a Vec of intervals which are equivalent to those found by finding the gaps in the discrete interval tree formed by the intersection of all the intervals associated with every identifier inside the structure.

See Gqdit::gaps_with_identifier to ignore intervals from a specific identifier.

Panics

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

Examples

use std::collections::BTreeSet;

use nodit::interval::{ii, iu};
use nodit::Gqdit;

let mut map = Gqdit::new();

map.insert(BTreeSet::from([0_u8]), ii(0, 4));
map.insert(BTreeSet::from([2_u8]), ii(2, 6));
map.insert(BTreeSet::from([4_u8]), ii(10, 40));

assert_eq!(
	map.gaps_with_identifier(2_u8, ii(0, 100)),
	[ii(5, 9), iu(41)]
);

pub fn cut_with_identifiers<Q>(&mut self, identifiers: BTreeSet<D>, interval: Q)

where Q: IntervalType<I>,

Cuts the given interval out of all the interval sets associated with the given identifiers.

Cutting an interval with no identifiers is a no-op.

Examples

use std::collections::BTreeSet;

use nodit::interval::{ii, iu};
use nodit::Gqdit;

let mut map = Gqdit::new();

map.insert(BTreeSet::from([0_u8]), ii(0, 4));
map.insert(BTreeSet::from([2_u8]), ii(2, 6));
map.insert(BTreeSet::from([4_u8]), ii(10, 40));

map.cut_with_identifiers(BTreeSet::from([2, 4]), ii(0, 20));

assert_eq!(
	map.gaps_no_identifier(ii(0, 100)),
	[ii(5, 20), iu(41)]
);

Panics

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

pub fn cut_all_identifiers<Q>(&mut self, interval: Q)

where Q: IntervalType<I>,

Cuts the given interval out of all interval sets in the structure.

Examples

use std::collections::BTreeSet;

use nodit::interval::{ii, iu};
use nodit::Gqdit;

let mut map = Gqdit::new();

map.insert(BTreeSet::from([0_u8]), ii(0_u8, 4));
map.insert(BTreeSet::from([2_u8]), ii(2, 6));
map.insert(BTreeSet::from([4_u8]), ii(10, 40));

map.cut_all_identifiers(ii(0, 20));

assert_eq!(
	map.gaps_no_identifier(ii(0, 100)),
	[ii(0, 20), iu(41)]
);

Panics

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

pub fn insert(&mut self, identifiers: BTreeSet<D>, interval: K)

Inserts an interval into the structure assigned to the given identifiers.

How overlapping/touching intervals of the same specifier are stored internally is unspecified since only the gaps are able to be queried and regardless of how they are stored the gaps will be the same.

Inserting an interval with no identifiers is a no-op.

Panics

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

Examples

use std::collections::BTreeSet;

use nodit::interval::ii;
use nodit::Gqdit;

let mut map = Gqdit::new();

map.insert(BTreeSet::from([0_u8]), ii(0, 4));

pub fn append(&mut self, other: &mut Self)

Appends all the intervals from other to self.

Examples

use std::collections::BTreeSet;

use nodit::interval::ii;
use nodit::Gqdit;

let mut map = Gqdit::new();
map.insert(BTreeSet::from([0_u8]), ii(0, 4));

let mut other = Gqdit::new();
other.insert(BTreeSet::from([0_u8]), ii(6, 10));

map.append(&mut other);

assert_eq!(map.gaps_no_identifier(ii(0, 10)), [ii(5, 5)]);

pub fn identifiers_at_point(&self, point: I) -> BTreeSet<D>

Return all the identifiers with intervals overlapping the given point.

Examples

use std::collections::BTreeSet;

use nodit::interval::ii;
use nodit::Gqdit;

let mut map = Gqdit::new();
map.insert(BTreeSet::from([0_u8]), ii(2, 6));
map.insert(BTreeSet::from([1_u8]), ii(4, 8));

assert_eq!(map.identifiers_at_point(0), BTreeSet::from([]));
assert_eq!(map.identifiers_at_point(2), BTreeSet::from([0]));
assert_eq!(map.identifiers_at_point(5), BTreeSet::from([0, 1]));
assert_eq!(map.identifiers_at_point(8), BTreeSet::from([1]));
assert_eq!(map.identifiers_at_point(10), BTreeSet::from([]));

Trait Implementations

impl<I: Clone, K: Clone, D: Clone> Clone for Gqdit<I, K, D>

fn clone(&self) -> Gqdit<I, K, D>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<I: Debug, K: Debug, D: Debug> Debug for Gqdit<I, K, D>

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

Formats the value using the given formatter.

impl<I, K, D> Default for Gqdit<I, K, D>

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

fn default() -> Self

Returns the “default value” for a type.

impl<I, K, D> PartialEq for Gqdit<I, K, D>

where I: PartialEq, K: PartialEq, BTreeSet<D>: PartialEq,

fn eq(&self, other: &Self) -> 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.