Tree Templates
[CORELIB]

Collaboration diagram for Tree Templates:


Classes

struct  CBioTreeFeaturePair
 Tree node feature pair (id to string). More...
class  CBioTreeFeatureList
 Features storage for the bio tree node. More...
struct  CBioTreeEmptyNodeData
 Basic node data structure used by BioTreeBaseNode. More...
class  BioTreeBaseNode< TNodeData, TNodeFeatures >
 Basic data contained in every bio-tree node. More...
class  CBioTreeFeatureDictionary
 Feature dictionary. More...
class  CBioTree< TBioNode >
 Basic tree structure for biological applications. More...
class  CTree2TreeFunc< TDstTreeNode, TSrcTreeNode, TNodeConvFunc >
 Visitor functor to convert one tree to another. More...
class  CBioTreeConvert2ContainerFunc< TBioTreeContainer, TDynamicTree >
 Visitor functor to convert dynamic tree nodes to ASN.1 BioTree container. More...
class  CTaxon1NodeConvertVisitor< TITaxon4Each, TITaxon1Node, TITreeIterator, TBioTreeContainer >
 Taxon1 tree visitor functor. More...
class  CTaxon1ConvertToBioTreeContainer< TBioTreeContainer, TTaxon1, TITaxon1Node, TITreeIterator >
class  CTreeParentTraceFunc< TTreeNode, TTraceContainer >
 Functor to trace node pointers to root (TreeForEachParent). More...
class  CTreePrintFunc< TTreeNode, TConverter >
 Tree print functor used as a tree traversal payload. More...
class  CTreeIdToSetFunc< TTreeNode, TBackInsert >
 Functor to trace node pointers to root and create set of parents (TreeForEachParent). More...
class  CTreeSet2NodeListFunc< TTreeNode, TSet, TNodeList >
 Functor to convert tree to a nodelist by the set pattern. More...
class  CTreeNonRedundantSet< TNode, TSet, TNodeList >
 Class-algorithm to compute Non Redundant Set. More...
class  CTreeMinimalSet< TNode, TSet, TNodeList >
 Functor takes a single nodelist as an argument and tries to push that nodelist as high as it can. More...
class  CNodesToBitset< TNode, TSet, TNodeList >
 Utility to join to node lists according to a set of ids. More...
class  CTreeNodesAnd< TNode, TSet, TNodeList >
 Node list AND (set intersection). More...
class  CTreeNodesOr< TNode, TSet, TNodeList >
 Node list OR (set union). More...
class  CDefaultNodeKeyGetter< TValue >
 Default key getter for CTreeNode. More...
struct  CTreeNode< TValue, TKeyGetter >
 definition of a Culling tree More...
class  CPairNodeKeyGetter< TNode >
 Default key getter for pair-node (id + value). More...
struct  CTreePair< TId, TValue >
 Node data template for id-value trees. More...

Typedefs

typedef unsigned int TBioTreeFeatureId
 Feature Id.
typedef unsigned int TBioTreeNodeId
 Tree node id. Every node has its unique id in the tree.
typedef CBioTree< BioTreeBaseNode<
CBioTreeEmptyNodeData, CBioTreeFeatureList > > 		CBioTreeDynamic
 Bio tree without static elements.

Enumerations

enum  ETreeTraverseCode { eTreeTraverse, eTreeTraverseStop, eTreeTraverseStepOver }
 Tree traverse code returned by the traverse predicate function. More...

Functions

CNcbiOstream & operator<< (CNcbiOstream &os, const CBioTreeDynamic &tree)
 Newick format output.
void WriteNexusTree (CNcbiOstream &os, const CBioTreeDynamic &tree, const string &tree_name="the_tree")
 Nexus format output (Newick with some stuff around it).
void PrintNode (CNcbiOstream &os, const CBioTreeDynamic &tree, const CBioTreeDynamic::TBioTreeNode &node)
 Newick but without the terminal ';'.
template<class TDynamicTree, class TSrcBioTree, class TNodeConvFunc>
void BioTreeConvert2Dynamic (TDynamicTree &dyn_tree, const TSrcBioTree &bio_tree, TNodeConvFunc node_conv)
 Convert biotree to dynamic tree using a node converter.
template<class TDynamicTree, class TTreeNode, class TNodeConvFunc>
void TreeConvert2Dynamic (TDynamicTree &dyn_tree, const TTreeNode *src_tree, TNodeConvFunc node_conv)
 Convert CTreeNode<> to dynamic tree using a node converter.
template<class TDynamicTree, class TTreeNode, class TNodeConvFunc>
TTreeNode * DynamicConvert2Tree (TDynamicTree &dyn_tree, TNodeConvFunc node_conv, TTreeNode *&dst_node)
 Convert dynamic tree to CTreeNode<>, returned CTReeNode<> to be deleted by caller.
