00001 #define BOOST_AUTO_TEST_MAIN
00002 #include <boost/test/auto_unit_test.hpp>
00003 #include <gslib/sapling/tree.h>
00004 #include <gslib/sapling/scribble.h>
00005 #include <gslib/sapling/dump.h>
00006 #include <iostream>
00007 #include <gslib/test/assert_new.h>
00008 #include <gslib/test/del_counter.h>
00009
00010 using namespace gslib;
00011 using namespace sapling;
00012
00013 typedef tree< int > tree_type;
00014
00015 BOOST_AUTO_UNIT_TEST( test_basic ) {
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
00027 t.insert( root.end(), 10 );
00028
00029
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
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
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
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 }
00078
00079 tree_type make_tree() {
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
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
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125 return t;
00126 }
00127
00128 BOOST_AUTO_UNIT_TEST( test_release ) {
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 );
00140
00141
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 }
00178
00179 template < size_t BlockSize, size_t NumBlock >
00180 class array_allocator {
00181 char array_[ BlockSize * NumBlock ];
00182 char* cur_;
00183 int count_;
00184 public:
00185 int count() const { return count_; }
00186 array_allocator() {
00187 cur_ = array_;
00188 count_ = 0;
00189 }
00190 void* allocate( size_t n ) {
00191 char* result = cur_;
00192 cur_ += BlockSize;
00193 ++count_;
00194 return cur_;
00195 }
00196 void deallocate( void* adrs, size_t n ) {}
00197 };
00198
00199 template < typename Value, typename Allocator >
00200 class allocator_ref {
00201 Allocator* allocator_;
00202 public:
00203 Allocator* get() const { return allocator_; }
00204 template < typename Other >
00205 struct rebind {
00206 typedef allocator_ref< Other, Allocator > other;
00207 };
00208 allocator_ref( Allocator* allocator = 0 ) : allocator_( allocator ) {}
00209 template < typename Other >
00210 allocator_ref( const allocator_ref< Other, Allocator >& other ) : allocator_( other.get() ) {}
00211 Value* allocate( size_t n ) {
00212 return reinterpret_cast< Value* >( allocator_->allocate( n ) );
00213 }
00214 void deallocate( void* adrs, size_t n ) {
00215 allocator_->deallocate( adrs, n );
00216 }
00217 };
00218
00219 BOOST_AUTO_UNIT_TEST( test_pool ) {
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 }
00250
00251 BOOST_AUTO_UNIT_TEST( test_iterator ) {
00252
00253 tree_type t = make_tree();
00254
00255 dump( t, std::cout );
00256
00257
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
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281
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 }