main page namespaces classes files
ELL home

src/ell/LT_BarrierTree.hh

Go to the documentation of this file.

#ifndef LT_BARRIERTREE_HH_
#define LT_BARRIERTREE_HH_

#include <biu/HashMap.hh>

#include "ell/LT_MinimaSet.hh"
#include "ell/State.hh"

#include <vector>
#include <iostream>
#include <string>


//##############################################################################
//##############################################################################


namespace ell
{

    class LT_BarrierTree: public LT_MinimaSet {
    
    public:
        
        static const std::string LT_ID;
        
        
    protected:
        
        class StateList;
        class NodeList;
        
        class Node {
        public:
            Node* parent;
            NodeList* children;
            StateList* content;
            
            Node(   Node* parent, 
                    NodeList* children, 
                    StateList* content,
                    const bool isRoot = false );

            ~Node();
        };
        
        class NodeList {
        public:
            Node* current;
            NodeList* next;
            
            NodeList(   Node* current, NodeList* next );
            
            ~NodeList();
            
            static
            void
            addToList( NodeList*& list, Node* toAdd );
            
            static
            void
            remFromList( NodeList*& listHead, const Node* toRem );
            
        };
        
        class StateList {
        public:
            State* current;
            StateList* next;
            
            StateList(  State* current, StateList* next );
            
            ~StateList();
            
            static
            void
            addToList( StateList*& list, State* toAdd );
        };
        
#ifdef HAVE_GNU_HASH_MAP
        
        class hash_StateP {
        public:
            size_t operator()(const State* s) const {
                return (size_t)s;
            }
        };
        class hash_NodeP {
        public:
            size_t operator()(const Node* n) const {
                return (size_t)n;
            }
        };

        typedef __gnu_cxx::hash_map< const State*, Node*, hash_StateP > Min2Node_MAP;
        typedef __gnu_cxx::hash_map< const Node*, const Node*, hash_NodeP > Node2Node_MAP;
        typedef __gnu_cxx::hash_map< const Node*, size_t, hash_NodeP > Node2SizeT_MAP;
        typedef __gnu_cxx::hash_map< const Node*, int, hash_NodeP > Node2Int_MAP;
        typedef __gnu_cxx::hash_map< size_t, const Node* > SizeT2Node_MAP;
#else
        typedef std::map< const State*, Node* > Min2Node_MAP;
        typedef std::map<const Node*, const Node* > Node2Node_MAP;
        typedef std::map<const Node*, size_t > Node2SizeT_MAP;
        typedef std::map<const Node*, int > Node2Int_MAP;
        typedef std::map< size_t, const Node* > SizeT2Node_MAP;
#endif

    protected:
        
        using LT_MinimaSet::vMinima;
        using LT_MinimaSet::mfeIndex;
        using LT_MinimaSet::sorted;
        
        double maxMergeBarrier;
        Node* root;
        Min2Node_MAP min2node;
        size_t numOfLeaves;
        
    public:
        
        LT_BarrierTree(  const double maxMergeBarrier = 0.0 );
        
        LT_BarrierTree(  const LT_BarrierTree& toCopy );
        
        virtual ~LT_BarrierTree();

        
        
        virtual 
        bool 
        addSaddle(const size_t i, const size_t j, const State* const s);
        
        virtual 
        bool 
        addSaddle(const State* const m_i, const State* const m_j, const State* const s);
        
        virtual 
        const size_t 
        addMin(const State* const m);
        
        virtual 
        double 
        getDistance(const LandscapeTopology* const lt) const;
        
        virtual 
        void 
        clear();

        virtual 
        void
        write(  std::ostream & out, 
                const bool writeGraph = false ) const;

        virtual 
        std::pair<int,std::string>
        read(   std::istream & in, 
                const State * const templateState );
        
        
        bool
        isForest( void ) const;
        
        size_t
        getNumOfTrees( void ) const;
        
        size_t
        getNumOfLeaves( void ) const;
        
        virtual
        LT_BarrierTree&
        operator = ( const LT_BarrierTree& toCopy );
        
        virtual
        LT_BarrierTree&
        operator = ( const LT_MinimaSet& toCopy );
        
        
        virtual
        const State*
        getBarrier( const size_t m1, const size_t m2 ) const;
        
        
        virtual
        const State*
        getBarrier( const State* const m1, const State* const m2 ) const;
        
        
    protected:
        
        Node*
        getHighestParentLEQ( Node* child, const double maxEnergy );
        
        const Node*
        getHighestParentLEQ( const Node* child, const double maxEnergy ) const;
        
        Node*
        mergeSubTrees( Node* t1, Node* t2 );
        
        Node*
        getLCA( Node* n1, Node* n2 );
        
        const Node*
        getLCA( const Node* n1, const Node* n2 ) const;
        
        Node*
        checkIfObsolete( Node* n );
        
    public:
        
        void
        write_PStree(  std::ostream& out, const size_t maxLeaves2print = UINT_MAX ) ; 
        
    protected:  
        
        class nodeT {
        public:
            nodeT() : height(0.0), saddle_height(0.0), father(INT_MAX), label(NULL) {}
          float height;         /* height (energy, time, whatever) of this leaf    */
          float saddle_height;  /* height of internal node that connects this leaf */
          int father;           /* node with which it connects                     */
          char *label;          /* label string, if NULL use index+1               */ 
        };

        class linkT {
        public:
            linkT() : x(0), next(NULL) {}
          int x;
          linkT *next;
        };

        static void PS_tree_plot(   std::ostream& out
                                    , const std::vector<nodeT> &nodes
                                    );
        
        class cmp_saddle {
        public:
            cmp_saddle(const std::vector<nodeT> *leaves_) : leaves(leaves_) {}
            const std::vector<nodeT> *leaves;
            bool operator() (int A,int B);
        };

    };

} // namespace ell

//##############################################################################

  // include inline implementation
#include "ell/LT_BarrierTree.icc"

//##############################################################################

#endif /*LT_BARRIERTREE_HH_*/