//AList Exits, Ramps, Corridors, Aisles, Rows;
//AList ExitNodes, RampNodes, CorridorNodes, AisleNodes, RowNodes;
AList ExitNodes, Ramps, Corridors, Aisles, Rows, Bombs, FieldExitNodes, FieldExitCorridors, BottomRows;


class Graph {
  int numAgents, agentSize;

  //UNITS in FT
  static final float ftPerInputUnit = 5; //3.65; //How many feet per unit?  Lets us use standard units
  static final float secsPerStep = 0.25;
  static final float personWalkPerSec = 10.0 / ftPerInputUnit;
  static final float personWalkPerStep = personWalkPerSec * secsPerStep;
  //  1 (square meter) = 10.7639104 square feet
  float crowdedDensity = 4 / 10.7639 * sq(ftPerInputUnit); //4 people per square meter
  float trampleDensity = 5*crowdedDensity;

  static final float singleFileWidth = 1.5/ftPerInputUnit;
  static final float widthOfRow = 1.5 * singleFileWidth;
  static final float widthOfAisle = 2.0 * singleFileWidth;
  static final float widthOfCorridor = 12.0 * singleFileWidth; 




  static final String Exit = "Exit";
  static final String Ramp = "Ramp";
  static final String Corridor = "Corridor";
  static final String Aisle = "Aisle";
  static final String Row = "Row";

  static final String ExitList = "ExitList";
  static final String MinExit = "MinExit";
  static final String ExitDistances = "ExitDistances";
  //  static final String BombData = "BombData";
  static final String BombStep = "BombStep";
  static final String BombRadius = "BombRadius";
  static final String SavedLabel = "SavedLabel";
  static final String FieldExitNode = "FieldExitNode";
  static final String FieldExitCorridor = "FieldExitCorridor";
  static final String BottomRow = "BottomRow";


  int nodeRadius = 0, nodeShape = Node.POINT, steps = 0;
  boolean useLights = false, showLabels = false, useIDLabels = false;
  static final float bombWeight = 100.0f, randomAgents = .2f;


  color nodeColor = color(128), edgeColor = color(0,255,255, 50); // REMIND: Make defaults in class.
  color rampColor = color(0,255,0, 50), corridorColor = color(50,100,255, 100);
  color aisleColor = color(0,255,0, 50), rowColor = color(255,255,0, 50), bombColor = color(255,0,0, 128);
  color injuredColor = color(255,0,0);

  boolean useBlenderCoords = true; //Whether stadium and agent I/O should presume blender coords.

  // ========== Construction ==========
  Graph (int numAgents, int agentSize) {
    Agents.clear();
    InjuredAgents.clear();
    Edges.clear();
    Nodes.clear();

    this.numAgents = numAgents;
    this.agentSize = agentSize;
  }

  void registerGraph() {
    Nodes.setShowLabel(showLabels);
    Edges.setShowLabel(showLabels);
    Nodes.setDataByData(SavedLabel,Base.Label);
    Edges.setDataByData(SavedLabel,Base.Label);

    //Exits     = Edges.with(Base.Type, Exit);
    Ramps     = Edges.with(Base.Type, Ramp);
    Corridors = Edges.with(Base.Type, Corridor);
    Aisles    = Edges.with(Base.Type, Aisle);
    Rows      = Edges.with(Base.Type, Row);

    Bombs         = Nodes.with(BombStep);
    ExitNodes     = Nodes.with(Base.Type, Exit);
    FieldExitNodes = Nodes.with(Base.Type, FieldExitNode);
    FieldExitCorridors = Edges.with(Base.Type, FieldExitCorridor);
    BottomRows = Edges.with(Base.Subtype, BottomRow);
    //RampNodes     = Nodes.with(Base.Type, Ramp);
    //CorridorNodes = Nodes.with(Base.Type, Corridor);
    //AisleNodes    = Nodes.with(Base.Type, Aisle);
    //RowNodes      = Nodes.with(Base.Type, Row);

    //println("SavedLabel Test Ramps:"+arrayListToString(Ramps.map(SavedLabel)));

    createAgents(numAgents, personWalkPerStep); // create agents b4 floodfill: it readjusts agents too.
    setupLineGraphs();
    InjuredAgents.clear();
    numExitedAgents = 0;
    deathDueToTrampling = 0;

    Rows.ask(new ModifyWeight(1.5f));
    Corridors.ask(new ModifyWeight(.75f));
    floodFill(ExitNodes);
    setAgentExits();

    Ramps.setColor(rampColor);
    Corridors.setColor(corridorColor);
    Aisles.setColor(aisleColor);
    Rows.setColor(rowColor);

  }

