#include <stdio.h>
#include <stdlib.h>
//#include <iostream>
//#include <ios>
//#include <mingw32\bits\c++io.h>
//#include <math.h>
#include <time.h>

#define ITERATIONS 50
#define MAX_ITEMS  64

typedef unsigned short int item_property;
typedef unsigned int       bag_property;
typedef unsigned long long  bag;


struct item
{
    item_property mass, value;

	//default constructor with defined default values(so it can be called with())
	item (const item_property x = 0, const item_property y = 0);

	//copy constructor
	item (const item &i);


};


item::item (const item_property x, const item_property y): mass(x), value(y)
{
	//nothing to do here
}

item::item (const item &i) : mass(i.mass), value(i.value)
{
	//nothing to do here
}



//typedef int pole[5] ;
typedef item item_list[MAX_ITEMS];


////////////////////////////////////////////////////////////////////////////////
/////////////////////general functions//////////////////////////////////////////
bag_property CalcMass (const item_list &i, bag b, const int &s)
{
    bag_property tot_mass = 0;

    for (unsigned char a = 0; a < s; a++)
    {
        //get last bit of the bag
        const unsigned char mask = b & 1;

        //summ
        tot_mass += (i[a].mass)*mask;

        //shift
        b = b >> 1;
    }

    return tot_mass;
}

bag_property CalcValue (const item_list &i, bag b, const int &s)
{
    bag_property tot_val = 0;

    for (unsigned char a = 0; a < s; a++)
    {
        //get last bit of the bag
        const unsigned char mask = b & 1;

        //summ
        tot_val += (i[a].value)*mask;

        //shift
        b = b >> 1;
    }

    return tot_val;
}

bag AddItem (const item_list &i, bag b, const short int number)
{
    const bag mask = (1 << number);
    b = b | mask;
    return b;
}


//reads item from file opened using FOPEN
item ReadItem (FILE *in_file)
{
    //be careful, needs to be an int!!!
    int x ,y;

	if ( !(fscanf (in_file, "%i %i", &x, &y)) )
	{
		//cerr << "Error reading an item from input file.";
		exit(1);
	}

    return item(x,y);
}




