#include <arb_progress.h>
#include "gb_local.h"
#include <arb_strarray.h>
#include <set>
#include <limits.h>
#include <arb_global_defs.h>
#include <arb_strbuf.h>
#include <arb_diff.h>
#include <arb_defs.h>
#include <arb_match.h>
#include <arb_msg_nospam.h>
#include "TreeNode.h"

Include dependency graph for adtree.cxx:

Classes
struct	link_tree_data

struct	indexed_name

Macros
#define	GBT_PUT_DATA 1

#define	GBT_GET_SIZE 0

Functions
GBDATA *	GBT_get_tree_data (GBDATA *gb_main)

TreeNode *	GBT_remove_leafs (TreeNode tree, GBT_TreeRemoveType mode, const GB_HASH species_hash, int removed, int groups_removed)

int	get_tree_idx (GBDATA *gb_tree)

int	get_max_tree_idx (GBDATA *gb_treedata)

GBDATA *	get_tree_with_idx (GBDATA *gb_treedata, int at_idx)

GBDATA *	get_tree_infrontof_idx (GBDATA *gb_treedata, int infrontof_idx)

GBDATA *	get_tree_behind_idx (GBDATA *gb_treedata, int behind_idx)

GB_ERROR	set_tree_idx (GBDATA *gb_tree, int idx)

static GB_ERROR	reserve_tree_idx (GBDATA *gb_treedata, int idx)

static void	ensure_trees_have_order (GBDATA *gb_treedata)

static void	tree_set_default_order (GBDATA *gb_tree)

GB_ERROR	GBT_write_group_name (GBDATA gb_group_name, const char new_group_name, bool pedantic)

GB_ERROR	GBT_write_name_to_groupData (GBDATA gb_group, bool createNameEntry, const char new_group_name, bool pedantic)

static GB_ERROR	gbt_write_tree_nodes (GBDATA gb_tree, TreeNode node, long *startid)

static char *	gbt_write_tree_rek_new (const TreeNode node, char dest, long mode)

static GB_ERROR	gbt_write_tree (GBDATA gb_main, GBDATA gb_tree, const char tree_name, TreeNode tree)

GB_ERROR	GBT_write_tree (GBDATA gb_main, const char tree_name, TreeNode *tree)

GB_ERROR	GBT_overwrite_tree (GBDATA gb_tree, TreeNode tree)

static GB_ERROR	write_tree_remark (GBDATA gb_tree, const char remark)

GB_ERROR	GBT_write_tree_remark (GBDATA gb_main, const char tree_name, const char *remark)

GB_ERROR	GBT_log_to_tree_remark (GBDATA gb_tree, const char log_entry, bool stamp)

GB_ERROR	GBT_log_to_named_trees_remark (GBDATA gb_main, const char tree_name, const char *log_entry, bool stamp)

GB_ERROR	GBT_write_tree_with_remark (GBDATA gb_main, const char tree_name, TreeNode tree, const char remark)

static TreeNode *	gbt_read_tree_rek (char *data, long startid, GBDATA *gb_tree_nodes, TreeRoot troot, int size_of_tree, GB_ERROR &error)

static TreeNode *	read_tree_and_size_internal (GBDATA gb_tree, GBDATA gb_ctree, TreeRoot *troot, int node_count, GB_ERROR &error)

TreeNode *	GBT_read_tree_and_size (GBDATA gb_main, const char tree_name, TreeRoot troot, int tree_size)

TreeNode *	GBT_read_tree (GBDATA gb_main, const char tree_name, TreeRoot *troot)

size_t	GBT_count_leafs (const TreeNode *tree)

static GB_ERROR	gbt_invalid_because (const TreeNode tree, const char reason)

bool	has_son (const TreeNode father, const TreeNode son)

static GB_ERROR	gbt_is_invalid (bool is_root, const TreeNode *tree)

GB_ERROR	GBT_is_invalid (const TreeNode *tree)

static GB_ERROR	gbt_link_tree_to_hash_rek (TreeNode tree, link_tree_data ltd)

static GB_ERROR	GBT_link_tree_using_species_hash (TreeNode tree, bool show_status, GB_HASH species_hash, int zombies, int duplicates)

GB_ERROR	GBT_link_tree (TreeNode tree, GBDATA gb_main, bool show_status, int zombies, int duplicates)

