/* file mcp4post.cc, used for MCP implementation
 * All right reserved by M.Y. Wu
 */
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>

#define MAXINT          0x7FFFFFFF
#define MAX(x,y)        ((x == MAXINT || x > y) ? x : y)
#define MIN(x,y)        (x > y) ? y : x)
#define vNODEi vector<NODE>::iterator 
#define vLINKi vector<LINK>::iterator 
#define vALAPi vector<ALAP>::iterator 
#define lINTi  list<int>::iterator 
#define lHOLEi list<HOLE>::iterator 
#define DEBUG true

class LINK { // links can be upwards (in vParent) or downwards (in vChild)
  int    dst, commcost;
public:
  LINK(int x, int y) {dst=x; commcost=y; }
  const int getDst() {return dst;}
  const int getCost() {return commcost;}
}; 
 
class NODE { // as input/output, nodes are enumerated as 1,2,3...
  int    nid, compcost, flev, alap, refnum, schPe, start;
public:
  vector<LINK> vChild, vParent; // vector of LINKs
  NODE(int x, int y): flev(0),alap(0),refnum(0),schPe(-1),start(0)
    {nid=x; compcost = y; };
  bool InitRef() {return (refnum=vChild.size())==0;}
  void InitALAP(int x) {alap=x;}
  void AddChild(int x, int c) {vChild.push_back(LINK(x,c));}
  void AddParent(int x, int c) {vParent.push_back(LINK(x,c));}
  bool UpdateRef() {return (--refnum)==0; }
  void UpdateFlev(int x) {if (x>flev) flev=x;}
  void Sch2PE(int x, int y) {schPe=x; start=y;}
  const int getALAP() {return alap;}
  const int getFlev() {return flev;}
  const int getCost() {return compcost;}
  const int getStart() {return start;}
  const int getEnd() {return start+compcost;}
  const int getSchPE() {return schPe;}
  const int getNid() {return nid;}
  const void PrintSch() {
    cout << "  node# "<<nid+1<<" with comp weight "<<compcost
	 <<" scheduled at PE "<<schPe<<" start from "<<start<<"\n";}
}; 

struct ALAP { // used for sorting
  int nid; double alap;
  ALAP(int x, double y) {nid=x; alap=y;}
};
struct LessALAP { // ascending order of ALAP
  bool operator()(const ALAP& p, const ALAP& q) const {
    return p.alap < q.alap; }
};
struct HOLE { // used for insertion
  int start,end;
  HOLE(int x, int y) {start=x; end=y;}
  };

class GRAPH { // vector of nodes, enumerated as 0,1,2,...
  int numpe, cplength;
  list<int> readyQ;
  vector<ALAP> alap_order;
public:
  vector<NODE> vNode;
  void GraphIn(const char* gfilename, int numpe);
  void BuildLink();
  void CompALAP();
  void SortALAP();
  void ScheduleALAP();
};

void GRAPH::GraphIn(const char *gfilename, int x) {
  int n,comp,comm,m,nid,cid; numpe = x; ifstream gin(gfilename);
  gin >> n; vNode.reserve(n);
  for (int i=0; i<n; i++) { // for each node
    gin >> nid >> comp >> m; assert(i==nid-1);
    NODE newnode(i,comp);
    for (int j=0; j<m; j++) { // listing of its child nodes
      gin >> cid >> comm; assert (cid<=n);
      newnode.AddChild(cid-1,comm);
      };
    vNode.push_back(newnode);
    };
}

void GRAPH::BuildLink() { // from vChild, build vParent
  int k; vNODEi p; vLINKi q;
  for (p=vNode.begin(),k=0; p!=vNode.end(); p++,k++) {
    for (q=p->vChild.begin(); q!=p->vChild.end(); q++) 
      vNode[q->getDst()].AddParent(k,q->getCost());
    if (p->InitRef()) readyQ.push_back(k); // is ready if no child
    }
}

void GRAPH::CompALAP() {
  cplength = 0; vNODEi p,pp; vLINKi q;
  while (!readyQ.empty()) { // for each next ready node
    p = &vNode[*readyQ.begin()]; readyQ.pop_front();
    for (q=p->vParent.begin(); q!=p->vParent.end(); q++) {
      pp = &vNode[q->getDst()]; // for each of its parent
      pp->UpdateFlev(p->getFlev()+p->getCost()+q->getCost());
      // a node can be ready if all of its chilren updated its Flev
      if (pp->UpdateRef()) readyQ.push_back(q->getDst());
      }
    cplength = MAX(cplength,p->getFlev()+p->getCost());
    }
  // compute ALAP based on their flooring level and critical path length
  for (p=vNode.begin(); p!=vNode.end(); p++) {
    p->InitALAP(cplength-p->getFlev()-p->getCost());
    }
}

void GRAPH::SortALAP() { // sorting in ascending order of ALAP
  for (vNODEi p=vNode.begin(); p!=vNode.end(); p++) {
    // extendedALAP: utilize one-level children's ALAP to break even
    double x,childalap = double(cplength);
    for (vLINKi q=p->vChild.begin(); q!=p->vChild.end(); q++) 
      childalap=(x=double(vNode[q->getDst()].getALAP()))<childalap?x:childalap;
    x = double((cplength+1)*p->getALAP())+childalap;
    alap_order.push_back(ALAP(p->getNid(),x));
    }
  sort(alap_order.begin(),alap_order.end(),LessALAP());
}

void GRAPH::ScheduleALAP() {
  list<int> arySch[numpe]; int schlength=0;
  vALAPi o; vNODEi p, pp; vLINKi q; lINTi r;
  list<HOLE> aryHole[numpe]; // used for efficient insertion
  for (int i=0; i<numpe; i++) 
    aryHole[i].push_front(HOLE(0,MAXINT));
  for (o=alap_order.begin(); o!=alap_order.end(); o++) { 
    int tmp,latest=0, latestpe=0, latest2=0, latestpe2=0;
    p = &vNode[o->nid]; // schedule this node
    for (q=p->vParent.begin(); q!=p->vParent.end(); q++) {
      pp = &vNode[q->getDst()]; // consider its parent's constraint
      if ((tmp=pp->getEnd()+q->getCost()) > latest) {
	latest = tmp; latestpe = pp->getSchPE(); }
      }
    for (q=p->vParent.begin(); q!=p->vParent.end(); q++) {
      pp = &vNode[q->getDst()];
      tmp=(pp->getSchPE()==latestpe)?pp->getEnd():pp->getEnd()+q->getCost();
      if (tmp > latest2) {
	latest2 = tmp; latestpe2 = pp->getSchPE(); }
      }
    int early=MAXINT, earlype=0; lHOLEi earlyptr=0;
    for (int i=0; i<numpe; i++) { lHOLEi r; // try every PE
      int nodeready = (i==latestpe) ? latest2 : latest;
      for (r=aryHole[i].begin(); r!=aryHole[i].end();r++) { 
	nodeready=MAX(nodeready,r->start);
        if ((r->end-nodeready)>=p->getCost()) break;
        }
      if (nodeready<early) {early=nodeready; earlype=i; earlyptr=r;}
      }
    p->Sch2PE(earlype,early); lINTi r1;
    for (lINTi r=r1=arySch[earlype].begin(); r!=arySch[earlype].end();r1=r,r++)  
	if (vNode[*r].getStart()>=early) break;
    arySch[earlype].insert(++r1,p->getNid());
    if (earlyptr->start<early) { // split the hole
      aryHole[earlype].insert(earlyptr,HOLE(earlyptr->start,early));
      }
    earlyptr->start=early+p->getCost(); // update the hole
    schlength=MAX(schlength,early+p->getCost());
    }
  if (DEBUG) for (int i=0; i<numpe; i++) { cout << "PE"<<i<<":\n";
    for (lINTi r=arySch[i].begin(); r!=arySch[i].end(); r++) 
      vNode[*r].PrintSch();
    }
  cout << "SchLength = "<<schlength<<"\n";
}

/*********************************************************************
 *    main program 
 *********************************************************************/
void main(int argc, char **argv)
{ GRAPH graph;
    if (argc != 3) {
        cerr <<"usage: "<<argv[0]<<" TargetPeNum GraphFile\n";
        exit(0); }
    graph.GraphIn(argv[2],atoi(argv[1]));
    graph.BuildLink();
    graph.CompALAP();
    graph.SortALAP();
    graph.ScheduleALAP();
}