#include <cstdlib>
#include <fstream>
#include <sstream>
#include <vector>
#include <deque>
#include <numeric>
#include <iostream>
#include "colors.hpp"
#include "perform.hpp"

std::vector<unsigned int> maxWeightMatching(const std::deque<std::pair<std::pair<unsigned int,unsigned int>,unsigned long long> >& edgeWeights);

template<class Type>
struct AlwaysTrue {
  bool operator()(const Type&) const {return true;}
};

template<class Type>
struct Identity {
  Type operator()(const Type& type) const {return type;}
};

class SchedulePenalties {
  const unsigned int numPlayers;
  const unsigned int numPairings;
  const bool byeFlag;
  std::vector<std::vector<unsigned long long> > triangle;
  SchedulePenalties(const unsigned int numPlayers_) :
    numPlayers(numPlayers_),
    numPairings(numPlayers_/2),
    byeFlag(numPlayers_%2!=0),
    triangle(std::vector<std::vector<unsigned long long> >(numPlayers_)) {}

  unsigned long long maxPenalty() const
  {
    unsigned long long result=0;
    for (unsigned int player1=0;player1<numPlayers;++player1) {
      const unsigned int rowSize=triangle[player1].size();
      for (unsigned int player2=0;player2<rowSize;++player2)
        result=std::max(result,triangle[player1][player2]);
    }
    return result;
  }

  template<class WeightModification,class ByeCondition>
  std::vector<unsigned int> maxWeightMatching(const WeightModification& weightModification,const ByeCondition& byeCondition) const
  {
    std::deque<std::pair<std::pair<unsigned int,unsigned int>,unsigned long long> > edgeWeights;
    for (unsigned int player1=1;player1<numPlayers;++player1)
      for (unsigned int player2=0;player2<player1;++player2)
        edgeWeights.push_back(std::make_pair(std::make_pair(player2,player1),weightModification(triangle[player1][player2])+1));
    if (byeFlag)
      for (unsigned int player=0;player<numPlayers;++player)
        if (triangle[player].size()>player && byeCondition(player))
          edgeWeights.push_back(std::make_pair(std::make_pair(player,numPlayers),weightModification(triangle[player][player])+1));
    return ::maxWeightMatching(edgeWeights);
  }

  unsigned long long totalWeight(const std::vector<unsigned int>& pairings) const
  {
    unsigned long long result=0;
    for (unsigned int player1=0;player1<pairings.size();++player1) {
      const unsigned int player2=pairings[player1];
      if (player2<player1)
        result+=(player1==numPlayers) ?
          triangle[player2][player2] :
          triangle[player1][player2];
    }
    return result;
  }

  void compressPairings()
  {
    unsigned long long offset=std::numeric_limits<unsigned long long>::max();
    for (unsigned int player1=1;player1<numPlayers;++player1)
      for (unsigned int player2=0;player2<player1;++player2)
        offset=std::min(offset,triangle[player1][player2]);
    for (unsigned int player1=1;player1<numPlayers;++player1)
      for (unsigned int player2=0;player2<player1;++player2)
        triangle[player1][player2]-=offset;
  }

  void compressByes()
  {
    unsigned long long offset=std::numeric_limits<unsigned long long>::max();
    for (unsigned int player=0;player<numPlayers;++player)
      if (triangle[player].size()>player) { // bye allowed
        const unsigned long long byePenalty=triangle[player][player];
        if (byePenalty==0)
          return;
        else
          offset=std::min(offset,byePenalty);
      }
    for (unsigned int player=0;player<numPlayers;++player)
      if (triangle[player].size()>player) // bye allowed
        triangle[player][player]-=offset;
  }

  friend std::vector<unsigned int> bestSchedule(
    const std::vector<unsigned int>& plays,
    const std::vector<int>& losses,
    const std::vector<std::vector<unsigned int> >& orderedEncounters);
};

template<class Type,class Comparator>
class ElementComparison {
  const std::vector<Type>& vector;
  const Type value;
public:
  ElementComparison(const std::vector<Type>& vector_,Type value_) :
    vector(vector_),
    value(value_) {}
  bool operator()(unsigned int index) const {return Comparator()(vector[index],value);}
};

