tree_algo.hpp

来自「ncbi源码」· HPP 代码 · 共 898 行 · 第 1/2 页

/// Create set of all sub-nodes (recursively)
/// 
/// @param tree_node
///    root node
/// @param back_ins
///   Back insert iterator (represents set)
///
template<class TNode, class TBackInsert>
void TreeMakeSet(const TNode& tree_node, TBackInsert back_ins)
{
    TNode* node = const_cast<TNode*>(&tree_node);
    CTreeIdToSetFunc<TNode, TBackInsert> func(back_ins);
    TreeDepthFirstTraverse(*node, func);
}

/// Create set of all immediate sub-nodes (one level down from the root)
/// 
/// @param tree_node
///    root node
/// @param back_ins
///   Back insert iterator (represents set)
///
template<class TNode, class TBackInsert>
void TreeMakeSubNodesSet(const TNode& tree_node, TBackInsert back_ins)
{
    typename TNode::TNodeList_CI it     = tree_node.SubNodeBegin();
    typename TNode::TNodeList_CI it_end = tree_node.SubNodeEnd();

    for(;it != it_end; ++it) {
        const TNode* node = *it;
        *back_ins = node->GetValue().GetId();
        ++back_ins;
    }
}



/// Functor to convert tree to a nodelist by the set pattern
///
/// @internal
template<class TTreeNode, class TSet, class TNodeList>
class CTreeSet2NodeListFunc
{
public:
    CTreeSet2NodeListFunc(const TSet& node_set, TNodeList* node_list)
    : m_NodeSet(node_set),
      m_NodeList(node_list)
    {}

    ETreeTraverseCode operator()(const TTreeNode& node, 
                                 int              delta_level=0)
    {
        if (delta_level >= 0) {
            unsigned id = node.GetValue().GetId();
            bool b = m_NodeSet[id];
            if (b) {
                m_NodeList->push_back(&node);
            }
        }
        return eTreeTraverse;
    }

private:
    const TSet&   m_NodeSet;
    TNodeList*    m_NodeList;
};




/// Convert set of node ids to list of nodes
///
/// Traverses the tree, if node is in the set adds node pointer to 
/// the nodelist.
///
template<class TNode, class TSet, class TNodeList>
void TreeSetToNodeList(const TNode&  tree_node, 
                       const TSet&   node_set, 
                       TNodeList&    nlist)
{
    TNode* node = const_cast<TNode*>(&tree_node);
    CTreeSet2NodeListFunc<TNode, TSet, TNodeList> func(node_set, &nlist);
    TreeDepthFirstTraverse(node, func);
}



/// Class-algorithm to compute Non Redundant Set
///
/// Takes a single nodelist as an arguiment and copies every node
/// which has no ancestors in the source set. 
/// @note Result set might be not minimal
///
template<class TNode, class TSet, class TNodeList>
class CTreeNonRedundantSet
{
public:
    void operator()(const TNodeList& src_nlist,
                    TNodeList&       dst_nlist)
    {
        TSet src_set;
        TreeListToSet(src_nlist, src_set.inserter());

        TSet ancestor_set;

        ITERATE(typename TNodeList, it, src_nlist) {
            TNode* snode = *it;

            ancestor_set.clear();

            TreeMakeParentsSet(*snode, ancestor_set.inserter());

            ancestor_set &= src_set;
            unsigned cnt = ancestor_set.count();

            if (cnt == 0) { // source set contains no ancestors of the node
                // node is part of the non redundant set
                dst_nlist.push_back(snode);
            }

        } // ITERATE
    }

};

/// Functor takes a single nodelist as an argument and tries to
/// push that nodelist as high as it can. If all of the childred 
/// of a given node are in the nodelist, the children are removed from 
/// the nodelist and the parent is added. The process is repeated util
/// it cannot be reduced anymore.
///
template<class TNode, class TSet, class TNodeList>
class CTreeMinimalSet
{
public:

    /// Compute minimal set.
    ///
    /// @param src_nlist
    ///    Source node list
    /// @param dst_nlist
    ///    Destination node list
    /// @param ignore_set
    ///    Set of node ids to ignore when we do reduction
    ///
    void operator()(const TNodeList& src_nlist,
                    TNodeList&       dst_nlist,
                    const TSet*      ignore_set = 0)
    {
        MinimalSet(src_nlist, dst_nlist, ignore_set);
    }


protected:

