Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members

test_tree.cpp File Reference

#include <boost/test/auto_unit_test.hpp>
#include <gslib/sapling/tree.h>
#include <gslib/sapling/scribble.h>
#include <gslib/sapling/dump.h>
#include <iostream>
#include <gslib/test/assert_new.h>
#include <gslib/test/del_counter.h>

Include dependency graph for test_tree.cpp:

Include dependency graph

Go to the source code of this file.

Namespaces

namespace  sapling

Classes

class  array_allocator
class  allocator_ref
struct  allocator_ref::rebind

Defines

#define BOOST_AUTO_TEST_MAIN

Typedefs

typedef tree< int > tree_type

Functions

 BOOST_AUTO_UNIT_TEST (test_basic)
tree_type make_tree ()
 BOOST_AUTO_UNIT_TEST (test_release)
 BOOST_AUTO_UNIT_TEST (test_pool)
 BOOST_AUTO_UNIT_TEST (test_iterator)


Define Documentation

#define BOOST_AUTO_TEST_MAIN
 

Definition at line 1 of file test_tree.cpp.


Typedef Documentation

typedef tree< int > tree_type
 

Definition at line 13 of file test_tree.cpp.

Referenced by BOOST_AUTO_UNIT_TEST(), gslib::sapling::dump(), make_tree(), and gslib::sapling::scribbler< Value, Allocator >::scribbler().


Function Documentation

BOOST_AUTO_UNIT_TEST test_iterator   ) 
 

Definition at line 251 of file test_tree.cpp.

References make_tree(), and tree_type.

00251                                       {
00252     
00253     tree_type t = make_tree();
00254     
00255     dump( t, std::cout );
00256     
00257     //  pre order ならそのままの順番になるはず
00258     {
00259         tree_type::pre_order_iterator it = t.begin_pre_order();
00260         int cnt = 0;
00261         for ( ; it != t.end(); ++it, ++cnt ) {
00262             BOOST_CHECK( cnt == *it );
00263         }
00264         BOOST_CHECK( 11 == cnt );
00265         for ( --cnt, --it; it != t.end(); --it, --cnt ) {
00266             BOOST_CHECK( cnt == *it );
00267         }
00268     }
00269     
00270     //  post order なら
00271     //  10
00272     //      2
00273     //          0
00274     //          1
00275     //      8
00276     //          3
00277     //          6
00278     //              4
00279     //              5
00280     //          7
00281     //      9
00282     {
00283         int expect_table[] = {
00284             2,
00285             3,
00286             1,
00287             5,
00288             7,
00289             8,
00290             6,
00291             9,
00292             4,
00293             10,
00294             0
00295         };
00296         tree_type::post_order_iterator it = t.begin_post_order();
00297         int cnt = 0;
00298         for ( ; it != t.end(); ++it, ++cnt ) {
00299             BOOST_CHECK( expect_table[ cnt ] == *it );
00300         }
00301         BOOST_CHECK( 11 == cnt );
00302         for ( --cnt, --it; it != t.end(); --it, --cnt ) {
00303             BOOST_CHECK( expect_table[ cnt ] == *it );
00304         }
00305     }
00306 }

Here is the call graph for this function:

BOOST_AUTO_UNIT_TEST test_pool   ) 
 

Definition at line 219 of file test_tree.cpp.

00219                                   {
00220     test::assert_new::begin();
00221     typedef array_allocator< tree_type::allocation_size, 100 >  ary_alloc_type;
00222     typedef allocator_ref< void, ary_alloc_type >   alloc_ref;
00223     typedef tree<
00224         int,
00225         alloc_ref > pool_tree;
00226     
00227     ary_alloc_type  ary_alloc;
00228     alloc_ref   ary_alloc_ref( &ary_alloc );
00229     pool_tree t( ary_alloc_ref );
00230     scribble( t )
00231         .b( 1 )
00232             .b( 100 )
00233                 ( 34 )
00234                 ( 36 )
00235             .e()
00236             .b( 3563 )
00237                 .b( 32 )
00238                     ( 35 )
00239                     ( 63 )
00240                 .e()
00241                 ( 24 )
00242                 ( 98 )
00243             .e()
00244         .e();
00245     
00246     BOOST_CHECK( 10 == ary_alloc.count() );
00247         
00248     test::assert_new::end();
00249 }

BOOST_AUTO_UNIT_TEST test_release   ) 
 

Definition at line 128 of file test_tree.cpp.

References tree_type.

00128                                      {
00129     using namespace test;
00130     
00131     typedef tree< del_counter > tree_type;
00132     
00133     int delcnt = 0;
00134     {
00135         tree_type   t;
00136         t.root( del_counter( delcnt ) );
00137         delcnt = 0;
00138     }
00139     BOOST_CHECK( 1 == delcnt ); // t 内の del_counter デストラクタ      
00140     
00141     //  tree のデストラクタによる解放を確認
00142     tree_type   t;
00143     {
00144         tree_type   t1;
00145         scribble( t1 )
00146             .b( del_counter( delcnt ) )
00147                 .b( del_counter( delcnt ) )
00148                     ( del_counter( delcnt ) )
00149                     ( del_counter( delcnt ) )
00150                 .e()
00151                 ( del_counter( delcnt ) )
00152                 .b( del_counter( delcnt ) )
00153                     ( del_counter( delcnt ) )
00154                     .b( del_counter( delcnt ) )
00155                         ( del_counter( delcnt ) )
00156                         ( del_counter( delcnt ) )
00157                     .e()
00158                     ( del_counter( delcnt ) )
00159                 .e()
00160                 ( del_counter( delcnt ) )
00161             .e();
00162         t = t1;
00163         
00164         delcnt = 0;
00165     }
00166     BOOST_CHECK( 12 == delcnt );
00167     
00168     //  部分削除
00169     {
00170         tree_type t1( t );
00171         delcnt = 0;
00172         t1.erase( t1.begin().begin().begin() );
00173         BOOST_CHECK( 1 == delcnt );
00174         t1.erase( t1.begin().begin() );
00175         BOOST_CHECK( 3 == delcnt );
00176     }
00177 }

