Struct BubbleSortIter 

pub struct BubbleSortIter<'a, T> { /* private fields */ }

The states a bubble sort of a permutation passes through, one adjacent swap at a time: cursor 0 is the permutation itself and cursor Self::swap_distance is sorted order.

No swap is recorded. A state is rebuilt from the permutation’s inversion table, which counts the larger values before each value. A bubble sort pass moves every value that has a larger one before it one place left, past exactly one larger value, so it lowers each nonzero entry of the table by one (Knuth, The Art of Computer Programming, Vol. 3, section 5.2.2). The state after k swaps is therefore the permutation whose table is the original one less the passes those swaps complete, followed by the first swaps of the next pass. That keeps memory linear in the permutation and costs O(n log n) per move, where a record of every swap grows with the square of its length: two schedules of a few million events can be trillions of swaps apart.

Implementations

impl<'a, T> BubbleSortIter<'a, T>

where T: Hash + Eq,

pub fn edit_distance(&self) -> usize

Get the edit distance between the source and target slices. This is different from the swap distance because any elements that appear in one slice, but not the other will not contribute to the swap distance

pub fn swap_distance(&self) -> usize

Number of swaps take to permute the source slice into the target slice when values not accounting for items that appear in one slice, but not the other

pub fn next<'b>(&'b mut self) -> Option<Perm<'a, 'b, T>>

The state one swap further toward sorted order. Each step rebuilds the state, in O(n log n), as every move does.

pub fn skip(&mut self, distance: usize)

pub fn next_back<'b>(&'b mut self) -> Option<Perm<'a, 'b, T>>

The state one swap back toward the permutation, in O(n log n).

pub fn skip_back(&mut self, distance: usize)

pub fn current<'b>(&'b self) -> Perm<'a, 'b, T>

pub fn midpoint<'b>(&'b mut self) -> Perm<'a, 'b, T>

pub fn interpolate<'b>( &'b mut self, interpolate_percentage: u8, ) -> Perm<'a, 'b, T>

pub fn history_size(&self) -> usize