#include "AI.h"

#include <vector>
#include <algorithm>
#include <cstdlib>
#include <iostream>

const int inf = 1e9;
const int M = 150;


int n;

bool bad [M];
vector< vector<int> > g;
vector< vector<int> > dd;
vector< vector<int> > pp;
vector<int> owner;
vector<int> monsters;
vector<int> myNodes;
vector<int> hisNodes;
vector<int> freeNodes;

vector<int> freeV;


void AI::buildGraph(World *world) {
	cerr<<"Building graph"<<endl;
	g = vector< vector<int> >(M);
	std::vector<Node*>& allNodes = world->getMap()->getNodes();
	n = allNodes.size();
	owner = vector<int>(M);
	monsters = vector<int>(M);
	myNodes.clear();
	hisNodes.clear();
	freeNodes.clear();

	for(auto& v : allNodes)
	{
		const std::vector<Node*>& neighbours = v->getNeighbours();

//		cerr<<v->getIndex()<<": ";
		for( auto& u : neighbours){
			g[v->getIndex()].push_back(u->getIndex());
//			cerr<<u->getIndex()<<" ";
		}
//		cerr<<endl;

		owner[v->getIndex()] = v->getOwner();
		if( owner[v->getIndex()] != -1 ){
			owner[v->getIndex()] = (v->getOwner() == world->getMyId());
			if(owner[v->getIndex()])
				myNodes.push_back(v->getIndex());
			else
				hisNodes.push_back(v->getIndex());
		}
		else{
			freeNodes.push_back(v->getIndex());
		}
		monsters[v->getIndex()] = v->getArmyCount();

		cerr<<v->getIndex()<<" Monsters: "<<monsters[v->getIndex()]<<" Owner: "<<v->getOwner()<<" "<<world->getMyId()<<endl;
	}

	dd = vector< vector<int> >(M, vector<int>(M) );
	pp = vector< vector<int> >(M, vector<int>(M) );

	for( int v = 0; v < n; v++ ){
		for( int u = 0; u < n; u++ )
			dd[v][u] = inf;
		for( int u : g[v] ){
			dd[v][u] = 1;
			pp[v][u] = u;
		}
	}



	for( int t = 0; t < n; t++)
		for( int v = 0; v < n; v++ )
			for( int u = 0; u < n; u++ ){
				if( dd[v][u] > dd[v][t] + dd[t][u] ){
					dd[v][u] = dd[v][t] + dd[t][u];
					pp[v][u] = pp[v][t];
				}
			}
}

int was [M];

void AI::dfs(int v){
	was[v] = 1;
	if(owner[v]==-1) freeV.push_back(v);
	for( int to : g[v] ){
		if(was[to]==1 || owner[to]==0) continue;
		dfs(to);
	}
}

void AI::reachableFree(World *world){
	freeV.clear();
	for( int i = 0; i < n; i++ ){
		if(owner[i] == 1 && !was[i]){
			dfs(i);
		}
	}
}

void AI::doTurn(World *world)
{
	cerr<<"===================="<<endl;
	for( int i = 0; i < n; i++ ) bad[i] = 0;
	buildGraph(world);
	/** Fill this method. We've presented a stupid AI as an example! **/
	/*std::vector<Node*>& allNodes = world->getMap()->getNodes();
	for(auto& kek : allNodes){
		cerr<<kek->getOwner()<<" "<<kek->getArmyCount()<<endl;
	}
		cerr<<"==========================="<<endl;*/
	for( int v : myNodes ){
		for( int u : g[v] ){
			if(monsters[v]==0) break;
			if(owner[u]==-1){
				world->moveArmy(v,u,monsters[v]);
				monsters[v]--;
				bad[v] = 1;
				cerr<<"Scout from "<<v<<" to "<<u<<endl;

				break;
			}
		}
	}

	vector<int> closest (M);

	int myTotalArmy = 0;
	int crucialDst = inf;
	for( int v : myNodes ){
		closest[v] = inf;
		if(!bad[v])
			myTotalArmy += monsters[v];
		for( int i = 0; i < n; i++ ){
			if( owner[i]==0 ){
				closest[v] = min( closest[v], dd[v][i] );
				crucialDst = min( crucialDst, closest[v] );
			}
		}
		cerr<<v<<" closest is "<<closest[v]<<" afar."<<endl;
	}

	vector<int> crucialP;
	cerr<<"Crucial: ";
	for( int v : myNodes ){
		if(closest[v] != crucialDst)
			continue;
		crucialP.push_back(v);
		cerr<<v<<" ";
	}
	cerr<<endl;

	int crucialMonsters = myTotalArmy / max(1, (int)crucialP.size());

	cerr<<"CrucialMonsters "<<crucialMonsters<<endl;

	vector<int> need (M);
	cerr<<"Need: ";
	for( int v : crucialP ){
		need[v] = max(0, crucialMonsters - monsters[v]);
		cerr<<need[v]<<" ";
	}
	cerr<<endl;


	for( int v : myNodes ){
		if(crucialP.empty()) break;
		if( closest[v]==crucialDst ) continue;
		if(bad[v]) continue;

		for( int u : g[v] ){
			if(closest[u] < closest[v]){
				world->moveArmy(v,u,monsters[v]);
				bad[v] = 1;
				break;
			}
		}
		bad[v] = 1;
	}
	for( int v : crucialP ){
		if( bad[v] ) continue;
		int myClass = 0;
		if(monsters[v]>10) myClass = 1;
		if(monsters[v]>30) myClass = 2;
		for( int u : g[v] ){
			if(owner[u]==0 && monsters[u] <= myClass ){
				world->moveArmy(v,u,monsters[v]);
				bad[v] = 1;
				break;
			}
		}

	}
}