package modules.hierarchy;

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

/*
  Unlike its relative, the simple hierarchy, the PNHierarchy 
  uses groups based not on individual processors, but on Persistent
  Nodes. As such, it is surprisingly simple in aspect, and levels
  depend only weakly on each other...

  For level i, nodes of radius 2^i are used, so at level 1, we use
  radius 2 nodes, level 2 uses radius 4, etc. At level 0, of course,
  no nodes are used at all.
  Node density is maintained as follows:
  1) If two node cores are touching, one node will suicide
  2) If a processor is not a member of any node's 2.5 penumbra, it will
     initiate a new node.
  When a node is partitioned, this is prevented from being significant
  by ensuring that the two halves cannot co-exist within the same i+1
  node. This is done by having every node have an umbra size of 5.

  Neighbors (which are not actually used for anything) are the set 
  of nodes for which any member of our core is a member of its umbra.
  For hysteresis, they persist as long as a member of the reflector
  is in the umbra
*/

//TO DO TOMORROW:
//done 1. leaders join higher level nodes
//2. leaders poll for neighbors
//done 3. leaders propagate info to followers
//done 4. leaders propagate info down the tree
//5. set level height
//6. increase umbra size to prevent fission problems
//7. create list of children/parents?

public class PNHierarchy implements ProcessorModule {
  //********** ProcessorModule Glue ***********
  //  These are the glue routines used to patch into the processor
  PortedProcessor pp; ActiveGradient ag; NeighborSet ns; PersistentNodeB pn;
  Broadcast bc; RegionManager rm;
  public Symbol getName() { return Symbol.GetSymbol("Hierarchy"); }
  public void link(PortedProcessor p) {
    pp = p;
    ag = (ActiveGradient)p.getModule("ActiveGradient");
    ns = (NeighborSet)pp.getModule("NeighborSet");
    pn = (PersistentNodeB)pp.getModule("PersistentNode");
    bc = (Broadcast)p.getModule("Broadcast");
    bc.openBroadcastPort(this,myType);
    rm = (RegionManager)p.getModule("RegionManager");
    pp.addClockListener(this);
  }
  
  // init just has to create the first level
  public void init() {
    id.add(0,new Double(pp.getUID())); nbrs.add(0,new Vector(2));
    id.add(1,new Double(Double.NaN)); nbrs.add(1,new Vector(2));
  }

  // on clock ticks, update the hierarchy
  public boolean signalEvent(Symbol name,Object data) {
    boolean changed = false;
    if(name==PortedProcessor.kClock) {
      update();
    } else if(name==myType) { // convergecast goes out...
    } else if(name==PortedProcessor.kTransmit) { // ack of convergecast
      //System.out.println("Poll complete:"+data);
      Object returnValue = ((Pair)((Pair)data).cdr()).cdr();
      int level = ((Integer)((Pair)returnValue).car()).intValue();
      Vector nbrdata = (Vector)((Pair)returnValue).cdr();
      if(level<nbrs.size()) {
        nbrs.set(level,nbrdata);
        sendNeighbors(level,true);
      }
    }
    return changed;
  }

  public String toString() { 
    String s = "Hierarchy: "+id.toString()+"\n\t"+nbrs.toString(); 
    return s;
  }

  //  public String toString() { return "Hierarchy: [s="+stability+"]"+levels.toString(); }
  
  //********** External Accessors ***********
  public int size() { return id.size(); }
  public Vector getID() { return (Vector)id.clone(); }

  public static final Symbol myType = Symbol.GetSymbol("HM");
  public static final Symbol bcast = Symbol.GetSymbol("infowaveP");
  public static final Symbol bcast2 = Symbol.GetSymbol("infowaveN");
  public static final Symbol myType2 = Symbol.GetSymbol("HMNbr");
  Vector id = new Vector(2);
  Vector nbrs=new Vector(2);

  void update() {
    receiveState();
    chooseL0Parent(); // elect self into a level zero group
    // for each higher level, maintain the hierarchy
    maintainHierarchy();
    // run the maintainance of level PersistentNodes
    for(int i=1;i<id.size();i++) maintainPNs(i);
  }

  static final int kDimension = 2;
  static final int kBaseRadius = 2;//4
  static final int kRadiusFactor = 2;
  static final double density = 3.2; // for now, a hard-wired estimate
  
  // base level is ONE, not zero
  private void maintainPNs(int l) {
    int radius = (int)(Math.pow(kRadiusFactor,l-1)*kBaseRadius);
    double p_l = 1/(density*0.5*Math.pow(2*1.5*radius,1+kDimension));

    // get the PN data and filter to retain only this level
    Vector nodes = getLevelNodes(l);
    Vector penumbras = getLevelPenumbras(l,2.5);
    
    if(nodes.size()>1) { // if we're in two nodes, kill lesser
      Iterator i=nodes.iterator(); Pair best=null;
      while(i.hasNext()) {
        Pair nid = (Pair)i.next();
        if(best==null) { best=nid; }
        else if(((Double)best.cdr()).compareTo(nid.cdr())<0) {
          pn.killNode(best); best=nid;
        } else {
          pn.killNode(nid);
        }
      }
    } else if(penumbras.isEmpty()) { // if we're in none, start one
      if(Math.random()<p_l) {
        Pair nid = NID(l,new Double(Math.random()));
        pn.initiateNode(nid,radius,3,
                        new NodeLevelExclusionEstimator(nid,LID(l)));
      }
    }
  }