std::vector<unsigned int> bestSchedule(
  const std::vector<unsigned int>& plays,
  const std::vector<int>& losses,
  const std::vector<std::vector<unsigned int> >& orderedEncounters)
{
  SchedulePenalties schedulePenalties(plays.size());

  if (schedulePenalties.numPlayers==0)
    return std::vector<unsigned int>();

  std::vector<std::pair<unsigned int,unsigned int> > lossPlayerPairs;
  lossPlayerPairs.reserve(schedulePenalties.numPlayers);
  for (unsigned int player=0;player<schedulePenalties.numPlayers;++player)
    lossPlayerPairs.push_back(std::make_pair(losses[player],player));
  sort(lossPlayerPairs.begin(),lossPlayerPairs.end()); // stable because of second element sorting

  std::vector<int> newRanks(schedulePenalties.numPlayers);

  unsigned int minLossDiff=std::numeric_limits<unsigned int>::max();
  unsigned int maxEqualLossDiff=0;
  unsigned int equalLossDiff=0;
  for (unsigned int newRank=0;newRank<schedulePenalties.numPlayers;++newRank) {
    const std::pair<unsigned int,unsigned int>& lossPlayerPair=lossPlayerPairs[newRank];
    newRanks[lossPlayerPair.second]=newRank;
    if (newRank<schedulePenalties.numPlayers-1) {
      const unsigned int lossDiff=lossPlayerPairs[newRank+1].first-lossPlayerPair.first;
      if (lossDiff==0) {
        ++equalLossDiff;
        minLossDiff=0;
        continue;
      }
      else
        minLossDiff=std::min(minLossDiff,lossDiff);
    }
    if (equalLossDiff>maxEqualLossDiff)
      maxEqualLossDiff=equalLossDiff;
    equalLossDiff=0;
  }
  unsigned int minPlays=std::numeric_limits<unsigned int>::max();
  unsigned int maxPlays=0;
  std::vector<std::vector<unsigned int> > lossDifferences(schedulePenalties.numPlayers);
  std::vector<std::vector<unsigned int> > unorderedEncounters(schedulePenalties.numPlayers);
  unsigned int minEncounters=std::numeric_limits<unsigned int>::max();
  unsigned int maxEncounters=0;
  const unsigned int maxEqualLossScore=maxEqualLossDiff*maxEqualLossDiff;
  for (int player1=schedulePenalties.numPlayers-1;player1>=0;--player1) {
    schedulePenalties.triangle[player1].reserve(player1);
    lossDifferences           [player1].reserve(player1);
    unorderedEncounters       [player1].reserve(player1);
    for (int player2=0;player2<player1;++player2) {
      const int rankDifference=newRanks[player1]-newRanks[player2];
      unsigned long long pairingPenalty;
      if (losses[player1]==losses[player2])
        pairingPenalty=maxEqualLossScore-rankDifference*rankDifference;
      else
        pairingPenalty=rankDifference*rankDifference-1;
      schedulePenalties.triangle[player1].push_back(pairingPenalty);
      lossDifferences           [player1].push_back(abs(losses[player1]-losses[player2]));

      const unsigned int numEncounters=orderedEncounters[player1][player2]+
                                       orderedEncounters[player2][player1];
      unorderedEncounters[player1].push_back(numEncounters);
      minEncounters=std::min(minEncounters,numEncounters);
      maxEncounters=std::max(maxEncounters,numEncounters);
    }
    minPlays=std::min(minPlays,plays[player1]);
    maxPlays=std::max(maxPlays,plays[player1]);
  }

  if (schedulePenalties.byeFlag) {
    for (unsigned int player=0;player<schedulePenalties.numPlayers;++player)
      if (plays[player]==maxPlays)
        schedulePenalties.triangle[player].push_back(0);
    unsigned int previousPlayerWithBye=0;
    while (plays[previousPlayerWithBye]<maxPlays)
      ++previousPlayerWithBye;
    const unsigned long long byePenalty=
      schedulePenalties.totalWeight(
        schedulePenalties.maxWeightMatching(
          Identity<unsigned long long>(),
          AlwaysTrue<unsigned int>()))-
      schedulePenalties.totalWeight(
        schedulePenalties.maxWeightMatching(
          std::bind1st(std::minus<unsigned long long>(),schedulePenalties.maxPenalty()),
          AlwaysTrue<unsigned int>()))+1;
    unsigned int playerCount=1;
    for (unsigned int player=previousPlayerWithBye+1;player<schedulePenalties.numPlayers;++player)
      if (plays[player]==maxPlays) {
        schedulePenalties.triangle[player][player]=byePenalty*playerCount;
        previousPlayerWithBye=player;
        ++playerCount;
      }
  }
  const unsigned int minLoss=lossPlayerPairs.front().first;
  const unsigned int maxLoss=lossPlayerPairs.back ().first;
  const unsigned int maxLossDiff=maxLoss-minLoss;
  for (unsigned int lossDiff=minLossDiff+1;lossDiff<=maxLossDiff;++lossDiff) {
    const unsigned long long pairingPenalty=
      schedulePenalties.totalWeight(
        schedulePenalties.maxWeightMatching(
          Identity<unsigned long long>(),
          AlwaysTrue<unsigned int>()))-
      schedulePenalties.totalWeight(
        schedulePenalties.maxWeightMatching(
          std::bind1st(std::minus<unsigned long long>(),schedulePenalties.maxPenalty()),
          AlwaysTrue<unsigned int>()))+1;
    bool pairingCompression=true;
    for (unsigned int player1=1;player1<schedulePenalties.numPlayers;++player1)
      for (unsigned int player2=0;player2<player1;++player2) {
        unsigned long long& currentPairingPenalty=schedulePenalties.triangle[player1][player2];
        if (lossDiff==lossDifferences[player1][player2])
          currentPairingPenalty+=pairingPenalty;
        else if (currentPairingPenalty==0)
          pairingCompression=false;
      }
    if (pairingCompression)
      schedulePenalties.compressPairings();
  }
  if (schedulePenalties.byeFlag && minLoss<maxLoss) {
    unsigned int newRank=0;
    while (plays[lossPlayerPairs[newRank].second]<maxPlays)
      ++newRank;
    unsigned int earlierLossScore=lossPlayerPairs[newRank].first;
    if (earlierLossScore<maxLoss) {
      while (lossPlayerPairs[newRank].first==earlierLossScore)
        ++newRank;
      unsigned int lossScore=lossPlayerPairs[newRank].first;
      while (true) {
        const unsigned long long upperbound=
          schedulePenalties.totalWeight(
            schedulePenalties.maxWeightMatching(
              Identity<unsigned long long>(),
              ElementComparison<int,std::equal_to<int> >(losses,earlierLossScore)));
        const unsigned long long lowerbound=
          schedulePenalties.totalWeight(
            schedulePenalties.maxWeightMatching(
              std::bind1st(std::minus<unsigned long long>(),schedulePenalties.maxPenalty()),
              ElementComparison<int,std::equal_to<int> >(losses,lossScore)));
        if (upperbound>=lowerbound) {
          const unsigned long long byePenalty=upperbound-lowerbound+1;
          bool possibleByeCompression=false;
          do {
            const unsigned int player=lossPlayerPairs[newRank].second;
            if (plays[player]==maxPlays) {
              unsigned long long& currentByePenalty=schedulePenalties.triangle[player][player];
              if (currentByePenalty==0)
                possibleByeCompression=true;
              currentByePenalty+=byePenalty;
            }
            ++newRank;
          } while (newRank<schedulePenalties.numPlayers && lossPlayerPairs[newRank].first==lossScore);
          if (possibleByeCompression)
            schedulePenalties.compressByes();
        }
        else
          do
            ++newRank;
          while (newRank<schedulePenalties.numPlayers && lossPlayerPairs[newRank].first==lossScore);
        if (lossScore<maxLoss) {
          earlierLossScore=lossScore;
          lossScore=lossPlayerPairs[newRank].first;
        }
        else
          break;
      }
    }
  }
  for (unsigned int numEncounters=minEncounters+1;numEncounters<=maxEncounters;++numEncounters) {
    const unsigned long long pairingPenalty=
      schedulePenalties.totalWeight(
        schedulePenalties.maxWeightMatching(
          Identity<unsigned long long>(),
          AlwaysTrue<unsigned int>()))-
      schedulePenalties.totalWeight(
        schedulePenalties.maxWeightMatching(
          std::bind1st(std::minus<unsigned long long>(),schedulePenalties.maxPenalty()),
          AlwaysTrue<unsigned int>()))+1;
    bool pairingCompression=true;
    for (unsigned int player1=1;player1<schedulePenalties.numPlayers;++player1)
      for (unsigned int player2=0;player2<player1;++player2) {
        unsigned long long& currentPairingPenalty=schedulePenalties.triangle[player1][player2];
        if (numEncounters==unorderedEncounters[player1][player2])
          currentPairingPenalty+=pairingPenalty;
        else if (currentPairingPenalty==0)
          pairingCompression=false;
      }
    if (pairingCompression)
      schedulePenalties.compressPairings();
  }
  if (schedulePenalties.byeFlag && minPlays<maxPlays) {
    for (unsigned int player=0;player<schedulePenalties.numPlayers;++player)
      if (plays[player]<maxPlays)
        schedulePenalties.triangle[player].push_back(0);
    const unsigned long long upperbound=
      schedulePenalties.totalWeight(
        schedulePenalties.maxWeightMatching(
          Identity<unsigned long long>(),
          ElementComparison<unsigned int,std::equal_to<unsigned int> >(plays,maxPlays)));
    const unsigned long long lowerbound=
      schedulePenalties.totalWeight(
        schedulePenalties.maxWeightMatching(
          std::bind1st(std::minus<unsigned long long>(),schedulePenalties.maxPenalty()),
          ElementComparison<unsigned int,std::less<unsigned int> >(plays,maxPlays)));
    if (upperbound>=lowerbound) {
      const unsigned long long byePenalty=upperbound-lowerbound+1;
      for (unsigned int player=0;player<schedulePenalties.numPlayers;++player)
        if (plays[player]<maxPlays)
          schedulePenalties.triangle[player][player]=byePenalty;
    }
  }
  return schedulePenalties.maxWeightMatching(
    std::bind1st(std::minus<unsigned long long>(),schedulePenalties.maxPenalty()),
    AlwaysTrue<unsigned int>());
}

