A toolkit for working with phylogenetic data.
v0.24.0
NewickBroker Class Reference

#include <genesis/tree/formats/newick/broker.hpp>

Detailed Description

Stores a Newick tree in an intermediate format that can be further processed into a Tree.

The NewickBroker is a transitional format between the Newick formatted tree and a Tree object. It is neccessary to have this intermediate step, because the ordering of nodes in the Newick format differs from our requirements. Newick trees starts with leaf nodes, while our internal representation is build up from the root.

The NewickBroker is organized as a stack, where the root of the tree is at the top/front. Then follow the nodes in a preorder manner, where each node is of type NewickBrokerElement.

The topology of the tree is represented via a depth attribute of each node: Two subsequent nodes are siblings (belong to the same parent node), if they have the same depth. If the second node has a depth that is one higher than the first ones, it is it's child (depth thus cannot increase more than one between two nodes). Lastly, if the depth of the second node is smaller than the first ones, it belongs to a different subtree.

For example, the following tree in Newick format:

((A,((B,C,D)E,F)G)H,((I,J,K)L,M,N)O,P,Q)R;

would be stored as the following stack:

R Rank(4)
    Q (Leaf)
    P (Leaf)
    O Rank(3)
        N (Leaf)
        M (Leaf)
        L Rank(3)
            K (Leaf)
            J (Leaf)
            I (Leaf)
    H Rank(2)
        G Rank(2)
            F (Leaf)
            E Rank(3)
                D (Leaf)
                C (Leaf)
                B (Leaf)
        A (Leaf)

Here, the rank represents the number of immediate children of this node. Leaf nodes have no children and thus rank zero.

Every function modifiying the content of the broker is required to leave it in a valid state, meaning:

  • The top node has to be the root of the tree, which is equivalent to having depth zero. This is also true for trees rooted on a leaf.
  • The nesting of the nodes has to be correct, so the depth cannot increase more than one per node when going down the tree.
  • The attribute NewickBrokerElement::is_leaf of the NewickBrokerElements can be set (for exmaple when parsing a Newick tree) and then be used to validate the integrity of the tree using validate(). However, the attribute is not further used – see its description for more on this. %

Definition at line 106 of file broker.hpp.

Public Member Functions

 NewickBroker ()=default
 
 NewickBroker (NewickBroker const &)=default
 
 NewickBroker (NewickBroker &&)=default
 
 ~NewickBroker ()=default
 
void assign_ranks () const
 Iterate over the tree and assign ranks (= number of immediate children) to all nodes. More...
 
NewickBrokerElementat (std::size_t index)
 Provides index based array access to the nodes, doing a boundary check first. More...
 
NewickBrokerElement const & at (std::size_t index) const
 
iterator begin ()
 Returns an iterator to the top of the stack. More...
 
const_iterator begin () const
 Returns an iterator to the top of the stack for const objects. More...
 
NewickBrokerElementbottom ()
 Returns a reference to the bottom node of the tree stack. More...
 
NewickBrokerElement const & bottom () const
 
const_iterator cbegin () const
 Const version of begin(). More...
 
const_iterator cend () const
 Const version of end(). More...
 
void clear ()
 Deletes all nodes from the broker. More...
 
const_reverse_iterator crbegin ()
 Const version of rbegin(). More...
 
const_reverse_iterator crend ()
 Const version of rend(). More...
 
std::string dump () const
 Return a readable string representation of the elements of the NewickBroker. More...
 
bool empty () const
 Returns whether the stack is empty. More...
 
iterator end ()
 Returns an iterator to the end of the token list. More...
 
const_iterator end () const
 Returns an iterator to the end of the token list for const objects. More...
 
size_t inner_count () const
 
bool is_bifurcating () const
 
size_t leaf_count () const
 Returns the number of leaf nodes in the tree. assign_ranks() has to be called first. More...
 
long max_rank () const
 Returns the highest rank of the nodes in the tree. assign_ranks() has to be called first. More...
 
size_t node_count () const
 Alias for size(). More...
 
NewickBrokeroperator= (NewickBroker const &)=default
 
NewickBrokeroperator= (NewickBroker &&)=default
 
NewickBrokerElementoperator[] (std::size_t index)
 Provides index based array access to the nodes. More...
 