  private Vector getLevelNodes(int l) {
    Vector nodes = pn.getNodes();
    Iterator i=nodes.iterator();
    while(i.hasNext()) {
      Object nid=i.next();
      if(!(nid instanceof Pair) || (LID(l)!=((Pair)nid).car())) i.remove();
    }
    return nodes;
  }
  private Vector getLevelPenumbras(int l,double pu) {
    Vector penumbras = pn.getNodePenumbras(pu);
    Iterator i=penumbras.iterator(); 
    while(i.hasNext()) { 
      Object nid=i.next();
      if(!(nid instanceof Pair) || (LID(l)!=((Pair)nid).car())) i.remove();
    }
    return penumbras;
  }
  
  // In this function, a processor opts into the closest node as parent.
  // If another node is much closer, then it will opt into that node
  // instead.
  private void chooseL0Parent() {
    Vector parents = getLevelPenumbras(1,3);
    boolean parentok = false;
    int parentdist=-1;
    int best=-1;
    Pair candidate=null;

    Iterator i=parents.iterator();
    while(i.hasNext()) {
      Pair nid = (Pair)i.next();
      if(nid.cdr().equals(id.get(1))) {
        parentok=true; parentdist=pn.centerDistance(nid);
      }
      int dist = pn.centerDistance(nid);
      if(dist!=-1 && (candidate==null || dist<best)) {
        best=dist; candidate = nid;
      }
    }
    // if parent is OK, take best if it's a full base better
    if(parentok) {
      if(candidate!=null && (parentdist-best)>=kBaseRadius)
        id.set(1,candidate.cdr());
    } else if(candidate!=null) {
      id.set(1,candidate.cdr());
    } else {
      id.set(1,new Double(Double.NaN));
    }
  }

  // To be executed by the center processor of a node.
  // Chooses the closest one, then stays with it until it 
  // drifts out of the area of influence
  private void chooseLnParent(int l) {
    if(id.size()<l+2) return; // make sure we're in range
    Vector parents = getLevelPenumbras(l+1,2.5);
    boolean parentok = false;
    int best=-1; Pair candidate=null;
    Iterator i=parents.iterator();
    while(i.hasNext()) {
      Pair nid = (Pair)i.next();
      if(nid.cdr().equals(id.get(l+1))) { parentok=true; break; }
      int dist = pn.centerDistance(nid);
      if(dist!=-1 && (candidate==null || dist<best)) 
        { best=dist; candidate=nid; }
    }
    if(parentok) {} // we're fine
    else if(candidate!=null) {
      id.set(l+1,candidate.cdr());
    } else {
      id.set(1+1,new Double(Double.NaN));
    }
  }

  private void maintainHierarchy() {
    adjustHeight();
    // walk nodes, checking which we're central to. When one is found,
    // run the update routines
    Iterator i = pn.getNodes().iterator();
    while(i.hasNext()) {
      // get nodes and filter for non-hierarchy nodes
      Object n = i.next(); if(!(n instanceof Pair)) continue;
      Pair nid = (Pair)n; if(!isLID(nid.car())) continue;
      // check if we're in the center
      int dist = pn.centerDistance(nid);
      if(dist==0) {
        int pfx = myType.toString().length();
        String lstr = nid.car().toString().substring(pfx);
        int level = (new Integer(lstr)).intValue();
        
        // run the update program
        if(!rm.inRegion(nid)) // make sure the region's OK
          rm.addRegion(nid,myType,new NodeRegion(nid));
        chooseLnParent(level);
        sendState(level);
      }
    }
  }

  // The requirement is that precisely one level have no neighbors,
  // and that level must be topmost.
  private void adjustHeight() {
    int i;
    for(i=1;i<id.size();i++) {
      if(((Vector)nbrs.get(i)).size()==0) break;
    }
    // the number left in i is the id of the topmost level
    id.setSize(i+1); nbrs.setSize(i+1);
    for(i=0;i<nbrs.size();i++) {
      if(id.get(i)==null) {
        id.set(i,new Double(Double.NaN));
        nbrs.set(i,new Vector());
      }
    }
  }

  // transmits the infowave to other members of the node
  double pollfreq = 0.1; // poll at rate once every 10*r rounds
  private void sendState(int level) {
    sendParent(level); // first, send the parent
    sendNeighbors(level,false); // second, send the neighbors
  }
   
