package modules.hierarchy;

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

public class Hierarchy implements ProcessorModule {
  //********** ProcessorModule Glue ***********
  //  These are the glue routines used to patch into the processor
  PortedProcessor pp; ActiveGradient ag; NeighborSet ns;
  public Symbol getName() { return Symbol.GetSymbol("Hierarchy"); }
  public void link(PortedProcessor p) {
    pp = p;
    ag = (ActiveGradient)p.getModule("ActiveGradient");
    ns = (NeighborSet)pp.getModule("NeighborSet");
    pp.addClockListener(this);
  }
  // init just has to create the first level
  public void init() {
    levels.add(new Level(pp.getUID(),0));
    commitstate();
  }
  // on clock ticks, update the hierarchy
  public boolean signalEvent(Symbol name,Object data) {
    boolean changed = false;
    if(name==PortedProcessor.kClock) {
      gatherstate();
      update();
      commitstate();
    }
    return changed;
  }

  public String toString() { return "Hierarchy: [s="+stability+"]"+levels.toString(); }
  
  //********** External Accessors ***********
  public int size() { return id.length; }
  public double[] getID() { return id; }
  public int getStability() { return stability; }
  public int getStability(int i) { 
    if(i>=0 && i<lvlStability.length) return lvlStability[i]; 
    else return -1;
  }
  public int status(int i) { 
    if(i>=0 && i<levels.size()) return ((Level)levels.get(i)).getStatus();
    else return Level.NID_PENDING;
  }
  // Convergence test:
  // this processor has converged if:
  // 1. top level has wait-time zero
  // 2. top level has status NID_PENDING
  // 3. top level has no neighbors
  // 4. every other level has status NID_SELF or NID_NEIGHBOR
  public boolean converged() { 
    Level top = (Level)levels.get(id.length-1);
    if(top.timeout>0) return false; // 1
    if(top.getStatus()!=Level.NID_PENDING) return false; // 2
    Set nbrs = ag.getTypeLive(LID(id.length-1));
    if(!nbrs.isEmpty()) return false; // 3
    for(int i=0;i<id.length-1;i++) {
      Level l = (Level)levels.get(i);
      if(l.getStatus()==Level.NID_PENDING) return false; // 4
    }
    return true;
  }

  public static final Symbol myType = Symbol.GetSymbol("HM");
  Vector levels = new Vector();
  double[] id=new double[0]; int[] lvlStability=new int[0];
  HashSet localNbrs = new HashSet();
  int stability=0;

  // grunge/transation routines
  // loads localNbrs
  //  For any immediately neighboring group, pluck that information
  //  from the neighborset immediate nbr info, so we can pass it 
  //  along in a gradient.
  private void gatherstate() {
    localNbrs.clear();
    Iterator i = ns.getNeighbors();
    while(i.hasNext()) { // 1a: find local neighbors
      Level[] nbrl = (Level[])ns.getData(myType,i.next()); 
      if(nbrl==null) continue;
      int minsize = Math.min(nbrl.length,levels.size());
      for(int j=0;j<minsize;j++) {
        if(nbrl[j].ID!=((Level)levels.get(j)).ID)
          localNbrs.add(nbrl[j]);
      }
    }
  }
    
  // sucks level names into id[]
  // dumps levels into neighborset data
  //  In order that our neighbors can originate cross-boundary 
  //  information, we need to dump our state into the neighborset
  private void commitstate() {
    int n = levels.size();
    double[] oldid = id; int[] oldlvls = lvlStability;
    boolean changed=false;
    id = new double[n]; lvlStability = new int[n];
    Level[] nsdata = new Level[n];
    for(int i=0;i<n;i++) {
      Level l = (Level)levels.get(i);
      if(oldid.length>i) {
        if(l.ID != oldid[i]) { lvlStability[i]=0; changed=true; }
        else lvlStability[i] = oldlvls[i]+1;
      }
      id[i] = l.ID; nsdata[i] = (Level)l.clone();
    }
    ns.setData(myType,nsdata);
    if(changed || (oldid.length!=n)) stability=0; else stability++;
  }

