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

static countup(edge,count) GRAPH_EDGE edge; int count; {
  return count + 1;
}

typedef struct lip {
  LIST list;
  GRAPH_INDEX index;
} * LIP; 

static LIP countdown(edge,lip) GRAPH_EDGE edge; LIP lip; {
  GRAPH_NODE n = edge_to(edge);
  int count = -- node_data(n,lip -> index);
  if (count == 0) {
    lip -> list = list_prepend(lip -> list, n);
  }
  return lip;
}

LIST graph_tsort(g, i, unsorted) GRAPH g; GRAPH_INDEX i; LIST * unsorted; {
  GRAPH_INDEX j = next_graph_index(g);
  GRAPH_NODE n;
  GRAPH_NODE last = NULL_NODE;
  LIST l = list_new();
  LIST ordered = list_new();

  int count = 0;

  foreachnodein(g,n) {
    node_data(n,j) = foreach_edge_to(g,i,n,countup,0);
    count++; }

  foreachnodein(g,n)
    {
      if (node_data(n,j) == 0)
	l = list_prepend(l,n);
    }

  while (! list_is_empty(l)) {
    count--;
    n = (GRAPH_NODE) list_data(l);

    ordered = list_prepend(ordered, n);

    l = list_delete_one(l);
    {
      struct lip temp;
      temp.list = l;
      temp.index = j;
      l = ((LIP) foreach_edge_from(g,i,n,countdown,&temp)) -> list;
    }
  }

  if (unsorted != 0)
    {
      foreachnodein(g,n)
	{
	  if (node_data(n,j) != 0)
	    l = list_prepend(l,n);
	}
      *unsorted = l;
    }

  delete_graph_index(g,j);

  return list_reverse(ordered);
}

#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 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; Tsort 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 'c': case 'C':
      scanf("%d", &i);
      if (i > 0 && i <= gmax) {
	delete_graph_index(g,i);
      }
      break;
    case 't': case 'T':
      scanf("%d", &i);
      if (i > 0 && i <= gmax) {
	LIST l = graph_tsort(g,i);
	while ( ! list_is_empty(l)) {
	  printf("%d\n", list_data(l));
	  l = list_delete_one(l);
	}
      }
      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