"use strict"


var Change = function()
{


}

module.exports=Change;


//data structure to hold each candidate solution that is generated
var Candidate = function()
{
    
    var searched=false;
    var coins=[];

    this.Searched =function()
    {
        searched=true;
    }
    
    this.isSearched = function()
    {
        return searched;
    }
    
    this.getCoins = function()
    {
        return coins;
    }
    
    this.addCoin = function(coin)
    {
        function sortNum(a,b)
        {
            return a-b;
        }
        
        coins.push(coin);
        coins.sort(sortNum);

    }
    
    this.getCoinCount=function()
    {
        return coins.length;
    }

    this.getSum=function()
    {
        function getSum(total, num){return total+num;}
        return coins.reduce(getSum);
    }
  

}

Change.prototype.calculate=function(coinArray, target)
{

    var candidates=[];
    //fill the array with 0 to start
    candidates[target]=0;
    candidates.fill(0);

    //validation checks up front
    if(target==0)return [];

    if(target<0)
    {
        throw new Error( 'Negative totals are not allowed.');
    }

    if(target<Math.min.apply(null,coinArray))
    {
        throw new Error('The total '+ target +' cannot be represented in the given currency.');
    }

    
    initialize();
    //printAll();
   

    //process the arrange until everything is searched
    while(isDone()==false)
    {
        let candidate=getNext();
        branch(candidate);
        candidate.Searched();
    }
     //printAll();


    //print the result
    if(typeof(candidates[target])!='number')
        return candidates[target].getCoins();
    else throw new Error('The total '+ target +' cannot be represented in the given currency.');


    //print the candidate array
    function printAll()
    {
        for(let j=0; j< candidates.length; j++)
        {
            if(typeof(candidates[j])=='object')
            {
                console.log('index: ' + j + ' ' + candidates[j].getCoins() + ' searched: ' + candidates[j].isSearched());
            }
            else
            {
                console.log('index: ' + j + ' is empty ' + typeof(candidates[j]));
            }
        }
    }

    //initialize the candidate array with the given coins only
    function initialize()
    {
        for(let j=0; j<coinArray.length; j++)
        {
            let temp= coinArray[j];
            let candidate = new Candidate();
            candidate.addCoin(temp);
            saveCandidate(candidate);
            
        }
    }

    //is everthing searched?
    function isDone()
    {
        let done=true;
        for (let i=0; i<candidates.length; i++)
        {
            let temp=candidates[i];
            if(typeof(temp)!='number')
            {
                if(temp.isSearched()==false)
                {
                    done=false;
                    break;
                }
            }
        }
        return done;
    }
    
    //get the next unsearched member of the candidate array
    function getNext()
    {
        for(let i=0; i< candidates.length; i++)
        {
            let temp= candidates[i];
            if (typeof(temp)!='number' && 
                temp.isSearched()==false)return temp;
        }
        return null;

    }

    //save a new candidate to the candidate array
    function saveCandidate(candidate)
    {
        let sum=candidate.getSum();

        if( candidate.getSum()<=target &&
            typeof(candidates[sum])!='number' &&
            candidates[sum].getCoinCount()>candidate.getCoinCount())
        {
            candidates[sum]=candidate;
        }

        if(candidate.getSum()<=target &&
           typeof(candidates[sum])=='number')
        {
            candidates[sum]=candidate;
        }
    }
    

    //for the candidate, generate another candate for each of the possible coins
    function branch(current)
    {
        for(let j=0; j<coinArray.length; j++)
        {
            
            //make a new Candidate for coin type
            let candidate= new Candidate();

            //copy the curent coins into it and add the new coin type
            for(var i=0; i< current.getCoins().length; i++)candidate.addCoin(current.getCoins()[i]);

            candidate.addCoin(coinArray[j]);

            saveCandidate(candidate);
        }
        
    }

}