/*******************************************************************************
+
+  LEDA 3.5
+
+  embed.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#include <math.h>
#include <LEDA/graphwin.h>
#include <LEDA/array.h>
#include "../../src/graphwin/local.h"


point GraphWin::first_hit(node v, const line& l, 
                          bool from_left, bool from_above)
{
  point  p_v = get_position(v);

  double x0 = p_v.xcoord();
  double y0 = p_v.ycoord();
  double rx = get_radius1(v);
  double ry = get_radius2(v);

  switch(get_shape(v)) {

    case circle_node:
      ry=rx;
    case ellipse_node: {

      if (l.is_vertical()) 
      { double x  = l.x_proj(0);
        double dx = x-x0;
        double s  = ry/rx*sqrt(rx*rx-dx*dx);
        if (from_above) s = -s;
        return point(x,y0+s);
       }

      double m  = l.slope();
      double t0 = y0-l.y_proj(0);
      double t1 = m*rx*rx;
      double t2 = ry*ry;
      double t3 = x0*t2+t0*t1;
      t2 = t1*m+t2;
      t1 = x0*m-t0;
      t1 = rx*ry*sqrt(t2-t1*t1);

      double x = (from_left) ? (t3-t1)/t2 : (t3+t1)/t2;

      return point(x,l.y_proj(x));
    }


    case square_node:
      ry=rx;
    case rectangle_node: {

      if (l.is_vertical()) 
      { double x  = l.x_proj(0);
        if (from_above)
          return point(x,y0-ry);
        else
          return point(x,y0+ry);
       }

      if (l.is_horizontal()) 
      { double y  = l.y_proj(0);
        if (from_left)
          return point(x0-rx,y);
        else
          return point(x0+rx,y);
       }

      x0 += (from_left  ? -rx : +rx);
      y0 += (from_above ? -ry : +ry);

      double x = l.x_proj(y0);
      double y = l.y_proj(x0);
        
      if (from_above) 
         if (y < y0) 
            return point(x,y0);
         else
            return point(x0,y);
      else
         if (y > y0) 
            return point(x,y0);
         else
            return point(x0,y);
     }
  }

  return point(0,0); // never reached
}  


//----------------------------------------------------------------------------


point GraphWin::compute_leaving_point(node v, const point& p) 
{
  point  p_v  = get_position(v);
  double x_v  = p_v.xcoord();
  double y_v  = p_v.ycoord();
  double x    = p.xcoord();
  double y    = p.ycoord();

  if (ortho_mode)
  { double rx_v = get_radius1(v);
    double ry_v = get_radius2(v);
    if (x >= x_v-rx_v && x <= x_v+rx_v)
       return first_hit(v, line(p,vector(0,1)), false, y<y_v);
    if (y >= y_v*ry_v && y <= y_v+ry_v)
       return first_hit(v, line(p,vector(1,0)), x<x_v, false);
  }

  return first_hit(v, line(p,p_v), x<x_v, y<y_v);
}




//----------------------------------------------------------------------------


double GraphWin::compute_ortho_leaving_points(node v,node w,point& pv,point& pw)
{
  point p = get_position(v);
  point q = get_position(w);

  array<double> x(4);

  x[0] = p.xcoord() - get_radius1(v);
  x[1] = p.xcoord() + get_radius1(v);
  x[2] = q.xcoord() - get_radius1(w);
  x[3] = q.xcoord() + get_radius1(w);

  if (x[2] <= x[1] && x[3] >= x[0])
  { x.sort();
    point p1((x[1]+x[2])/2,p.ycoord());
    line l(p1,vector(0,1));
    pv = first_hit(v,l,false,q.ycoord() < p.ycoord());
    pw = first_hit(w,l,false,q.ycoord() > p.ycoord());
    return x[2]-x[1];
   }

  x[0] = p.ycoord() - get_radius2(v);
  x[1] = p.ycoord() + get_radius2(v);
  x[2] = q.ycoord() - get_radius2(w);
  x[3] = q.ycoord() + get_radius2(w);

  if (x[2] <= x[1] && x[3] >= x[0])
  { x.sort();
    point p1(p.xcoord(),(x[1]+x[2])/2);
    line l(p1,vector(1,0));
    pv = first_hit(v,l,q.xcoord() < p.xcoord(),false);
    pw = first_hit(w,l,q.xcoord() > p.xcoord(),false);
    return x[2]-x[1];
   }

  return -1;
}


//----------------------------------------------------------------------------

static void parallel_tangents_to_ellipse(double rx, double ry,
                                         const line& l, line& l1, line& l2) 
{ rx *= rx;
  ry *= ry;
  double m = l.slope();
  double n = m*rx;
  double s = sqrt(ry+m*n);
  rx = n/s;
  ry = -ry/s;

  l1 = l.translate(vector(rx,ry));
  l2 = l.translate(vector(-rx,-ry));
}


//----------------------------------------------------------------------------

static void parallel_tangents_to_rectangle(double rx, double ry,
                                           const line& l, line& l1, line& l2) 
{ if (l.slope() > 0) rx = -rx;
  l1 = l.translate(vector(rx,ry));
  l2 = l.translate(vector(-rx,-ry));
}

//----------------------------------------------------------------------------

double GraphWin::max_edge_distance(node v, node w) 
{
  point p_v=get_position(v);
  point p_w=get_position(w);

  if (p_v.xcoord() == p_w.xcoord())  // vertical
  { return  0.9*2*Min(get_radius1(v),get_radius1(w)); }

  if (p_v.ycoord() == p_w.ycoord())  // horizontal
  { return  0.9*2*Min(get_radius2(v),get_radius2(w)); }


  line l(p_v,p_w);

  line v_l1;
  line v_l2;
  line w_l1;
  line w_l2;
  
  double rx=get_radius1(v);
  double ry=get_radius2(v);

  switch (get_shape(v)) {
    case circle_node :
      ry=rx;
    case ellipse_node:
      parallel_tangents_to_ellipse(rx,ry,l,v_l1,v_l2);
      break;
    case square_node:
      ry=rx;
    case rectangle_node:
      parallel_tangents_to_rectangle(rx,ry,l,v_l1,v_l2);
      break;
  }

  rx=get_radius1(w);
  ry=get_radius2(w);

  switch (get_shape(w)) {
    case circle_node :
      ry=rx;
    case ellipse_node:
      parallel_tangents_to_ellipse(rx,ry,l,w_l1,w_l2);
      break;
    case square_node: 
      ry=rx;
    case rectangle_node:
      parallel_tangents_to_rectangle(rx,ry,l,w_l1,w_l2);
      break;
  }

 // compute distance of inner parallels

  double m = v_l1.slope();
  double a = v_l1.y_proj(0);
  double b = v_l2.y_proj(0);
  double c = w_l1.y_proj(0);
  double d = w_l2.y_proj(0);

  if (a > b) { double tmp=a; a=b; b=tmp; }
  if (c > d) { double tmp=c; c=d; d=tmp; }
  
  double f = fabs((b < d ? b : d) - (a < c ? c : a));

  return 0.9*f/sqrt(m*m+1);
}

//----------------------------------------------------------------------------

void GraphWin::embed_edges(node v, node w) 
{
  if (get_index(v) > get_index(w)) { node tmp=v; v=w; w=tmp; }

  edge e; 

  if (v == w) //loops
  { point src_p = get_position(v);
    forall_incident_edges(e,v,w)
    { list<point>& P = e_info[e].p;
      if (P.size() >= 4) continue;
      double d1 = 2.5 * get_radius1(v);
      double d2 = 2.5 * get_radius2(v);
      point p0 = P.pop();
      if (P.size() > 1) P.pop();
      P.push(src_p.translate(-d1, 0));
      P.push(src_p.translate(-d1,d2));
      P.push(src_p.translate( 0, d2));
      P.push(p0);
    }
  }
      


  list<list<point>*> auto_list_vw;
  list<list<point>*> auto_list_wv;
  
  forall_incident_edges(e,v,w)
  { list<point>& P=e_info[e].p;
    if (P.size() == 2) 
       auto_list_vw.append(&P);
    else 
     { list_item it1 = P.first();
       list_item it2 = P.last();
       P[it1] = compute_leaving_point(v,P[P.succ(it1)]);
       P[it2] = compute_leaving_point(w,P[P.pred(it2)]);
      }
   }

  if (v != w)
    forall_incident_edges(e,w,v) 
    { list<point>& P=e_info[e].p;
      if (P.size() == 2) 
         auto_list_wv.append(&P);
      else    
       { list_item it1 = P.first();
         list_item it2 = P.last();
         P[it1] = compute_leaving_point(w,P[P.succ(it1)]);
         P[it2] = compute_leaving_point(v,P[P.pred(it2)]);
        }
     }

  unsigned s_vw=auto_list_vw.size();
  unsigned s_wv=auto_list_wv.size();

  unsigned s = s_vw + s_wv;

  if (s == 0) return;

  if (s == 1) 
  { if (s_vw == 1) 
    { list<point>* P = auto_list_vw.pop();
      P->clear();
      point vp,wp;
      if (ortho_mode && compute_ortho_leaving_points(v,w,vp,wp) > 0)
      { P->push(wp);
        P->push(vp);
       }
      else
      { P->push(compute_leaving_point(w,get_position(v)));
        P->push(compute_leaving_point(v,get_position(w)));
       }
      return;
     }
    list<point>* P = auto_list_wv.pop();
    P->clear();
    point vp,wp;
    if (ortho_mode && compute_ortho_leaving_points(v,w,vp,wp) > 0)
    { P->push(vp);
      P->push(wp);
     }
    else
    { P->push(compute_leaving_point(v,get_position(w)));
      P->push(compute_leaving_point(w,get_position(v)));
     }
    return;
   }

  s--;

  point p_v=get_position(v);
  point p_w=get_position(w);

  double max_dist=max_edge_distance(v,w);

  if (ortho_mode)
  { double d = compute_ortho_leaving_points(v,w,p_v,p_w);
    if (d > 0) max_dist = d;
   }

  line l(p_v,p_w);	// embed all edges around l


  double h = (edge_distance * s > max_dist) ? max_dist/s : edge_distance;
  
  if (fabs(p_v.xcoord()-p_w.xcoord())*win_p->scale() < 0.5) 
    l = line(p_v,vector(0,1));

  bool from_left  = p_v.xcoord() > p_w.xcoord();
  bool from_above = p_v.ycoord() > p_w.ycoord(); 

  if ((l.is_vertical()&&from_above) || (!l.is_vertical()&&from_left)) h = -h; 

  vector vec(2);

  if (l.is_vertical()) 
     vec=vector(h,0);
  else 
   { double sl=l.slope(); 
     vec=vector(0,h*sqrt(sl*sl+1)); 
    }

  if (s%2) l=l.translate(vec*0.5);

  int t    = 0;
  int sign = 1;

  while( !auto_list_vw.empty() ) 
  { l = l.translate(vec*sign*t);
    list<point>* P = auto_list_vw.pop();
    P->clear();
    P->push(first_hit(v,l,from_left,from_above));
    P->append(first_hit(w,l,!from_left,!from_above));
    t++;
    sign = -sign;
  }

  while( !auto_list_wv.empty() ) 
  { l = l.translate(vec*sign*t);
    list<point>* P = auto_list_wv.pop();
    P->clear();
    P->push(first_hit(v,l,from_left,from_above));
    P->push(first_hit(w,l,!from_left,!from_above));
    t++;
    sign = -sign;
  }

}

//----------------------------------------------------------------------------

void GraphWin::embed_node_with_edges(node u) 
{ node_list adj_nodes;
  edge e;
  forall_inout_edges(e,u) 
  { node w=opposite(u,e);
    if (adj_nodes.member(w)) continue;
    adj_nodes.append(w);
    embed_edges(source(e),target(e));
  }
}

//----------------------------------------------------------------------------

void GraphWin::embed_edges() 
{ node_array<bool> considered(*gr_p,false);
  node u;
  forall_nodes(u,*gr_p) 
  { if (considered[u]) continue;
    considered[u]=true;
    embed_node_with_edges(u);
  }
  edges_embedded=true;
}

//----------------------------------------------------------------------------

void GraphWin::move_edge(edge e, const vector& trans) 
{ list<point>& P = e_info[e].p;
  list_item it;
  forall_items(it,P) P[it] = P[it].translate(trans);
}

//----------------------------------------------------------------------------

void GraphWin::move_node(node v, const vector& trans) {
  point& p = n_info[v].pos;
  p = p.translate(trans);
}

//----------------------------------------------------------------------------

void GraphWin::move_nodes_with_edges(const list<node>& L, const vector& trans) {
  node v;
  forall(v,L) 
  { move_node(v,trans);
    edge e;
    forall_adj_edges(e,v) move_edge(e,trans);
  }
}

//----------------------------------------------------------------------------


void GraphWin::move_nodes(const node_array<point>& dest, unsigned anim) 
{
  if (node_move == move_single_node)  
  { node v;
    forall_nodes(v,*gr_p) move_node_with_edges(v,dest[v],anim);
    edges_embedded=true;
    return;
   }    


  if (anim) 
  { node_array<vector> p_trans(*gr_p);
    node v;
    forall_nodes(v,*gr_p) 
         p_trans[v] = (dest[v]-get_position(v))*(1.0/(anim+1));

    unsigned i=0;

    do { forall_nodes(v,*gr_p)
	 { point& p=n_info[v].pos;
	   p = p.translate(p_trans[v]);
	  }
         embed_edges();
         win_p->start_buffering();
         win_p->clear();
         draw_graph();
         win_p->flush_buffer();
         win_p->stop_buffering();
     } while (++i < anim); 
   }

   node v;
   forall_nodes(v,*gr_p) n_info[v].pos=dest[v];

   embed_edges();
   win_p->start_buffering();
   win_p->clear();
   draw_graph();
   win_p->flush_buffer();
   win_p->stop_buffering();
   edges_embedded=true;
}

//----------------------------------------------------------------------------

void GraphWin::move_node_with_edges(node v, const point& new_p, unsigned anim) 
{
  point& p = n_info[v].pos;

  if (p == new_p) return;

  n_animation_start(v);

  if (anim) 
  { vector trans((new_p-p)*(1.0/(anim+1)));
    do { p = p + trans;
         n_animation_step();
       } while (--anim > 0); 
   }
  p = new_p;
  n_animation_end();
}

