#include <iostream.h>
#include <math.h>
#include "LinkedList.h"

#define TRUE  1
#define FALSE 0
#define MAX_DISTANCE 99999


/* This data struct is the element that will represent a point
 * in our "mesh".  It is needed because BOTH an x-coordinate and
 * y-coordinate will be used as the key for the binary search tree.
 * Thus, we need to define the greater-than and less-than operators
 * to be able to compare two points.  I also had to overload the 
 * << operator inorder to print a Point.  */
class Point
{
   public:
      float x;
      float y;
      // each Point may have edges to other points
      List<Point *> edges;
      ListItr<Point *> theItr;
      float maxDistToEdge;
      float minDistToEdge;
      float minAngle;
      Point* farthestEdge;
      Point* closestEdge;

      // constructors below
      Point()
      {
      }
      Point(float xpt, float ypt) : x(xpt), y(ypt), maxDistToEdge(0), minDistToEdge(MAX_DISTANCE), minAngle(360), farthestEdge(NULL), closestEdge(NULL)
      {
      }

      // methods dealing with edges
      void addEdge(Point *nbr);
      void delEdge(Point *nbr);
      void copyEdges(Point *prev);
      bool findEdge(Point *nbr);
      void deleteSelfFromNbrs();
//      void deleteNbrsFromSelf();
      void addSelfToNbrs();
      void findMinMaxDist();
      void findMinAngle();
      void printEdges();
      bool hasEdges()
      {
         if(edges.isEmpty()) return false;
	 else return true;
      }

      // WSM: the final const below fixed a bad compilation error
      bool operator <(const Point &pt) const;
      bool operator >(const Point &pt) const;
      bool operator ==(const Point &pt) const;
      friend ostream & operator << (ostream &os, const Point &pt);
};

void
Point::addEdge(Point *nbr)
{
   numEdges++;
   theItr = edges.zeroth();
   edges.insert(nbr,theItr);
}

void
Point::delEdge(Point *nbr)
{
   numEdges--;
   edges.remove(nbr);
}

void
Point::copyEdges(Point *prev)
{
   // code from the book below:
   if(prev->edges.isEmpty())
      cout << "This point has no nbrs!\n";
   else
   {
      ListItr<Point *> itr = prev->edges.first();
      for( ; !itr.isPastEnd(); itr.advance() )
      {
         theItr = edges.zeroth();
         edges.insert(itr.retrieve(),theItr);
      }
   }
}

bool
Point::findEdge(Point *nbr)
{
   // if this point has no edges, return false
   if(edges.isEmpty())
      return false;
   // otherwise, try to find the edge
   else
   {
      ListItr<Point *> itr = edges.first();
      for( ; !itr.isPastEnd(); itr.advance())
      {
	 if(itr.retrieve() == nbr)
	    return true;
      }
      return false;
   }
}

void
Point::deleteSelfFromNbrs()
{
   Point* nbr;
   // code from the book below:
   if(edges.isEmpty())
      cout << "This point has no nbrs!\n";
   else
   {
      ListItr<Point *> itr = edges.first();
      for( ; !itr.isPastEnd(); itr.advance() )
      {
	 nbr = itr.retrieve();
	 numEdges--;
	 nbr->delEdge(this);
      }
   }
}

void
Point::addSelfToNbrs()
{
   Point* nbr;
   // code from the book below:
   if(edges.isEmpty())
      cout << "This point has no nbrs!\n";
   else
   {
      ListItr<Point *> itr = edges.first();
      for( ; !itr.isPastEnd(); itr.advance() )
      {
	 nbr = itr.retrieve();
	 numEdges++;
	 nbr->addEdge(this);
      }
   }
}

void
Point::findMinMaxDist()
{
   Point *nbr;
   float dist=0;
   maxDistToEdge=0;
   minDistToEdge=MAX_DISTANCE;
   farthestEdge=NULL;
   closestEdge=NULL;
   // code from the book below:
   if(edges.isEmpty())
      ; // do nothing
      // cout << "This point has no nbrs!\n";
      // cout << "The point " << *this << " has no nbrs!\n";
   else
   {
      ListItr<Point *> itr = edges.first();
      for( ; !itr.isPastEnd(); itr.advance() )
      {
	 nbr=itr.retrieve();
	 dist = sqrt(pow((nbr->x - x),2) + pow((nbr->y - y),2));
	 if (dist > maxDistToEdge)
	 {
	    maxDistToEdge = dist;
	    farthestEdge = nbr;
	 }
	 if (dist < minDistToEdge)
	 {
	    minDistToEdge = dist;
	    closestEdge = nbr;
	 }
      }
   }
}