void	GBT_unlink_tree (TreeNode *tree)

GBDATA *	GBT_find_tree (GBDATA gb_main, const char tree_name)

bool	is_tree (GBDATA *gb_tree)

GBDATA *	get_first_tree (GBDATA *gb_main)

GBDATA *	get_next_tree (GBDATA *gb_tree)

static GBDATA *	find_largest_tree (GBDATA *gb_main)

GBDATA *	GBT_tree_infrontof (GBDATA *gb_tree)

GBDATA *	GBT_tree_behind (GBDATA *gb_tree)

GBDATA *	GBT_find_top_tree (GBDATA *gb_main)

GBDATA *	GBT_find_bottom_tree (GBDATA *gb_main)

const char *	GBT_existing_tree (GBDATA gb_main, const char tree_name)

GBDATA *	GBT_find_next_tree (GBDATA *gb_tree)

const char *	GBT_get_tree_name (GBDATA *gb_tree)

GB_ERROR	GBT_check_tree_name (const char *tree_name)

const char *	GBT_name_of_largest_tree (GBDATA *gb_main)

const char *	GBT_name_of_bottom_tree (GBDATA *gb_main)

const char *	GBT_tree_info_string (GBDATA gb_main, const char tree_name, int maxTreeNameLen)

long	GBT_size_of_tree (GBDATA gb_main, const char tree_name)

void	GBT_get_tree_names (ConstStrArray &names, GBDATA *gb_main, bool sorted)

NOT4PERL GB_ERROR	GBT_move_tree (GBDATA gb_moved_tree, GBT_ORDER_MODE mode, GBDATA gb_target_tree)

static GBDATA *	get_source_and_check_target_tree (GBDATA gb_main, const char source_tree, const char *dest_tree, GB_ERROR &error)

static GBDATA *	copy_tree_container (GBDATA gb_source_tree, const char newName, GB_ERROR &error)

GB_ERROR	GBT_copy_tree (GBDATA gb_main, const char source_name, const char *dest_name)

GB_ERROR	GBT_rename_tree (GBDATA gb_main, const char source_name, const char *dest_name)

static GB_CSTR *	fill_species_name_array (GB_CSTR current, const TreeNode tree)

GB_CSTR *	GBT_get_names_of_species_in_tree (const TreeNode tree, size_t count)

static void	tree2newick (const TreeNode *tree, GBS_strstruct &out, NewickFormat format, int indent)

char *	GBT_tree_2_newick (const TreeNode *tree, NewickFormat format, bool compact)

Macro Definition Documentation

#define GBT_PUT_DATA 1

Definition at line 24 of file adtree.cxx.

Referenced by gbt_write_tree(), and gbt_write_tree_rek_new().

#define GBT_GET_SIZE 0

Definition at line 25 of file adtree.cxx.

Referenced by gbt_write_tree().

Function Documentation

GBDATA* GBT_get_tree_data ( GBDATA * gb_main )

Definition at line 27 of file adtree.cxx.

References GBT_find_or_create().

Referenced by awt_create_TREE_selection_list(), ensure_trees_have_order(), GBT_check_data(), GBT_find_bottom_tree(), GBT_find_top_tree(), GBT_find_tree(), GBT_get_tree_names(), gbt_write_tree(), get_first_tree(), reorder_trees_cb(), and transfer_tree().

TreeNode* GBT_remove_leafs	(	TreeNode *	tree,
		GBT_TreeRemoveType	mode,
		const GB_HASH *	species_hash,
		int *	removed,
		int *	groups_removed
	)

Remove leafs from given 'tree'.

Parameters

tree	tree from which species will be removed
mode	defines what to remove
species_hash	hash translation from leaf-name to species-dbnode (not needed if tree is linked; see GBT_link_tree)
removed	will be incremented for each removed leaf (if !NULp)
groups_removed	will be incremented for each removed group (if !NULp)

Returns: new root node

if 'species_hash' is not provided and tree is not linked, the function will silently act strange:

GBT_REMOVE_MARKED and GBT_REMOVE_UNMARKED will remove any leaf
GBT_REMOVE_ZOMBIES and GBT_KEEP_MARKED will remove all leafs

