//
// Elements of a graph (class GRAPH) are nodes (class NODE). Nodes might be connected by edges (class EDGE).
// Computing the layout of a graph means to compute positions of all nodes (NODE::center). 
// To describe a position (a point in a plane) we use objects of class VECTOR. 
// VECTOR implements operations of vector arithmetics as far as needed.
// A graph represented by an object of class GRAPH cannot draw itself - 
// this capability is delegated to class DRAWING (see SpingImpl.h).


  class VECTOR 
  { 
    friend VECTOR &operator *(double, const VECTOR &); 

    public:    
         VECTOR(void) : x(0.0), y(0.0)
         {
         }
         VECTOR(double _x, double _y) : x(_x), y(_y)
         {
         }

         VECTOR &operator +(const VECTOR &) const;
         VECTOR &operator -(const VECTOR &) const;
         VECTOR &operator *(const VECTOR &) const;
         VECTOR &operator /(const VECTOR &) const;
         VECTOR &operator +=(const VECTOR &);
         VECTOR &operator -=(const VECTOR &);
         VECTOR &operator *(double) const;
         VECTOR &operator /(double) const;
         VECTOR &operator /=(double);

         inline VECTOR &operator =(const VECTOR &vector)
         {
           x = vector.x;   y = vector.y;  
           return *this;
         }
         inline int operator ==(const VECTOR &vector) const
         {
            return x == vector.x  &&  y == vector.y;
         }

         double Angle(const VECTOR &); 

         double Distance(const VECTOR &) const;
         double Abs(void) const;
         VECTOR &Normalize(void) const;
         void *operator new(size_t);

         double x;  
         double y;
  };

  class NODE;

  class EDGE
  {
    public:
         EDGE(NODE *_source, NODE *_target) : source(_source), target(_target)
         {
           length = 0.0;
         }

         inline NODE *SourceNode(void)
         {
           return source;
         }
         inline NODE *TargetNode(void)
         {
           return target;
         }

    private:    
         NODE *source, *target;  // edge from node 'source' to node 'target' 
         double length;          // distance between 'source' and 'target'

  };

  class NODE 
  { 
    friend class GRAPH;
  
    public:
          NODE(void);
          NODE(char *_name, double x, double y);
           
          inline const VECTOR &Center(void) const
          {
            return center;
          }
          inline const VECTOR &LastImpulse(void) const
          {
            return lastImpulse;
          }
          inline double Temperature(void) const
          {
            return temperature;
          }
          inline double Distance(const NODE &node) const
          {
            return center.Distance(node.Center());
          }
          inline const char *Name(void) const
          {
            return name;
          }
          

          inline void MarkAsMoved(void)
          {
            flags |= 1;
          }
          inline int HasMoved(void)
          {
            return flags & 1;
          }
          inline void Shake(void)
          {
            flags &= ~ 1; 
          }
           
          inline NODE *Next(void)
          {
            return next;
          } 
          
          void Connect(NODE &);

          NODE *Voisin(int &);

          double Mass(void);

          NODE &operator +=(EDGE &); 
          
          void MoveBy(double dx, double dy);


  private:

          char *name;    // nodes are named
          
          int n;
          EDGE **edges;  // n edges starting from this node
          NODE *next;    // linked list for all edges of the graph

          VECTOR center;  // position of this node
          VECTOR lastImpulse;  // last impulse

          double temperature;
          double skew;
          double force;

          int flags;  // see MarkAsMoved() and HasMoved()
  };

  class GRAPH 
  {
  public:
          GRAPH(void);
   
          void MainIteration(void);
          VECTOR &AttractiveForce(NODE &node1, NODE &node2);
          VECTOR &RepulsiveForce(NODE &node1, NODE &node2);
          VECTOR &GravitationalForce(NODE &);
          VECTOR &RandomForce(NODE &);

          VECTOR &ComputeNodeImpulse(NODE &node);

          int *CreateRandomIndices(int n);

          void AdjustTemperatureAndSkew(NODE &node, double angle);
          double TemperatureSum(void);
          double ForceSum(void);

          void SetBaryCenter(void);

          inline NODE *First(void)
          {
            return first; 
          }
          NODE *Get(int k);  // get k-th node

          GRAPH &operator +=(NODE &); // add node to graph

          void Print(void);
 
          int Intersect(NODE &);  // compute number of intersections
          static int Intersect(const VECTOR &, const VECTOR &, const VECTOR &, const VECTOR &, double &, double &); 

  private:
          int n;
          NODE *first;

          VECTOR baryCenter;

          double maxRandom;
          double c1;
          double c2;
          double c3;

          double stepConstantC4;
          double osciConstantC5;
          double skewConstantC6;
          double rotaConstantC7;
          
          double c8;  

          int iteration;
};

#define MAXITERATION 1
#define MAX_TEMPERATURESUM 0.3

#define D_EPS 1.E-10