Skip to content
Fetching contributors…
Cannot retrieve contributors at this time
590 lines (423 sloc) 15 KB
/*
* Copyright (C) 2009-2012 Simon A. Berger
*
* This file is part of papara.
*
* papara 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 3 of the License, or
* (at your option) any later version.
*
* papara 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 papara. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef __tree_utils_h
#define __tree_utils_h
#if 0
#include <algorithm>
#include <stdexcept>
#include <vector>
#include <set>
#include <cassert>
#include <stdint.h>
#include <boost/tr1/unordered_set.hpp>
#include "ivymike/smart_ptr.h"
#include "ivymike/tree_parser.h"
enum tip_case {
TIP_TIP,
TIP_INNER,
INNER_INNER
};
template<class lnode>
struct rooted_bifurcation {
lnode * parent;
lnode * child1;
lnode * child2;
tip_case tc;
rooted_bifurcation() : parent(0), child1(0), child2(0) {}
rooted_bifurcation( lnode *p, lnode *c1, lnode *c2, tip_case t )
: parent(p),
child1(c1),
child2(c2),
tc(t)
{}
};
template<typename lnode>
inline bool operator==( const rooted_bifurcation<lnode> &n1, const rooted_bifurcation<lnode> &n2 ) {
return n1.parent == n2.parent && n1.child1 == n2.child1 && n1.child2 == n2.child2 && n1.tc == n2.tc;
}
template<class lnode>
inline std::ostream &operator<<( std::ostream &os, const rooted_bifurcation<lnode> &rb ) {
const char *tc = "W.T.F.";
switch( rb.tc ) {
case TIP_TIP:
tc = "TIP_TIP";
break;
case TIP_INNER:
tc = "TIP_INNER";
break;
case INNER_INNER:
tc = "INNER_INNER";
break;
}
os << tc << " " << *(rb.parent->m_data) << " " << *(rb.child1->m_data) << " " << *(rb.child2->m_data);
return os;
}
template <class lnode, class container>
void rooted_traveral_order_rec( lnode *n, container &cont, bool incremental = false ) {
lnode *n1 = n->next->back;
lnode *n2 = n->next->next->back;
assert( n->m_data->isTip || n1 != 0 );
assert( n->m_data->isTip || n2 != 0 );
// FIXME: why did I allow n to be a tip in the assertions above. fix this some time!
// this function will crash if n is a tip...
// TODO: should this function silently ignore+return if n is a tip, or
// is it better to enforce strict handling at a higher level?
// This function itself does not descent into links to tips, so high level handling
// makes more sense.
assert( n1 != 0 && n2 != 0 );
// STUPID: this just bit me in a non-debug build (assertions disabled), so make it a real runtime error (but keep in assertion, because it is better for debugging)
if( n1 == 0 || n2 == 0 ) {
throw std::runtime_error( "n1 == 0 || n2 == 0" );
}
n->towards_root = true;
n->next->towards_root = false;
n->next->next->towards_root = false;
if( n1->m_data->isTip && n2->m_data->isTip ) {
cont.push_front( rooted_bifurcation<lnode>( n, n1, n2, TIP_TIP ));
} else if( n1->m_data->isTip && !n2->m_data->isTip ) {
cont.push_front( rooted_bifurcation<lnode>( n, n1, n2, TIP_INNER ));
if( !incremental || !n2->towards_root ) {
rooted_traveral_order_rec( n2, cont );
}
} else if( !n1->m_data->isTip && n2->m_data->isTip ) {
cont.push_front( rooted_bifurcation<lnode>( n, n2, n1, TIP_INNER ));
if( !incremental || !n1->towards_root ) {
rooted_traveral_order_rec( n1, cont );
}
} else {
cont.push_front( rooted_bifurcation<lnode>( n, n1, n2, INNER_INNER ));
if( !incremental || !n1->towards_root ) {
rooted_traveral_order_rec( n1, cont );
}
if( !incremental || !n2->towards_root ) {
rooted_traveral_order_rec( n2, cont );
}
}
}
//template <class lnode, class container>
//void rooted_traveral_order( lnode *n1, lnode *n2, container &cont, bool incremental ) {
//
// if( !n1->m_data->isTip ) {
// rooted_traveral_order_rec<lnode, container>( n1, cont, incremental );
// }
// if( !n2->m_data->isTip ) {
// rooted_traveral_order_rec<lnode, container>( n2, cont, incremental );
// }
//
//
// //std::reverse( cont.begin(), cont.end());
//}
template <class lnode, class container>
void rooted_traversal_order( lnode *n1, lnode *n2, lnode *n3, container &cont, bool incremental ) {
if( !n1->m_data->isTip ) {
rooted_traveral_order_rec<lnode, container>( n1, cont, incremental );
}
if( !n2->m_data->isTip ) {
rooted_traveral_order_rec<lnode, container>( n2, cont, incremental );
}
if( n3 != 0 ) {
if( !n3->m_data->isTip ) {
rooted_traveral_order_rec<lnode, container>( n3, cont, incremental );
}
}
//std::reverse( cont.begin(), cont.end());
}
template <class lnode, class container>
void rooted_traversal_order( lnode *n1, lnode *n2, container &cont, bool incremental ) {
rooted_traversal_order<lnode,container>( n1, n2, 0, cont, incremental );
}
template <class lnode, typename oiter>
void rooted_preorder_traversal( lnode *n, oiter start, bool incremental = false ) {
if( n == 0 ) {
return;
}
if( n->m_data->isTip ) {
return;
}
lnode *n1 = n->next->back;
lnode *n2 = n->next->next->back;
assert( n->m_data->isTip || n1 != 0 );
assert( n->m_data->isTip || n2 != 0 );
n->towards_root = true;
n->next->towards_root = false;
n->next->next->towards_root = false;
if( n1->m_data->isTip && n2->m_data->isTip ) {
*(start++) = rooted_bifurcation<lnode>( n, n1, n2, TIP_TIP );
} else if( n1->m_data->isTip && !n2->m_data->isTip ) {
*(start++) = rooted_bifurcation<lnode>( n, n1, n2, TIP_INNER );
if( !incremental || !n2->towards_root ) {
rooted_preorder_traversal( n2, start );
}
} else if( !n1->m_data->isTip && n2->m_data->isTip ) {
*(start++) = rooted_bifurcation<lnode>( n, n2, n1, TIP_INNER );
if( !incremental || !n1->towards_root ) {
rooted_preorder_traversal( n1, start );
}
} else {
*(start++) = rooted_bifurcation<lnode>( n, n1, n2, INNER_INNER );
if( !incremental || !n1->towards_root ) {
rooted_preorder_traversal( n1, start );
}
if( !incremental || !n2->towards_root ) {
rooted_preorder_traversal( n2, start );
}
}
}
template <class lnode>
lnode *towards_tree( lnode *n ) {
int ct = 0;
while( n->back == 0 ) {
n = n->next;
if( ct > 3 ) {
throw std::runtime_error( "node not connected to tree" );
}
ct++;
}
return n;
}
template <class visitor>
void visit_lnode( typename visitor::lnode *n, visitor &v, bool go_back = true ) {
v( n );
if( go_back && n->back != 0 ) {
visit_lnode( n->back, v, false );
}
if( n->next->back != 0 ) {
visit_lnode( n->next->back, v, false );
}
if( n->next->next->back != 0 ) {
visit_lnode( n->next->next->back, v, false );
}
};
template <class visitor>
void visit_lnode_postorder( typename visitor::lnode *n, visitor &v, bool go_back = true ) {
if( go_back && n->back != 0 ) {
visit_lnode( n->back, v, false );
}
if( n->next->back != 0 ) {
visit_lnode( n->next->back, v, false );
}
if( n->next->next->back != 0 ) {
visit_lnode( n->next->next->back, v, false );
}
v( n );
};
template <class LNODE, class CONT = std::vector<sptr::shared_ptr<LNODE> > >
struct tip_collector {
typedef LNODE lnode;
typedef CONT container;
//container<lnode *> m_nodes;
container m_nodes;
void operator()( lnode *n ) {
if( n->m_data->isTip ) {
m_nodes.push_back(n->get_smart_ptr().lock());
}
}
};
template <class LNODE>
struct tip_collector_dumb {
typedef LNODE lnode;
//container<lnode *> m_nodes;
std::vector<lnode *> m_nodes;
void operator()( lnode *n ) {
if( n->m_data->isTip ) {
m_nodes.push_back(n);
}
}
};
//template <class LNODE>
//struct node_collector_dumb {
// typedef LNODE lnode;
// typedef std::vector<lnode *> container;
// container m_nodes;
//
//
// void operator()( lnode *n ) {
// if( n->m_data->isTip ) {
// m_nodes.push_back(n);
// }
// }
//};
template <typename visitor>
void visit_edges( typename visitor::lnode *n, visitor &v, bool at_root = true ) {
assert( n->back != 0 );
if( !at_root ) {
v( n, n->back );
}
if( at_root && n->back != 0 ) {
visit_edges( n->back, v, false );
}
if( n->next->back != 0 ) {
visit_edges( n->next->back, v, false );
}
if( n->next->next->back != 0 ) {
visit_edges( n->next->next->back, v, false );
}
// at the root, the edge between n and n->back will be visited when recursing to n->back
};
template <class LNODE>
struct edge_collector {
public:
typedef LNODE lnode;
typedef std::pair<LNODE *, LNODE *> edge;
typedef std::vector<edge> container;
void operator()( lnode *n1, lnode *n2 ) {
// std::cout << "edge: " << n1 << " " << n2 << "\n";
m_edges.push_back( edge( n1, n2 ) );
}
container m_edges;
};
class node_level_assignment {
typedef ivy_mike::tree_parser_ms::lnode lnode;
std::vector<std::pair<int,lnode *> > m_level_mapping;
std::tr1::unordered_set<lnode *>m_mix;
std::tr1::unordered_set<lnode *>m_closed;
size_t round( int level ) {
// std::cerr << "round " << level << " " << m_mix.size() << "\n";
std::tr1::unordered_set<lnode *> cand;
std::vector<lnode *>rm;
for( std::tr1::unordered_set<lnode *>::iterator it = m_mix.begin(); it != m_mix.end(); ++it ) {
lnode *n = *it;
// std::cout << "mix: " << level << " " << n << " " << n->next << "\n";
assert( !n->m_data->isTip );
if( m_mix.find(n->next) != m_mix.end() ) {
// std::cout << "level: " << level << " " << *(n->next->next->m_data) << "\n";
// m_level_mapping.push_back( std::pair<int,lnode*>(level, n->next->next ));
rm.push_back( n );
// rm.push_back( n->next );
// if( m_closed.find( n->next->next->back ) == m_closed.end() ) {
// m_mix.insert( n->next->next->back );
// }
}
}
for( std::vector<lnode *>::iterator it = rm.begin(); it != rm.end(); ++it ) {
lnode *n = *it;
m_level_mapping.push_back( std::pair<int,lnode*>(level, n->next->next ));
m_closed.insert(n->next->next);
m_mix.erase( *it );
m_mix.erase( (*it)->next );
}
for( std::vector<lnode *>::iterator it = rm.begin(); it != rm.end(); ++it ) {
lnode *n = *it;
if( m_closed.find( n->next->next->back ) == m_closed.end() ) {
m_mix.insert( n->next->next->back );
}
}
return m_mix.size();
}
public:
node_level_assignment( std::vector<lnode *> tips ) {
for( std::vector<lnode *>::iterator it = tips.begin(); it != tips.end(); ++it ) {
m_level_mapping.push_back( std::pair<int,lnode*>( 0, *it ) );
// m_closed.insert( *it );
m_closed.insert(*it);
assert( (*it)->back != 0 );
if( !(*it)->back->m_data->isTip ) {
m_mix.insert( (*it)->back );
}
}
int level = 1;
while( round( level++ ) != 0 ) {}
// for( std::vector<std::pair<int,lnode *> >::iterator it = m_level_mapping.begin(); it != m_level_mapping.end(); ++it ) {
// std::cout << "level: " << it->first << " " << *(it->second->m_data) << "\n";
// }
// std::cout << "end\n";
}
std::vector<std::pair<int,lnode *> > &get_level_mapping() {
return m_level_mapping;
}
};
//////////////////////////////////////////////////////////////////////////
// STL inspired replacements to the 'visitor' stuff above.
// (Which actually has nothing to do with the stupid java hack that is
// commonly called visitor pattern)
// STL compatible function to iterate over the lnodes (kind of like a std::copy)
template <typename lnode, typename oiter>
void iterate_lnode( lnode *n, oiter start, bool go_back = true ) {
*(start++) = n;
//outer++;
if( go_back && n->back != 0 ) {
iterate_lnode( n->back, start, false );
}
if( n->next->back != 0 ) {
iterate_lnode( n->next->back, start, false );
}
if( n->next->next->back != 0 ) {
iterate_lnode( n->next->next->back, start, false );
}
};
template <typename lnode, typename Tfunc>
void apply_lnode( lnode *n, Tfunc func, bool go_back = true ) {
//*(start++) = n;
func(n);
//outer++;
if( go_back && n->back != 0 ) {
apply_lnode( n->back, func, false );
}
if( n->next->back != 0 ) {
apply_lnode( n->next->back, func, false );
}
if( n->next->next->back != 0 ) {
apply_lnode( n->next->next->back, func, false );
}
};
// TEST" implement interate_node in terms of the more generic lnode_apply
template <typename lnode, typename oiter>
void iterate_lnode_test( lnode *n, oiter start, bool go_back = true ) {
// call recurseve apply with a 'iterator inserter' lambda
apply_lnode(n, [&start](lnode *n) {*(start++)=n;}, go_back );
};
// UNTESTED: back_insert_iterator that only only inserts if predicate is true (TDD is for pussies)
// combined with is_tip and iterate_lnodes it replaces most of the stupid hard-coded collectors from above.
template <class Container, typename Pred>
class back_insert_if_iterator :
public std::iterator<std::output_iterator_tag,void,void,void,void>
{
protected:
Container* container_;
Pred p_;
public:
typedef Container container_type;
explicit back_insert_if_iterator (Container& x, Pred p ) : container_(&x), p_(p) {}
back_insert_if_iterator<Container, Pred>& operator= (typename Container::const_reference value) {
if( p_( value ) ) {
container_->push_back(value);
}
return *this;
}
back_insert_if_iterator<Container,Pred>& operator* () {
return *this;
}
back_insert_if_iterator<Container,Pred>& operator++ () {
return *this;
}
back_insert_if_iterator<Container,Pred> operator++ (int) {
return *this;
}
};
template <class Container, typename Pred>
back_insert_if_iterator<Container, Pred> back_insert_ifer(Container &cont, Pred p ) {
return back_insert_if_iterator<Container, Pred>(cont, p);
}
inline bool is_tip( ivy_mike::tree_parser_ms::lnode * l ) {
assert( l != 0 );
assert( l->m_data != 0 );
return l->m_data->isTip;
}
#endif
#endif
Something went wrong with that request. Please try again.