//*****************************************************************************
// VST: Graph editor and vertex spanning tree, Jarek Rossignac, March 2006
//*****************************************************************************
int vn =5;                   // initial number of vertices
int en =5;                   // initial number of edges
int cap=128;                 // max nuber of edges and vertices 
pt[] P = new pt [cap];       // points (also called vertices or graph nodes)
edge[] E = new edge[cap];    // edges
int [] colEdge = new int[cap]; // colors of edges
int [] colVert = new int[cap]; // colors of points
pt Mouse = new pt(0,0);         // current mouse position
int bs=-1, be=-1;               // index of mouse-selected vertex on click and on release (-1 if new)
int mj=10;                    // user-controlled limit on the depth of vertex spanning tree
boolean numbers = true;         // toggles display of vertex numbers                                 
color soft = color(200, 200, 210); color red = color(200, 10, 10); // COLORS
color blue = color(10, 10, 200); color green = color(0, 150, 0); 
color black = color(10, 10, 10); color magenta = color(250, 150, 200); 
color brown = color(100, 50, 20); 

void setup() {   size(600, 600);          // window size
  PFont font = loadFont("Courier-14.vlw"); textFont(font, 12);  // font Courier-14.vlw must be created (see Tools>Creat Font)
  for (int i=0; i<cap; i++) {P[i]=new pt(0,0); E[i]=new edge(0,0); colEdge[i]=0; colVert[i]=0;}; // clear vertices, edges, colors
  // set initial edges and vertices on a circular pattern
  for (int i=0; i<vn; i++) {P[i].setFromValues(-sin((i+0.5)*TWO_PI/vn)*(width*0.45)+width/2.0,cos((i+0.5)*TWO_PI/vn)*(height*0.45)+height/2.0);};
  for (int i=0; i<vn; i++) {E[i].setFromValues(i,in(i)); };
  VST();                              // call the computation of the vertex-spanning-tree which resets the vertex and edge colors
} 
 
//**************************************
// **** DISPLAYING THE GRAPH
//**************************************

void draw() { background(255);       // clear screen, white background
  if (mousePressed) {                // if mouse is pressed, we are dragging something 
      if (keyPressed) {P[bs].setFromMouse(); } // if a key is pressed, we are editing the position of a vertex (new or old)
      else {line(mouseX,mouseY,P[bs].x,P[bs].y);};}; // otherwise, we are editing the endvertex of a new edge
  strokeWeight(2); drawEdges();     // draw all edges in their color (blue if in VST)
  drawPoints();                      // draw points in their color (red if visited by VST)
  };
  
void drawEdges()  {for (int i=0; i<en; i++) {if (colEdge[i]==0) {stroke(green);} else {stroke(blue);};  E[i].show(); };  };    

void drawPoints() {       // draw and label all points
  vec V = new vec(5,10);   // displacement for the label (point ID) next to the point  
  for (int i=0; i<vn; i++) {if (colVert[i]==0) {stroke(magenta);} else {stroke(red);}; P[i].show(5);}; // draw points as fat dots   
  if (numbers) {fill(10,10,100); for (int i=0; i<vn; i++) {P[i].label(str(i),V );}; noFill();}; // print all labels
  };     

//**************************************
// **** GUI FOR EDITING THE GRAPH
//**************************************
void mousePressed() {                                                   // to do when mouse is pressed  
  bs=pick();  // sets bs to the ID of closest point is close enough, otherwise to -1
  if (bs==-1) {P[vn].setFromMouse(); bs=vn; println("inserted vertex "+bs); vn++;};
   }
  
int pick() {  // finds closest point
  float bd=20;              // init smallest distance to selected point
  Mouse.setFromMouse();     // save current mouse location
  int pp=-1;                // init id of closest point to none
  for (int i=0; i<vn; i++) { if (d2(i)<bd) {bd=d2(i); pp=i;  };};       // select closeest point
  if (bd>10) {pp=-1;};                                                   // if closest point is too far, pp=-1
  return(pp);
  }

float d2(int j) {return (Mouse.disTo(P[j]));};                      // distance from mouse to vertex P[j]

void mouseReleased() {                                      // do this when mouse released
  if (keyPressed) {P[bs].setFromMouse(); }      // if a key is pressed, leave the dragged point here
  else {                                        // otherwise, make a new edge ending at a close-by point or create a new end-point
    be=pick();  if (be==-1) {P[vn].setFromMouse(); be=vn; println("inserted vertex "+be); vn++;};
    E[en].setFromValues(bs,be); println("inserted edge "+en+" = ("+bs+","+be+")"); en++;
    VST();
    };
  };
 
