// GroupOutputs.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <time.h>


using namespace std;

#include "../../Kernel/kernelincludes.h"
#include "../../Apps/BOOM/FC_Min.h"

void Help()
{
		cerr << "Syntax: GroupOutputs [options] source.pla" << endl;
		cerr << "   Options: " << endl;
		cerr << "            -g n       Make n groups" << endl;
		cerr << "            -omax n    Make groups, so that each group will have n outputs at most" << endl;
		cerr << "            -iters n   Perform n FC-Min iterations. 1 is default" << endl;
		cerr << "            -rnd       Perform random grouping" << endl;
		cerr << "            -name      Use names in the grouping file, instead of ordinary numbers" << endl;
}

list< list<unsigned int> > MakeGrouping( PLA &src, unsigned int groups, unsigned int iters )
{
	unsigned int i, j, k;
	unsigned int outputs;
	unsigned int members;
	PLA *pool;
	FC_Min *FC_alg;
	vector< vector<unsigned int> > G;
	list<Term>::iterator ti;
	vector<bool> assigned;
	unsigned int i1, i2;
	unsigned int mx;
	list< list<unsigned int> > grouping;
	list<unsigned int> group;
	list<unsigned int>::iterator gi; 
	unsigned int numassigned;
	vector<unsigned int> i1_candidates;
	vector<unsigned int> i2_candidates;

	outputs = src.outputs();
	members = outputs/groups;
	if ( outputs % groups != 0 ) members++;
//	if ( members < 2 ) throw RuntimeException( "GroupOutputs: Grouping is menaningless" );
	pool = new PLA( src.inputs(), outputs, PLA_type("f") );
	pool->setUnique();

	FC_alg = new FC_Min( &src, pool );
	if ( FC_alg == NULL) throw RuntimeException( "GroupOutputs: Not enough memory" );

		// Compute implicants by FC-Min
	for ( i = 0; i < iters; i++ )
		FC_alg->Run();

		// Compute G-Matrix
	G.resize(outputs);
	for ( i = 0; i < outputs; i++ )
		G[i].resize(outputs, 0);

	for ( ti = pool->getData()->begin(); ti != pool->getData()->end(); ti++ )
		for ( j = 0; j < outputs; j++ )
			for ( k = j+1; k < outputs; k++ )
				if ( (*ti).isOM_1(j) && (*ti).isOM_1(k) ) {
					G[j][k]++;
					G[k][j]++;
				}

		// make statistics
	i = 0;
	for ( j = 0; j < outputs; j++ )
		for ( k = j+1; k < outputs; k++ )
			if ( G[j][k] != 0 ) i++;
	cerr << (float)i/(outputs*(outputs-1)) << endl;


		// Make grouping
	assigned.resize( outputs, false );
	numassigned = 0;
	do {
		group.clear();
		if ( outputs - numassigned != 1 ) {
			// Find maximum in G to generate the first element in a group
			mx = 0;
			i1_candidates.clear();
			i2_candidates.clear();
			for ( j = 0; j < outputs; j++ )
				if ( !assigned[j] )
					for ( k = j+1; k < outputs; k++ )
						if ( !assigned[k] ) {
							if ( G[j][k] == mx ) {
								i1_candidates.push_back(j);
								i2_candidates.push_back(k);
							}
							else if ( G[j][k] > mx ) {
								i1_candidates.clear();
								i2_candidates.clear();
								i1_candidates.push_back(j);
								i2_candidates.push_back(k);
								mx = G[j][k];
							}
						}
			i = rand() % i1_candidates.size();
			i1 = i1_candidates[i];
			i2 = i2_candidates[i];
			group.push_back(i1);
			group.push_back(i2);
			assigned[i1] = true;
			assigned[i2] = true;
			numassigned += 2;

			// Fill the group
			while ( group.size() != members && numassigned != outputs ) {
				mx = 0;
				i1_candidates.clear();
				for ( gi = group.begin(); gi != group.end(); gi++ )
					for ( j = 0; j < outputs; j++ )
						if ( !assigned[j] && (*gi) != j ) {
							if ( G[(*gi)][j] == mx )
								i1_candidates.push_back(j);
							else if ( G[(*gi)][j] > mx ) {
								i1_candidates.clear();
								i1_candidates.push_back(j);
								mx = G[(*gi)][j];
							}
						}
				i1 = i1_candidates[rand() % i1_candidates.size()];
				group.push_back(i1);
				assigned[i1] = true;
				numassigned++;
			}
		} else {			// just one left
			for ( i = 0; i < outputs; i++ )
				if ( !assigned[i] ) {
					group.push_back(i);
					assigned[i] = true;
					numassigned++;
				}
		}
		grouping.push_back(group);
	} while ( numassigned != outputs );
	return grouping;
}