Definition at line 34 of file adtree.cxx.

References destroy(), TreeNode::fixDeletedSon(), TreeNode::forget_origin(), TreeNode::forget_relatives(), gb_assert, TreeNode::gb_node, GB_read_flag(), GBS_read_hash(), GBT_REMOVE_MARKED, GBT_REMOVE_UNMARKED, GBT_REMOVE_ZOMBIES, TreeNode::get_tree_root(), TreeNode::is_leaf(), TreeNode::is_root_node(), TreeNode::leftson, TreeNode::name, NULp, TreeNode::rightson, and tree.

Referenced by NT_alltree_remove_leafs(), and sq_calc_seq_quality_cb().

int get_tree_idx ( GBDATA * gb_tree )

inline

Definition at line 113 of file adtree.cxx.

References gb_assert, GB_entry(), and GB_read_int().

Referenced by ensure_trees_have_order(), GBT_copy_tree(), GBT_get_tree_names(), GBT_move_tree(), GBT_tree_behind(), GBT_tree_infrontof(), get_max_tree_idx(), get_tree_behind_idx(), get_tree_infrontof_idx(), get_tree_with_idx(), and tree_set_default_order().

int get_max_tree_idx ( GBDATA * gb_treedata )

inline

Definition at line 123 of file adtree.cxx.

References GB_child(), GB_nextChild(), and get_tree_idx().

Referenced by ensure_trees_have_order(), and tree_set_default_order().

GBDATA* get_tree_with_idx	(	GBDATA *	gb_treedata,
		int	at_idx
	)

inline

Definition at line 132 of file adtree.cxx.

References GB_child(), GB_nextChild(), get_tree_idx(), and NULp.

Referenced by GBT_find_top_tree(), and reserve_tree_idx().

GBDATA* get_tree_infrontof_idx	(	GBDATA *	gb_treedata,
		int	infrontof_idx
	)

inline

Definition at line 143 of file adtree.cxx.

References gb_assert, GB_child(), GB_nextChild(), get_tree_idx(), and NULp.

Referenced by GBT_find_bottom_tree(), and GBT_tree_infrontof().

GBDATA* get_tree_behind_idx	(	GBDATA *	gb_treedata,
		int	behind_idx
	)

inline

Definition at line 159 of file adtree.cxx.

References gb_assert, GB_child(), GB_nextChild(), get_tree_idx(), and NULp.

Referenced by GBT_find_top_tree(), and GBT_tree_behind().

GB_ERROR set_tree_idx	(	GBDATA *	gb_tree,
		int	idx
	)

inline

Definition at line 175 of file adtree.cxx.

References error(), GB_await_error(), GB_create(), GB_entry(), GB_INT, GB_write_int(), and NULp.

Referenced by ensure_trees_have_order(), GBT_copy_tree(), GBT_get_tree_names(), GBT_move_tree(), reserve_tree_idx(), and tree_set_default_order().

static GB_ERROR reserve_tree_idx	(	GBDATA *	gb_treedata,
		int	idx
	)

static

Definition at line 186 of file adtree.cxx.

References error(), get_tree_with_idx(), NULp, and set_tree_idx().

Referenced by GBT_copy_tree(), GBT_get_tree_names(), and GBT_move_tree().

static void ensure_trees_have_order ( GBDATA * gb_treedata )

static

Definition at line 196 of file adtree.cxx.

References error(), gb_assert, GB_await_error(), GB_child(), GB_get_father(), GB_get_root(), GB_INT, gb_main, GB_nextChild(), GB_read_int(), GB_search(), GB_write_int(), GBK_terminatef(), GBT_get_tree_data(), get_max_tree_idx(), get_tree_idx(), NULp, and set_tree_idx().

Referenced by GBT_find_bottom_tree(), GBT_find_top_tree(), GBT_get_tree_names(), GBT_move_tree(), GBT_tree_behind(), and GBT_tree_infrontof().

static void tree_set_default_order ( GBDATA * gb_tree )

static

Definition at line 220 of file adtree.cxx.

References GB_get_father(), get_max_tree_idx(), get_tree_idx(), and set_tree_idx().

Referenced by gbt_write_tree().

GB_ERROR GBT_write_group_name	(	GBDATA *	gb_group_name,
		const char *	new_group_name,
		bool	pedantic
	)