    // The main workhorse function
    void MinimalSet(const TNodeList& src_nlist,
                    TNodeList&       dst_nlist,
                    const TSet*      ignore_set = 0)
    {
        TSet src_set;
        TreeListToSet(src_nlist, src_set.inserter());

        TSet child_set;
        TSet tmp_set;

        bool moved_up; // flag that group of nodes got substituted for parent

        do {
            moved_up = 
                CheckNodeList(src_nlist, dst_nlist, 
                              src_set,   tmp_set, child_set, ignore_set);

            if (moved_up) {
                moved_up =
                 CheckNodeList(dst_nlist, dst_nlist, 
                               src_set,   tmp_set, child_set, ignore_set);
            }
        } while (moved_up); // repeat while we can move nodes up

        loop_restart:

        // clean the destination node list from reduced parents
        NON_CONST_ITERATE(typename TNodeList, it, dst_nlist) {
            TNode* snode = *it;
            unsigned id = snode->GetValue().GetId();

            // check if node was excluded from the source set
            bool b = src_set[id];
            if (!b) {
                dst_nlist.erase(it);
                goto loop_restart;
            }
        }

        // add non reduced source nodes to the destination list
        ITERATE(typename TNodeList, it, src_nlist) {
            TNode* snode = *it;
            unsigned id = snode->GetValue().GetId();

            bool b = src_set[id];
            if (b) {
                dst_nlist.push_back(snode);
            }            
        }

    }


    bool CheckNodeList(const TNodeList& nlist, 
                       TNodeList&       dst_nlist,
                       TSet&            src_set,
                       TSet&            tmp_set,
                       TSet&            child_set,
                       const TSet*      ignore_set)
    {
        TNodeList  tmp_nlist; // (to avoid problems when &nlist == &dst_nlist)

        bool promo_flag = false;

        ITERATE(typename TNodeList, it, nlist) {
            TNode* snode = *it;

            unsigned id = snode->GetValue().GetId();
            TNode* parent = snode->GetParent();

            // check if node was excluded from the source set
            bool b = src_set[id];
            if (!b || (parent == 0)) 
                continue;

            unsigned parent_id = parent->GetValue().GetId();

            child_set.clear();
            // Add immediate subnodes
            TreeMakeSubNodesSet(*parent, child_set.inserter());
            tmp_set = child_set;
            tmp_set -= src_set;

            if (ignore_set) {
                tmp_set -= *ignore_set;
            }

            if (tmp_set.none()) {  // we can move up to the parent

                // Add ALL subordinate node, not just children
                TreeMakeSet(*parent, child_set.inserter());

                src_set -= child_set;
                
                bool parent_in = src_set[parent_id];

                if (!parent_in) {
                    src_set[parent_id] = true;
                    //
                    // precautionary measure: make sure we do not 
                    // invalidate the source iterator 
                    // (TNodeList can be a vector)
                    //
                    if (&nlist != &dst_nlist) {
                        dst_nlist.push_back(parent);
                    } else {
                        tmp_nlist.push_back(parent);
                    }
                }
                promo_flag = true;
            }

        } // ITERATE

        // copy temp node list to the dst set
        //
        ITERATE(typename TNodeList, it, tmp_nlist) {
            TNode* snode = *it;
            dst_nlist.push_back(snode);
        }
        return promo_flag;
    }

};

/// Utility to join to node lists according to a set of ids
template<class TNode, class TSet, class TNodeList>
class CNodesToBitset
{
public:
    /// Join two node lists
    ///
    /// @param src_nlist_a
    ///    node list 1
    /// @param src_nlist_b
    ///    node list 2
    /// @param mask_set
    ///    subset of two nodelists assigns nodes coming to dst_list
    /// @param dst_list
    ///    destination node list
    /// @param dst_set
    ///    auxiliary set used to track in target set
    ///    (to make sure we will have non repeated list of nodes)
    void JoinNodeList(const TNodeList&  src_nlist_a,
                      const TNodeList&  src_nlist_b,
                      const TSet&       mask_set,
                      TNodeList&        dst_list,
                      TSet&             dst_set)
    {
        dst_set.clear();

        MaskCopyNodes(src_nlist_a, mask_set, dst_list, dst_set);
        unsigned dst_count = dst_set.count();
        unsigned src_count = mask_set.count();

        if (src_count != dst_count) {
            MaskCopyNodes(src_nlist_b, mask_set, dst_list, dst_set);
        }
    }

