Struct timely::progress::frontier::MutableAntichain
source · pub struct MutableAntichain<T> { /* private fields */ }
Expand description
An antichain based on a multiset whose elements frequencies can be updated.
The MutableAntichain
maintains frequencies for many elements of type T
, and exposes the set
of elements with positive count not greater than any other elements with positive count. The
antichain may both advance and retreat; the changes do not all need to be to elements greater or
equal to some elements of the frontier.
The type T
must implement PartialOrder
as well as Ord
. The implementation of the Ord
trait
is used to efficiently organize the updates for cancellation, and to efficiently determine the lower
bounds, and only needs to not contradict the PartialOrder
implementation (that is, if PartialOrder
orders two elements, then so does the Ord
implementation).
The MutableAntichain
implementation is done with the intent that updates to it are done in batches,
and it is acceptable to rebuild the frontier from scratch when a batch of updates change it. This means
that it can be expensive to maintain a large number of counts and change few elements near the frontier.
Implementations§
source§impl<T> MutableAntichain<T>
impl<T> MutableAntichain<T>
sourcepub fn new() -> MutableAntichain<T>
pub fn new() -> MutableAntichain<T>
Creates a new empty MutableAntichain
.
§Examples
use timely::progress::frontier::MutableAntichain;
let frontier = MutableAntichain::<usize>::new();
assert!(frontier.is_empty());
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Removes all elements.
§Examples
use timely::progress::frontier::MutableAntichain;
let mut frontier = MutableAntichain::<usize>::new();
frontier.clear();
assert!(frontier.is_empty());
sourcepub fn frontier(&self) -> AntichainRef<'_, T>
pub fn frontier(&self) -> AntichainRef<'_, T>
Reveals the minimal elements with positive count.
§Examples
use timely::progress::frontier::MutableAntichain;
let mut frontier = MutableAntichain::<usize>::new();
assert!(frontier.frontier().len() == 0);
sourcepub fn new_bottom(bottom: T) -> MutableAntichain<T>
pub fn new_bottom(bottom: T) -> MutableAntichain<T>
Creates a new singleton MutableAntichain
.
§Examples
use timely::progress::frontier::{AntichainRef, MutableAntichain};
let mut frontier = MutableAntichain::new_bottom(0u64);
assert!(frontier.frontier() == AntichainRef::new(&[0u64]));
sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Returns true if there are no elements in the MutableAntichain
.
§Examples
use timely::progress::frontier::MutableAntichain;
let mut frontier = MutableAntichain::<usize>::new();
assert!(frontier.is_empty());
sourcepub fn less_than<O>(&self, time: &O) -> boolwhere
T: PartialOrder<O>,
pub fn less_than<O>(&self, time: &O) -> boolwhere
T: PartialOrder<O>,
Returns true if any item in the MutableAntichain
is strictly less than the argument.
§Examples
use timely::progress::frontier::MutableAntichain;
let mut frontier = MutableAntichain::new_bottom(1u64);
assert!(!frontier.less_than(&0));
assert!(!frontier.less_than(&1));
assert!(frontier.less_than(&2));
sourcepub fn less_equal<O>(&self, time: &O) -> boolwhere
T: PartialOrder<O>,
pub fn less_equal<O>(&self, time: &O) -> boolwhere
T: PartialOrder<O>,
Returns true if any item in the MutableAntichain
is less than or equal to the argument.
§Examples
use timely::progress::frontier::MutableAntichain;
let mut frontier = MutableAntichain::new_bottom(1u64);
assert!(!frontier.less_equal(&0));
assert!(frontier.less_equal(&1));
assert!(frontier.less_equal(&2));
sourcepub fn update_iter<I>(&mut self, updates: I) -> Drain<'_, [(T, i64); 2]>
pub fn update_iter<I>(&mut self, updates: I) -> Drain<'_, [(T, i64); 2]>
Applies updates to the antichain and enumerates any changes.
§Examples
use timely::progress::frontier::{AntichainRef, MutableAntichain};
let mut frontier = MutableAntichain::new_bottom(1u64);
let changes =
frontier
.update_iter(vec![(1, -1), (2, 7)])
.collect::<Vec<_>>();
assert!(frontier.frontier() == AntichainRef::new(&[2]));
assert!(changes == vec![(1, -1), (2, 1)]);
Trait Implementations§
source§impl<T: Clone> Clone for MutableAntichain<T>
impl<T: Clone> Clone for MutableAntichain<T>
source§fn clone(&self) -> MutableAntichain<T>
fn clone(&self) -> MutableAntichain<T>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<T: Debug> Debug for MutableAntichain<T>
impl<T: Debug> Debug for MutableAntichain<T>
source§impl<T> Default for MutableAntichain<T>
impl<T> Default for MutableAntichain<T>
source§impl<'de, T> Deserialize<'de> for MutableAntichain<T>where
T: Deserialize<'de>,
impl<'de, T> Deserialize<'de> for MutableAntichain<T>where
T: Deserialize<'de>,
source§fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
source§impl<T: PartialOrder + Ord + Clone> From<Antichain<T>> for MutableAntichain<T>
impl<T: PartialOrder + Ord + Clone> From<Antichain<T>> for MutableAntichain<T>
source§impl<'a, T: PartialOrder + Ord + Clone> From<AntichainRef<'a, T>> for MutableAntichain<T>
impl<'a, T: PartialOrder + Ord + Clone> From<AntichainRef<'a, T>> for MutableAntichain<T>
source§fn from(antichain: AntichainRef<'a, T>) -> Self
fn from(antichain: AntichainRef<'a, T>) -> Self
source§impl<T> FromIterator<(T, i64)> for MutableAntichain<T>
impl<T> FromIterator<(T, i64)> for MutableAntichain<T>
Auto Trait Implementations§
impl<T> Freeze for MutableAntichain<T>where
T: Freeze,
impl<T> RefUnwindSafe for MutableAntichain<T>where
T: RefUnwindSafe,
impl<T> Send for MutableAntichain<T>where
T: Send,
impl<T> Sync for MutableAntichain<T>where
T: Sync,
impl<T> Unpin for MutableAntichain<T>where
T: Unpin,
impl<T> UnwindSafe for MutableAntichain<T>where
T: UnwindSafe + RefUnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)