package modules.line;

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


// System:
// 1. anchor data is originated by the source, with priority to the
//    member of the source which is also a member of the line. It spreads 
//    throughout the whole source, destination, and line, plus a fringe
// 2. the source updates its version once every N cycles.
// 3. if the source is not in the line, it sends out search gradients
//    of size 2^L. After k*2^L cycles, it raises the size
// 4. if the source is in the line, it sends out maintainance gradients
// 5. if a processor is at the front of the line, it sends out s search
//    gradient of size 2^L-h, where h is the hopcount of its maint G
// 6. if a search or maint G reaches the destination, it calculates its
//    predecessors: all h-1 neighbors.
// 7. If a node's h+1 neighbor designates it as a predecessor, then that
//    nbr is added to its successors. Any node with a successor calculates its
//    predecessors. A successor dies only when the line has a higher version.
// 8. If a node in the source has a successor, it becomes part of the line
//    and designates one of its successors as the next link in the line.
//    any node designated as a "next link" which is not in the destination
//    chooses a successor. The version of a line is equal to the version of
//    its successor relations (which can only increase going up)
//    The source also tracks how frequently it hears a new successor version,
//    and considers itself to have lost the line if it goes too long w/o
// 9. If a node is in the line, it sends the "filler" gradient used by
//    maints to find their prey. Data is the line's version.
// 10.If a node is in the destination, it makes sure that the inverse
//    line exists too.

// Problems:
// - lines are deleted too fast

// Kludges:
// 1. maintainAnchorData: origin = in source
// 2. fringing is started manually for anchor init
// 3. mirror gradient is off
// 4. line version-lag turned off
// 5. separate line version by 2

