/*
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 Read rooted tree */
int
read_rooted_tree(phylogenetic_tree T, char **num_to_name,
		 char *newick_tree, hashtable name_to_num);

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

/*
 * ! \brief Prints unrooted 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 Set the taxa_size variables of each node appropriately */
void            set_subtree_edgelens(phylogenetic_tree T);

/*
 * ! \brief Set the taxa_size variables of each node appropriately --- for
 * rooted tree
 */
void            set_rooted_subtree_sizes(phylogenetic_tree T);

/*
 * ! \brief Set the sum_edge_lens variables of each node appropriately ---
 * for rooted tree
 */
void            set_rooted_subtree_edgelens(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);

/* ! \brief Contract all edges of length at most (including) l */
void            contract_edgelens(phylogenetic_tree T, float l);

/* ! \brief Return number of degree two nodes */
int             num_degreetwo_nodes(phylogenetic_tree T);

/* ! \brief Root tree on edge e */
void            reroot_phylo_tree(phylogenetic_tree T, edge e);

#endif