///////////////////////////////////////////////////////////////////////////////
//                                                                           //
// Copyright (C) 2006 by Intel Coproration and Carnegie Mellon University    //
// Contacts: casey.j.helfrich @ intel.com                                    //
//           bdr @ cs.cmu.edu                                                //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#include "DPRHierarchy.hxx"

#include "CatomWorld.hxx"
#include "CatomSim.hxx"

using namespace std;

LandmarkMsg::LandmarkMsg(DPRHierarchy* _hierarchy, vector<catomID> dest, 
			 Message* _payload) : 
  Message(_hierarchy->hierarchyMessageBox), 
  destination(dest), 
  payload(_payload) { }
LandmarkMsg::LandmarkMsg(MailboxID _mailboxID, vector<catomID> dest, 
			 Message* _payload) : 
  Message(_mailboxID), 
  destination(dest), 
  payload(_payload) { }

LandmarkBeacon::LandmarkBeacon(DPRHierarchy* _hierarchy, catomID _id, 
			       long int _beaconVersionID, 
			       unsigned int _visDistance, 
			       unsigned int _distanceSoFar, 
			       int _level, catomID _parent) : 
  Message(_hierarchy->landmarkBeaconBox), 
  id(_id), 
  beaconVersionID(_beaconVersionID), 
  visDistance(_visDistance), 
  distanceSoFar(_distanceSoFar), 
  level(_level), 
  parent(_parent) { }
LandmarkBeacon::LandmarkBeacon(MailboxID _mailboxID, catomID _id, 
			       long int _beaconVersionID, 
			       unsigned int _visDistance, 
			       unsigned int _distanceSoFar, 
			       int _level, catomID _parent) : 
  Message(_mailboxID), 
  id(_id), 
  beaconVersionID(_beaconVersionID), 
  visDistance(_visDistance), 
  distanceSoFar(_distanceSoFar), 
  level(_level), 
  parent(_parent) { }

DPRHierarchy::DPRHierarchy(catomID _hostCatom, string _hierarchyName) :
  Hierarchy(_hostCatom, _hierarchyName),
  hierarchyMessageBox("_hchy_" + _hierarchyName),
  landmarkBeaconBox("_lm_" + _hierarchyName),
  visibilityDistance(2),
  lastAnnouncementTime(-1),
  nextBeaconVersionID(1) {  }

DPRHierarchy::~DPRHierarchy() { }

void DPRHierarchy::simulationStart() {
  Hierarchy::simulationStart();

  worldPtr->catomHash[hostCatom]->C.mailboxManager.registerHandler(hierarchyMessageBox,
								   this,
								   (msgHandlerPtr)&DPRHierarchy::hierarchyMessageHandler,
								   false);
  worldPtr->catomHash[hostCatom]->C.mailboxManager.registerHandler(landmarkBeaconBox,
								   this,
								   (msgHandlerPtr)&DPRHierarchy::landmarkBeaconHandler,
								   true);

  // Add our physical neighbors to the peers set to seed it
  for(featureID i=1; i<=NUM_FEATURES; i++) {
    catomID neighbor = worldPtr->catomHash[hostCatom]->C.getNeighbor(i);
    if(neighbor != 0)
      peers.insert(neighbor);
  }
}

void DPRHierarchy::dumpStats() {
  worldPtr->oStart();
  cerr << worldPtr->current_time << " DPRHierarchy(" << hierarchyName << ") "  << hostCatom << ":"
       << " peers.size " << peers.size()
       << " visibility " << visibilityDistance
       << endl << flush;
  worldPtr->oEnd();

  Hierarchy::dumpStats();
}

