#include <tree.h>
Collaboration diagram for gslib::sapling::tree< Value, Allocator >:

Public Types | |
| typedef Value | value_type |
| typedef value_type & | reference |
| typedef const value_type & | const_reference |
| typedef size_t | size_type |
| typedef sibling_iterator | iterator |
| typedef const_sibling_iterator | const_iterator |
Public Member Functions | |
| template<typename It> It | insert (It &ioWhere, const Value &v) |
| void | erase (iterator_base &it) |
| void | clear () |
| void | root (const_reference v) |
| ルートが存在しない場合はルートを作成する。 すでにルートが存在する場合は v で上書きする。 | |
| reference | root () |
| const_reference | root () const |
| iterator | begin () |
| iterator | end () |
| const_iterator | begin () const |
| const_iterator | end () const |
| bool | empty () const |
| tree (const Allocator &allocator=Allocator()) | |
| void | swap (tree &other) |
| tree (const tree &other) | |
| tree & | operator= (const tree &other) |
| ~tree () | |
Static Public Attributes | |
| const size_type | npos = ~0 |
| const size_type | allocation_size = sizeof ( node ) |
| tree が一度にアロケーションする大きさ ( メモリプールなどに利用する ) | |
Private Types | |
| typedef Allocator::rebind< node >::other | allocator_type |
Private Member Functions | |
| node * | root_ptr () |
| const node * | root_ptr () const |
| void | connect_root (link *root) |
| void | copy (const_sibling_iterator first, const_sibling_iterator last, sibling_iterator out_last) |
Static Private Member Functions | |
| node * | get_node (link *lnk) |
| bool | has_child (const link *lnk) |
| bool | is_root_end (const link *lnk) |
| node * | get_parent (link *lnk) |
| const node * | get_parent (const link *lnk) |
| bool | is_end (link *lnk) |
| bool | is_back (link *lnk) |
| bool | is_begin (link *lnk) |
| bool | is_root (const link *lnk) |
Private Attributes | |
| allocator_type | allocator_ |
| root_end | end_ |
Definition at line 88 of file tree.h.
|
|||||
|
|
|
|||||
|
Definition at line 543 of file tree.h. Referenced by gslib::sapling::tree< Value, Allocator >::begin(), and gslib::sapling::tree< Value, Allocator >::end(). |
|
|||||
|
|
|
|||||
|
|
|
|||||
|
Definition at line 91 of file tree.h. Referenced by gslib::sapling::tree< Value, Allocator >::root(), and gslib::sapling::tree< Value, Allocator >::node::value(). |
|
|||||
|
Definition at line 93 of file tree.h. Referenced by gslib::sapling::tree< Value, Allocator >::iterator_base::depth(), and gslib::sapling::tree< Value, Allocator >::node::depth(). |
|
|||||
|
Definition at line 90 of file tree.h. Referenced by gslib::sapling::tree< Value, Allocator >::root(). |
|
||||||||||
|
Definition at line 652 of file tree.h.
00652 : 00653 allocator_( allocator ) { 00654 } |
|
||||||||||
Here is the call graph for this function:

|
|||||||||
|
Definition at line 690 of file tree.h. References gslib::sapling::tree< Value, Allocator >::clear().
00690 {
00691 clear();
00692 }
|
Here is the call graph for this function:

|
|||||||||
|
Definition at line 642 of file tree.h. References gslib::sapling::tree< Value, Allocator >::const_iterator.
00642 {
00643 return begin_sibling();
00644 }
|
|
|||||||||
|
Definition at line 634 of file tree.h. Referenced by gslib::sapling::tree< Value, Allocator >::clear().
00634 {
00635 return begin_sibling();
00636 }
|
|
|||||||||
|
Definition at line 590 of file tree.h. References gslib::sapling::tree< Value, Allocator >::begin(), and gslib::sapling::tree< Value, Allocator >::erase(). Referenced by gslib::sapling::tree< Value, Allocator >::~tree().
|
Here is the call graph for this function:

|
||||||||||
|
||||||||||||||||||||
|
Definition at line 603 of file tree.h. References gslib::sapling::tree< Value, Allocator >::const_sibling_iterator::begin(), gslib::sapling::tree< Value, Allocator >::const_sibling_iterator::end(), and gslib::sapling::tree< Value, Allocator >::insert(). Referenced by gslib::sapling::tree< Value, Allocator >::tree().
|
Here is the call graph for this function:

|
|||||||||
|
|||||||||
|
Definition at line 646 of file tree.h. References gslib::sapling::tree< Value, Allocator >::const_iterator.
00646 {
00647 return end_sibling();
00648 }
|
|
|||||||||
|
Definition at line 638 of file tree.h. Referenced by gslib::sapling::dump(), and gslib::sapling::tree< Value, Allocator >::root().
00638 {
00639 return end_sibling();
00640 }
|
|
||||||||||
|
Definition at line 568 of file tree.h. References gslib::sapling::tree< Value, Allocator >::iterator_base::cur_, gslib::sapling::tree< Value, Allocator >::empty(), gslib::sapling::tree< Value, Allocator >::link::next, gslib::sapling::tree< Value, Allocator >::link::prev, and gslib::sapling::tree< Value, Allocator >::iterator_base::self(). Referenced by gslib::sapling::tree< Value, Allocator >::clear().
00568 {
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 }
|
Here is the call graph for this function:

|
||||||||||
|
Definition at line 236 of file tree.h. References gslib::sapling::tree< Value, Allocator >::link::self. Referenced by gslib::sapling::tree< Value, Allocator >::iterator_base::depth(), and gslib::sapling::tree< Value, Allocator >::is_end().
00236 {
00237 return static_cast< node* >( lnk->self );
00238 }
|
|
||||||||||
|
Definition at line 254 of file tree.h. References gslib::sapling::tree< Value, Allocator >::node::end(), gslib::sapling::tree< Value, Allocator >::node::parent(), and gslib::sapling::tree< Value, Allocator >::link::self.
00254 {
00255 const node* n = static_cast< const node* >( lnk->self );
00256 return lnk == n->end() ? n : static_cast< const node* >( n->parent() );
00257 }
|
Here is the call graph for this function:

|
||||||||||
|
Definition at line 249 of file tree.h. References gslib::sapling::tree< Value, Allocator >::node::end(), gslib::sapling::tree< Value, Allocator >::node::parent(), and gslib::sapling::tree< Value, Allocator >::link::self. Referenced by gslib::sapling::tree< Value, Allocator >::insert(), gslib::sapling::tree< Value, Allocator >::is_back(), gslib::sapling::tree< Value, Allocator >::is_begin(), gslib::sapling::tree< Value, Allocator >::is_root(), gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::parent(), gslib::sapling::tree< Value, Allocator >::const_post_order_iterator::parent(), gslib::sapling::tree< Value, Allocator >::const_sibling_iterator::parent(), gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::up(), and gslib::sapling::tree< Value, Allocator >::const_post_order_iterator::up().
00249 {
00250 node* n = static_cast< node* >( lnk->self );
00251 return lnk == n->end() ? n : static_cast< node* >( n->parent() );
00252 }
|
Here is the call graph for this function:

|
||||||||||
|
Definition at line 240 of file tree.h. References gslib::sapling::tree< Value, Allocator >::node::begin(), gslib::sapling::tree< Value, Allocator >::node::end(), and gslib::sapling::tree< Value, Allocator >::link::self. Referenced by gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::bottom_back(), and gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::increment().
00240 {
00241 const node* n = static_cast< const node* >( lnk->self );
00242 return n->begin() != n->end();
00243 }
|
Here is the call graph for this function:

|
||||||||||||||||||||
Here is the call graph for this function:

|
||||||||||
|
Definition at line 263 of file tree.h. References gslib::sapling::tree< Value, Allocator >::node::end(), gslib::sapling::tree< Value, Allocator >::get_parent(), and gslib::sapling::tree< Value, Allocator >::node::prev().
00263 {
00264 return lnk == get_parent( lnk )->end()->prev;
00265 }
|
Here is the call graph for this function:

|
||||||||||
|
Definition at line 267 of file tree.h. References gslib::sapling::tree< Value, Allocator >::node::begin(), and gslib::sapling::tree< Value, Allocator >::get_parent(). Referenced by gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::decrement(), and gslib::sapling::tree< Value, Allocator >::const_post_order_iterator::decrement().
00267 {
00268 return lnk == get_parent( lnk )->begin();
00269 }
|
Here is the call graph for this function:

|
||||||||||
|
Definition at line 259 of file tree.h. References gslib::sapling::tree< Value, Allocator >::node::end(), and gslib::sapling::tree< Value, Allocator >::get_node(). Referenced by gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::increment(), and gslib::sapling::tree< Value, Allocator >::const_post_order_iterator::increment().
|
Here is the call graph for this function:

|
||||||||||
|
Definition at line 271 of file tree.h. References gslib::sapling::tree< Value, Allocator >::get_parent(), and gslib::sapling::tree< Value, Allocator >::is_root_end(). Referenced by gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::decrement(), and gslib::sapling::tree< Value, Allocator >::node::depth().
00271 {
00272 return is_root_end( get_parent( lnk ) );
00273 }
|
Here is the call graph for this function:

|
||||||||||
|
Definition at line 245 of file tree.h. Referenced by gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::decrement(), gslib::sapling::tree< Value, Allocator >::const_post_order_iterator::decrement(), gslib::sapling::tree< Value, Allocator >::node::depth(), gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::increment(), gslib::sapling::tree< Value, Allocator >::const_post_order_iterator::increment(), and gslib::sapling::tree< Value, Allocator >::is_root().
00245 {
00246 return 0 == static_cast< const root_end* >( lnk )->parent;
00247 }
|
|
||||||||||
|
Definition at line 684 of file tree.h. References gslib::sapling::tree< Value, Allocator >::swap().
00684 {
00685 tree deadbeef( other );
00686 deadbeef.swap( *this );
00687 return *this;
00688 }
|
Here is the call graph for this function:

|
|||||||||
|
Definition at line 630 of file tree.h. References gslib::sapling::tree< Value, Allocator >::root_ptr(), gslib::sapling::tree< Value, Allocator >::node::value(), and gslib::sapling::tree< Value, Allocator >::value_type.
00630 {
00631 return root_ptr() ? root_ptr()->value() : *( ( value_type* ) 0 );
00632 }
|
Here is the call graph for this function:

|
|||||||||
|
Definition at line 627 of file tree.h. References gslib::sapling::tree< Value, Allocator >::reference, gslib::sapling::tree< Value, Allocator >::root_ptr(), gslib::sapling::tree< Value, Allocator >::node::value(), and gslib::sapling::tree< Value, Allocator >::value_type. Referenced by gslib::sapling::tree< Value, Allocator >::root(), and gslib::sapling::tree< Value, Allocator >::tree().
00627 {
00628 return root_ptr() ? root_ptr()->value() : *( ( value_type* ) 0 );
00629 }
|
Here is the call graph for this function:

|
||||||||||
|
ルートが存在しない場合はルートを作成する。 すでにルートが存在する場合は v で上書きする。
Definition at line 617 of file tree.h. References gslib::sapling::tree< Value, Allocator >::empty(), gslib::sapling::tree< Value, Allocator >::end(), gslib::sapling::tree< Value, Allocator >::insert(), and gslib::sapling::tree< Value, Allocator >::root(). Referenced by gslib::sapling::tree< Value, Allocator >::tree().
|
Here is the call graph for this function:

|
|||||||||
|
Definition at line 283 of file tree.h. References gslib::sapling::tree< Value, Allocator >::end_, gslib::sapling::tree< Value, Allocator >::link::next, and gslib::sapling::tree< Value, Allocator >::link::self.
|
|
|||||||||
|
Definition at line 280 of file tree.h. References gslib::sapling::tree< Value, Allocator >::end_, gslib::sapling::tree< Value, Allocator >::link::next, and gslib::sapling::tree< Value, Allocator >::link::self. Referenced by gslib::sapling::tree< Value, Allocator >::insert(), and gslib::sapling::tree< Value, Allocator >::root().
|
|
||||||||||
|
Definition at line 656 of file tree.h. References gslib::sapling::tree< Value, Allocator >::allocator_, gslib::sapling::tree< Value, Allocator >::connect_root(), gslib::sapling::tree< Value, Allocator >::end_, gslib::sapling::tree< Value, Allocator >::link::next, and gslib::sapling::tree< Value, Allocator >::link::prev. Referenced by gslib::sapling::tree< Value, Allocator >::operator=().
00656 {
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 }
|
Here is the call graph for this function:

|
|||||
|
tree が一度にアロケーションする大きさ ( メモリプールなどに利用する )
|
|
|||||
|
Definition at line 277 of file tree.h. Referenced by gslib::sapling::tree< Value, Allocator >::swap(). |
|
|||||
|
|||||
|
|
1.3.6