  /*
    For an update, we do two steps:
    1. push the gradients of local neighbors
    2. for each level:
      2a. assemble a list of neighbors
      2b. calculate the nextID
      2c. check for ID updates and level kills
      2d. for the top level, spawn a new level if necessary
  **/
  private void update() {
    // 1. push the gradients of local neighbors
    Iterator i=localNbrs.iterator();
    while(i.hasNext()) { 
      Level nbrl = (Level)i.next();
      Symbol type = LID(nbrl.level);
      PropagationTest limit = new HierarchyPropagation(nbrl.level,nbrl.ID);
      ag.sendGradient(new Pair(type,new Double(nbrl.ID)),type,nbrl,limit);
    }
    // 2: for each level
    for(int j=0;j<levels.size();j++) {
      Level l = (Level)levels.get(j);
      // 2a. assemble a list of neighbors
      Set nbrs = ag.getTypeLive(LID(j));
      HashSet ndata = new HashSet();
      i=nbrs.iterator(); while(i.hasNext()) {ndata.add(ag.get(i.next()).data);}
      // 2b. calculate the nextID
      l.calculateNextID(ndata);
      // 2c. check for ID updates and level kills
      // Destroy if: no neighbors at level i -> destroy all above it
      //   optionally: if NID_PENDING, destroy all above it
      if(nbrs.size()==0) {
        for(int k=levels.size()-1;k>j;k--) levels.removeElementAt(k);
      }
      // Modify if: i-1 nextID != i ID
      if(j>0) { double preID=((Level)levels.get(j-1)).nextID;
        if(l.ID!=preID && !Double.isNaN(preID)) 
          { l.ID=preID; l.setStatus(Level.NID_PENDING); }
      }
      // 2d. for the top level, spawn a new level if necessary
      // Create if: top level isn't NID_PENDING and has timed out
      if(l.timeout>0) l.timeout--;
      if(j==levels.size()-1 && l.getStatus()!=Level.NID_PENDING
         && l.timeout==0) {
        //if(j<=3) // temporary brake
          levels.add(new Level(l.nextID,j+1));
      }
    }
  }


  static Symbol LID(int level) 
  { return Symbol.GetSymbol(myType+""+level); }
}


/***** HIERARCHY PROPAGATION SUBCLASS *****/
class HierarchyPropagation implements PropagationTestExt {
  DistancePropagation dp; double gid; int level;
  static final double n_0 = 1;
  static final double n_m = 2;

  public HierarchyPropagation(int lvl, double id) {
    level = lvl; gid=id;
    int dist = (int)(n_0*Math.pow(n_m,lvl));
    dp = new DistancePropagation(dist);
  }

  // the gradients used flow within regions, or across a boundary if 
  // the hopcount is low enough
  // Three cases:
  // 1. ID==gid: do not propagate
  // 2. nbrID!=ID!=gid: propagate if dp propagates
  // 3. nbrID==ID!=gid: always propagate
  public boolean propagate(Gradient g, PortedProcessor pp, Object srcID) {
    NeighborSet ns = (NeighborSet)pp.getModule("NeighborSet");
    Level[] myID = (Level[])ns.getData(Hierarchy.myType);
    Level[] nbrID = (Level[])ns.getData(Hierarchy.myType,srcID);
    if(myID==null || nbrID==null || myID.length<=level || nbrID.length<=level)
      return false;
    if(myID[level].ID==gid) return false;
    else if(myID[level].ID==nbrID[level].ID) return true;
    else return dp.propagate(g,pp);
  }

  public boolean propagate(Gradient g, PortedProcessor pp) {
    System.out.println("Improper call to hierarchy propagation!");
    return false;
  }
}