NewickBrokerElement const & operator[] (std::size_t index) const
 
void pop_bottom ()
 
void pop_top ()
 
void push_bottom (NewickBrokerElement const &node)
 
void push_bottom (NewickBrokerElement &&node)
 
void push_top (NewickBrokerElement const &node)
 
void push_top (NewickBrokerElement &&node)
 
reverse_iterator rbegin ()
 Returns a reverse iterator to the nodes on the stack. More...
 
const_reverse_iterator rbegin () const
 Returns a reverse iterator to the nodes on the stack for const objects. More...
 
reverse_iterator rend ()
 Reverse version of end(). More...
 
const_reverse_iterator rend () const
 Reverse version of end() for const objects. More...
 
size_t size () const
 Returns the size of the stack, i.e. the number of nodes stored in the broker. More...
 
NewickBrokerElementtop ()
 Returns a reference to the top node of the tree stack. More...
 
NewickBrokerElement const & top () const
 
bool validate () const
 Returns true iff the tree is valid. assign_ranks() has to be called first. More...
 

Public Types

typedef std::deque< NewickBrokerElement >::const_iterator const_iterator
 
typedef std::deque< NewickBrokerElement >::const_reverse_iterator const_reverse_iterator
 
typedef std::deque< NewickBrokerElement >::iterator iterator
 
typedef std::deque< NewickBrokerElement >::reverse_iterator reverse_iterator
 

Constructor & Destructor Documentation

◆ NewickBroker() [1/3]

NewickBroker ( )
default

◆ ~NewickBroker()

~NewickBroker ( )
default

◆ NewickBroker() [2/3]

NewickBroker ( NewickBroker const &  )
default

◆ NewickBroker() [3/3]

NewickBroker ( NewickBroker &&  )
default

Member Function Documentation

◆ assign_ranks()

void assign_ranks ( ) const

Iterate over the tree and assign ranks (= number of immediate children) to all nodes.

This function is for example needed to check whether it is a bifurcating/binary tree, or to check how many leaves and inner nodes the tree has. Thus, it is usually called after the broker is filled with data.

Definition at line 85 of file broker.cpp.

◆ at() [1/2]

NewickBrokerElement & at ( std::size_t  index)

Provides index based array access to the nodes, doing a boundary check first.

In out of bounds cases, an exception is thrown.

Definition at line 197 of file broker.cpp.

◆ at() [2/2]

NewickBrokerElement const & at ( std::size_t  index) const

Definition at line 205 of file broker.cpp.

◆ begin() [1/2]

Returns an iterator to the top of the stack.

Definition at line 237 of file broker.cpp.

◆ begin() [2/2]

Returns an iterator to the top of the stack for const objects.

Definition at line 242 of file broker.cpp.

◆ bottom() [1/2]

NewickBrokerElement & bottom ( )

Returns a reference to the bottom node of the tree stack.

Calling this function on an empty() broker causes undefined behavior.

Definition at line 223 of file broker.cpp.

◆ bottom() [2/2]

NewickBrokerElement const & bottom ( ) const

Definition at line 228 of file broker.cpp.

◆ cbegin()

NewickBroker::const_iterator cbegin ( ) const

Const version of begin().

Definition at line 257 of file broker.cpp.

◆ cend()

Const version of end().

Definition at line 262 of file broker.cpp.

◆ clear()

void clear ( )

Deletes all nodes from the broker.

Definition at line 46 of file broker.cpp.

◆ crbegin()

Const version of rbegin().

Definition at line 287 of file broker.cpp.

◆ crend()

Const version of rend().

Definition at line 292 of file broker.cpp.

◆ dump()

std::string dump ( ) const

Return a readable string representation of the elements of the NewickBroker.

Definition at line 327 of file broker.cpp.

◆ empty()

bool empty ( ) const

Returns whether the stack is empty.

Definition at line 173 of file broker.cpp.

◆ end() [1/2]

Returns an iterator to the end of the token list.

Definition at line 247 of file broker.cpp.

◆ end() [2/2]

Returns an iterator to the end of the token list for const objects.

Definition at line 252 of file broker.cpp.

◆ inner_count()

size_t inner_count ( ) const

