Struct MergingIter 

pub struct MergingIter<Key: ?Sized, Cmp, Iter> { /* private fields */ }

Available on crate feature alloc only.

A MergingIter takes several SeekableLendingIterators as input, and iterates over the sorted union of their entries.

The given iterators may have overlap in their keys, and can be provided in any order.

Conceptually, each SeekableLendingIterator is a circular iterator over the entries of some sorted collection; this also holds of MergingIter. The collection corresponding to a MergingIter is the sorted union (without de-duplication) of its given iterators’ collections. However, note that the presence of duplicate keys across different iterators can cause unexpected behavior in certain well-defined scenarios (see below). Ideally, the iterators that are merged should not have duplicate keys.

Note on backwards iteration

Some SeekableLendingIterator implementations have better performance for forwards iteration than backwards iteration. MergingIter itself otherwise has roughly equal performance in either direction, but has overhead for switching the direction of iteration (see below for more information). Moreover, switching direction does not play well with duplicate keys. Therefore, MergingIter::prev, MergingIter::seek_before, and MergingIter::seek_to_last (the three methods that use backwards iteration) should be avoided if possible.

Warning for duplicate keys

If a key is present in multiple iterators, then repeatedly calling next or repeatedly calling prev will yield all items with that key. That is, as expected, iterating through the entire collection associated with a MergingIter is possible, and can be done in either the forwards or backwards direction.

However, switching between next and prev will return at least one but not necessarily all of the items with the key returned by MergingIter::current at the time of the switch in direction.

To be precise, the items with duplicate keys may be skipped whenever the MergingIter changes which “direction” (forwards or backwards) that it is iterating in. When switching direction, some of the items whose keys compare equal to MergingIter::current may be skipped over.

The following methods need to switch direction if necessary, and iterate in a certain direction:

• Forwards:
  • MergingIter::next
• Backwards:
  • MergingIter::prev

The following methods are not impacted by the direction, but set the direction:

• Set direction to forwards:
  • MergingIter::new
  • MergingIter::reset
  • MergingIter::seek
  • MergingIter::seek_to_first
• Set direction to backwards:
  • MergingIter::seek_before
  • MergingIter::seek_to_last

The following methods do not impact and are not impacted by the direction:

• MergingIter::valid
• MergingIter::current

Time Complexity

MergingIter::new takes O(n) time and O(1) space, where n is iterators.len(). Switching direction, seeking, or resetting takes O(n) time. MergingIter::valid and MergingIter::current are O(1). Currently, MergingIter::next and MergingIter::prev take O(n) time even if they do not switch direction; soon, they will be O(log n) unless switching direction, in exchange for MergingIter::new taking O(n) space.

Implementations

impl<Key, Cmp, Iter> MergingIter<Key, Cmp, Iter>

where Key: ?Sized, Cmp: Comparator<Key>, Iter: SeekableLendingIterator<Key, Cmp> + ItemToKey<Key>,

pub fn new(iterators: Vec<Iter>, cmp: Cmp) -> Self

Create a new MergingIter. See the type-level documentation for details on behavior.

Comparator requirements

The Comparators used by each of the provided iterators must all behave identically to each other and to the provided cmp value. In particular, this requirement is met if the Cmp generic is a ZST, or if all the comparators were cloned from some common source.

Panics

Panics if the length of iterators is usize::MAX. Any other number of iterators can, theoretically, be merged.

Trait Implementations

impl<Key, Cmp, Iter> CursorLendingIterator for MergingIter<Key, Cmp, Iter>

where Key: ?Sized, Cmp: Comparator<Key>, Iter: SeekableLendingIterator<Key, Cmp> + ItemToKey<Key>,

fn prev(&mut self) -> Option<LentItem<'_, Self>>

Move the iterator one position back, and return the entry at that position. Returns None if the iterator was at the first entry.

The inner Iter iterators may have worse performance for backwards iteration than forwards iteration, so prefer to not use prev. Additionally, MergingIter has overhead for switching between backwards and forwards iteration; check the type-level documentation if you wish to use prev.

fn valid(&self) -> bool

Determine whether the iterator is currently at any value in the collection. If the iterator is invalid, then it is conceptually one position before the first entry and one position after the last entry. (Or, there may be no entries.)

fn next(&mut self) -> Option<LentItem<'_, Self>>

Move the iterator one position forwards, and return the entry at that position. Returns None if the iterator was at the last entry.

fn current(&self) -> Option<LentItem<'_, Self>>

Get the current value the iterator is at, if the iterator is valid.

fn into_lender(self) -> LenderAdapter<Self>

where Self: Sized,

Available on crate feature lender only.

Convert the CursorLendingIterator into a lender::Lender lending iterator.

fn into_lending_iterator(self) -> LendingIteratorAdapter<Self>

where Self: Sized,

Available on crate feature lending-iterator only.

Convert the CursorLendingIterator into a lending_iterator::LendingIterator.

impl<Key: Debug + ?Sized, Cmp: Debug, Iter: Debug> Debug for MergingIter<Key, Cmp, Iter>

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

Formats the value using the given formatter.

impl<Key, Cmp, Iter> ItemToKey<Key> for MergingIter<Key, Cmp, Iter>

where Key: ?Sized, Iter: ItemToKey<Key>,

fn item_to_key(item: LentItem<'_, Self>) -> &Key

Convert one of the items of an iterator into a Key reference, intended for use with a SeekableLendingIterator.

impl<'lend, Key, Cmp, Iter> LendItem<'lend> for MergingIter<Key, Cmp, Iter>

where Key: ?Sized, Iter: LendItem<'lend>,

type Item = <Iter as LendItem<'lend>>::Item

The item of a lending iterator, with a particular lifetime.

impl<Key, Cmp, Iter> Seekable<Key, Cmp> for MergingIter<Key, Cmp, Iter>

where Key: ?Sized, Cmp: Comparator<Key>, Iter: SeekableLendingIterator<Key, Cmp> + ItemToKey<Key>,

fn seek_before(&mut self, strict_upper_bound: &Key)

Move the iterator to the greatest key which is strictly less than the provided strict_upper_bound.

If there is no such key, the iterator becomes !valid(), and is conceptually one position before the first entry and one position after the last entry (if there are any entries in the collection).

The inner Iter iterators may have worse performance for seek_before than seek. Additionally, MergingIter has overhead for switching between backwards and forwards iteration; check the type-level documentation if you wish to use seek_before.

fn seek_to_last(&mut self)

Move the iterator to the greatest key in the collection.

If the collection is empty, the iterator is !valid().

MergingIter has overhead for switching between backwards and forwards iteration; check the type-level documentation if you wish to use seek_before.

fn reset(&mut self)

Reset the iterator to its initial position, before the first entry and after the last entry (if there are any entries in the collection).

fn seek(&mut self, min_bound: &Key)

Move the iterator to the smallest key which is greater or equal than the provided min_bound.

fn seek_to_first(&mut self)

Move the iterator to the smallest key in the collection.