//*************************************************************
// **** COMPUTE THE VERTEX SPANNING TREE WITH ROOT AT VERTEX 0
//*************************************************************
void VST() {                                    // computes the vertex spanning tree (sets colors of edges and points in the tree)
  //**********************************************
  // insert your code here
  // it should change the color of all vertices and edges in the TST
  //**********************************************

  
  
  
  //***********************************************************
  // my placeholder code just to have something (please delete)
  //************************************************************
  for (int i=0; i<vn; i++) {colVert[i]=0;};     // resets vertex colors to 0 (not visited)
  for (int i=0; i<en; i++) {colEdge[i]=0;};     // resets edge colors to 0 (not in the VST)
  colVert[0]=1;                                 // seeds the VST root at vertex 0 (color = 1)
  for (int i=0; i<en; i++) {if(i%2==1) {colEdge[i]=1; colVert[E[i].s]=1; colVert[E[i].e]=1;};}; // changes colors of odd edges and their vertices
 }

//**********************************
//***      CONTROL WITH KEYS
//**********************************
void keyPressed() {  
  if (key=='n') {numbers=!numbers;};                                    // n toggles the display of vertex numbers
  if (key=='w') {writePts(); writeEdges();};                            // prints points and edges on the bottom window of the editor
  if (key=='s') {savePts(); saveEdges();};                             // saves points and edges to file
  if (key=='l') {loadPts(); loadEdges(); VST();};                      // loads points and edges from file and performs VST
  if (key=='i') { saveFrame("pix-####.tif");};                         // saves a picture of the screen
  if (key=='f') { float sx=width; float sy=height; float bx=0.0; float by=0.0; // recenters the graph
     for (int i=0; i<vn; i++) {if (P[i].x>bx) {bx=P[i].x;}; if (P[i].x<sx) {sx=P[i].x;}; if (P[i].y>by) {by=P[i].y;}; if (P[i].y<sy) {sy=P[i].y;}; };
     float m=max(bx-sx,by-sy);  float dx=(m-(bx-sx))/2; float dy=(m-(by-sy))/2;
     for (int i=0; i<vn; i++) {P[i].x=(P[i].x-sx+dx)*4*width/5/m+width/10;  P[i].y=(P[i].y-sy+dy)*4*height/5/m+height/10;};
     };
  };                                                                 

//**************************************
//**** utilities for polyloops
//**************************************
int in(int j) {  if (j==vn-1) {return (0);}  else {return(j+1);}  };  // next vertex in cyclic order

void writePts() { println(vn+" vertices"); for (int i=0; i<vn; i++) {print(" col["+i+"]="+colVert[i]+" "); P[i].write(); }; println();};
void writeEdges() { println(en+" edges"); for (int i=0; i<en; i++) {print(" col["+i+"]="+colEdge[i]+" "); E[i].write();  }; println();};

void savePts() {                              // saves vertices onto a file called points.pts
  String [] inppts = new String [vn+1];
  int s=0;
  inppts[s++]=str(vn);
  for (int i=0; i<vn; i++) {inppts[s++]=str(P[i].x)+","+str(P[i].y);};
  saveStrings("points.pts",inppts);
  };
  
void saveEdges() {                          // saves edges onto a file called edges.egs
  String [] inppts = new String [en+1];
  int s=0;
  inppts[s++]=str(en);
  for (int i=0; i<en; i++) {inppts[s++]=str(E[i].s)+","+str(E[i].e);};
  saveStrings("edges.egs",inppts);
  };

void loadPts() {                          // loads saved points
  String [] ss = loadStrings("points.pts");
  String subpts;
  int s=0;
  int comma;
  vn = int(ss[s]);
  for(int i=0;i<vn; i++) {
      comma=ss[++s].indexOf(',');
      P[i]=new pt (float(ss[s].substring(0, comma)), float(ss[s].substring(comma+1, ss[s].length())));
    };
  };

void loadEdges() {                      // loads saved edges
  String [] ss = loadStrings("edges.egs");
  String subpts;
  int s=0;
  int comma;
  en = int(ss[s]);
  for(int i=0;i<en; i++) {
      comma=ss[++s].indexOf(',');
      E[i]=new edge (int(ss[s].substring(0, comma)), int(ss[s].substring(comma+1, ss[s].length())));
    };
  };