Definition at line 136 of file broker.cpp.

◆ is_bifurcating()

bool is_bifurcating ( ) const

Definition at line 164 of file broker.cpp.

◆ leaf_count()

size_t leaf_count ( ) const

Returns the number of leaf nodes in the tree. assign_ranks() has to be called first.

Definition at line 122 of file broker.cpp.

◆ max_rank()

long max_rank ( ) const

Returns the highest rank of the nodes in the tree. assign_ranks() has to be called first.

Definition at line 149 of file broker.cpp.

◆ node_count()

size_t node_count ( ) const

Alias for size().

Definition at line 144 of file broker.cpp.

◆ operator=() [1/2]

NewickBroker& operator= ( NewickBroker const &  )
default

◆ operator=() [2/2]

NewickBroker& operator= ( NewickBroker &&  )
default

◆ operator[]() [1/2]

NewickBrokerElement & operator[] ( std::size_t  index)

Provides index based array access to the nodes.

This also allows to iterate over them using:

NewickBroker tb;
for (size_t i = 0; i < tb.size(); ++i) {
   NewickBrokerElement* tn = tb[i];
   std::cout << tn.name << std::endl;
}

Caveat: this operator does no boundary check. If you need this check, use at() instead.

Definition at line 187 of file broker.cpp.

◆ operator[]() [2/2]

NewickBrokerElement const & operator[] ( std::size_t  index) const

Definition at line 192 of file broker.cpp.

◆ pop_bottom()

void pop_bottom ( )

Definition at line 76 of file broker.cpp.

◆ pop_top()

void pop_top ( )

Definition at line 71 of file broker.cpp.

◆ push_bottom() [1/2]

void push_bottom ( NewickBrokerElement const &  node)

Definition at line 61 of file broker.cpp.

◆ push_bottom() [2/2]

void push_bottom ( NewickBrokerElement &&  node)

Definition at line 66 of file broker.cpp.

◆ push_top() [1/2]

void push_top ( NewickBrokerElement const &  node)

Definition at line 51 of file broker.cpp.

◆ push_top() [2/2]

void push_top ( NewickBrokerElement &&  node)

Definition at line 56 of file broker.cpp.

◆ rbegin() [1/2]

Returns a reverse iterator to the nodes on the stack.

Definition at line 267 of file broker.cpp.

◆ rbegin() [2/2]

Returns a reverse iterator to the nodes on the stack for const objects.

Definition at line 272 of file broker.cpp.

◆ rend() [1/2]

Reverse version of end().

Definition at line 277 of file broker.cpp.

◆ rend() [2/2]

Reverse version of end() for const objects.

Definition at line 282 of file broker.cpp.

◆ size()

size_t size ( ) const

Returns the size of the stack, i.e. the number of nodes stored in the broker.

Definition at line 178 of file broker.cpp.

◆ top() [1/2]

Returns a reference to the top node of the tree stack.

Usually, the top element is the root of the tree (i.e., it has depth zero). Only when called during the broker is being filled with nodes (for example, while parsing a Newick tree), the top element is not the root.

Calling this function on an empty() broker causes undefined behavior.

Definition at line 213 of file broker.cpp.

◆ top() [2/2]

NewickBrokerElement const & top ( ) const

Definition at line 218 of file broker.cpp.

◆ validate()

bool validate ( ) const

Returns true iff the tree is valid. assign_ranks() has to be called first.

A valid tree in a NewickBroker has to fullfill those criteria:

  • The depth (nesting level) of the nodes cannot increase more than one level between nodes, as this would imply a non-existing node with a depth in between. However, it can arbitrarily decrease, as this simply means the end of a subtree.
  • Furthermore, rank 1 is not valid, as this represents a node that is not furcating in any way. %

Definition at line 302 of file broker.cpp.

Member Typedef Documentation

◆ const_iterator

Definition at line 115 of file broker.hpp.

◆ const_reverse_iterator

Definition at line 117 of file broker.hpp.

◆ iterator

typedef std::deque<NewickBrokerElement>::iterator iterator

Definition at line 114 of file broker.hpp.

◆ reverse_iterator

Definition at line 116 of file broker.hpp.


The documentation for this class was generated from the following files: