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

static freer(edge) GRAPH_EDGE edge; {
  return;
}

static UINT hasher(edge) register GRAPH_EDGE edge; {
  return ((UINT) (edge -> from) >> 2) + 
         (UINT) (edge -> to) +
	 ((UINT) (edge -> label) << 8) +
	 (UINT) (edge -> index);
}

static GRAPH_EDGE copier(edge) GRAPH_EDGE edge; {
  return edge;
}

static UINT tester(edge1, edge2) register GRAPH_EDGE edge1, edge2; {
  return edge1 -> from == edge2 -> from &&
         edge1 -> to == edge2 -> to &&
	 edge1 -> label == edge2 -> label &&
	 edge1 -> index == edge2 -> index;
}

GRAPH new_graph() {
  GRAPH g = (GRAPH) malloc(sizeof (*g));
  g -> first_node = NULL_NODE;
  g -> last_node = NULL_NODE;
  g -> next_graph_index = 1;
  g -> max_graph_index = 4;
  g -> lookup_table = g_new_map(hasher, freer, copier, tester);
  g -> edge_cache = NULL_EDGE;
  g -> bunch_cache = NULL_BUNCH;
  return g;
}

GRAPH_INDEX next_graph_index(g) GRAPH g; {
  if (g -> next_graph_index == g -> max_graph_index) {
    GRAPH_NODE temp_node;

    g -> max_graph_index *= 2;

    foreachnodein(g,temp_node) {
      temp_node -> data = (UINT *) realloc(temp_node -> data,
				  sizeof(UINT) * g -> max_graph_index);
    }
  }
  return g -> next_graph_index++;
}

GRAPH_NODE new_node(g) GRAPH g; {
  GRAPH_NODE n = (GRAPH_NODE) malloc (sizeof (*n));
  n -> from_list = NULL_BUNCH;
  n -> to_list = NULL_BUNCH;
  n -> next_node = g -> first_node;
  g -> first_node = n;
  n -> data = (UINT *) malloc(sizeof(UINT) * g -> max_graph_index);
  return n;
}

GRAPH_EDGE find_edge(graph, index, label, from, to)
     GRAPH graph;
     GRAPH_INDEX index;
     UINT label;
     GRAPH_NODE from;
     GRAPH_NODE to;
{
  struct graph_edge dummy;
  GRAPH_EDGE e;
  UINT table_index;

  dummy.from = from;
  dummy.to = to;
  dummy.label = label;
  dummy.index = index;

  table_index = g_inmap(graph -> lookup_table, &dummy);
  if (table_index > 0) {
    return (GRAPH_EDGE) g_unmap(graph -> lookup_table, table_index);
  }
  else return NULL_EDGE;
}

static GRAPH_EDGE new_edge(graph, index, label, from, to)
     GRAPH graph;
     GRAPH_INDEX index;
     UINT label;
     GRAPH_NODE from;
     GRAPH_NODE to;
{
  GRAPH_EDGE e;
  UINT lookup_index;

  if (graph -> edge_cache == NULL_EDGE)
    e = (GRAPH_EDGE) malloc (sizeof (*e));
  else {
    e = graph -> edge_cache;
    graph -> edge_cache = e -> next_from;
  }

  e -> from = from;
  e -> to = to;
  e -> label = label;
  e -> index = index;

  lookup_index = g_map(graph -> lookup_table, e);

  if (e != (GRAPH_EDGE) g_unmap(graph -> lookup_table, lookup_index)) {
    /* Not a new entry; fix up. */
    /* link onto free edge cache */
    e -> next_from = graph -> edge_cache;
    graph -> edge_cache = e;
    e = NULL_EDGE;
  }
  return e;
}

static GRAPH_BUNCH find_bunch(pb, index)
     GRAPH_BUNCH * pb;
     GRAPH_INDEX index;
{
  GRAPH_BUNCH b, temp;
  temp = NULL_BUNCH;
  b = *pb;
  while (b != NULL_BUNCH && b -> index != index) {
    temp = b;
    b = b -> next_bunch;
  }
  if (b == NULL_BUNCH || b == *pb) return b;

  /* Else do a move-to-front to ease later searches */
  temp -> next_bunch = b -> next_bunch;
  b -> next_bunch = *pb;
  *pb = b;

  return b;  
}

