/* =============================================================== */
#include "meta.h"

int node_distance ()
{

/*  node_distance starts with the page array and page_link matrix,
    assuming that for all nodes the dist_to_base field is currently
    marked as either UNREACHED or 0.  It then fills in the
    dist_to_base fields of as yet UNREACHED nodes with their distance
    from any reached node.  It normally returns the maximal
    distance + 1 found for any connected node.  If a node is
    initially neither UNREACHED nor 0, it returns -2.  If no node
    is 0 (no base), it returns -1.
*/

   extern int                num_pages;
   extern struct page_rec    page[];
   extern char               page_link[];

   int    next_level, page_ix, from_dex, to_dex, empty, pageloc[MAX_PAGE];
   int    dtb, fromloc,toloc;

   next_level = -1;

   /* set up list for *bidirectional* breadth-first search;  this list
      contains, first, reached nodes, then an empty slot, then
      unreached nodes
   */

   from_dex = 0;
   to_dex = num_pages;
   for (page_ix=0 ; page_ix<num_pages; page_ix++)
   {
      dtb = page[page_ix].dist_to_base;
      if (dtb == 0)
      {
         pageloc[from_dex++] = page_ix;
      }
      else if (dtb == UNREACHED)
      {
         pageloc[to_dex--] = page_ix;
      }
      else
      {
         printf ("Node_distance: node#%d had dist_to_base=%d, name=%s \n",
                 page_ix, dtb, page[page_ix].nickname);
         return (-2);
      }  /* ENDIF: */
   }

   if (to_dex != from_dex)
   {
      printf ("Node_distance subscript error: from=%d, to=%d\n",
                 from_dex, to_dex);
      return (-3);
   }  /* ENDIF: */


   empty = from_dex;
   from_dex = 0;

   while (from_dex < empty)
   {
      fromloc = pageloc[from_dex++];
      next_level = page[fromloc].dist_to_base + 1;

      for (to_dex = empty+1; to_dex <= num_pages; to_dex++)
      {
         toloc = pageloc[to_dex];

         /* Is to-page bi-directionally adjacent to from-page?
            Skip if not.  */
         if (page_link[fromloc*num_pages + toloc] == '.' &&
             page_link[toloc*num_pages + fromloc] == '.') continue;

         /* move to-entry into reached segment */
         pageloc[empty]  = toloc;
         pageloc[to_dex] = pageloc[++empty];

         /* mark as reached */
         page[toloc].dist_to_base = next_level;

         /* printf ("Marking as dist_to_base: name=%s, level=%d \n",
                     page[toloc].nickname, next_level);
		     */

      }  /* ENDFOR: */
   }  /* ENDWHILE: */

   return (next_level);
}