Struct Inserter 

pub struct Inserter<A: BucketAccumulator> { /* private fields */ }

Item feeder for BucketAccumulators

Instances of this type allow collecting items into Buckets and committing them to a BucketAccumulator via the insert_items function.

Time complexity

A call to insert_items comes with an estimated runtime cost of O(n log(b) + a(n/b)) with n denoting the number of items to insert, b denoting the target bucket size the instance was constructed with and a(x) denoting the complexity of adding x buckets to the BucketAccumulator. Since the influence of the second term will be neglectible for sufficiently large b and all relevant implementations, the estimated runtime cost is effectifely O(n log(b)).

Bucket target size

While the above indicates that insertion is more costly with larget bucket sizes, the overall sorting performance benefits from larger buckets.

An Inserter fills Buckets up to a target bucket size. A new Inserter is initialized with a default value which is chosen to be safe in most situations, i.e. a value which is unlikely to promote exhausting or overcomitting memory. However, for better performance users of this type are encouraged to choose a target bucket size based on the availible memory and the number of Inserters involved in the target use-case.

Implementations

impl<A: BucketAccumulator> Inserter<A>

pub fn new(bucket_accumulator: A) -> Self

Create a new Inserter with a default bucket target size

Create a new Inserter for the given bucket_accumulator. Buckets committed to that BucketAccumulator will be of a size near a default bucket size.

pub fn insert_items( &mut self, items: impl IntoIterator<Item = A::Item>, ) -> Result<(), InsertionError>

Insert items into the accumulator

This function inserts the given items to the buffer. If the insertion fails due to an (re-)allocation failure, an error is returned.

Even in the event of such an error, all items consumed from the Iterator passed to this method will reside either in the underlying BucketAccumulator or the Inserters internal accumulator after the operation. Thus, callers can recover from allocation failures without any data loss by passing a mutable reference to an Iterator rather than a value, e.g. the result of Iterator::by_ref.

pub fn set_bucket_size(&mut self, size: NonZeroUsize) -> &mut Self

Set a new target bucket size

After calling this function, this inserter will commit Buckets containing near size items.

pub fn set_bucket_bytesize(&mut self, bytesize: usize) -> &mut Self

Set a new target bucket size in bytes

After calling this function, this inserter will commit Buckets near bytesize bytes in size.

pub fn bucket_size(&self) -> NonZeroUsize

Get the current target bucket size in items

pub fn bucket_bytesize(&self) -> usize

Get the current target bucket size in bytes

impl<A: BucketAccumulator<Item = Reverse<T>>, T: Ord> Inserter<A>

pub fn insert_items_reversed( &mut self, items: impl IntoIterator<Item = T>, ) -> Result<(), InsertionError>

Insert reversed items into the accumulator

This function inserts the given items to the buffer, each wrapped in a std::cmp::Reverse. If the insertion fails due to an (re-)allocation failure, an error is returned alongside an iterator over those items that were not inserted.

Trait Implementations

impl<A: Debug + BucketAccumulator> Debug for Inserter<A>

where A::Item: Debug,

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

Formats the value using the given formatter.

impl<A: BucketAccumulator> Drop for Inserter<A>

fn drop(&mut self)

Executes the destructor for this type.

impl<A: BucketAccumulator> Extend<<A as BucketAccumulator>::Item> for Inserter<A>

fn extend<I: IntoIterator<Item = A::Item>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.