#include<stdlib.h>
#include<iostream>
#include<fstream>
#include<string>
#include <queue>
#include <stack>
#include <stdio.h>
// yes I could use just one i/o lib
using namespace std;


// As per specification, the project has to be able to grow to an 
// arbitrary amount of items. MAX_ITEMS describes the size of the
// appropriate arrays and must be changed at compile time.
// (dynamically created arrays had their pointers corrupted when 
// their parent object was in the priority queue, so static sized
// arrays were used

#define MAX_ITEMS 65536		
//the above bound comes from the fixed value for the boolean array TODO REMOVE LIMITATION

typedef long ITEM_MASS;
typedef long INDEX_TYPE;


using namespace std;

// ******************************************************************
// * CLASS : item													*
// * Container object with all the data for a particular item		*
// ******************************************************************
class item {
public:
//	float getRatio();
	ITEM_MASS getWeight();
    ITEM_MASS getCost();
//	ITEM_MASS getNumber();
	void setData(ITEM_MASS);
private:
	ITEM_MASS weight;
	ITEM_MASS cost;
//	float ratio;
//	ITEM_MASS number;
};

// ******************************************************************
// * CLASS : backpack												*
// * Container object with all the data for an entire knapsack		*
// * Full declaration follows, partial declare here for key			*
// ******************************************************************
class backpack;

// ******************************************************************
// * CLASS : key													*
// * Container object with all the data for the equivalent of a node*
// * on the state space tree										*
// * To allow data to remain private (and decrease the need of data *
// * such as max_weight and total_items to be passed along with		*
// * every function call, a pointer to the containing backpack is	*
// * instead implemented.											*
// ******************************************************************
class key {
public:
	void initKey( backpack *);
	void flagNext();
	void addCurItem();
	bool doneItems();
	float getBound();
	bool checkItem(INDEX_TYPE);
	ITEM_MASS getWeight();
	ITEM_MASS getValue();
private:
	void calcBound();
	bool inserted[MAX_ITEMS];
	INDEX_TYPE nextitem;
	ITEM_MASS cur_weight;
	ITEM_MASS cur_value;
	float upper_bound;
	backpack *myBackpack;
};

// ******************************************************************
// * STRUCT : item_comparator										*
// * Functor for comparing the ratio between items					*
// ******************************************************************
struct item_comparator {
	bool operator()( item left, item right ) const 
//	{ return ( left.getRatio() < right.getRatio() ) ; }  
	{ return 0 ; }  //same ratio to all, don't actually do a compare!
} ;

// ******************************************************************
// * STRUCT : key_comparator										*
// * Functor for comparing the bound between items					*
// ******************************************************************
struct key_comparator {
	bool operator()( key left, key right ) const 
	{ return ( left.getBound() < right.getBound() ) ; } 
} ;

// ******************************************************************
// * CLASS : backpack												*
// * Container object with all the data for an entire knapsack		*
// ******************************************************************
class backpack {
public:
	void initBackpack(INDEX_TYPE, ITEM_MASS);
	void putItem(ITEM_MASS);//, ITEM_MASS);
	void store_item_array();
	void branch_and_bound(int,ITEM_MASS);
	ITEM_MASS get_totalItems();
	ITEM_MASS get_maxWeight();
	item get_Item(INDEX_TYPE);
private:
	priority_queue< item, vector<item> , item_comparator> item_queue;
	item *item_array;
	priority_queue< key, vector<key>, key_comparator> key_queue;
	INDEX_TYPE totalItems;
	ITEM_MASS maxWeight;
	long addnodeCount, worknodeCount;
};



// ******************************************************************
// * FUNCTION : initKey		IN : CLASS key							*
// * Initalizes a key, setting the backpack pointer and inital		*
// * values then calculating the bound.								*
// ******************************************************************
void key::initKey(backpack *theCaller){
	this->myBackpack = theCaller;
	this->nextitem=0;
	this->cur_weight=0;
	this->cur_value=0;
	this->calcBound();
}

// ******************************************************************
// * FUNCTION : flagNext		IN : CLASS key						*
// * Modifies the key by setting the next item as not inserted but	*
// * as processed, then updates the bound.							*
// ******************************************************************
void key::flagNext(){
	this->inserted[this->nextitem]=0;
	nextitem++;
	this->calcBound();
}