template<class Type1,class Type2>
struct greater_second {
  bool operator()(const std::pair<Type1,Type2>& lhs,const std::pair<Type1,Type2>& rhs) {
    return lhs.second>rhs.second;
  }
};

std::vector<unsigned int> ratingsToRanks(
  const std::vector<long double>& ratings,
  const std::vector<bool>& removed,
  const bool randomizeTies)
{
  std::vector<std::pair<unsigned int,long double> > playerRatingPairs;
  const unsigned int numPlayers=ratings.size();
  for (unsigned int player=0;player<numPlayers;++player)
    if (!removed[player])
      playerRatingPairs.push_back(std::make_pair(player,ratings[player]));
  if (randomizeTies)
    random_shuffle(playerRatingPairs.begin(),playerRatingPairs.end());
  stable_sort(playerRatingPairs.begin(),playerRatingPairs.end(),greater_second<unsigned int,long double>());
  std::vector<unsigned int> rankToPlayer;
  for (std::vector<std::pair<unsigned int,long double> >::const_iterator i=playerRatingPairs.begin();
       i!=playerRatingPairs.end();++i)
    rankToPlayer.push_back(i->first);
  return rankToPlayer;
}

std::vector<int> bestSchedule(
  unsigned int numLives,
  const long double virtualGameWeight,
  const bool randomizeSeeds,
  const std::vector<unsigned int>& losses,
  const std::vector<std::vector<unsigned int> >& orderedEncounters,
  const std::vector<std::vector<unsigned int> >& ratedDefeats,
  std::vector<bool>& removed
)
{
  std::vector<long double> performanceRatings=calculatePerformanceRatings(virtualGameWeight,ratedDefeats);

  const unsigned int numPlayers=losses.size();

  unsigned int minLosses=std::numeric_limits<unsigned int>::max();
  for (unsigned int player=0;player<numPlayers;++player)
    if (!removed[player])
      minLosses=std::min(minLosses,losses[player]);

  numLives=std::max(numLives,minLosses+1);

  for (unsigned int player=0;player<numPlayers;++player)
    if (losses[player]>=numLives)
      removed[player]=true;

  std::vector<unsigned int> rankToPlayer=ratingsToRanks(performanceRatings,removed,randomizeSeeds);

  const unsigned int remainingPlayers=rankToPlayer.size();
  std::vector<unsigned int> playsByRank(remainingPlayers);
  std::vector<int> lossesByRank;
  lossesByRank.reserve(remainingPlayers);
  std::vector<std::vector<unsigned int> > orderedEncountersByRank(remainingPlayers,std::vector<unsigned int>(remainingPlayers));

  for (unsigned int rank1=0;rank1<remainingPlayers;++rank1) {
    const unsigned int player1=rankToPlayer[rank1];
    lossesByRank.push_back(losses[player1]);
    for (unsigned int rank2=0;rank2<remainingPlayers;++rank2)
      orderedEncountersByRank[rank1][rank2]=orderedEncounters[player1][rankToPlayer[rank2]];
    for (unsigned int player2=0;player2<numPlayers;++player2)
      playsByRank[rank1]+=orderedEncounters[player1][player2]+
                          orderedEncounters[player2][player1];
  }

  const std::vector<unsigned int> rankedPairings=bestSchedule(playsByRank,lossesByRank,orderedEncountersByRank);

  std::vector<int> result(numPlayers,-1);
  for (unsigned int rank1=0;rank1<remainingPlayers;++rank1) {
    const unsigned int player1=rankToPlayer[rank1];
    const unsigned int rank2=rankedPairings[rank1];
    if (rank2==remainingPlayers)
      result[player1]=player1;
    else
      result[player1]=rankToPlayer[rank2];
  }

  return result;
}

