im-util: Add Sort, SortBy adapters

[jplatte]

[jplatte]

I started updating the tests and I think I found a bug. Check this test which currently passes (ignore the copy-pasted comments), I don't see how that could make any sense.

[jplatte]

Yeah so this is unrelated to my changes, this also succeeds on main when logically only a Set should be emitted:

#[test]
fn bug() {
    let mut ob = ObservableVector::<char>::from(vector!['d', 'e', 'b', 'g']);
    let (values, mut sub) = ob.subscribe().sort_by(&|a, b| b.cmp(a));

    assert_eq!(values, vector!['g', 'e', 'd', 'b']);

    ob.set(0, 'c');
    assert_next_eq!(sub, VectorDiff::Remove { index: 2 });
    assert_next_eq!(sub, VectorDiff::Insert { index: 2, value: 'c' });

    drop(ob);
    assert_closed!(sub);
}

[Hywan]

This isn’t technically a bug. The Remove + Insert can indeed be simplified into a single Set if the index is the same. I can add this as an optimisation, which is likely to be necessary for performance reason. Good catch.

[jplatte]

Right. Just very unexpected :)

I guess I should finish the tests independently of that optimization.

[Hywan]

Hmm, actually, this optimisation is already present, and even tested.

The test:

https://github.com/jplatte/eyeball/blob/71e0a72adc377584da78fb4c1b3ad9714a7287f4/eyeball-im-util/tests/it/sort.rs#L337-L343

The code:

https://github.com/jplatte/eyeball/blob/71e0a72adc377584da78fb4c1b3ad9714a7287f4/eyeball-im-util/src/vector/sort.rs#L504-L531

[Hywan]

Actually, it's not a bug… Taking this code:

let mut ob = ObservableVector::<char>::from(vector!['d', 'e', 'b', 'g']);
let (values, mut sub) = ob.subscribe().sort_by(&|a, b| b.cmp(a));

assert_eq!(values, vector!['g', 'e', 'd', 'b']);

ob.set(0, 'c');
assert_next_eq!(sub, VectorDiff::Remove { index: 2 });
assert_next_eq!(sub, VectorDiff::Insert { index: 2, value: 'c' });

So, when doing set(0, 'c'), the algorithm will compute the old_index and the new_index:

https://github.com/jplatte/eyeball/blob/71e0a72adc377584da78fb4c1b3ad9714a7287f4/eyeball-im-util/src/vector/sort.rs#L488-L502

The old_index in this case is 2, which is correct: (0, 'd') is at the position 2 in the “sorted view”. The new_index in this case is 3, which is… also correct because of how binary_search_by with this compare function works. The position to insert c is at index 3 because the vector is reverse-ordered.

And indeed, if you change sort_by(&|a, b| b.cmp(a)) to sort_by(&|a, b| a.cmp(b)), you get:

let mut ob = ObservableVector::<char>::from(vector!['d', 'e', 'b', 'g']);
let (values, mut sub) = ob.subscribe().sort_by(&|a, b| a.cmp(b));

assert_eq!(values, vector!['b', 'd', 'e', 'g']);

ob.set(0, 'c');
assert_next_eq!(sub, VectorDiff::Set { index: 1, value: 'c' });

drop(ob);
assert_closed!(sub);

I know, it's surprising, but it's indeed perfectly logical.

One thing that is questionnable though: is it correct to assume that if 2 indices are side-by-side, we can optimise it, like if we have old_index == new_index - 1 (so, Remove { index: old_index } then Insert { index: new_index - 1 }, we can consider we are updating the same place?

[Hywan]

OK, see https://github.com/jplatte/eyeball/pull/49 for the fix. Thanks for noticing this!