// ******************************************************************
// * FUNCTION : addCurItem		IN : CLASS key						*
// * Follows up flagNext by actually marking the last item as		*
// * inserted, adding values and weights, then recalcing the bound.	*
// ******************************************************************
void key::addCurItem(){
	nextitem--;
	this->inserted[this->nextitem]=1;
	this->cur_value  += (this->myBackpack->get_Item(this->nextitem)).getCost();
	this->cur_weight += (this->myBackpack->get_Item(this->nextitem)).getWeight();
	nextitem++;
	this->calcBound();
}

// ******************************************************************
// * FUNCTION : doneItems		IN : CLASS key						*
// * Returns TRUE if all the items have been processed				*
// ******************************************************************
bool key::doneItems(){
	return ( this->myBackpack->get_totalItems() == this->nextitem );
}

// ******************************************************************
// * FUNCTION : getBound		IN : CLASS key						*
// * Returns the bound.												*
// ******************************************************************
float key::getBound(){
	return this->upper_bound;
}

// ******************************************************************
// * FUNCTION : calcBound		IN : CLASS key						*
// * Calculates the bound. If there are no more items, the bound	*
// * remains unchanged. Else, perform the calcuations.				*
// * If the weight is over max_weight, set the bound to 0			*
// ******************************************************************
void key::calcBound(){
	float temp;
	if (this->doneItems()) {
		temp = 0;
	}
	else {
		temp = (float)((this->myBackpack->get_maxWeight()) - cur_weight);
//		temp = temp * (this->myBackpack->get_Item(this->nextitem)).getRatio(); (ratio = 1!)
	}
	this->upper_bound = cur_value + temp;

	// What about if the bag is overloaded?
	if (this->cur_weight > this->myBackpack->get_maxWeight()){
		this->upper_bound = 0;		// invalidate it, will never reach 0 in bound
	}
}


// ******************************************************************
// * FUNCTION : checkItem		IN : CLASS key						*
// * Checks if a given item is listed as inserted.					*
// ******************************************************************
bool key::checkItem(INDEX_TYPE num) {
	return (this->inserted[num]);
}

// ******************************************************************
// * FUNCTION : getValue		IN : CLASS key						*
// * Gets the Value of the current key.								*
// ******************************************************************
ITEM_MASS key::getValue(){
	return this->cur_value;
}

// ******************************************************************
// * FUNCTION : getWeight		IN : CLASS key						*
// * Gets the Weight of the current key.							*
// ******************************************************************
ITEM_MASS key::getWeight(){
	return this->cur_weight;
}

// ******************************************************************
// * FUNCTION : getRatio		IN : CLASS item						*
// * Gets the Ratio for the current item.							*
// ******************************************************************
//float item::getRatio(){
//	return ratio;
//}

// ******************************************************************
// * FUNCTION : getWeight		IN : CLASS item						*
// * Gets the Weight of the current item.							*
// ******************************************************************
ITEM_MASS item::getWeight(){
	return this->weight;
}

// ******************************************************************
// * FUNCTION : getCost			IN : CLASS item						*
// * Gets the Value of the current item.							*
// ******************************************************************
ITEM_MASS item::getCost(){
	return this->cost;
}

// ******************************************************************
// * FUNCTION : getNumber		IN : CLASS item						*
// * Gets the Index of the current item.							*
// ******************************************************************
//ITEM_MASS item::getNumber(){
//	return this->number;
//}

// ******************************************************************
// * FUNCTION : setData			IN : CLASS item						*
// * Sets all the data for an item.									*
// ******************************************************************
void item::setData(ITEM_MASS weightage){ //, ITEM_MASS costage, ITEM_MASS numerage){
	this->cost = weightage; //costage;
	this->weight = weightage;
//	this->ratio = ( (float)(cost)/(float)(weight) );
//	this->ratio = 1; //ratio = 1
//	this->number = numerage;
}


// ******************************************************************
// * FUNCTION : initBackpack	IN : CLASS backpack					*
// * Initalizes the backpack values and creates the item array		*
// ******************************************************************
void backpack::initBackpack(INDEX_TYPE total, ITEM_MASS max){
	this->totalItems = total;
	this->maxWeight = max;
	item_array = new item[total];
	worknodeCount = 0;
	addnodeCount = 0;
}