template<class TBioTreeContainer, class TDynamicTree>
void BioTreeConvert2Container (TBioTreeContainer &tree_container, const TDynamicTree &dyn_tree)
 Convert Dynamic tree to ASN.1 BioTree container.
template<class TBioTreeContainer, class TDynamicTree>
void BioTreeConvertContainer2Dynamic (TDynamicTree &dyn_tree, const TBioTreeContainer &tree_container)
 Convert ASN.1 BioTree container to dynamic tree.
template<class TBioTreeContainer>
void BioTreeAddFeatureToDictionary (TBioTreeContainer &tree_container, unsigned int feature_id, const string &feature_name)
template<class TTreeNode, class TCompFun>
bool TreeCompare (const TTreeNode &tree1, const TTreeNode &tree2, TCompFun func)
 Compare two trees using comparison functor where order of children matters.
template<class TTreeNode, class TFunc>
TFunc TreeForEachParent (const TTreeNode &tree_node, TFunc func, bool skip_self=false)
 Visit every parent of the specified node.
template<class TTreeNode, class TTraceContainer>
void TreeTraceToRoot (const TTreeNode &tree_node, TTraceContainer &trace)
 Trace from the specified node to to the tree root.
template<class TTreeNode>
void TreeReRoot (TTreeNode &new_root_node)
 Change tree root (tree rotation).
template<class TTreeNode>
const TTreeNode * TreeFindCommonParent (const TTreeNode &tree_node_a, const TTreeNode &tree_node_b)
 Check if two nodes have the same common root.
template<class TTreeNode, class TConverter>
void TreePrint (CNcbiOstream &os, const TTreeNode &tree_node, TConverter conv, bool print_ptr=false)
 Tree printing (use for debugging purposes).
template<class TPairTree, class TValue>
const TPairTree * PairTreeBackTraceNode (const TPairTree &tr, const TValue &search_id)
 Algorithm to to search for a node with specified id.
template<class TPairTree, class TPathList>
const TPairTree * PairTreeTraceNode (const TPairTree &tr, const TPathList &node_path)
 Algorithm to trace the pair tree and find specified leaf along the node path.
template<class TNodeListIt, class TBackInsert>
void TreeListToSet (TNodeListIt node_list_first, TNodeListIt node_list_last, TBackInsert back_ins)
 Convert list of node pointers to set of ids Input set is represented by input forward iterators Output set is a back insert iterator.
template<class TNodeList, class TBackInsert>
void TreeListToSet (const TNodeList &node_list, TBackInsert back_ins)
 Convert list of node pointers to set of ids.
template<class TNode, class TBackInsert>
void TreeMakeParentsSet (const TNode &tree_node, TBackInsert back_ins)
 Traverses all ancestors and add their ids to a set.
template<class TNode, class TBackInsert>
void TreeMakeSet (const TNode &tree_node, TBackInsert back_ins)
 Create set of all sub-nodes (recursively).
template<class TNode, class TBackInsert>
void TreeMakeSubNodesSet (const TNode &tree_node, TBackInsert back_ins)
 Create set of all immediate sub-nodes (one level down from the root).
template<class TNode, class TSet, class TNodeList>
void TreeSetToNodeList (const TNode &tree_node, const TSet &node_set, TNodeList &nlist)
 Convert set of node ids to list of nodes.
template<class TTreeNode, class Fun>
Fun TreeDepthFirstTraverse (TTreeNode &tree_node, Fun func)
 Depth-first tree traversal algorithm.
template<class TTreeNode, class Fun>
Fun TreeBreadthFirstTraverse (TTreeNode &tree_node, Fun func)
 Breadth-first tree traversal algorithm.
 CTreeNode::CTreeNode (const TValue &value=TValue())
 Tree node construction.
 CTreeNode::~CTreeNode ()
 CTreeNode::CTreeNode (const TTreeType &tree)
CTreeNode & CTreeNode::operator= (const TTreeType &tree)
void CTreeNode::CopyFrom (const TTreeType &tree)
void CTreeNode::RemoveNode (TTreeType *subnode)
 Remove subnode of the current node.
void CTreeNode::RemoveNode (TNodeList_I it)
 Remove subnode of the current node.
TTreeType * CTreeNode::DetachNode (TTreeType *subnode)
 Remove the subtree from the tree without freeing it.
TTreeType * CTreeNode::DetachNode (TNodeList_I it)
 Remove the subtree from the tree without freeing it.
void CTreeNode::AddNode (TTreeType *subnode)
 Add new subnode.
