#include <algorithm>
#include <limits>

#include "Libraries/Network/TemporalNetwork.h"
#include "Libraries/Params/Parameters.h"

using namespace std;

/**
 *void Print( const set < shared_ptr < string >, cmp_str_ptr >& seed )
 *
 * Simple helper function. Prints the members of a set on the same line (with following newline).
 *
 *@param seed Vertices to print
 */
void Print( const set < shared_ptr < string >, cmp_str_ptr >& seed ){
  set < shared_ptr < string > >::const_iterator it_s = seed.begin();
  while (it_s != seed.end() ){
    cout << **it_s << "|";
    ++it_s;
  }
  cout << endl;
}

/**
 *double CalcDensity( const int& size, const double& Win, const double& Wout, const double& lambda )
 *
 *   Function to calculate the density of a given set of vertices
 *
 *@param size Number of vertices in the set
 *@param Win Total weight of edges between two vertices in the set
 *@param Wout Total weight of edges with only 1 vertex in the set
 *@param lambda Weight value between the two parts of the density measure
 *
 *@return Density of set of vertices
 */
double CalcDensity( const int& size, const double& Win, const double& Wout, const double& lambda ){
  if ( size < 1 ) return numeric_limits < double >::min();

  double partA = ( ( 1 - lambda ) * ( Win / ( Win + Wout ) ) );

  double partB = (lambda * (( 2 * Win) / (size * (size - 1))));
  if ( size == 1 ) partB = lambda;

  return  partA + partB;
}

/**
 *map < double, set < shared_ptr < string >, cmp_str_ptr > > Components ( set < shared_ptr < string >, cmp_str_ptr > seed, shared_ptr < Network > G, double lambda )
 *
 *  Splits a set of vertices into the connected components that it is made up of. Associates each component
 * with its density value.
 *
 *@param seed Set of vertices to split
 *@param G Network structure
 *@param lambda Value for density calculation (see CalcDensity)
 *
 *@return A map associating density values with the components
 */
map < double, set < shared_ptr < string >, cmp_str_ptr > > Components ( set < shared_ptr < string >, cmp_str_ptr > seed, shared_ptr < Network > G, double lambda ) {
  map < double, set < shared_ptr < string >, cmp_str_ptr > > result;

  set < shared_ptr < string >, cmp_str_ptr >::iterator it_s, it_u, it_v;
  set < shared_ptr < string >, cmp_str_ptr > seen;
  double win = 0, wout = 0;

  for ( it_s = seed.begin(); it_s != seed.end(); it_s++ ){                   //Go through each vertex in set
    if ( seen.find (*it_s) != seen.end() ) continue;                         //If already assigned to partition, skip

    win = 0;
    wout = 0;
    set < shared_ptr < string >, cmp_str_ptr > component, to_check;
    to_check.insert(*it_s);                                                  //Initialize stats for new component

    //Keep expanding the component based off the neighborhoods of members until no new members can be added
    while ( to_check.size() != 0 ){
      //Add the first vertex to component
      it_u = to_check.begin();
      component.insert(*it_u);
      seen.insert(*it_u);
      map < shared_ptr < string >, double, cmp_str_ptr > N = G->GetNeighborhood(*it_u);
      to_check.erase(it_u);

      //Go through vertex neighborhodd to find vertices that are also in the component while tracking density measures
      map < shared_ptr < string >, double, cmp_str_ptr >::iterator it_n;
      for ( it_n = N.begin(); it_n != N.end(); it_n++ ){
	if ( ( seen.find(it_n->first) == seen.end() ) && (seed.find(it_n->first) != seed.end())){
	  to_check.insert(it_n->first);
	  win += it_n->second;
	} else {
	  wout += it_n->second;
	}
      }
    }

    //document results
    result.insert(pair < double, set < shared_ptr < string >, cmp_str_ptr > > (CalcDensity(component.size(), win, wout, lambda), component));
  }

  //Return full results
  return result;
}

/**
 *void ExpandSeed ( set < shared_ptr < string >, cmp_str_ptr >& seed, shared_ptr < Network > G, double lambda )
 *
 * Main portion of CIS. Takes a seed and iteratively adds neighbors/removes members in order to maximize the
 *  CalcDensity() value of the set of vertices. Only rule is that the component must remain connected. If it
 *  becomes disconnected, the component that has the highest independant density is taken.
 *
 *@param seed Set of vertices to start from
 *@param G Network structure
 *@param lambda Value for density calculation
 */