// ******************************************************************
// * FUNCTION : putItem			IN : CLASS backpack					*
// * Creates an item and places it into the priority queue			*
// ******************************************************************
void backpack::putItem(ITEM_MASS weight){  //,  ITEM_MASS cost){
	item temp_item;
	temp_item.setData(weight);//,cost);//,(int)(this->item_queue.size())+1); // sometimes this starts at 2000?
	this->item_queue.push(temp_item);
}

// ******************************************************************
// * FUNCTION : store_item_array IN : CLASS backpack				*
// * Dumps the Item Queue in order into an Array for Rand. Access	*
// ******************************************************************
void backpack::store_item_array(){
	this->item_array = new item[this->totalItems];
	for ( int i = 0; this->totalItems > i; i++){
		this->item_array[i] = this->item_queue.top();
		this->item_queue.pop();
	}
}

// ******************************************************************
// * FUNCTION : get_totalItems	IN : CLASS backpack					*
// * Returns the number of items for consideration.					*
// ******************************************************************
ITEM_MASS backpack::get_totalItems(){
	return this->totalItems;
}

// ******************************************************************
// * FUNCTION : get_maxWeight	IN : CLASS backpack					*
// * Returns the maximum weight for this backpack.					*
// ******************************************************************
ITEM_MASS backpack::get_maxWeight(){
	return this->maxWeight;
}

// ******************************************************************
// * FUNCTION : get_Item		IN : CLASS backpack					*
// * Returns a particular item from the item array					*
// ******************************************************************
item backpack::get_Item(INDEX_TYPE index){
	return ( this->item_array[index] );
}

// ******************************************************************
// * FUNCTION : branch_and_bound IN : CLASS backpack				*
// * Performs Best-First-Fit Branch and Bound on this backpack		*
// * while keeping track of the nodecounts.							*
// * Create a template key with the best possible bound.			*
// * Place that key into the queue and start a loop					*
// * As long as the 'onwards' flag is TRUE, repeat:					*
// *	Take the topmost (highest bound) key out of the queue.		*
// *	If that bound has all of its items processed, clear ownards	*
// *	Else, create two keys from the original key					*
// *	One without the next item and one with.						*
// *	Place the new keys into the queue and discard the current	*
// *	Repeat														*
// * If the loop is ended, the top item on the queue is the best	*
// * possible solution for this knapsack.							*
// * Fetch all the information and print it out.					*
// ******************************************************************
void backpack::branch_and_bound(int DEBUG_MODE, ITEM_MASS targetvalue){
	key temp_key;
	
	temp_key.initKey(this);
	this->key_queue.push(temp_key);
	this->addnodeCount++;

	bool onwards = 1;

	do
	{
		temp_key = key_queue.top();
		this->key_queue.pop();
		if ( temp_key.doneItems() ) {
			onwards = 0;
		}
		else {
			this->worknodeCount++;
            temp_key.flagNext();
                this->key_queue.push(temp_key);
				this->addnodeCount++;
			temp_key.addCurItem();
			if (temp_key.getBound() != 0){
				this->key_queue.push(temp_key);
				this->addnodeCount++;
			}
		}
	}
	while (onwards);
	

	if (DEBUG_MODE) {
		printf("Case n=%2d Total possible nodes in thie state space tree is 2^%2d-1\n",this->totalItems,this->totalItems);
		printf("          Number of nodes placed in the priority queue: %6d\n",this->addnodeCount);
		printf("          Number of nodes examined/split:               %6d\n",this->worknodeCount);
/*		printf("\nObjects Chosen \n");

		printf("\t\tWeights\tValues\n");
		int totalitemsinserted = 0;
		for (int i = 0; this->totalItems > i; i++) {
			if ( temp_key.checkItem(i) ) {
				printf("\t\t%4.2f\t%4.2f\n", this->item_array[i].getWeight(), this->item_array[i].getCost());
				totalitemsinserted++; // this->item_array[i].getNumber(),   removed
			}
		}
		printf("======================================================\n");
		printf("Totals:\t%3d\t%4.2f\t%4.2f\n",totalitemsinserted, temp_key.getWeight(),  temp_key.getValue());
	//	printf("Ratio :     %2.5f\n", ((float)temp_key.getValue()/(float)temp_key.getWeight())); */
	}

	
	if ( temp_key.getWeight() == targetvalue ) {
		int totalitemsinserted = 0;
		int first=1;
		for (int i = 0; this->totalItems > i; i++) {
			if ( temp_key.checkItem(i) ) {
				if (first==0) { printf(","); } 
				else {first = 0;}                     // there has GOT to be a better way!
				printf("%d", this->item_array[i].getWeight());
			}
		}
	}
	else { printf("CANNOT FILL PALLET\n"); }
}

