#include <tree.h>
gslib::sapling::tree< Value, Allocator >のコラボレーション図
Public 型 | |
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 メソッド | |
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 変数 | |
const size_type | npos = ~0 |
const size_type | allocation_size = sizeof ( node ) |
tree が一度にアロケーションする大きさ ( メモリプールなどに利用する ) | |
Private 型 | |
typedef Allocator::rebind< node >::other | allocator_type |
Private メソッド | |
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 メソッド | |
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 変数 | |
allocator_type | allocator_ |
root_end | end_ |
|
|
|
参照元 gslib::sapling::tree< Value, Allocator >::begin(), と gslib::sapling::tree< Value, Allocator >::end(). |
|
|
|
|
|
参照元 gslib::sapling::tree< Value, Allocator >::root(), と gslib::sapling::tree< Value, Allocator >::node::value(). |
|
参照元 gslib::sapling::tree< Value, Allocator >::iterator_base::depth(), と gslib::sapling::tree< Value, Allocator >::node::depth(). |
|
|
|
00652 : 00653 allocator_( allocator ) { 00654 } |
|
関数の呼び出しグラフ:
|
参照先 gslib::sapling::tree< Value, Allocator >::clear().
00690 { 00691 clear(); 00692 } |
関数の呼び出しグラフ:
|
参照先 gslib::sapling::tree< Value, Allocator >::const_iterator.
00642 {
00643 return begin_sibling();
00644 }
|
|
参照元 gslib::sapling::tree< Value, Allocator >::clear().
00634 {
00635 return begin_sibling();
00636 }
|
|
参照先 gslib::sapling::tree< Value, Allocator >::begin(), と gslib::sapling::tree< Value, Allocator >::erase(). 参照元 gslib::sapling::tree< Value, Allocator >::~tree().
|
関数の呼び出しグラフ:
|
|
関数の呼び出しグラフ:
|
|
参照先 gslib::sapling::tree< Value, Allocator >::const_iterator.
00646 {
00647 return end_sibling();
00648 }
|
|
参照元 gslib::sapling::dump(), と gslib::sapling::tree< Value, Allocator >::root().
00638 {
00639 return end_sibling();
00640 }
|
|
参照先 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, と gslib::sapling::tree< Value, Allocator >::iterator_base::self(). 参照元 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 } |
関数の呼び出しグラフ:
|
参照先 gslib::sapling::tree< Value, Allocator >::link::self. 参照元 gslib::sapling::tree< Value, Allocator >::iterator_base::depth(), と gslib::sapling::tree< Value, Allocator >::is_end().
00236 {
00237 return static_cast< node* >( lnk->self );
00238 }
|
|
参照先 gslib::sapling::tree< Value, Allocator >::node::end(), gslib::sapling::tree< Value, Allocator >::node::parent(), と 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 } |
関数の呼び出しグラフ:
|
関数の呼び出しグラフ:
|
参照先 gslib::sapling::tree< Value, Allocator >::node::begin(), gslib::sapling::tree< Value, Allocator >::node::end(), と gslib::sapling::tree< Value, Allocator >::link::self. 参照元 gslib::sapling::tree< Value, Allocator >::const_pre_order_iterator::bottom_back(), と 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 } |
関数の呼び出しグラフ:
|
関数の呼び出しグラフ:
|
参照先 gslib::sapling::tree< Value, Allocator >::node::end(), gslib::sapling::tree< Value, Allocator >::get_parent(), と gslib::sapling::tree< Value, Allocator >::node::prev().
00263 { 00264 return lnk == get_parent( lnk )->end()->prev; 00265 } |
関数の呼び出しグラフ:
|
関数の呼び出しグラフ:
|
関数の呼び出しグラフ:
|
関数の呼び出しグラフ:
|
|
参照先 gslib::sapling::tree< Value, Allocator >::swap().
00684 { 00685 tree deadbeef( other ); 00686 deadbeef.swap( *this ); 00687 return *this; 00688 } |
関数の呼び出しグラフ:
|
参照先 gslib::sapling::tree< Value, Allocator >::root_ptr(), gslib::sapling::tree< Value, Allocator >::node::value(), と gslib::sapling::tree< Value, Allocator >::value_type.
00630 { 00631 return root_ptr() ? root_ptr()->value() : *( ( value_type* ) 0 ); 00632 } |
関数の呼び出しグラフ:
|
関数の呼び出しグラフ:
|
ルートが存在しない場合はルートを作成する。 すでにルートが存在する場合は v で上書きする。
参照先 gslib::sapling::tree< Value, Allocator >::empty(), gslib::sapling::tree< Value, Allocator >::end(), gslib::sapling::tree< Value, Allocator >::insert(), と gslib::sapling::tree< Value, Allocator >::root(). 参照元 gslib::sapling::tree< Value, Allocator >::tree().
|
関数の呼び出しグラフ:
|
参照先 gslib::sapling::tree< Value, Allocator >::end_, gslib::sapling::tree< Value, Allocator >::link::next, と gslib::sapling::tree< Value, Allocator >::link::self.
|
|
|
参照先 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, と gslib::sapling::tree< Value, Allocator >::link::prev. 参照元 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 } |
関数の呼び出しグラフ:
|
tree が一度にアロケーションする大きさ ( メモリプールなどに利用する )
|
|
|
|
|
|