list< list<unsigned int> > MakeRandomGrouping( PLA &src, unsigned int groups )
{
	unsigned int outputs;
	unsigned int members;
	vector<bool> assigned;
	unsigned int i1;
	list< list<unsigned int> > grouping;
	list<unsigned int> group;
	unsigned int numassigned;

	outputs = src.outputs();
	members = outputs/groups;
//	if ( members < 2 ) throw RuntimeException( "GroupOutputs: Grouping is menaningless" );
	if ( outputs % groups != 0 ) members++;

		// Make grouping
	assigned.resize( outputs, false );
	numassigned = 0;
	do {
		group.clear();
		// Fill the group
		while ( group.size() != members && numassigned != outputs ) {
			i1 = rand() % outputs;
			while ( assigned[i1] ) {
				i1++;
				i1 %= outputs;
			}
			group.push_back(i1);
			assigned[i1] = true;
			numassigned++;
		}
		grouping.push_back(group);
	} while ( numassigned != outputs );
	return grouping;
}


int main(int argc, char* argv[])
{
    PLA source;
	list< list<unsigned int> > grouping;
	unsigned int groups = 1, iters = 1, omax = 0;
	list< list<unsigned int> >::iterator grit;
	list<unsigned int>::iterator groupit;
	bool rnd = false;
	int i;
	unsigned int j;
	bool name = false;
	char *iname = NULL;
	
	srand( (unsigned)time( NULL ) );
	
	cerr << "GroupOutputs 1.3, (c) July 2010 by Petr Fiser" << endl << endl;
    if ( argc < 3 ) {
		Help();
		exit(1);
    }

	i = 1;
	while ( i < argc ) {
		if ( strcmp( argv[i], "-rnd" ) == 0 ) {
			rnd = true;
			i++;
		}
		else if ( strcmp( argv[i], "-name" ) == 0 ) {
			name = true;
			i++;
		}
		else if ( strcmp( argv[i], "-g" ) == 0 ) {
			i++;
			groups = atoi(argv[i]);
			i++;
		}
		else if ( strcmp( argv[i], "-omax" ) == 0 ) {
			i++;
			omax = atoi(argv[i]);
			i++;
		}
		else if ( strcmp( argv[i], "-iters" ) == 0 ) {
			i++;
			iters = atoi(argv[i]);
			i++;
		}
		else if ( argv[i][0] != '-' && iname == NULL ) {
			iname = argv[i];
			i++;
		}
		else {
			Help();
			exit(1);
		}
    }

	if ( groups == 0 || iters == 0 || iname == NULL ) {
		Help();
		exit(1);
    }

	try {
        source.LoadPLA(iname);
    } catch (IOException e) {
            cerr << e.GetMsg() << endl;
            exit(1);
    }

	if ( omax != 0 ) {
		groups = source.outputs()/omax;
		if ( source.outputs() % omax != 0 ) groups++;
	}

	if ( name ) source.NameVars();

	if ( !rnd )	grouping = MakeGrouping( source, groups, iters );
	else grouping = MakeRandomGrouping( source, groups );

	for ( grit = grouping.begin(); grit != grouping.end(); grit++ ) {
		j = 0;
		for ( groupit = (*grit).begin(); groupit != (*grit).end(); groupit++ ) {
			if ( !name ) cout << (*groupit);
			else cout << source.getOName(*groupit);
			if ( j++ != (*grit).size()-1 ) cout << " ";
		}
		cout << endl;
	}
    return 0;
}
