#include "cop.h"
#include "graph.h"
#include <assert.h>

using namespace std;

#define BETWEEN100(x) assert( (x) >= -100 && (x) <= 100)

#undef DEBUG

void CopData::makePlan(World &w)
{
#ifdef DEBUG
  debug << __FUNCTION__ << endl;
#endif
  // Really dirty hack to ensure that we get
  // two foot mcgruffs and two car mcgruffs in qual round
  if (firstTurn)
  {
    firstTurn = false;
    int foot = 0, i = 0, car = 0;
    while (foot < 2)
    {
      if (i==w.me)
      {
        i++;
        continue;
      }
      w.cops[i].second = COP_FOOT;
      foot++;
      i++;
    }
    while (car < 2)
    {
      if (i==w.me)
      {
        i++;
        continue;
      }
      w.cops[i].second = COP_CAR;
      car++;
      i++;
    }
  }
  
  vector< vector<nodePair> > floydMap;

  vector<bool> nodeMarks(w.foot.size(), false);
  vector<bool> targetNodes(w.foot.size(), false);
  
  myPlan.clear();

  int RobPosN = naiveRobPos.size()-1;
  vector<int> numTimesUsed(w.foot.size(), false);
  debug << "makePlan: naiveRobPos=";
  for (set<int>::iterator I=naiveRobPos[RobPosN].begin(); 
      I != naiveRobPos[RobPosN].end(); ++I) 
  {
    targetNodes[*I] = true;
    debug << " "  << *I;
  }
  debug << endl;
  for (int i=0; i<COPS; i++)
  {
    vector<int> moveSeq;
    vector<vector<int> > &map = (w.cops[i].second==COP_CAR ? w.car : w.foot);
    floydMap = (w.cops[i].second==COP_CAR ? pureCarMap : pureFootMap);
    numTimesUsed[w.cops[i].first]++;
    int len = findClearPath(w.cops[i].first, targetNodes, w, map, 
        nodeMarks, moveSeq, numTimesUsed[w.cops[i].first]);
    if (len > 0) 
      myPlan.push_back( guess(i, moveSeq[0], w.cops[i].second, w.n+1) );
    else {
      // This really shouldn't happen, if it does, don't do anything
      debug << "Somehow we're currently on a guess, or we can't get through...\n";
    }
  }
}

//---------------------------------------------------------


void CopData::processInfo( World &w, vector< vector<guess> > info )
{
#ifdef DEBUG
  debug << __FUNCTION__ << endl;
#endif
  // I hope this is the copy constructor
  tracks.push_back( vector<int>( tracks[tracks.size()-1] ) );
  foreignInfo.push_back( vector<guess>() );
/*
  smellMap.clear();
  smellMap.resize(w.foot.size(), false);
  for (int i=0; i<info.size(); i++)
  {
    for (int j=0; j<info[i].size(); i++)
    {
      if (info[i][j].certainty > 0)
        smellMap[info[i][j].locId] = true;
    }
  }
  vector<vector<int> > &map = (w.cops[w.me].second==COP_CAR ? w.car : w.foot);
  if (w.smell)
  {
    for (int i=0; i<map[w.cops[w.me].first].size(); i++)
      smellMap[map[w.cops[w.me].first][i]] = true;
  } */

  /*
   * You've got to love this if statement
   */
  set<int> foreignPositiveInfo;
  set<int> tmpForeignPositiveInfo;
  set<int> foreignNegativeInfo;
  //bool firstCop = true;
  debug << "w.robberId=" << w.robberId << ", world=" << w.n << endl;
  for (unsigned int i=0; i<info.size(); ++i) {
    debug << "testing: info[i].size()=" << info[i].size() << endl;
    if (i != (unsigned int)w.me) {
      for (unsigned int j=0; j<info[i].size(); ++j) {
        if ( (info[i][j].world == w.n || info[i][j].world == w.n-1)
            && info[i][j].botId == w.robberId)
        {
          foreignInfo[foreignInfo.size()-1].push_back( info[i][j] );
          foreignInfo[foreignInfo.size()-1]
            [foreignInfo[foreignInfo.size()-1].size()-1].botId = i;
        }
        if ( (info[i][j].world == w.n || info[i][j].world == w.n+1)
             && info[i][j].botId == w.robberId
        //     && naiveRobPos.find(info[i][j].locId) != naiveRobPos.end() 
           )
        {
#ifdef DEBUG
          debug << "Updating info for world " << w.n << " node " << info[i][j].locId
                << " " << tracks[w.n+1][info[i][j].locId] << " --> " << info[i][j].certainty 
                << endl;
#endif
#if 0
          if (info[i][j].certainty > 0)
            tmpForeignPositiveInfo.insert(info[i][j].locId);
          if (info[i][j].certainty < 0)
            foreignNegativeInfo.insert(info[i][j].locId);
#endif
          tracks[w.n+1][info[i][j].locId] = info[i][j].certainty;
          if ( tracks[w.n+1][info[i][j].locId] >= 100 )
            tracks[w.n+1][info[i][j].locId] = 99;
          if ( tracks[w.n+1][info[i][j].locId] <= -100 )
            tracks[w.n+1][info[i][j].locId] = -99;
        }
      }
#if 0
      if (firstCop) {
        firstCop = false;
        foreignPositiveInfo = tmpForeignPositiveInfo;
      } else
        foreignPositiveInfo = intersectNodes(foreignPositiveInfo, 
                                            tmpForeignPositiveInfo);
#endif
    }
  }
#if 0
  set<int> tmp = intersectNodes(naiveRobPos, foreignPositiveInfo);
  if (tmp.size() > 0)
    naiveRobPos = tmp;
  for (set<int>::iterator I=foreignNegativeInfo.begin(); I != foreignNegativeInfo.end();
        ++I) 
    naiveRobPos.erase(naiveRobPos.find(*I));
#endif
}

