#include "util.h"
#include "gmap.h"
#include "graph.h"
#include "lists.h"
#include "uf.h"

extern free();

/* This next cheats somewhat and ignores the directedness of edges, sort of. */
/* In this case, the label contains the cost. */

typedef struct costfn_and_prioq {
 CELL (*cf)();
 LIST * pq;
} STATE;

STATE * put_in_queue(edge,state) GRAPH_EDGE edge; STATE * state;
{
  int i = (*(state -> cf))(edge);
  state -> pq[i] = list_prepend(state -> pq[i], edge);
  return state;
}

default_costfn(edge) GRAPH_EDGE edge;
{
  return edge_label(edge);
}

GRAPH_INDEX graph_spanning_tree(g, old_i, maxcost, costfn, ptotcost)
     GRAPH g; GRAPH_INDEX old_i; int maxcost; CELL (*costfn)(); int * ptotcost;
{
  GRAPH_INDEX new_i = next_graph_index(g);
  LIST * priority_queue = (LIST *) malloc((maxcost + 1) * sizeof(LIST));
  GRAPH_NODE n;
  STATE temp;

  int totcost = 0;

  int i,j,k;
  int cost;

  if (costfn == 0) costfn = default_costfn;

  temp.pq = priority_queue;
  temp.cf = costfn;

  for (i = 0; i <= maxcost; i++)
    priority_queue[i] = list_new();

  foreach_edge_in_i(g, old_i, put_in_queue, &temp);
  
  priority_queue = temp.pq;

  foreachnodein(g,n)
    node_data(n,new_i) = UF_new(n);

  for (cost = 0; cost <= maxcost; cost++)
    {
      LIST l = priority_queue[cost];
      while (!list_is_empty(l))
	{
	  GRAPH_EDGE e = (GRAPH_EDGE) list_data(l);
	  GRAPH_NODE from = edge_from(e),
	             to = edge_to(e);
	  UF_TREE wfrom = UF_find(node_data(from,new_i)),
	          wto = UF_find(node_data(to,new_i));
	  if ((CELL) wfrom != (CELL) wto)
	    {
	      UF_union(wfrom,wto);
	      if ((CELL) wfrom < (CELL) wto)
		new_edge_after(g,new_i,0,from,to);
	      else
		new_edge_after(g,new_i,0,to,from);
	      totcost += cost;
	    }
	  l = list_delete_one(l);
	}
    }

  free(priority_queue);

  if (ptotcost != 0)
    *ptotcost = totcost;

  return new_i;
}


#ifdef TEST
#include <stdio.h>

struct print_state {
  FILE * fd;
  GRAPH g;
};

print_edge(e,g,fd) GRAPH g; GRAPH_EDGE e; FILE * fd; {
  fprintf(fd, "E = %d (%d), F = %d, T = %d, L = %d, I = %d\n",
	  e, g_inmap (g -> lookup_table, e),
	  e -> from, e -> to, e -> label, e -> index);
}


static struct print_state * special_print_edge(edge, state)
     GRAPH_EDGE edge;
     struct print_state * state;
{
  print_edge(edge, state -> g, state -> fd);
  return state;
}

FILE * dump_graph(g, file)
     GRAPH g;
     FILE * file;
{
  struct print_state foo;

  foo.fd = file;
  foo.g = g;

  foreach_edge(g, special_print_edge, &foo);
  return file;
}

main() {
  char buffer[256];
  UINT i;
  GRAPH_NODE n[10];
  GRAPH g = new_graph();
  GRAPH_INDEX gmax = next_graph_index(g);
  UINT l;
  UINT from, to;
  GRAPH_EDGE e;

  int totcost;

  int iterating = 1;

  for (i = 0; i < 10; i++) n[i] = new_node(g);
       
  while (iterating)  {
    printf("Add f,t,l,g; Look f,t,l,g; Remove i; Index i; Dump; Quit; Extend; Clear i; Span i\n");
    scanf("%s", buffer);

    switch(buffer[0]) {
    case 'e': case 'E':
      gmax = next_graph_index(g);
      printf("New max graph index is %d\n", gmax);
      break;
    case 's': case 'S':
      scanf("%d", &i);
      if (i > 0 && i <= gmax)
	{
	  gmax = graph_spanning_tree(g,i,1000,0,&totcost);
	  printf("Spanning tree returns new max graph index %d, cost %d\n", gmax, totcost);
	}
      else
	{
	  printf("Urp!");
	}
      break;
    case 'c': case 'C':
      scanf("%d", &i);
      if (i > 0 && i <= gmax) {
	delete_graph_index(g,i);
      }
      break;
    case 'a': case 'A':
      scanf("%d", &from);
      scanf("%d", &to);
      scanf("%d", &l);
      scanf("%d", &i);
      if (from >= 0 && from < 10 &&
	  to >= 0 && to < 10 &&
	  i <= gmax && i > 0) {
	/* All is ok; do the addition */
	e = new_edge_after(g, i, l, n[from], n[to]);
      }
      else {
	printf("Something was invalid\n");
      }
      break;
    case 'r': case 'R':
      scanf("%d", &i);
      if (i > 0 &&
	  i <= g_map_size(g -> lookup_table) &&
	  g_valid_index(g -> lookup_table,i)) {
	delete_edge(g, g_unmap(g -> lookup_table, i));
      }
      else {
	printf("Something was invalid\n");
      }
      break;
    case 'l': case 'L':
      scanf("%d", &from);
      scanf("%d", &to);
      scanf("%d", &l);
      scanf("%d", &i);
      if (from >= 0 && from < 10 &&
	  to >= 0 && to < 10 &&
	  i <= gmax && i > 0) {
	/* All is ok; do the addition */
	e = find_edge(g, i, l, n[from], n[to]);
	printf("Found edge %d (%d)\n", e, g_inmap(g -> lookup_table, e));
      }
      else {
	printf("Something was invalid\n");
      }
      break;
    case 'i': case 'I':
      scanf("%d", &i);
      if (i > 0 &&
	  i <= g_map_size(g -> lookup_table) &&
	  g_valid_index(g -> lookup_table,i)) {
	e = (GRAPH_EDGE) g_unmap(g -> lookup_table, i);
	print_edge(e,g,stdout);
      }
      else {
	printf("Something was invalid\n");
      }
      break;
    case 'd': case 'D':
      dump_graph(g,stdout);
      break;
    case 'q': case 'Q':
      iterating = 0;    
      break;
    }
  }
}
#endif