#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(). |
|
|
|