TTreeType * CTreeNode::AddNode (const TValue &val=TValue())
 Add new subnode whose value is (a copy of) val.
void CTreeNode::MoveSubnodes (TTreeType *src_tree_node)
 Remove all subnodes from the source node and attach them to the current tree (node).
void CTreeNode::InsertNode (TNodeList_I it, TTreeType *subnode)
 Insert new subnode before the specified location in the subnode list.
void CTreeNode::RemoveAllSubNodes (EDeletePolicy del=eDelete)
 Remove all immediate subnodes.
const TTreeType * CTreeNode::GetRoot (void) const
 Get the topmost node.
bool CTreeNode::IsParent (const TTreeType &tree_node) const
 Check if node is a direct or indirect parent of this node.
void CTreeNode::FindNodes (const TKeyList &node_path, TNodeList *res)
 Find tree nodes corresponding to the path from the top.
TTreeType * CTreeNode::FindOrCreateNode (const TKeyList &node_path)
 Find or create tree node corresponding to the path from the top.
void CTreeNode::FindNodes (const TKeyList &node_path, TConstNodeList *res) const
 Find tree nodes corresponding to the path from the top.
const TTreeType * CTreeNode::FindSubNode (const TKeyType &key) const
 Non recursive linear scan of all subnodes, with key comparison.
TTreeType * CTreeNode::FindSubNode (const TKeyType &key)
 Non recursive linear scan of all subnodes, with key comparison.
const TTreeType * CTreeNode::FindNode (const TKeyType &key, TNodeSearchMode sflag=eImmediateAndTop) const
 Search for node.

Typedef Documentation

typedef CBioTree<BioTreeBaseNode<CBioTreeEmptyNodeData, CBioTreeFeatureList> > CBioTreeDynamic
 

Bio tree without static elements.

Everything is stored as features.

Definition at line 468 of file bio_tree.hpp.

typedef unsigned int TBioTreeFeatureId
 

Feature Id.

All bio tree dynamic features are encoded by feature ids. Ids are shared among the tree nodes. Feature id to feature name map is supported by the tree.

Definition at line 60 of file bio_tree.hpp.

typedef unsigned int TBioTreeNodeId
 

Tree node id. Every node has its unique id in the tree.

Definition at line 63 of file bio_tree.hpp.

Enumeration Type Documentation

enum ETreeTraverseCode
 

Tree traverse code returned by the traverse predicate function.

Enumerator:
eTreeTraverse  Keep traversal.
eTreeTraverseStop  Stop traversal (return form algorithm).
eTreeTraverseStepOver  Do not traverse current node (pick the next one).

Definition at line 390 of file ncbi_tree.hpp.

Function Documentation

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::TTreeType * CTreeNode< TValue, TKeyGetter >::AddNode (  const TValue &  val = TValue()  )  [inherited]
 

Add new subnode whose value is (a copy of) val.

Parameters:
val value reference
Returns:
pointer to new subtree

Reimplemented in CBioTree< TBioNode >::CBioNode.

Definition at line 679 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::AddNode().

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::AddNode (  TTreeType *  subnode  )  [inherited]
 

Add new subnode.

Parameters:
subnode subnode pointer

Definition at line 670 of file ncbi_tree.hpp.

References _ASSERT, CTreeNode< TValue, TKeyGetter >::m_Nodes, and CTreeNode< TValue, TKeyGetter >::SetParent().

Referenced by AddFunc_Arg(), CTreeNode< TValue, TKeyGetter >::AddNode(), CMenuItem::AddSubItem(), CClusterer::ComputeClusters(), CTreeNode< TValue, TKeyGetter >::CopyFrom(), CTreeNode< TValue, TKeyGetter >::MoveSubnodes(), newickparse(), CDistMethods::NjTree(), QTreeAddNode(), s_ConvertFastMeTree(), and CPhyloRectCladogram::x_DrawTree().

template<class TBioTreeContainer>
void BioTreeAddFeatureToDictionary (  TBioTreeContainer &  tree_container,
unsigned int  feature_id,
const string &  feature_name
) 
 

Definition at line 547 of file bio_tree_conv.hpp.

Referenced by CTaxon1ConvertToBioTreeContainer< TBioTreeContainer, TTaxon1, TITaxon1Node, TITreeIterator >::operator()().

template<class TBioTreeContainer, class TDynamicTree>
void BioTreeConvert2Container (  TBioTreeContainer &  tree_container,
const TDynamicTree &  dyn_tree
) 
 

Convert Dynamic tree to ASN.1 BioTree container.

Definition at line 285 of file bio_tree_conv.hpp.

References CBioTreeFeatureDictionary::GetFeatureDict(), ITERATE, and TreeDepthFirstTraverse().