static GRAPH_BUNCH new_bunch(g, pb, index)
     GRAPH g;
     GRAPH_BUNCH * pb;
     GRAPH_INDEX index;
{
  GRAPH_BUNCH b;
  if (g -> bunch_cache == NULL_BUNCH) 
    b = (GRAPH_BUNCH) malloc (sizeof *b);
  else {
    b = g -> bunch_cache;
    g -> bunch_cache = b -> next_bunch;
  }
    
  b -> next_bunch = *pb;
  *pb = b;
  b -> index = index;
  b -> first_edge = NULL_EDGE;
  b -> last_edge = NULL_EDGE;
  return b;
}
GRAPH_EDGE  new_edge_before(graph, index, label, from, to )
     GRAPH graph;
     GRAPH_INDEX index;
     UINT label;
     GRAPH_NODE from;
     GRAPH_NODE to;
{
  GRAPH_EDGE e = new_edge(graph, index, label, from, to);
  GRAPH_BUNCH b;
  if (e == NULL_EDGE) return find_edge(graph, index, label, from, to);

  b = find_bunch(&(from -> from_list), index);
  if (b == NULL_BUNCH) b = new_bunch(graph, &(from -> from_list), index);

  e -> next_from = b -> first_edge;
  b -> first_edge = e;
  if (e -> next_from == NULL_EDGE) b -> last_edge = e;

  b = find_bunch(&(to -> to_list), index);
  if (b == NULL_BUNCH) b = new_bunch(graph, &(to -> to_list), index);

  e -> next_to = b -> first_edge;
  b -> first_edge = e;
  if (e -> next_to == NULL_EDGE) b -> last_edge = e;

  return e;
}

GRAPH_EDGE new_edge_after(graph, index, label, from, to)
     GRAPH graph;
     GRAPH_INDEX index;
     UINT label;
     GRAPH_NODE from;
     GRAPH_NODE to;
{
  GRAPH_EDGE e = new_edge(graph, index, label, from, to);
  GRAPH_BUNCH b;
  if (e == NULL_EDGE) return find_edge(graph, index, label, from, to);

  b = find_bunch(&(from -> from_list), index);
  if (b == NULL_BUNCH) b = new_bunch(graph, &(from -> from_list), index);

  if (b -> last_edge == NULL_EDGE) {
    b -> first_edge = e;
  }
  else {
    b -> last_edge -> next_from  = e;
  }
  e -> next_from = NULL_EDGE;
  b -> last_edge = e;

  b = find_bunch(&(to -> to_list), index);
  if (b == NULL_BUNCH) b = new_bunch(graph, &(to -> to_list), index);

  if (b -> last_edge == NULL_EDGE) {
    b -> first_edge = e;
  }
  else {
    b -> last_edge -> next_to  = e;
  }
  e -> next_to = NULL_EDGE;
  b -> last_edge = e;

  return e;
}

delete_edge(g,e) GRAPH g; GRAPH_EDGE e;
{
  GRAPH_NODE from = e -> from;
  GRAPH_NODE to = e -> to;
  GRAPH_BUNCH b;
  GRAPH_EDGE * pe;
  GRAPH_EDGE temp;
  GRAPH_INDEX index = e -> index;
  UINT j = g_inmap(g -> lookup_table, e);

  if (j == 0) return; /* Should I complain? */

  g_delent(g -> lookup_table, j);

  /* Need to take it out of lists */

  /* Remove from the FROM list */  
  b = find_bunch(&(from -> from_list), index);
  pe = &(b -> first_edge);
  temp = *pe;
  while (temp != e) {
    pe = &(temp -> next_from);
    temp = *pe;
  }
  *pe = e -> next_from;
  if (b -> last_edge == e) b -> last_edge = *pe;

  /* Remove from the TO list */
  b = find_bunch(&(to -> to_list), index);
  pe = &(b -> first_edge);
  temp = *pe;
  while (temp != e) {
    pe = &(temp -> next_to);
    temp = *pe;
  }
  *pe = e -> next_to;
  if (b -> last_edge == e) b -> last_edge = *pe;

  /* Blast a bunch of fields to prevent confusion */
  e -> next_to = NULL_EDGE;
  e -> from = NULL_NODE;
  e -> to = NULL_NODE;
  e -> index = NULL_INDEX;

  /* link onto free edge cache */
  e -> next_from = g -> edge_cache;
  g -> edge_cache = e;

  return;
}

