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>

source

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());
source

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());
source

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);
source

pub fn new_bottom(bottom: T) -> MutableAntichain<T>
where T: Ord + Clone,

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]));
source

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());
source

pub fn less_than(&self, time: &T) -> bool
where T: PartialOrder,

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));
source

pub fn less_equal(&self, time: &T) -> bool
where T: PartialOrder,

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));
source

pub fn update_iter<I>(&mut self, updates: I) -> Drain<'_, (T, i64)>
where T: Clone + PartialOrder + Ord, I: IntoIterator<Item = (T, i64)>,

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)]);
source

pub fn count_for(&self, query_time: &T) -> i64
where T: Ord,

Reports the count for a queried time.

source

pub fn updates(&mut self) -> impl Iterator<Item = &(T, i64)>
where T: Clone + PartialOrder + Ord,

Reports the updates that form the frontier. Returns an iterator of timestamps and their frequency.

Rebuilds the internal representation before revealing times and frequencies.

Trait Implementations§

source§

impl<T> Abomonation for MutableAntichain<T>

source§

unsafe fn entomb<W: Write>(&self, _write: &mut W) -> Result<()>

Write any additional information about &self beyond its binary representation. Read more
source§

fn extent(&self) -> usize

Reports the number of further bytes required to entomb self.
source§

unsafe fn exhume<'a, 'b>( &'a mut self, bytes: &'b mut [u8] ) -> Option<&'b mut [u8]>

Recover any information for &mut self not evident from its binary representation. Read more
source§

impl<T: Clone> Clone for MutableAntichain<T>

source§

fn clone(&self) -> MutableAntichain<T>

Returns a copy of the value. Read more
1.0.0 · source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
source§

impl<T: Debug> Debug for MutableAntichain<T>

source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
source§

impl<T> Default for MutableAntichain<T>

source§

fn default() -> Self

Returns the “default value” for a type. Read more
source§

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>,

Deserialize this value from the given Serde deserializer. Read more
source§

impl<T: PartialOrder + Ord + Clone> From<Antichain<T>> for MutableAntichain<T>

source§

fn from(antichain: Antichain<T>) -> Self

Converts to this type from the input type.
source§

impl<'a, T: PartialOrder + Ord + Clone> From<AntichainRef<'a, T>> for MutableAntichain<T>

source§

fn from(antichain: AntichainRef<'a, T>) -> Self

Converts to this type from the input type.
source§

impl<T> FromIterator<(T, i64)> for MutableAntichain<T>
where T: Clone + PartialOrder + Ord,

source§

fn from_iter<I>(iterator: I) -> Self
where I: IntoIterator<Item = (T, i64)>,

Creates a value from an iterator. Read more
source§

impl<T> Serialize for MutableAntichain<T>
where T: Serialize,

source§

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>
where __S: Serializer,

Serialize this value into the given Serde serializer. Read more

Auto Trait Implementations§

§

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,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ProgressEventTimestamp for T
where T: Data + Debug + Any,

source§

fn as_any(&self) -> &(dyn Any + 'static)

Upcasts this ProgressEventTimestamp to Any. Read more
source§

fn type_name(&self) -> &'static str

Returns the name of the concrete type of this object. Read more
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<T> Data for T
where T: Clone + 'static,

source§

impl<T> Data for T
where T: Send + Sync + Any + Serialize + for<'a> Deserialize<'a> + 'static,

source§

impl<T> DeserializeOwned for T
where T: for<'de> Deserialize<'de>,

source§

impl<T> ExchangeData for T
where T: Data + Data,