Referenced by CPhyTreeView::CommitTheChanges(), CPhyTreeView::GetSelection(), CGuideTree::GetSerialTree(), CGuideTree::WriteTree(), and CGuideTree::WriteTreeInNetcache().

template<class TDynamicTree, class TSrcBioTree, class TNodeConvFunc>
void BioTreeConvert2Dynamic (  TDynamicTree &  dyn_tree,
const TSrcBioTree &  bio_tree,
TNodeConvFunc  node_conv
) 
 

Convert biotree to dynamic tree using a node converter.

Definition at line 128 of file bio_tree_conv.hpp.

References CTree2TreeFunc< TDstTreeNode, TSrcTreeNode, TNodeConvFunc >::GetTreeNode(), and TreeDepthFirstTraverse().

template<class TBioTreeContainer, class TDynamicTree>
void BioTreeConvertContainer2Dynamic (  TDynamicTree &  dyn_tree,
const TBioTreeContainer &  tree_container
) 
 

Convert ASN.1 BioTree container to dynamic tree.

Definition at line 329 of file bio_tree_conv.hpp.

References ITERATE, and CBioTreeFeatureDictionary::Register().

Referenced by CGuideTree::CGuideTree(), CPhyloPhylipReader::GetTree(), CGuideTreeCalc::GetTree(), CPhyTreeView::OnProjectChanged(), and CPhyExportJob::Run().

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::CopyFrom (  const TTreeType &  tree  )  [protected, inherited]
 

Definition at line 611 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::AddNode(), CTreeNode< TValue, TKeyGetter >::CTreeNode(), ITERATE, and CTreeNode< TValue, TKeyGetter >::m_Nodes.

Referenced by CTreeNode< TValue, TKeyGetter >::CTreeNode(), and CTreeNode< TValue, TKeyGetter >::operator=().

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::CTreeNode (  const TTreeType &  tree  )  [inherited]
 

Definition at line 589 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::CopyFrom().

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::CTreeNode (  const TValue &  value = TValue()  )  [inherited]
 

Tree node construction.

Parameters:
value - node value

Definition at line 572 of file ncbi_tree.hpp.

Referenced by CTreeNode< TValue, TKeyGetter >::CopyFrom().

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::TTreeType * CTreeNode< TValue, TKeyGetter >::DetachNode (  TNodeList_I  it  )  [inherited]
 

Remove the subtree from the tree without freeing it.

If subnode is not connected directly with the current node the call has no effect. The caller is responsible for deletion of the returned subtree.

Parameters:
subnode direct subnode pointer
Returns:
subtree pointer or NULL if requested subnode does not exist

Definition at line 660 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::m_Nodes, and CTreeNode< TValue, TKeyGetter >::SetParent().

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::TTreeType * CTreeNode< TValue, TKeyGetter >::DetachNode (  TTreeType *  subnode  )  [inherited]
 

Remove the subtree from the tree without freeing it.

If subnode is not connected directly with the current node the call has no effect. The caller is responsible for deletion of the returned subtree.

Parameters:
subnode direct subnode pointer
Returns:
subtree pointer or NULL if requested subnode does not exist

Definition at line 645 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::m_Nodes, NON_CONST_ITERATE, and CTreeNode< TValue, TKeyGetter >::SetParent().

Referenced by CPhyloTreeDataSource::Cut(), CMenuItem::DestroyAllSubNodes(), CPhyloTreeDataSource::Remove(), CMenuItem::RemoveItem(), CPhyloTreeDataSource::RerootTree(), CPhyloTreeDataSource::SetSubtree(), CPhyloTreeDataSource::x_ConvertUpstream(), and CTree::x_RerootTree().

template<class TDynamicTree, class TTreeNode, class TNodeConvFunc>
TTreeNode* DynamicConvert2Tree (  TDynamicTree &  dyn_tree,
TNodeConvFunc  node_conv,
TTreeNode *&  dst_node
) 
 

Convert dynamic tree to CTreeNode<>, returned CTReeNode<> to be deleted by caller.

Definition at line 180 of file bio_tree_conv.hpp.

References CTree2TreeFunc< TDstTreeNode, TSrcTreeNode, TNodeConvFunc >::GetTreeNode(), and TreeDepthFirstTraverse().

Referenced by CPhyloTreeDataSource::Init().

template<class TValue, class TKeyGetter>
const CTreeNode< TValue, TKeyGetter >::TTreeType * CTreeNode< TValue, TKeyGetter >::FindNode (  const TKeyType &  key,
TNodeSearchMode  sflag = eImmediateAndTop
)  const [inherited]
 

Search for node.

