Trait strata::Algebra

pub trait Algebra {
    fn tau(&self, k: Position) -> Extent;
    fn tau_prime(&self, k: Position) -> Extent;
    fn rho(&self, k: Position) -> Extent;
    fn rho_prime(&self, k: Position) -> Extent;

    fn iter_tau(self) -> IterTau<Self>
    where
        Self: Sized,
    { ... }
    fn iter_rho(self) -> IterRho<Self>
    where
        Self: Sized,
    { ... }
    fn iter_tau_prime(self) -> IterTauPrime<Self>
    where
        Self: Sized,
    { ... }
    fn iter_rho_prime(self) -> IterRhoPrime<Self>
    where
        Self: Sized,
    { ... }
}

The basic query algebra from the Clarke et al. paper

Iterators

Iterators are provided that return the entire result set in the positive direction (tau, rho) and the negative direction (tau-prime, rho-prime). Both forward iterators and both backwards iterators return the same extents, and the forwards and backwards iterators return the same extents in reverse order from each other. All 4 iterators are provided for completeness.

tau-prime and rho-prime

The paper does not give a concrete example of how to construct the *_prime functions, simply stating

The access functions τ′ and ρ′ are the converses of τ and ρ.

Through trial and error, I've determined that there are 4 concrete steps to transform between prime and non-prime implementations:

1. Swap usages of {tau,rho} with {tau-prime,rho-prime}
2. Swap the sign of epsilon
3. Swap the usages of p and q
4. Swap comparison operators

Required methods

fn tau(&self, k: Position) -> Extent

The first extent starting at or after the position k.

fn tau_prime(&self, k: Position) -> Extent

The last extent ending at or before the position k.

This is akin to running tau from the other end of the number line. We are interested in the first number we arrive at (the end of the extent). We take the first extent that passes the criteria (the last extent in order).

fn rho(&self, k: Position) -> Extent

The first extent ending at or after the position k.

fn rho_prime(&self, k: Position) -> Extent

The last extent starting at or before the position k.

This is akin to running rho from the other end of the number line. We are interested in the second number we arrive at (the start of the extent). We take the first extent that passes the criteria (the last extent in order).

Loading content...

Provided methods

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Find all extents in a forward direction using the tau primitive

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Find all extents in a forward direction using the rho primitive

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Find all extents in a backward direction using the tau-prime primitive

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

Find all extents in a backward direction using the rho-prime primitive

Loading content...

Implementations on Foreign Types

impl<'a, A: ?Sized> Algebra for Box<A> where
    A: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl<'a, A: ?Sized> Algebra for &'a A where
    A: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl Algebra for [ValidExtent]

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

Loading content...

Implementors

impl Algebra for Documents

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl Algebra for Empty

fn tau(&self, _: Position) -> Extent

fn tau_prime(&self, _: Position) -> Extent

fn rho(&self, _: Position) -> Extent

fn rho_prime(&self, _: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl<A, B> Algebra for BothOf<A, B> where
    A: Algebra,
    B: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl<A, B> Algebra for ContainedIn<A, B> where
    A: Algebra,
    B: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl<A, B> Algebra for Containing<A, B> where
    A: Algebra,
    B: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl<A, B> Algebra for FollowedBy<A, B> where
    A: Algebra,
    B: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl<A, B> Algebra for NotContainedIn<A, B> where
    A: Algebra,
    B: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl<A, B> Algebra for NotContaining<A, B> where
    A: Algebra,
    B: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

impl<A, B> Algebra for OneOf<A, B> where
    A: Algebra,
    B: Algebra, 

fn tau(&self, k: Position) -> Extent

fn tau_prime(&self, k: Position) -> Extent

fn rho(&self, k: Position) -> Extent

fn rho_prime(&self, k: Position) -> Extent

Important traits for IterTau<T>

impl<T> Iterator for IterTau<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau(self) -> IterTau<Self> where
    Self: Sized, 

Important traits for IterRho<T>

impl<T> Iterator for IterRho<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho(self) -> IterRho<Self> where
    Self: Sized, 

Important traits for IterTauPrime<T>

impl<T> Iterator for IterTauPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_tau_prime(self) -> IterTauPrime<Self> where
    Self: Sized, 

Important traits for IterRhoPrime<T>

impl<T> Iterator for IterRhoPrime<T> where
    T: Algebra,  type Item = ValidExtent;

fn iter_rho_prime(self) -> IterRhoPrime<Self> where
    Self: Sized, 

Loading content...