/*
// have to deal with non int #s

int intcomp (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}*/

void syntaxmsg(){
	printf("Usage:\n");
	printf("<program name> <input filename> <D/d>\n");
	printf("input contains a series of integers [A], comma delimited,\n\t followed by a CR and an int [B]\n");
	printf("program outputs a comma delimited list of elements of A that sum to B,\n\t or CANNOT FILL PALLET\n");
	printf("Program written for the UCLA ACM Feb 2005 Coding Competition\n");
	printf("Dervied from previous academic work written by the author\n(C) 2002-2005 Rizwan Kassim\n");
	printf("If the second argument is a D or d, verbose debugging mode will be enabled\n\n");
	return;
}

// ******************************************************************
// * FUNCTION : main												*
// * Initalizes the backpack and the items inside.					*
// * Copies those items into an array, prints out the items.		*
// * Run the branch_and_bound method.								*
// ******************************************************************
int main(int argc, char *argv[])
{
	item temp_item;
	int DEBUG_MODE = 0;

	if ( argc < 2 ) { syntaxmsg(); return 2;}
	if ( argc > 4 ) { syntaxmsg(); return 3;}
	if ( argc == 3 ) {
		if ( argv[2][0] == 'D' || argv[2][0] == 'd' ) {
		printf("Debug switch caught, outputing debug messages\n");
		DEBUG_MODE =1; 
		} else { syntaxmsg(); return 4;}
	}
		
	if (DEBUG_MODE) {
		printf("Entry into UCLA ACM Feb. 2005 Coding Competition\n");
		printf("Based on code developed (myself) for CS331 Project 4 at CSU Pomona\n"); 
		printf("Version 4\n");
		printf("All compiled / source code are (C) Rizwan Kassim 2005\n\n");
	}
	
		
	INDEX_TYPE max_inventory;
	
	ifstream inputfs;
	inputfs.open (argv[1]);
	if (!inputfs.is_open())
	  { printf("File open of %s failed!\n", argv[1]);
		syntaxmsg(); 
		return 1; }
	if (DEBUG_MODE) {
		printf("File %s Open!\n",argv[1]);
	}
	
	INDEX_TYPE length;
	inputfs.seekg (0, ios::end);
	length = inputfs.tellg();
	inputfs.seekg (0, ios::beg);
	
	max_inventory= 1 + length/2;	// Elements cannot be more than this amount
	
	char * read_buffer = (char *) malloc (length);
	ITEM_MASS * inventory = (ITEM_MASS *) malloc (length);
		// could use stack instead of array --- doesn't require malloc, more 'safe' avoids overflows, esp if 
		// input file is funky --- its better software engineering, but its slower. Given that this is a pretty
		// small system, I'll stick with the array
	inputfs.getline (read_buffer, length-1);

	char * theToken; INDEX_TYPE index = 0;
	theToken=strtok(read_buffer,",");
	// assume 1+ items
	while ( theToken != NULL ) {
		//printf("tokendebug %d %f\n",theToken,theToken);
		inventory[index] = atol(theToken);
		//printf("index %d, token %s, value %d\n",index,theToken,inventory[index]);
		index++;
		theToken = strtok (NULL,",");
		}

	INDEX_TYPE size_inventory = index; //remember this is 1 based, not 0
	
	int SUPER_MODE = 0;
	if (inventory[0]==1) { SUPER_MODE=0;}

	if (DEBUG_MODE) {
		printf("Line 1 read - %d products from warehouse\n", size_inventory);
		if (SUPER_MODE) printf("Working in Superincreasing mode!\n");
	}
	
//	qsort ( inventory, size_inventory, sizeof(int), intcomp);	// we now have a sorted list
	// NEED TRY/CATCH error handling for possible segfault locations
	inputfs.getline (read_buffer, length-1);	
	ITEM_MASS palette_size=atoi(read_buffer);
	
	if (DEBUG_MODE) {
		printf("Line 2 read - %d weight units can fit onto palette\n",palette_size);
	}
	
	inputfs.close();
	free(read_buffer);
	
	if 

	
	// ckeanup, release memeory, close files here		

	
// I could use a class to extrapolate out the file loading function like my 499 project....	
	
	backpack knapsackOne;

	knapsackOne.initBackpack(size_inventory,palette_size);
	if (DEBUG_MODE) {
		printf("init %d, %d\n",size_inventory,palette_size);
	}
	for ( INDEX_TYPE store_index=0; size_inventory>store_index;store_index++ ) {
		knapsackOne.putItem(inventory[store_index]);

		if (DEBUG_MODE) {
			printf("insert %d\n",inventory[store_index]);
		}
		
	}
	knapsackOne.store_item_array();
	free(inventory);
	knapsackOne.branch_and_bound(DEBUG_MODE,palette_size);

	printf("\n");
}