public class PersistentLine 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 maintType = Symbol.GetSymbol("line-M"); // keepers
  public static Symbol fillType = Symbol.GetSymbol("line-F"); // fatteners
  public static Symbol anchorType = Symbol.GetSymbol("line-A"); // anchors

  // for swapping which line-gradient we're talking about
  Object invertID(Object gid,PLGDataA plgd)
  { return new Pair(rootID(gid),plgd.dst); }
  Object rootID(Object gid) { return ((Pair)gid).car(); }
  Object searchID(Object gid) { return new Pair(gid,searchType); }
  Object maintID(Object gid) { return new Pair(gid,maintType); }
  Object anchorID(Object gid) { return new Pair(gid,anchorType); }

  // returns the gids of all lines being processed
  Iterator getSMGradients() {
    Hashtable h = new Hashtable();
    Iterator i = ag.getType(searchType).iterator();
    while(i.hasNext()) 
      { Object gid = rootID(((Gradient)i.next()).gid); h.put(gid,gid); }
    i = ag.getType(maintType).iterator();
    while(i.hasNext())
      { Object gid = rootID(((Gradient)i.next()).gid); h.put(gid,gid); }
    return h.values().iterator();
  }
  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 = getSMGradients();
      while(i.hasNext()) { // for each search/maint gradient:
        Object gid = i.next();
        VersionedGradient gS = (VersionedGradient)ag.get(searchID(gid));
        VersionedGradient gM = (VersionedGradient)ag.get(maintID(gid));
        // if both dead or missing, remove from consideration.
        if((gS==null || gS.isDead()) && (gM==null || gM.isDead())) {
          ns.setData(gid,null);
          continue;
        }
        VersionedGradient g; if(gM==null || gM.isDead()) g=gS; else g=gM;
        
        PLGDataA plgd = (PLGDataA)g.data;
        
        // 1. anchor data & 2. version maintainance
        LineDataA ld = new LineDataA((LineDataA)ns.getData(gid));
        AnchorData ad = maintainAnchorData(g,ld);
        
        // update local information:
        ld.hop = g.getHopcount();
        ld.version = g.getVersion();
        calculatePredecessors(gid,plgd,ld); // 6. predecessors
        calculateSuccessors(gid,plgd,ld); // 7. successors
        calculateInLine(gid,plgd,ld,ad); // 8. line membership
        ns.setData(gid,ld);

        // 3. if source and not line, send search G
        // 4. if source and line, send maint G
        if(plgd.src.member(pp)) {
          if(ad.connected) sendMaint(gid,plgd,ad);
          else sendSearch(gid,plgd,ad,ld);
        } else if(lineEdge(gid,ld)) { // 5. if line edge, send short search G
          sendSearch(gid,plgd,ad,ld);
          System.out.println("edgetick");
        }

        // 9. send fattener if in line
        if(ld.connected) sendFiller(gid,plgd,ld);

        // 10. mirror gradient if in destination
        if(false && plgd.dst.member(pp)) mirrorGradient(gid,plgd);
      }
    }
    return changed;
  }
  // debugutil
  public boolean inLine() {
    Iterator i = getSMGradients();
    while(i.hasNext()) {
      Object gid = i.next();
      LineDataA ld = (LineDataA)ns.getData(gid);
      if(ld!=null && ld.connected) return true;
    }
    return false;
  }

  // *****************
  // *** Utilities ***
  // *****************
  // returns the current anchordata. If it's an origin, updates the data
  AnchorData maintainAnchorData(VersionedGradient g,LineDataA ld) {
    Object aID = anchorID(rootID(g.gid));
    PLGDataA plgd = (PLGDataA)g.data;
    VersionedGradient ga = (VersionedGradient)ag.get(aID);
    AnchorData ad=new AnchorData(); if(ga!=null) ad=(AnchorData)ga.data;
    // if we're not in the source, just return it.
    if(!plgd.src.member(pp)) return ad;
    // if it doesn't exist, originate a blank one
    if(ga==null) { 
      ad=ad.update(g,ld);
      FringedPropagation limit =
        new FringedPropagation(plgd.radius,new LineBodyPropagation(plgd));
      ga = new VersionedGradient(aID,anchorType,ad,limit);
      ag.sendGradient(ga);
      limit.startFringe(ga,pp); // 'cuz it won't start fringing itself
    } else {
      // renew gradient if either we're the origin, or it's not line and we are
      // or it's gone dead
      boolean origin = (ga.getHopcount()==0);
      origin = plgd.src.member(pp); // kludge
      if(ga.isDead() || origin || (!ad.connected && ld.connected)) {
        ga.data=ad=ad.update(g,ld);
        ga.setVersion(ad.version);
        if(ad.connected) ga.setQuality(1); else ga.setQuality(0);
        ag.renewGradient(ga);
      }
    }
    return ad;
  }
  // if in dst or having successors, set pred to h-1 nbrs
  void calculatePredecessors(Object gid,PLGDataA plgd,LineDataA ld) {
    ld.predecessors.clear();
    if(plgd.dst.member(pp) || !ld.successors.isEmpty()) {
      Iterator i = ns.getNeighbors();
      while(i.hasNext()) {
        Object nid = i.next();
        LineDataA d = (LineDataA)ns.getData(gid,nid);
        if(d!=null && d.version==ld.version && d.hop==ld.hop-1)
          ld.predecessors.add(nid);
      }
    }
  }
  // 7. If a node's h+1 neighbor designates it as a predecessor, then that
  //    nbr is added to its successors. 
  //    A successor dies only when the line has a higher version.
  void calculateSuccessors(Object gid,PLGDataA plgd,LineDataA ld) {
    // first, put current successors
    Object myid = ns.getSelf();
    Iterator i = ns.getNeighbors();
    while(i.hasNext()) {
      Object nid = i.next();
      LineDataA d = (LineDataA)ns.getData(gid,nid);
      if(d!=null && d.predecessors.contains(myid)) 
        ld.successors.put(nid,new Integer(d.version));
    }
    // second, prune obsolete successors
    i = ld.successors.values().iterator();
    while(i.hasNext()) {
      if(((Integer)i.next()).intValue()<ld.lineVersion-2) // kludge
        i.remove();
    }
  }
  // determines the line version, as well as where it's in the line at all
  // (see top for full description)
  static final int maxVersionLag=5;
  void calculateInLine(Object gid,PLGDataA plgd,LineDataA ld,AnchorData ad) {
    boolean instConnect=false;
    if(ld.successors.isEmpty()) { // if no successors: not in line
      Gradient fg = ag.get(rootID(gid)); // fetch the filler-gradient
      ld.nextLink=null; instConnect=false;
      if(fg!=null)
        ld.lineVersion = ((Integer)fg.data).intValue(); // line version
    } else {
      // in line if in source and successor is recent or if a nbr's nextlink
      if(plgd.src.member(pp)) {
        // calculate line version
        Iterator i=ld.successors.values().iterator();
        while(i.hasNext()) {
          int v = ((Integer)i.next()).intValue();
          if(v>ld.lineVersion) ld.lineVersion=v;
        }
        // if it's recent enough, we're in the line
        instConnect = (ad.getVersionLag()<maxVersionLag);
        instConnect=true; // kludge
      } else {
        instConnect=false;
        Object myid = ns.getSelf();
        Iterator i = ns.getNeighbors();
        while(i.hasNext()) {
          Object nid = i.next();
          LineDataA d = (LineDataA)ns.getData(gid,nid);
          if(d!=null && d.nextLink==myid) { 
            instConnect=true; ld.lineVersion=d.lineVersion; break; 
          }
        }
      }
      // if connected, choose most recent successor to be next link
      // (assuming that successor still has a greater hopcount)
      // If the current next-link is still valid, keep it.
      if(ld.connected) {
        int best = -1;
        if(ld.nextLink!=null && ld.successors.containsKey(ld.nextLink))
          best = ((Integer)ld.successors.get(ld.nextLink)).intValue();
        Iterator i=ld.successors.keySet().iterator();
        while(i.hasNext()) {
          Object nid = i.next();
          int v = ((Integer)ld.successors.get(nid)).intValue();
          LineDataA nld = (LineDataA)ns.getData(gid,nid);
          if(v>best && nld!=null && nld.hop>ld.hop) // or in dst
            { ld.nextLink=nid; best=v; }
        }
      } else { // otherwise, nextLink is null
        ld.nextLink=null;
      }
    }
    // connection age
    if(instConnect) {
      ld.age=0; ld.connected=true;
    } else {
      ld.age++; 
      if(ld.age>connectDecay) ld.connected=false;
    }
  }
  static final int connectDecay=5;

  void sendMaint(Object gid,PLGDataA plgd, AnchorData ad) {
    VersionedGradient vg = (VersionedGradient)ag.get(maintID(gid));
    if(vg==null) {
      PropagationTest limit = new GradientInternalPropagation(rootID(gid));
      vg = new VersionedGradient(maintID(gid),maintType,plgd,limit,0,
                                 ad.version);
      ag.sendGradient(vg);
    } else {
      vg.setVersion(ad.version);
      ag.renewGradient(vg);
    }
  }
  void sendSearch(Object gid,PLGDataA plgd, AnchorData ad, LineDataA ld) {
    VersionedGradient vg = (VersionedGradient)ag.get(searchID(gid));
    if(vg==null) {
      PropagationTest limit = new DistancePropagation(ad.getRadius());
      vg = new VersionedGradient(searchID(gid),searchType,plgd,limit,0,
                                 ad.version);
      ag.sendGradient(vg);
    } else {
      if(((DistancePropagation)vg.limit).getLimit()!=ad.getRadius()) 
        vg.limit = new DistancePropagation(ad.getRadius());
      vg.setVersion(ad.version);
      ag.renewGradient(vg,ld.hop);
    }
  }
  void sendFiller(Object gid,PLGDataA plgd, LineDataA ld) {
    VersionedGradient vg = (VersionedGradient)ag.get(rootID(gid));
    if(vg==null) {
      PropagationTest limit = new DistancePropagation(plgd.radius*2);
      vg = new VersionedGradient(rootID(gid),fillType,
                                 new Integer(ld.lineVersion),limit,0,
                                 ld.version);
      ag.sendGradient(vg);
    } else {
      vg.data=new Integer(ld.lineVersion);
      vg.setVersion(ld.version);
      ag.renewGradient(vg);
    }
  }
  // maintain the inverse line
  void mirrorGradient(Object gid,PLGDataA plgd) {
    Object iid = invertID(gid,plgd);
    Gradient ginv = ag.get(maintID(iid)); // try maint first
    if(ginv==null) ginv = ag.get(searchID(iid)); // try search if no maint
    if(ginv==null) {
      initiateLine(rootID(gid),plgd.dst,plgd.src,plgd.radius,plgd.load);
    } else {
      ag.renewGradient(ginv);
    }
  }
  // edge of line is connected, but doesn't have an active successor in
  // the line yet (i.e. no nbr w. >hopcount and connected=true)
  boolean lineEdge(Object gid, LineDataA ld) {
    if(!ld.connected) return false;
    if(ld.nextLink==null) return true;
    if(true) return false;
    Iterator i = ns.getNeighbors();
    while(i.hasNext()) {
      LineDataA nld = (LineDataA)ns.getData(gid,i.next());
      if(nld==null) continue;
      if(nld.connected && nld.hop>ld.hop) return false;
    }
    return true;
  }

  // ***** 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) {
    PLGDataA d = new PLGDataA(r,src,dst,l);
    VersionedGradient g = 
      new VersionedGradient(searchID(new Pair(lid,src)),searchType,d,
                            new DistancePropagation(AnchorData.base));
    ag.sendGradient(g);
  }

  // it's in the line if it's in the fattened gradient
  // (but only to the radius: half the width of the fattened)
  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) && 
         (g.getHopcount() < ((DistancePropagation)g.limit).getLimit()/2)) {
        ll.add(g.gid);  // add if in node
      }
    }
    return ll;
  }

  public String toString() {
    Vector lines = getLines();
    String s = "Persistent Line: "+lines.toString()+
      " anchors: ";
    Iterator i = ag.getType(anchorType).iterator();
    while(i.hasNext()) {
      Gradient g = (Gradient)i.next();
      s+=g.data.toString();
      if(i.hasNext()) s+=", ";
    }
    return s;
  }


}

