#include <memory>
#include <algorithm>

#include "print.hpp"

/**
 * @brief Aggiorna il cambio minimo
 * 
 * Questa funzione aggiorna il cambio minimo noto usando il cambio
 * corrente.
 * 
 * @param minimo è il miglior cambio noto
 * @param len_minimo è il numero di monete nel miglior cambio noto
 * @param corrente è il nuovo cambio trovato
 * @param len_corrente è il numero di monete del nuovo cambio trovato
 */
void
aggiorna_minimo(unsigned int*& minimo, size_t& len_minimo,
                const unsigned int* corrente, const size_t& len_corrente)
{
    delete[] minimo;

    len_minimo = len_corrente;
    minimo = new unsigned int[len_minimo];

    for (size_t i=0; i<len_corrente; ++i) {
        minimo[i] = corrente[i];
    }
}

/**
 * @brief Trova un cambio minimo
 * 
 * Questa funzione trova un cambio minimo, a partire da quello corrente, 
 * per cambiare un valore. 
 * Ogni invocazione della funzione opera su:
 * - il cambio minimo noto fino al momento dell'invocazione
 * - il cambio corrente al quale si aggiungeranno monete durante la 
 *   computazione
 * - il cambia monete al quale si toglieranno le monete aggiunte al 
 *   cambio corrente
 * - il valore che non è stato ancora cambiato
 * - il sotto-insieme di tagli che può ancora essere usato per il 
 *   cambio di quanto manca
 * 
 * La prima chiamata prevede che il cambio minimo sia ignoto, il cambio
 * corrente sia vuoto, e il sotto-insieme di tagli usabili per il 
 * cambio corrisponda a tutti i tagli del cambia-monete
 * 
 * Questa una funzione è implementata ricorsivamente con i 
 * seguenti casi:
 * 1. **Caso Base** Il cambio corrente contiene più monete del cambio
 *    minimo noto. Dal cambio corrente non posso generare un nuovo 
 *    cambio minimo e faccio backtracking.
 * 2. **Caso Base** Il valore da cambiare è 0: il cambio corrente è un 
 *    cambio valido per il valore che si voleva cambiare alla prima 
 *    invocazione del metodo. Aggiorno il cambio minimo e faccio 
 *    backtracking.
 * 3. **Passo Ricorsivo** Ci sono monete del tipo `indice_taglio` e
 *    il taglio di tali monete è minore o uguale a quello del valore 
 *    da cambiare. Provo ad aggiungere una di tali monete al cambio, 
 *    rimuovo la moneta da quelle disponibili nel cambia monete,
 *    riduco il valore da cambiare del valore della monete e 
 *    procedo ricorsivamente. Al rientro dalla chiamata ricorsiva, 
 *    rimetto la moneta nel cambia monete.
 * 4. **Passo Ricorsivo** Provo a trovare il minimo tra i cambi che 
 *    non aggiungono ulteriori monete del tipo `indice_taglio`.
 *  
 * @param minimo è il migliore cambio noto 
 * @param len_minimo è il numero di monete del miglior cambio not
 * @param corrente è il cambio a partire dal quale devo cambiare `valore`
 * @param len_corrente è il numero di monete usate da `corrente`
 * @param tagli è l'array dei tagli di monete
 * @param num_di_tagli è il numero di tagli nel cambia monete
 * @param monete è il numero di monete per ogni taglio
 * @param valore è il valore da cambiare
 * @param indice_taglio è l'estremo sinistro dei tagli utilizzabili per il 
 *            cambio
 */
void
trova_cambio(unsigned int*& minimo, size_t& len_minimo,      // parametri del miglio cambio noto
             unsigned int* corrente, size_t& len_corrente,  // parametri del cambio su cui sto lavorando
             const unsigned int tagli[], const size_t& num_tagli, unsigned int monete[],  // parametri del cambiamonete
             const size_t valore, size_t indice_taglio);

/**
 * Prova ad aggiungere una moneta e a trovare un cambio
 *
 * Questa funzione implementa il punto 3. della funzione trova_cambio()
 * 
 * @param minimo è il migliore cambio noto 
 * @param len_minimo è il numero di monete del miglior cambio not
 * @param corrente è il cambio a partire dal quale devo cambiare `valore`
 * @param len_corrente è il numero di monete usate da `corrente`
 * @param tagli è l'array dei tagli di monete
 * @param num_di_tagli è il numero di tagli nel cambia monete
 * @param monete è il numero di monete per ogni taglio
 * @param valore è il valore da cambiare
 * @param indice_taglio è l'estremo sinistro dei tagli utilizzabili per il 
 *            cambio 
 */