void super ( ITEM_MASS target_value , INDEX_TYPE size_inventory, int DEBUG_MODE ) {
	// input, a super increasing set, lowest to highest. 
	// the number of elements in the list [1-ordinal]
	// a target value.
	//debugmode
	
	// need to output values that sum to target
	// need another place to store. --- not another array, need LIFO structure. A stack of course. 
	// we have to count downwards during super increasing, or we could qsort the list. (not going to do that)
	
	stack<ITEM_MASS> packages_to_load;

	if (DEBUG_MODE) {
		printf("Extracting values, highest to lowest, doing reduction\n");
	}
	for ( INDEX_TYPE store_index=size_inventory-1; size_inventory<=0;store_index-- ) {
		if (DEBUG_MODE) {
			printf("value %d, is it smaller than %d? If so, subtract and store.\n",inventory[store_index],target_value);
		}
		if ( inventory[store_index] <= target_value ) {
			target_value = target_value - inventory[store_index];
			packages_to_load.push(inventory[store_index]);
		}
	}
	if ( target_value == 0 ) {
		int first = 1;
		while ( ! packages_to_load.empty() ) {
			if (first==0) { printf(","); } 
			else {first = 0;}                     // there has GOT to be a better way!			
			printf("%d",packages_to_load.top());
			packages_to_load.pop();
		}
		else { printf("CANNOT FILL PALLET\n"); }
		
		
	}




/* 
Modifications to the original branch-and-bound algorithim/approach

This program was to compute the maximum value that can be fit into a bag --- Using Levitin p380 for reference
right now. As our problem is actually a SUBSET of the given problem ,we can simplify some of the functions.
We also don't want any packs too small, but we'll let this compute, see how big the state tree is versus
an alternative algorithm.

	knapsackOne.initBackpack(5,17); // 5 total items, 17 total weight
	knapsackOne.putItem(4,1);
	knapsackOne.putItem(7,1);
	knapsackOne.putItem(5,1);
	knapsackOne.putItem(9,1);
	knapsackOne.putItem(1,1);

For given same, 2^5-1 possible nodes in tree, 14 nodes placed, 7 split.

Lets try something larger. n=10 1,2,3,4,5,6,7,8,9,10 => 18

Oooh, we can vary the max backpack item count to only use a certain amount of the items!

Whats interesting is that we can keep the various ratio calculations, as we WOULD rather insert an item of 10 lbs rather than 1
We just equate weight and value later on! (Or set a fixed ratio of 1)		
		knapsack insert (value,value)
		
		This was max 2^10-1 with only 47 nodes and 33 splits.
		
And lets try with a random set of 25 numbers!
70,76,55,17,70,77,52,81,11,31,57,47,93,53,83,33,1,59,29,33,78,79,37,26,83 ==> 200
Chose:
              1           70           70
              3           55           55
             24           26           26
             23           37           37
             17            1            1
              9           11           11
2^25-1 worst case, 142 nodes, 115 split!
real    0m0.036s
user    0m0.030s
sys     0m0.030s




then 50:
186,130,132,108,112,39,90,88,105,172,50,46,125,79,22,192,139,132,77,195,21,129,134,76,179,89,32,55,61,160,49,191,153,86,45,16,196,109,1,178,51,104,40,88,135,100,108,182,30,48  => 1470
2^50 worst case, 1826 nodes, 1443 splits
real    0m0.044s
user    0m0.062s
sys     0m0.000s


Now, lets really ramp it up so that we can see optimzation effects
n=2500! won't even care to list the numbers, no point!

Wait, we exceeded 3 minutes there (our weight size was just a guess, btw, might not actually ahve a value)
Oh, our memory bound was maxed out so it hit a loop ... it actually completed in less than a sec! God bless my processor :)
Lets bump it up to 5k, 

Case n=5000 Total possible nodes in thie state space tree is 2^5000-1
          Number of nodes placed in the priority queue:  35037
          Number of nodes examined/split:                34942

real    0m2.810s
user    0m1.843s
sys     0m0.062s


Given that this is about the largest we can hope to achieve before INTMAX because a massive issue (we should really typedefine the container class), lets see what optimizations we can make to this code!

must do 1 - 
move all the ITEM_MASSs to (other)
the ITEM_MASSs are now ITEM_TYPE, a def earlier on (we could have done typedef here too, of course)
real    0m2.928s
user    0m1.999s
sys     0m0.061s
Slight increase.

Bad things happen when we try to make it into floats, I just tired. floats can't be [] contents for an array ;p
Doing unsigned long for now.
goal 1 = stop ratio calculation and comparisons if at all possible!
real time shot up!
real    0m3.994s
user    0m2.390s
sys     0m0.046s

(that being said, timse don't seem to be consistent. CVS is storing our versions, lets plow on)

remove the comparator in the structcomparator
real    0m2.830s
user    0m2.030s
sys     0m0.015s

remove the printout of the items as inserted
real    0m1.423s
user    0m1.436s
sys     0m0.015s

remove the tracking of the item "number", we don't need to deal with it with this project.

after moved all unsigned ints to typedefs, 
typedef float ITEM_MASS;
typedef long INDEX_TYPE;

and modified the printfs to handle floating !

real    0m1.591s
user    0m1.562s
sys     0m0.000s
		
inserting a float does :
				
acm2.cpp: In function `int main(int, char**)':
acm2.cpp:410: error: no matching function for call to `backpack::putItem(
   double, int, int)'
acm2.cpp:279: error: candidates are: void backpack::putItem(float, float)
make: *** [acm2] Error 1

(and it locks up if we have a decimal in seeked value)

ok we move onwards to remove weight,value calls and replace them with just weight
we also use notepad/sed to remove half the sample knapsack calls
we realize in doing this that we've actually got 7009 elements! modifiying appropraite values!

real    0m2.627s
user    0m2.624s
sys     0m0.000s

but now it uses all 17.


Lets try an appropriately high value instead of the 50000ish we're using now. Lets say, we want ... 
600 elements of 7000, at avg value of 5000 3000000ish?

Case n=6998 Total possible nodes in thie state space tree is 2^6998-1
          Number of nodes placed in the priority queue:  70797
          Number of nodes examined/split:                69811

Totals: 114     509283.00       509283.00

then...

============================ KNAPSACK ONE ================================
Case n=6998 Total possible nodes in thie state space tree is 2^6998-1
          Number of nodes placed in the priority queue: 108848
          Number of nodes examined/split:                96391

Totals: 1002    5091283.00      5091283.00


real    0m9.526s
user    0m9.249s
sys     0m0.203s


I'm actually pretty happy with this. We havent tested a few conditions, but its time we got the file loading routine in


todo 
1) when it doesnt work
2) when its already reached stop
3) float

For superincreasing sets, its INCREDIBLY easy to do
Sort it.
if (current value < pallete size), palletsize-current value, current_value on board.
repeat until end



=== loading file now
make input float ok

reverted to base type of non float --- making the stored value float did badthings to atoi / atof (they didnt work)


we could really move the pqueue to a queue --- although don't we want to push bigger items to the top to fill it up faster?

goal 1 - lets remove the double call to the creator function, weight=value ratio=1		

		
		*/