use timely::order::PartialOrder;
use timely::progress::{Antichain, frontier::AntichainRef};
pub trait Lattice : PartialOrder {
fn join(&self, &Self) -> Self;
fn join_assign(&mut self, other: &Self) where Self: Sized {
*self = self.join(other);
}
fn meet(&self, &Self) -> Self;
fn meet_assign(&mut self, other: &Self) where Self: Sized {
*self = self.meet(other);
}
#[inline]
fn advance_by(&mut self, frontier: AntichainRef<Self>) where Self: Sized {
let mut iter = frontier.iter();
if let Some(first) = iter.next() {
let mut result = self.join(first);
for f in iter {
result.meet_assign(&self.join(f));
}
*self = result;
}
}
}
use timely::order::Product;
impl<T1: Lattice, T2: Lattice> Lattice for Product<T1, T2> {
#[inline]
fn join(&self, other: &Product<T1, T2>) -> Product<T1, T2> {
Product {
outer: self.outer.join(&other.outer),
inner: self.inner.join(&other.inner),
}
}
#[inline]
fn meet(&self, other: &Product<T1, T2>) -> Product<T1, T2> {
Product {
outer: self.outer.meet(&other.outer),
inner: self.inner.meet(&other.inner),
}
}
}
macro_rules! implement_lattice {
($index_type:ty, $minimum:expr) => (
impl Lattice for $index_type {
#[inline] fn join(&self, other: &Self) -> Self { ::std::cmp::max(*self, *other) }
#[inline] fn meet(&self, other: &Self) -> Self { ::std::cmp::min(*self, *other) }
}
)
}
use std::time::Duration;
implement_lattice!(Duration, Duration::new(0, 0));
implement_lattice!(usize, 0);
implement_lattice!(u128, 0);
implement_lattice!(u64, 0);
implement_lattice!(u32, 0);
implement_lattice!(u16, 0);
implement_lattice!(u8, 0);
implement_lattice!(isize, 0);
implement_lattice!(i128, 0);
implement_lattice!(i64, 0);
implement_lattice!(i32, 0);
implement_lattice!(i16, 0);
implement_lattice!(i8, 0);
implement_lattice!((), ());
pub fn antichain_join<T: Lattice>(one: &[T], other: &[T]) -> Antichain<T> {
let mut upper = Antichain::new();
for time1 in one {
for time2 in other {
upper.insert(time1.join(time2));
}
}
upper
}
pub fn antichain_meet<T: Lattice+Clone>(one: &[T], other: &[T]) -> Antichain<T> {
let mut upper = Antichain::new();
for time1 in one {
upper.insert(time1.clone());
}
for time2 in other {
upper.insert(time2.clone());
}
upper
}
impl<T: Lattice+Clone> Lattice for Antichain<T> {
fn join(&self, other: &Self) -> Self {
let mut upper = Antichain::new();
for time1 in self.elements().iter() {
for time2 in other.elements().iter() {
upper.insert(time1.join(time2));
}
}
upper
}
fn meet(&self, other: &Self) -> Self {
let mut upper = Antichain::new();
for time1 in self.elements().iter() {
upper.insert(time1.clone());
}
for time2 in other.elements().iter() {
upper.insert(time2.clone());
}
upper
}
}