Struct timely::progress::change_batch::ChangeBatch

pub struct ChangeBatch<T> { /* fields omitted */ }

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.

Methods

impl<T: Ord> ChangeBatch<T>

pub fn new() -> ChangeBatch<T>

Allocates a new empty ChangeBatch.

#Examples

use timely::progress::ChangeBatch;

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

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

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

Important traits for Vec<u8>

impl Write for Vec<u8>

pub fn into_inner(self) -> Vec<(T, i64)>

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(), vec![(17, 1)]);

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;

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

Important traits for Drain<'a, T>

impl<'a, T> Iterator for Drain<'a, T> type Item = T;

pub fn drain(&mut self) -> Drain<(T, i64)>

Drains the set of updates.

This operation first compacts the set of updates so that the drained results have at most one occurence 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 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());

pub fn is_empty(&mut self) -> bool

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 canonicalize(&mut self)

Compact and sort data, so that two instances can be compared without false negatives.

pub fn drain_into(&mut self, other: &mut ChangeBatch<T>) 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());

Trait Implementations

impl<T: Clone> Clone for ChangeBatch<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for ChangeBatch<T>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: Eq> Eq for ChangeBatch<T>

impl<T: PartialEq> PartialEq for ChangeBatch<T>

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

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, __arg_0: &ChangeBatch<T>) -> bool

This method tests for !=.