ctreecont.hpp
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:13k
源码类别:

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: ctreecont.hpp,v $
  4.  * PRODUCTION Revision 1000.1  2004/04/12 17:27:06  gouriano
  5.  * PRODUCTION PRODUCTION: UPGRADED [CATCHUP_003] Dev-tree R6.6
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. #ifndef NCBI_OBJECTS_CTREECONT_HPP
  10. #define NCBI_OBJECTS_CTREECONT_HPP
  11. /*  $Id: ctreecont.hpp,v 1000.1 2004/04/12 17:27:06 gouriano Exp $
  12. * ===========================================================================
  13. *
  14. *                            PUBLIC DOMAIN NOTICE
  15. *               National Center for Biotechnology Information
  16. *
  17. *  This software/database is a "United States Government Work" under the
  18. *  terms of the United States Copyright Act.  It was written as part of
  19. *  the author's official duties as a United States Government employee and
  20. *  thus cannot be copyrighted.  This software/database is freely available
  21. *  to the public for use. The National Library of Medicine and the U.S.
  22. *  Government have not placed any restriction on its use or reproduction.
  23. *
  24. *  Although all reasonable efforts have been taken to ensure the accuracy
  25. *  and reliability of the software and data, the NLM and the U.S.
  26. *  Government do not and cannot warrant the performance or results that
  27. *  may be obtained by using this software or data. The NLM and the U.S.
  28. *  Government disclaim all warranties, express or implied, including
  29. *  warranties of performance, merchantability or fitness for any particular
  30. *  purpose.
  31. *
  32. *  Please cite the author in any work or product based on this material.
  33. *
  34. * ===========================================================================
  35. *
  36. * File Name:  CTreeCont.hpp
  37. *
  38. * Author:  Vladimir Soussov, Yuri Sadykov, Michael Domrachev
  39. *
  40. * File Description: General purpose tree container
  41. *
  42. */
  43. #include <corelib/ncbistl.hpp>
  44. #include <objects/taxon1/taxon1.hpp>
  45. BEGIN_NCBI_SCOPE
  46. #ifndef BEGIN_objects_SCOPE
  47. #  define BEGIN_objects_SCOPE BEGIN_SCOPE(objects)
  48. #  define END_objects_SCOPE END_SCOPE(objects)
  49. #endif
  50. BEGIN_objects_SCOPE // namespace ncbi::objects::
  51. class CTreeIterator;
  52. class CTreeConstIterator;
  53. class CTreeCont;
  54. class CTreeContNodeBase  {
  55.     friend class CTreeIterator;
  56.     friend class CTreeConstIterator;
  57.     friend class CTreeCont;
  58. public:
  59.     //////////////////////////////////////////////////////////////
  60.     // the following method are used by tree manipulation methods
  61.     // from CTreeCursor and CTree classes
  62.     //////////////////////////////////////////////////////////////
  63.     CTreeContNodeBase() {
  64. m_parent= m_sibling= m_child= 0;
  65.     }
  66.     bool IsTerminal() const {
  67. return (m_child == 0);
  68.     }
  69.     bool IsRoot() const {
  70. return (m_parent == 0);
  71.     }
  72.     bool IsLastChild() const {
  73. return (m_sibling == 0);
  74.     }
  75.     bool IsFirstChild() const {
  76. return ((m_parent == 0) || (m_parent->m_child == this));
  77.     }
  78.     void Merge( CTreeContNodeBase* ) {}
  79.     const CTreeContNodeBase* Parent() const  { return m_parent;  }
  80.     const CTreeContNodeBase* Sibling() const { return m_sibling; }
  81.     const CTreeContNodeBase* Child() const   { return m_child;   }
  82. protected:
  83.     CTreeContNodeBase*       Parent()        { return m_parent;  }
  84.     CTreeContNodeBase*       Sibling()       { return m_sibling; }
  85.     CTreeContNodeBase*       Child()         { return m_child;   }
  86.     virtual ~CTreeContNodeBase(){};
  87. private:
  88.     CTreeContNodeBase* m_parent;
  89.     CTreeContNodeBase* m_sibling;
  90.     CTreeContNodeBase* m_child;
  91. };
  92. class CTreeCont {
  93. friend class CTreeIterator;
  94. friend class CTreeConstIterator;
  95. public:
  96.     CTreeCont() {
  97. m_root= 0;
  98.     }
  99.     CTreeIterator*      GetIterator();
  100.     CTreeConstIterator* GetConstIterator() const;
  101.     bool SetRoot(CTreeContNodeBase* root) {
  102. if((!m_root) && root) {
  103.     m_root= root;
  104.     m_root->m_parent= m_root->m_sibling= m_root->m_child= 0;
  105. }
  106. return (m_root == root);
  107.     }
  108.     const CTreeContNodeBase* GetRoot() const {
  109. return m_root;
  110.     }
  111.     bool AddNode(CTreeContNodeBase* pParentNode, CTreeContNodeBase* pNewNode);
  112.     void Clear()    { if (m_root) { DelNodeInternal(m_root); m_root = 0; } }
  113.     ~CTreeCont();
  114. private:
  115.     CTreeContNodeBase* m_root;
  116. //    CPntrPot m_cursorPot;
  117. //    CPntrPot m_spyPot;
  118.     void DeleteSubtree(CTreeContNodeBase* stroot, CTreeIterator* pCur);
  119.     void Done(CTreeContNodeBase* node);
  120.     void MoveNode(CTreeContNodeBase* node2move, CTreeContNodeBase* new_parent);
  121.     void MoveChildren(CTreeContNodeBase* old_parent, CTreeContNodeBase* new_parent);
  122.     void Merge(CTreeContNodeBase* src, CTreeContNodeBase* dst, CTreeIterator* pCur);
  123.     void AddChild(CTreeContNodeBase* parent);
  124.     void DelNodeInternal(CTreeContNodeBase* pN);
  125. };
  126. class CTreeIterator {
  127. public:
  128.     // navigation
  129.     void GoRoot() {// move cursor to the root node
  130. m_node= m_tree->m_root;
  131.     }
  132.     bool GoParent() {// move cursor to the parent node
  133. if(m_node->m_parent) {
  134.     m_node= m_node->m_parent;
  135.     return true;
  136. }
  137. return false;
  138.     }
  139.     bool GoChild() { // move cursor to the child node
  140. if(m_node->m_child) {
  141.     m_node= m_node->m_child;
  142.     return true;
  143. }
  144. return false;
  145.     }
  146.     bool GoSibling() { // move cursor to the sibling node
  147. if(m_node->m_sibling) {
  148.     m_node= m_node->m_sibling;
  149.     return true;
  150. }
  151. return false;
  152.     }
  153.     bool GoNode(CTreeContNodeBase* node) { // move cursor to the node with given node_id
  154. if(node) {
  155.     m_node= node;
  156.     return true;
  157. }
  158. return false;
  159.     }
  160.     bool GoAncestor(CTreeContNodeBase* node); // move cursor to the nearest common ancestor
  161.                                      // between node pointed by cursor and the node
  162.                                      // with given node_id
  163.     // callback for ForEachNodeInSubtree method
  164.     // this function should return eStop if it wants to abandon the nodes scanning
  165.     // or eBreak to abandon scanning of subtree belonging to the current node
  166.     enum EAction {
  167. eCont,   // Continue scan
  168. eStop,   // Stop scanning, exit immediately
  169. eSkip   // Skip current node's subree and continue scanning
  170.     };
  171.     typedef EAction (*ForEachFunc)(CTreeContNodeBase* pNode, void* user_data);
  172.     // "Callback" class for traversing the tree.
  173.     // For 'downward' traverse node (nodes that closer to root processed first)
  174.     // order of execution is: execute(), levelBegin(), and levelEnd(). Latter
  175.     // two functions are called only when node has children.
  176.     // For 'upward' traverse node (nodes that closer to leaves processed first)
  177.     // order of execution is: levelBegin(), levelEnd(), and execute(). Former
  178.     // two functions are called only when node has children.
  179.     class C4Each {
  180.     public:
  181. virtual EAction LevelBegin(CTreeContNodeBase* /*pParent*/)
  182. { return eCont; }
  183. virtual EAction Execute(CTreeContNodeBase* pNode)= 0;
  184. virtual EAction LevelEnd(CTreeContNodeBase* /*pParent*/)
  185. { return eCont; }
  186.     };
  187.     // iterator through subtree.
  188.     // it calls the ucb function one time for each node in given subtree
  189.     // (including subtree root)
  190.     // to abandon scanning ucb should return eStop.
  191.     // (the iterator will stay on node which returns this code)
  192.     // 'Downward' traverse functions (nodes that closer to root processed first)
  193.     EAction ForEachDownward(ForEachFunc ucb, void* user_data);
  194.     EAction ForEachDownward(C4Each&);
  195.     EAction ForEachDownwardLimited(ForEachFunc ucb, void* user_data, int levels);
  196.     EAction ForEachDownwardLimited(C4Each&, int levels);
  197.     // 'Upward' traverse node (nodes that closer to leaves processed first)
  198.     EAction ForEachUpward(ForEachFunc ucb, void* user_data);
  199.     EAction ForEachUpward(C4Each&);
  200.     EAction ForEachUpwardLimited(ForEachFunc ucb, void* user_data, int levels);
  201.     EAction ForEachUpwardLimited(C4Each&, int levels);
  202.     // modification of tree
  203.     class CSortPredicate {
  204.     public:
  205. virtual bool Execute( CTreeContNodeBase* p1, CTreeContNodeBase* p2 )=0;
  206.     };
  207.     // add child to a node pointed by cursor
  208.     bool AddChild(CTreeContNodeBase* new_node);
  209.     // add sibling AFTER a node pointed by cursor
  210.     bool AddSibling(CTreeContNodeBase* new_node);
  211.     // add child preserving the sorted order
  212.     bool AddChild(CTreeContNodeBase* new_node, CSortPredicate& );
  213.     void SortChildren( CSortPredicate& );
  214.     void SortAllChildrenInSubtree( CSortPredicate& );
  215.     //bool updateNode(const void* node_data, int node_data_size);
  216.     bool DeleteNode(); // delete node pointed by cursor (cursor will be moved to the parent node in the end)
  217.     bool DeleteSubtree(); // delete subtree pointed by cursor (cursor will be moved to the parent node in the end)
  218.     bool MoveNode(CTreeContNodeBase* to_node); // move the node (subtree) pointed by cursor
  219.                                         // to the new parent with given node_id
  220.     bool MoveChildren(CTreeContNodeBase* to_node); // move children from the node pointed by cursor
  221.                                             // to the new parent with given node_id
  222.     bool Merge(CTreeContNodeBase* to_node); // merge node pointed by cursor with the node
  223.                                      // with given node_id
  224.     // notify others about update
  225.     void NodeUpdated() {
  226. m_tree->Done(m_node);
  227.     }
  228.     // retrieval
  229.     CTreeContNodeBase* GetNode() const {return m_node;}
  230.     bool BelongSubtree(const CTreeContNodeBase* subtree_root); // check if node pointed by cursor
  231.                                                   // is belong to subtree wich root node
  232.                                                   // has given node_id
  233.     bool AboveNode(CTreeContNodeBase* node); // check if node with given node_id belongs
  234.                                     // to subtree pointed by cursor
  235.     CTreeIterator(CTreeCont* tree) {
  236. m_tree= tree;
  237. // tree->m_cursorPot.add((PotItem)this);
  238. GoRoot();
  239.     }
  240.     ~CTreeIterator() {
  241. // m_tree->m_cursorPot.remove((PotItem)this);
  242.     }
  243. private:
  244.     CTreeIterator() {}
  245.     CTreeContNodeBase* m_node;
  246.     class CTreeCont*   m_tree;
  247. };
  248. class CTreeConstIterator {
  249. public:
  250.     // navigation
  251.     void GoRoot() {// move cursor to the root node
  252. m_node= m_tree->m_root;
  253.     }
  254.     bool GoParent() {// move cursor to the parent node
  255. if(m_node->m_parent) {
  256.     m_node= m_node->m_parent;
  257.     return true;
  258. }
  259. return false;
  260.     }
  261.     bool GoChild() { // move cursor to the child node
  262. if(m_node->m_child) {
  263.     m_node= m_node->m_child;
  264.     return true;
  265. }
  266. return false;
  267.     }
  268.     bool GoSibling() { // move cursor to the sibling node
  269. if(m_node->m_sibling) {
  270.     m_node= m_node->m_sibling;
  271.     return true;
  272. }
  273. return false;
  274.     }
  275.     bool GoNode(const CTreeContNodeBase* pNode) {
  276. if(pNode) {
  277.     m_node= pNode;
  278.     return true;
  279. }
  280. return false;
  281.     }
  282.     bool GoAncestor(const CTreeContNodeBase* node); // move cursor to the nearest common ancestor
  283.                                      // between node pointed by cursor and the node
  284.                                      // with given node_id
  285.     // retrieval
  286.     const CTreeContNodeBase* GetNode() const
  287.     {return m_node;}
  288.     // check if node pointed by cursor
  289.     // is belong to subtree wich root node
  290.     // has given node_id
  291.     bool BelongSubtree(const CTreeContNodeBase* subtree_root) const;
  292.     // check if node with given node_id belongs
  293.     // to subtree pointed by cursor
  294.     bool AboveNode(const CTreeContNodeBase* node) const;
  295.     CTreeConstIterator(const CTreeCont* tree)
  296. : m_node( tree->m_root ), m_tree( tree ) {
  297. //tree->m_cursorPot.add((PotItem)this);
  298. //goRoot();
  299.     }
  300.     virtual ~CTreeConstIterator() {
  301. //m_tree->m_cursorPot.remove((PotItem)this);
  302.     }
  303. private:
  304.     CTreeConstIterator(){}
  305.     const CTreeContNodeBase* m_node;
  306.     const CTreeCont* m_tree;
  307. };
  308. END_objects_SCOPE // namespace ncbi::objects::
  309. END_NCBI_SCOPE
  310. /*
  311.  * $Log: ctreecont.hpp,v $
  312.  * Revision 1000.1  2004/04/12 17:27:06  gouriano
  313.  * PRODUCTION: UPGRADED [CATCHUP_003] Dev-tree R6.6
  314.  *
  315.  * Revision 6.6  2004/02/04 16:14:44  domrach
  316.  * New iterator types (modes of operation) are introduced. They include:
  317.  * full tree, branches'n'leaves, best, and blast. Position inquiry f-ns
  318.  * IsTerminal(), IsFirstChild(), and IsLastChild() has been moved from
  319.  * ITreeNode to ITreeIterator. Node loading f-ns() now return the ITreeNode
  320.  * for tax id.
  321.  *
  322.  * Revision 6.5  2003/05/09 22:08:15  domrach
  323.  * Destructor of CTreeContNodeBase made virtual
  324.  *
  325.  * Revision 6.4  2003/05/08 16:00:07  ucko
  326.  * Remove inappropriate dynamic_cast<>.
  327.  *
  328.  * Revision 6.3  2003/05/06 19:53:53  domrach
  329.  * New functions and interfaces for traversing the cached partial taxonomy tree introduced. Convenience functions GetDivisionName() and GetRankName() were added
  330.  *
  331.  * Revision 6.2  2003/01/21 19:37:19  domrach
  332.  * GetRoot method added to CTreeCont class.
  333.  *
  334.  * Revision 6.1  2002/01/30 16:13:37  domrach
  335.  * Changes made to pass through MSVC compiler. Some src files renamed
  336.  *
  337.  * Revision 6.1  2002/01/28 19:56:11  domrach
  338.  * Initial checkin of the library implementation files
  339.  *
  340.  */
  341. #endif // NCBI_OBJECTS_CTREECONT_HPP