// Ryan Swart. New Mexico Supercomputing challenge
// 2012, final report
// This code draws trees with labels in 3D



import shapes3d.utils.*;
import shapes3d.animation.*;
import shapes3d.*;


import processing.opengl.*;


import peasy.test.*;
import peasy.org.apache.commons.math.*;
import peasy.*;
import peasy.org.apache.commons.math.geometry.*;



PFont font;

//Program to draw tree
//String INPUTFILE = "powertree.txt";//use frac 1.0
//String INPUTFILE = "testtree.txt";//use frac .3
//String INPUTFILE = "Countries.txt";//use frac .6
String INPUTFILE = "Cities.txt";//use frac .8
//String INPUTFILE = "randomnumbertree.txt";//use frac .3
String OUTPUTFILE = "output.txt";

int maxlevels = 10;
int maxbranches = 25000;
int maxpnts = maxbranches + 1;
float inner_rad = 30;
float outer_rad = 500;
float[] rad = new float[maxlevels];
int a = 1;
color c = color(250, 250, 250);
float frac = 0.6;//fraction of the circle used for drawing


Branch[] b = new Branch[maxbranches];
int[][] BranchesAtLevel = new int[maxlevels][2];

// npt means number of the point
// ex. npt["The Oracle"] = 0
HashMap<String, Integer> npt = new HashMap<String, Integer>();

// osn means output string name of the point
// ex. osn[0] = "The Oracle"
String[] osn = new String[maxpnts];

float[] x = new float[maxpnts];
float[] y = new float[maxpnts];

PeasyCam cam;

int[] pntsinlvl = new int[maxlevels];
int[][] pntlvl = new int[maxlevels][2];
int[][] childofpnt = new int[maxpnts][2];


float ang = radians(30.0);
float motherang = radians(45.0);
float length = 100.0;
float th=5.0;

int nbranches=0; // number of branches
int npts = 0; // number of points
int motherbranch;
int level=0;// Set the level
int nb; // branch counter

float x0, y0; // center of tree at the root