BOOST_AUTO_UNIT_TEST test_basic   ) 
 

Definition at line 15 of file test_tree.cpp.

References tree_type.

00015                                    {
00016     tree_type   t;
00017     BOOST_CHECK( true == t.empty() );
00018     BOOST_CHECK( t.begin() == t.end() );
00019     t.root( 100 );
00020     BOOST_CHECK( false == t.empty() );
00021     BOOST_CHECK( 100 == t.root() );
00022     tree_type::sibling_iterator root = t.begin_sibling();
00023     BOOST_CHECK( 100 == *root );
00024     BOOST_CHECK( t.begin() != t.end() );
00025     BOOST_CHECK( root.begin() == root.end() );
00026 //  BOOST_CHECK( 1 == t.size() );
00027     t.insert( root.end(), 10 );
00028 //  BOOST_CHECK( 2 == t.size() );
00029 //  BOOST_CHECK( 10 == root.front() );
00030     BOOST_CHECK( 10 == *root.begin() );
00031     BOOST_CHECK( root.begin() != root.end() );
00032     tree_type::sibling_iterator child1 = root.begin();
00033     BOOST_CHECK( child1.begin() == child1.end() );
00034     BOOST_CHECK( child1.parent() == root );
00035     BOOST_CHECK( root.parent() == t.end() );
00036     t.insert( root.end(), 11 );
00037     tree_type::sibling_iterator child2 = boost::prior( root.end() );
00038     BOOST_CHECK( 11 == *child2 );
00039     BOOST_CHECK( boost::prior( child2 ) == child1 );
00040     BOOST_CHECK( child2 == boost::next( child1 ) );
00041 
00042     //  ふつうに post_order_iterator テスト
00043     tree_type::post_order_iterator post_it = t.begin_post_order();
00044     BOOST_CHECK( 10 == *post_it++ );
00045     BOOST_CHECK( 11 == *post_it++ );
00046     BOOST_CHECK( 100 == *post_it++ );
00047     BOOST_CHECK( t.end() == post_it );
00048     
00049     {
00050         //  コピーコンストラクタで生成した木に対して post_order_iterator テスト
00051         tree_type t2( t );
00052         post_it = t2.begin_post_order();
00053         BOOST_CHECK( 10 == *post_it++ );
00054         BOOST_CHECK( 11 == *post_it++ );
00055         BOOST_CHECK( 100 == *post_it++ );
00056         BOOST_CHECK( t2.end() == post_it );
00057     }
00058     
00059     {
00060         //  代入演算子で生成した木に対して post_order_iterator テスト
00061         tree_type t3;
00062         t3 = t;
00063         post_it = t3.begin_post_order();
00064         BOOST_CHECK( 10 == *post_it++ );
00065         BOOST_CHECK( 11 == *post_it++ );
00066         BOOST_CHECK( 100 == *post_it++ );
00067         BOOST_CHECK( t3.end() == post_it );
00068     }
00069     
00070     //  解放
00071     t.erase( root );
00072     BOOST_CHECK( true == t.empty() );
00073 
00074     //  多重解放テスト
00075     t.clear();
00076     BOOST_CHECK( true == t.empty() );
00077 }

tree_type make_tree  ) 
 

Definition at line 79 of file test_tree.cpp.

References tree_type.

Referenced by BOOST_AUTO_UNIT_TEST().

00079                       {
00080     //  以下のような木を作る
00081     //  0
00082     //      1
00083     //          2
00084     //          3
00085     //      4
00086     //          5
00087     //          6
00088     //              7
00089     //              8
00090     //          9
00091     //      10
00092     tree_type t;
00093     tree_type::iterator it = t.end();
00094     it = t.insert( it, 0 );
00095         it = t.insert( it.end(), 1 );
00096             t.insert( it.end(), 2 );
00097             t.insert( it.end(), 3 );
00098         it = it.parent();
00099         it = t.insert( it.end(), 4 );
00100             t.insert( it.end(), 5 );
00101             it = t.insert( it.end(), 6 );
00102                 t.insert( it.end(), 7 );
00103                 t.insert( it.end(), 8 );
00104             it = it.parent();
00105             t.insert( it.end(), 9 );
00106         it = it.parent();
00107         it = t.insert( it.end(), 10 );
00108     /*
00109     scribble( t )
00110         .b( 0 )     //  子を持つノードは .b()。xml での <tag>
00111             .b( 1 )
00112                 ( 2 )   //  子を持たないノードは ()。xml での <tag/>
00113                 ( 3 )
00114             .e()
00115             .b( 4 )
00116                 ( 5 )
00117                 .b( 6 )
00118                     ( 7 )
00119                     ( 8 )
00120                 .e()
00121                 ( 9 )
00122             .e()
00123             ( 10 )
00124         .e();       //  終了タグ .e()。xml での </tag>*/
00125     return t;
00126 }


Generated on Sat Nov 27 15:02:49 2004 for sapling by doxygen 1.3.6