Struct timely::progress::change_batch::ChangeBatch

pub struct ChangeBatch<T, const X: usize = 2> { /* private fields */ }

A collection of updates of the form (T, i64).

A ChangeBatch accumulates updates of the form (T, i64), where it is capable of consolidating the representation and removing elements whose i64 field accumulates to zero.

The implementation is designed to be as lazy as possible, simply appending to a list of updates until they are required. This means that several seemingly simple operations may be expensive, in that they may provoke a compaction. I’ve tried to prevent exposing methods that allow surprisingly expensive operations; all operations should take an amortized constant or logarithmic time.

Implementations

impl<T, const X: usize> ChangeBatch<T, X>

pub fn new() -> Self

Allocates a new empty ChangeBatch.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new();
 assert!(batch.is_empty());

pub fn with_capacity(capacity: usize) -> Self

Allocates a new empty ChangeBatch with space for capacity updates.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::with_capacity(10);
 assert!(batch.is_empty());

pub fn is_dirty(&self) -> bool

Returns true if the change batch is not guaranteed compact.

pub fn unstable_internal_updates(&self) -> &SmallVec<[(T, i64); X]>

Expose the internal vector of updates.

pub fn unstable_internal_clean(&self) -> usize

Expose the internal value of clean.

pub fn clear(&mut self)

Clears the map.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new_from(17, 1);
 batch.clear();
 assert!(batch.is_empty());

impl<T, const X: usize> ChangeBatch<T, X>

where T: Ord,

pub fn new_from(key: T, val: i64) -> Self

Allocates a new ChangeBatch with a single entry.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new_from(17, 1);
 assert!(!batch.is_empty());

pub fn update(&mut self, item: T, value: i64)

Adds a new update, for item with value.

This could be optimized to perform compaction when the number of “dirty” elements exceeds half the length of the list, which would keep the total footprint within reasonable bounds even under an arbitrary number of updates. This has a cost, and it isn’t clear whether it is worth paying without some experimentation.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new();
 batch.update(17, 1);
 assert!(!batch.is_empty());

pub fn extend<I: Iterator<Item = (T, i64)>>(&mut self, iterator: I)

Performs a sequence of updates described by iterator.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new_from(17, 1);
 batch.extend(vec![(17, -1)].into_iter());
 assert!(batch.is_empty());

pub fn into_inner(self) -> SmallVec<[(T, i64); X]>

Extracts the Vec<(T, i64)> from the map, consuming it.

Examples

 use timely::progress::ChangeBatch;

 let batch = ChangeBatch::<usize>::new_from(17, 1);
 assert_eq!(batch.into_inner().to_vec(), vec![(17, 1)]);

pub fn iter(&mut self) -> Iter<'_, (T, i64)>

Iterates over the contents of the map.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new_from(17, 1);
 {   // scope allows borrow of `batch` to drop.
     let mut iter = batch.iter();
     assert_eq!(iter.next(), Some(&(17, 1)));
     assert_eq!(iter.next(), None);
 }
 assert!(!batch.is_empty());

pub fn drain(&mut self) -> Drain<'_, [(T, i64); X]>

Drains the set of updates.

This operation first compacts the set of updates so that the drained results have at most one occurrence of each item.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new_from(17, 1);
 {   // scope allows borrow of `batch` to drop.
     let mut iter = batch.drain();
     assert_eq!(iter.next(), Some((17, 1)));
     assert_eq!(iter.next(), None);
 }
 assert!(batch.is_empty());

pub fn is_empty(&mut self) -> bool

Returns true iff all keys have value zero.

This method requires mutable access to self because it may need to compact the representation to determine if the batch of updates is indeed empty. We could also implement a weaker form of is_empty which just checks the length of self.updates, and which could confirm the absence of any updates, but could report false negatives if there are updates which would cancel.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new_from(17, 1);
 batch.update(17, -1);
 assert!(batch.is_empty());

pub fn len(&mut self) -> usize

Number of compacted updates.

This method requires mutable access to self because it may need to compact the representation to determine the number of actual updates.

Examples

 use timely::progress::ChangeBatch;

 let mut batch = ChangeBatch::<usize>::new_from(17, 1);
 batch.update(17, -1);
 batch.update(14, -1);
 assert_eq!(batch.len(), 1);

pub fn drain_into(&mut self, other: &mut ChangeBatch<T, X>)

where T: Clone,

Drains self into other.

This method has similar a effect to calling other.extend(self.drain()), but has the opportunity to optimize this to a ::std::mem::swap(self, other) when other is empty. As many uses of this method are to propagate updates, this optimization can be quite handy.

Examples

 use timely::progress::ChangeBatch;

 let mut batch1 = ChangeBatch::<usize>::new_from(17, 1);
 let mut batch2 = ChangeBatch::new();
 batch1.drain_into(&mut batch2);
 assert!(batch1.is_empty());
 assert!(!batch2.is_empty());

pub fn compact(&mut self)

Compact the internal representation.

This method sort self.updates and consolidates elements with equal item, discarding any whose accumulation is zero. It is optimized to only do this if the number of dirty elements is non-zero.

Trait Implementations

impl<T: Clone, const X: usize> Clone for ChangeBatch<T, X>

fn clone(&self) -> ChangeBatch<T, X>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, const X: usize> Debug for ChangeBatch<T, X>

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

Formats the value using the given formatter.

impl<T, const X: usize> Default for ChangeBatch<T, X>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, T, const X: usize> Deserialize<'de> for ChangeBatch<T, X>

where T: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T: PartialEq, const X: usize> PartialEq for ChangeBatch<T, X>

fn eq(&self, other: &ChangeBatch<T, X>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, const X: usize> Serialize for ChangeBatch<T, X>

where T: Serialize,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<T: Eq, const X: usize> Eq for ChangeBatch<T, X>

impl<T, const X: usize> StructuralPartialEq for ChangeBatch<T, X>