#include <iostream.h>
#include <string>
float numEdges=0;
#include "Point.h"
// #include "AvlTree.h"
#include "SplayTree.h"


// required for the constructor of AvlTree
Point NOT_FOUND(-9999,-9999);

class Mesh
{
   private:
      // AvlTree<Point> tree(NOT_FOUND);
      SplayTree<Point> tree;
//      AvlTree<Point> tree;

   public:
      Mesh() : tree(NOT_FOUND), numNodes(0), avgNbrs(0.0), maxDist(0)
      {
      }
      void addnode(Point &pt);
      void deletenode(Point &pt);
      Point & find(Point pt);
      void calcVitalStats();
      void getVitalStats();
      void print();
      // this routine recursively traverses the tree
      // and gets each Point to calculate its farthest/closest edge
      void calcEdgeDistances(BinaryNode<Point> *rt);
      // this method gets the information created by
      // calcEdgeDistances()
      void getEdgeDistances(BinaryNode<Point> *rt);

      float numNodes; //, numEdges;
      float avgNbrs;
      // farthest/closest distance between edges amongst all the Points
      float maxDist, minDist, minAngle; 
      // the Points that correspond to maxDist and minDst
      Point *srcMaxDist, *dstMaxDist;
      Point *srcMinDist, *dstMinDist;
};

void
Mesh::addnode(Point &pt)
{
   numNodes++;
   tree.insert(pt);
}

void
Mesh::deletenode(Point &pt)
{
   numNodes--;
   tree.remove(pt);
}

Point &
Mesh::find(Point pt)
{
   return tree.find(pt);
}

void
Mesh::calcVitalStats()
{
   BinaryNode<Point> *rt;
   rt = tree.getRoot();

   calcEdgeDistances(rt);
}

void
Mesh::getVitalStats()
{
   // reset the maximum and minimum distances
   maxDist = 0;
   minDist = MAX_DISTANCE;
   minAngle = 360;
   BinaryNode<Point> *rt;
   rt = tree.getRoot();

   getEdgeDistances(rt);
}

// SplayTree's don't use NULL to show the end of a
// tree branch: they use the same ptr as the leaf!
void
Mesh::calcEdgeDistances(BinaryNode<Point> *rt)
{
   // for each Point, find its closest/farthest nbr
   rt->element.findMinMaxDist();
   rt->element.findMinAngle();
   if (rt->left!=rt)
   {
      calcEdgeDistances(rt->left);
   }
   if (rt->right!=rt)
   {
      calcEdgeDistances(rt->right);
   }
}

void
Mesh::getEdgeDistances(BinaryNode<Point> *rt)
{
   float curMax, curMin, curAngle;
   
   curMax=rt->element.maxDistToEdge;
   if(curMax>0)
   {
      if(curMax>maxDist)
      {
	 // this is the newest point with the farthest edge
	 maxDist = curMax;
	 srcMaxDist = &rt->element;
	 dstMaxDist = rt->element.farthestEdge;
      }
   }
   curMin=rt->element.minDistToEdge;
   if(curMin<MAX_DISTANCE)
   {
      if(curMin<minDist)
      {
	 // this is the newest point with the farthest edge
	 minDist = curMin;
	 srcMinDist = &rt->element;
	 dstMinDist = rt->element.closestEdge;
      }
   }
   curAngle=rt->element.minAngle;
   if(curAngle<360)
   {
      if(curAngle<minAngle)
      {
	 // this is the newest point with the farthest edge
	 minAngle = curAngle;
      }
   }
// SplayTree's don't use NULL to show the end of a
// tree branch: they use the same ptr as the leaf!
   if (rt->left!=rt)
   {
      getEdgeDistances(rt->left);
   }
   if (rt->right!=rt)
   {
      getEdgeDistances(rt->right);
   }
}

void
Mesh::print()
{
   tree.printTree();
}