  int getBiasedEdge(AList edges, float w[]) {
    float total = 0;
    Edge e;

    for (int i=0; i< w.length; i++) {
      total += w[i];
    }
    float pick = random(total);
    total = 0;
    int j = 0;
    while (total < pick && j < w.length) {
      total += w[j];
      j ++;
    }
    j--;
    return j;
  }

  void createAgents(int numAgents, float initialSpeed){
    int maxTrys = 100;
    int j,pick;
    float w[] = new float[Rows.size()];
    for (int i=0; i<w.length; i++) {
      w[i] = ((Edge)Rows.get(i)).edgeLength;
    }

    Edge e = null;
    for(int i = 0; i<numAgents; i++) {
      j = 0;

      do {
        pick = getBiasedEdge(Rows, w);
        e = (Edge)Rows.get(pick);
        //e = (Edge)Rows.randomOneOf();
        j++;
      } 
      while (e.isFull() && j<maxTrys);
      w[pick] = e.edgeLength / (e.getAgentsHere().size() + 1);

      float percent = e.placeAgent();
      float speed = percent>0.50?initialSpeed:-initialSpeed;
      Agent a = new RibbonAgent(e, randomBrightColor(), agentSize, speed * (random(0.1) + 0.95), percent); //no label or breed/type
    }

    for (int i=0; i<Rows.size(); i++) {
      e = (Edge)Rows.get(i);
      e.placeAgentsUniform();
      println("Placed agents: " + e.getAgentsHere().size() + " Edge: " + e.id + " length: " + e.edgeLength * Graph.ftPerInputUnit + " density: " + e.calcCurrentDensity()/(sq(ftPerInputUnit)));
    }
  }


  void setAgentExits(){
    int ran = 0;
    for(int i = 0; i<Agents.size(); i++) {
      Agent a = (Agent)Agents.get(i);
      if (((RibbonAgent)a).fieldExit != null) continue;
      if (!changeExit && a.getCurrentExit() > 0) continue;
      ran += a.setAgentExit(confusion);
      goTowardExit(a);
    }
    println("setAgentExits: setting n random exits, n="+ran);
  }

  float distanceToNode(Agent a, Node n) {
    //only nodes of a's current exit
    if (n == a.edge().n0()) return a.percent * a.edge().len();
    if (n == a.edge().n1()) return (1.0 - a.percent) * a.edge().len();
    return 0.;    
  }

  void goTowardExit(Agent a) {
    float d1,d2;

    d1 = getDistanceToExit(a.toNode(), a.getCurrentExit()) + distanceToNode(a, a.toNode());
    d2 = getDistanceToExit(a.edge().nOther(a.toNode()), a.getCurrentExit()) + distanceToNode(a, a.edge().nOther(a.toNode()));
    if (d2 < d1) a.speed *= -1;
  }


  float getDistanceToExit(Node n, int i) {
    float d1 = ((Float)  ((ArrayList) n.getData(Graph.ExitDistances)).get(i)).floatValue();

    return d1;    
  }


  // ========== General I/O used for writing Graph and Agents ==========
  void writeAgents(Writer agentWriter) {
    StringBuffer s = new StringBuffer();
    s.append(""+steps);
    for(int i = 0; i<Agents.size(); i++) {
      Agent a = (Agent)Agents.get(i);
      if(useBlenderCoords)
        s.append(","+a.id+" "+NF(a.x)+" "+NF(-a.z)+" "+NF(-a.y));
      else
        s.append(","+a.id+" "+NF(a.x)+" "+NF(a.y)+" "+NF(a.z));
    }
    s.append(System.getProperty("line.separator"));
    writeWriter(agentWriter,s.toString());
  }

  String bombString() { // could be global from ToyGraph
    String s = "Bombs [";
    for(int i = 0; i<Bombs.size(); i++) {
      Node n = (Node)Bombs.get(i);
      s+=(i==0?"":",")+n.getID()+" "+n.getData(BombStep)+" "+n.getData(BombRadius);
    }
    return s+"]";
  }