Parameters:
sflag ORed ENodeSearchType
Returns:
node pointer or NULL

Definition at line 897 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::eAllUpperSubNodes, CTreeNode< TValue, TKeyGetter >::eImmediateSubNodes, CTreeNode< TValue, TKeyGetter >::FindSubNode(), and CTreeNode< TValue, TKeyGetter >::GetParent().

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::FindNodes (  const TKeyList &  node_path,
TConstNodeList *  res
)  const [inherited]
 

Find tree nodes corresponding to the path from the top.

Parameters:
node_path hierachy of node keys to search for
res list of discovered found nodes (const pointers)

Definition at line 834 of file ncbi_tree.hpp.

References ITERATE, CTreeNode< TValue, TKeyGetter >::SubNodeBegin(), and CTreeNode< TValue, TKeyGetter >::SubNodeEnd().

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::FindNodes (  const TKeyList &  node_path,
TNodeList *  res
)  [inherited]
 

Find tree nodes corresponding to the path from the top.

Parameters:
node_path hierachy of node keys to search for
res list of discovered found nodes

Definition at line 767 of file ncbi_tree.hpp.

References ITERATE, CTreeNode< TValue, TKeyGetter >::SubNodeBegin(), and CTreeNode< TValue, TKeyGetter >::SubNodeEnd().

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::TTreeType * CTreeNode< TValue, TKeyGetter >::FindOrCreateNode (  const TKeyList &  node_path  )  [inherited]
 

Find or create tree node corresponding to the path from the top.

Parameters:
node_path hierachy of node keys to search for
Returns:
tree node

Definition at line 800 of file ncbi_tree.hpp.

References ITERATE, CTreeNode< TValue, TKeyGetter >::SubNodeBegin(), and CTreeNode< TValue, TKeyGetter >::SubNodeEnd().

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::TTreeType * CTreeNode< TValue, TKeyGetter >::FindSubNode (  const TKeyType &  key  )  [inherited]
 

Non recursive linear scan of all subnodes, with key comparison.

Returns:
SubNode pointer or NULL

Definition at line 882 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::SubNodeBegin(), and CTreeNode< TValue, TKeyGetter >::SubNodeEnd().

template<class TValue, class TKeyGetter>
const CTreeNode< TValue, TKeyGetter >::TTreeType * CTreeNode< TValue, TKeyGetter >::FindSubNode (  const TKeyType &  key  )  const [inherited]
 

Non recursive linear scan of all subnodes, with key comparison.

Returns:
SubNode pointer or NULL

Definition at line 867 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::SubNodeBegin(), and CTreeNode< TValue, TKeyGetter >::SubNodeEnd().

Referenced by CTreeNode< TValue, TKeyGetter >::FindNode().

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::TTreeType * CTreeNode< TValue, TKeyGetter >::GetRoot (  void   )  const [inherited]
 

Get the topmost node.

Returns:
global parent of the current node, this if it is a top of the tree

Definition at line 722 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::GetParent().

Referenced by CPhyloTreeLabel::x_GenerateAutoLabel().

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::InsertNode (  TNodeList_I  it,
TTreeType *  subnode
)  [inherited]
 

Insert new subnode before the specified location in the subnode list.

Parameters:
it subnote iterator idicates the location of the new subtree
subnode subtree pointer

Definition at line 700 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::m_Nodes, and CTreeNode< TValue, TKeyGetter >::SetParent().

Referenced by CMenuItem::InsertSubItem(), ncbi_q_parse(), CPhyloTreeDataSource::Paste(), CPhyloTreeDataSource::Remove(), and CPhyloTreeDataSource::RerootTree().

template<class TValue, class TKeyGetter>
bool CTreeNode< TValue, TKeyGetter >::IsParent (  const TTreeType &  tree_node  )  const [inherited]
 

Check if node is a direct or indirect parent of this node.

Parameters:
tree_node Node candidate
Returns:
TRUE if tree_node is a direct or indirect parent

Definition at line 751 of file ncbi_tree.hpp.

References _ASSERT, and CTreeNode< TValue, TKeyGetter >::GetParent().

Referenced by CTreeNode< TValue, TKeyGetter >::MoveSubnodes().

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::MoveSubnodes (  TTreeType *  src_tree_node  )  [inherited]
 

Remove all subnodes from the source node and attach them to the current tree (node).

Source node cannot be an ancestor of the current node

Definition at line 688 of file ncbi_tree.hpp.

References _ASSERT, CTreeNode< TValue, TKeyGetter >::AddNode(), CTreeNode< TValue, TKeyGetter >::IsParent(), ITERATE, and CTreeNode< TValue, TKeyGetter >::m_Nodes.