void DPRHierarchy::endTick() {
  if(parent == 0) {
    //we have no parent yet; see whether we should become one
    
    // only possibly self elect if:
    // (a) we have at least 4 peers OR
    // (b) we're just starting out as a leaf and have any peers OR
    // (c) we're visible to the entire object already, so may be the root, and do have other peers already
    if((peers.size() > 4) ||
       ((peers.size() > 0) && (level == 0)) ||
       ((peers.size() > 0) && (visibilityDistance >= (1.25*worldPtr->catomHash.size())))) {
      // only do anything if we actually have some peers, otherwise best to wait until later
      // declare ourselves a parent with some probability
      // TODO: make this smarter, somehow
      float threshold = 1.0f / (peers.size()+1);
      float val = (float)((double)random() / (double)LONG_MAX);
      if(val <= threshold) {
	// we hit the probability, so we should elect ourselves
	promoteSelf();
      }
    } else {
      // if we're not already visible to everybody, and we don't have enough peers even though there's
      // been time for our beacon to propagate, expand our visibility radius
      if((visibilityDistance < (1.25*worldPtr->catomHash.size())) &&
	 (worldPtr->current_time - lastAnnouncementTime) > (1.25*visibilityDistance + 1)) {
	visibilityDistance = (int)ceil(1.25*visibilityDistance);
	landmarkAnnounce();
      }
    }
  }
  
  // broadcast an update beacon if 25 ticks have passed
  if((worldPtr->current_time - lastAnnouncementTime) >= 25)
    landmarkAnnounce();
  
  Hierarchy::endTick();
}

void DPRHierarchy::promoteSelf() {
  // send ourselves up a level
  level++;
  
  // recalculate our visibility distance
  visibilityDistance = (unsigned)ceil(visibilityDistance*1.25);
  
  // send a new beacon
  landmarkAnnounce();
  
  // reset peers
  peers.clear();
  // timeLastPeerAdded = worldPtr->current_time;
}

bool DPRHierarchy::hierarchyMessageHandler(Message* _msg) {
  LandmarkMsg* msg = (LandmarkMsg*)_msg;
  
  if(msg->destination.front() == hostCatom) {
    // it's meant for us; handle the payload
    worldPtr->catomHash[hostCatom]->C.mailboxManager.fileMessage(msg->payload);
    worldPtr->catomHash[hostCatom]->C.speculationManager.messageRouted(msg->arrivalContact, 0);
    delete msg;
  } 
  else {
    // we should just route it
    vector<catomID>::iterator destIter = msg->destination.begin();
    featureID contact = 0;
    while((destIter != msg->destination.end()) && (contact == 0)) {
      catomID theGUID = *destIter; destIter++;
      contact = routingTable[theGUID];
    }
    
    if(contact == 0) {
      // Routing failure!
      cerr << "Routing failure at " << hostCatom << endl;
      return false;
    }
    
    worldPtr->catomHash[hostCatom]->C.speculationManager.messageRouted(msg->arrivalContact, contact);
    worldPtr->catomHash[hostCatom]->C.getFeatureMap()[contact].getNetworkAdapter()->sendMessage(msg);
  }

  return true;
}

bool DPRHierarchy::landmarkBeaconHandler(Message* _msg) {
  LandmarkBeacon* msg = (LandmarkBeacon*)_msg;

  //worldPtr->oStart();
  //cerr << worldPtr->current_time << " " << hostCatom << " receives beacon from "
  //     << msg->id << "(level " << msg->level << ")\n";
  //worldPtr->oEnd();
  
  if(msg->id == hostCatom) {
    return false;
  }
  
  bool didChange = updateLandmarkRoutingTables(msg->id, msg->arrivalContact, msg->beaconVersionID, msg->distanceSoFar);

  // adopt as a parent, if desired
  if((parent == 0) && (msg->level == (level+1))) {
    // we still need a parent, become a child of that landmark
    parent = msg->id;
    
    unsigned int neededDistance = (int)(msg->distanceSoFar * 1.05); // give a 5% leeway
    if(neededDistance > visibilityDistance) {
      visibilityDistance = neededDistance;
      landmarkAnnounce();
    }
  }
  
  // see if they're a peer
  if(msg->level == level) {
    peers.insert(msg->id).second;
    
    // possibly change our visibility if we're still in the running for being a parent
    if((parent == 0) && (msg->visDistance > visibilityDistance)) {
      visibilityDistance = msg->visDistance;
      landmarkAnnounce();
    }
  }
  
  // see if they're a child
  if(msg->parent == hostCatom) {
    // if it's not already in the map, add it to the list with a new child data object
		if(childData.find(msg->id) == childData.end())
			childData[msg->id] = newChildDataObject();
  }
  
  // propagate the announcement
  if(didChange && (msg->distanceSoFar < msg->visDistance)) {
    for(unsigned int i=1; i<=NUM_FEATURES; i++) {
      Feature* contact = &((worldPtr->catomHash[hostCatom]->C.getFeatureMap())[i]);
      LandmarkBeacon* newMsg = new LandmarkBeacon(this,
						  msg->id,
						  msg->beaconVersionID,
						  msg->visDistance,
						  msg->distanceSoFar+1,
						  msg->level,
						  msg->parent);
      contact->getNetworkAdapter()->sendMessage(newMsg);
    }
  } else if(!didChange) {

  } else {

  }

  delete msg;

  return true;
}