  // ========== Drawing/Stepping ==========
  void paint() {
    if (useLights) lights();
    for(int i = 0; i<Edges.size(); i++) {
      ((Edge)Edges.get(i)).paint();
    }
    for(int i = 0; i<Nodes.size(); i++) {
      ((Node)Nodes.get(i)).paint();
    }
    for(int i = 0; i<Agents.size(); i++) {
      ((Agent)Agents.get(i)).paint();
    }
  }


  public void step() {
    if (graph.steps() == 0)
          floodFillBottomRows();

    if ((graph.steps() % (confusion?120:60) == 0) && (graph.steps() > 0)) {
      floodFill(ExitNodes);
      setAgentExits();
    }

    for(int i = 0; i<Edges.size(); i++) {
      ((Edge)Edges.get(i)).step();   
    }

    Agent agent;

    for(int i = 0; i<Agents.size(); i++) {
      agent = (Agent)Agents.get(i);
      agent.step();
    }

    //Data
    agentVelocitySum = 0;
    agentVelocitySquareSum = 0;
    agentCount = 0;


    float x,y,z,v;

    for(int i = 0; i<Agents.size(); i++) {
      agent = (Agent)Agents.get(i);
      if (((RibbonAgent) agent).fieldExit != null) continue;
      x = agent.x; 
      y = agent.y; 
      z = agent.z;
      agent.setXYZ();
      v = sqrt(sq(agent.x - x) + sq(agent.y - y) + sq(agent.z-z))*ftPerInputUnit/secsPerStep;
      agentVelocitySum += v;
      agentVelocitySquareSum += v*v;
      agentCount += 1;

      //somehow agent.percent can get out of whack in the step... this fixes it.
      if (!(agent.percent >=0 && agent.percent<=1)) agent.percent = 0.5;
    }


    double mean = (agentVelocitySum / agentCount);
    //("agentVelSum: " + agentVelocitySum + " agentVelSqSum: " + agentVelocitySquareSum);
    //out.println( "Num agents: " + agentCount + " Avg velocity: " + mean + " Var: " + (agentVelocitySquareSum/agentCount - mean*mean));

    stepBombs();
    steps++;

  }

  void setLabelState(int i) {
    if (i == 0) {
      Nodes.setShowLabel(false);
      Edges.setShowLabel(false);
    } 
    else if (i==1) {
      Nodes.setShowLabel(true);
      Edges.setShowLabel(true);
      Nodes.setLabelByData(Base.ID);
      Edges.setLabelByData(Base.ID);

    } 
    else if (i == 2) {
      Nodes.setShowLabel(true);
      Edges.setShowLabel(true);
      Nodes.setLabelByData(Base.Type);
      Edges.setLabelByData(Base.Type);
    } 
    else if (i == 3) {
      Nodes.setShowLabel(true);
      Edges.setShowLabel(true);
      Nodes.setLabelByData(SavedLabel);
      Edges.setLabelByData(SavedLabel);
    }    

  }

  // ========== Floodfill ==========
  // Floodfill adds these data entries:
  // ExitDistances: AList of distances. ExitDistances[0] is distance for EdgeNodes[0] etc.
  // 

  void floodFill(AList exits) {
    Nodes.setData(ExitList, exits); // probably could just use global ExitNodes
    Nodes.setData(ExitDistances, null); // allows recalling floodfill
    for(int i = 0; i<exits.size(); i++) {
      Node ex = (Node)exits.get(i);
      ex.floodFill();
      Nodes.appendData(ExitDistances, ex, true);
      Nodes.unsetData(ex);
    }

    Nodes.setDataMinIndexOf(MinExit, ExitDistances);
  }

  void floodFillBottomRows() {
    Node n;
    Edge e;
    ArrayList stack = new ArrayList();
    for (int i=0; i<BottomRows.size(); i++) {
      e = (Edge) BottomRows.get(i);
      n = e.n0;
      n.distToBottom = 0;
      stack.add(n);      
      n = e.n1;
      n.distToBottom = 0;
      stack.add(n);
    }

    while (stack.size() > 0) {
      n = (Node)stack.remove(0);
      int nDist = n.distToBottom;
      AList edges = n.getEdges();
      for(int i = 0; i<edges.size(); i++) {
        e = (Edge)edges.get(i);
        int eDist = nDist+1;
        Node eNode = e.nOther(n);        
        int eNodeDist = eNode.distToBottom;
        if(eDist < eNodeDist) {
          eNode.distToBottom = eDist;
          stack.add(eNode);
        }
      }
    }
  }

