Trait differential_dataflow::lattice::Lattice

source · 
pub trait Lattice: PartialOrder {
    fn minimum() -> Self;
    fn maximum() -> Self;
    fn join(&self, _: &Self) -> Self;
    fn meet(&self, _: &Self) -> Self;

    fn advance_by(&self, frontier: &[Self]) -> Self
    where
        Self: Sized,
    { ... }
}
Expand description

A bounded partially ordered type supporting joins and meets.

Required Methods

The smallest element of the type.

#Examples

use differential_dataflow::lattice::Lattice;

let min = <usize as Lattice>::minimum();
assert_eq!(min, usize::min_value());

The largest element of the type.

#Examples

use differential_dataflow::lattice::Lattice;

let max = <usize as Lattice>::maximum();
assert_eq!(max, usize::max_value());

The smallest element greater than or equal to both arguments.

Examples

let time1 = Product::new(3, 7);
let time2 = Product::new(4, 6);
let join = time1.join(&time2);

assert_eq!(join, Product::new(4, 7));

The largest element less than or equal to both arguments.

Examples

let time1 = Product::new(3, 7);
let time2 = Product::new(4, 6);
let meet = time1.meet(&time2);

assert_eq!(meet, Product::new(3, 6));

Provided Methods

Advances self to the largest time indistinguishable under frontier.

This method produces the “largest” lattice element with the property that for every lattice element greater than some element of frontier, both the result and self compare identically to the lattice element. The result is the “largest” element in the sense that any other element with the same property (compares identically to times greater or equal to frontier) must be less or equal to the result.

When provided an empty frontier, the result is <Self as Lattice>::maximum(). It should perhaps be distinguished by an Option<Self> type, but the None case only happens when frontier is empty, which the caller can see for themselves if they want to be clever.

Examples

let time = Product::new(3, 7);
let frontier = vec![Product::new(4, 8), Product::new(5, 3)];
let advanced = time.advance_by(&frontier[..]);

// `time` and `advanced` are indistinguishable to elements >= an element of `frontier`
for i in 0 .. 10 {
    for j in 0 .. 10 {
        let test = Product::new(i, j);
        // for `test` in the future of `frontier` ..
        if frontier.iter().any(|t| t.less_equal(&test)) {
            assert_eq!(time.less_equal(&test), advanced.less_equal(&test));
        }
    }
}

assert_eq!(advanced, Product::new(4, 7));

Implementations on Foreign Types

Implementors