void main()
{
   string input; // stores the whole line input by the user
   // the following variables are used to "parse" input
   string command; // gets the first word typed in
   // get the arguments typed in
   string arg1, arg2, arg3, arg4;
   // used for parsing: find where the ' ' (spaces) are
   int pos, end_arg1, end_arg2, end_arg3, end_arg4;
   // temporarily stores a string (arg1, arg2, etc...) 
   // as a char array until we can convert it into a float
   char* temp;
   // for commands that only have one x and y coordinate
   double xcoord, ycoord;
   // for commands that have two x and y coordinates
   double xcoord1, ycoord1, xcoord2, ycoord2;

   Mesh mesh;

   // get the input from the user.  Parse the line looking for
   // the correct commands (ie, addnode, deletenode, etc...)
   while(getline(cin,input))
   {
      pos = input.find(" ",0);
      command = input.substr(0,pos);
#ifdef DEBUG
      cout << "command: " << command << "END" << endl;
#endif
//////////////////////////////////////////////////////////////
#ifdef SHORTCOMMANDS
      if(command=="add")
#else
      if(command=="addnode")
#endif
      {
	 end_arg1 = input.find(" ",pos+1);
	 arg1 = input.substr(pos+1, end_arg1 - pos - 1);
	 xcoord = atof(arg1.c_str());

	 end_arg2 = input.find(" ",end_arg1+1);
	 arg2 = input.substr(end_arg1+1, end_arg2 - end_arg1 - 1);
	 ycoord = atof(arg2.c_str());
#ifdef DEBUG
	 cout << "----match addnode----\n";
	 cout << "arg1: " << arg1 << "END" << endl;
	 cout << "xcoord: " << xcoord << endl;
	 cout << "arg2: " << arg2 << "END" << endl;
	 cout << "ycoord: " << ycoord << endl;
	 cout << "----end match----\n";
#endif
	 // add the new point into our data structure
	 Point pt(xcoord,ycoord);
	 // make sure the point is not already in the mesh
	 // if((mesh.find(pt)!=NULL)) 
	 if((mesh.find(pt))!=NOT_FOUND) 
	 {// WSM: TODO use addnode()'s result instead
	  // that will require modifying AvlTree.cpp :(
	    cout << "\nOUTPUT: node " << pt << " already exists, addnode ignored\n\n";
	 }
	 else mesh.addnode(pt);
      }
//////////////////////////////////////////////////////////////
#ifdef SHORTCOMMANDS
      else if(command=="adde")
#else
      else if(command=="addedge")
#endif
      {
	 end_arg1 = input.find(" ",pos+1);
	 arg1 = input.substr(pos+1, end_arg1 - pos - 1);
	 xcoord1 = atof(arg1.c_str());

	 end_arg2 = input.find(" ",end_arg1+1);
	 arg2 = input.substr(end_arg1+1, end_arg2 - end_arg1 - 1);
	 ycoord1 = atof(arg2.c_str());

	 end_arg3 = input.find(" ",end_arg2+1);
	 arg3 = input.substr(end_arg2+1, end_arg3 - end_arg2 - 1);
	 xcoord2 = atof(arg3.c_str());

	 end_arg4 = input.find(" ",end_arg3+1);
	 arg4 = input.substr(end_arg3+1, end_arg4 - end_arg3 - 1);
	 ycoord2 = atof(arg4.c_str());
#ifdef DEBUG
	 cout << "----match addedge----\n";
	 cout << "arg1: " << arg1 << "END" << endl;
	 cout << "xcoord1: " << xcoord << endl;
	 cout << "arg2: " << arg2 << "END" << endl;
	 cout << "ycoord1: " << ycoord << endl;
	 cout << "arg3: " << arg3 << "END" << endl;
	 cout << "xcoord2: " << xcoord2 << endl;
	 cout << "arg4: " << arg4 << "END" << endl;
	 cout << "ycoord2: " << ycoord2 << endl;
	 cout << "----end match----\n";
#endif
         // NOTE: the edges are UNdirected (which makes it easier)
         // the source and destination points
         Point *src;
         Point *dst;
         Point lookupSrc(xcoord1,ycoord1);
         Point lookupDst(xcoord2,ycoord2);
         // First, find if the points exist
         src=&mesh.find(lookupSrc);
         dst=&mesh.find(lookupDst);
         if(*src!=NOT_FOUND && *dst!=NOT_FOUND)
         {
	    // only insert this edge if it doesn't already exist
	    if(!src->findEdge(dst))
	    {
               src->addEdge(dst);
	    }
	    else
	    {
	       cout << "\nOUTPUT: edge from " << *src << " to " << *dst << " already exists, addedge ignored\n\n";
	       // since the edge already exists, don't bother checking
	       // the other point
	       continue;
	    }
#ifdef DEBUG
            cout << "point " << *src << " has the following edges:\n";
            src->printEdges();
#endif
            dst->addEdge(src);
#ifdef DEBUG
            cout << "point " << *dst << " has the following edges:\n";
            dst->printEdges();
#endif
         }
         // else cout << "one or both points do not exist\n";
	 else
	 {
	    if(*src==NOT_FOUND)
	    {
	       cout << "\nOUTPUT: node " << lookupSrc << " does not exist, addedge ignored\n\n";
	    }
	    if(*dst==NOT_FOUND)
	    {
	       cout << "\nOUTPUT: node " << lookupDst << " does not exist, addedge ignored\n\n";
	    }
	 }

      }
//////////////////////////////////////////////////////////////
#ifdef SHORTCOMMANDS
      else if(command=="del")
#else
      else if(command=="deletenode")
#endif
      {
	 end_arg1 = input.find(" ",pos+1);
	 arg1 = input.substr(pos+1, end_arg1 - pos - 1);
	 xcoord = atof(arg1.c_str());

	 end_arg2 = input.find(" ",end_arg1+1);
	 arg2 = input.substr(end_arg1+1, end_arg2 - end_arg1 - 1);
	 ycoord = atof(arg2.c_str());
#ifdef DEBUG
	 cout << "----match deletenode----\n";
	 cout << "arg1: " << arg1 << "END" << endl;
	 cout << "xcoord: " << xcoord << endl;
	 cout << "arg2: " << arg2 << "END" << endl;
	 cout << "ycoord: " << ycoord << endl;
	 cout << "----end match----\n";
#endif
	 // WSM: continue from here
	 Point pt(xcoord,ycoord);
	 Point *delPt;
//	 BinaryNode<Edge>* edgesRoot;
//	 Edge currentEdge; // for each of this points edges
	 
	 // find the point to delete
	 delPt = &mesh.find(pt);
	 // make sure the point exists...
	 if(*delPt!=NOT_FOUND)
	 {
	    // now, go through its "neighbours"
	    delPt->deleteSelfFromNbrs();
	    mesh.deletenode(pt);

	 }
	 else cout << pt << " node not found\n";
      }
//////////////////////////////////////////////////////////////
#ifdef SHORTCOMMANDS
      else if(command=="dele")
#else
      else if(command=="deleteedge")
#endif
      {
	 end_arg1 = input.find(" ",pos+1);
	 arg1 = input.substr(pos+1, end_arg1 - pos - 1);
	 xcoord1 = atof(arg1.c_str());

	 end_arg2 = input.find(" ",end_arg1+1);
	 arg2 = input.substr(end_arg1+1, end_arg2 - end_arg1 - 1);
	 ycoord1 = atof(arg2.c_str());

	 end_arg3 = input.find(" ",end_arg2+1);
	 arg3 = input.substr(end_arg2+1, end_arg3 - end_arg2 - 1);
	 xcoord2 = atof(arg3.c_str());

	 end_arg4 = input.find(" ",end_arg3+1);
	 arg4 = input.substr(end_arg3+1, end_arg4 - end_arg3 - 1);
	 ycoord2 = atof(arg4.c_str());
#ifdef DEBUG
	 cout << "----match deleteedge----\n";
	 cout << "arg1: " << arg1 << "END" << endl;
	 cout << "xcoord1: " << xcoord << endl;
	 cout << "arg2: " << arg2 << "END" << endl;
	 cout << "ycoord1: " << ycoord << endl;
	 cout << "arg3: " << arg3 << "END" << endl;
	 cout << "xcoord2: " << xcoord2 << endl;
	 cout << "arg4: " << arg4 << "END" << endl;
	 cout << "ycoord2: " << ycoord2 << endl;
	 cout << "----end match----\n";
#endif
         // NOTE: the edges are UNdirected (which makes it easier)
         // the source and destination points
         Point *src;
         Point *dst;
         Point lookupSrc(xcoord1,ycoord1);
         Point lookupDst(xcoord2,ycoord2);
         // First, find if the points exist
         src=&mesh.find(lookupSrc);
         dst=&mesh.find(lookupDst);
         if(*src!=NOT_FOUND && *dst!=NOT_FOUND)
         {
	    // only delete this edge if it doesn't already exist
	    if(src->findEdge(dst))
	    {
               src->delEdge(dst);
	    }
	    else
	    {
	       cout << "edge does not exist\n";
	       // since the edge already exists, don't bother checking
	       // the other point
	       continue;
	    }
#ifdef DEBUG
            cout << "point " << *src << " has the following edges:\n";
            src->printEdges();
#endif
            dst->delEdge(src);
#ifdef DEBUG
            cout << "point " << *dst << " has the following edges:\n";
            dst->printEdges();
#endif
         }
         // else cout << "one or both points do not exist\n";
	 else
	 {
	    if(*src==NOT_FOUND)
	    {
	       cout << "\nOUTPUT: node " << lookupSrc << " does not exist, deleteedge ignored\n\n";
	    }
	    if(*dst==NOT_FOUND)
	    {
	       cout << "\nOUTPUT: node " << lookupDst << " does not exist, deleteedge ignored\n\n";
	    }
	 }
      }
//////////////////////////////////////////////////////////////
#ifdef SHORTCOMMANDS
      else if(command=="mv")
#else
      else if(command=="movenode")
#endif
      {
	 end_arg1 = input.find(" ",pos+1);
	 arg1 = input.substr(pos+1, end_arg1 - pos - 1);
	 xcoord1 = atof(arg1.c_str());

	 end_arg2 = input.find(" ",end_arg1+1);
	 arg2 = input.substr(end_arg1+1, end_arg2 - end_arg1 - 1);
	 ycoord1 = atof(arg2.c_str());

	 end_arg3 = input.find(" ",end_arg2+1);
	 arg3 = input.substr(end_arg2+1, end_arg3 - end_arg2 - 1);
	 xcoord2 = atof(arg3.c_str());

	 end_arg4 = input.find(" ",end_arg3+1);
	 arg4 = input.substr(end_arg3+1, end_arg4 - end_arg3 - 1);
	 ycoord2 = atof(arg4.c_str());
#ifdef DEBUG
	 cout << "----match movenode----\n";
	 cout << "arg1: " << arg1 << "END" << endl;
	 cout << "xcoord1: " << xcoord << endl;
	 cout << "arg2: " << arg2 << "END" << endl;
	 cout << "ycoord1: " << ycoord << endl;
	 cout << "arg3: " << arg3 << "END" << endl;
	 cout << "xcoord2: " << xcoord2 << endl;
	 cout << "arg4: " << arg4 << "END" << endl;
	 cout << "ycoord2: " << ycoord2 << endl;
	 cout << "----end match----\n";
#endif

         // NOTE: the edges are UNdirected (which makes it easier)
         // the source and destination points
         Point *src;
         Point *dst;
         Point *newdst;
         Point lookupSrc(xcoord1,ycoord1);
         Point lookupDst(xcoord2,ycoord2);
         // First, find if the points exist
         src=&mesh.find(lookupSrc);
         dst=&mesh.find(lookupDst);
         if(*src!=NOT_FOUND && *dst==NOT_FOUND)
         {
            mesh.addnode(lookupDst);
	    newdst=&mesh.find(lookupDst);
	    newdst->copyEdges(src);
            src->deleteSelfFromNbrs();
// WSM: TODO
//          src->deleteNbrsFromSelf();
	    mesh.deletenode(lookupSrc);
            newdst->addSelfToNbrs();
         }
         else cout << "source doesn't exist or destination already exists\n";
      }
//////////////////////////////////////////////////////////////
#ifdef SHORTCOMMANDS
      else if(command=="nbrs")
#else
      else if(command=="printneighbors")
#endif
      {
	 end_arg1 = input.find(" ",pos+1);
	 arg1 = input.substr(pos+1, end_arg1 - pos - 1);
	 xcoord = atof(arg1.c_str());

	 end_arg2 = input.find(" ",end_arg1+1);
	 arg2 = input.substr(end_arg1+1, end_arg2 - end_arg1 - 1);
	 ycoord = atof(arg2.c_str());
#ifdef DEBUG
	 cout << "----match printneighbors----\n";
	 cout << "arg1: " << arg1 << "END" << endl;
	 cout << "xcoord: " << xcoord << endl;
	 cout << "arg2: " << arg2 << "END" << endl;
	 cout << "ycoord: " << ycoord << endl;
	 cout << "----end match----\n";
#endif
	 Point *pt;
	 Point findPt(xcoord,ycoord);

	 pt = &mesh.find(findPt);
	 // make sure the point exists before trying to print
	 // its nbrs!
	 if (*pt!=NOT_FOUND)
	 {
	    cout << "\nOUTPUT: neighbors of node " << *pt << ":\n";
	    pt->printEdges();
//	    pt->findMaxDist();
            // calculate ALL the max distances for each point
/*
	    mesh.calcVitalStats();
            if(pt->hasEdges())
	    {
	       cout << "max distance: " << pt->maxDistToEdge << " to edge: " << *pt->farthestEdge << endl;
	    }
*/
	 }
	 else cout << findPt << " does not exist\n";
      }
      // else if(command=="printstatistics") // WSM: TODO
//////////////////////////////////////////////////////////////
#ifdef SHORTCOMMANDS
      else if(command=="stats")
#else
      else if(command=="printstatistics")
#endif
      {
#ifdef DEBUG
	 cout << "----match printstatistics----\n";
	 mesh.print();
#endif
	 cout << "\nOUTPUT: The mesh has " << mesh.numNodes << " nodes and " << numEdges/2 << " edges\n";
	 mesh.avgNbrs = (numEdges/mesh.numNodes);
	 cout << "OUTPUT: The avg number of nbrs/node is " << mesh.avgNbrs << endl;
// WSM: TODO: put these two methods together
         // calculate ALL the max distances for each point
         mesh.calcVitalStats();
	 mesh.getVitalStats();
// WSM: TODO: only print this if there are edges!
         cout << "OUTPUT: The shortest edge joins node " << *mesh.srcMinDist;
	 cout << " and " << *mesh.dstMinDist << " with length ";
	 cout << mesh.minDist << endl;
         cout << "OUTPUT: The longest edge joins node " << *mesh.srcMaxDist;
	 cout << " and " << *mesh.dstMaxDist << " with length ";
	 cout << mesh.maxDist << endl;
	 cout << "OUTPUT: The smallest angle is " << mesh.minAngle << " degrees\n\n";
//	 mesh.printVitalStats();
      }
      else if(command=="q") exit(0);
//////////////////////////////////////////////////////////////
      else
      {
	 cout << "----no match----\n";
      }
   } // while
}