//---------------------------------------------------------

void CopData::processState(World &w)
{
  set<int> temporary = trustedRobPos[trustedRobPos.size()-1];
  trustedRobPos.push_back(temporary);
  temporary = naiveRobPos[naiveRobPos.size()-1];
  naiveRobPos.push_back(temporary);
  int RobPosN = trustedRobPos.size()-1;

  /*
   * eh, maybe later -- right now lets just see who's obedient
  vector< vector< pair<int,ptype> > > plan;
   */
#ifdef DEBUG
  debug << __FUNCTION__ << ": Loyalty checks" << endl;
#endif
  for (unsigned int i=0; i<lastAcceptedPlan.size(); ++i)
    if ( lastAcceptedPlan[i].world == w.n-1 && lastAcceptedPlan[i].betrayal(w) )
      santasList[lastAcceptedPlan[i].botId][electedTactician]++;
  curPos = w.self().first;
  
  debug << "Tracking robber position: robberPosKnown: " << w.robberPosKnown << endl;
  tracks.push_back( vector<int>(w.car.size(), -100) );
  if ( w.robberPosKnown )
  {
    debug << "  Absolute robber position found" << endl;
    tracks[tracks.size()-1][w.robber.first] = 100;
    robberPosGuess = w.robber.first;
    set<int> tmp;
    tmp.insert(w.robber.first);
    trustedRobPos[RobPosN] = tmp;
    naiveRobPos[RobPosN] = tmp;
    return;
  }

  // Expand the possible robber locations
  set<int> tmpPRP;
  for (set<int>::iterator I=trustedRobPos[RobPosN].begin(); I != trustedRobPos[RobPosN].end();
          ++I) {
    for (unsigned int i=0; i<w.foot[*I].size(); i++) {
      tmpPRP.insert(w.foot[*I][i]);
    }
  }
  for (set<int>::iterator I=tmpPRP.begin(); I != tmpPRP.end(); ++I)
    trustedRobPos[RobPosN].insert(*I);
  tmpPRP.clear();
  for (set<int>::iterator I=naiveRobPos[RobPosN].begin(); I != naiveRobPos[RobPosN].end();
          ++I) {
    for (unsigned int i=0; i<w.foot[*I].size(); i++) {
      tmpPRP.insert(w.foot[*I][i]);
    }
  }
  for (set<int>::iterator I=tmpPRP.begin(); I != tmpPRP.end(); ++I)
    naiveRobPos[RobPosN].insert(*I);


  // Remove all nodes occupied by the police
  for (int i=0; i<COPS; i++) {
    if (trustedRobPos[RobPosN].find(w.cops[i].first) != trustedRobPos[RobPosN].end()) 
      trustedRobPos[RobPosN].erase(trustedRobPos[RobPosN].find(w.cops[i].first));
    if (naiveRobPos[RobPosN].find(w.cops[i].first) != naiveRobPos[RobPosN].end()) 
      naiveRobPos[RobPosN].erase(naiveRobPos[RobPosN].find(w.cops[i].first));
  }


  // Remove all banks (if he's on a bank, we returned from this function
  // by now)
  for (unsigned int i=0; i<w.bankPos.size(); i++) {
    if (trustedRobPos[RobPosN].find(w.bankPos[i]) != trustedRobPos[RobPosN].end())
      trustedRobPos[RobPosN].erase(trustedRobPos[RobPosN].find(w.bankPos[i]));
    if (naiveRobPos[RobPosN].find(w.bankPos[i]) != naiveRobPos[RobPosN].end())
      naiveRobPos[RobPosN].erase(naiveRobPos[RobPosN].find(w.bankPos[i]));
  }
  
  // If it stinks, intersect with all the stinky nodes; if it doesn't stink,
  // remove all nodes where he would be detected if he was there.
  if ( w.smell > 0 )
  {
    debug << "  It stinks" << endl;
    set<int> adj = w.smellyNodes(pureFootMap);
    trustedRobPos[RobPosN] = intersectNodes(trustedRobPos[RobPosN], adj);
    naiveRobPos[RobPosN] = intersectNodes(naiveRobPos[RobPosN], adj);
    for (set<int>::iterator I=adj.begin(); I != adj.end(); ++I) {
      tracks[tracks.size()-1][*I] = 100/adj.size();
      BETWEEN100(tracks[tracks.size()-1][*I]);
    }
  } else {
    w.smell = 1;
    set<int> tmp1 = w.smellyNodes(pureFootMap);
    w.smell = 2;
    set<int> tmp2 = w.smellyNodes(pureFootMap);
    set<int> adj = intersectNodes(tmp1, tmp2);
    w.smell = 0;
    for (set<int>::iterator I=adj.begin(); I != adj.end();
          ++I)  {
      if (trustedRobPos[RobPosN].find(*I) != trustedRobPos[RobPosN].end())
        trustedRobPos[RobPosN].erase(trustedRobPos[RobPosN].find(*I));
      if (naiveRobPos[RobPosN].find(*I) != naiveRobPos[RobPosN].end())
        naiveRobPos[RobPosN].erase(naiveRobPos[RobPosN].find(*I));
    }
  }
  
  // Make trustedRobPos[RobPosN] and naiveRobPos[RobPosN] 
  // consistent with the evidence
  for (unsigned int i=lastEvidenceUsed; i<w.evidence.size(); i++)
  {
    set<int> evidenceData;
    markNodesSet(w.evidence[i].first, evidenceData, w.foot, 
        (w.n - 1 - w.evidence[i].second) / 2);
    trustedRobPos[RobPosN] = intersectNodes(evidenceData, trustedRobPos[RobPosN]);
    naiveRobPos[RobPosN] = intersectNodes(evidenceData, naiveRobPos[RobPosN]);
    // Should another cop have picked this up?
    int whenLeft = w.evidence[i].second / 2;
    for (unsigned int j=whenLeft; j<w.moveHist.size(); j++)
      for (int k=0; k<COPS; k++)
        if (w.moveHist[j][k].first == w.evidence[i].first)
        {
          // We have a candidate for borging!
          copsToAccuse.push_back(k);
        }
  }
  lastEvidenceUsed = w.evidence.size();
  
  debug << "trustedRobPos[RobPosN] = ";
  for (set<int>::iterator I=trustedRobPos[RobPosN].begin(); I != trustedRobPos[RobPosN].end(); ++I) 
    debug << " " << *I;
  debug << endl;


  for (unsigned int i=0; i<w.evidence.size(); ++i)
    if ( w.robberCertain < w.evidence[i].second )
    {
      debug << "  Updating robber tracks" << endl;
      w.robberCertain = w.evidence[i].second;
      tracks[w.evidence[i].second][w.evidence[i].first] = 100;
      for (int j = w.evidence[i].second; j < w.n; ++j)
        verifyFrom( j, w );
    }
  if ( w.smell > 0 )
    return;

  debug << "  Diffusing probabilities" << endl;
  diffuseFrom( w.n-1, w );
  debug << "Tracking done" << endl;
}