Definition at line 230 of file adtree.cxx.

References GBS_strstruct::cat(), GBS_strstruct::cat_sQuoted(), error(), gb_assert, GB_GROUP_NAME_MAX, GB_read_key_pntr(), GB_warningf(), GB_write_string(), GBS_global_string(), GBS_static_string(), GBS_strstruct::get_data(), KEELED_INDICATOR, label, GBS_strstruct::nprintf(), NULp, and parse_treelabel().

Referenced by gbt_read_tree_rek(), GBT_write_name_to_groupData(), gbt_write_tree_nodes(), FoundGroup::rename_by_ACI(), and SpecSetRegistry::write_node_information().

GB_ERROR GBT_write_name_to_groupData	(	GBDATA *	gb_group,
		bool	createNameEntry,
		const char *	new_group_name,
		bool	pedantic
	)

Definition at line 325 of file adtree.cxx.

References GB_await_error(), GB_FIND, GB_search(), GB_STRING, and GBT_write_group_name().

Referenced by AWT_graphic_tree::toggle_group(), and GroupBuilder::update_group().

static GB_ERROR gbt_write_tree_nodes	(	GBDATA *	gb_tree,
		TreeNode *	node,
		long *	startid
	)

static

Definition at line 332 of file adtree.cxx.

References error(), GB_await_error(), GB_child(), GB_clear_user_flag(), GB_create_container(), GB_delete(), GB_FIND, GB_have_error(), GB_INT, GB_nextChild(), TreeNode::gb_node, GB_read_key_pntr(), GB_search(), GB_STRING, GB_USERFLAG_GHOSTNODE, GB_write_int(), GBT_write_group_name(), GBT_write_int(), TreeNode::is_leaf(), TreeNode::keeledStateInfo(), TreeNode::name, and NULp.

Referenced by gbt_write_tree().

static char* gbt_write_tree_rek_new	(	const TreeNode *	node,
		char *	dest,
		long	mode
	)

static

Definition at line 386 of file adtree.cxx.

References buffer, gb_assert, GBT_PUT_DATA, TreeNode::get_remark(), TreeNode::has_no_remark(), TreeNode::is_leaf(), TreeNode::leftlen, TreeNode::name, and TreeNode::rightlen.

Referenced by gbt_write_tree().

static GB_ERROR gbt_write_tree	(	GBDATA *	gb_main,
		GBDATA *	gb_tree,
		const char *	tree_name,
		TreeNode *	tree
	)

static

writes a tree to the database.

If tree is loaded by function GBT_read_tree(..) then 'tree_name' should be NULp else 'gb_tree' should be set to NULp

To copy a tree call GBT_copy_tree() or copy_tree_container() or set recursively all tree->gb_node variables to zero (that unlinks the tree),

Definition at line 441 of file adtree.cxx.

References error(), GB_allow_compression(), gb_assert, GB_await_error(), GB_CREATE_CONTAINER, GB_delete(), GB_entry(), GB_nextEntry(), GB_raise_user_flag(), GB_search(), GB_user_flag(), GB_USERFLAG_GHOSTNODE, GBS_global_string(), GBT_check_tree_name(), GBT_GET_SIZE, GBT_get_tree_data(), GBT_PUT_DATA, GBT_write_int(), GBT_write_string(), gbt_write_tree_nodes(), gbt_write_tree_rek_new(), NULp, and tree_set_default_order().

Referenced by GBT_overwrite_tree(), and GBT_write_tree().

GB_ERROR GBT_write_tree	(	GBDATA *	gb_main,
		const char *	tree_name,
		TreeNode *	tree
	)

Definition at line 523 of file adtree.cxx.

References gbt_write_tree(), and NULp.

Referenced by ARB_main(), compress_sequence_tree(), di_calculate_tree_cb(), GBT_commit_rename_session(), GBT_write_tree_with_remark(), main(), NT_alltree_remove_leafs(), and AP_tree_root::saveToDB().

GB_ERROR GBT_overwrite_tree	(	GBDATA *	gb_tree,
		TreeNode *	tree
	)

Definition at line 526 of file adtree.cxx.

References GB_get_root(), gbt_write_tree(), and NULp.

