Trait binary_merge::MergeOperation[−][src]

pub trait MergeOperation<M: MergeState> {
    const MCM_THRESHOLD: usize;

    fn from_a(&self, m: &mut M, n: usize) -> bool;

    fn from_b(&self, m: &mut M, n: usize) -> bool;

    fn collision(&self, m: &mut M) -> bool;

    fn cmp(&self, a: &M::A, b: &M::B) -> Ordering;

    fn binary_merge(&self, m: &mut M, an: usize, bn: usize) -> bool { ... }

    fn tape_merge(&self, m: &mut M) -> bool { ... }

    fn merge(&self, m: &mut M) -> bool { ... }
}
Expand description

A binary merge operation

It is often useful to keep the merge operation and the merge state separate. E.g. computing the intersection and checking if the intersection exists can be done with the same operation, but a different merge state. Likewise in-place operations and operations that produce a new entity can use the same merge operation. THerefore, the merge state is an additional parameter.SortedPairIter

The operation itself will often be a zero size struct

Associated Constants

Threshold above which we use the minimum comparison merge

For very small collections, the tape merge has a similar number of comparisons and requires less state.

Also, if the comparison operation is very cheap, the minimum comparison merge does not have big advantages.

Set this to 0 to always do minimum comparison merge. Set it to usize::max to always do tape merge.

Required methods

Take n elements from a, return true to continue operation

Take n elements from b, return true to continue operation

Take 1 element from both a and b, return true to continue operation

The comparison operation

Provided methods

merge an elements from a and bn elements from b into the result

This is a minimum comparison merge that has some overhead, so it is only worth it for larger collections and if the comparison operation is expensive.

It does make a big difference e.g. when merging a very large and a very small sequence, or two disjoint sequences.

returns false if the operation was prematurely aborted

This is the classical tape merge algorithm, useful for when either the number of elements is small or the comparison operation is very cheap.

Implementors