/*
This file converts a set of bipartitions into a tree.
Copyright (C) 2004 The University of Texas at Austin

Based upon Daniel Huson's implementation. 

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<splits2tree.h>
#include<hashtable2.h>
#include<split.h>
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<ugraph_aux_vars.h>
/*#include<time.h>*/

static void splits2tree_rec(const node v, const edge e, const list_node ln, const list listsplits, const int_set taxa, hashtable2 edge2split, phylogenetic_tree T);

/*extern int diff_time; */

void splits2tree(const list listsplits, const int_set taxa, phylogenetic_tree T){
  hashtable2 edge2split;
  node v; node_aux_vars node_vars;
  list_node it; int i;

  /*diff_time = 0;*/
  assert(T->G->n_nodes==0 && T->G->n_edges==0);
  assert(taxa && size_int_set(taxa));

  edge2split = new_hashtable2(size_list(listsplits));
  node_vars = new_node_aux_vars();
  assign_int_set(node_vars->taxaset, taxa);
  v = new_node(T->G, node_vars);
  for(it=listsplits->head; it; it=it->next)
    splits2tree_rec(v, (edge)0, it, listsplits, taxa, edge2split, T);
  
  /*free up the hashtable2 structure*/
  for(i=0; i < edge2split->size_; i++)
    if(edge2split->table_[i] && edge2split->table_[i]->value)
      edge2split->table_[i]->value=NULL;
  
  del_hashtable2(edge2split);
  edge2split=NULL;

  /*set taxon_ids correctly*/
  for(v=T->G->first_node; v; v=v->next)
    if(v->degree==1){
      T->num_leaves++;
      ((node_aux_vars)v->aux_vars)->taxon_id=
	choose_int_set(((node_aux_vars)v->aux_vars)->taxaset);
      assert(((node_aux_vars)v->aux_vars)->taxon_id != -1);
    }
    else 
      ((node_aux_vars)v->aux_vars)->taxon_id=-1;
  
  /*printf("diff time=%d\n", diff_time);*/
}

static void splits2tree_rec(const node v, const edge e, const list_node it, const list listsplits, const int_set taxa, hashtable2 edge2split, phylogenetic_tree T){
   
  list tomove; list_node ln;
  edge f, g; node w, n;
  int_set A, B, diff; 
  node_aux_vars node_vars;
  edge_aux_vars edge_vars;
  void* vp;
  /*time_t begin, end;*/

  tomove = new_list();
  
  for(f=v->first_edge; f; ){
    if(f!=e){
      A = get_A_split((split)(it->data));
      B = get_A_split((split) lookup_hashtable2(edge2split, (PTR_TYPE) f));

      if(subseteq_int_set(B, A)){
	splits2tree_rec(opposite(v,f), f, it, listsplits, taxa,
			edge2split, T);
        for(ln = tomove->head; ln; ln = ln->next)ln->data=NULL;
        del_list(tomove);
        tomove=NULL;
	return;
      }
      else if(subseteq_int_set(A, B)){
	append_list(tomove, (void*) f);
      }
    }
    if(f->u == v) f = f->u_next;
    else if (f->v == v) f = f->v_next;
    else assert(0);
  }
  
  /*begin=time(NULL);*/
  diff = diff_int_set(((node_aux_vars)(v->aux_vars))->taxaset,
		      get_A_split((split)(it->data)));
  /*end=time(NULL); diff_time+=difftime(end,begin);*/

  node_vars = new_node_aux_vars();
  assign_int_set(node_vars->taxaset, diff);
  del_int_set(diff); diff=NULL;

  n = new_node(T->G, node_vars);

  /*begin=time(NULL);*/
  diff = diff_int_set(((node_aux_vars)(v->aux_vars))->taxaset,
		    ((node_aux_vars)(n->aux_vars))->taxaset);
  /*end=time(NULL); diff_time+=difftime(end,begin);*/

  assign_int_set(((node_aux_vars)(v->aux_vars))->taxaset, diff);
  del_int_set(diff); diff=NULL;

  edge_vars = new_edge_aux_vars();
  edge_vars->wgt = ((split)(it->data))->wgt;
  f = new_edge(T->G, v, n, edge_vars);
  
  insert_hashtable2(edge2split, (PTR_TYPE) f, it->data);
  
  for(ln = tomove->head; ln; ln = ln->next){
    f = (edge) ln->data;
    w = opposite(v, f);
    edge_vars = new_edge_aux_vars();
    edge_vars->wgt = ((edge_aux_vars)(f->aux_vars))->wgt;
    g = new_edge(T->G, w, n, edge_vars);
    
    vp = lookup_hashtable2(edge2split, (PTR_TYPE) f);

    insert_hashtable2(edge2split, (PTR_TYPE) g, vp);

    /*del_edge_aux_vars((edge_aux_vars)(f->aux_vars));
      f->aux_vars = NULL;*/

    if(lookup_hashtable2(edge2split, (PTR_TYPE) f))
      set_value_null_hashtable2(edge2split, (PTR_TYPE) f);

    del_edge(T->G, f);
    f = NULL;
  }

  /*free up tomove list*/
  for(ln = tomove->head; ln; ln = ln->next)ln->data=NULL;
  del_list(tomove);
  tomove=NULL;
}