CNcbiOstream& operator<< (  CNcbiOstream &  os,
const CBioTreeDynamic &  tree
) 
 

Newick format output.

Definition at line 223 of file bio_tree.cpp.

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter > & CTreeNode< TValue, TKeyGetter >::operator= (  const TTreeType &  tree  )  [inherited]
 

Definition at line 598 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::CopyFrom(), CTreeNode< TValue, TKeyGetter >::m_Nodes, CTreeNode< TValue, TKeyGetter >::m_Parent, and NON_CONST_ITERATE.

template<class TPairTree, class TValue>
const TPairTree* PairTreeBackTraceNode (  const TPairTree &  tr,
const TValue &  search_id
) 
 

Algorithm to to search for a node with specified id.

Tree is traversed back. When searching the upper(parent) level the algorithm never goes down the hierarchy but tries only immediate children.

Definition at line 375 of file tree_algo.hpp.

template<class TPairTree, class TPathList>
const TPairTree* PairTreeTraceNode (  const TPairTree &  tr,
const TPathList &  node_path
) 
 

Algorithm to trace the pair tree and find specified leaf along the node path.

Algorithm always chooses the deepest leaf

Definition at line 412 of file tree_algo.hpp.

References _ASSERT, and ITERATE.

void PrintNode (  CNcbiOstream &  os,
const CBioTreeDynamic &  tree,
const CBioTreeDynamic::TBioTreeNode &  node
) 
 

Newick but without the terminal ';'.

Definition at line 184 of file bio_tree.cpp.

Referenced by operator<<().

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::RemoveAllSubNodes (  EDeletePolicy  del = eDelete  )  [inherited]
 

Remove all immediate subnodes.

Parameters:
del Subnode delete policy. When delete policy is "eNoDelete" nodes are just excluded from the tree. It is responsibility of the caller to track them and guarantee proper destruction.

Definition at line 708 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::eDelete, CTreeNode< TValue, TKeyGetter >::m_Nodes, CTreeNode< TValue, TKeyGetter >::m_Parent, and NON_CONST_ITERATE.

Referenced by CPhyloTreeDataSource::Remove().

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::RemoveNode (  TNodeList_I  it  )  [inherited]
 

Remove subnode of the current node.

Must be direct subnode.

If subnode is not connected directly with the current node the call has no effect.

Parameters:
it subnode iterator

Definition at line 635 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::m_Nodes, and CTreeNode< TValue, TKeyGetter >::m_Parent.

template<class TValue, class TKeyGetter>
void CTreeNode< TValue, TKeyGetter >::RemoveNode (  TTreeType *  subnode  )  [inherited]
 

Remove subnode of the current node.

Must be direct subnode.

If subnode is not connected directly with the current node the call has no effect.

Parameters:
subnode direct subnode pointer

Definition at line 621 of file ncbi_tree.hpp.

References CTreeNode< TValue, TKeyGetter >::m_Nodes, CTreeNode< TValue, TKeyGetter >::m_Parent, and NON_CONST_ITERATE.

Referenced by CPhyloTreeDataSource::Remove().

template<class TTreeNode, class Fun>
Fun TreeBreadthFirstTraverse (  TTreeNode &  tree_node,
Fun  func
) 
 

Breadth-first tree traversal algorithm.

Takes tree and visitor function and calls function for every node in the tree in breadth-first order. Functor is evaluated at each node only once.

Functor should have the next prototype: ETreeTraverseCode Func(TreeNode& node) where node is a reference to the visited node

See also:
ETreeTraverseCode

Definition at line 505 of file ncbi_tree.hpp.

References eTreeTraverse, eTreeTraverseStepOver, and eTreeTraverseStop.

template<class TTreeNode, class TCompFun>
bool TreeCompare (  const TTreeNode &  tree1,
const TTreeNode &  tree2,
TCompFun  func
) 
 

Compare two trees using comparison functor where order of children matters.

Parameters:
tree1 First tree
tree2 Second tree
func Comparison functor (operates on 2 node-value types and returns bool)

Definition at line 62 of file tree_algo.hpp.

template<class TDynamicTree, class TTreeNode, class TNodeConvFunc>
void TreeConvert2Dynamic (  TDynamicTree &  dyn_tree,
const TTreeNode *  src_tree,
TNodeConvFunc  node_conv
) 
 

Convert CTreeNode<> to dynamic tree using a node converter.

Definition at line 156 of file bio_tree_conv.hpp.

References CTree2TreeFunc< TDstTreeNode, TSrcTreeNode, TNodeConvFunc >::GetTreeNode(), and TreeDepthFirstTraverse().

Referenced by CPhyloTreeDataSource::Save().

