How to change Vec sorting based on a signal

[njam]

Let's say I have a Vec of things, and I'd like to sort it on-the-fly based on a sort-option (by size, by name, etc..). Whenever the sort-option changes, the vector items should be updated accordingly.

Is it possible to sort a SignalVec based on a closure that gets re-evaluated when a signal triggers? I can see for filtering there is filter_signal_cloned(), but I can't see something similar for sorting. Is it even feasible?

[Pauan]

Yup, that's exactly what sort_by_cloned does. It's quite fast: inserting a new element is only O(log(n)), not O(n * log(n)).

[njam]

Hmm.. The closure passed to filter_signal_cloned() returns a Signal<Item = bool>, so I can change the filtering later using a signal.
For example in this case when filter_option is changed, the SignalVec will re-filter:

    let list = signal_vec::always(vec![3, 1, 6, 2]).map(Rc::new);

    #[derive(Copy, Clone)]
    enum FilterOption { Odd, Even }
    let filter_option = Rc::new(Mutable::new(FilterOption::Odd));

    let mut signal = list
        .filter_signal_cloned(|item| {
            let item = Rc::clone(item);
            let filter_option = Rc::clone(&filter_option);
            filter_option.signal_ref(move |filter_option| {
                match filter_option {
                    FilterOption::Odd => *item % 2 != 0,
                    FilterOption::Even => *item % 2 == 0,
                }
            })
        });

But the closure passed to sort_by_cloned() returns a Ordering, so the sort order cannot be changed using a signal, right?
If I have a sort_option like this, I cannot have the vec re-sort when the sort options changes:

    let list = signal_vec::always(vec![3, 1, 6, 2]).map(Rc::new);

    #[derive(Copy, Clone)]
    enum SortOption { Incr, Decr }
    let sort_option = Rc::new(Mutable::new(SortOption::Incr));

    let mut signal = list
        .sort_by_cloned({
            let sort_option = Rc::clone(&sort_option);
            move |left, right| {
                match sort_option.get() {
                    SortOption::Incr => left.cmp(&right),
                    SortOption::Decr => right.cmp(&left),
                }
            }
        });

Or maybe I'm missing something?

(full code examples)

[Pauan]

@njam Normally I'd recommend using map_signal, since that allows you to map over every item and return a Signal, but that doesn't actually sound like what you're trying to do.

Let me think about the best way to fix this.

P.S. You don't need to wrap Mutable in Rc, it already supports reference-counting directly, so you can just clone the Mutable.

[Pauan]

So, after thinking about it, I think implementing sort_by_signal_cloned makes sense, analogous to filter_signal_cloned.

[njam]

Just a thought.
I guess when the sort-function changes, the sorting needs to be applied for all items again. Then maybe it's ok to just replace all the Vec's items (instead of tracking the items, and moving their position).

[Pauan]

Yeah, I think it will need to be something like that, because having FnMut(&Self::Item, &Self::Item) -> impl Signal<Item = Ordering> doesn't work.

[Pauan]

I recently implemented a to_signal_cloned method for SignalVec, you can use it like this:

let signal = map_mut! {
    let list = list.to_signal_cloned(),
    let sort_option = sort_option.signal() => {
        list.sort_by(|left, right| {
            match *sort_option {
                SortOption::Incr => left.cmp(&right),
                SortOption::Decr => right.cmp(&left),
            }
        });

        list
    }
};

This will resort the entire list whenever it changes, which isn't optimal for performance, but at least it works.

[njam]

Got it thanks! Should I close this ticket then?

For reference, here's a full example with this functionality:
https://gist.github.com/njam/c6eff91f490d04c9f215248973cd3e1b

[Pauan]

I'd still like to have a more efficient method specialized to this use case, but it's tricky to do it right.

[njam]

I guess the most efficient implementation would apply granular VecDiffs when the underlying SignalVec changes, but when the "sort_option" changes it would re-sort the whole vector and emit a VecDiff::Replace with the new items?

As an approximation for such behaviour I am now just replacing my MutableVec's content with itself whenever the sort-order changes.

[Pauan]

@njam Yes, that part is easy, the tricky part is the public API.

If you use to_signal_cloned then you don't need to replace the MutableVec, everything will happen automatically (though inefficiently).

[njam]

If you use to_signal_cloned then you don't need to replace the MutableVec, everything will happen automatically (though inefficiently).

But if I use to_signal_cloned() I cannot subscribe to granular VecDiff changes, right? The returned ToSignalCloned implements Signal, but not SignalVec. It will notify with the full vector on any changes, even if in the original list for example an item was appended. Or am I missing something?

[Pauan]

Yes, that's correct. That's the problem that the more efficient method is supposed to solve. So in the meantime replacing the MutableVec is a decent workaround.

[Pauan]

After thinking about it some more, I figured out a really good API.

I just published version 0.3.11 which contains the new switch_signal_vec method. It works like this:

sort_option.signal().switch_signal_vec(move |sort_option| {
    mutable_vec.to_signal_vec().sort_by_cloned(move |left, right| {
        match sort_option {
            SortOption::Incr => left.cmp(&right),
            SortOption::Decr => right.cmp(&left),
        }
    })
})

The way that it works is:

1. switch_signal_vec accepts a Signal as an input and returns a SignalVec.

2. It calls the closure with the current value of the Signal. The closure returns a SignalVec.

3. The output from the closure's SignalVec is routed to the switch's SignalVec, so you get incremental changes.

4. Whenever the Signal changes, it calls the closure again (which returns a new SignalVec).

5. It then switches from the old SignalVec to the new SignalVec (using VecDiff::Replace).

So the end result is that you will get incremental changes for the SignalVec which is returned by the closure, and whenever the Signal changes it will then send a VecDiff::Replace.

What I really like about this design is that it isn't specific to sorting: you can use switch_signal_vec in all sorts of situations.

For example, you might be doing some URL routing, and you want to change the webpage based on the URL. So you could use switch_signal_vec for that:

url.signal().switch_signal_vec(move |url| {
    match url {
        "/foo" => return_signal_vec_for_foo(),
        "/bar" => return_signal_vec_for_bar(),
    }
});

[njam]

Nice, works great, thanks!