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

tree.h

Go to the documentation of this file.
00001 #ifndef GAME_SYOKUNIN_COM_SAPLING_TREE_H
00002 
00003 #define GAME_SYOKUNIN_COM_SAPLING_TREE_H
00004 
00005 /*
00006 gslib/sapling/tree.h
00007 
00008 zlib/libpng license
00009 -------------------
00010 
00011 Copyright (C) 2004 &o
00012 
00013 This software is provided 'as-is', without any express or implied warranty. In n
00014 o event will the authors be held liable for any damages arising from the use of 
00015 this software.
00016 
00017 Permission is granted to anyone to use this software for any purpose, including 
00018 commercial applications, and to alter it and redistribute it freely, subject to 
00019 the following restrictions:
00020 
00021 The origin of this software must not be misrepresented; you must not claim that 
00022 you wrote the original software. If you use this software in a product, an ackno
00023 wledgment in the product documentation would be appreciated but is not required.
00024 
00025 Altered source versions must be plainly marked as such, and must not be misrepre
00026 sented as being the original software.
00027 This notice may not be removed or altered from any source distribution.
00028 
00029 project site : https://sourceforge.jp/projects/gslib/
00030 my site : http://www.game-syokunin.com/
00031 --------------------------------------------------------------------------------
00032 
00033 法的には、上記の原文のほうが有効なので、より厳密には日本語訳よりも原文を参考にし
00034 てください。日本語訳は、http://opensource.jp/licenses/zlib-license.html から頂い
00035 てきました。
00036 
00037 zlib/libpngライセンス ( 日本語訳 )
00038 
00039 Copyright (C) 2004 &o
00040 
00041 本ソフトウェアは「現状のまま」で、明示であるか暗黙であるかを問わず、何らの保証も
00042 なく提供されます。本ソフトウェアの使用によって生じるいかなる損害についても、作者
00043 は一切の責任を負わないものとします。 以下の制限に従う限り、商用アプリケーション
00044 を含めて、本ソフトウェアを任意の目的に使用し、自由に改変して再頒布することをすべ
00045 ての人に許可します。
00046 
00047 本ソフトウェアの出自について虚偽の表示をしてはなりません。あなたがオリジナルのソ
00048 フトウェアを作成したと主張してはなりません。あなたが本ソフトウェアを製品内で使用
00049 する場合、製品の文書に謝辞をれていただければ幸いですが、必須ではありません。
00050 ソースを変更した場合は、そのことを明示しなければなりません。オリジナルのソフトウ
00051 ェアであるという虚偽の表示をしてはなりません。
00052 ソースの頒布物から、この表示を削除したり、表示の内容を変更したりしてはなりません
00053 
00054 
00055 project site : https://sourceforge.jp/projects/gslib/
00056 my site : http://www.game-syokunin.com/
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                     //  root 作成
00620                     insert( end(), v );
00621                 } else {
00622                     //  root 上書き
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

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