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