开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 生物技术 > 查看源码
ctreecont.cpp
资源名称：ncbi_cxx_win--Jul_08_2004.zip　[点击查看]
上传用户：yhdzpy8989
上传日期：2007-06-13
资源大小：13604k
文件大小：27k
源码类别：

生物技术

开发平台：

C/C++

ctreecont.cpp：源码内容
  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: ctreecont.cpp,v $
  4.  * PRODUCTION Revision 1000.1  2004/06/01 19:35:13  gouriano
  5.  * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R6.5
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  10. /*  $Id: ctreecont.cpp,v 1000.1 2004/06/01 19:35:13 gouriano Exp $
  11. * ===========================================================================
  12. *
  13. *                            PUBLIC DOMAIN NOTICE
  14. *               National Center for Biotechnology Information
  15. *
  16. *  This software/database is a "United States Government Work" under the
  17. *  terms of the United States Copyright Act.  It was written as part of
  18. *  the author's official duties as a United States Government employee and
  19. *  thus cannot be copyrighted.  This software/database is freely available
  20. *  to the public for use. The National Library of Medicine and the U.S.
  21. *  Government have not placed any restriction on its use or reproduction.
  22. *
  23. *  Although all reasonable efforts have been taken to ensure the accuracy
  24. *  and reliability of the software and data, the NLM and the U.S.
  25. *  Government do not and cannot warrant the performance or results that
  26. *  may be obtained by using this software or data. The NLM and the U.S.
  27. *  Government disclaim all warranties, express or implied, including
  28. *  warranties of performance, merchantability or fitness for any particular
  29. *  purpose.
  30. *
  31. *  Please cite the author in any work or product based on this material.
  32. *
  33. * ===========================================================================
  34. *
  35. * File Name:  CTreeCont.cpp
  36. *
  37. * Author:  Vladimir Soussov, Yuri Sadykov, Michael Domrachev
  38. *
  39. * File Description:  General purpose tree container implementation
  40. *
  41. */
  43. #include <ncbi_pch.hpp>
  44. #include "ctreecont.hpp"
  47. BEGIN_NCBI_SCOPE
  48. BEGIN_objects_SCOPE
  51. bool CTreeIterator::BelongSubtree(const CTreeContNodeBase* subtree_root)
  52. {
  53.     if(m_node == subtree_root)
  54.         return true;
  55.     for(CTreeContNodeBase* pN= m_node->m_parent; pN != 0; pN= pN->m_parent) {
  56.         if(pN == subtree_root)
  57.             return true;
  58.     }
  59.     return false;
  60. }
  62. bool CTreeIterator::AboveNode(CTreeContNodeBase* node)
  63. {
  64.     if(node == 0) return false;
  65.     do {
  66.         if(node->m_parent == m_node) return true;
  67.     }
  68.     while((node= node->m_parent) != 0);
  70.     return false;
  71. }
  73. // move cursor to the nearest common ancestor
  74. bool CTreeIterator::GoAncestor(CTreeContNodeBase* node)
  75. {
  76.     if(BelongSubtree(node)) {
  77.         m_node= node;
  78.         return true;
  79.     }
  80.     CTreeContNodeBase* pN= m_node;;
  81.     while(!AboveNode(node)) {
  82.         if(m_node->m_parent == 0) {
  83.             m_node= pN;
  84.             return false;
  85.         }
  86.         m_node= m_node->m_parent;
  87.     }
  88.     return true;
  89. }
  92. // add child to a node pointed by cursor
  93. bool CTreeIterator::AddChild(CTreeContNodeBase* new_node)
  94. {
  95.     if(new_node) {
  96.         m_tree->AddChild(m_node);
  97.         new_node->m_parent= m_node;
  98.         new_node->m_sibling= m_node->m_child;
  99.         new_node->m_child= 0;
  100.         m_node->m_child= new_node;
  101.         m_tree->Done(new_node);
  102.         return true;
  103.     }
  104.     return false;
  105. }
  107. // add sibling to a node pointed by cursor
  108. bool CTreeIterator::AddSibling(CTreeContNodeBase* new_node)
  109. {
  110.     if(new_node && m_node->m_parent) {
  111.         m_tree->AddChild(m_node->m_parent);
  112.         new_node->m_parent= m_node->m_parent;
  113.         new_node->m_sibling= m_node->m_sibling;
  114.         new_node->m_child= 0;
  115.         m_node->m_sibling= new_node;
  116.         m_tree->Done(new_node);
  117.         return true;
  118.     }
  119.     return false;
  120. }
  122. bool CTreeIterator::MoveNode(CTreeContNodeBase* to_node)
  123. {
  124.     if((to_node == 0) || AboveNode(to_node)) {
  125.         return false;
  126.     }
  128.     if(m_node->m_parent == to_node) return true;
  130.     // notify the spies
  131.     m_tree->MoveNode(m_node, to_node);
  134.     // detach the node
  135.     if(m_node->m_parent->m_child == m_node) { // this is a first child
  136.         m_node->m_parent->m_child= m_node->m_sibling;
  137.     }
  138.     else {
  139.         CTreeContNodeBase* pN;
  140.         for( pN= m_node->m_parent->m_child;
  141.              pN->m_sibling != m_node;
  142.              pN= pN->m_sibling );
  143.         pN->m_sibling= m_node->m_sibling;
  144.     }
  146.     // attach it
  147.     m_node->m_sibling= to_node->m_child;
  148.     m_node->m_parent= to_node;
  149.     to_node->m_child= m_node;
  151.     // notify the spies
  152.     m_tree->Done(m_node);
  154.     return true;
  155. }
  157. bool CTreeIterator::MoveChildren(CTreeContNodeBase* to_node)
  158. {
  159.     if((to_node == 0) || AboveNode(to_node)) {
  160.         return false;
  161.     }
  163.     if((m_node == to_node) || (m_node->m_child == 0)) return true;
  165.     // notify the spies
  166.     m_tree->MoveChildren(m_node, to_node);
  168.     CTreeContNodeBase* pN= m_node->m_child;
  170.     do {
  171.         pN->m_parent= to_node;
  172.         if(pN->m_sibling == 0) break;
  173.     }
  174.     while((pN= pN->m_sibling) != 0);
  176.     pN->m_sibling= to_node->m_child;
  177.     to_node->m_child= m_node->m_child;
  178.     m_node->m_child= 0;
  180.     // notify the spies
  181.     m_tree->Done(m_node);
  183.     return true;
  184. }
  186. void CTreeCont::DelNodeInternal(CTreeContNodeBase* pN)
  187. {
  188.     CTreeContNodeBase* pNxt;
  189.     for(CTreeContNodeBase* pChild= pN->m_child; pChild != 0; pChild= pNxt) {
  190.         pNxt= pChild->m_sibling;
  191.         DelNodeInternal(pChild);
  192.     }
  193.     delete pN;
  194. }
  196. bool CTreeIterator::DeleteSubtree()
  197. {
  198.     if(m_node->m_parent == 0) return false; // can't delete the whole tree
  200.     // notify the spies
  201.     m_tree->DeleteSubtree(m_node, this);
  203.     CTreeContNodeBase* pN;
  205.     // detach the node
  206.     if(m_node->m_parent->m_child == m_node) { // this is a first child
  207.         m_node->m_parent->m_child= m_node->m_sibling;
  208.     }
  209.     else {
  210.         for(pN= m_node->m_parent->m_child;
  211.             pN->m_sibling != m_node;
  212.             pN= pN->m_sibling);
  213.         pN->m_sibling= m_node->m_sibling;
  214.     }
  216.     pN= m_node->m_parent;
  218.     m_tree->DelNodeInternal(m_node);
  220.     // notify the spies
  221.     m_node= pN;
  222.     m_tree->Done(m_node);
  224.     return true;
  225. }
  228. bool CTreeIterator::DeleteNode()
  229. {
  230.     if(m_node->m_parent == 0) return false; // can't delete the root
  231.     if(m_node->m_child) {
  232.         MoveChildren(m_node->m_parent);
  233.     }
  235.     return DeleteSubtree();
  236. }
  238. bool CTreeIterator::Merge(CTreeContNodeBase* to_node)
  239. {
  240.     if(MoveChildren(to_node)) {
  241.         m_tree->Merge(m_node, to_node, this);
  242.         to_node->Merge(m_node);
  244.         // detach the node
  245.         if(m_node->m_parent->m_child == m_node) { // this is a first child
  246.             m_node->m_parent->m_child= m_node->m_sibling;
  247.         }
  248.         else {
  249.             CTreeContNodeBase* pN;
  250.             for(pN= m_node->m_parent->m_child;
  251.                 pN->m_sibling != m_node;
  252.                 pN= pN->m_sibling);
  253.             pN->m_sibling= m_node->m_sibling;
  254.         }
  255.         delete m_node;
  256.         m_node= to_node;
  257.         m_tree->Done(m_node);
  258.         return true;
  259.     }
  260.     return false;
  261. }
  263. CTreeIterator::EAction
  264. CTreeIterator::ForEachDownward(C4Each& cb)
  265. {
  266.     switch( cb.Execute(m_node) ) {
  267.     default:
  268.     case eCont:
  269.         if(!m_node->IsTerminal()) {
  270.             switch( cb.LevelBegin(m_node) ) {
  271.             case eStop: return eStop;
  272.             default:
  273.             case eCont:
  274.                 if(GoChild()) {
  275.                     do {
  276.                         if(ForEachDownward(cb)==eStop)
  277.                             return eStop;
  278.                     } while(GoSibling());
  279.                 }
  280.             case eSkip: // Means skip this level
  281.                 break;
  282.             }
  283.             GoParent();
  284.             if( cb.LevelEnd(m_node) == eStop )
  285.                 return eStop;
  286.         }
  287.     case eSkip: break;
  288.     case eStop: return eStop;
  289.     }
  290.     return eCont;
  291. }
  293. CTreeIterator::EAction
  294. CTreeIterator::ForEachDownward(ForEachFunc ucb, void* user_data)
  295. {
  296.     switch( (*ucb)(m_node, user_data) ) {
  297.     default:
  298.     case eCont:
  299.         if(GoChild()) {
  300.             do {
  301.                 if(ForEachDownward(ucb, user_data)==eStop)
  302.                     return eStop;
  303.             } while(GoSibling());
  304.             GoParent();
  305.         }
  306.     case eSkip: break;
  307.     case eStop: return eStop;
  308.     }
  309.     return eCont;
  310. }
  312. CTreeIterator::EAction
  313. CTreeIterator::ForEachDownwardLimited(C4Each& cb, int levels)
  314. {
  315.     if(levels > 0) {
  316.         switch( cb.Execute(m_node) ) {
  317.         default:
  318.         case eCont:
  319.             if(!m_node->IsTerminal()) {
  320.                 switch( cb.LevelBegin(m_node) ) {
  321.                 case eStop: return eStop;
  322.                 default:
  323.                 case eCont:
  324.                     if(GoChild()) {
  325.                         do {
  326.                             if(ForEachDownwardLimited(cb, levels-1)==eStop)
  327.                                 return eStop;
  328.                         } while(GoSibling());
  329.                     }
  330.                 case eSkip: // Means skip this level
  331.                     break;
  332.                 }
  333.                 GoParent();
  334.                 if( cb.LevelEnd(m_node) == eStop )
  335.                     return eStop;
  336.             }
  337.         case eSkip: break;
  338.         case eStop: return eStop;
  339.         }
  340.     }
  341.     return eCont;
  342. }
  344. CTreeIterator::EAction
  345. CTreeIterator::ForEachDownwardLimited(ForEachFunc ucb, void* user_data,
  346.                                       int levels)
  347. {
  348.     if(levels > 0) {
  349.         switch( (*ucb)(m_node, user_data) ) {
  350.         default:
  351.         case eCont:
  352.             if(GoChild()) {
  353.                 do {
  354.                     if(ForEachDownwardLimited(ucb, user_data,
  355.                                               levels-1)==eStop)
  356.                         return eStop;
  357.                 } while(GoSibling());
  358.                 GoParent();
  359.             }
  360.         case eSkip: break;
  361.         case eStop: return eStop;
  362.         }
  363.     }
  364.     return eCont;
  365. }
  367. ///////////////////////////////////////////////////////
  368. // Get iterators
  369. ///////////////////////////////////////////////////////
  370. CTreeIterator*
  371. CTreeCont::GetIterator()
  372. {
  373.     return new CTreeIterator(this);
  374. }
  376. CTreeConstIterator*
  377. CTreeCont::GetConstIterator() const
  378. {
  379.     return new CTreeConstIterator(this);
  380. }
  381. ///////////////////////////////////////////////////////
  382. // delete subtree notification (private method)
  383. ///////////////////////////////////////////////////////
  384. void
  385. CTreeCont::DeleteSubtree(CTreeContNodeBase*, CTreeIterator*)
  386. {
  387.     //     int i;
  389.     //     if((n= m_cursorPot.nof()) > 1) {
  390.     //  // move all cursors out of deleted subtree
  391.     //  CTreeIterator* iCursor;
  393.     //  for(i= 0; i < n; i++) {
  394.     //      iCursor= (CTreeIterator*)(m_cursorPot.get(i));
  395.     //      if((iCursor != pCursor) && iCursor->belongSubtree(stroot)) {
  396.     //  iCursor->GoNode(stroot->m_parent); // move it up
  397.     //      }
  398.     //  }
  399.     //     }
  400. }
  402. ////////////////////////////////////////////////////////////
  403. // notify others that operation completed (private method)
  404. ////////////////////////////////////////////////////////////
  405. void CTreeCont::Done(CTreeContNodeBase* /*node*/)
  406. {
  407.     //     int n= m_spyPot.nof();
  409.     //     if(n > 0) { // notify all spies about delSubtree operation
  410.     //  int i;
  411.     //  CTreeContSpy* pSpy;
  413.     //  for(i= 0; i < n; i++) {
  414.     //      pSpy= (CTreeContSpy*)(m_spyPot.get(i));
  415.     //      pSpy->Done(node);
  416.     //  }
  417.     //     }
  418. }
  420. ///////////////////////////////////////////////////////////
  421. // move node notification (private method)
  422. ///////////////////////////////////////////////////////////
  423. void CTreeCont::MoveNode(CTreeContNodeBase*, CTreeContNodeBase*)
  424. {
  425.     //     int n= m_spyPot.nof();
  427.     //     if(n > 0) { // notify all spies about delSubtree operation
  428.     //  int i;
  429.     //  CTreeContSpy* pSpy;
  431.     //  for(i= 0; i < n; i++) {
  432.     //      pSpy= (CTreeContSpy*)(m_spyPot.get(i));
  433.     //      pSpy->node_move(node2move, new_parent);
  434.     //  }
  435.     //     }
  436. }
  438. //////////////////////////////////////////////////////////////
  439. // move children (private method)
  440. //////////////////////////////////////////////////////////////
  441. void CTreeCont::MoveChildren(CTreeContNodeBase*, CTreeContNodeBase*)
  442. {
  443.     //     int n= m_spyPot.nof();
  445.     //     if(n > 0) { // notify all spies about delSubtree operation
  446.     //  int i;
  447.     //  CTreeContSpy* pSpy;
  449.     //  for(i= 0; i < n; i++) {
  450.     //      pSpy= (CTreeContSpy*)(m_spyPot.get(i));
  451.     //      pSpy->children_move(old_parent, new_parent);
  452.     //  }
  453.     //     }
  454. }
  456. ///////////////////////////////////////////////////////////////
  457. // add child notification (private method)
  458. ///////////////////////////////////////////////////////////////
  459. void CTreeCont::AddChild(CTreeContNodeBase*)
  460. {
  461.     //     int n= m_spyPot.nof();
  463.     //     if(n > 0) { // notify all spies about delSubtree operation
  464.     //  int i;
  465.     //  CTreeContSpy* pSpy;
  467.     //  for(i= 0; i < n; i++) {
  468.     //      pSpy= (CTreeContSpy*)(m_spyPot.get(i));
  469.     //      pSpy->child_add(parent);
  470.     //  }
  471.     //     }
  472. }
  474. //////////////////////////////////////////////////////
  475. // merge nodes notification (private method)
  476. //////////////////////////////////////////////////////
  477. void CTreeCont::Merge(CTreeContNodeBase* , CTreeContNodeBase* ,
  478.                       CTreeIterator* )
  479. {
  480.     //     int i;
  481.     //     int n= m_spyPot.nof();
  483.     //     if(n > 0) { // notify all spies about delSubtree operation
  484.     //  CTreeContSpy* pSpy;
  486.     //  for(i= 0; i < n; i++) {
  487.     //      pSpy= (CTreeContSpy*)(m_spyPot.get(i));
  488.     //      pSpy->node_merge(src, dst);
  489.     //  }
  490.     //     }
  492.     //     if((n= m_cursorPot.nof()) > 1) {
  493.     //  // move all cursors out of src
  494.     //  CTreeIterator* iCursor;
  496.     //  for(i= 0; i < n; i++) {
  497.     //      iCursor= (CTreeIterator*)(m_cursorPot.get(i));
  498.     //      if((iCursor != pCursor) && (iCursor->getNode() == src)) {
  499.     //  iCursor->GoNode(dst); // move it to merged node
  500.     //      }
  501.     //  }
  502.     //     }
  503. }
  505. CTreeCont::~CTreeCont()
  506. {
  507.     //     int i, n;
  509.     //     // delete all cursors
  510.     //     if((n= m_cursorPot.nof()) > 1) {
  511.     //  // move all cursors out of deleted subtree
  512.     //  CTreeIterator* iCursor;
  514.     //  for(i= 0; i < n; i++) {
  515.     //      iCursor= (CTreeIterator*)(m_cursorPot.get(i));
  516.     //      delete iCursor;
  517.     //  }
  518.     //     }
  519.     if(m_root)
  520.         DelNodeInternal(m_root);
  521. }
  524. bool CTreeCont::AddNode(CTreeContNodeBase* pParentNode,
  525.                         CTreeContNodeBase* pNewNode)
  526. {
  527.     if(pNewNode && pParentNode) {
  528.         pNewNode->m_parent = pParentNode;
  529.         pNewNode->m_sibling = pParentNode->m_child;
  530.         pNewNode->m_child = 0;
  531.         pParentNode->m_child = pNewNode;
  533.         return true;
  534.     }
  536.     return false;
  537. }
  540. bool CTreeConstIterator::BelongSubtree(const CTreeContNodeBase* subtree_root)
  541.     const
  542. {
  543.     if(m_node == subtree_root)
  544.         return true;
  545.     for(const CTreeContNodeBase* pN= m_node->m_parent; pN != 0;
  546.         pN= pN->m_parent) {
  547.         if(pN == subtree_root)
  548.             return true;
  549.     }
  550.     return false;
  551. }
  553. bool CTreeConstIterator::AboveNode(const CTreeContNodeBase* node) const
  554. {
  555.     if(node == 0)
  556.         return false;
  557.     do {
  558.         if(node->m_parent == m_node)
  559.             return true;
  560.     }
  561.     while((node= node->m_parent) != 0);
  563.     return false;
  564. }
  566. // move cursor to the nearest common ancestor
  567. bool CTreeConstIterator::GoAncestor(const CTreeContNodeBase* node)
  568. {
  569.     if(BelongSubtree(node)) {
  570.         m_node= node;
  571.         return true;
  572.     }
  573.     const CTreeContNodeBase* pN= m_node;;
  574.     while(!AboveNode(node)) {
  575.         if(m_node->m_parent == 0) {
  576.             m_node= pN;
  577.             return false;
  578.         }
  579.         m_node= m_node->m_parent;
  580.     }
  581.     return true;
  582. }
  584. // CTreeConstIterator::EAction
  585. // CTreeConstIterator::ForEachDownward(C4Each& cb)
  586. // {
  587. //     switch( cb.Execute(m_node) ) {
  588. //     default:
  589. //     case eCont:
  590. //         if(!m_node->IsTerminal()) {
  591. //             switch( cb.LevelBegin(m_node) ) {
  592. //             case eStop: return eStop;
  593. //             default:
  594. //             case eCont:
  595. //                 if(GoChild()) {
  596. //                     do {
  597. //                         if(ForEachDownward(cb)==eStop) return eStop;
  598. //                     } while(GoSibling());
  599. //                 }
  600. //             case eSkip: // Means skip this level
  601. //                 break;
  602. //             }
  603. //             GoParent();
  604. //             if( cb.LevelEnd(m_node) == eStop )
  605. //                 return eStop;
  606. //         }
  607. //     case eSkip: break;
  608. //     case eStop: return eStop;
  609. //     }
  610. //     return eCont;
  611. // }
  613. // CTreeConstIterator::EAction
  614. // CTreeConstIterator::ForEachDownward(ForEachFunc ucb, void* user_data)
  615. // {
  616. //     switch( (*ucb)(m_node, user_data) ) {
  617. //     default:
  618. //     case eCont:
  619. //         if(GoChild()) {
  620. //             do {
  621. //                 if(ForEachDownward(ucb, user_data)==eStop) return eStop;
  622. //             } while(GoSibling());
  623. //             GoParent();
  624. //         }
  625. //     case eSkip: break;
  626. //     case eStop: return eStop;
  627. //     }
  628. //     return eCont;
  629. // }
  631. // CTreeConstIterator::EAction
  632. // CTreeConstIterator::ForEachDownwardLimited(C4Each& cb, int levels)
  633. // {
  634. //     if(levels > 0) {
  635. //         switch( cb.Execute(m_node) ) {
  636. //         default:
  637. //         case eCont:
  638. //             if(!m_node->IsTerminal()) {
  639. //                 switch( cb.LevelBegin(m_node) ) {
  640. //                 case eStop: return eStop;
  641. //                 default:
  642. //                 case eCont:
  643. //                     if(GoChild()) {
  644. //                         do {
  645. //                             if(ForEachDownwardLimited(cb, levels-1)==eStop)
  646. //                                 return eStop;
  647. //                         } while(GoSibling());
  648. //                     }
  649. //                 case eSkip: // Means skip this level
  650. //                     break;
  651. //                 }
  652. //                 GoParent();
  653. //                 if( cb.LevelEnd(m_node) == eStop )
  654. //                     return eStop;
  655. //             }
  656. //         case eSkip: break;
  657. //         case eStop: return eStop;
  658. //         }
  659. //     }
  660. //     return eCont;
  661. // }
  663. // CTreeConstIterator::EAction
  664. // CTreeConstIterator::ForEachDownwardLimited( ForEachFunc ucb,
  665. //                                             void* user_data, int levels)
  666. // {
  667. //     if(levels > 0) {
  668. //         switch( (*ucb)(m_node, user_data) ) {
  669. //         default:
  670. //         case eCont:
  671. //             if(GoChild()) {
  672. //                 do {
  673. //                     if(ForEachDownwardLimited(ucb, user_data,
  674. //                                               levels-1)==eStop)
  675. //                         return eStop;
  676. //                 } while(GoSibling());
  677. //                 GoParent();
  678. //             }
  679. //         case eSkip: break;
  680. //         case eStop: return eStop;
  681. //         }
  682. //     }
  683. //     return eCont;
  684. // }
  686. // add child preserving the sorting order
  687. bool CTreeIterator::AddChild(CTreeContNodeBase* new_node, 
  688.                              CTreeIterator::CSortPredicate& pred )
  689. {
  690.     // Temporary 
  691.     CTreeContNodeBase* prev;
  692.     CTreeContNodeBase* next;
  693.     
  694.     if( GoChild() ) {
  695.         new_node->m_child = 0;
  696.         new_node->m_parent = m_node->Parent();
  697.         prev = 0;
  698.         next = GetNode();
  699.         while( next && pred.Execute( next, new_node ) ) {
  700.             prev = next;
  701.             next = prev->Sibling();
  702.         }
  703.         new_node->m_sibling = next;
  704.         if( prev ) { // insert after prevtmp
  705.             prev->m_sibling = new_node;
  706.         } else { // insert as first child
  707.             prev->Parent()->m_child = next;
  708.         }
  709.         // Restore state
  710.         GoParent();
  711.     } else {
  712.         return AddChild( new_node );
  713.     }
  714.     return true;
  715. }
  717. void CTreeIterator::SortChildren( CTreeIterator::CSortPredicate& pred )
  718. {
  719.     // Sorting the list by insertion
  720.     CTreeContNodeBase* prev;
  721.     CTreeContNodeBase* next;
  722.     CTreeContNodeBase* tmp;
  723.     CTreeContNodeBase* prevtmp;
  724.     
  725.     if( GoChild() ) {
  726.         prev = GetNode();
  727.         if( GoSibling() ) {
  728.             next = GetNode();
  729.             while( next ) {
  730.                 if( !pred.Execute( prev, next ) ) { // The order is not right
  731.                     tmp = prev->Parent()->Child();
  732.                     prevtmp = 0;
  733.                     while( tmp != prev && pred.Execute( tmp, next ) &&
  734.                            (prevtmp = tmp) && (tmp = tmp->Sibling()) );
  735.                     if( tmp ) {
  736.                         // Move from prev place
  737.                         prev->m_sibling = next->m_sibling;
  739.                         if( prevtmp ) { // insert after prevtmp
  740.                             next->m_sibling = prevtmp->m_sibling;
  741.                             prevtmp->m_sibling = next;
  742.                         } else { // insert as first child
  743.                             next->m_sibling = prev->Parent()->Child();
  744.                             prev->Parent()->m_child = next;
  745.                         }
  746.                     }
  747.                 } else { // the oreder is right, move to the next
  748.                     prev = next;
  749.                 }
  750.                 next = prev->Sibling();
  751.             }
  752.         }
  753.         // Restore state
  754.         GoParent();
  755.     }
  756. }
  758. class CLevelSort : public CTreeIterator::C4Each {
  759. public:
  760.     CLevelSort( CTreeIterator::CSortPredicate& pred, CTreeCont* tree )
  761.         : m_pred(pred), m_tree(tree) {}
  762.     virtual CTreeIterator::EAction Execute(CTreeContNodeBase* pNode) {
  763.         CTreeIterator::EAction retc = CTreeIterator::eCont;
  764.         CTreeIterator* it = m_tree->GetIterator();
  765.         if( it->GoNode( pNode ) ) {
  766.             it->SortChildren( m_pred );
  767.         } else {
  768.             retc = CTreeIterator::eSkip;
  769.         }
  770.         delete it;
  771.         return retc;
  772.     }
  773. private:
  774.     CTreeIterator::CSortPredicate& m_pred;
  775.     CTreeCont*                     m_tree;
  776. };
  778. void
  779. CTreeIterator::SortAllChildrenInSubtree( CTreeIterator::CSortPredicate& pred )
  780. {
  781.     CLevelSort sorter( pred, m_tree );
  782.     ForEachDownward( sorter );
  783. }
  785. CTreeIterator::EAction
  786. CTreeIterator::ForEachUpward(C4Each& cb)
  787. {
  788.     if(!m_node->IsTerminal()) {
  789.         switch( cb.LevelBegin(m_node) ) {
  790.         case eStop: return eStop;
  791.         default:
  792.         case eCont:
  793.             if(GoChild()) {
  794.                 do {
  795.                     if(ForEachUpward(cb)==eStop)
  796.                         return eStop;
  797.                 } while(GoSibling());
  798.             }
  799.         case eSkip: // Means skip this level
  800.             break;
  801.         }
  802.         GoParent();
  803.         if( cb.LevelEnd(m_node) == eStop )
  804.             return eStop;
  805.     }
  806.     return cb.Execute(m_node);
  807. }
  809. CTreeIterator::EAction
  810. CTreeIterator::ForEachUpward(ForEachFunc ucb, void* user_data)
  811. {
  812.     if(GoChild()) {
  813.         do {
  814.             if(ForEachUpward(ucb, user_data)==eStop)
  815.                 return eStop;
  816.         } while(GoSibling());
  817.         GoParent();
  818.     }
  819.     return (*ucb)(m_node, user_data);
  820. }
  822. CTreeIterator::EAction
  823. CTreeIterator::ForEachUpwardLimited(C4Each& cb, int levels)
  824. {
  825.     if(levels > 0) {
  826.         if(!m_node->IsTerminal()) {
  827.             switch( cb.LevelBegin(m_node) ) {
  828.             case eStop: return eStop;
  829.             default:
  830.             case eCont:
  831.                 if(GoChild()) {
  832.                     do {
  833.                         if(ForEachUpwardLimited(cb, levels-1)==eStop)
  834.                             return eStop;
  835.                     } while(GoSibling());
  836.                 }
  837.             case eSkip: // Means skip this level
  838.                 break;
  839.             }
  840.             GoParent();
  841.             if( cb.LevelEnd(m_node) == eStop )
  842.                 return eStop;
  843.         }
  844.         return cb.Execute(m_node);
  845.     }
  846.     return eCont;
  847. }
  849. CTreeIterator::EAction
  850. CTreeIterator::ForEachUpwardLimited(ForEachFunc ucb, void* user_data,
  851.                                     int levels)
  852. {
  853.     if(levels > 0) {
  854.         if(GoChild()) {
  855.             do {
  856.                 if(ForEachUpwardLimited(ucb, user_data,
  857.                                         levels-1)==eStop)
  858.                     return eStop;
  859.             } while(GoSibling());
  860.             GoParent();
  861.         }
  862.         return (*ucb)(m_node, user_data);
  863.     }
  864.     return eCont;
  865. }
  867. // CTreeConstIterator::EAction
  868. // CTreeConstIterator::ForEachUpward(C4Each& cb)
  869. // {
  870. //     if(!m_node->IsTerminal()) {
  871. //         switch( cb.LevelBegin(m_node) ) {
  872. //         case eStop: return eStop;
  873. //         default:
  874. //         case eCont:
  875. //             if(GoChild()) {
  876. //                 do {
  877. //                     if(ForEachUpward(cb)==eStop)
  878. //                         return eStop;
  879. //                 } while(GoSibling());
  880. //             }
  881. //         case eSkip: // Means skip this level
  882. //             break;
  883. //         }
  884. //         GoParent();
  885. //         if( cb.LevelEnd(m_node) == eStop )
  886. //             return eStop;
  887. //     }
  888. //     return cb.Execute(m_node);
  889. // }
  891. // CTreeConstIterator::EAction
  892. // CTreeConstIterator::ForEachUpward(ForEachFunc ucb, void* user_data)
  893. // {
  894. //     if(GoChild()) {
  895. //         do {
  896. //             if(ForEachUpward(ucb, user_data)==eStop)
  897. //                 return eStop;
  898. //         } while(GoSibling());
  899. //         GoParent();
  900. //     }
  901. //     return (*ucb)(m_node, user_data);
  902. // }
  904. // CTreeConstIterator::EAction
  905. // CTreeConstIterator::ForEachUpwardLimited(C4Each& cb, int levels)
  906. // {
  907. //     if(levels > 0) {
  908. //         if(!m_node->IsTerminal()) {
  909. //             switch( cb.LevelBegin(m_node) ) {
  910. //             case eStop: return eStop;
  911. //             default:
  912. //             case eCont:
  913. //                 if(GoChild()) {
  914. //                     do {
  915. //                         if(ForEachUpwardLimited(cb, levels-1)==eStop)
  916. //                             return eStop;
  917. //                     } while(GoSibling());
  918. //                 }
  919. //             case eSkip: // Means skip this level
  920. //                 break;
  921. //             }
  922. //             GoParent();
  923. //             if( cb.LevelEnd(m_node) == eStop )
  924. //                 return eStop;
  925. //         }
  926. //         return cb.Execute(m_node);
  927. //     }
  928. //     return eCont;
  929. // }
  931. // CTreeConstIterator::EAction
  932. // CTreeConstIterator::ForEachUpwardLimited(ForEachFunc ucb, void* user_data,
  933. //                                          int levels)
  934. // {
  935. //     if(levels > 0) {
  936. //         if(GoChild()) {
  937. //             do {
  938. //                 if(ForEachUpwardLimited(ucb, user_data,
  939. //                                         levels-1)==eStop)
  940. //                     return eStop;
  941. //             } while(GoSibling());
  942. //             GoParent();
  943. //         }
  944. //         return (*ucb)(m_node, user_data);
  945. //     }
  946. //     return eCont;
  947. // }
  950. END_objects_SCOPE
  951. END_NCBI_SCOPE
  955. /*
  956.  * $Log: ctreecont.cpp,v $
  957.  * Revision 1000.1  2004/06/01 19:35:13  gouriano
  958.  * PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R6.5
  959.  *
  960.  * Revision 6.5  2004/05/19 17:27:10  gorelenk
  961.  * Added include of PCH - ncbi_pch.hpp
  962.  *
  963.  * Revision 6.4  2003/05/06 19:53:53  domrach
  964.  * New functions and interfaces for traversing the cached partial taxonomy tree introduced. Convenience functions GetDivisionName() and GetRankName() were added
  965.  *
  966.  * Revision 6.3  2002/10/22 22:15:41  vakatov
  967.  * Get rid of a compilation warning
  968.  *
  969.  * Revision 6.2  2002/01/31 00:31:26  vakatov
  970.  * Follow the renaming of "CTreeCont.hpp" to "ctreecont.hpp".
  971.  * Get rid of "std::" which is unnecessary and sometimes un-compilable.
  972.  * Also done some source identation/beautification.
  973.  *
  974.  * Revision 6.1  2002/01/30 16:13:37  domrach
  975.  * Changes made to pass through MSVC compiler. Some src files renamed
  976.  *
  977.  * Revision 6.1  2002/01/28 19:56:11  domrach
  978.  * Initial checkin of the library implementation files
  979.  *
  980.  */