/*******************************************************************************
+
+  LEDA 3.5
+
+  _embed1.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.
+ 
*******************************************************************************/

//------------------------------------------------------------------------------
// 
// straight line embedding
//                                                                              
// K. Mehlhorn (1989)
//------------------------------------------------------------------------------


#include <LEDA/graph_alg.h>


const int A = -2; 
const int B = -1; 

static node_array<list_item>  Classloc;
static node_array<int>  ord, labelled, Class;
static node_array<node> first, second, last;

void label_node(graph& G, list<node>& L, int& count,
                list<node>& Al,list<node>& Bl,list<node>*& Il,
                node v, node c)

{ // labels the node v; c is the special node which is to be labelled
  // last; the details are described in lemma 10
  edge e;
  L.append(v);
  ord[v]=count++; 
  labelled[v]=1;

  forall_adj_edges(e,v)
  { edge e1 = G.reversal(e);
    node tt = target(e);
    int i;

    if (labelled[tt] && !labelled[target(G.cyclic_adj_succ(e))])
      { first[v]=tt; 
        second[v]=target(G.cyclic_adj_pred(e));
       }

    if (labelled[tt] && !labelled[target(G.cyclic_adj_pred(e))]) last[v]=tt;

    if (!labelled[tt] && (tt != c))
      { if (Class[tt] == A) 
          { Al.del(Classloc[tt]); 
            Classloc[tt] = Bl.push(tt);
            Class[tt]=B;
           }  
        else 
          { if (Class[tt] == B) 
               { Bl.del(Classloc[tt]);
                 i = 2-labelled[target(G.cyclic_adj_succ(e1))]
                      -labelled[target(G.cyclic_adj_pred(e1))];
                }
            else 
               { i=Class[tt];
                 Il[i].del(Classloc[tt]);
                 i = i+1-labelled[target(G.cyclic_adj_succ(e1))]
                        -labelled[target(G.cyclic_adj_pred(e1))];
                }

             Class[tt]=i;
             Classloc[tt]=Il[i].push(tt);

           }//end else case

      }//end if

  }//end 

}//end of label_node


void compute_labelling(graph& G,list<node>& L, list<node>& Pi)
{ /* computes the ordering of lemma 10 in List L ,the sequence pi
     in List Pi, the function L^-1(v) in Array ord, and the functions
     first,second,last of lemma 11 in the corresponding Arrays
   */
  node v,a,b,c;

  /* zuerst berechne ich die drei Knoten,die am Rand des aeusseren 
     Gebiets liegen sollen
   */

  a=G.first_node();
  list<edge> temp = G.adj_edges(a);
  b = target(temp.pop());
  c = target(temp.pop());


/*
  node_array<int> labelled(G,0);
*/

  labelled.init(G,0);

  int count = 0;
  
  list<node> Al ;

/*
  node_array<int> Class(G); 
  node_array<list_item> Classloc(G);
*/

  Class.init(G); 
  Classloc.init(G);

  forall_nodes(v,G) { Classloc[v] = Al.push(v);Class[v]=A;}

  list<node> Bl;
  list<node>* Il = new list<node>[G.number_of_nodes()];
  
  label_node(G,L,count,Al,Bl,Il,a,c);
  label_node(G,L,count,Al,Bl,Il,b,c);

  while ( !Il[1].empty() )
  { node v = Il[1].pop(); 
    label_node(G,L,count,Al,Bl,Il,v,c);
   }

  label_node(G,L,count,Al,Bl,Il,c,c);

   //nun berechne ich noch first second und last des Knoten c 
  first[c]=a;
  last[c]=b;

  edge e;
  forall_adj_edges(e,c) if (target(e)==a) second[c]=target(G.cyclic_adj_pred(e));
  
 //nun die Folge Pi
  node_array<list_item> Piloc(G);
  Piloc[a] = Pi.push(a);
  Piloc[b] = Pi.append(b);
  forall(v,L) if (v != a && v != b) Piloc[v] = Pi.insert(v,Piloc[second[v]],-1);

}//end of compute_labelling 

void move_to_the_right(list<node>& Pi, node v, node w, 
                       node_array<int>& ord, node_array<int>& x)

{ //increases the x-coordinate of all nodes which follow w in List Pi
  //and precede v in List L,i.e., have a smaller ord value than v
  int seen_w = 0;
  node z;
  forall(z,Pi)
  { if (z==w) seen_w=1;
    if (seen_w && (ord[z]<ord[v])) x[z]=x[z]+1;
  }
}


int STRAIGHT_LINE_EMBEDDING(graph& G,node_array<int>& x, node_array<int>& y)
{
 // computes a straight-line embedding of the planar map G into
 // the 2n by n grid. The coordinates of the nodes are returned
 // in the Arrays x and y. Returns the maximal coordinate.

if (G.empty()) return 0;

if (G.number_of_nodes() == 1)
{ node v = G.first_node();
  x[v] = y[v] = 1;
  return 1;
 }

list<node> L;
list<node> Pi;
list<edge> TL;

node v;
edge e;
int maxcoord = 1;

/*
node_array<int>  ord(G);
node_array<node> first(G), second(G), last(G);
*/

ord.init(G);
first.init(G);
second.init(G);
last.init(G);


TL = G.triangulate_map();

if (!G.make_map())
  error_handler(1,"STRAIGHT LINE EMBEDDING: graph must be a planar map");


compute_labelling(G,L,Pi);


//I now embed the first three nodes

v = L.pop();
x[v] = 0;
y[v] = 0;

if (!L.empty())
{ v = L.pop();
  x[v] = 2;
  y[v] = 0;
 }

if (!L.empty())
{ v = L.pop();
  x[v] = 1;
  y[v] = 1;
 }

//I now embed the remaining nodes

while ( !L.empty() )
 { 
   v = L.pop();

   // I first move the nodes depending on second[v] by one unit
   // and the the nodes depending on last[v] by another unit to the 
   // right


   move_to_the_right(Pi,v,second[v],ord,x);
   move_to_the_right(Pi,v,last[v],ord,x);

   // I now embed v at the intersection of the line with slope +1
   // through first[v] and the line with slope -1 through last[v]

   int x_first_v = x[first[v]];
   int x_last_v =  x[last[v]];
   int y_first_v = y[first[v]];
   int y_last_v =  y[last[v]];

   x[v]=(y_last_v - y_first_v + x_first_v + x_last_v)/2;
   y[v]=(x_last_v - x_first_v + y_first_v + y_last_v)/2;
 }

// delete triangulation edges

forall(e,TL) G.del_edge(e);

forall_nodes(v,G) maxcoord = Max(maxcoord,Max(x[v],y[v]));

return maxcoord;

}



void STRAIGHT_LINE_EMBEDDING(graph& G,node_array<double>& x, node_array<double>& y)
{ 
  node_array<int> x0(G);
  node_array<int> y0(G);

  int maxc = STRAIGHT_LINE_EMBEDDING(G,x0,y0);

  node v;
  forall_nodes(v,G) 
  { x[v] = double(x0[v])/maxc;
    y[v] = double(y0[v])/maxc; 
   }
}