void ExpandSeed ( set < shared_ptr < string >, cmp_str_ptr >& seed, shared_ptr < Network > G, double lambda ) {
  cout << *(*seed.begin())<<",,,";
  map < shared_ptr < string > , pair < double, double >, cmp_str_ptr > members, neighbors;
  set < shared_ptr < string >, cmp_str_ptr > fringe;
  set < shared_ptr < string >, cmp_str_ptr >::iterator it_s;
  map < shared_ptr < string >, double, cmp_str_ptr >::iterator it_n;
  map < shared_ptr < string >, pair < double, double >, cmp_str_ptr >::iterator it_d, it_d2;

  double seed_win = 0, seed_wout = 0;

  for ( it_s = seed.begin(); it_s != seed.end(); it_s++ ){  //Tally members of the seed, calculating individual
                                                            // Win and Wout measures and noting neighborhood
    map < shared_ptr < string > , double, cmp_str_ptr > N = G->GetNeighborhood ( *it_s );
    double Win = 0, Wout = 0;
    for ( it_n = N.begin(); it_n != N.end(); it_n++ ){
      if ( seed.find ( it_n->first ) != seed.end() ){     //If the neighbor is also in the seed, increase weight_in
	Win += it_n->second;
	seed_win += it_n->second;
      } else {                                            //Else increase weight out
	Wout += it_n->second;
	seed_wout += it_n->second;
	fringe.insert( it_n->first);
      }
    }

    members.insert(pair < shared_ptr < string >, pair < double, double > > (shared_ptr <string> (*it_s), pair < double, double > (Win, Wout)));
    //cout << **it_s << " : " << Win << " " << Wout << endl;
  }

  seed_win /= 2.0;  //Internal edges were counted twice (assumed undirected)

  //cout << "Fringe: " << endl;

  for ( it_s = fringe.begin(); it_s != fringe.end(); it_s++ ){ //Tally same information for neighborhood
    map < shared_ptr < string > , double, cmp_str_ptr > N = G->GetNeighborhood ( *it_s );
    double Win = 0, Wout = 0;
    for ( it_n = N.begin(); it_n != N.end(); it_n++ ){
      if ( seed.find ( it_n->first ) != seed.end() ){
	Win += it_n->second;
      } else {
	Wout += it_n->second;
      }
    }

    neighbors.insert(pair < shared_ptr < string >, pair < double, double > > (shared_ptr <string> (*it_s), pair < double, double > (Win, Wout)));
    //cout << **it_s << " : " << Win << " " << Wout << endl;
  }

  bool changed = true;

  srand(time(NULL));

  //cout << endl << " NEW SEED " << endl << endl;

  //While the seed is changing, add new members and remove poor members
  while ( changed ){
    changed = false;
    vector < shared_ptr < string > > to_check;
    vector < set < shared_ptr < string >, cmp_str_ptr > >  order_by_degree;
    set < shared_ptr < string >, cmp_str_ptr >::iterator it_deg;

    for ( it_d = neighbors.begin(); it_d != neighbors.end(); it_d++ ){
      int deg = G->Degree(it_d->first);
      if ( order_by_degree.size() < deg + 1 ) order_by_degree.resize(deg + 1);
      order_by_degree[deg].insert(it_d->first);
    }

    for (int k = 0; k < order_by_degree.size(); k++){
      for ( it_deg = order_by_degree[k].begin(); it_deg != order_by_degree[k].end(); it_deg++ ){
	to_check.push_back(*it_deg);
      }
    }

    /*for ( it_d = neighbors.begin(); it_d != neighbors.end(); it_d++ ){
      to_check.push_back(it_d->first);
    }

    random_shuffle ( to_check.begin(), to_check.end() );   ///Get the neighborhood in a random order*/

    for ( unsigned int i = 0; i < to_check.size(); i++ ){ // Go through all the neighbors
      it_d = neighbors.find( to_check[i] );

      //cout << *to_check[i] << " to be checked for addition : " << seed_win << " " << seed_wout << " " << it_d->second.first << " " << it_d->second.second << " " << CalcDensity(seed.size(), seed_win, seed_wout, lambda) << " " <<  CalcDensity(seed.size() + 1, seed_win + it_d->second.first, seed_wout + it_d->second.second - it_d->second.first, lambda) << endl;

      if ( CalcDensity(seed.size(), seed_win, seed_wout, lambda) < CalcDensity(seed.size() + 1, seed_win + it_d->second.first, seed_wout + it_d->second.second - it_d->second.first, lambda) ) {
	//If the density would increase by includeing the vertex - do it
	//cout << "...Added" << endl;
	changed = true; //Mark the change in seed
	seed_win += it_d->second.first;
	seed_wout = seed_wout - it_d->second.first + it_d->second.second;
	seed.insert(it_d->first);  //Update seed
	members.insert(pair < shared_ptr < string >, pair < double, double > > (it_d->first, it_d->second));
	neighbors.erase( to_check[i] ); //Update local trackers

	//UPDATE MEMBER AND NEIGHBOR LISTS
	// The Win and Wout values of vertices connected to the added vertex have changed...
	map < shared_ptr < string >, double, cmp_str_ptr > N = G->GetNeighborhood(to_check[i]);

	for (it_n = N.begin(); it_n != N.end(); it_n++){
	  if ( (it_d2 = members.find( it_n->first ) ) != members.end() ){ //Update member
	    it_d2->second.first += it_n->second;
	    it_d2->second.second -= it_n->second;
	  } else if ( (it_d2 = neighbors.find( it_n->first ) ) != neighbors.end() ) { //Update current neighbor
	    it_d2->second.first += it_n->second;
	    it_d2->second.second -= it_n->second;
	  } else { //Add new neighbor
	    map < shared_ptr < string >, double, cmp_str_ptr > N2 = G->GetNeighborhood(it_n->first);
	    map < shared_ptr < string >, double, cmp_str_ptr >::iterator it_d3;
	    double newWin = 0, newWout = 0;
	    for ( it_d3 = N2.begin(); it_d3 != N2.end(); it_d3++){
	      if ( members.find ( it_d3->first ) != members.end() ) newWin += it_d3->second;
	      else newWout += it_d3->second;
	    }

	    neighbors.insert(pair < shared_ptr < string >, pair < double, double > > (it_n->first, pair < double, double > (newWin, newWout)));
	  }
	}
      }

      /*Print ( seed );
      for ( it_d2 = members.begin(); it_d2 != members.end(); it_d2++ ){
	cout << *(it_d2->first) << "|";
      }
      cout << endl;*/
    }

    //REPEAT FOR MEMBERS (reversing mathematical signs where necessary, of course)
    to_check.clear();
    order_by_degree.clear();

    for ( it_d = members.begin(); it_d != members.end(); it_d++ ){
      int deg = G->Degree(it_d->first);
      if ( order_by_degree.size() < deg + 1 ) order_by_degree.resize(deg + 1);
      order_by_degree[deg].insert(it_d->first);
    }

    for (int k = 0; k < order_by_degree.size(); k++){
      for ( it_deg = order_by_degree[k].begin(); it_deg != order_by_degree[k].end(); it_deg++ ){
	to_check.push_back(*it_deg);
      }
    }

    /* for ( it_d = members.begin(); it_d != members.end(); it_d++ ){
      to_check.push_back(it_d->first);
    }
    random_shuffle ( to_check.begin(), to_check.end() );*/

    for ( unsigned int i = 0; i < to_check.size(); i++ ){
      it_d = members.find( to_check[i] );

      //cout << *to_check[i] << " to be checked for removal : " << seed_win << " " << seed_wout << " " << it_d->second.first << " " << it_d->second.second << " " << CalcDensity(seed.size(), seed_win, seed_wout, lambda) << " " <<  CalcDensity(seed.size() + 1, seed_win + it_d->second.first, seed_wout + it_d->second.second - it_d->second.first, lambda) << endl;

      if ( CalcDensity(seed.size(), seed_win, seed_wout, lambda) < CalcDensity(seed.size() - 1, seed_win - it_d->second.first, seed_wout - it_d->second.second + it_d->second.first, lambda) ) {
	//cout << "...Removed" << endl;
	changed = true;
	seed_win -= it_d->second.first;
	seed_wout = seed_wout + it_d->second.first - it_d->second.second;
	seed.erase(it_d->first);
	neighbors.insert(pair < shared_ptr < string >, pair < double, double > > (it_d->first, it_d->second));
	members.erase( to_check[i] );

	//UPDATE MEMBER AND NEIGHBOR LISTS
	map < shared_ptr < string >, double, cmp_str_ptr > N = G->GetNeighborhood(to_check[i]);

	for (it_n = N.begin(); it_n != N.end(); it_n++){
	  if ( (it_d2 = members.find( it_n->first ) ) != members.end() ){ //Update member
	    it_d2->second.first -= it_n->second;
	    it_d2->second.second += it_n->second;
	  } else if ( (it_d2 = neighbors.find( it_n->first ) ) != neighbors.end() ) { //Update current neighbor
	    it_d2->second.first -= it_n->second;
	    it_d2->second.second += it_n->second;
	  } //No new neighbors can be added to consider when removing members
	}
      }
    }

    //Get best component to move forward with
    //map < double, set < shared_ptr < string >, cmp_str_ptr > > comps = Components(seed, G, lambda);
    //seed = (comps.begin())->second;

    //Print ( seed );
  }
}