// all final since it's going to be passed in gradients
class AnchorData {
  int age;
  int searchAge;
  boolean connected; // 
  int searchLevel; // radius=base*2^searchLevel
  int version; // current version: updates as time goes on
  int lastChange;
  int lastLineVersion;
  static final int base = 5;
  static final int timeFactor=2;//4;
  static final int period = 10;

  // returns a new copy of the data (since it's going to be gradient-propagated
  AnchorData update(VersionedGradient g, LineDataA ld)
  { return new AnchorData(this,g,ld); }
  public AnchorData() { // default constructor
    age=0; searchAge=0; connected=false; searchLevel=0; version=0;
    lastChange=0; lastLineVersion=0;
  }
  // this is where all the meat lives (the *real* update function)
  // every 10 steps, it increments the version
  // when not connected, it times searches too
  private AnchorData(AnchorData ad, VersionedGradient g, LineDataA ld) {
    // defaults:
    searchLevel=ad.searchLevel; connected=ld.connected; version=ad.version;
    age=ad.age+1; lastLineVersion=ld.lineVersion; lastChange=ad.lastChange;
    if(!connected) searchAge=ad.searchAge+1; else searchAge=0;
    // update functionality:
    if(ad.connected != ld.connected) { // on connection change, reset
      age=0; searchAge=0; 
      if(!ld.connected) searchLevel=0;
    } else { // otherwise, do periodic updates
      if(ad.age >= period) { age=0; version++; }
      if(!ad.connected && 
         searchAge>=(base*timeFactor*Math.pow(2,searchLevel))) {
        searchAge=0; searchLevel++;
      }
    }
    if(ad.lastLineVersion != ld.lineVersion) {
      lastChange=ad.version; // on line update, remember the version dif
    }
  }
  // returns the size of the current search radius
  public int getRadius() { return (int)(base*Math.pow(2,searchLevel)); }
  // returns the number of versionings since the last reply from the dst
  public int getVersionLag() { return version-lastChange; }
  public String toString() {
    return "("+age+", "+searchAge+", "+connected+", "+searchLevel+", "+
      version+", "+lastChange+", "+lastLineVersion+")";
  }
}

