pub trait Lattice: PartialOrder {
// Required methods
fn join(&self, other: &Self) -> Self;
fn meet(&self, other: &Self) -> Self;
// Provided methods
fn join_assign(&mut self, other: &Self)
where Self: Sized { ... }
fn meet_assign(&mut self, other: &Self)
where Self: Sized { ... }
fn advance_by(&mut self, frontier: AntichainRef<'_, Self>)
where Self: Sized { ... }
}Expand description
A “lattice” is a partially ordered set in which every pair of elements has a least upper bound, called a “join”, and greatest lower bound, called a “meet”. See https://en.wikipedia.org/wiki/Lattice_(order).
DBSP uses lattices to work with Timestamps, which are only partially ordered.
Required Methods§
Sourcefn join(&self, other: &Self) -> Self
fn join(&self, other: &Self) -> Self
The smallest element greater than or equal to both arguments.
§Examples
use dbsp::{
algebra::{Lattice, PartialOrder},
time::Product,
};
let time1 = Product::new(3, 7);
let time2 = Product::new(4, 6);
let join = time1.join(&time2);
assert_eq!(join, Product::new(4, 7));Sourcefn meet(&self, other: &Self) -> Self
fn meet(&self, other: &Self) -> Self
The largest element less than or equal to both arguments.
§Examples
use dbsp::{
algebra::{Lattice, PartialOrder},
time::Product,
};
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§
Sourcefn join_assign(&mut self, other: &Self)where
Self: Sized,
fn join_assign(&mut self, other: &Self)where
Self: Sized,
Updates self to the smallest element greater than or equal to both
arguments.
§Examples
use dbsp::{
algebra::{Lattice, PartialOrder},
time::Product,
};
let mut time1 = Product::new(3, 7);
let time2 = Product::new(4, 6);
time1.join_assign(&time2);
assert_eq!(time1, Product::new(4, 7));Sourcefn meet_assign(&mut self, other: &Self)where
Self: Sized,
fn meet_assign(&mut self, other: &Self)where
Self: Sized,
Updates self to the largest element less than or equal to both
arguments.
§Examples
use dbsp::{
algebra::{Lattice, PartialOrder},
time::Product,
};
let mut time1 = Product::new(3, 7);
let time2 = Product::new(4, 6);
time1.meet_assign(&time2);
assert_eq!(time1, Product::new(3, 6));Sourcefn advance_by(&mut self, frontier: AntichainRef<'_, Self>)where
Self: Sized,
fn advance_by(&mut self, frontier: AntichainRef<'_, Self>)where
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 self is not modified.
§Examples
use dbsp::{
algebra::{Lattice, PartialOrder},
time::{Antichain, AntichainRef, Product},
};
let time = Product::new(3, 7);
let mut advanced = Product::new(3, 7);
let frontier = Antichain::from(vec![Product::new(4, 8), Product::new(5, 3)]);
advanced.advance_by(frontier.as_ref());
// `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.less_equal(&test) {
assert_eq!(time.less_equal(&test), advanced.less_equal(&test));
}
}
}
assert_eq!(advanced, Product::new(4, 7));Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.