/**
 *void Print( const set < shared_ptr < string >, cmp_str_ptr >& seed )
 *
 * Simple helper function. Prints the members of a set on the same line (with following newline).
 *
 *@param seed Vertices to print
 */
void Print( const set < shared_ptr < string >, cmp_str_ptr >& seed, ofstream& fout, const string delim ){
  set < shared_ptr < string > >::const_iterator it_s = seed.begin();

  fout << **it_s;

  ++it_s;
  while (it_s != seed.end() ){
    fout << delim << **it_s;
    ++it_s;
  }
  fout << endl;
}


/**
 *Insertion point for CIS
 */
int main ( int argc, char** argv ){
  //Get command line params
  Parameters P;
  P.Read(argc, argv);

  string inputfile, outputfile, delimiters, seed_file, seed_delim, output_delim;
  bool directed, given_seeds;
  double lambda;

  P.set < string > (&inputfile, "i", "network.dat");
  P.set < string > (&outputfile, "o", "clusters.dat");
  P.set < string > (&delimiters, "dl", "|");
  P.set < string > (&seed_file, "s", "seeds.dat");
  P.set < string > (&seed_delim, "sdl", "|");
  P.set < double > (&lambda, "l", 0);
  P.set < string > (&output_delim, "odl", "|");

  P.boolset(&given_seeds, "s");
  P.boolset(&directed, "dir");

  if ( argc < 2 ) {
    cout << "Usage:\n\t./cis -i network -o output -dl delimiter -s seed file -l lambda value" << endl;
    return 0;
  }

  //Load the network
  TemporalNetwork T;
  shared_ptr < Network > G ( T.AddNetwork(inputfile, delimiters, directed) );
  set < set < shared_ptr < string >, cmp_str_ptr >, cmp_set_str > results;

  // Either read seeds from file or go through each vertex as seed.
  // Expand each seed and record the result
  if ( given_seeds ) {
    ifstream fin;
    openFileHarsh( &fin, seed_file );

    vector < string > fields;

    while ( fline_tr ( &fin, &fields, seed_delim ) ){
      set < shared_ptr < string >, cmp_str_ptr > seed;
      for ( unsigned int i = 0; i < fields.size(); i++ ){
	seed.insert(shared_ptr < string > ( new string ( fields[i] ) ) );
      }

      ExpandSeed ( seed, G, lambda );
      results.insert(seed);
    }
  } else {
    set < string >::const_iterator it_v = T.getFirstVertex();
    while (it_v != T.getLastVertex()){
      set < shared_ptr < string >, cmp_str_ptr > seed;
      seed.insert(shared_ptr < string > ( new string ( *it_v ) ) );

      ExpandSeed ( seed, G, lambda );
      cout <<"!!!"<<seed.size()<<"\t:";
      for(auto str:seed){
        cout << *str <<",";
      }
      cout << endl;
      results.insert(seed);

      //cout << seed.size() << endl;
      ++it_v;
    }
  }

  for(auto iter_tmp = results.begin(); iter_tmp!= results.end(); ++iter_tmp){
    for(auto iter_tmp2 = (*iter_tmp).begin(); iter_tmp2!=(*iter_tmp).end(); ++ iter_tmp2){
      cout << *(*iter_tmp2)<<",";
    }
    cout <<endl;
  }
  //Print resulting communities
  set < set < shared_ptr < string >, cmp_str_ptr >, cmp_set_str >::iterator it_ss;
  ofstream fout ( outputfile.c_str() );
  for (it_ss = results.begin(); it_ss != results.end(); it_ss++){
    Print ( *it_ss, fout, output_delim );
  }
  fout.close();

  return 0;
}