// this is going to be passed around with the neighborset, so we need
// to make sure it can't be modified once it starts getting passed...
class LineDataA {
  int age=0;
  int hop=0; // current hopcount level
  int version=0; // version associated with the hopcount
  int lineVersion=0; // version of the current line
  Object nextLink=null;
  Hashtable successors=new Hashtable(); // updated incrementally
  Vector predecessors=new Vector(); // continually recalculated
  boolean connected=false; // is it in a line?
  // if non-null, clone in construction
  public LineDataA(LineDataA ld) {
    if(ld!=null) {
      age=ld.age;
      hop=ld.hop;
      version=ld.version;
      lineVersion=ld.lineVersion;
      nextLink=ld.nextLink;
      successors.putAll(ld.successors);
      predecessors.addAll(ld.predecessors);
      connected=ld.connected;
    }
  }
  public String toString() {
    return "("+age+", "+hop+", "+version+", "+lineVersion+", "+nextLink+", "+
      connected+", "+successors+", "+predecessors+")";
  }
}

class PLGDataA { // passed around with the gradient
  final int radius;
  final ProcessorLoadEstimator load;
  final LineAnchor src;
  final LineAnchor dst;
  public PLGDataA(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 LineBodyPropagation implements PropagationTest {
  private final PLGDataA plgd;

  public LineBodyPropagation(PLGDataA d) { plgd=d; }
  
  // 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(); }
  public boolean propagate(Gradient g, PortedProcessor pp) {
    if(plgd.src.member(pp) || plgd.dst.member(pp)) return true;

    ActiveGradient ag = (ActiveGradient)pp.getModule("ActiveGradient");
    Gradient lg = ag.get(rootID(rootID(g.gid)));
    if(lg!=null && lg.getHopcount()<plgd.radius) return true;

    return false;
  }
}
