/*
This file implements an undirected graph structure. 
Copyright (C) 2004 The University of Texas at Austin

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your option)
any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place - Suite 330, Boston, MA 02111-1307, USA.

Email: usman@cs.njit.edu
Mail: Usman Roshan, Department of Computer Sciences, NJIT-CCS, Computer
Science Department, GITC 4400, University Heights, Newark, NJ 07102
*/
#include<ugraph_aux_vars.h>
#include<ugraph.h>
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<hashtable2.h>

static void assign_graph_rec(ugraph dest, ugraph src, hashtable2 node_map,
			     edge e, node v);

/*appends the new node into the list of nodes*/
node new_node(ugraph G, void* aux_vars_) {
  
  node n;

  n = (node) malloc(sizeof(struct node_struct));
  
  if(!G->first_node) G->first_node = n;
  if(G->last_node) G->last_node->next = n;

  n->prev = G->last_node;
  n->next = 0;
  G->last_node = n;

  G->n_nodes++;
  G->id_nodes++;
  n->id = G->id_nodes;
  n->degree = 0;
  
  n->first_edge = 0;
  n->last_edge = 0;
  
  n->aux_vars = aux_vars_;
  
  return n;
}

/*function del_edge_aux_vars MUST be defined to free up
  the edge auxillary variables*/
void del_edge(ugraph G, edge e){

  assert(G); assert(e);

  e->u->degree--;
  e->v->degree--;

  if(e == G->first_edge) G->first_edge = e->next;
  if(e == G->last_edge) G->last_edge = e->prev;

  if(e == e->u->first_edge) e->u->first_edge = e->u_next;
  if(e == e->u->last_edge) e->u->last_edge = e->u_prev;

  if(e == e->v->first_edge) e->v->first_edge = e->v_next;
  if(e == e->v->last_edge) e->v->last_edge = e->v_prev;
  
  if(e->prev) e->prev->next = e->next;
  if(e->next) e->next->prev = e->prev;

  if(e->u_prev) {
    if(e->u_prev->u == e->u) e->u_prev->u_next = e->u_next;
    else if(e->u_prev->v == e->u) e->u_prev->v_next = e->u_next;
    else assert(0);
  }
  if(e->v_prev) {
    if(e->v_prev->v == e->v) e->v_prev->v_next = e->v_next;
    else if(e->v_prev->u == e->v) e->v_prev->u_next = e->v_next;
    else assert(0);
  }
  
  if(e->u_next) {
    if(e->u_next->u == e->u) e->u_next->u_prev = e->u_prev;
    else if(e->u_next->v == e->u) e->u_next->v_prev = e->u_prev;
    else assert(0);
  }
  
  if(e->v_next){
    if(e->v_next->v == e->v) e->v_next->v_prev = e->v_prev;
    else if(e->v_next->u == e->v) e->v_next->u_prev = e->v_prev;
    else assert(0);
  }
  
  del_edge_aux_vars(e->aux_vars);
  free(e);
  G->n_edges--;
}
  
/*function del_node_aux_vars MUST be defined to delete auxilliary
  variables*/
void del_node(ugraph G, node u){ 

  edge temp_edge = u->first_edge;

  assert(G); assert(u);

  while(temp_edge){
    del_edge(G, temp_edge);
    temp_edge = u->first_edge;
  }
  
  if(u->prev) u->prev->next = u->next;
  if(u->next) u->next->prev = u->prev;

  if(G->first_node == u) G->first_node = u->next;
  if(G->last_node == u) G->last_node = u->prev;

  /*free aux_vars in main code using proper casting*/
  del_node_aux_vars(u->aux_vars);
  free(u);
  G->n_nodes--;
}

edge new_edge(ugraph G, node u, node v, void* aux_vars_) {
  
  edge e;
  
  e = (edge) malloc(sizeof(struct edge_struct));

  e->aux_vars = aux_vars_;

  if(!G->first_edge) G->first_edge = e;
  if(G->last_edge) G->last_edge->next = e;

  e->prev = G->last_edge;
  e->next = 0;
  G->last_edge = e;

  G->n_edges++;
  G->id_edges++;
  e->id = G->id_edges;

  u->degree++;
  v->degree++;

  e->u = u;
  e->v = v;
  
  if(u->last_edge) {
    e->u_next = 0;
    if(u->last_edge->u == u)
      u->last_edge->u_next = e;
    else if(u->last_edge->v == u)
      u->last_edge->v_next = e;
    else assert(0);
    
    e->u_prev = u->last_edge; 
    u->last_edge = e;
  }
  else {
    e->u_next = 0; e->u_prev = 0;
    u->first_edge = e;
    u->last_edge = e;
  }
  
  if(v->last_edge) {
    e->v_next = 0;

    if(v->last_edge->v == v)
      v->last_edge->v_next = e;
    else if(v->last_edge->u == v)
      v->last_edge->u_next = e;
    else assert(0);

    e->v_prev = v->last_edge; 
    v->last_edge = e;
  }
  else {
    e->v_next = 0; e->v_prev = 0;
    v->last_edge = e;
    v->first_edge = e;
  }

  return e;
}