template<class TTreeNode, class Fun>
Fun TreeDepthFirstTraverse (  TTreeNode &  tree_node,
Fun  func
) 
 

Depth-first tree traversal algorithm.

Takes tree and visitor function and calls function for every node in the tree.

Functor should have the next prototype: ETreeTraverseCode Func(TreeNode& node, int delta_level) where node is a reference to the visited node and delta_level reflects the current traverse direction(depth wise) in the tree, 0 - algorithm stays is on the same level 1 - we are going one level deep into the tree (from the root) -1 - we are traveling back by one level (getting close to the root)

The specificts of the algorithm is that it calls visitor both on the way from the root to leafs and on the way back Using this template we can implement both variants of tree traversal (pre-order and post-order) Visitor controls the traversal by returning ETreeTraverseCode

See also:
ETreeTraverseCode

Definition at line 420 of file ncbi_tree.hpp.

References eTreeTraverse, eTreeTraverseStepOver, and eTreeTraverseStop.

Referenced by CBioTree< TBioNode >::AddNode(), BDB_PrintQueryTree(), BioTreeConvert2Container(), BioTreeConvert2Dynamic(), CPhyloTreeDataSource::Clean(), CPhyloTreeDataSource::ConvertSelectionToBiotree(), CBDB_QueryParserEnvironment::DetachQueryClause(), CQueryParserEnv::DetachQueryTree(), DynamicConvert2Tree(), CQueryExec::Evaluate(), CBDB_FileScanner::Evaluate(), CGuideTree::ExpandCollapseSubtree(), CPhyloTreeDataSource::Filter(), CPhyloTreeDataSource::FilterDistances(), CBioTree< TBioNode >::FindNode(), CQueryParserEnv::Free(), CGuideTree::FullyExpand(), CPhyloTreeDataSource::GetBoundRect(), CGuideTree::GetMap(), CPhyloTreeDataSource::GetNode(), CPhyloTreeDataSource::GetSelectedIds(), CPhyloTreeDataSource::GetSelectedNodes(), CTaxTreeBrowser::GetSelectedUids(), CGuideTree::GetTreeInfo(), CPhyloTreeDataSource::Init(), CGuideTree::IsSingleBlastName(), CPhyloTreeDataSource::MarkAllDirty(), CQueryParseTree::Print(), CPhyloTreeDataSource::Refresh(), CBDB_Query::ResetQueryClause(), CQueryParseTree::ResetUserObjects(), CBDB_FileScanner::ResolveFields(), CBioTree< TBioNode >::SetParentTree(), CBioTree< TBioNode >::SetTreeNode(), CPhyloTreeDataSource::ShowAll(), CPhyloTreeDataSource::SimplifyForDepth(), CGuideTree::SimplifyTree(), CPhyloTreeDataSource::Sort(), TreeConvert2Dynamic(), TreeMakeSet(), TreePrint(), TreeSetToNodeList(), CPhyloForce::x_Calculate(), CTaxTreeBrowser::x_CountNodes(), CPhyloTreeCGIApplication::x_GetMap(), CGuideTree::x_GetNode(), CPhyloTreeDataSource::x_MeasureTree(), and CBDB_QueryParserEnvironment::~CBDB_QueryParserEnvironment().

template<class TTreeNode>
const TTreeNode* TreeFindCommonParent (  const TTreeNode &  tree_node_a,
const TTreeNode &  tree_node_b
) 
 

Check if two nodes have the same common root.

Algorithm finds first common ancestor (farthest from the root)

Parameters:
tree_node_a Node A
tree_node_b Node B
Returns:
Nearest common root or NULL if there is no common parent

Definition at line 244 of file tree_algo.hpp.

References TreeTraceToRoot().

template<class TTreeNode, class TFunc>
TFunc TreeForEachParent (  const TTreeNode &  tree_node,
TFunc  func,
bool  skip_self = false
) 
 

Visit every parent of the specified node.

Parameters:
tree_node Starting node
func Visiting functor
skip_self Flag to skip the first node (tree_node itself) When TRUE visits only true ancestors

Definition at line 156 of file tree_algo.hpp.

Referenced by TreeMakeParentsSet(), and TreeTraceToRoot().

template<class TNodeList, class TBackInsert>
void TreeListToSet (  const TNodeList &  node_list,
TBackInsert  back_ins
) 
 

Convert list of node pointers to set of ids.

Parameters:
node_list node list container (must support const_iterator)
back_ins back insert iterator for the set container

Definition at line 482 of file tree_algo.hpp.

References TreeListToSet().

template<class TNodeListIt, class TBackInsert>
void TreeListToSet (  TNodeListIt  node_list_first,
TNodeListIt  node_list_last,
TBackInsert  back_ins
) 
 

