/*
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;
}