void
aggiungi_moneta(unsigned int*& minimo, size_t& len_minimo,
                unsigned int* corrente, size_t& len_corrente,
                const unsigned int tagli[], const size_t& num_tagli, unsigned int monete[],
                const size_t valore, size_t indice_taglio)
{
    corrente[len_corrente++] = tagli[indice_taglio];
    --(monete[indice_taglio]);

    trova_cambio(minimo, len_minimo, 
                 corrente, len_corrente,
                 tagli, num_tagli, 
                 monete, valore-tagli[indice_taglio], 
                 indice_taglio);
    
    --len_corrente;
    ++(monete[indice_taglio]);
}

void
trova_cambio(unsigned int*& minimo, size_t& len_minimo,      // parametri del miglio cambio noto
             unsigned int* corrente, size_t& len_corrente,  // parametri del cambio su cui sto lavorando
             const unsigned int tagli[], const size_t& num_tagli, unsigned int monete[],  // parametri del cambiamonete
             const size_t valore, size_t indice_taglio)
{

    if (len_minimo > 0 && len_corrente > len_minimo) {   // punto 1.

        // fai backtracking
        return;
    }

    if (valore==0) {    // punto 2.
        aggiorna_minimo(minimo, len_minimo, corrente, len_corrente);

        return;
    }

    if (valore >= tagli[indice_taglio] && monete[indice_taglio]>0) {  // punto 3.
        
        aggiungi_moneta(minimo, len_minimo, corrente, len_corrente,
                        tagli, num_tagli, monete, valore, indice_taglio);
    }

    if (indice_taglio+1<num_tagli) {  // punto 4. se ci sono ancora tagli 
                                      // diversi da `indice_taglio` 
                                      // disponbili per l'uso
        trova_cambio(minimo, len_minimo, corrente, len_corrente,
                     tagli, num_tagli, monete, valore, indice_taglio+1);
    }
}

/**
 * Trova il minimo in un array
 * 
 * @tparam T è il tipo degli elementi dell'array
 * @param A è un array
 * @param len è la lunghezza dell'array
 * @return il minimo del valori in `A`
*/
template<typename T>
T trova_min(const T A[], const size_t len)
{
    T min_value = A[0];

    for (size_t i=1; i<len; ++i) {
        if (min_value > A[i]) {
            min_value = A[i];
        }
    }

    return min_value;
}

/**
 * @brief Cambia un valore in monete
 * 
 * @param[out] len_cambio è la lunghezza del minimo cambio trovato
 * @param[in] tagli è l'array dei tagli di monete disponibili nel cambia monete
 * @param[in] num_di_tagli è il numero di tagli nel cambia monete
 * @param[in] monete è il numero di monete per ogni taglio
 * @param[in] valore è il valore da cambiare
 * @return Il cambio migliore per valore
 */
std::unique_ptr<unsigned int[]>
cambia(size_t& lunghezza_cambio, 
       const unsigned int tagli[], const size_t& num_tagli, unsigned int monete[],
       const unsigned int& valore)
{
    // inizializzazione del minimo trovato
    // fino a questo punto
    unsigned int* minimo = nullptr;
    lunghezza_cambio = 0;

    unsigned int min_tagli = trova_min(tagli, num_tagli);
    unsigned int max_monete = valore/min_tagli + 1;

    // cambio del valore già cambiato
    unsigned int* corrente = new unsigned int[max_monete];
    size_t len_corrente = 0;

    trova_cambio(minimo, lunghezza_cambio, corrente, len_corrente,
                 tagli, num_tagli, monete, valore, 0);

    delete[] corrente;
    
    return std::unique_ptr<unsigned int[]>{minimo};
}

int main()
{
    unsigned int tagli[] = {1, 29, 100};
    unsigned int monete[] = {30, 4, 2};

    size_t len_cambio;

    auto cambio = cambia(len_cambio, tagli, 3, monete, 117);

    println(cambio.get(), len_cambio);

    return 0;
}