int main (int argc, char **argv)
{


	//cout << "Bag problem solving program" << endl << "(c)Tomas Kubes 2005" << endl;
    //printf("");
    printf("Bag problem solving program\n(c)Tomas Kubes 2005\n\n");

	if ( argc != 3 )
	{
		//cerr << "Invalid parameters" << endl << "Usage: batoh input_file output_file" << endl;
		if (argc == 1)
		{
            //cerr << "No help..." << endl;
		  /*

			cerr << endl << "Input file structure:" << endl
				  <<"board_dimension_x,board_dimension_y" << endl
				  <<"tower_pos_x,tower_pos_y" << endl
				  <<"pawn_conut" << endl
				  <<"panw_pos_x,pawn_pos_y" << endl
				  <<"...pawn_count_times" << endl ;
		  */
		}

		exit (2);
	}

	//opens file
	printf("Opening files");
	FILE *input_file, *output_file;
	if ((input_file = fopen(argv[1], "rt")) == NULL)
	{
		//cerr << "Cannot open data input file." << endl;
		exit (1);
	}

	if ((output_file = fopen(argv[2], "at")) == NULL)
	{
		//cerr << "Cannot open result output file." << endl;
		exit (1);
	}
    fprintf (output_file, "Instance_id   items    value    bag_state   brute_time;    he_items    he_value   he_state   he_time\n");
    printf("... ok!\n");

    //time accounting variables
    time_t iteration_start, iteration_end, total_start, total_end;
    double brute, heur, total;
    time (&total_start);

    //printf("Starting iterations.\n");
    //assume that each input file holds 50 instances!!
    int iteration = 0;  //needs to be here because of scope
    for (; iteration < ITERATIONS; iteration++)
    {

        //read isntance specifications
        int instance_id, i, c;
        if ( !(fscanf (input_file, "%i %i %i ", &instance_id, &i, &c)) )
        {
            //cerr << "Error reading a bag specification from input file.";
            exit(3);
        }

        const int items = i;
        const bag_property capacity = c;
        const bag states = ((bag) 2)<<i; //retyping is important!
        item_list my_items;

        //read items
        printf("Reading item definitions, iteration %i, instance id: %i.\n", iteration, instance_id);
        for (i = 0; i < items; i ++)
        {
            my_items[i] = ReadItem(input_file);
            //printf("(%i,%i) ", my_items[i].mass, my_items[i].value);
        }
        printf("%i read!\n", i);

        if (iteration != (ITERATIONS-1))
            fscanf (input_file, "\n");

        //variables
        bag best_state = 0;
        bag_property total_value = 0, total_mass = 0;

        ////////////////////////////////////////////////////////////////////////
        //brute force solution - search ALL states
        printf("Starting brute force computation.\n");
        time (&iteration_start);
        for (bag my_bag = 0; my_bag < states; my_bag++)
        {
            //printf("%i ", instance_id);
            //check if current state is better than bet known so far
            const  bag_property cm = CalcMass(my_items, my_bag, items), cv = CalcValue (my_items, my_bag, items);
            if ((cm <= capacity) && (cv > total_value))
            {
                //printf("Solution: value: %i mass: %i.\n", cv, cm);
                total_value = cv;
                total_mass = cm;
                best_state = my_bag;
            }
            //printf(".");
        }

        //time accounting
        time (&iteration_end);

        brute = difftime (iteration_end,iteration_start);
        printf("Brute force time %.1fs.\n", brute);

        ////////////////////////////////////////////////////////////////////////
        //heuristics

        unsigned short int ordered[MAX_ITEMS], tmp[MAX_ITEMS];

        //clear tmp
        for (unsigned short int tmp_i = 0; tmp_i < items; tmp_i++)
            tmp[tmp_i] = 0;

        //create a sorted array of pointers to items
        //use find highest algorithm
        for (unsigned short int k = 0; k < items; k++)
        {
            bag_property cur_max_val = 0;
            unsigned short int cur_p = 0;

            //find most valuable element, which was not chosen yet
            for (unsigned short int l = 0; l < items; l++)
            {
                const bag_property val_mas = my_items[l].value / my_items[l].mass;
                if ((val_mas > cur_max_val) && (tmp[l] == 0))
                {
                    cur_max_val = val_mas ;
                    cur_p = l;
                    tmp[l] = 1;
                }

            }

            //store the pointer to the element
            ordered [k] = cur_p;
        }

        //now we have array of pointers sorted according to value/mass.
        //run ourr trivial heuristics
        bag my_bag = 0;
        unsigned short int h_i = 0;
        for (unsigned short int k = 0; k < items; k++)
        {
            //stop adding items if bag would be full
            if (CalcMass(my_items, AddItem (my_items, my_bag, ordered[k]), items) > capacity)
            {
                break;
            }
            else
            {
                my_bag = AddItem (my_items, my_bag, ordered[k]);
                h_i++;
            }

        }

        //accounting
        const  bag_property cv = CalcValue (my_items, my_bag, items);


        //time for heuristics
    	time (&total_end);
        heur = difftime (total_end, iteration_end);

      //fprintf (output_file, "Instance_id   items    value    bag_state   brute_time;    he_items    he_value   he_state   he_time\n");
	    fprintf (output_file, "       %4i      %2i     %4i     %8X       %5.1fs           %2i        %4i   %8X    %5.1fs\n", instance_id, items, total_value, best_state, brute, h_i,  cv , my_bag, heur);

        //limit 5 minutes per file
    	total = difftime (total_end,total_start);
        if ( total > 300 ) break;

    }

    fprintf (output_file, "Iterations: %i, Time: %4.1fs.\n", iteration, total);

    fclose (input_file);
    fclose (output_file);

    return 0;

}