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

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

生物技术

开发平台：

C/C++

test_ncbi_tree.cpp：源码内容
  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: test_ncbi_tree.cpp,v $
  4.  * PRODUCTION Revision 1000.2  2004/06/01 19:09:53  gouriano
  5.  * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.16
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  10. /*  $Id: test_ncbi_tree.cpp,v 1000.2 2004/06/01 19:09:53 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.  * Author:  Anatoliy Kuznetov
  36.  *
  37.  * File Description:
  38.  *   TEST for:  NCBI C++ core tree related API
  39.  *
  40.  */
  42. #include <ncbi_pch.hpp>
  43. #include <corelib/ncbiapp.hpp>
  44. #include <corelib/ncbienv.hpp>
  45. #include <corelib/ncbireg.hpp>
  46. #include <corelib/ncbi_tree.hpp>
  47. #include <util/bitset/bitset_debug.hpp>
  48. #include <algo/tree/tree_algo.hpp>
  49. #include <util/bitset/ncbi_bitset.hpp>
  50. #include <algorithm>
  52. #include <test/test_assert.h>  /* This header must go last */
  55. // This is to use the ANSI C++ standard templates without the "std::" prefix
  56. // and to use NCBI C++ entities without the "ncbi::" prefix
  57. USING_NCBI_SCOPE;
  61. /////////////////////////////////
  62. // Test application
  63. //
  65. class CTestApplication : public CNcbiApplication
  66. {
  67. public:
  68.     void Init(void);
  69.     int Run(void);
  70. };
  73. void CTestApplication::Init(void)
  74. {
  75.     // Set err.-posting and tracing to maximum
  76.     SetDiagTrace(eDT_Enable);
  77.     SetDiagPostFlag(eDPF_All);
  78.     SetDiagPostLevel(eDiag_Info);
  79. }
  81. ETreeTraverseCode TestFunctor1(CTreeNode<int>& tr, int delta)
  82. {
  83.     cout << tr.GetValue() << " :" << delta << endl;
  84.     return eTreeTraverse;
  85. }
  87. static string s_IntToStr(int i)
  88. {
  89.     return NStr::IntToString(i);
  90. }
  92. static void s_TEST_Tree()
  93. {
  94.     typedef CTreeNode<int>  TTree;
  95.     
  96.     TTree* tr = new TTree(0);
  97.     
  98.     TTree* tr10 = tr->AddNode(10);
  99.     tr->AddNode(11);
  101. //    TreePrint(cout, *tr, (IntConvType) NStr::IntToString);
  102. //    TreeReRoot(*tr10);
  103. //    TreePrint(cout, *tr10, (IntConvType) NStr::IntToString);
  106.     TreeDepthFirstTraverse(*tr, TestFunctor1);
  107.     cout << endl;
  109.     {{
  110.     unsigned int cnt;
  111.     TTree::TNodeList_CI it = tr->SubNodeBegin();
  112.     TTree::TNodeList_CI it_end = tr->SubNodeEnd();
  113.     
  114.     for (cnt = 0; it != it_end; ++it, ++cnt) {
  115.         const TTree* t = *it;
  116.         int v = t->GetValue();
  117.         assert(v == 10 || v == 11);
  118.     }
  119.     assert(cnt == 2);
  120.     }}
  121.     
  122.     {{
  123.     TTree* tr2 = new TTree(*tr);
  124.     unsigned int cnt;
  125.     TTree::TNodeList_CI it = tr2->SubNodeBegin();
  126.     TTree::TNodeList_CI it_end = tr2->SubNodeEnd();
  127.     
  128.     for (cnt = 0; it != it_end; ++it, ++cnt) {
  129.         const TTree* t = *it;
  130.         int v = t->GetValue();
  131.         assert(v == 10 || v == 11);
  132.     }
  133.     assert(cnt == 2);
  134.     delete tr2;
  135.     }}
  136.     
  137.     
  138.     {{
  139.     TTree::TNodeList_I it = tr->SubNodeBegin();
  140.     TTree::TNodeList_I it_end = tr->SubNodeEnd();
  141.     
  142.     for (; it != it_end; ++it) {
  143.         TTree* t = *it;
  144.         int v = t->GetValue();
  145.         if (v == 10)
  146.         {
  147.             tr->RemoveNode(t);
  148.             break;
  149.         }
  150.     }
  151.     }}
  153.     TreeDepthFirstTraverse(*tr, TestFunctor1);
  154.     cout << endl;
  156.     {{
  157.     unsigned int cnt;
  158.     TTree::TNodeList_CI it = tr->SubNodeBegin();
  159.     TTree::TNodeList_CI it_end = tr->SubNodeEnd();
  160.     
  161.     for (cnt = 0; it != it_end; ++it, ++cnt) {
  162.         const TTree* t = *it;
  163.         int v = t->GetValue();
  164.         assert(v == 11);
  165.     }
  166.     assert(cnt == 1);
  167.     }}
  168.     
  169.     delete tr;
  171.     TTree* str = tr = new TTree(0);
  172.     
  173.     //
  174.     // 0 - 2 
  175.     //       - 4
  176.     //   - 3 
  177.     //       - 5
  178.     //       - 6
  179.     //
  181.     TTree* tr4 = tr->AddNode(2)->AddNode(4);
  182.     tr = tr->AddNode(3);
  183.     TTree* tr5 = tr->AddNode(5);
  184.     TTree* tr6 = tr->AddNode(6);
  186.     cout << "Test Tree: " << endl;
  188.     TreeDepthFirstTraverse(*str, TestFunctor1);
  189.     cout << endl;
  191.     vector<const TTree*> trace_vec;
  192.     TreeTraceToRoot(*tr6, trace_vec);
  194.     assert(trace_vec.size() == 3);
  196.     {{
  197.     cout << "Trace to root: ";
  199.     ITERATE(vector<const TTree*>, it, trace_vec) {
  200.         cout << (*it)->GetValue() << "; ";
  201.     }
  203.     cout << endl;
  205.     }}
  207.     const TTree* parent_node = TreeFindCommonParent(*tr4, *tr6);
  209.     assert(tr4->IsParent(*parent_node));
  210.     assert(tr6->IsParent(*parent_node));
  211.     assert(!tr4->IsParent(*tr6));
  214.     assert(parent_node);
  216.     cout << "parent: " << parent_node->GetValue() << endl;
  218.     assert(parent_node->GetValue() == 0);
  220.     parent_node = TreeFindCommonParent(*tr5, *tr6);
  221.     assert(parent_node);
  222.     assert(parent_node->GetValue() == 3);
  225.     TreePrint(cout, *str, s_IntToStr);
  226.     cout << endl;
  228.     TreeReRoot(*tr5);
  229.     TreePrint(cout, *tr5, s_IntToStr);
  231.     tr5->MoveSubnodes(str);
  232.     TreePrint(cout, *tr5, s_IntToStr);
  234.     delete tr5;
  235. }
  237. struct IdValue
  238. {
  239.     int id;
  240.     
  241.     IdValue() : id(0) {}
  242.     IdValue(int v) : id(v) {}
  244.     operator int() const { return id; }
  245.     int GetId() const { return id; }
  246. };
  248. static string s_IdValueToStr(const IdValue& idv)
  249. {
  250.     return NStr::IntToString(idv.id);
  251. }
  253. static void s_TEST_IdTreeOperations()
  254. {
  255.     cout << "--------------------- s_TEST_IdTreeOperations " << endl;
  257.     typedef CTreeNode<IdValue> TTree;
  259.     TTree* tr = new TTree(0);
  261.     TTree* tr10 = tr->AddNode(10);
  262.     TTree* tr11 = tr->AddNode(11);
  263.     TTree* tr110 = tr10->AddNode(110);
  264.     TTree* tr1100 = tr110->AddNode(1100);
  266.     TreePrint(cout, *tr, s_IdValueToStr);
  268.     bm::bvector<> bv;
  269.     TreeMakeSubNodesSet(*tr, bv.inserter());
  270.     assert(bv.count() == 2);
  271.     assert(bv[10]);
  272.     assert(bv[11]);
  274.     typedef vector<TTree*> TNodeList;
  275.     TNodeList node_list;
  276.     node_list.push_back(tr10);
  277.     node_list.push_back(tr11);
  278.     node_list.push_back(tr110);
  279.     node_list.push_back(tr1100);
  281.     TNodeList res_node_list;
  283.     CTreeNonRedundantSet<TTree, bm::bvector<>, TNodeList> nr_func;
  284.     nr_func(node_list, res_node_list);
  286.     cout << "Non-redundant set:" << endl;
  287.     ITERATE(TNodeList, it, res_node_list) {
  288.         cout << (*it)->GetValue().GetId() << "; ";
  289.     }
  290.     cout << endl;
  291.     assert(res_node_list.size() == 2);
  294.     res_node_list.clear();
  295.     node_list.clear();
  297.     node_list.push_back(tr110);
  298.     node_list.push_back(tr1100);
  300.     CTreeMinimalSet<TTree, bm::bvector<>, TNodeList> min_func;
  301.     min_func(node_list, res_node_list);
  303.     
  304.     cout << "Minimal set:" << endl;
  305.     ITERATE(TNodeList, it, res_node_list) {
  306.         cout << (*it)->GetValue().GetId() << "; ";
  307.     }
  308.     cout << endl;
  309.     cout << "-----" << endl;
  310.     assert(res_node_list.size() == 1);
  313.     res_node_list.clear();
  314.     node_list.clear();
  317.     node_list.push_back(tr110);
  318.     node_list.push_back(tr1100);
  319.     node_list.push_back(tr11);
  321.     min_func(node_list, res_node_list);
  323.     
  324.     cout << "Minimal set:" << endl;
  325.     ITERATE(TNodeList, it, res_node_list) {
  326.         cout << (*it)->GetValue().GetId() << "; ";
  327.     }
  328.     cout << endl;
  329.     cout << "-----" << endl;
  330.     assert(res_node_list.size() == 1);
  333.     res_node_list.clear();
  334.     node_list.clear();
  337.     
  338.     TNodeList node_list_a;
  339.     TNodeList node_list_b;
  340.     TNodeList node_list_c;
  342.     node_list_a.push_back(tr10);
  343.     node_list_a.push_back(tr11);
  344.     node_list_a.push_back(tr110);
  345.     node_list_a.push_back(tr1100);
  346.     
  347.     node_list_b.push_back(tr10);
  348.     node_list_b.push_back(tr11);
  349.     node_list_b.push_back(tr110);
  351.     CTreeNodesAnd<TTree, bm::bvector<>, TNodeList> and_func;
  352.     and_func(node_list_a, node_list_b, node_list_c);
  354.     ITERATE(TNodeList, it, node_list_c) {
  355.         cout << (*it)->GetValue().GetId() << "; ";
  356.     }
  357.     cout << endl;
  358.     assert(node_list_c.size() == 3);
  361.     node_list_c.clear();
  363.     CTreeNodesOr<TTree, bm::bvector<>, TNodeList> or_func;
  364.     or_func(node_list_a, node_list_b, node_list_c);
  366.     ITERATE(TNodeList, it, node_list_c) {
  367.         cout << (*it)->GetValue().GetId() << "; ";
  368.     }
  369.     cout << endl;
  370.     assert(node_list_c.size() == 4);
  373.     delete tr;
  375.     cout << "--------------------- s_TEST_IdTreeOperations ok" << endl;
  376. }
  378. static void s_TEST_IdTree()
  379. {
  380.     typedef CTreePairNode<int, int> TTree;
  382.     TTree* tr = new TTree(0, 0);
  383.     
  384.     tr->AddNode(1, 10);
  385.     tr->AddNode(100, 110);
  386.     TTree* tr2 = tr->AddNode(2, 20);
  387.     tr2->AddNode(20, 21);    
  388.     TTree* tr3 =tr2->AddNode(22, 22);
  389.     tr3->AddNode(222, 222);
  391.     {{
  392.     list<int> npath;
  393.     npath.push_back(2);
  394.     npath.push_back(22);
  396.     TTree::TConstPairTreeNodeList res;
  397.     tr->FindNodes(npath, &res);
  398.     assert(!res.empty());
  399.     TTree::TConstPairTreeNodeList::const_iterator it = res.begin();
  400.     const TTree* ftr = *it;
  402.     assert(ftr->GetValue() == 22);
  403.     }}
  405.     {{
  406.     list<int> npath;
  407.     npath.push_back(2);
  408.     npath.push_back(32);
  410.     TTree::TConstPairTreeNodeList res;
  411.     tr->FindNodes(npath, &res);
  412.     assert(res.empty());
  413.     }}
  415.     {{
  416.     list<int> npath;
  417.     npath.push_back(2);
  418.     npath.push_back(22);
  419.     npath.push_back(222);
  420.     npath.push_back(100);
  422.     const TTree* node = PairTreeTraceNode(*tr, npath);
  423.     assert(node);
  424.     cout << node->GetId() << " " << node->GetValue() << endl;
  425.     assert(node->GetValue() == 110);
  428.     node = PairTreeBackTraceNode(*tr3, 1);
  429.     assert(node);
  430.     cout << node->GetId() << " " << node->GetValue() << endl;
  431.     assert(node->GetValue() == 10);
  432.     }}
  434.     {{
  435.     list<int> npath;
  436.     npath.push_back(2);
  437.     npath.push_back(22);
  438.     npath.push_back(222);
  440.     const TTree* node = PairTreeTraceNode(*tr, npath);
  441.     assert(node);
  442.     cout << node->GetId() << " " << node->GetValue() << endl;
  443.     assert(node->GetValue() == 222);
  444.     }}
  446.     delete tr;
  447. }
  451. int CTestApplication::Run(void)
  452. {
  455.     //        CExceptionReporterStream reporter(cerr);
  456.     //        CExceptionReporter::SetDefault(&reporter);
  457.     //        CExceptionReporter::EnableDefault(false);
  458.     //        CExceptionReporter::EnableDefault(true);
  459.     //        CExceptionReporter::SetDefault(0);
  460.     
  461.     SetupDiag(eDS_ToStdout);
  462.     /*      
  463.     CExceptionReporter::EnableDefault(true);
  464.     cerr << endl;
  465.     NCBI_REPORT_EXCEPTION(
  466.     "****** default reporter (stream) ******",e);
  468.     CExceptionReporter::SetDefault(0);
  469.     cerr << endl;
  470.     NCBI_REPORT_EXCEPTION(
  471.     "****** default reporter (diag) ******",e);
  472.     */
  473.     
  474.     s_TEST_Tree();
  476.     s_TEST_IdTree();
  478.     s_TEST_IdTreeOperations();
  480.     return 0;
  481. }
  483.   
  484. /////////////////////////////////
  485. // APPLICATION OBJECT and MAIN
  486. //
  488. int main(int argc, const char* argv[] /*, const char* envp[]*/)
  489. {
  490.     CTestApplication theTestApplication;
  491.     return theTestApplication.AppMain(argc, argv, 0 /*envp*/, eDS_ToMemory);
  492. }
  495. /*
  496.  * ==========================================================================
  497.  * $Log: test_ncbi_tree.cpp,v $
  498.  * Revision 1000.2  2004/06/01 19:09:53  gouriano
  499.  * PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.16
  500.  *
  501.  * Revision 1.16  2004/05/14 13:59:51  gorelenk
  502.  * Added include of ncbi_pch.hpp
  503.  *
  504.  * Revision 1.15  2004/04/22 13:53:15  kuznets
  505.  * + test for minimal set
  506.  *
  507.  * Revision 1.14  2004/04/21 16:43:08  kuznets
  508.  * + test cases for AND, OR (tree node lists)
  509.  *
  510.  * Revision 1.13  2004/04/21 12:58:32  kuznets
  511.  * + s_TEST_IdTreeOperations
  512.  *
  513.  * Revision 1.12  2004/04/19 16:01:30  kuznets
  514.  * + #include <algo/tree/tree_algo.hpp>
  515.  *
  516.  * Revision 1.11  2004/04/09 14:40:33  kuznets
  517.  * TreeReRoot tested
  518.  *
  519.  * Revision 1.10  2004/04/08 21:46:35  ucko
  520.  * Use a more foolproof method of supplying NStr::IntToString to TreePrint.
  521.  *
  522.  * Revision 1.9  2004/04/08 18:35:50  kuznets
  523.  * + tree print test
  524.  *
  525.  * Revision 1.8  2004/04/08 11:48:22  kuznets
  526.  * + TreeTraceToRoot test
  527.  *
  528.  * Revision 1.7  2004/01/14 17:38:27  kuznets
  529.  * Reflecting changed in ncbi_tree
  530.  *
  531.  * Revision 1.6  2004/01/14 17:03:28  kuznets
  532.  * + test case for PairTreeTraceNode
  533.  *
  534.  * Revision 1.5  2004/01/14 15:26:24  kuznets
  535.  * Added test case for PairTreeTraceNode
  536.  *
  537.  * Revision 1.4  2004/01/14 14:20:08  kuznets
  538.  * + test for for depth first traversal
  539.  *
  540.  * Revision 1.3  2004/01/12 20:09:41  kuznets
  541.  * Renamed CTreeNWay to CTreeNode
  542.  *
  543.  * Revision 1.2  2004/01/12 15:02:48  kuznets
  544.  * + test for CTreePairNode
  545.  *
  546.  * Revision 1.1  2004/01/09 19:00:40  kuznets
  547.  * Added test for tree
  548.  *
  549.  *
  550.  * ==========================================================================
  551.  */