//#################################### routes.lib ########################################
// A library to handle signal routing in Faust. Its official prefix is `ro`.
//
// #### References
// * <https://github.com/grame-cncm/faustlibraries/blob/master/routes.lib>
//########################################################################################

/************************************************************************
************************************************************************
FAUST library file
Copyright (C) 2003-2019 GRAME, Centre National de Creation Musicale
----------------------------------------------------------------------
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as
published by the Free Software Foundation; either version 2.1 of the
License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

EXCEPTION TO THE LGPL LICENSE : As a special exception, you may create a
larger FAUST program which directly or indirectly imports this library
file and still distribute the compiled code generated by the FAUST
compiler, or a modified version of this compiled code, under your own
copyright and license. This EXCEPTION TO THE LGPL LICENSE explicitly
grants you the right to freely choose the license for the resulting
compiled code. In particular the resulting compiled code has no obligation
to be LGPL or GPL. For example you are free to choose a commercial or
closed source license or any other license if you decide so.
************************************************************************
************************************************************************/

ba = library("basics.lib");
si = library("signals.lib");
sp = library("spats.lib");

declare name "Faust Signal Routing Library";
declare version "1.2.0";

//=============================Functions Reference========================================
//========================================================================================

//--------------------------------`(ro.)cross`-----------------------------------
// Cross N signals: `(x1,x2,..,xn) -> (xn,..,x2,x1)`.
// `cross` is a standard Faust function.
//
// #### Usage
//
// ```
// cross(N)
// _,_,_ : cross(3) : _,_,_
// ```
//
// Where:
//
// * `N`: number of signals (int, as a constant numerical expression)
//
// #### Note
//
// Special case: `cross2`:
//
// ```
// cross2 = _,cross(2),_;
// ```
//-----------------------------------------------------------------------------
// cross n cables : (x1,x2,..,xn) -> (xn,..,x2,x1)
cross(N) = route(N, N, par(i, N, (i+1, N-i)));
cross2 = _,cross(2),_; // for compatibility with some old misceffects.lib functions


//--------------`(ro.)crossnn`--------------
// Cross two `bus(N)`s.
//
// #### Usage
//
// ```
// (si.bus(2*N)) : crossnn(N) : (si.bus(2*N))
// ```
//
// Where:
//
// * `N`: the number of signals in the `bus` (int, as a constant numerical expression)
//--------------------------------------
crossnn(N) = crossNM(N,N);


//--------------`(ro.)crossn1`--------------
// Cross `bus(N)` and `bus(1)`.
//
// #### Usage
//
// ```
// (si.bus(N),_) : crossn1(N) : (_,si.bus(N))
// ```
//
// Where:
//
// * `N`: the number of signals in the first `bus` (int, as a constant numerical expression)
//--------------------------------------
crossn1(N) = crossNM(N,1);


//--------------`(ro.)cross1n`--------------
// Cross `bus(1)` and `bus(N)`.
//
// #### Usage
//
// ```
// (_,si.bus(N)) : crossn1(N) : (si.bus(N),_)
// ```
//
// Where:
//
// * `N`: the number of signals in the second `bus` (int, as a constant numerical expression)
//--------------------------------------
cross1n(N) = crossNM(1,N);


//--------------`(ro.)crossNM`--------------
// Cross `bus(N)` and `bus(M)`.
//
// #### Usage
//
// ```
// (si.bus(N),si.bus(M)) : crossNM(N,M) : (si.bus(M),si.bus(N))
// ```
//
// Where:
//
// * `N`: the number of signals in the first `bus` (int, as a constant numerical expression)
// * `M`: the number of signals in the second `bus` (int, as a constant numerical expression)
//--------------------------------------
crossNM(N,M) = route(N+M, N+M, par(i, N+M, i+1, ((i+M)%(N+M))+1));


