Is it possible to implement an iter for slices that could perform bubble-sort?

In some algorithm, we may want to index a single vector twice (e.g., bubble-sort)

for i in 0..vec.len() {
    for j in 0..i {
        if vec[i]>vec[j] {
            vec.swap(i,j)
        }
    }
}

is it possible to provide some api that could index the same vector twice or even more?

 // yields [&slice[i],&slice[j],&slice[k],...] where i<j<k<...
fn iter_ascend<T,const N:usize>(&[T])->impl Iterator<Item=[&T;N]> {...}
fn iter_ascend_mut<T,const N:usize>(&mut [T])->impl Iterator<Item=[&mut T;N]> {...}
 // yields [&slice[i],&slice[j],&slice[k],...] where i>j>k>...
fn iter_descend<T,const N:usize>(&[T])->impl Iterator<Item=[&T;N]> {...}
fn iter_descend_mut<T,const N:usize>(&mut [T])->impl Iterator<Item=[&mut T;N]> {...}
 // yields [&slice[i],&slice[j],&slice[k],...] for all valid i,j,k,...
fn iter<T,const N:usize>(&[T])->impl Iterator<Item=[&T;N]> {...}
// iter_mut is not possible to make such modification here.

Is it worth to wrote such a crate or just open an RFC?

This is probably not common enough to go into std.

1 Like

Itertools::combinations exists.

2 Likes

Mutable access versions won't be possible with a normal Iterator because multiple items cannot be (or contain) mutable references to the same thing.

2 Likes

for creating an iterator, that's ok.

But if we want to modify the slice itself, a _mut suffix is needed.

What's more, combinations() need a Clone mark, which limits the usage of this function.

note: required by a bound in `combinations`
    --> /home/neutron/.cargo/registry/src/mirrors.ustc.edu.cn-4affec411d11e50f/itertools-0.10.5/src/lib.rs:1485:27
     |
1485 |               Self::Item: Clone
     |                           ^^^^^ required by this bound in `Itertools::combinations`

Shared references are Clone. The &mut case isn't possible. But Cell can get you part way there.

3 Likes

But that's not an ad-hoc constraint. How do you expect the iterator to return the same item multiple times if it can't be duplicated somehow?