bool DPRHierarchy::updateLandmarkRoutingTables(catomID _landmarkID, featureID _contact, long _beaconID, unsigned long _hopcount) {
  long lastID = beaconIDs[_landmarkID];

  // if it's not at least as new as the last beacon we heard, then quit
  if(lastID > _beaconID)
    return false;
  
  if((lastID == 0) || (_beaconID > lastID) || // If it's a new beacon,
     (_hopcount < beaconHopcounts[_landmarkID])) { // or a shorter path than we already had
    // then we definitely need to update
    beaconIDs[_landmarkID] = _beaconID;
    beaconHopcounts[_landmarkID] = _hopcount;
    routingTable[_landmarkID] = _contact;

    return true;
  }

  // Otherwise, we know here that it's the same beacon we've already seen

  // Throw it out if it's just a longer path
  if(_hopcount > beaconHopcounts[_landmarkID])
    return false;

  // Otherwise, it's not only the same beacon, it's the same path length
  // Break the tie with a hash of contact number and landmark id
  if((_contact+_landmarkID)%NUM_FEATURES < (routingTable[_landmarkID]+_landmarkID)%NUM_FEATURES) {
    // We update in this case to get stability
    beaconIDs[_landmarkID] = _beaconID;
    beaconHopcounts[_landmarkID] = _hopcount;
    routingTable[_landmarkID] = _contact;
  }

  // But even if we updated, we still return false here, because it doesn't need to be propagated
  return false;

  /*
  if(worldPtr->current_time > 150) {
    worldPtr->oStart();
    cerr << worldPtr->current_time << " " << hostCatom << " changed its routing table late in the game:"
	 << " landmarkID " << _landmarkID 
	 << " old_contact " << routingTable[_landmarkID]
	 << " new_contact " << _contact
	 << " old_send_time " << lastSendTime
	 << " new_send_time " << _msgSendTime
	 << endl;
    worldPtr->oEnd();
  }
  */
}

void DPRHierarchy::landmarkAnnounce() {
  // Short circuit out if we've already sent something this tick
  if(lastAnnouncementTime >= worldPtr->current_time)
    return;

  nextBeaconVersionID++;
  lastAnnouncementTime = worldPtr->current_time;
  
  Feature* featureMap = worldPtr->catomHash[hostCatom]->C.getFeatureMap();
  for(unsigned int i=1; i<=NUM_FEATURES; i++) {
    LandmarkBeacon* newMsg = new LandmarkBeacon(this,
						hostCatom,
						nextBeaconVersionID,
						visibilityDistance,
						1,
						level,
						parent);
    
    featureMap[i].getNetworkAdapter()->sendMessage(newMsg);
  }
}

// API/Utilities

bool DPRHierarchy::sendMsgToParent(Message* msg) {
  vector<catomID> dest;
  dest.push_back(parent);
  
  if(parent == 0) {
    delete msg;
    return false;
  }
  
  LandmarkMsg* lMsg = new LandmarkMsg(this, dest, msg);
  hierarchyMessageHandler(lMsg);
  
  return true;
}
