package modules.line;

import utils.*;
import modules.neighborset.*;
import modules.gradient.*;
import modules.node.*;
import simulator.*;
import java.util.*;


// System:
// 1. all members of source originate search gradient every K ticks
// 2. destination marks "inline" and propagates "inline-ness" backwards
// 3. inline nodes send marker gradient
// 3. source keeps estimated hopcount and restricts search to summed estimate

// edge sizes can be constrained better: try a fringing gradient?


public class PersistentLineB implements ProcessorModule {
  PortedProcessor pp; ActiveGradient ag; NeighborSet ns;

  public Symbol getName() { return Symbol.GetSymbol("PersistentLine"); }
  public void link(PortedProcessor p) { 
    pp = p; 
    ag = (ActiveGradient)p.getModule("ActiveGradient");
    ns = (NeighborSet)p.getModule("NeighborSet");
    pp.addClockListener(this);
  }

  public void init() {
  }

  int defaultRadius = 2;

  public static Symbol searchType = Symbol.GetSymbol("line-S"); // finders
  public static Symbol fillType = Symbol.GetSymbol("line-F"); // fatteners

  // for swapping which line-gradient we're talking about
  Object invertID(Object gid,PLGData plgd)
  { return new Pair(rootID(gid),plgd.dst); }
  Object rootID(Object gid) { return ((Pair)gid).car(); }

  // returns the gids of all lines being processed
  public boolean signalEvent(Symbol name,Object data) {
    boolean changed = false;
    if(name==PortedProcessor.kClock) {
      // get the set of lines [by checking through search & maintain gradients
      Iterator i = ag.getType(searchType).iterator();
      while(i.hasNext()) { // for each search/maint gradient:
        VersionedGradient g = (VersionedGradient)i.next();
        // if dead, remove from consideration.
        if(g.isDead()) {
          ns.setData(g.gid,null);
          continue;
        }
        PLGData plgd = (PLGData)g.data;
        LineData ld = new LineData((LineData)ns.getData(g.gid));
        
        // if in source, send search G
        if(plgd.src.member(pp)) sendSearch(g,ld);
        // if in destination, do mirror gradient
        if(plgd.dst.member(pp)) mirrorGradient(g.gid,plgd,ld);
        
        // propagate backwards gradients
        boolean mem=ld.connected;
        lineBackprop(g,ld); // calculate line data
        ns.setData(g.gid,ld);
        //if(plgd.src.member(pp) && mem!=ld.connected) { 
        //  System.out.println("StateChange "+g.gid+": "+ld.connected);
        //}

        // send fattener if in line
        if(ld.connected) sendFiller(g.gid,plgd,ld);
      }
    }
    return changed;
  }
  // debugutil
  public boolean inLine() {
    Iterator i = ag.getType(searchType).iterator();
    while(i.hasNext()) { // for each search/maint gradient:
      VersionedGradient g = (VersionedGradient)i.next();
      LineData ld = (LineData)ns.getData(g.gid);
      if(ld!=null && ld.connected) return true;
    }
    return false;
  }
  
