/*************************************************************
 *      Program Solving the KNAPSACK problem by brute force  *
 *      Author Jakub Holy                                    *
 *      For the subject PAA, LS2002                          *
 *************************************************************
 */


#include <iomanip.h>

#include "hw1_force.hh"

// *** ******************************************** KnapsackProblem
KnapsackProblem::KnapsackProblem(int task_id, int nr_items, int max_load, Item **items){
  // Parameters
  KnapsackProblem::task_id  = task_id;
  KnapsackProblem::nr_items = nr_items;
  KnapsackProblem::max_load = max_load;
  KnapsackProblem::items    = items;
  // Init other fields
  config 	= new bool[nr_items];
  best_config 	= new bool[nr_items];
  best_cost	= 0;
  load 		= 0;
  cost		= 0;
  index		= 0;
} // constructor

KnapsackProblem::~KnapsackProblem(){
  delete [] items;
  delete [] config;
  delete [] best_config;
} //destructor

// *************************************************************** DESCEND

/** SOLVE the problem by brute force
 *  The approach:
 *  + We have to try all possible configurations (for which load <= max_load).
 *	A configuration is represented as an array of booleans called config;
 *	if config[i]==true => i-th item is in the solution (in the knapsack).
 *	Thus we have to try all possible bit strings of the length equal to 
 *	the number of items.
 *	We start to set values in the string from the beginning (func. descend), 
 *	when the end is reached, we return to the nearest included item, exclude 
 *	it and set again the rest of the string (from the item to the end; func.
 *	mount()).
 *  The first configuration tried is all ones (if max_load large enough),
 *	the last one all zeros.(Descend creates 1s, mount always adds a 0.)
 */
void KnapsackProblem::solve(void){
  bool cont = true;
  // Following shared variables (class fields) are used:
  // index, load, config, best_config, best_cost.
  // Fields nr_items and max_load are use as constants here.
  // They are initiated in the constructor.
  index = load = best_cost = 0;	// re-initiate non-pointer variables
  while (cont) {
    descend();
    cont = mount();
  }//while not done
}// solve

/** DESCEND
 *  Moves forward in the config[] array to the end.
 *  It always sets config[i] to true, unless the max_load would be exceeded.
 *  Before it finishes, it compares the current (complete) configuration 
 *  with the best one and saves it, if better.
 */
void KnapsackProblem::descend(void){

  // Descend till the last item (its index is nr_items-1).
  for(; index < nr_items; index++) {

    // Check if we can include the current item (don't exceed max_load)
    if( ( load + items[index]->weight ) <= max_load ){
      config[index] = true;		// include the item
      load += items[index]->weight;	// add its weight to the total load
      cost += items[index]->cost;  	// add its cost to the total one
    } else {
      config[index] = false;
    }//if-else

  }//while not in a leaf
  // Decrement index again, now it's invalid, for it equals to nr_items.
  index--;

  // Compare the current configuration to the best one and perhaps replace it.
  if( cost > best_cost ){
    best_cost = cost;		// save the new best cost
    // save the configuration
    for(int i=0; i < nr_items; i++){
      best_config[i] = config[i];
    }//for
  }// compare with the best known solution so far

} // descend

/** MOUNT
 *  Moves backward in the config[] array until config[i]==true found,
 *  set it to false (exlcude it) and finish. Descend will start at config[i+1].
 *  @return false if cannot mount => we are done
 */
bool KnapsackProblem::mount(void){
  bool reached1 = false;

  // Exclude the leaf item (by mounting the bottom part of config[] 
  // becomes invalid. Bottom means > index.
  assert(index == (nr_items-1) );
  // exclude the first item, if it is included
  if ( config[index] ){
    config[index] = false;	
    load -= items[index]->weight;
    cost -= items[index]->cost;
  }// if 1st item included

  // Mount until an included item found or the beginning of config[] reached.
  while( (!reached1) && (index > 0) ){
    // This must be first to mount from a leaf (that's where mount is called from)
    // The config. with the leaf excluded doesn't need to be tested, because it
    // can be only worse (by decreasing cost).
    index--;

    // If the current item is included, exclude it, inc. index and finish.
    if ( config[index] ){
      reached1      = true;	 // say we are done here
      // This item won't be excluded at the beginning of this while
      // => do it now
      config[index] = false;	// exclude the item
      load -= items[index]->weight;
      cost -= items[index]->cost;
      // descend 1 item, otherwise it would be included again be descend()
      index++;
    }// it the current item is included

  }//while not an included item found or can't mount more

  return reached1;
} // mount

// ****************************************************************** printResult
void KnapsackProblem::printResult(void){
  assert( items!=0 );
  cout << task_id << " "<< nr_items <<" " << setw(4) << setiosflags(ios::left)<< best_cost;
  for(int i=0; i<nr_items; i++ ){
    //    if( best_config[i] )
    cout <<" "<< best_config[i];
  }//for
  cout << endl;
}//printResult

// ******************************************************************** MAIN
// ******************************************************************** MAIN
int main(int argc, char **argv){
  //Open data file and load the 1st task
  if ( argc != 2 ) {
    cout << "Error: Wrong number of parameters.\n";
    cout << "Use: bruteforce taskfile\n"; 
  }// if wrong input
  KnapsackInput *in = new KnapsackInput( argv[1] );

  // For all tasks in the file:
  do {
    // Solve a task
    KnapsackProblem *problem = new KnapsackProblem(in->getTaskID(), in->getNr_items(), in->getMax_load(), in->getItems() );
    problem->solve();
    problem->printResult();
  } while ( in->loadNextTask() );
  //---------
  return 0;
}// main