Referenced by adjustTreeRoot(), NTREE_move_tree_info(), and ARB_seqtree_root::saveToDB().

static GB_ERROR write_tree_remark	(	GBDATA *	gb_tree,
		const char *	remark
	)

static

Definition at line 530 of file adtree.cxx.

References GBT_write_string().

Referenced by GBT_log_to_tree_remark(), and GBT_write_tree_remark().

GB_ERROR GBT_write_tree_remark	(	GBDATA *	gb_main,
		const char *	tree_name,
		const char *	remark
	)

Definition at line 533 of file adtree.cxx.

References GBT_find_tree(), and write_tree_remark().

Referenced by di_calculate_tree_cb(), GBT_write_tree_with_remark(), and main().

GB_ERROR GBT_log_to_tree_remark	(	GBDATA *	gb_tree,
		const char *	log_entry,
		bool	stamp
	)

append 'log_entry' to tree comment

Parameters

gb_tree	the tree
log_entry	text to append
stamp	true -> prefix date before 'log_entry'

Returns: error in case of failure

Definition at line 537 of file adtree.cxx.

References error(), GB_await_error(), GB_have_error(), GBS_log_action_to(), GBT_read_char_pntr(), NULp, and write_tree_remark().

Referenced by adjustTreeRoot(), GBT_log_to_named_trees_remark(), and NTREE_move_tree_info().

GB_ERROR GBT_log_to_named_trees_remark	(	GBDATA *	gb_main,
		const char *	tree_name,
		const char *	log_entry,
		bool	stamp
	)

append 'log_entry' to tree comment

Parameters

gb_main	database
tree_name	name of tree
log_entry	text to append
stamp	true -> prefix date before 'log_entry'

Returns: error in case of failure

Definition at line 556 of file adtree.cxx.

References GBS_global_string(), GBT_find_tree(), and GBT_log_to_tree_remark().

Referenced by di_calculate_tree_cb(), and main().

GB_ERROR GBT_write_tree_with_remark	(	GBDATA *	gb_main,
		const char *	tree_name,
		TreeNode *	tree,
		const char *	remark
	)

Definition at line 570 of file adtree.cxx.

References error(), GBT_write_tree(), and GBT_write_tree_remark().

Referenced by create_consense_tree_cb(), save_tree_as_newick(), and TREE_load_to_db().

static TreeNode* gbt_read_tree_rek	(	char **	data,
		long *	startid,
		GBDATA **	gb_tree_nodes,
		TreeRoot *	troot,
		int	size_of_tree,
		GB_ERROR &	error
	)

static

static TreeNode* read_tree_and_size_internal	(	GBDATA *	gb_tree,
		GBDATA *	gb_ctree,
		TreeRoot *	troot,
		int	node_count,
		GB_ERROR &	error
	)

static

Definition at line 691 of file adtree.cxx.

References ARB_calloc(), error(), TreeNode::father, gb_assert, GB_await_error(), GB_delete(), GB_entry(), GB_get_root(), gb_main, GB_nextEntry(), TreeNode::gb_node, GB_read_int(), GB_read_key_pntr(), GB_read_string(), GBS_global_string(), GBT_message(), gbt_read_tree_rek(), TreeNode::has_group_info(), implicated, TreeNode::is_normal_group(), TreeNode::keelTarget(), TreeNode::name, NULp, and TreeRoot::set_bootstrap_seen().

Referenced by GBT_read_tree_and_size().

TreeNode* GBT_read_tree_and_size	(	GBDATA *	gb_main,
		const char *	tree_name,
		TreeRoot *	troot,
		int *	tree_size
	)

Loads a tree from DB into any user defined structure.

Parameters

gb_main	DB root node
tree_name	is the name of the tree in the db
troot	constructs the tree-node instances
tree_size	if specified -> will be set to "size of tree" (aka number of leafs minus 1)

Returns

NULp if any error occurs (which is exported then)
root of loaded tree (dynamic type depends on 'nodeFactory')

Definition at line 770 of file adtree.cxx.

References TreeNode::announce_tree_constructed(), TreeRoot::delete_by_node(), error(), gb_assert, GB_entry(), GB_export_errorf(), GB_FIND, GB_read_int(), GB_search(), GBT_check_tree_name(), GBT_find_tree(), TreeNode::is_normal_group(), NULp, read_tree_and_size_internal(), and tree.

