Run-time list processing

[dariosanfilippo]

Hello, people.

This came out during a conversation on Discord's #faust channel. Could some kind of run-time list processing be useful for the libraries? The following orders a set of parallel signals in ascending order. If so, I can do a PR.

Ciao,
Dario

import("stdfaust.lib");
list = par(i, 5, hslider("item%i", 4 - i, 0, 4, .001));
N = outputs(list);
tagList(N) = si.bus(N) , par(i, N, i) : ro.interleave(N, 2);
untagList(N) = par(i, N, select2(0));
taggedIf(cond, then0, then1, else0, else1) =    ba.if(cond, then0, else0) , 
                                                ba.if(cond, then1, else1);
taggedMin = route(4, 6, (1, 1), (3, 2), (1, 3), (2, 4), (3, 5), (4, 6)) :   < , 
                                                                            si.bus(4) : taggedIf;
taggedMinN(1) = _ , _;
taggedMinN(2) = taggedMin;
taggedMinN(N) = taggedMinN(N - 1, taggedMin);
delTaggedItem(N, sig, tag) = ro.interleave(2 , N) : delItem(N, tag) , delItem(N, tag) : ro.interleave(N - 1 , 2);
delItem(N, idx) = si.bus(N) <: par(i, N - 1, ba.selectn(N, ba.if(i < idx, i, i + 1)));
moveMinToTop(N) = tagList(N) <: (taggedMinN(N) <: si.bus(4)) , si.bus(N * 2) : si.bus(2) , delTaggedItem(N) : untagList(N);
bus(0) = 0 : !;
bus(1) = _;
bus(N) = si.bus(N);
orderList(N) = seq(i, N - 1, bus(i) , moveMinToTop(N - i));
process = list <: si.bus(N) , orderList(N);

[dariosanfilippo]

Improved algorithm:

import("stdfaust.lib");
M = 8;
list = par(i, M, hslider("item%2i", M - i - 1, 0, M - 1, .001));
N = outputs(list);
bus(0) = 0 : !;
bus(N) = si.bus(N);
minSwap = si.bus(2) <: si.bus(4) <: select2(>) , select2(<);
minSwapN(0) = 0 : !;
minSwapN(1) = _;
minSwapN(2) = minSwap;
minSwapN(N) = seq(i, N - 1, bus(i) , minSwap , bus(N - i - 2));
sortList(N) = seq(i, N - 1, minSwapN(N));
process = list : sortList(N);

Ciao,
Dario

[dariosanfilippo]

Better still, since after the first pass of swaps the largest element is placed last, we can then perform the swaps on the first N-1 elements and so on:

import("stdfaust.lib");
M = 8;
list = par(i, M, hslider("item%2i", M - i - 1, 0, M - 1, .001));
N = outputs(list);
bus(0) = 0 : !;
bus(N) = si.bus(N);
minSwap = si.bus(2) <: si.bus(4) <: select2(>) , select2(<);
minSwapN(0) = 0 : !;
minSwapN(1) = _;
minSwapN(2) = minSwap;
minSwapN(N) = seq(i, N - 1, bus(i) , minSwap , bus(N - i - 2));
sortList(N) = seq(i, N - 1, minSwapN(N - i) , bus(i));
process = list : sortList(N);

[sletz]

import("stdfaust.lib");

M = 32;
list = par(i, M, hslider("item%2i", M - i - 1, 0, M - 1, .001));

sortList(list) = list : seq(i, N - 1, minSwapN(N - i), bus(i))
with {
    N = outputs(list);
    bus(0) = 0 : !;
    bus(N) = si.bus(N);
    minSwapN = case { 
        (0) => 0 : !; 
        (1) => _; 
        (2) => minSwap;
        (N) => seq(i, N - 1, bus(i), minSwap, bus(N - i - 2));
    } with {
        minSwap = si.bus(2) <: si.bus(4) <: select2(>), select2(<);
    };
};

process = sortList(list);

[dariosanfilippo]

Thanks, Stéphane. I hadn't done any finessing yet; mostly looking for the best algorithm. :)

[dariosanfilippo]

I just realised that what I implemented is the Bubble Sort algorithm, so I'd go with this, assuming N>=2:

import("stdfaust.lib");
N = 8;
list = par(i, N, hslider("item%2i", N - i - 1, 0, N - 1, .001));
bubbleSort(N) = seq(i, N - 1, pairSortN(N - i) , bus(i))
    with {
        bus(0) = 0 : !;
        bus(N) = si.bus(N);
        pairSort = bus(2) <: select2(>) , select2(<);
        pairSortN(N) = seq(i, N - 1, bus(i) , pairSort , bus(N - i - 2));
    };
process = list : bubbleSort(N);

[sletz]

I suggest having the bubbleSort take the list itself as parameter:

import("stdfaust.lib");

M = 16;
list = par(i, M, hslider("item%2i", M - i - 1, 0, M - 1, .001));

bubbleSort(list) = list : seq(i, N - 1, pairSortN(N - i) , bus(i))
    with {
        N = outputs(list);
        bus(0) = 0 : !;
        bus(N) = si.bus(N);
        pairSort = bus(2) <: select2(>) , select2(<);
        pairSortN(N) = seq(i, N - 1, bus(i) , pairSort , bus(N - i - 2));
    };

process = bubbleSort(list);

[dariosanfilippo]

As a run-time processor, wouldn't it be better to instantiate it with whatever number of channels we want to process like ba.selectn?

[sletz]

I don't understand, what is the point ? what would be the code ?

[dariosanfilippo]

I'd just find it more natural to set up a sorting unit of N inputs and outputs rather than having the list passed as an argument determining the inputs and outputs.

Particularly for the generated diagrams, it is less straightforward to understand what happens inside the function; see these two diagrams, for example:

import("stdfaust.lib");
N = 8;
bubbleSort(list) = list : seq(i, N - 1, pairSortN(N - i) , bus(i))
    with {
        N = outputs(list);
        bus(0) = 0 : !;
        bus(N) = si.bus(N);
        pairSort = bus(2) <: select2(>) , select2(<);
        pairSortN(N) = seq(i, N - 1, bus(i) , pairSort , bus(N - i - 2));
    };
list = si.bus(N * 2) :> si.bus(N);
process = bubbleSort(list) , bubbleSort(list);

import("stdfaust.lib");
N = 8;
bubbleSort(N) = seq(i, N - 1, pairSortN(N - i) , bus(i))
    with {
        bus(0) = 0 : !;
        bus(N) = si.bus(N);
        pairSort = bus(2) <: select2(>) , select2(<);
        pairSortN(N) = seq(i, N - 1, bus(i) , pairSort , bus(N - i - 2));
    };
list = si.bus(N * 2) :> si.bus(N);
process = bubbleSort(N, list) , bubbleSort(N, list);

[sletz]

OK so I guess bubbleSort can go in signals.lib library ?

[dariosanfilippo]

I personally see it more as automatic routing.

[sletz]

so where?

[dariosanfilippo]

routes.lib for me :)

[sletz]

OK let's go for routes.lib