////////////////////////////////////////////////////////////////////////////
//
// Praxis des Programmierens, Uni Greifswald, Wintersemester 2009/10,
// by Clemens Groepl, 2009-11-19
//
////////////////////////////////////////////////////////////////////////////
//
// The *longest increasing subsequence problem* is defined as follows:
// 
// We are given a sequence of numbers ( a_i | i=0,...,n-1 ),
// a_i \in \reals (just for concreteness).
// 
// The goal is to find an increasing subsequence of maximum length.
// That is, find a sequence of indices ( i_j | j=0,...,k-1 )
// such that
//   j < j'  implies   i_j < i_{j'} and a_{i_j} < a_{i_{j'}}        (*)
// and
//   k is maximal with with property (*).                          (**) 
//
// The *heaviest increasing subsequence problem* is defined similar,
// but we are additionally given a sequence of weights,
//   ( w_i | i=0,...,n-1 )
// and the goal is to find an increasing subsequence
// such that
//   \sum_{j=0}^{k-1} w_{i_j} is maximal with property (*).       (***)
//
// An O(n log n ) algorithm for the longest increasing subsequence problem
// is explained at:
// http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem
//
////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <fstream>
#include <vector>
#include <string>

////////////////////////////////////////////////////////////////////////////
// Please *do* *use* the following typedefs!
// Later we want to try out whether your solution still works
// if double is replaced by something different, e.g. std::string
//
typedef double ItemType;
typedef std::vector<ItemType> SequenceType;
typedef std::vector<int> SubsequenceIndicesType;
// typedef std::vector<SequenceType::size_type> SubsequenceIndicesType;
////////////////////////////////////////////////////////////////////////////


template < typename Container >
void print( Container const & rhs )
{
	for ( typename Container::const_iterator i = rhs.begin();; )
	{	
		std::cout << *i;
		if ( ++i == rhs.end() ) break;
		std::cout << ' ';
	}
	std::cout << std::endl;
	return;
}

void readItems(	const std::string & filename, SequenceType &sequence )
{
	sequence.clear();
	std::ifstream is(filename.c_str());
	SequenceType::value_type item;
	while (is >> item) { sequence.push_back(item); }
}

void writeItems( const std::string & filename, const SequenceType & sequence )
{
	std::ofstream os(filename.c_str());
	os.precision(15);
	for ( SequenceType::const_iterator ci = sequence.begin(); ci != sequence.end(); ++ci )
	{ os << *ci << '\n'; }
	os.flush();
}

void parseCmdline ( int argc, char **argv, std::vector<std::string> &args )
{
	args.clear();
	args.reserve(argc);
	for ( int i = 0; i < argc; ++i ) { args.push_back(argv[i]); }
	return;
}

////////////////////////////////////////////////////////////////////////////
// Your turn ...


void longest_increasing_subsequence
		(
			SubsequenceIndicesType & subsequence_indices,
			SequenceType const & input_sequence,
			std::string const & method
		)
{
	// 	clear the results vector at the beginning
	subsequence_indices.clear();

	if ( method == "student" )
	{

	}
	else if ( method == "dummy" )
	{
		// ... Just to see whether all this compiles, we put a dummy method here that picks every second one...
		for ( SequenceType::size_type i = 0; i < input_sequence.size(); ++i )
		{
			if ( i%2 ) subsequence_indices.push_back(i);
		}
	}
	else if ( method == "greedy" )
	{
		if ( !input_sequence.empty() )
		{
			subsequence_indices.push_back(0);
		}
		else
		{
			return;
		}
		for ( size_t i = 1; i < input_sequence.size(); ++i )
		{
			if ( input_sequence[i] > input_sequence[subsequence_indices.back()] )
			{
				subsequence_indices.push_back(i);
			}
		}
	}
	else if ( method == "brute_force" )
	{
#define V_brute_force(a)
// #define V_brute_force(a) a
		if ( input_sequence.size() > 32 )
		{
			std::cerr << "method brute_force available for input size <= 32 only" << std::endl;
			return;
		}
		size_t best_loop = 0;
		size_t best_size = 0;
		for ( size_t loop = 0; loop < (size_t(1)<<input_sequence.size()); ++loop )
		{
			V_brute_force(std::cout << "loop:\t" << loop << '\t');
			subsequence_indices.clear();
			for ( size_t i = 0; i < input_sequence.size(); ++i )
			{
				V_brute_force(std::cout << bool(loop & (size_t(1)<<i)));
				if ( ( loop & (size_t(1)<<i) ) &&
						( subsequence_indices.empty() ||
							input_sequence[i] > input_sequence[subsequence_indices.back()]
						) 
					 )
				{
					subsequence_indices.push_back(i);
				}
			}
			V_brute_force(std::cout << "\tsubsequence_indices.size(): " << subsequence_indices.size() << " # ");
			if ( subsequence_indices.size() > best_size )
			{
				best_loop = loop;
				best_size = subsequence_indices.size();
			}
#if V_brute_force(true||) false 
			for ( size_t i = 0; i < subsequence_indices.size(); ++i )
			{
				std::cout << ' ' << input_sequence[subsequence_indices[i]];
			}
			std::cout << std::endl
#endif
		}
		V_brute_force(std::cout << "best_loop:\t" <<  best_loop << std::endli);
		subsequence_indices.clear();
		for ( size_t i = 0; i < input_sequence.size(); ++i )
		{
			if ( ( best_loop & (size_t(1)<<i) ) &&
				 	( subsequence_indices.empty() ||
					 	input_sequence[i] > input_sequence[subsequence_indices.back()]
				 	)
				 )
			{
				subsequence_indices.push_back(i);
			}
		}
	}
	else if ( method == "fredman" )
	{
#define V_fredman(a) a
// #define V_fredman(a) a

		std::cerr << "method '" << method << "' not implemented." << std::endl;

	// omitted here, solution is in a parallel directory (suffix _solution or so) with password protection on the web

	}
	else
	{
		std::cerr << "method '" << method << "' not implemented." << std::endl;
	}

	return;
}


////////////////////////////////////////////////////////////////////////////

int main (int argc, char ** argv )
{
	std::vector<std::string> args;
	parseCmdline(argc,argv,args);

	if (args.size() < 4 )
	{
		std::cerr << "usage: " << args[0] << " <input_sequence.txt> <output_sequence.txt> <method>" << std::endl;
		std::cerr <<"Available methods: student, dummy, greedy, brute_force" << std::endl;
		return 0;
	}

	std::string const & input (args[1]);
	std::string const & output (args[2]);
	std::string const & method (args[3]);

	SequenceType input_sequence;

	readItems(input,input_sequence);

	SubsequenceIndicesType subsequence_indices;

	// your implementation, please
	longest_increasing_subsequence(subsequence_indices,input_sequence,method);

	SequenceType output_sequence;
	
	for( SubsequenceIndicesType::const_iterator iter = subsequence_indices.begin();
			 iter != subsequence_indices.end();
			 ++iter
		 )
	{
		output_sequence.push_back(input_sequence[*iter]);
	}
		
	writeItems(output,output_sequence);

	return 0;
}