delete_graph_index(g,i) GRAPH g; GRAPH_INDEX i;
{
  GRAPH_BUNCH b;
  GRAPH_EDGE e;
  GRAPH_NODE n;

  n = g -> first_node;
  while (n != NULL_NODE) {
    n -> data[i] = 0;
    b = find_bunch(&(n -> from_list), i);
    if (b != NULL_BUNCH) {
      if (b -> last_edge != NULL_EDGE) {

        e = b -> first_edge;

	while (e != NULL_EDGE) {
	  UINT j = g_inmap(g -> lookup_table, e);
	  GRAPH_EDGE old_e = e;
	  g_delent(g -> lookup_table, j);
	  e -> next_to = NULL_EDGE;
	  e -> from = NULL_NODE;
	  e -> to = NULL_NODE;
	  e -> index = NULL_INDEX;
	  e = e -> next_from;
	  free(old_e);
	}

        /* Glue to the edge cache in a batch */
/* 	b -> last_edge -> next_from = g -> edge_cache;
	g -> edge_cache = b -> first_edge;
*/	}

      /* Because of a move-to-front stategy, we know how to delete b */
      n -> from_list = b -> next_bunch;
      b -> next_bunch = g -> bunch_cache;
      g -> bunch_cache = b;
    }

    /* Now do the TO list */
    b = find_bunch(&(n -> to_list), i);

    if (b != NULL_BUNCH) {   
      /* Because of a move-to-front stategy, we know how to delete b */
      n -> to_list = b -> next_bunch;
      b -> next_bunch = g -> bunch_cache;
      g -> bunch_cache = b;
    }
    n = n -> next_node;    
  } 
}
   

UINT foreach_edge_from(graph, index, from, func, state)
   GRAPH graph;
   GRAPH_INDEX index;
   GRAPH_NODE from;
   UINT (*func)();
   UINT state;
{
  GRAPH_BUNCH b;
  GRAPH_EDGE e;
  b = find_bunch(&(from -> from_list), index);
  if (b == NULL_BUNCH) return state;
  e = b -> first_edge;
  while (e != NULL_EDGE) {
    state = (*func)(e, state);
    e = e -> next_from;
  }
  return state;
}

UINT foreach_edge_to(graph, index, to, func, state)
   GRAPH graph;
   GRAPH_INDEX index;
   GRAPH_NODE to;
   UINT (*func)();
   UINT state;
{
  GRAPH_BUNCH b;
  GRAPH_EDGE e;
  b = find_bunch(&(to -> to_list), index);
  if (b == NULL_BUNCH) return state;
  e = b -> first_edge;
  while (e != NULL_EDGE) {
    state = (*func)(e, state);
    e = e -> next_to;
  }
  return state;
}

UINT foreach_edge(graph, func, state)
   GRAPH graph;
   UINT (*func)();
   UINT state;
{
  GMAP m = graph -> lookup_table;
  UINT imax = g_map_size(m);
  UINT i;
  for (i = 1; i <= imax; i++) {
    if (g_valid_index(m,i)) state = (*func)(g_unmap(m,i),state);
  }
}

struct filter_thunk {
  UINT (*func)();
  UINT state;
  GRAPH_INDEX index;
};

static struct filter_thunk * filter_func(edge, state)
     GRAPH_EDGE edge;
     struct filter_thunk * state;
{
  if (state -> index == edge -> index) 
    state -> state = (*(state -> func))(edge, state -> state);
  return state;
}

UINT foreach_edge_in_i(graph, index, func, state)
   GRAPH graph;
   GRAPH_INDEX index;
   UINT (*func)();
   UINT state;
{
  struct filter_thunk filter_state;
  filter_state.func = func;
  filter_state.index = index;
  filter_state.state = state;

  filter_state.state = foreach_edge(graph, filter_func, &filter_state);

  return filter_state.state;
}
#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\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 '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