/*
    This software may only be used by you under license from AT&T Corp.
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
    AT&T's Internet website having the URL:
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
    If you received this software without first entering into a license
    with AT&T, you have an infringing copy of this software and cannot use
    it without violating AT&T's intellectual property rights.
*/
#pragma prototyped

#include    "circle.h"
#define DEF_RANKSEP 1.00


/* dfs to set distance from a particular leaf.
 * Note that termination is implicit in the test
 * for reduced number of steps. Proof?
 */
static void
setNStepsToLeaf(Agraph_t* g, Agnode_t* n, Agnode_t* prev)
{
  Agnode_t* next;
  Agedge_t* ep;
  int nsteps = SLEAF(n) + 1;

  for (ep = agfstedge(g,n); ep; ep = agnxtedge(g,ep,n)) {
    if ((next = ep->tail) == n) next = ep->head;

    if (prev == next) continue;

    if (nsteps < SLEAF(next)) {
      SLEAF(next) = nsteps;
      setNStepsToLeaf(g, next, n);
    }
  }
}

static int
isLeaf (Agraph_t* g, Agnode_t* n)
{
  Agedge_t* ep;
  int cnt = 0;

  for (ep = agfstedge(g,n); ep; ep = agnxtedge(g,ep,n)) {
    cnt++;
    if (cnt == 2) break;
  }
  return (cnt == 1);

}

static void
initLayout (Agraph_t* g) 
{
  Agnode_t* n;
  int nnodes = agnnodes (g);
  int INF = nnodes*nnodes;

  for (n = agfstnode(g); n; n = agnxtnode (g,n)) {
    STSIZE(n) = 0;
    NCHILD(n) = 0;
    SCENTER(n) = INF;
    if (isLeaf(g,n)) SLEAF(n) = 0;
    else SLEAF(n) = INF;
  }
}

/*
 * Working recursively in from each leaf node (ie, each node
 * with nStepsToLeaf == 0; see initLayout), set the
 * minimum value of nStepsToLeaf for each node.  Using
 * that information, assign some node to be the centerNode.
*/
static Agnode_t*
findCenterNode(Agraph_t* g) 
{
  Agnode_t* n;
  Agnode_t* center=NULL;
  int maxNStepsToLeaf = 0;

    /* With just 1 or 2 nodes, return anything. */
  if (agnnodes(g) <= 2) return (agfstnode(g));

    /* dfs from each leaf node */
  for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
    if (SLEAF(n) == 0) 
      setNStepsToLeaf(g, n, 0);
  }

  for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
    if (SLEAF(n) > maxNStepsToLeaf) {
      maxNStepsToLeaf = SLEAF(n);
      center = n;
    }
  }
  return center;
}

/* dfs to set distance from center
 * Note that termination is implicit in the test
 * for reduced number of steps. Proof?
 */
static void
setNStepsToCenter(Agraph_t* g, Agnode_t* n, Agnode_t* prev)
{
  Agnode_t* next;
  Agedge_t* ep;
  int nsteps = SCENTER(n) + 1;

  for (ep = agfstedge(g,n); ep; ep = agnxtedge(g,ep,n)) {
    if ((next = ep->tail) == n) next = ep->head;

    if (prev == next) continue;

    if (nsteps < SCENTER(next)) {
      SCENTER(next) = nsteps;
      if (PARENT(next))
        NCHILD(PARENT(next))--;
      PARENT(next) = n;
      NCHILD(n)++;
      setNStepsToCenter(g, next, n);
    }
  }
}


/*
 * Work out from the center and determine the value of
 * nStepsToCenter and parent node for each node.
 */
static int
setParentNodes(Agraph_t* sg, Agnode_t* center)
{
  Agnode_t* n;
  int maxn = 0;

  SCENTER(center) = 0;
  PARENT(center) = 0;
  setNStepsToCenter(sg, center, 0);

   /* find the maximum number of steps from the center */
  for (n = agfstnode(sg); n; n = agnxtnode(sg,n)) {
    if (SCENTER(n) > maxn) {
      maxn = SCENTER(n);
    }
  }
  return maxn;
}

/* Sets each node's subtreeSize, which counts the number of 
 * leaves in subtree rooted at the node.
 * At present, this is done bottom-up.
 */
static void
setSubtreeSize(Agraph_t* g, Agnode_t* center)
{
  Agnode_t* n;
  Agnode_t* parent;

  for (n = agfstnode(g); n; n = agnxtnode (g,n)) {
    if (NCHILD(n) > 0) continue;
    STSIZE(n)++;
    parent = PARENT(n);
    while (parent) {
      STSIZE(parent)++;
      parent = PARENT(parent);
    }
  }
}

