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