Convert list of node pointers to set of ids Input set is represented by input forward iterators Output set is a back insert iterator.

Definition at line 464 of file tree_algo.hpp.

Referenced by CTreeMinimalSet< TNode, TSet, TNodeList >::MinimalSet(), CTreeNodesOr< TNode, TSet, TNodeList >::operator()(), CTreeNodesAnd< TNode, TSet, TNodeList >::operator()(), CTreeNonRedundantSet< TNode, TSet, TNodeList >::operator()(), and TreeListToSet().

template<class TNode, class TBackInsert>
void TreeMakeParentsSet (  const TNode &  tree_node,
TBackInsert  back_ins
) 
 

Traverses all ancestors and add their ids to a set.

Parameters:
tree_node Starting node
back_ins Back insert iterator (represents set)

Definition at line 526 of file tree_algo.hpp.

References TreeForEachParent().

Referenced by CTreeNonRedundantSet< TNode, TSet, TNodeList >::operator()().

template<class TNode, class TBackInsert>
void TreeMakeSet (  const TNode &  tree_node,
TBackInsert  back_ins
) 
 

Create set of all sub-nodes (recursively).

Parameters:
tree_node root node
back_ins Back insert iterator (represents set)

Definition at line 541 of file tree_algo.hpp.

References TreeDepthFirstTraverse().

Referenced by CTreeMinimalSet< TNode, TSet, TNodeList >::CheckNodeList().

template<class TNode, class TBackInsert>
void TreeMakeSubNodesSet (  const TNode &  tree_node,
TBackInsert  back_ins
) 
 

Create set of all immediate sub-nodes (one level down from the root).

Parameters:
tree_node root node
back_ins Back insert iterator (represents set)

Definition at line 556 of file tree_algo.hpp.

Referenced by CTreeMinimalSet< TNode, TSet, TNodeList >::CheckNodeList().

template<class TTreeNode, class TConverter>
void TreePrint (  CNcbiOstream &  os,
const TTreeNode &  tree_node,
TConverter  conv,
bool  print_ptr = false
) 
 

Tree printing (use for debugging purposes).

Parameters:
os Stream to print the tree
tree_node Tree node to print (top or sub-tree)
conv Converter of node value to string (string Conv(node_value) )
print_ptr When TRUE function prints all internal pointers (debugging)

Definition at line 348 of file tree_algo.hpp.

References TreeDepthFirstTraverse().

template<class TTreeNode>
void TreeReRoot (  TTreeNode &  new_root_node  ) 
 

Change tree root (tree rotation).

Parameters:
new_root_node new node which becomes new tree root after the call

Definition at line 217 of file tree_algo.hpp.

References ITERATE, trace, and TreeTraceToRoot().

template<class TNode, class TSet, class TNodeList>
void TreeSetToNodeList (  const TNode &  tree_node,
const TSet &  node_set,
TNodeList &  nlist
) 
 

Convert set of node ids to list of nodes.

Traverses the tree, if node is in the set adds node pointer to the nodelist.

Definition at line 609 of file tree_algo.hpp.

References TreeDepthFirstTraverse().

template<class TTreeNode, class TTraceContainer>
void TreeTraceToRoot (  const TTreeNode &  tree_node,
TTraceContainer &  trace
) 
 

Trace from the specified node to to the tree root.

Trace path is a container of node const node pointers (The only requirement is push_back method) The input node becomes first element, then comes its parent. If the node is a tree top its pointer is the only element of the trace vector

Parameters:
tree_node Starting node (added to the trace first)
trace Trace container (vector<const TTreeNode*> or similar)

Definition at line 205 of file tree_algo.hpp.

References TreeForEachParent().

Referenced by TreeFindCommonParent(), and TreeReRoot().

void WriteNexusTree (  CNcbiOstream &  os,
const CBioTreeDynamic &  tree,
const string &  tree_name = "the_tree"
) 
 

Nexus format output (Newick with some stuff around it).

tree_name gets put in the file.

Definition at line 231 of file bio_tree.cpp.

Referenced by CPhyExportJob::Run().

template<class TValue, class TKeyGetter>
CTreeNode< TValue, TKeyGetter >::~CTreeNode (   )  [inherited]
 

Definition at line 578 of file ncbi_tree.hpp.

References _ASSERT, CTreeNode< TValue, TKeyGetter >::m_Nodes, CTreeNode< TValue, TKeyGetter >::m_Parent, and NON_CONST_ITERATE.

Generated on Mon Dec 7 16:01:47 2009 for NCBI C++ ToolKit by  doxygen 1.4.6
Modified on Mon Dec 07 16:24:35 2009 by modify_doxy.py rev. 173732