  // ========== Misc ==========
  Bounds getBounds() {
    Bounds bounds = new Bounds();
    for(int i = 0; i<Nodes.size(); i++)
      bounds.update((Node)Nodes.get(i));
    return bounds;
  }
  void adjustAgentsSpeed(final float percent) { // REMIND: remove final when lib.
    Agents.ask(new Ask(){
      void ask(Object o) {
        Agent a = (Agent)o;
        a.setSpeed(a.getSpeed()*percent);
      }
    }
    );
  }
  void halfAgentSpeeds() {
    adjustAgentsSpeed(.5f);
  }
  void doubleAgentSpeeds() {
    adjustAgentsSpeed(2f);
  }
  int steps() {
    return steps;
  }

  // ========== Bombs ==========
  //REMIND: final required by inner classes, remove when go to lib.
  void setOffBomb(final Node n, final int radius) {
    AList agentsInRadius = Agents.inRadius(n, radius);
    agentsInRadius.setData(Agent.Paused, true);
    agentsInRadius.setColor(injuredColor);
    InjuredAgents.addAll(agentsInRadius);
    Agents.removeAll(agentsInRadius);

    Agent agent;
    for (int j=0; j<agentsInRadius.size(); j++) {
      agent = (Agent) agentsInRadius.get(j);
      agent.here.removeAgentHere(agent);
    } 
    AList edgesInRadius = Edges.inRadius(n, 1.5*radius); // make it a bit wider
    edgesInRadius.ask(new ModifyWeightByRadius(n, bombWeight));
    edgesInRadius.setColor(color(255,0,0,100)); // DEBUG AID
    floodFill(ExitNodes);

    //Inform agents to flee
    for (int i=0; i<Agents.size(); i++) {
      ((Agent)Agents.get(i)).flee(n.x,n.y,n.z);  
    }

    out.println("Bomb set off at Node:"+n.getData(Base.ID)+" injured="+agentsInRadius.size());
    n.setData(BombStep,steps);
    n.setData(BombRadius,radius);
    //n.setData(BombData, n.id+" "+steps+" "+radius);
    //out.println("Bomb data: id step radius = "+n.id+" "+steps+" "+radius);
    n.setShape(bombColor,Node.SPHERE,radius);
    if(!Bombs.contains(n))
      Bombs.add(n);
    //out.println(bombString());
  }
  void stepBombs() {
    for(int i = 0; i<Bombs.size(); i++) {
      Node n = (Node)Bombs.get(i);
      int nodeStep = n.getIntData(BombStep);
      if(nodeStep==steps) {
        if(n.getRadius()==nodeRadius) //avoid race condition w/ UI
          setOffBomb(n, n.getIntData(BombRadius));
      } 
      else if(nodeStep<steps) {
        float radius = max(nodeRadius,n.getRadius()-1);
        if(radius>nodeRadius)
          n.setShape(bombColor,Node.SPHERE,radius);
        else {
          n.setShape(nodeColor,Node.POINT,nodeRadius);
          //bombs.remove(n);
        }
      }
    }
  }


}

class Bounds {
  float minX = Float.MAX_VALUE, minY = Float.MAX_VALUE, minZ = Float.MAX_VALUE;
  float maxX = Float.MIN_VALUE, maxY = Float.MIN_VALUE, maxZ = Float.MIN_VALUE;
  float lenX, lenY, lenZ, midX, midY, midZ;
  void update(Node n) {
    minX=min(minX,n.x);
    minY=min(minY,n.y);
    minZ=min(minZ,n.z);
    maxX=max(maxX,n.x);
    maxY=max(maxY,n.y);
    maxZ=max(maxZ,n.z);
    lenX = abs(maxX-minX);
    lenY = abs(maxY-minY);
    lenZ = abs(maxZ-minZ);
    midX = (minX+maxX)/2f;
    midY = (minY+maxY)/2f;
    midZ = (minZ+maxZ)/2f;
  }
  String toString() {
    return "[["+
      minX+" "+maxX+" "+midX+" "+lenX+"] ["+
      minY+" "+maxY+" "+midY+" "+lenY+"] ["+
      minZ+" "+maxX+" "+midZ+" "+lenZ+"]]";
  }
}