  private void sendParent(int level) {
    if(!(level+1<id.size())) return;
    Object data=id.get(level+1);
    Object gid = iwID(level,(Double)id.get(level));
    VersionedGradient g = (VersionedGradient)ag.get(gid);
    if(g==null) {
      PropagationTest prop = 
        new NodePropagation(NID(level,(Double)id.get(level)),3);
      g=new VersionedGradient(gid,myType,data,prop);
    } else {
      g.data=data;
      g.incrementVersion(); g.setQuality(Math.random());
    }
    ag.sendGradient(g);
  }
  private void sendNeighbors(int level,boolean fresh) {
    if(!(level<id.size())) return;
    Object data=((Vector)nbrs.get(level)).clone();
    Object gid = nwID(level,(Double)id.get(level));
    Object nid = NID(level,(Double)id.get(level));
    VersionedGradient g = (VersionedGradient)ag.get(gid);
    if(g==null) {
      PropagationTest prop = new NodePropagation(nid,3);
      g=new VersionedGradient(gid,myType2,data,prop);
    } else { // do nothing here: state gets incremented on bcast returns
      if(fresh) {
        g.incrementVersion(); g.data=data;
      } else {
        g.setQuality(g.getQuality()+1);
      }
    }
    ag.sendGradient(g);

    if(!fresh) { // possibly initiate a new neighbor poll:
      double radius = (Math.pow(kRadiusFactor,level-1)*kBaseRadius);
      if(Math.random()<(pollfreq/radius)) { // initiate one every kr rounds
        bc.convergecast(myType,new NeighborPoll(nid,level,2.5),nid);
        //System.out.println("startpoll "+nid+", "+level);
      }
    }
  }

  // Key question: if I send to a sub-state, and it sends back, what
  // should I do to my own state?
  private void receiveState() {
    // get the leader broadcast
    Set s = ag.getType(myType);
    Iterator i = s.iterator();
    while(i.hasNext()) {
      Gradient g = ag.get(i.next());
      int level = ((Integer)((Tuple)g.gid).third()).intValue();
      Double nid = (Double)((Tuple)g.gid).fourth();
      if(id.size()>level+1 && nid.equals(id.get(level))) {
        id.set(level+1,g.data);
      }
    }
    // get the neighbor broadcast
    s = ag.getType(myType2);
    i = s.iterator();
    while(i.hasNext()) {
      Gradient g = ag.get(i.next());
      int level = ((Integer)((Tuple)g.gid).third()).intValue();
      Double nid = (Double)((Tuple)g.gid).fourth();
      if(id.size()>level && nid.equals(id.get(level))) {
        nbrs.set(level,g.data);
      }
    }
  }

  // doesn't actually check anything but the prefix right now. 
  static boolean isLID(Object o) {
    if(!(o instanceof Symbol)) return false;
    String s = o.toString();
    if(s.startsWith(myType.toString())) return true; // close enough...
    else return false;
  }
  static Symbol LID(int level) 
  { return Symbol.GetSymbol(myType+""+level); }
  static Pair NID(int level, Double id) {
    return new Pair(LID(level),id);
  }
  static Tuple iwID(int level, Double id) {
    return new Tuple(myType,bcast,new Integer(level),id);
  }
  static Tuple nwID(int level, Double id) {
    return new Tuple(myType,bcast2,new Integer(level),id);
  }
}

class NeighborPoll implements ConvergeCast {
  HashSet h = new HashSet(2);
  Object nid; int level; double pu;
  public NeighborPoll(Object nid,int level,double pu)
  { this.nid=nid; this.level=level; this.pu=pu; }

  static Symbol LID(int level) 
  { return Symbol.GetSymbol("HM"+level); }
  private Set getLevelPenumbras(PortedProcessor pp) {
    PersistentNodeB pn = (PersistentNodeB)pp.getModule("PersistentNode");
    HashSet s = new HashSet(pn.getNodePenumbras(pu));
    Iterator i=s.iterator();
    while(i.hasNext()) {
      Object nid=i.next();
      if(!(nid instanceof Pair) || (LID(level)!=((Pair)nid).car())) i.remove();
    }
    return s;
  }

  private Object poll(PortedProcessor pp) {
    h.addAll(getLevelPenumbras(pp));
    h.remove(nid);
    return h;
  }

  public Object getLeafValue(PortedProcessor pp) { return poll(pp); }
  public Object getBranchValue(PortedProcessor pp) { return poll(pp); }
  public Object deliverRoot(PortedProcessor pp) { 
    return new Pair(new Integer(level),new Vector((Set)poll(pp))); 
  }
  public void putBranchValue(PortedProcessor pp, Object input)
  { h.addAll((Set)input); }
  public void putRootValue(PortedProcessor pp, Object input) 
  { h.addAll((Set)input); }

  public Object deliverLeaf(PortedProcessor pp) { return null; }
  public Object deliverBranch(PortedProcessor pp) { return null; }
  public Object fail(PortedProcessor pp) { return null; }
  
  public ConvergeCast getChild() { return new NeighborPoll(nid,level,pu); }
}

