#! /usr/bin/gawk -f
# Last edited on 2001-01-15 03:05:03 by stolfi

BEGIN{
  abort = -1;
  usage = ( "compute-elem-distances \\\n" \
    "  { -v elemList='a,o,...' | -v elemTable=FILE } \\\n" \
    "  [ -v exponent=NUM ] \\\n" \
    "  < INFILE.wct > OUTFILE.tex" \
  );
  
  # Reads from standard input a table of element-element distances
  # d(u,v) in the format
  # 
  #   SYMB1 SYMB2 DIST
  #
  # where SYMB1 and SYMB2 are elements, and DIST = d(SYMB1,SYMB2).
  # 
  # Looks for a linear ordering v[1..n] of the elements that 
  # minimizes the sum W(v) of d(v[i-1],v[i]) for i in [2..n].
  # 
  # Only considers the elements listed in the string `elemList' or
  # in the file named `elemTable', ignoring entries which are 
  # "+", "-", "/", "~".
  
  if ((elemList == "") == (elemTable == ""))
    { arg_error("must define exactly one of \"elemList\" and \"elemTable\""); }
  split("", elem);
  split("", eindex);
  split("", eclass);
  if (elemList != "") 
    { nelems = parse_explicit_elems(elemList,elem,eindex,eclass); }
  else
    { nelems = load_elems_from_file(elemTable,elem,eindex,eclass); }
    
  # Eliminate bogus elements:
  
  k = 0;
  for (i = 1; i <= nelems; i++) 
    { if (elem[i] !~ /[-/~+]/) 
        { k++; elem[k] = elem[i]; eindex[elem[k]] = k; }
    }
  nelems = k;
  
  split("", d);
}

(abort >= 0) { exit abort; }

/^ *([#]|$)/ { next; }

/./ { 
  if (NF != 3) { data_error("bad line format"); }
  x = $1; y = $2; dist = $3;
  if ((x,y) in d) { data_error(("repeated pair \"" x "," y "\"")); }
  if ((x !~ /[-/~+]/) && (y !~ /[-/~+]/)) { d[x,y] = ct; }
  next;
}

END {
  if (abort >= 0) { exit abort; }
  compute_linear_order();
  for (i = 1; i <= nelems; i++) { print v[i]; }
}

function compute_linear_order(   n,i,budget)
{
  # Global in: 
  #    nelem = number of elements.
  #    elem[1..nelem] = the elements.
  #    d[u,v] = penalty for placing v after u, where u,v are elements.
  # Global out:
  #    v[1..nelem] = elements in proper sequence.
  
  n = nelems;
  split("", v);
  for (i = 1; i <= n; i++) { v[i] = elem[i]; }
  W = compute_cost(v);
  
  budget = 10 * n*n*n;
  while (1)
    { 
      printf "main iteration, W = %8.5f budget = %8d\n", W, budget > "/dev/stderr";
      if (budget <= 0) { return; }
      try_rearrangements();
    }
}
  
function try_rearrangements()
{
  # Global in:
  #   nelems = number of elements.
  #   d[u,v] = penalty for placing v after u.
  #   budget = number of trials allowed.
  #   v[1..nelems] = the current permutation.
  #   W = its cost.
  # Global out:
  #   v[1..nelems] = the best permutation found.
  #   W = its cost.
  #   budget = number of additional trials allowed.
  
  for (k = 2; k <= n; k++)
    { 
      if (budget <= 0 ) { return(1); }
      if (try_kfold_rearrangements(k)) { return; }
    }
  return (0);
}

function try_kfold_rearrangements(k,  beg,end,dir,w,i,j,r,d)
{
  # Tries the rearrangements that require splitting the 
  # current path into k pieces.
  
  split("", beg);
  split("", end);
  split("", dir);
  split("", w);
  for (i = 0; i < k; i++) { beg[i] = i; end[i] = i; dir[i] = +1; }
  while (find_next_rearrangement(beg,end,flip)) 
    { would 
      # Apply rearrangement
      j = 0;
      for (i = 0; i < k; i++)
        { d = dir[i];
          r = (d > 0 ? beg[i] : end[i]);
          s = (d > 0 ? end[i] : beg[i]);
          while(r != s) { j++; w[j] = v[r]; r += d; }
          
          
      
      i = k-1;
      while ((i > 0) && (flip[i]) && (