//---------------------------------------------------------


// sets where the robber could be in tracks[n+1] using
// information from tracks[n]
void CopData::verifyFrom( int n, World& w )
{
  for (unsigned int i=0; i<tracks[n+1].size(); ++i)
  {
    vector<int> adj = w.foot[i]; // all paths coming into this node
    bool noPath = tracks[n][i] == -100;
    for (unsigned int j=0; j<adj.size() && noPath; ++j)
      if ( tracks[n][adj[j]] > -100 )
        noPath = false;
    if ( noPath )
      tracks[n+1][i] = -100;
  }
}

//---------------------------------------------------------


// sets where the robber could be in tracks[n+1] using
// information from tracks[n]
void CopData::diffuseFrom( int n, World& w )
{
#ifdef DEBUG
  debug << __FUNCTION__ << "( " << n << ", world:" << w.n << " )" << endl;
#endif

  for (unsigned int i=0; i<tracks[n].size(); ++i)
  {
    assert ( tracks[n][i] >= -100 && tracks[n][i] <= 100 );
    if ( tracks[n][i] > -100 && tracks[n][i] != 0 )
    {
  //    if ( tracks[n][i] > 100 )
  //      debug << "  Oh CRAP: tracks[n][i]: " << tracks[n][i] << endl;
      vector<int> adj = w.foot[i]; // all paths from this node
      BETWEEN100(tracks[n][i]);
  //    debug << "adjacent size: " << adj.size() << endl;
      int diff = tracks[n][i] / ((signed int)adj.size()+1);
      BETWEEN100(diff);
      if (diff == 0)
        diff = 1;
 //     debug << "  Diffusing probability " << diff << " to adjacent nodes" << endl;

      if (tracks[n+1][i] == -100)
        tracks[n+1][i] = 0;
      tracks[n+1][i] += diff;
      if (tracks[n+1][i] <= -100)
        tracks[n+1][i] = -99;
      if (tracks[n+1][i] >= 100)
        tracks[n+1][i] = 99;
      assert ( tracks[n+1][i] >= -100 && tracks[n+1][i] <= 100 );

  //    debug << "  Visiting ";
      for (unsigned int j=0; j<adj.size(); ++j)
      {
  //      debug << adj[j] << " ";
        if (tracks[n+1][adj[j]] == -100)
          tracks[n+1][adj[j]] = 0;
        tracks[n+1][adj[j]] += diff;
        if (tracks[n+1][adj[j]] <= -100)
          tracks[n+1][adj[j]] = -99;
        if (tracks[n+1][adj[j]] >= 100)
          tracks[n+1][adj[j]] = 99;
        assert ( tracks[n+1][j] >= -100 && tracks[n+1][j] <= 100 );
      }
  //    debug << endl;
    }
  }

}

