ctreecont.hpp
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:13k
- /*
- * ===========================================================================
- * PRODUCTION $Log: ctreecont.hpp,v $
- * PRODUCTION Revision 1000.1 2004/04/12 17:27:06 gouriano
- * PRODUCTION PRODUCTION: UPGRADED [CATCHUP_003] Dev-tree R6.6
- * PRODUCTION
- * ===========================================================================
- */
- #ifndef NCBI_OBJECTS_CTREECONT_HPP
- #define NCBI_OBJECTS_CTREECONT_HPP
- /* $Id: ctreecont.hpp,v 1000.1 2004/04/12 17:27:06 gouriano Exp $
- * ===========================================================================
- *
- * PUBLIC DOMAIN NOTICE
- * National Center for Biotechnology Information
- *
- * This software/database is a "United States Government Work" under the
- * terms of the United States Copyright Act. It was written as part of
- * the author's official duties as a United States Government employee and
- * thus cannot be copyrighted. This software/database is freely available
- * to the public for use. The National Library of Medicine and the U.S.
- * Government have not placed any restriction on its use or reproduction.
- *
- * Although all reasonable efforts have been taken to ensure the accuracy
- * and reliability of the software and data, the NLM and the U.S.
- * Government do not and cannot warrant the performance or results that
- * may be obtained by using this software or data. The NLM and the U.S.
- * Government disclaim all warranties, express or implied, including
- * warranties of performance, merchantability or fitness for any particular
- * purpose.
- *
- * Please cite the author in any work or product based on this material.
- *
- * ===========================================================================
- *
- * File Name: CTreeCont.hpp
- *
- * Author: Vladimir Soussov, Yuri Sadykov, Michael Domrachev
- *
- * File Description: General purpose tree container
- *
- */
- #include <corelib/ncbistl.hpp>
- #include <objects/taxon1/taxon1.hpp>
- BEGIN_NCBI_SCOPE
- #ifndef BEGIN_objects_SCOPE
- # define BEGIN_objects_SCOPE BEGIN_SCOPE(objects)
- # define END_objects_SCOPE END_SCOPE(objects)
- #endif
- BEGIN_objects_SCOPE // namespace ncbi::objects::
- class CTreeIterator;
- class CTreeConstIterator;
- class CTreeCont;
- class CTreeContNodeBase {
- friend class CTreeIterator;
- friend class CTreeConstIterator;
- friend class CTreeCont;
- public:
- //////////////////////////////////////////////////////////////
- // the following method are used by tree manipulation methods
- // from CTreeCursor and CTree classes
- //////////////////////////////////////////////////////////////
- CTreeContNodeBase() {
- m_parent= m_sibling= m_child= 0;
- }
- bool IsTerminal() const {
- return (m_child == 0);
- }
- bool IsRoot() const {
- return (m_parent == 0);
- }
- bool IsLastChild() const {
- return (m_sibling == 0);
- }
- bool IsFirstChild() const {
- return ((m_parent == 0) || (m_parent->m_child == this));
- }
- void Merge( CTreeContNodeBase* ) {}
- const CTreeContNodeBase* Parent() const { return m_parent; }
- const CTreeContNodeBase* Sibling() const { return m_sibling; }
- const CTreeContNodeBase* Child() const { return m_child; }
- protected:
- CTreeContNodeBase* Parent() { return m_parent; }
- CTreeContNodeBase* Sibling() { return m_sibling; }
- CTreeContNodeBase* Child() { return m_child; }
- virtual ~CTreeContNodeBase(){};
- private:
- CTreeContNodeBase* m_parent;
- CTreeContNodeBase* m_sibling;
- CTreeContNodeBase* m_child;
- };
- class CTreeCont {
- friend class CTreeIterator;
- friend class CTreeConstIterator;
- public:
- CTreeCont() {
- m_root= 0;
- }
- CTreeIterator* GetIterator();
- CTreeConstIterator* GetConstIterator() const;
- bool SetRoot(CTreeContNodeBase* root) {
- if((!m_root) && root) {
- m_root= root;
- m_root->m_parent= m_root->m_sibling= m_root->m_child= 0;
- }
- return (m_root == root);
- }
- const CTreeContNodeBase* GetRoot() const {
- return m_root;
- }
- bool AddNode(CTreeContNodeBase* pParentNode, CTreeContNodeBase* pNewNode);
- void Clear() { if (m_root) { DelNodeInternal(m_root); m_root = 0; } }
- ~CTreeCont();
- private:
- CTreeContNodeBase* m_root;
- // CPntrPot m_cursorPot;
- // CPntrPot m_spyPot;
- void DeleteSubtree(CTreeContNodeBase* stroot, CTreeIterator* pCur);
- void Done(CTreeContNodeBase* node);
- void MoveNode(CTreeContNodeBase* node2move, CTreeContNodeBase* new_parent);
- void MoveChildren(CTreeContNodeBase* old_parent, CTreeContNodeBase* new_parent);
- void Merge(CTreeContNodeBase* src, CTreeContNodeBase* dst, CTreeIterator* pCur);
- void AddChild(CTreeContNodeBase* parent);
- void DelNodeInternal(CTreeContNodeBase* pN);
- };
- class CTreeIterator {
- public:
- // navigation
- void GoRoot() {// move cursor to the root node
- m_node= m_tree->m_root;
- }
- bool GoParent() {// move cursor to the parent node
- if(m_node->m_parent) {
- m_node= m_node->m_parent;
- return true;
- }
- return false;
- }
- bool GoChild() { // move cursor to the child node
- if(m_node->m_child) {
- m_node= m_node->m_child;
- return true;
- }
- return false;
- }
- bool GoSibling() { // move cursor to the sibling node
- if(m_node->m_sibling) {
- m_node= m_node->m_sibling;
- return true;
- }
- return false;
- }
- bool GoNode(CTreeContNodeBase* node) { // move cursor to the node with given node_id
- if(node) {
- m_node= node;
- return true;
- }
- return false;
- }
- bool GoAncestor(CTreeContNodeBase* node); // move cursor to the nearest common ancestor
- // between node pointed by cursor and the node
- // with given node_id
- // callback for ForEachNodeInSubtree method
- // this function should return eStop if it wants to abandon the nodes scanning
- // or eBreak to abandon scanning of subtree belonging to the current node
- enum EAction {
- eCont, // Continue scan
- eStop, // Stop scanning, exit immediately
- eSkip // Skip current node's subree and continue scanning
- };
- typedef EAction (*ForEachFunc)(CTreeContNodeBase* pNode, void* user_data);
- // "Callback" class for traversing the tree.
- // For 'downward' traverse node (nodes that closer to root processed first)
- // order of execution is: execute(), levelBegin(), and levelEnd(). Latter
- // two functions are called only when node has children.
- // For 'upward' traverse node (nodes that closer to leaves processed first)
- // order of execution is: levelBegin(), levelEnd(), and execute(). Former
- // two functions are called only when node has children.
- class C4Each {
- public:
- virtual EAction LevelBegin(CTreeContNodeBase* /*pParent*/)
- { return eCont; }
- virtual EAction Execute(CTreeContNodeBase* pNode)= 0;
- virtual EAction LevelEnd(CTreeContNodeBase* /*pParent*/)
- { return eCont; }
- };
- // iterator through subtree.
- // it calls the ucb function one time for each node in given subtree
- // (including subtree root)
- // to abandon scanning ucb should return eStop.
- // (the iterator will stay on node which returns this code)
- // 'Downward' traverse functions (nodes that closer to root processed first)
- EAction ForEachDownward(ForEachFunc ucb, void* user_data);
- EAction ForEachDownward(C4Each&);
- EAction ForEachDownwardLimited(ForEachFunc ucb, void* user_data, int levels);
- EAction ForEachDownwardLimited(C4Each&, int levels);
- // 'Upward' traverse node (nodes that closer to leaves processed first)
- EAction ForEachUpward(ForEachFunc ucb, void* user_data);
- EAction ForEachUpward(C4Each&);
- EAction ForEachUpwardLimited(ForEachFunc ucb, void* user_data, int levels);
- EAction ForEachUpwardLimited(C4Each&, int levels);
- // modification of tree
- class CSortPredicate {
- public:
- virtual bool Execute( CTreeContNodeBase* p1, CTreeContNodeBase* p2 )=0;
- };
- // add child to a node pointed by cursor
- bool AddChild(CTreeContNodeBase* new_node);
- // add sibling AFTER a node pointed by cursor
- bool AddSibling(CTreeContNodeBase* new_node);
- // add child preserving the sorted order
- bool AddChild(CTreeContNodeBase* new_node, CSortPredicate& );
- void SortChildren( CSortPredicate& );
- void SortAllChildrenInSubtree( CSortPredicate& );
- //bool updateNode(const void* node_data, int node_data_size);
- bool DeleteNode(); // delete node pointed by cursor (cursor will be moved to the parent node in the end)
- bool DeleteSubtree(); // delete subtree pointed by cursor (cursor will be moved to the parent node in the end)
- bool MoveNode(CTreeContNodeBase* to_node); // move the node (subtree) pointed by cursor
- // to the new parent with given node_id
- bool MoveChildren(CTreeContNodeBase* to_node); // move children from the node pointed by cursor
- // to the new parent with given node_id
- bool Merge(CTreeContNodeBase* to_node); // merge node pointed by cursor with the node
- // with given node_id
- // notify others about update
- void NodeUpdated() {
- m_tree->Done(m_node);
- }
- // retrieval
- CTreeContNodeBase* GetNode() const {return m_node;}
- bool BelongSubtree(const CTreeContNodeBase* subtree_root); // check if node pointed by cursor
- // is belong to subtree wich root node
- // has given node_id
- bool AboveNode(CTreeContNodeBase* node); // check if node with given node_id belongs
- // to subtree pointed by cursor
- CTreeIterator(CTreeCont* tree) {
- m_tree= tree;
- // tree->m_cursorPot.add((PotItem)this);
- GoRoot();
- }
- ~CTreeIterator() {
- // m_tree->m_cursorPot.remove((PotItem)this);
- }
- private:
- CTreeIterator() {}
- CTreeContNodeBase* m_node;
- class CTreeCont* m_tree;
- };
- class CTreeConstIterator {
- public:
- // navigation
- void GoRoot() {// move cursor to the root node
- m_node= m_tree->m_root;
- }
- bool GoParent() {// move cursor to the parent node
- if(m_node->m_parent) {
- m_node= m_node->m_parent;
- return true;
- }
- return false;
- }
- bool GoChild() { // move cursor to the child node
- if(m_node->m_child) {
- m_node= m_node->m_child;
- return true;
- }
- return false;
- }
- bool GoSibling() { // move cursor to the sibling node
- if(m_node->m_sibling) {
- m_node= m_node->m_sibling;
- return true;
- }
- return false;
- }
- bool GoNode(const CTreeContNodeBase* pNode) {
- if(pNode) {
- m_node= pNode;
- return true;
- }
- return false;
- }
- bool GoAncestor(const CTreeContNodeBase* node); // move cursor to the nearest common ancestor
- // between node pointed by cursor and the node
- // with given node_id
- // retrieval
- const CTreeContNodeBase* GetNode() const
- {return m_node;}
- // check if node pointed by cursor
- // is belong to subtree wich root node
- // has given node_id
- bool BelongSubtree(const CTreeContNodeBase* subtree_root) const;
- // check if node with given node_id belongs
- // to subtree pointed by cursor
- bool AboveNode(const CTreeContNodeBase* node) const;
- CTreeConstIterator(const CTreeCont* tree)
- : m_node( tree->m_root ), m_tree( tree ) {
- //tree->m_cursorPot.add((PotItem)this);
- //goRoot();
- }
- virtual ~CTreeConstIterator() {
- //m_tree->m_cursorPot.remove((PotItem)this);
- }
- private:
- CTreeConstIterator(){}
- const CTreeContNodeBase* m_node;
- const CTreeCont* m_tree;
- };
- END_objects_SCOPE // namespace ncbi::objects::
- END_NCBI_SCOPE
- /*
- * $Log: ctreecont.hpp,v $
- * Revision 1000.1 2004/04/12 17:27:06 gouriano
- * PRODUCTION: UPGRADED [CATCHUP_003] Dev-tree R6.6
- *
- * Revision 6.6 2004/02/04 16:14:44 domrach
- * New iterator types (modes of operation) are introduced. They include:
- * full tree, branches'n'leaves, best, and blast. Position inquiry f-ns
- * IsTerminal(), IsFirstChild(), and IsLastChild() has been moved from
- * ITreeNode to ITreeIterator. Node loading f-ns() now return the ITreeNode
- * for tax id.
- *
- * Revision 6.5 2003/05/09 22:08:15 domrach
- * Destructor of CTreeContNodeBase made virtual
- *
- * Revision 6.4 2003/05/08 16:00:07 ucko
- * Remove inappropriate dynamic_cast<>.
- *
- * Revision 6.3 2003/05/06 19:53:53 domrach
- * New functions and interfaces for traversing the cached partial taxonomy tree introduced. Convenience functions GetDivisionName() and GetRankName() were added
- *
- * Revision 6.2 2003/01/21 19:37:19 domrach
- * GetRoot method added to CTreeCont class.
- *
- * Revision 6.1 2002/01/30 16:13:37 domrach
- * Changes made to pass through MSVC compiler. Some src files renamed
- *
- * Revision 6.1 2002/01/28 19:56:11 domrach
- * Initial checkin of the library implementation files
- *
- */
- #endif // NCBI_OBJECTS_CTREECONT_HPP