#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 が一度にアロケーションする大きさ ( メモリプールなどに利用する )
|
|
|||||
|
|
|
|||||
|
|||||
|
|
1.3.6