Referenced by GBT_read_tree(), and MatrixOrder::MatrixOrder().

TreeNode* GBT_read_tree	(	GBDATA *	gb_main,
		const char *	tree_name,
		TreeRoot *	troot
	)

See also: GBT_read_tree_and_size()

Definition at line 837 of file adtree.cxx.

References GBT_read_tree_and_size(), and NULp.

Referenced by create_consense_tree_cb(), di_calculate_compressed_matrix_cb(), DI_MATRIX::extract_from_tree(), GBT_commit_rename_session(), GBT_compress_sequence_tree2(), get_cached_taxonomy(), load_and_add_tree(), ARB_seqtree_root::loadFromDB(), main(), mark_action(), NT_alltree_remove_leafs(), PVP_calculate(), sort_tree_by_other_tree(), sq_calc_seq_quality_cb(), TREE_write_Newick(), and TREE_write_XML().

size_t GBT_count_leafs ( const TreeNode * tree )

Definition at line 842 of file adtree.cxx.

References TreeNode::is_leaf().

Referenced by ARB_main(), count_nodes(), DeconstructedTree::deconstruct_weighted(), export_tree_node_print_xml(), GBT_get_names_of_species_in_tree(), GBT_link_tree_using_species_hash(), get_cached_taxonomy(), and AP_pos_var::retrieve().

static GB_ERROR gbt_invalid_because	(	const TreeNode *	tree,
		const char *	reason
	)

static

Definition at line 849 of file adtree.cxx.

References GBS_global_string().

Referenced by gbt_is_invalid(), and GBT_is_invalid().

bool has_son	(	const TreeNode *	father,
		const TreeNode *	son
	)

inline

Definition at line 853 of file adtree.cxx.

References TreeNode::is_leaf(), TreeNode::leftson, and TreeNode::rightson.

Referenced by gbt_is_invalid().

static GB_ERROR gbt_is_invalid	(	bool	is_root,
		const TreeNode *	tree
	)

static

Definition at line 857 of file adtree.cxx.

References error(), TreeNode::father, gbt_invalid_because(), has_son(), TreeNode::is_leaf(), TreeNode::leftson, NULp, TreeNode::rightson, and tree.

Referenced by GBT_is_invalid().

GB_ERROR GBT_is_invalid ( const TreeNode * tree )

Definition at line 880 of file adtree.cxx.

References TreeNode::father, gbt_invalid_because(), gbt_is_invalid(), and TreeNode::is_leaf().

Referenced by di_calculate_tree_cb().

static GB_ERROR gbt_link_tree_to_hash_rek	(	TreeNode *	tree,
		link_tree_data *	ltd
	)

static

Definition at line 897 of file adtree.cxx.

References link_tree_data::duplicates, error(), TreeNode::gb_node, GBS_read_hash(), GBS_write_hash(), TreeNode::is_leaf(), TreeNode::name, NULp, link_tree_data::progress, link_tree_data::seen_species, link_tree_data::species_hash, and link_tree_data::zombies.

Referenced by GBT_link_tree_using_species_hash().

static GB_ERROR GBT_link_tree_using_species_hash	(	TreeNode *	tree,
		bool	show_status,
		GB_HASH *	species_hash,
		int *	zombies,
		int *	duplicates
	)

static

Definition at line 921 of file adtree.cxx.

References link_tree_data::duplicates, error(), GB_IGNORE_CASE, GBS_create_hash(), GBS_free_hash(), GBT_count_leafs(), gbt_link_tree_to_hash_rek(), NULp, link_tree_data::progress, link_tree_data::seen_species, link_tree_data::species_hash, and link_tree_data::zombies.

Referenced by GBT_link_tree().

GB_ERROR GBT_link_tree	(	TreeNode *	tree,
		GBDATA *	gb_main,
		bool	show_status,
		int *	zombies,
		int *	duplicates
	)

Link a given tree to the database. That means that for all tips the member 'gb_node' is set to the database container holding the species data.

Parameters

tree	which will be linked to DB
gb_main	DB root node
show_status	show a progress indicator?
zombies	if specified -> set to number of zombies (aka non-existing species) in tree
duplicates	if specified -> set to number of duplicated species in tree