int main(int argc,char* argv[])
{
  if (argc<6)
    return EXIT_FAILURE;

  std::string line,goldPlayer,silverPlayer;
  ColorHistory colorHistory;
  for (int arg=1;arg<argc-5;++arg) {
    std::ifstream past(argv[arg]);
    while (std::getline(past,line)) {
      if (line.empty())
        continue;
      std::stringstream ss;
      ss<<line;
      if (!(ss>>goldPlayer))
        continue;
      if (!(ss>>silverPlayer))
        abort();
      colorHistory.addGame(goldPlayer,silverPlayer);
    }
  }

  std::ifstream ratingFile(argv[argc-4]);
  std::vector<std::string> players;
  std::map<std::string,unsigned int> playerToID;
  while (std::getline(ratingFile,line)) {
    if (line.empty())
      continue;
    std::stringstream ss;
    ss<<line;
    std::string player;
    if (!(ss>>player))
      continue;
    playerToID.insert(make_pair(player,players.size()));
    players.push_back(player);
  }

  const unsigned int numPlayers=players.size();

  std::vector<bool> removed(numPlayers);
  std::vector<unsigned int> losses(numPlayers);
  std::vector<std::vector<unsigned int> > orderedEncounters(numPlayers,std::vector<unsigned int>(numPlayers)),
                                          ratedDefeats(orderedEncounters);
  std::ifstream tournament(argv[argc-2]);
  while (std::getline(tournament,line)) {
    if (line.empty())
      continue;
    std::stringstream ss;
    ss<<line;
    if (!(ss>>goldPlayer))
      continue;
    if (playerToID.find(goldPlayer)==playerToID.end())
      abort();
    const unsigned int goldID=playerToID[goldPlayer];
    if (!(ss>>silverPlayer)) {
      // player removed from tournament
      removed[goldID]=true;
      continue;
    }
    if (playerToID.find(silverPlayer)==playerToID.end())
      abort();
    const unsigned int silverID=playerToID[silverPlayer];
    ++orderedEncounters[goldID][silverID];
    colorHistory.addGame(goldPlayer,silverPlayer);
    std::string winner;
    if (!(ss>>winner)) {
      // double forfeit
      ++losses[goldID];
      ++losses[silverID];
    }
    else if (winner!=goldPlayer && winner!=silverPlayer)
      abort();
    else {
      const unsigned int loserID=(winner==goldPlayer ? silverID : goldID);
      ++losses[loserID];
      /*if (!(ss>>winner))*/ { // no dummy fourth word indicating forfeit (DISABLED)
        const unsigned int winnerID=playerToID[winner];
        ++ratedDefeats[winnerID][loserID];
      }
    }
  }

  long double virtualGameWeight;
  std::stringstream ss;
  ss<<argv[argc-3];
  ss>>virtualGameWeight;

  srand(time(0));
  const std::vector<int> pairings=bestSchedule(
    atoi(argv[argc-1]), // number of lives
    virtualGameWeight,
    atoi(argv[argc-5])!=0, // randomize seeds
    losses,
    orderedEncounters,
    ratedDefeats,
    removed
  );

  for (int player1=0;player1<static_cast<int>(numPlayers);++player1) {
    const int player2=pairings[player1];
    if (player1==player2)
      std::cout<<players[player1]<<'\n';
    else if (player1<player2 /*&& player2!=-1*/) {
      const int color=colorHistory.colorFirstPlayer(players[player1],players[player2]);
      if (color>0 || (color==0 && (rand()%2)==0)) {
          goldPlayer=players[player1];
        silverPlayer=players[player2];
      }
      else {
        silverPlayer=players[player1];
          goldPlayer=players[player2];
      }
      std::cout<<goldPlayer<<'\t'<<silverPlayer<<'\n';
      //colorHistory.addGame(goldPlayer,silverPlayer);
    }
  }
}