  // *****************
  // *** Utilities ***
  // *****************
  // Many tasks for this one:
  // 1. forward version: pluck from gradient except in source (which timeouts)
  // 2. connected: true if dst, or in a nbr's predecessor
  // 3. backVersion: 
  void lineBackprop(Gradient g,LineData ld) {
    PLGData plgd = (PLGData)g.data;
    
    // update forward version: 
    ld.forwAge++;
    Iterator i = ns.getNeighbors();
    while(i.hasNext()) {
      Object nid = i.next();
      LineData nld = (LineData)ns.getData(g.gid,nid);
      if(nld!=null && nld.forwVersion>ld.forwVersion) // if newer nbr, reset
        { ld.forwVersion=nld.forwVersion; ld.forwAge=0; }
    }
    if(plgd.src.member(pp) && ld.forwAge>ld.timeout) // if src & old, increment
      { ld.forwAge=0; ld.forwVersion++; }
    ld.hop = g.getHopcount();

    // check if connected:
    if(plgd.dst.member(pp)) { 
      ld.connected=true; ld.backAge=0; ld.backVersion=ld.forwVersion;
      ld.estDist=g.getHopcount(); ld.distAge=0;
    } else {
      // refresh connection if we're a predecessor
      Object myid = ns.getSelf();
      i = ns.getNeighbors();
      while(i.hasNext()) {
        Object nid = i.next();
        LineData nld = (LineData)ns.getData(g.gid,nid);
        if(nld!=null && nld.predecessor==myid && 
           nld.backVersion>=ld.backVersion) {
          if(ld.backVersion<nld.backVersion || ld.estDist>nld.estDist)
            { ld.estDist=nld.estDist; ld.distAge=0; }
          ld.connected=true; ld.backAge=0; ld.backVersion=nld.backVersion;
        }
      }
      // increment age and possibly disconnect
      if(ld.connected) {
        ld.backAge++;
        if(ld.backAge>ld.backPersist) ld.connected=false;
      }
    }

    // if we've not connected soon enough, double distance estimate
    ld.distAge++;
    if(ld.distAge > ld.estDist*ld.timeFactor) {
      ld.distAge=0; ld.estDist*=2;
    }

    // now, hunt for our own predecessor, w. pref for continuity
    if(ld.connected) {
      int best = ld.hop;
      LineData pd = null;
      if(ld.predecessor!=null) pd=(LineData)ns.getData(g.gid,ld.predecessor);
      if(pd==null || pd.forwVersion==ld.forwVersion) {
        if(pd!=null) best=pd.hop; // bias in favor of current pred
        i = ns.getNeighbors();
        while(i.hasNext()) {
          Object nid = i.next();
          LineData nld = (LineData)ns.getData(g.gid,nid);
          if(nld!=null && nld.hop<best && nld.forwVersion==ld.forwVersion) {
            best=nld.hop;
            ld.predecessor=nid;
          }
        }
      } // else leave it unchanged
    } else {
      ld.predecessor=null;
    }
  }
  // initiate the search gradient with the current estimates
  void sendSearch(VersionedGradient g, LineData ld) {
    LSPFringe ft = (LSPFringe)g.limit;
    int limitdist = ld.calcLimit();
    if(ft.getLimit()!=limitdist) {
      ft = new LSPFringe(LineData.fringe,limitdist);
      ft.startFringe(g,pp); // kludge for startup
      g.limit = ft;
    }
    g.setVersion(ld.forwVersion);
    ag.renewGradient(g);
  }
  // send the line fattener
  void sendFiller(Object gid,PLGData plgd, LineData ld) {
    VersionedGradient vg = (VersionedGradient)ag.get(rootID(gid));
    if(vg==null) {
      PropagationTest limit = new DistancePropagation(plgd.radius);
      vg = new VersionedGradient(rootID(gid),fillType,plgd,limit,0,
                                 ld.backVersion);
      ag.sendGradient(vg);
    } else {
      if(ld.backVersion>vg.getVersion())
        vg.setVersion(ld.backVersion);
      ag.renewGradient(vg);
    }
  }
  // maintain the inverse line
  void mirrorGradient(Object gid,PLGData plgd,LineData ld) {
    Object iid = invertID(gid,plgd);
    Gradient ginv = ag.get(iid);
    if(ginv==null) {
      initiateLine(rootID(gid),plgd.dst,plgd.src,plgd.radius,plgd.load,
                   ld.estDist);
    } else {
      ag.renewGradient(ginv);
    }
  }
  
  // ***** EXTERNAL INTERFACE *****
  // start a persistent node:
  public void initiateLine(Object lid, LineAnchor src, LineAnchor dst) 
  { initiateLine(lid,src,dst,defaultRadius); }
  public void initiateLine(Object lid, LineAnchor src, LineAnchor dst, int r)
  { initiateLine(lid,src,dst,r,new UnitEstimator()); }
  public void initiateLine(Object lid, LineAnchor src, LineAnchor dst, 
                           ProcessorLoadEstimator l)
  { initiateLine(lid,src,dst,defaultRadius,l); }
  public void initiateLine(Object lid, LineAnchor src, LineAnchor dst,
                           int r, ProcessorLoadEstimator l)
  { initiateLine(lid,src,dst,defaultRadius,l,LineData.base); }
  public void initiateLine(Object lid, LineAnchor src, LineAnchor dst,
                           int r, ProcessorLoadEstimator l, int distEst) {
    PLGData d = new PLGData(r,src,dst,l);
    Object gid = new Pair(lid,src);
    LSPFringe ft = new LSPFringe(LineData.fringe,distEst);
    VersionedGradient g = new VersionedGradient(gid,searchType,d,ft);
    ag.sendGradient(g);
    ft.startFringe(g,pp); // kludge for startup
  }
    
  // it's in the line if it's in the fattened gradient
  public Vector getLines() { 
    Vector ll = new Vector();
    Iterator i = ag.getType(fillType).iterator();
    while(i.hasNext()) {
      Gradient g = (Gradient)i.next();
      if(!g.isDead() && !ll.contains(g.gid))
        ll.add(g.gid);  // add if in line
    }
    return ll;
  }

