#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 &&)=default

	NewickBroker (NewickBroker const &)=default

	~NewickBroker ()=default

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

NewickBrokerElement &	at (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...

NewickBrokerElement &	bottom ()
	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...

NewickBroker &	operator= (NewickBroker &&)=default

NewickBroker &	operator= (NewickBroker const &)=default

NewickBrokerElement &	operator[] (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 &&node)

void	push_bottom (NewickBrokerElement const &node)

void	push_top (NewickBrokerElement &&node)

void	push_top (NewickBrokerElement const &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...

NewickBrokerElement &	top ()
	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]

NewickBroker::const_iterator begin ( )

Returns an iterator to the top of the stack.

Definition at line 237 of file broker.cpp.

◆ begin() [2/2]

const_iterator begin ( ) const

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

◆ bottom() [1/2]

NewickBrokerElement const & 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

◆ cbegin()

NewickBroker::const_iterator cbegin ( ) const

Const version of begin().

Definition at line 257 of file broker.cpp.

◆ cend()

NewickBroker::const_iterator cend ( ) const

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()

NewickBroker::const_reverse_iterator crbegin ( )

Const version of rbegin().

Definition at line 287 of file broker.cpp.

◆ crend()

NewickBroker::const_reverse_iterator 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]

NewickBroker::const_iterator end ( )

Returns an iterator to the end of the token list.

Definition at line 247 of file broker.cpp.

◆ end() [2/2]

const_iterator end ( ) const

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

◆ 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 && )

default

◆ operator=() [2/2]

NewickBroker& operator= ( NewickBroker const & )

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 && node )

Definition at line 66 of file broker.cpp.

◆ push_bottom() [2/2]

void push_bottom ( NewickBrokerElement const & node )

Definition at line 61 of file broker.cpp.

◆ push_top() [1/2]

void push_top ( NewickBrokerElement && node )

Definition at line 56 of file broker.cpp.

◆ push_top() [2/2]

void push_top ( NewickBrokerElement const & node )

Definition at line 51 of file broker.cpp.

◆ rbegin() [1/2]

NewickBroker::const_reverse_iterator rbegin ( )

Returns a reverse iterator to the nodes on the stack.

Definition at line 267 of file broker.cpp.

◆ rbegin() [2/2]

const_reverse_iterator rbegin ( ) const

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

◆ rend() [1/2]

NewickBroker::const_reverse_iterator rend ( )

Reverse version of end().

Definition at line 277 of file broker.cpp.

◆ rend() [2/2]

const_reverse_iterator rend ( ) const

Reverse version of end() for const objects.

◆ 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]

NewickBrokerElement const & top ( )

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

◆ 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

typedef std::deque<NewickBrokerElement>::const_iterator const_iterator

Definition at line 115 of file broker.hpp.

◆ const_reverse_iterator

typedef std::deque<NewickBrokerElement>::const_reverse_iterator 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

typedef std::deque<NewickBrokerElement>::reverse_iterator reverse_iterator

Definition at line 116 of file broker.hpp.

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

Detailed Description

Public Member Functions

Public Types

Constructor & Destructor Documentation

◆ NewickBroker() [1/3]

◆ ~NewickBroker()

◆ NewickBroker() [2/3]

◆ NewickBroker() [3/3]

Member Function Documentation

◆ assign_ranks()

◆ at() [1/2]

◆ at() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ bottom() [1/2]

◆ bottom() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ crbegin()

◆ crend()

◆ dump()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ inner_count()

◆ is_bifurcating()

◆ leaf_count()

◆ max_rank()

◆ node_count()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop_bottom()

◆ pop_top()

◆ push_bottom() [1/2]

◆ push_bottom() [2/2]

◆ push_top() [1/2]

◆ push_top() [2/2]

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ size()

◆ top() [1/2]

◆ top() [2/2]

◆ validate()

Member Typedef Documentation

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ reverse_iterator