//---------------------------------------------------------


vector<int> makeVote( World& w, std::vector< std::vector<guess> > plans )
{
  vector<int> votes;
  vector<int> scores(plans.size(), 0);

  // Evaluate each plan, and assign a score based on some heuristic
  // For the record, the opening brace should be on the same line as the for...
  for (unsigned int i = 0; i < plans.size(); ++i) 
  {
    for (unsigned int j = 0; j < plans[i].size(); ++j) 
    {
      
    }
  }

  return votes;
}

void CopData::updateRobPos(World &w)
{
  /* Retroactively update the history of possible robber locations based
   * on new trusted info we just got. If anyone turned out to be lying,
   * retroactively remove his contributions to naiveRobPos. */
  int earliestChanged = trustedRobPos.size()-1;
  vector<bool> allFalse(w.foot.size(), false);
  for (int i=trustedRobPos.size()-2; i>=0; i--)
  {
    set<int> tmpset = trustedRobPos[i];
    bool eraseFlag = false;
    for (set<int>::iterator I = trustedRobPos[i].begin();
         I != trustedRobPos[i].end(); I++)
    {
      if (!isNeighbour(*I, trustedRobPos[i+1], w, w.foot)) {
        eraseFlag = true;
        tmpset.erase(tmpset.find(*I));
      }
    }
    if (!eraseFlag)
      break;
    earliestChanged = i;
    trustedRobPos[i] = tmpset;
  }
  debug << "   survived update of trustedRobPos\n";
  for (unsigned int i = earliestChanged; i<trustedRobPos.size(); i++)
  {
    vector<set<int> > perCop;
    perCop.resize(COPS);
    for (unsigned int j=0; j<foreignInfo[i].size(); j++)
    {
      if (foreignInfo[i][j].certainty > 0 && foreignInfo[i][j].botId < COPS)
        perCop[foreignInfo[i][j].botId].insert(foreignInfo[i][j].locId);
    }
    for (int j=0; j<COPS; j++)
    {
      if (perCop[j].size() == 0)
        continue;
      set<int> tmp = intersectNodes(perCop[j], trustedRobPos[i]);
      if (tmp.size() == 0)
      {
        // We have a liar!
        debug << "Cop #" << j << " is a dirty liar!\n";
        lyingCops.insert(j);
      }
    }
  }
  debug << "   survived the lie detector\n";

  for (unsigned int i=0; i<foreignInfo.size(); i++)
    for (unsigned int j=0; j<foreignInfo[i].size(); j++)
      if (lyingCops.find(foreignInfo[i][j].botId) != lyingCops.end())
      {
        vector<guess>::iterator I = foreignInfo[i].begin() + j;
        foreignInfo[i].erase(I);
        j--;
      }
  debug << "   survived the liar erasures\n";
  
  // Recompute naiveRobPos
  naiveRobPos[0] = trustedRobPos[0];
  for (unsigned int i=1; i<trustedRobPos.size(); i++)
  {
    vector<set<int> > perCopPos;
    perCopPos.resize(COPS);
    set<int> negativeInfo;
    set<int> positiveInfo;
    for (unsigned int j=0; j<foreignInfo[i].size(); j++)
    {
      if (foreignInfo[i][j].certainty > 0)
        perCopPos[foreignInfo[i][j].botId].insert(foreignInfo[i][j].locId);
      if (foreignInfo[i][j].certainty < 0)
        negativeInfo.insert(foreignInfo[i][j].locId);
    }
    positiveInfo = perCopPos[0];
    for (int j=1; j<COPS; j++)
      positiveInfo = intersectNodes(perCopPos[j], positiveInfo);
    set<int> tmpset = naiveRobPos[i-1];
    for (set<int>::iterator I=naiveRobPos[i-1].begin(); 
          I!=naiveRobPos[i-1].end(); I++)
      for (unsigned int j=0; j<w.foot[*I].size(); j++)
        tmpset.insert(w.foot[*I][j]);
    naiveRobPos[i] = tmpset;
    naiveRobPos[i] = intersectNodes(naiveRobPos[i], trustedRobPos[i]);
    if (positiveInfo.size() > 0)
      naiveRobPos[i] = intersectNodes(naiveRobPos[i], positiveInfo);
    for (set<int>::iterator I=negativeInfo.begin(); I!=negativeInfo.end();
        I++)
    {
      set<int>::iterator I2 = naiveRobPos[i].find(*I);
      if (I2 != naiveRobPos[i].end())
        naiveRobPos[i].erase(I2);
    }
  }
  debug << "done updateRobPos\n";
  debug << "lyingCops= ";
  for (set<int>::iterator I=lyingCops.begin(); I!=lyingCops.end(); I++)
    debug << " " << *I;
  debug << endl;
}