  public String toString() {
    String s = "Persistent Line: "+getLines().toString();
    return s;
  }


}

// this is going to be passed around with the neighborset, so we need
// to make sure it doesn't get modified once it starts getting passed...
class LineData {
  int forwVersion=0; // version of forward search
  int forwAge=0; // time since last forward increment
  int hop=0; // current forward hopcount
  boolean connected=false; // is it in the line backbone?
  int estDist=base; // estimated destination hopcount [from backward chains]
  int distAge=0; // time since last update to estDist
  int backVersion=-1; // version of destination feedback
  int backAge=0; // time since last backward confirmation
  Object predecessor=null; // next back in line
  static final int base = 5;
  static final int fringe = 4; // 2 is minimum
  static final double timeFactor=4;
  static final int timeout = 10;
  static final int backPersist = 5;

  public int calcLimit() {
    int limitplus = (int)(estDist*0.1); // size+10%
    if(limitplus < base) limitplus=base; // minimum size
    return estDist;//+limitplus :killed in favor of fringing
  }

  public String toString() {
    return "("+forwVersion+", "+forwAge+", "+hop+", "+connected+", "+
      estDist+", "+distAge+", "+backVersion+", "+backAge+", "+predecessor+")";
  }
  public LineData() {}
  public LineData(LineData d) { // copy constructor
    if(d!=null) {
      forwVersion=d.forwVersion; forwAge=d.forwAge; hop=d.hop;
      connected=d.connected; estDist=d.estDist; distAge=d.distAge;
      backVersion=d.backVersion; backAge=d.backAge; predecessor=d.predecessor; 
    }
  }
}

class PLGData { // passed around with the gradient
  final int radius;
  final ProcessorLoadEstimator load;
  final LineAnchor src;
  final LineAnchor dst;
  public PLGData(int r, LineAnchor s, LineAnchor d, ProcessorLoadEstimator l) 
  { radius=r; src=s; dst=d; load=l; }
  public String toString() 
  { return "("+radius+", "+src+", "+dst+", "+load+")"; }
}

class LineSumPropagation implements PropagationTest {
  private final int limit;

  public LineSumPropagation(int l) { limit=l; }
  public int getLimit() { return limit; }
   
  // spreads through source, destination, and line regions
  // should be used in anchor-gradients, which will have a 2-layer ID
  Object rootID(Object gid) { return ((Pair)gid).car(); }
  Object invertID(Object gid,PLGData plgd)
  { return new Pair(rootID(gid),plgd.dst); }
  public boolean propagate(Gradient g, PortedProcessor pp) {
    Gradient g2 = getInverse(g,pp);
    int hop1 = g.getHopcount();
    int hop2 = 0; 
    if(g2!=null) hop2=g2.getHopcount();
    
    return (hop1+hop2 <= limit);
  }
  Gradient getInverse(Gradient g, PortedProcessor pp) {
    PLGData plgd = (PLGData)g.data;
    ActiveGradient ag = (ActiveGradient)pp.getModule("ActiveGradient");
    return ag.get(invertID(g.gid,plgd));
  }

}

class LSPFringe extends DistancePropagation {
  public LSPFringe(int f, int l) {
    super(l+f);
  }
  public void startFringe(Gradient g, PortedProcessor pp) {};
}

/*
class LSPFringe extends FringedPropagation {
  LineSumPropagation lsp;
  int limit;
  
  public LSPFringe(int f, int l) {
    //super(f,new LineSumPropagation(l));
    //lsp = (LineSumPropagation)getTest();
    super(0,new DistancePropagation(l+f)); // kludge
    limit=l+f;
  }

  public int getLimit() { return limit; } // lsp.getLimit(); }
  public boolean prupagate(Gradient g, PortedProcessor pp) {
    Object gid = new Pair(g.gid,type);
    ActiveGradient ag = (ActiveGradient)pp.getModule("ActiveGradient");
    VersionedGradient fg = (VersionedGradient)ag.get(gid);
    boolean hasInv = (lsp.getInverse(g,pp)!=null);
    if(lsp.propagate(g,pp)) {
      if(fg==null) {
        fg=new VersionedGradient(gid,type,new Boolean(hasInv),ftest);
        if(hasInv) fg.setQuality(1); else fg.setQuality(0);
        ag.sendGradient(fg);
      } else {
        if(hasInv || fg.data.equals(Boolean.FALSE)) {
          if(hasInv) fg.setQuality(1); else fg.setQuality(0);
          ag.renewGradient(fg);
        }
      }
      return true;
    } else {
      if(fg!=null) return true;
    }
    return false;
  }

}
*/
