00001 #ifndef GAME_SYOKUNIN_COM_SAPLING_TREE_H
00002
00003 #define GAME_SYOKUNIN_COM_SAPLING_TREE_H
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059 #include <boost/assert.hpp>
00060 #include <boost/iterator/iterator_facade.hpp>
00061 #include <memory>
00062
00063 #pragma warning( disable : 4355 )
00064
00065 namespace gslib {
00066 namespace sapling {
00067
00069
00087 template < typename Value, typename Allocator = std::allocator< void > >
00088 class tree {
00089 public:
00090 typedef Value value_type;
00091 typedef value_type& reference;
00092 typedef const value_type& const_reference;
00093 typedef size_t size_type;
00094 static const size_type npos = ~0;
00095
00096 private:
00097 struct link {
00098 link* self;
00099 link* prev;
00100 link* next;
00101
00102 link() : self( this ), prev( this ), next( this ) {}
00103 link( link* ioSelf ) : self( ioSelf ), prev( this ), next( this ) {}
00104 };
00105
00106 struct root_end : public link {
00107 root_end* parent;
00108
00109 root_end() : link(), parent( 0 ) {}
00110 root_end( root_end* ioSelf ) : link( ioSelf ), parent( 0 ) {}
00111 };
00112
00113 struct value_holder : public root_end {
00114 Value value;
00115
00116 value_holder() : root_end() {}
00117 value_holder( const_reference v ) : value( v ), root_end( this ) {}
00118 };
00119
00121 class node : public value_holder {
00122 link self_children_;
00123 public:
00124
00126
00131 size_type depth() const {
00132 if ( is_root_end( this ) ) {
00133 return npos;
00134 }
00135 size_type i = 0;
00136 const node* n = this;
00137 while ( false == is_root( n ) ) {
00138 ++i;
00139 n = n->parent();
00140 }
00141 return i;
00142 }
00143 node* parent() {
00144 return static_cast< node* >( value_holder::parent );
00145 }
00146 node* next() {
00147 return static_cast< node* >( value_holder::next );
00148 }
00149 node* prev() {
00150 return static_cast< node* >( value_holder::prev );
00151 }
00152 node* begin() {
00153 return static_cast< node* >( self_children_.next );
00154 }
00155 node* end() {
00156 return static_cast< node* >( &self_children_ );
00157 }
00158 const node* parent() const {
00159 return static_cast< const node* >( value_holder::parent );
00160 }
00161 const node* next() const {
00162 return static_cast< const node* >( value_holder::next );
00163 }
00164 const node* prev() const {
00165 return static_cast< const node* >( value_holder::prev );
00166 }
00167 const node* begin() const {
00168 return static_cast< const node* >( self_children_.next );
00169 }
00170 const node* end() const {
00171 return static_cast< const node* >( &self_children_ );
00172 }
00173 reference value() {
00174 return value_holder::value;
00175 }
00176 const_reference value() const {
00177 return value_holder::value;
00178 }
00179 void next( link* n ) {
00180 value_holder::next = n;
00181 }
00182 void prev( link* p ) {
00183 value_holder::prev = p;
00184 }
00185 void parent( link* p ) {
00186 value_holder::parent = static_cast< root_end* >( p );
00187 }
00188
00189 node( const_reference v ) :
00190 value_holder( v ),
00191 self_children_( this ) {
00192 }
00193 };
00194
00195 class iterator_base {
00196 protected:
00197 friend class tree;
00198
00199 value_holder* cur_;
00200
00201 void link_next() {
00202 cur_ = static_cast< value_holder* >( cur_->next );
00203 }
00204 void link_prev() {
00205 cur_ = static_cast< value_holder* >( cur_->prev );
00206 }
00207
00208 node* self() {
00209 return static_cast< node* >( cur_->self );
00210 }
00211 iterator_base() {}
00212 iterator_base( value_holder* n ) : cur_( n ) {}
00213
00214 public:
00215 bool equal( const iterator_base& other ) const {
00216 return cur_ == other.cur_;
00217 }
00218
00219 size_type depth() const {
00220 BOOST_ASSERT( 0 != cur_ );
00221 return get_node( cur_ )->depth();
00222 }
00223
00224 const_reference dereference() const {
00225 return cur_->value;
00226 }
00227
00228 bool operator == ( const iterator_base& other ) const {
00229 return equal( other );
00230 }
00231 bool operator != ( const iterator_base& other ) const {
00232 return !equal( other );
00233 }
00234 };
00235
00236 static node* get_node( link* lnk ) {
00237 return static_cast< node* >( lnk->self );
00238 }
00239
00240 static bool has_child( const link* lnk ) {
00241 const node* n = static_cast< const node* >( lnk->self );
00242 return n->begin() != n->end();
00243 }
00244
00245 static bool is_root_end( const link* lnk ) {
00246 return 0 == static_cast< const root_end* >( lnk )->parent;
00247 }
00248
00249 static node* get_parent( link* lnk ) {
00250 node* n = static_cast< node* >( lnk->self );
00251 return lnk == n->end() ? n : static_cast< node* >( n->parent() );
00252 }
00253
00254 static const node* get_parent( const link* lnk ) {
00255 const node* n = static_cast< const node* >( lnk->self );
00256 return lnk == n->end() ? n : static_cast< const node* >( n->parent() );
00257 }
00258
00259 static bool is_end( link* lnk ) {
00260 return lnk == get_node( lnk )->end();
00261 }
00262
00263 static bool is_back( link* lnk ) {
00264 return lnk == get_parent( lnk )->end()->prev;
00265 }
00266
00267 static bool is_begin( link* lnk ) {
00268 return lnk == get_parent( lnk )->begin();
00269 }
00270
00271 static bool is_root( const link* lnk ) {
00272 return is_root_end( get_parent( lnk ) );
00273 }
00274
00275 typedef typename Allocator::rebind< node >::other allocator_type;
00276
00277 allocator_type allocator_;
00278 root_end end_;
00279
00280 node* root_ptr() {
00281 return static_cast< node* >( end_.next->self );
00282 }
00283 const node* root_ptr() const {
00284 return static_cast< node* >( end_.next->self );
00285 }
00286
00287 public:
00288 static const size_type
00289 allocation_size = sizeof ( node );
00290
00291 class const_sibling_iterator :
00292 public iterator_base,
00293 public boost::iterator_facade<
00294 const_sibling_iterator,
00295 const value_type,
00296 boost::bidirectional_traversal_tag > {
00297 public:
00298 void increment() {
00299 iterator_base::link_next();
00300 }
00301 void decrement() {
00302 iterator_base::link_prev();
00303 }
00304
00305 const_sibling_iterator parent() {
00306 BOOST_ASSERT( cur_ && self() );
00307 return const_sibling_iterator( get_parent( cur_ ) );
00308 }
00309
00310 const_sibling_iterator next() {
00311 BOOST_ASSERT( cur_ && self() );
00312 return const_sibling_iterator( self()->next() );
00313 }
00314
00315 const_sibling_iterator prev() {
00316 BOOST_ASSERT( cur_ && self() );
00317 return const_sibling_iterator( self()->prev() );
00318 }
00319
00320 const_sibling_iterator begin() {
00321 BOOST_ASSERT( cur_ && self() );
00322 return const_sibling_iterator( self()->begin() );
00323 }
00324
00325 const_sibling_iterator end() {
00326 BOOST_ASSERT( cur_ && self() );
00327 return const_sibling_iterator( self()->end() );
00328 }
00329
00330 const_sibling_iterator() {}
00331 const_sibling_iterator( const value_holder* lnk ) : iterator_base( const_cast< value_holder* >( lnk ) ) {}
00332 };
00333
00334 #define ITERATOR_COMMON( x ) \
00335 class x##_iterator :\
00336 public const_##x##_iterator {\
00337 public:\
00338 reference dereference() const {\
00339 return cur_->value;\
00340 }\
00341 reference operator * () const {\
00342 return dereference();\
00343 }\
00344 value_type* operator -> () const {\
00345 return &dereference();\
00346 }\
00347 x##_iterator& operator ++ () {\
00348 return static_cast< x##_iterator& >( const_##x##_iterator::operator ++ () );\
00349 }\
00350 x##_iterator operator ++ ( int ) {\
00351 return static_cast< x##_iterator& >( const_##x##_iterator::operator ++ ( int() ) );\
00352 }\
00353 x##_iterator& operator -- () {\
00354 return static_cast< x##_iterator& >( const_##x##_iterator::operator -- () );\
00355 }\
00356 x##_iterator operator -- ( int ) {\
00357 return static_cast< x##_iterator& >( const_##x##_iterator::operator -- ( int() ) );\
00358 }\
00359 x##_iterator parent() {\
00360 return static_cast< x##_iterator& >( const_##x##_iterator::parent() );\
00361 }\
00362 x##_iterator next() {\
00363 BOOST_ASSERT( cur_ && cur_->self );\
00364 return static_cast< x##_iterator& >( const_##x##_iterator::next() );\
00365 }\
00366 x##_iterator prev() {\
00367 BOOST_ASSERT( cur_ && cur_->self );\
00368 return static_cast< x##_iterator& >( const_##x##_iterator::prev() );\
00369 }\
00370 x##_iterator begin() {\
00371 BOOST_ASSERT( cur_ && cur_->self );\
00372 return static_cast< x##_iterator& >( const_##x##_iterator::begin() );\
00373 }\
00374 x##_iterator end() {\
00375 BOOST_ASSERT( cur_ && cur_->self );\
00376 return static_cast< x##_iterator& >( const_##x##_iterator::end() );\
00377 }\
00378 x##_iterator() {}\
00379 x##_iterator( value_holder* lnk ) : const_##x##_iterator( lnk ) {}\
00380 };\
00381 x##_iterator end_##x##() { return x##_iterator( static_cast< value_holder* >( &end_ ) ); }\
00382 x##_iterator begin_##x##() { return ++end_##x##(); }\
00383 const_##x##_iterator end_##x##() const { return const_##x##_iterator( static_cast< const value_holder* >( &end_ ) ); }\
00384 const_##x##_iterator begin_##x##() const { return ++end_##x##(); }
00385
00386 ITERATOR_COMMON( sibling )
00387
00388 class const_post_order_iterator :
00389 public iterator_base,
00390 public boost::iterator_facade<
00391 const_post_order_iterator,
00392 const Value,
00393 boost::bidirectional_traversal_tag > {
00394
00395 void down() {
00396 cur_ = self()->begin();
00397 }
00398 void up() {
00399 cur_ = get_parent( cur_ );
00400 }
00401
00402 friend class tree;
00403
00405 void bottom() {
00406 while ( self()->begin() != self()->end() ) {
00407 down();
00408 }
00409 }
00410 public:
00411 void increment() {
00412 iterator_base::link_next();
00413 if ( is_root_end( cur_ ) ) {
00414
00415 return;
00416 } else if ( is_end( cur_ ) ) {
00417
00418 up();
00419 return;
00420 }
00421
00422 bottom();
00423 }
00424
00425 void decrement() {
00426 while ( false == is_root_end( cur_ ) && is_begin( cur_ ) ) {
00427
00428 up();
00429 }
00430 if ( 0 != self()->parent() ) {
00431 iterator_base::link_prev();
00432 }
00433 }
00434 const_post_order_iterator parent() {
00435 BOOST_ASSERT( cur_ && self() );
00436 return const_post_order_iterator( get_parent( cur_ ) );
00437 }
00438
00439 const_post_order_iterator next() {
00440 BOOST_ASSERT( cur_ && self() );
00441 return const_post_order_iterator( self()->next() );
00442 }
00443
00444 const_post_order_iterator prev() {
00445 BOOST_ASSERT( cur_ && self() );
00446 return const_post_order_iterator( self()->prev() );
00447 }
00448
00449 const_post_order_iterator begin() {
00450 BOOST_ASSERT( cur_ && self() );
00451 return const_post_order_iterator( self()->begin() );
00452 }
00453
00454 const_post_order_iterator end() {
00455 return *this;
00456 }
00457 const_post_order_iterator() {}
00458 const_post_order_iterator( const value_holder* lnk ) : iterator_base( const_cast< value_holder* >( lnk ) ) {}
00459 };
00460
00461 ITERATOR_COMMON( post_order )
00462
00463 class const_pre_order_iterator :
00464 public iterator_base,
00465 public boost::iterator_facade<
00466 const_pre_order_iterator,
00467 const Value,
00468 boost::bidirectional_traversal_tag > {
00469
00470 void down_front() {
00471 cur_ = self()->begin();
00472 }
00473
00474 void down_back() {
00475 cur_ = self()->end()->prev();
00476 }
00477 void up() {
00478 cur_ = get_parent( cur_ );
00479 }
00480
00481 friend class tree;
00482
00484 void bottom_back() {
00485 while ( has_child( cur_ ) ) {
00486 down_back();
00487 }
00488 }
00489 public:
00490 void increment() {
00491 if ( is_root_end( cur_ ) ) {
00492 iterator_base::link_next();
00493 } else if ( has_child( cur_ ) ) {
00494 down_front();
00495 } else {
00496 iterator_base::link_next();
00497 while ( false == is_root_end( cur_ ) && is_end( cur_ ) ) {
00498
00499 up();
00500 iterator_base::link_next();
00501 }
00502 }
00503 }
00504
00505 void decrement() {
00506 if ( false == is_root_end( cur_ ) && ( is_root( cur_ ) || is_begin( cur_ ) ) ) {
00507 up();
00508 } else {
00509 iterator_base::link_prev();
00510 bottom_back();
00511 }
00512 }
00513 const_pre_order_iterator parent() {
00514 BOOST_ASSERT( cur_ && self() );
00515 return const_pre_order_iterator( get_parent( cur_ ) );
00516 }
00517
00518 const_pre_order_iterator next() {
00519 BOOST_ASSERT( cur_ && self() );
00520 return const_pre_order_iterator( self()->next() );
00521 }
00522
00523 const_pre_order_iterator prev() {
00524 BOOST_ASSERT( cur_ && self() );
00525 return const_pre_order_iterator( self()->prev() );
00526 }
00527
00528 const_pre_order_iterator begin() {
00529 BOOST_ASSERT( cur_ && self() );
00530 return const_pre_order_iterator( self()->begin() );
00531 }
00532
00533 const_pre_order_iterator end() {
00534 return *this;
00535 }
00536 const_pre_order_iterator() {}
00537 const_pre_order_iterator( const value_holder* lnk ) : iterator_base( const_cast< value_holder* >( lnk ) ) {}
00538 };
00539
00540 ITERATOR_COMMON( pre_order )
00541
00542 typedef sibling_iterator iterator;
00543 typedef const_sibling_iterator const_iterator;
00544
00545 template < typename It >
00546 It insert( It& ioWhere, const Value& v ) {
00547 node* n;
00548 if ( &end_ == ioWhere.cur_ ) {
00549 BOOST_ASSERT( empty() );
00550 n = new( allocator_.allocate( 1 ) ) node( v );
00551 connect_root( n );
00552 } else {
00553 BOOST_ASSERT( root_ptr() != ioWhere.cur_ );
00554 value_holder* w = ioWhere.cur_;
00555 link* p = ioWhere.cur_->prev;
00556
00557 n = new( allocator_.allocate( 1 ) ) node( v );
00558
00559 p->next = n;
00560 n->prev( p );
00561 n->parent( get_parent( w ) );
00562 n->next( w );
00563 w->prev = n;
00564 }
00565 return It( n );
00566 }
00567
00568 void erase( iterator_base& it ) {
00569 if ( empty() ) {
00570
00571 return;
00572 }
00573
00574 post_order_iterator first = post_order_iterator( it.self() );
00575 first.bottom();
00576 post_order_iterator last = post_order_iterator( it.self() );
00577 for ( post_order_iterator j = first; j != last; ) {
00578 post_order_iterator del( j++ );
00579 del.self()->~node();
00580 allocator_.deallocate( del.self(), 1 );
00581 }
00582 link* n = it.cur_->next;
00583 link* p = it.cur_->prev;
00584 p->next = n;
00585 n->prev = p;
00586 it.self()->~node();
00587 allocator_.deallocate( it.self(), 1 );
00588 }
00589
00590 void clear() {
00591 erase( begin() );
00592 }
00593
00594 private:
00595 void connect_root( link* root ) {
00596 BOOST_ASSERT( root == root->self );
00597 end_.next = root;
00598 end_.prev = root;
00599 root->next = &end_;
00600 root->prev = &end_;
00601 static_cast< node* >( root )->parent( &end_ );
00602 }
00603 void copy( const_sibling_iterator first, const_sibling_iterator last, sibling_iterator out_last ) {
00604 for ( const_sibling_iterator it = first; it != last; ++it ) {
00605 copy(
00606 it.begin(),
00607 it.end(),
00608 insert( out_last, *it ).end() );
00609 }
00610 }
00611 public:
00613
00617 void root( const_reference v ) {
00618 if ( empty() ) {
00619
00620 insert( end(), v );
00621 } else {
00622
00623 root() = v;
00624 }
00625 }
00626
00627 reference root() {
00628 return root_ptr() ? root_ptr()->value() : *( ( value_type* ) 0 );
00629 }
00630 const_reference root() const {
00631 return root_ptr() ? root_ptr()->value() : *( ( value_type* ) 0 );
00632 }
00633
00634 iterator begin() {
00635 return begin_sibling();
00636 }
00637
00638 iterator end() {
00639 return end_sibling();
00640 }
00641
00642 const_iterator begin() const {
00643 return begin_sibling();
00644 }
00645
00646 const_iterator end() const {
00647 return end_sibling();
00648 }
00649
00650 bool empty() const { return end_.next == &end_; }
00651
00652 explicit tree( const Allocator& allocator = Allocator() ) :
00653 allocator_( allocator ) {
00654 }
00655
00656 void swap( tree& other ) {
00657 std::swap( allocator_, other.allocator_ );
00658 if ( end_.prev == &end_ ) {
00659 if ( other.end_.next != &other.end_ ) {
00660 connect_root( other.end_.next );
00661 }
00662 other.end_.prev = &other.end_;
00663 other.end_.next = &other.end_;
00664 } else if ( other.end_.next == &other.end_ ) {
00665 other.connect_root( end_.next );
00666 end_.prev = &end_;
00667 end_.next = &end_;
00668 } else {
00669
00670 link* other_root = other.end_.next;
00671 other.connect_root( end_.next );
00672 connect_root( other_root );
00673 }
00674 }
00675
00676 tree( const tree& other ) {
00677 if ( false == other.empty() ) {
00678 root( other.root() );
00679 const_sibling_iterator it = other.begin_sibling();
00680 copy( it.begin(), it.end(), begin_sibling().end() );
00681 }
00682 }
00683
00684 tree& operator = ( const tree& other ) {
00685 tree deadbeef( other );
00686 deadbeef.swap( *this );
00687 return *this;
00688 }
00689
00690 ~tree() {
00691 clear();
00692 }
00693
00694 #undef ITERATOR_COMMON
00695 };
00696 }
00697 }
00698
00699 #endif