void
Point::findMinAngle()
{
   // we need to calculate the angle using this point and two
   // of its neighbors
   Point *nbr1, *nbr2;
   // temporarily hold the current angle in this variable
   float curAngle;
   float a=0;
   float b=0;
   float c=0;
   minAngle=360; // Wsm: member variable

   if(!edges.isEmpty())
   {
      ListItr<Point *> itr1 = edges.first();
      for( ; !itr1.isPastEnd(); itr1.advance() )
      {
         ListItr<Point *> itr2 = edges.first();
         nbr1=itr1.retrieve();

         for( ; !itr2.isPastEnd(); itr2.advance() )
         {
            nbr2=itr2.retrieve();
            if (nbr1!=nbr2)
            {
               b = sqrt(pow((nbr1->x - x),2) + pow((nbr1->y - y),2));
               c = sqrt(pow((nbr2->x - x),2) + pow((nbr2->y - y),2));
               a = sqrt(pow((nbr2->x - nbr1->x),2) + pow((nbr2->y - nbr1->y),2));
               curAngle = acos(((b*b)+(c*c)-(a*a))/(2*b*c));
               curAngle = (curAngle*180)/3.1415926535897932;

               if (curAngle < minAngle)
               {
                  minAngle = curAngle;
               }
            }
         } // for
      } // for
   } // if
}

void
Point::printEdges()
{
   // code from the book below:
   if(edges.isEmpty())
      cout << "OUTPUT: This point has no nbrs!\n";
   else
   {
      ListItr<Point *> itr = edges.first();
      for( ; !itr.isPastEnd(); itr.advance() )
      {
	 cout << "OUTPUT: " << *itr.retrieve() << endl;
      }
      cout << endl;
   }
}
// returns TRUE if this point is less than the argument "pt"
bool
Point::operator <(const Point &pt) const
{
   if(x < pt.x) return TRUE;
   else if(x == pt.x)
   {
      if(y < pt.y) return TRUE;
      else return FALSE;
   }
   else return FALSE;
}

// returns TRUE if this point is greater than the argument "pt"
bool
Point::operator >(const Point &pt) const
{
   if(x > pt.x) return TRUE;
   else if(x == pt.x)
   {
      if(y > pt.y) return TRUE;
      else return FALSE;
   }
   else return FALSE;
}

bool
Point::operator ==(const Point &pt) const
{
   if((x == pt.x) && (y == pt.y)) return TRUE;
   else return FALSE;
}

ostream & operator << (ostream &os, const Point &pt)
{
   return os << "(" << pt.x << ", " << pt.y << ")";
}

#if 0
void main()
{
   float p1x, p1y;
   float p2x, p2y;

   
   cout << "p1 x: ";
   cin >> p1x;
   cout << "p1 y: ";
   cin >> p1y;
   cout << "p2 x: ";
   cin >> p2x;
   cout << "p2 y: ";
   cin >> p2y;


   Point p1(p1x,p1y);
   Point p2(p2x,p2y);
   Point p3(p2x-1,p2y-1);

   if (p1<p2) cout << "p1 < p2" << endl;
   else if (p1>p2) cout << "p1 > p2" << endl;
   else cout << "p1 = p2" << endl;

   p1.addEdge(&p2);
   p1.addEdge(&p3);
   p1.printNbrs();
   p1.delEdge(&p2);
   p1.printNbrs();

#if 0
   float e1x, e1y;

   cout << "edge x: ";
   cin >> e1x;
   cout << "edge y: ";
   cin >> e1y;

   p1.addEdge(e1);
   p1.addEdge(e2);
   p1.addEdge(e3);
   cout << "printing edges for the first point\n";
   p1.printEdges();
   cout << "done printing edges for the first point\n";
#endif

   cout << "pts: " << endl;
   cout << p1 << endl;
   cout << p2 << endl;
}
#endif