//tab-width: 4
/*
 * knapsack_problem.cc
 * Copyright (C) Tobias Hermann 2010 <daiw@gmx.net>
 * 
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <exception>
#include <sstream>
#include <cstdlib>

#include <sys/time.h>
#include <stdio.h>
#include <unistd.h>

using namespace std;

#define _WeightType int
#define _ValueType int

template <typename TWeight, typename TValue>
class Item
{
public:
	Item( string name, TWeight weight, TValue value ) : _name (name), _weight (weight), _value (value) {};
	TWeight Weight() { return _weight; }
	TWeight Value() { return _value; }
	void Show( int minNumberLength );
	string Name() { return _name; }
	~Item() {};
	
private:
	string _name;
	TWeight _weight;
	TValue _value;
};


template <typename TWeight, typename TValue>
void Item<TWeight, TValue>::Show( int minNumberLength )
{
	cout << "Item " << Name() << ": weight=" << setw( minNumberLength ) << setfill( '0' ) << Weight() << ", value=" << setw( minNumberLength ) << setfill( '0' ) << Value() << endl;
}

template <typename TWeight, typename TValue>
class Container
{
public:
	typedef Item <TWeight, TValue> TItem;
	typedef vector <TItem> TContent;
	Container( string name ) : _name (name) {};
	virtual ~Container() {};
	void Add( Item <TWeight, TValue> item) { _content.push_back( item ); }
	void Remove( size_t number )
	{
		if ( ( number < 1 ) || ( number > _content.size() ) )
			throw string( "Container::Get: number out of range." );
		_content.erase( _content.begin() + (number - 1) );
	}
	TItem Get( size_t number )
	{
		if ( ( number < 1 ) || ( number > _content.size() ) )
			throw string( "Container::Get: number out of range." );
		return _content.at( number-1 );
	}
	size_t Size() { return _content.size(); };
	void Clear() { _content.clear(); }
	void Show( int minNumberLength );
	string Name() { return _name; }
	Container<TWeight, TValue> &operator=( const Container<TWeight, TValue>& );

protected:
	TContent _content;
private:
	string _name;
};

template <typename TWeight, typename TValue>
Container<TWeight, TValue> &Container<TWeight, TValue>::operator=( const Container<TWeight, TValue> &other )
{
	_content = other._content;
	return *this;
}


template <typename TWeight, typename TValue>
class Knapsack : public Container<TWeight, TValue>
{
public:
	Knapsack( string name ) : Container<TWeight, TValue> ( name ) {};
	void Show( int minNumberLength );
	TValue Value();
	TWeight Weight();
};

template <typename TWeight, typename TValue>
void Container<TWeight, TValue>::Show( int minNumberLength )
{
	cout << endl << "--------" << Name() << "-------- start" << endl;
	for ( size_t i = 1; i <= _content.size(); i++ )
	{
		Get( i ).Show( minNumberLength );
	}
	cout << "--------" << Name() << "-------- end" << endl;
}

template <typename TWeight, typename TValue>
void Knapsack<TWeight, TValue>::Show( int minNumberLength )
{
	Container<TWeight, TValue>::Show( minNumberLength );
	cout << "--------" << Container<TWeight, TValue>::Name() << " - summary -------- start" << endl;
	cout << "Summarized weight: " << Weight() << endl;
	cout << "Summarized value: " << Value() << endl;
	cout << "--------" << Container<TWeight, TValue>::Name() << " - summary -------- end" << endl;
}

template <typename TWeight, typename TValue>
TWeight Knapsack<TWeight, TValue>::Weight()
{
	TWeight weight = 0;
	for ( size_t i = 1; i <= Container<TWeight, TValue>::Size(); i++ )
	{
		weight += Container<TWeight, TValue>::Get(i).Weight();
	}
	return weight;
}

template <typename TWeight, typename TValue>
TValue Knapsack<TWeight, TValue>::Value()
{
	TValue value = 0;
	for ( size_t i = 1; i <= Container<TWeight,TValue>::Size(); i++ )
	{
		value += Container<TWeight,TValue>::Get(i).Value();
	}
	return value;
}


int stringToInt( string str )
{
	stringstream stream;
	stream << str;
	int result;
	stream >> result;
	return result;
}

string IntToString( int i )
{
	stringstream stream;
	stream << i;
	string result;
	stream >> result;
	return result;
}


void recursive_knapsack_solve_NP( const _WeightType maximumWeight,
	Container<_WeightType, _ValueType> &source,
	Knapsack<_WeightType, _ValueType> &best,
	Knapsack<_WeightType, _ValueType> &current,
	const size_t sourcePos = 0,
	size_t depth = 1 )
{
	if ( sourcePos > source.Size() )
		return;

	if ( sourcePos > 0 )
		current.Add( source.Get( sourcePos ) );

	if ( current.Weight() <= maximumWeight )
	{
		if ( current.Value() > best.Value() )
		{
			best = current;
		}
		for ( size_t pos = sourcePos; pos < source.Size(); ++pos )
		{	
			recursive_knapsack_solve_NP( maximumWeight, source, best, current, pos+1, depth+1 );
			current.Remove( current.Size() );
		}
	}
}


// todo: Insert P-solution here. =)
void iterative_knapsack_solve_P( const _WeightType maximumWeight,
	Container<_WeightType, _ValueType> &source,
	Knapsack<_WeightType, _ValueType> &best,
	Knapsack<_WeightType, _ValueType> &current,
	const size_t sourcePos = 0,
	size_t depth = 1 )
{
	if ( sourcePos > source.Size() )
		return;

	if ( sourcePos > 0 )
		current.Add( source.Get( sourcePos ) );

	if ( current.Weight() <= maximumWeight )
	{
		if ( current.Value() > best.Value() )
		{
			best = current;
		}
		for ( size_t pos = sourcePos; pos < source.Size(); ++pos )
		{	
			iterative_knapsack_solve_P( maximumWeight, source, best, current, pos+1, depth+1 );
			current.Remove( current.Size() );
		}
	}
}


bool compare_knapsack_solvers( size_t numberOfItems )
{
	int minNumberLength = 1;
	typedef _WeightType TWeight;
	typedef _ValueType TValue;
	typedef Knapsack <TWeight, TValue> TKnapsack;
	typedef Item <TWeight, TValue> TItem;
	TKnapsack source( "Source Container" );
	TKnapsack bestKnapsack_NP( "best Knapsack NP" );
	TKnapsack currentKnapsack_NP( "current Knapsack" );
	TKnapsack bestKnapsack_P( "best Knapsack P" );
	TKnapsack currentKnapsack_P( "current Knapsack P" );

	for ( size_t item = 0; item < numberOfItems; ++item )
	{
		source.Add( TItem( IntToString( item ), rand() % 10000 + 1,  rand() % 10000 + 1 ) );
	}

	TWeight maximumWeight = rand() % ( source.Weight() ) + 1;

	source.Show( minNumberLength );
	cout << "maximumWeight: " << maximumWeight << endl;

	{
		struct timeval start, end;
		long mtime, seconds, useconds;    
		gettimeofday(&start, NULL);

		recursive_knapsack_solve_NP( maximumWeight, source, bestKnapsack_NP, currentKnapsack_NP );

		gettimeofday(&end, NULL);
		seconds  = end.tv_sec  - start.tv_sec;
		useconds = end.tv_usec - start.tv_usec;
		mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

		bestKnapsack_NP.Show( minNumberLength );

		cout << "Elapsed time: " << mtime << " milliseconds" << endl;
	}

	{
		struct timeval start, end;
		long mtime, seconds, useconds;    
		gettimeofday(&start, NULL);

		iterative_knapsack_solve_P( maximumWeight, source, bestKnapsack_P, currentKnapsack_P );

		gettimeofday(&end, NULL);
		seconds  = end.tv_sec  - start.tv_sec;
		useconds = end.tv_usec - start.tv_usec;
		mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

		bestKnapsack_P.Show( minNumberLength );

		cout << "Elapsed time: " << mtime << " milliseconds" << endl;
	}

	return ( ( bestKnapsack_NP.Weight() == bestKnapsack_P.Weight() ) &&
		( bestKnapsack_NP.Value() == bestKnapsack_P.Value() ) );
}


int main( int argc, char** argv )
{
	if ( argc != 3 )
	{
		cout << "numberOfItems? numberOfRuns?" << endl;
		return 1;
	}

	try
	{
		srand ( time(NULL) );
		size_t numberOfItems = stringToInt( argv[1] );
		size_t numberOfRuns  = stringToInt( argv[2] );
		for ( size_t run = 1; run <= numberOfRuns; ++run )
		{
			cout << endl << endl << "Run " << run << endl;
			if ( !compare_knapsack_solvers( numberOfItems ) )
			{
				cout << "P != NP :(" << endl;
				return 2;
			}
			else
			{
				cout << "P = NP ;-)" << endl;
			}
		}
	}
	catch( string &ex )
	{
		cout << "Exception: " << ex << endl;
	}
	return 0;
}