/*
This file converts a tree into a set of bipartitions.
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<tree2splits.h>
#include<split.h>
#include<assert.h>
#include<stdio.h>
#include<ugraph_aux_vars.h>
#include<time.h>

/* extern int global_probelength; */
/* int uniontime, diff_time, assigntime, deltime; */

static int_set  tree2splits_rec(const node v, const edge e, const phylogenetic_tree T, const int_set taxa, list listsplits);

int
tree2splits(const phylogenetic_tree T, list listsplits)
{

	node            n;
	node            root;
	int_set         tempset;
	int_set         taxa;

	/* uniontime=0; diff_time=0; assigntime=0; deltime=0; */
	taxa = new_int_set(32);

	assert(size_list(listsplits) == 0);

	/* insert all leaves into taxa */
	for (n = T->G->first_node; n; n = n->next)
		if (n->degree == 1 && ((node_aux_vars) n->aux_vars)->taxon_id != -1)
			insert_int_set(taxa, ((node_aux_vars) n->aux_vars)->taxon_id);

	/* choose arbitrary labeled root */
	for (n = T->G->first_node; n; n = n->next)
		if (n->degree == 1 && ((node_aux_vars) n->aux_vars)->taxon_id != -1) {
			root = n;
			break;
		}
	if (!root)
		return 0;
	tempset = tree2splits_rec(root, (edge) 0, T, taxa, listsplits);
	del_int_set(tempset);
	del_int_set(taxa);
	tempset = NULL;
	taxa = NULL;

	/*
	 * printf("union=%d, diff=%d, assign=%d\n",
	 * uniontime,diff_time,assigntime);
	 */

	return size_list(listsplits);
}

static          int_set
tree2splits_rec(const node v, const edge e, const phylogenetic_tree T, const int_set taxa, list listsplits)
{

	/* data */
	edge            f;
	int_set         f_taxa;
	split           s;
	int_set         difftaxa, uniontaxa;
	/* time_t begin, end; */

	/* code */
	int_set         e_taxa = new_int_set(32);

	/* begin=time(NULL); */
	assign_int_set(e_taxa, ((node_aux_vars) v->aux_vars)->taxaset);
	/* end=time(NULL); assigntime+=difftime(end, begin); */

	for (f = v->first_edge; f;) {
		if (f != e) {
			f_taxa = tree2splits_rec(opposite(v, f), f, T, taxa, listsplits);
			s = new_split();

			/* begin=time(NULL); */
			difftaxa = diff_int_set(taxa, f_taxa);
			/* end=time(NULL); diff_time+=difftime(end, begin); */

			set_split(s, f_taxa, difftaxa, ((edge_aux_vars) f->aux_vars)->wgt);
			append_list(listsplits, s);

			/* begin=time(NULL); */
			uniontaxa = union_int_set(e_taxa, f_taxa);
			/* end=time(NULL); uniontime+=difftime(end,begin); */

			/* begin=time(NULL); */
			assign_int_set(e_taxa, uniontaxa);
			/* end=time(NULL); assigntime+=difftime(end,begin); */

			del_int_set(uniontaxa);
			uniontaxa = NULL;
			del_int_set(difftaxa);
			del_int_set(f_taxa);
			difftaxa = NULL;
			f_taxa = NULL;
		}
		if (f->u == v)
			f = f->u_next;
		else if (f->v == v)
			f = f->v_next;
		else
			assert(0);
	}
	return e_taxa;
}