ugraph new_graph() {
  
  ugraph G;
   
  G = (ugraph) malloc(sizeof(struct ugraph_struct));
  
  G->first_edge = 0;
  G->last_edge = 0;
  G->first_node = 0;
  G->last_node = 0;
  
  G->n_nodes = 0;
  G->n_edges = 0;
  
  G->id_edges = 0;
  G->id_nodes = 0;

  return G;
}

void del_graph(ugraph G) {
  
  assert(G);
  while(G->first_node) {
    del_node(G, G->first_node);
  }
  /*while(G->first_edge) del_edge(G->first_edge);*/
  assert(G->n_nodes==0 && G->n_edges==0);
  free(G);
}

void print_graph(ugraph G) {
  
  /* Data */
  node n; edge e;

  /* Code */
  assert(G);
  printf("\nEdges\n");
  for(e = G->first_edge; e; e = e->next){
    printf("ptr: %d id: %d u_id: %d v_id: %d\nprev: %d next: %d\nprev_u: %d next_u: %d\nprev_v: %d next_v: %d\n\n",
	   (unsigned int)e, e->id, e->u->id, e->v->id, (unsigned int)e->prev, (unsigned int)e->next, 
	   (unsigned int)e->u_prev, (unsigned int)e->u_next, (unsigned int)e->v_prev, (unsigned int)e->v_next);
  }

  printf("Num of nodes = %d, num of edges = %d\n", G->n_nodes, G->n_edges);
  for(n = G->first_node; n; n = n->next) {
    printf("(%d %d): ", n->id, n->degree);
    for(e = n->first_edge; e;){
      printf(" (%d-%d) ", e->u->id, e->v->id);
      if(e->u == n) e = e->u_next;
      else if (e->v == n) e = e->v_next;
      else assert(0);
    }
    printf("\n");
  }
}

node opposite(node u, edge e){ 

  assert(u); assert(e);
  assert(e->u == u || e->v == u);
  if(e->u == u) return e->v;
  else return e->u;
}

/*TODO: need to make sure it works on any graph as 
  opposed to just a tree. right now it suffices for trees.*/
void assign_graph(ugraph dest, ugraph src){
  
  hashtable2 node_map;
  node v, n; node_aux_vars nvars; int i;

  assert(dest && src); 
  assert(dest->n_edges==0 && dest->n_nodes==0);
  node_map = new_hashtable2(src->n_nodes);
  
  /*pick an internal node and recurse from there*/
  for(v=src->first_node; v; v=v->next){
    if(v->degree > 1){
      /*make new node in dest and recurse*/
      nvars = new_node_aux_vars(); assign_node_aux_vars(nvars, v->aux_vars);
      n = new_node(dest, nvars);
      insert_hashtable2(node_map, (PTR_TYPE) v, (void*) n);
      assign_graph_rec(dest, src, node_map, (edge) 0, v);
      break;
    }
  }
  
  /*delete node_map hashtable*/
  for(i=0; i < node_map->size_; i++)
    if(node_map->table_[i]) node_map->table_[i]->value = NULL;
  del_hashtable2(node_map);

}

static void assign_graph_rec(ugraph dest, ugraph src, hashtable2 node_map,
		      edge e, node v){

  edge f; node u, n, a, b; 
  node_aux_vars nvars; edge_aux_vars evars;
  
  for(f = v->first_edge; f; ){
    if(f!=e){
      u = opposite(v, f);
      if(lookup_hashtable2(node_map, (PTR_TYPE) u)){
	/*node already exists, so only insert edge*/
	a = (node) lookup_hashtable2(node_map, (PTR_TYPE) u);
	b = (node) lookup_hashtable2(node_map, (PTR_TYPE) v);
	assert(a && b);
	evars = new_edge_aux_vars(); assign_edge_aux_vars(evars, f->aux_vars);
	new_edge(dest, a, b, evars);
      }
      else {
	/*create node and insert edge and recurse*/
	nvars = new_node_aux_vars(); assign_node_aux_vars(nvars, u->aux_vars);
	n = new_node(dest, nvars);
	insert_hashtable2(node_map, (PTR_TYPE) u, (void*) n);

	a = (node) lookup_hashtable2(node_map, (PTR_TYPE) v);
	assert(a); evars = new_edge_aux_vars(); 
	assign_edge_aux_vars(evars, (edge_aux_vars) f->aux_vars);
	assert(evars->wgt == ((edge_aux_vars)f->aux_vars)->wgt);
	new_edge(dest, n, a, evars);

	assign_graph_rec(dest, src, node_map, f, u);
      }
    }
    if(f->u == v) f = f->u_next;
    else if (f->v == v) f = f->v_next;
    else assert(0);
  }
  return;
}