void setup() {
  // usual stuff
  size(1100, 1100, OPENGL);
  smooth();
  background(250, 250, 250);
  //Set parameters for peasycam
  cam = new PeasyCam(this, 1100);
  cam.setMinimumDistance(1);
  cam.setMaximumDistance(1100);
  //Set the text font and size
  font = loadFont("ComicSansMS-48.vlw");
  textFont(font, 2);
  for ( int j=0; j < maxlevels; j++) {
    rad[j] = inner_rad + j*(outer_rad - inner_rad)/(maxlevels-1);
  }

  // read tree branches file
  nb = 0;
  int pnt0 = 0;
  int pnt1 = 1;
  x0 = width/2; 
  y0 = height/2;
  int pntCounter = 0;
  String[] lines = loadStrings(INPUTFILE);
  for (int i = 1; i < lines.length; i++) {
    String[] pieces = split(lines[i], ',');
    // use dictionaries osn and npt
    // is the point named pieces[0] in npt?
    if (npt.containsKey(pieces[0])) {
      pnt0 = npt.get(pieces[0]);
    }
    else {// if not, add the point named pieces[0] to pnt
      npt.put(pieces[0], pntCounter);
      osn[pntCounter] = pieces[0];
      pnt0 = pntCounter;
      pntCounter += 1;
    }  
    //is the point named pieces[1] in npt?
    if (npt.containsKey(pieces[1])) {
      pnt1 = npt.get(pieces[1]);
    }
    else {// if not, add pieces[1] to pnt
      npt.put(pieces[1], pntCounter);
      osn[pntCounter] = pieces[1];
      pnt1 = pntCounter;
      pntCounter += 1;
    }  

    b[i-1] = new Branch(this, pnt0, pnt1, length, radians(90.), th, 0.0, 0.0, c);
    nb++;
  }  

  npts = pntCounter;
  nbranches = nb;


  // Find the root of the tree 
  // this should be the first point on the first branch
  // else exit with error message
  int root = b[0].branchStart;
  for ( int i = 0; i < nb; i++ ) {
    if ( root == b[i].branchEnd ) {
      exit();
    }
  }
  // at this stage nb = # branches


  // find level 1 branches
  // note that the root node is at level 0
  // branches connected to the root is at branch level 1
  // the next level of points are at level 1

  for ( int i = 0; i < nbranches; i++) {
    if ( root == b[i].branchStart ) { 
      b[i].level = 1;
    }
  } 
  // find level 2 and higher branches
  for ( level=2; level < maxlevels; level++ ) {
    for ( int i = 0; i < nbranches; i++) {
      if ( b[i].level == level-1 ) {
        // now find all branches not yet seen and attached to b[i]
        for ( int j = 1; j < nbranches; j++) {
          //println( "    .....  branch # j = " + j);
          if ( b[j].level == -1 && i!=j ) {
            if ( isAttached( b[i], b[j] )) {
              b[j].level = level;
            };
          };
        };
      };
    };
  };
  maxlevels = level;

  // write tree out
  for ( int a = 0; a < nbranches; a++) {
    println("branch = "+ a + ", bstart = " + b[a].branchStart + ", bend = "+ b[a].branchEnd +", level = "+ b[a].level);
  }

  //write Hashmap of osn
  // Hashmap is your own designable dictionary
  for (int i = 0; i < npts; i++) {
    println(i + "," + osn[i]);
  }

  //compute branch end and branch start at each level
  nb = 0;
  BranchesAtLevel[0][0]=0;
  BranchesAtLevel[0][1]=0;
  BranchesAtLevel[1][0]=0;
  level = 1;
  while (nb < nbranches-1) {
    nb++;
    if ( b[nb].level != level ) {
      BranchesAtLevel[level][1] = nb - 1;
      //you may proceed to the next level
      level++;
      BranchesAtLevel[level][0] = nb;
      //nb++;
    }
  }
  BranchesAtLevel[level][1] = nb;
  maxlevels = level+1;
  for ( int level = 1; level < maxlevels; level++) {
    println("BranchesAtLevel = " + level + " start at " + BranchesAtLevel[level][0]);
    println("BranchesAtLevel = " + level + " end at " + BranchesAtLevel[level][1]);
  }

  //calculate pntsinlvl, pntlvl, pntchild
  for ( int level = 1; level < maxlevels; level++) {
    int b0 = BranchesAtLevel[level][0]; // starting branch # at this level
    int b1 = BranchesAtLevel[level][1]; // ending branch # at this level
    pntlvl[level][0] = b[b0].branchEnd; // # of first point at this level
    pntlvl[level][1] = b[b1].branchEnd; // # of last point at this level
    pntsinlvl[level] = pntlvl[level][1] - pntlvl[level][0] + 1; //the # of points in this level
    println("at level = "+ level+ ": points # starts at " +  pntlvl[level][0] +  " and ends at "  + pntlvl[level][1] + " = " +  pntsinlvl[level] + " points ");
  } 

  int pnt; 

  // set childofpnt = -1 if pnt has no children
  for ( pnt=0; pnt < npts; pnt++) {
    childofpnt[pnt][0] = -1;
    childofpnt[pnt][1] = -1;
  }


  // calculate children of each point that is not a leaf
  childofpnt[0][0] = pntlvl[1][0];
  childofpnt[0][1] = pntlvl[1][1];


  // sweep forwards
  for ( int i = 1; i <= BranchesAtLevel[maxlevels-1][1]; i++ ) {
    int p0 = b[i].branchStart;
    int p1 = b[i].branchEnd;
    childofpnt[p0][1] = p1;
  }

  // sweep backwards
  for ( int i = BranchesAtLevel[maxlevels-1][1]; i >0 ; i-- ) {
    int p0 = b[i].branchStart;
    int p1 = b[i].branchEnd;
    childofpnt[p0][0] = p1;
  }  

  childofpnt[0][0] = pntlvl[1][0];
  childofpnt[0][1] = pntlvl[1][1];

  for ( pnt=0; pnt < npts; pnt++) {
    println( "children of point "+pnt+" starts at " + childofpnt[pnt][0] + " & ends at "+ childofpnt[pnt][1]);
  }



  //find the position of the leaves
  level = maxlevels - 1;
  float noleaves = pntsinlvl[level];
  float smangle = frac*TWO_PI/noleaves;
  float angle = 0.0;
  float ar = 100.0;
  for (int i = pntlvl[level][0]; i <= pntlvl[level][1]; i++) {
    x[i] = width/2 + rad[level]*cos(angle);
    y[i] = height/2 + rad[level]*sin(angle);
    angle = angle + smangle;
  }

  //Done with leaves  
  int childstart, childend;
  for (level = maxlevels - 2; level >= 0; level--) {
    println("level =" + level);
    for (pnt = pntlvl[level][0]; pnt <= pntlvl[level][1]; pnt++) {
      println("point = " + pnt);
      childstart = childofpnt[pnt][0];
      childend = childofpnt[pnt][1];
      x[pnt] = xAveragePlacing( x[childstart], y[childstart], x[childend], y[childend]);
      y[pnt] = yAveragePlacing( x[childstart], y[childstart], x[childend], y[childend]);
      x[pnt] = xKickBack(x[pnt], y[pnt], x0, y0, rad[level]);
      y[pnt] = yKickBack(x[pnt], y[pnt], x0, y0, rad[level]);
      if ( pnt == 0) {
        x[pnt] = x0;
        y[pnt] = y0;
      }
    }
  }

  for ( int i = 0; i < nbranches; i++) {
    pnt = b[i].branchStart;
    b[i].x1 = x[pnt];
    b[i].y1 = y[pnt];
    pnt = b[i].branchEnd;
    b[i].x2 = x[pnt];
    b[i].y2 = y[pnt];
  }
}
//Drawing the root of the tree
void draw() {
  background(250, 250, 250);
  pushMatrix();
  fill(107, 145, 224);
  translate(width/2, height/2, 0);
  sphere(a);
  popMatrix();
  for ( int i = 0; i < nbranches; i++) {
    b[i].draw();
  }
}