vector<int> CopData::rankPlans(vector<vector<guess> > &plans, World &w)
{
  vector<int> retval;
  vector<int> points(plans.size(), 0);
  vector<bool> allFalse(w.foot.size(), false);
  vector<bool> guesses(w.foot.size(), false);
  vector< vector<nodePair> > floydMap;

  for (set<int>::iterator I=naiveRobPos[naiveRobPos.size()-1].begin();
       I != naiveRobPos[naiveRobPos.size()-1].end(); I++)
    guesses[*I] = true;
  
  for (unsigned int i=0; i<plans.size(); i++)
  {
    if (lyingCops.find(i) != lyingCops.end())
    {
      points[i] = -10000;
      break;
    }
    for (unsigned int j=0; j<plans[i].size(); j++)
    {
      vector<vector<int> > &map = (w.cops[plans[i][j].botId].second==COP_CAR ? w.car : w.foot);
      floydMap = (w.cops[plans[i][j].botId].second==COP_CAR ? pureCarMap : pureFootMap);
      if (plans[i][j].world != w.n+1)
        continue;
      // Bots who suggest illegal moves should be shot
      if (floydMap[w.cops[plans[i][j].botId].first][plans[i][j].locId].dist
          > 1)
      {
        points[i] = -10000;
        lyingCops.insert(i);
        continue;
      }
      // Attribute points to moves that get us closer to the guesses
      vector<int> moveSeq;
      int origDist = findClearPath(w.cops[plans[i][j].botId].first,
            guesses, w, map, allFalse, moveSeq, 1);
      int finalDist = findClearPath(plans[i][j].locId,
            guesses, w, map, allFalse, moveSeq, 1);
      points[i] -= finalDist - origDist;
    }
  }

  retval.push_back(w.me);
  for (unsigned int i=0; i<plans.size(); i++)
    if (i != w.me)
      retval.push_back(i);
  // sort the entries by points (except our own, of course)
  for (unsigned int i=1; i<retval.size(); i++)
    for (unsigned int j=i+1; j<retval.size(); j++)
      if (points[retval[j]] > points[retval[i]])
      {
        int tmp = retval[i];
        retval[i] = retval[j];
        retval[j] = tmp;
      }

  return retval;
}