Trait differential_dataflow::lattice::Lattice
[−]
[src]
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, { ... } }
A bounded partially ordered type supporting joins and meets.
Required Methods
fn minimum() -> Self
The smallest element of the type.
#Examples
use differential_dataflow::lattice::Lattice; let min = <usize as Lattice>::minimum(); assert_eq!(min, usize::min_value());
fn maximum() -> Self
The largest element of the type.
#Examples
use differential_dataflow::lattice::Lattice; let max = <usize as Lattice>::maximum(); assert_eq!(max, usize::max_value());
fn join(&self, _: &Self) -> Self
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));
fn meet(&self, _: &Self) -> Self
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
fn advance_by(&self, frontier: &[Self]) -> Self where
Self: Sized,
Self: Sized,
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));