// our Class that is used to describe the branches
class Branch {
  int branchStart, branchEnd;
  float len, ang, th, x1, y1, x2, y2;
  color bc;
  int level;
  Bezier3D tube; // shapes3d Bezier line
  BezTube btube; // shapes3d Bezier tube around Bezier line 
  PApplet pa;

  // constructor
  Branch(PApplet papa, int brStart, int brEnd, 
  float length, 
  float angle, 
  float thickness, 
  float xstart, float ystart, 
  color bcolor) {
    pa = papa;
    level = -1; //implies not set
    branchStart = brStart;
    branchEnd = brEnd;
    len = length;
    ang = angle; 
    th = thickness;
    x1 = xstart;
    y1 = ystart;
    x2 = x1 + len*cos(ang);
    y2 = y1 + len*sin(ang); 

    bc = bcolor;
  }


  void draw () {
    //Draw the BezTubes, then add text
    float textangle;  
    PVector[] p = new PVector[] {
      new PVector(x1, y1, 0), 
      new PVector(x2, y2, 0)
    };  
    tube = new Bezier3D(p, p.length);
    BezTube btube = new  BezTube(pa, tube, 1.0f, 2, 3);
    btube.fill(color(32, 32, 200));
    btube.stroke(color(64, 200, 200));
    btube.strokeWeight(2.0f);
    btube.drawMode(Shape3D.SOLID | Shape3D.WIRE);
    btube.draw();
    stroke(107, 145, 224);
    pushMatrix();
    fill(107, 145, 224);
    translate(x2, y2, 0);
    if (level > 2) {
      a=2;
    }
    box(a, a, a);
    fill(255);
    translate(0, 0, a);
    textangle= atan2(y2-y0, x2-x0);
    if (textangle > PI) {
      textangle = -(TWO_PI-textangle);
      textAlign(RIGHT);
    }
    rotate(textangle);
    text("   "+ osn[branchEnd], 0, 0);

    popMatrix();
  }
} 
void mouseClicked() {
  Shape3D picked = Shape3D.pickShapeB(this, mouseX, mouseY);
  if (picked != null)
    picked.fill(0);
}



boolean isAttached( Branch b1, Branch b2) {
  // check if b1 and b2 are connected
  if ( (b1.branchEnd == b2.branchStart) || (b1.branchStart == b2.branchEnd)) {
    return true;
  }
  else {
    return false;
  }
}

boolean branchesAreDifferent( Branch b1, Branch b2) {
  // check if b1 & b2 are different branches
  if (  (b1.branchEnd != b2.branchEnd) && (b1.branchStart != b2.branchStart )) {
    return true;
  }
  else {
    return false;
  }
}


float xAveragePlacing(float x1, float y1, float x2, float y2) {
  return (x1 + x2) / 2.0;
}

float yAveragePlacing(float x1, float y1, float x2, float y2) {
  return (y1 + y2) / 2.0;
}

float xKickBack(float x, float y, float x0, float y0, float r) {
  float h = pow(((x-x0)*(x-x0) + (y-y0)*(y-y0)), 0.5);
  return x0 + (x - x0)*r/h;
}

float yKickBack(float x, float y, float x0, float y0, float r) {
  float h = pow(((x-x0)*(x-x0) + (y-y0)*(y-y0)), 0.5);
  return y0 + (y - y0)*r/h;
}