//--------------------------`(ro.)interleave`------------------------------
// Interleave R x C cables from column order to row order. That is, transpose the input CxR matrix, 
// the first R inputs is the first row.
//
// input : `x(0), x(1), x(2) ..., x(row*col-1)`
//
// output: `x(0+0*row), x(0+1*row), x(0+2*row), ..., x(1+0*row), x(1+1*row), x(1+2*row), ...`
// 
// 
//
// #### Usage
//
// ```
// si.bus(R*C) : interleave(R,C) : si.bus(R*C)
// ```
//
// Where:
//
// * `R`: row length (int, as a constant numerical expression)
// * `C`: column length (int, as a constant numerical expression)
//-----------------------------------------------------------------------------
interleave(1,2) = _,_;
interleave(R,C) = route(R*C, R*C, par(i, R*C, (i+1, (i%R)*C + int(i/R) + 1)));

//-------------------------------`(ro.)butterfly`--------------------------------
// Addition (first half) then substraction (second half) of interleaved signals.
//
// #### Usage
//
// ```
// si.bus(N) : butterfly(N) : si.bus(N)
// ```
//
// Where:
//
// * `N`: size of the butterfly (N is int, even and as a constant numerical expression)
//-----------------------------------------------------------------------------
butterfly(2) = si.bus(2) <: +,-;
butterfly(N) = si.bus(N) <: interleave(N/2,2), interleave(N/2,2) : par(i, N/2, +), par(i, N/2, -);


//------------------------------`(ro.)hadamard`----------------------------------
// Hadamard matrix function of size `N = 2^k`.
//
// #### Usage
//
// ```
// si.bus(N) : hadamard(N) : si.bus(N)
// ```
//
// Where:
//
// * `N`: `2^k`, size of the matrix (int, as a constant numerical expression)
//
//-----------------------------------------------------------------------------
declare hadamard author "Remy Muller, revised by Romain Michon";
hadamard(2) = butterfly(2);
hadamard(N) = butterfly(N) : (hadamard(N/2), hadamard(N/2));


//---------------`(ro.)recursivize`-------------
// Create a recursion from two arbitrary processors `p` and `q`.
//
// #### Usage
//
// ```
// _,_ : recursivize(p,q) : _,_
//
// ```
//
// Where:
//
// * `p`: the forward arbitrary processor
// * `q`: the feedback arbitrary processor
//----------------------------------------
recursivize(p,q) = (_,_,_,_ :> sp.stereoize(p)) ~ sp.stereoize(q);


//--------------------`(ro.)bubbleSort`-----------------------------------------
//
// Sort a set of N parallel signals in ascending order on-the-fly through
// the Bubble Sort algorithm.
//
// Mechanism: having a set of N parallel signals indexed from 0 to N - 1,
// compare the first pair of signals and swap them if sig[0] > sig[1];
// repeat the pair comparison for the signals sig[1] and sig[2], then again
// recursively until reaching the signals sig[N - 2] and sig[N - 1]; by the end,
// the largest element in the set will be placed last; repeat the process for
// the remaining N - 1 signals until there is a single pair left.
//
// Note that this implementation will always perform the worst-case
// computation, O(n^2).
//
// Even though the Bubble Sort algorithm is one of the least efficient ones,
// it is a useful example of how automatic sorting can be implemented at the
// signal level.
//
// #### Usage
//
// ```
// si.bus(N) : bubbleSort(N) : si.bus(N)
//
// ```
//
// Where:
//
// * `N`: the number of signals to be sorted (must be an int >= 0, as a constant numerical expression)
//
// #### Reference
// <https://en.wikipedia.org/wiki/Bubble_sort>
//------------------------------------------------------------------------------
declare bubbleSort author "Dario Sanfilippo";
declare bubbleSort copyright "Copyright (C) 2021 Dario Sanfilippo
    <sanfilippo.dario@gmail.com>";
declare bubbleSort license "MIT License";
bubbleSort(0) = 0 : !;
bubbleSort(1) = _;
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));
    };