    /// Copy nodes from the source node list to destination
    /// if nodes are in the mask set and not yet in the destination set
    void MaskCopyNodes(const TNodeList&  src_nlist,
                       const TSet&       mask_set,
                       TNodeList&        dst_list,
                       TSet&             dst_set)
    {
        ITERATE(typename TNodeList, it, src_nlist) {
            unsigned id = (*it)->GetValue().GetId();
            bool exists = mask_set[id];
            if (exists) {
                exists = dst_set[id];
                if (!exists) {
                    dst_list.push_back(*it);
                    dst_set.set(id);
                }
            }
        } // ITERATE
    }

};


/// Node list AND (set intersection)
template<class TNode, class TSet, class TNodeList>
class CTreeNodesAnd
{
public:
    void operator()(const TNodeList& src_nlist_a,
                    const TNodeList& src_nlist_b,
                    TNodeList&       dst_nlist)
    {
        TSet tmp_set;
        this->operator()(src_nlist_a, src_nlist_b, dst_nlist, tmp_set);
    }

    void operator()(const TNodeList& src_nlist_a,
                    const TNodeList& src_nlist_b,
                    TNodeList&       dst_nlist,
                    TSet&            dst_set)
    {
        TSet set_a;
        TreeListToSet(src_nlist_a, set_a.inserter());

        {{
        TSet set_b;
        TreeListToSet(src_nlist_b, set_b.inserter());        
        set_a &= set_b;
        }}


        CNodesToBitset<TNode, TSet, TNodeList> merge_func;
        merge_func.JoinNodeList(src_nlist_a, src_nlist_b, set_a, 
                                dst_nlist, dst_set);
    }
};         


/// Node list OR (set union)
template<class TNode, class TSet, class TNodeList>
class CTreeNodesOr
{
public:
    void operator()(const TNodeList& src_nlist_a,
                    const TNodeList& src_nlist_b,
                    TNodeList&       dst_nlist)
    {
        TSet tmp_set;
        this->operator()(src_nlist_a, src_nlist_b, dst_nlist, tmp_set);
    }

    void operator()(const TNodeList& src_nlist_a,
                    const TNodeList& src_nlist_b,
                    TNodeList&       dst_nlist,
                    TSet&            dst_set)
    {
        TSet set_a;
        TreeListToSet(src_nlist_a, set_a.inserter());

        {{
        TSet set_b;
        TreeListToSet(src_nlist_b, set_b.inserter());        
        set_a |= set_b;
        }}


        CNodesToBitset<TNode, TSet, TNodeList> merge_func;
        merge_func.JoinNodeList(src_nlist_a, src_nlist_b, set_a, 
                                dst_nlist, dst_set);
    }
};         


/* @} */

END_NCBI_SCOPE


/*
 * ===========================================================================
 * $Log: tree_algo.hpp,v $
 * Revision 1000.2  2004/06/01 18:04:35  gouriano
 * PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.7
 *
 * Revision 1.7  2004/04/27 12:39:34  kuznets
 * Minimal set changed to work with ignore list of ids
 *
 * Revision 1.6  2004/04/22 17:58:07  kuznets
 * + more comments on minimal set
 *
 * Revision 1.5  2004/04/22 13:52:09  kuznets
 * + CTreeMinimalSet
 *
 * Revision 1.4  2004/04/21 16:42:18  kuznets
 * + AND, OR operations on node lists
 *
 * Revision 1.3  2004/04/21 13:27:18  kuznets
 * Bug fix: typename in templates
 *
 * Revision 1.2  2004/04/21 12:56:34  kuznets
 * Added tree related algorithms and utilities based on sets algebra
 * (TreeListToSet, TreeMakeParentsSet, TreeMakeSet, TreeSetToNodeList
 * CTreeNonRedundantSet)
 *
 * Revision 1.1  2004/04/19 16:02:06  kuznets
 * Initial revision. Migrated from <corelib/ncbi_tree.hpp>
 *
 *
 * ==========================================================================
 */

#endif