#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:

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) | |
|
|
Definition at line 1 of file test_tree.cpp. |
|
|
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(). |
|
|
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:

|
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
|
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 }
|
1.3.6