/*
This file implements a phylogenetic tree 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
*/

/*! \file phylo_tree.h
\brief Contains definition for a phylogenetic tree structure
*/

#ifndef PHYLO_TREE
#define PHYLO_TREE

#include<ugraph.h>
#include<hashtable.h>
#include<int_set.h>
#include<list.h>

/*! \brief A phylogenetic_tree is just a pointer to a phylogenetic_tree_struct */
typedef struct phylogenetic_tree_struct* phylogenetic_tree;

/*!\brief Representation of a phylogenetic tree.
*/
struct phylogenetic_tree_struct {
 
  /*!Undirected graph storing the unrooted tree structure*/
  ugraph G;
 
  /*!Number of leaves in the tree*/
  int num_leaves;
};

/*! \brief Create a new phylogenetic tree in constant time.*/
phylogenetic_tree new_phylogenetic_tree();

/*! \brief Delete the phylogenetic tree T in linear time.*/
void del_phylogenetic_tree(phylogenetic_tree T);

void remove_2degreeinternal_tree(phylogenetic_tree T);

/*! \brief Print the adjacency list representation of the phylogenetic tree in
linear time.*/
void print_phylo_tree(phylogenetic_tree T, char** num_to_name);

/*! \brief Reads in a tree in newick format into an indirected graph in linear time. The tree is built from bottom up and is read in as a rooted tree. After
the read is complete, the root and any vertices of degree two are deleted.
If name_to_num is empty then num_to_name table is filled with the tree
taxa names. Otherwise the name_to_num is used to fill up num_to_name.
*/
int read_tree(phylogenetic_tree T, char** num_to_name, char* newick_tree, 
	      hashtable name_to_num);

/*! \brief Prints tree to the tree_string. (tree_string must be initialized
  to all NULLs.) */
void print_tree(phylogenetic_tree T, char** num_to_name, char* tree_string, short do_wgts);

/* \brief Compute the tree restricted to the set taxa*/
void restrict_tree(phylogenetic_tree T, int_set taxa);

/* \brief Set the taxa_size variables of each node appropriately */
void set_subtree_sizes(phylogenetic_tree T);

/* \brief Copy tree src into dest. dest must not be an empty pointer but 
   contain an empty tree*/
void assign_tree(phylogenetic_tree dest, phylogenetic_tree src);

/* \brief Compute a tree from the uniform random distribution*/
void uniform_random_tree(int num_leaves, phylogenetic_tree base_tree);

/* \brief Randomly refine T by replacing each unresolved node with a subtree
   from the uniform distribution */
void random_refine(phylogenetic_tree T);

/* \brief Randomly refine T as above but assigning 0 edge length to new edges introduced*/
void random_refine_edgelens(phylogenetic_tree T);

#endif