static void
setChildSubtreeSpans(Agraph_t* g, Agnode_t* n) 
{
  Agedge_t* ep;
  Agnode_t* next;
  double    ratio;

  ratio = SPAN(n) / STSIZE(n);
  for (ep = agfstedge(g,n); ep; ep = agnxtedge(g,ep,n)) {
    if ((next = ep->tail) == n) next = ep->head;
    if (PARENT(next) != n) continue;

    SPAN(next) = ratio * STSIZE(next);

    if (NCHILD(next) > 0) {
      setChildSubtreeSpans(g, next);
    }
  }
}

static void
setSubtreeSpans(Agraph_t* sg, Agnode_t* center) 
{
  SPAN(center) = 2*PI;
  setChildSubtreeSpans(sg, center);
}


 /* Set the node positions for the 2nd and later rings. */
static void
setChildPositions(Agraph_t* sg, Agnode_t* n)
{
  Agnode_t* next;
  Agedge_t* ep;
  double    theta; /* theta is the lower boundary radius of the fan */

  if (PARENT(n) == 0) /* center */
    theta = 0;
  else
    theta = THETA(n) - SPAN(n)/2;

  for (ep = agfstedge(sg,n); ep; ep = agnxtedge(sg,ep,n)) {
    if ((next = ep->tail) == n) next = ep->head;
    if (PARENT(next) != n) continue;

    THETA(next) = theta + SPAN(next)/2.0 ;
    theta += SPAN(next);

    if (NCHILD(next) > 0)
      setChildPositions(sg, next);
  }
}

static void
setPositions(Agraph_t* sg, Agnode_t* center) 
{
  THETA(center) = 0;
  setChildPositions(sg, center);
}

static void
setAbsolutePos(Agraph_t* g)
{
  char*       p;
  Agnode_t*   n;
  double      xf;
  double      hyp;

  p = late_string(g,agfindattr(g->root,"ranksep"),NULL);
  if (p) {
    if (sscanf(p,"%lf",&xf) == 0) xf = DEF_RANKSEP;
    else {if (xf < MIN_RANKSEP) xf = MIN_RANKSEP;}
    }
  else xf = DEF_RANKSEP;
  if (Verbose) fprintf (stderr, "Rank separation = %f\n", xf);

    /* Convert circular to cartesian coordinates */
  for (n = agfstnode(g); n; n = agnxtnode (g,n)) {
    hyp = xf*(SCENTER(n));
    ND_pos(n)[0] = hyp*cos(THETA(n));
    ND_pos(n)[1] = hyp*sin(THETA(n));
  }
}

#if 0 /* not used */
static void
dumpGraph (Agraph_t* g)
{
  Agnode_t*   n;
  char*       p;

  fprintf (stderr, "     :  leaf  stsz nkids  cntr parent   span  theta\n");
  for (n = agfstnode(g); n; n = agnxtnode (g,n)) {
    if (PARENT(n)) p = PARENT(n)->name;
    else p = "<C>";
    fprintf (stderr, "%4s :%6d%6d%6d%6d%7s%7.3f%7.3f%8.3f%8.3f\n",
      n->name, SLEAF(n), STSIZE(n), NCHILD(n),
      SCENTER(n), p, SPAN(n), THETA(n), ND_pos(n)[0], ND_pos(n)[1]);
  }
}
#endif

/* circleLayout:
 *  We assume sg is is connected and non-empty.
 *  Also, if center != 0, we are guaranteed that center is
 *  in the graph.
 */
void
circleLayout(Agraph_t* sg, Agnode_t* center) 
{
  /* int maxNStepsToCenter; */

  if (agnnodes(sg) == 1) {
    Agnode_t* n = agfstnode(sg);
    ND_pos(n)[0] = 0;
    ND_pos(n)[1] = 0;
    return;
  }

  initLayout(sg);

  if (!center)
    center = findCenterNode(sg);
  if (Verbose) fprintf (stderr, "Center = %s\n", center->name);

  /* maxNStepsToCenter = setParentNodes(sg,center); */
  setParentNodes(sg,center);

  setSubtreeSize(sg, center);

  setSubtreeSpans(sg, center);

  setPositions(sg, center);

  setAbsolutePos (sg);
  /* dumpGraph (sg); */
}