|
#include <adobe/forest.hpp>
List of all members.
Public Member Functions |
reference | back () |
const_reference | back () const |
iterator | begin () |
const_iterator | begin () const |
void | clear () |
bool | empty () const |
iterator | end () |
const_iterator | end () const |
iterator | erase (const iterator &position) |
iterator | erase (const iterator &first, const iterator &last) |
reference | front () |
const_reference | front () const |
iterator | insert (const iterator &position, const T &x) |
iterator | insert (iterator position, const_child_iterator first, const_child_iterator last) |
iterator | insert_parent (child_iterator front, child_iterator back, const T &x) |
size_type | max_size () const |
void | pop_back () |
void | pop_front () |
void | push_back (const T &x) |
void | push_front (const T &x) |
reverse_iterator | rbegin () |
reverse_iterator | rbegin () const |
reverse_iterator | rend () |
reverse_iterator | rend () const |
void | reverse (child_iterator first, child_iterator last) |
iterator | root () |
size_type | size () const |
size_type | size () |
bool | size_valid () const |
iterator | splice (iterator position, forest< T > &x) |
iterator | splice (iterator position, forest< T > &x, iterator i) |
iterator | splice (iterator position, forest< T > &x, child_iterator first, child_iterator last) |
iterator | splice (iterator position, forest< T > &x, child_iterator first, child_iterator last, size_type count) |
Related Functions |
(Note that these are not member functions.)
|
child_iterator< BeadIterator > | child_begin (const BeadIterator &iter) |
child_iterator< BeadIterator > | child_end (const BeadIterator &iter) |
template<typename R > |
std::pair
< depth_fullorder_iterator
< typename
boost::range_iterator< R >
::type >
, depth_fullorder_iterator
< typename
boost::range_iterator< R >
::type > > | depth_range (R &x) |
template<typename R > |
std::pair
< depth_fullorder_iterator
< typename
boost::range_const_iterator< R >
::type >
, depth_fullorder_iterator
< typename
boost::range_const_iterator< R >
::type > > | depth_range (const R &x) |
template<typename R , typename P > |
std::pair
< filter_fullorder_iterator
< typename
boost::range_iterator< R >
::type, P >
, filter_fullorder_iterator
< typename
boost::range_iterator< R >
::type, P > > | filter_fullorder_range (R &x, P p) |
template<typename R , typename P > |
std::pair
< filter_fullorder_iterator
< typename
boost::range_const_iterator< R >
::type, P >
, filter_fullorder_iterator
< typename
boost::range_const_iterator< R >
::type, P > > | filter_fullorder_range (const R &x, P p) |
ForestTraveler | find_parent (ForestTraveler traveler) |
bool | has_children (const C &cursor) |
C | leading_of (C cursor) |
void | pivot (I &iter) |
I | pivot_of (I iter) |
template<typename R > |
std::pair< edge_iterator
< typename
boost::range_iterator< R >
::type, forest_trailing_edge >
, edge_iterator< typename
boost::range_iterator< R >
::type, forest_trailing_edge > > | postorder_range (R &x) |
template<typename R > |
std::pair< edge_iterator
< typename
boost::range_const_iterator< R >
::type, forest_trailing_edge >
, edge_iterator< typename
boost::range_const_iterator< R >
::type, forest_trailing_edge > > | postorder_range (const R &x) |
template<typename R > |
std::pair< edge_iterator
< typename
boost::range_iterator< R >
::type, forest_leading_edge >
, edge_iterator< typename
boost::range_iterator< R >
::type, forest_leading_edge > > | preorder_range (R &x) |
template<typename R > |
std::pair< edge_iterator
< typename
boost::range_const_iterator< R >
::type, forest_leading_edge >
, edge_iterator< typename
boost::range_const_iterator< R >
::type, forest_leading_edge > > | preorder_range (const R &x) |
template<typename R > |
std::pair
< reverse_fullorder_iterator
< typename
boost::range_iterator< R >
::type >
, reverse_fullorder_iterator
< typename
boost::range_iterator< R >
::type > > | reverse_fullorder_range (R &x) |
template<typename R > |
std::pair
< reverse_fullorder_iterator
< typename
boost::range_const_iterator< R >
::type >
, reverse_fullorder_iterator
< typename
boost::range_const_iterator< R >
::type > > | reverse_fullorder_range (const R &x) |
C | trailing_of (C cursor) |
Detailed Description
template<typename T>
class adobe::forest< T >
- A
forest is a linked structure, similiar to a list forming a number of hierarchies or trees. A forest can be traversed as a sequence, depth first, either pre-order or post-order, both forward and backward. Elements can be inserted and erased from any location in constant time. Inserting and splicing do not invalidate iterators to forest elements; erasing invalidates only the iterators that point to the elements that are erased.
- For information on adobe::forest utility classes see Forest.
- For additional information on the edge semantics of forest iterators, please see http://stlab.adobe.com/wiki/index.php/Edge_Interface_For_Forest_Iterators
- Model Of:
-
- Type Requirements:
- Only those imposed by the requirements of ReversibleContainer, FrontInsertionSequence, and BackInsertionSequence.
- Definitions:
- cursor : A cursor is similar to an iterator, except
*(cursor) == *(cursor + 1) may be true. (e.g, in the case when the cursor pivots but does not move off the current forest node to which it points.)
- Tutorial:
- A tutorial for forest is available.
Definition at line 543 of file forest.hpp.
Member Typedef Documentation
typedef implementation::forest_iterator<T> iterator |
Member Function Documentation
- Returns:
- The last node in the forest.
Definition at line 606 of file forest.hpp.
- Returns:
- The last node in the forest.
Definition at line 607 of file forest.hpp.
- Returns:
- An iterator to the first node in the forest.
Definition at line 594 of file forest.hpp.
- Returns:
- An iterator to the first node in the forest.
Definition at line 596 of file forest.hpp.
- Returns:
- An iterator to one-past-the last node in the forest.
Definition at line 595 of file forest.hpp.
- Returns:
- An iterator to one-past-the last node in the forest.
Definition at line 597 of file forest.hpp.
- Parameters:
-
position | an iterator to the node to be erased. |
- Returns:
- An iterator to the node succeeding the node erased.
Definition at line 834 of file forest.hpp.
This only erases nodes if the deletion iterator passes through the node twice. See the description below on deleting a node for a more illustrative example of range-based node deletion.
- Parameters:
-
first | an iterator to the first node to be erased. |
last | an iterator to one-past-the last node to be erased. |
- Returns:
- An iterator to the node succeeding the last node erased.
Definition at line 803 of file forest.hpp.
- Returns:
- The first node in the forest.
Definition at line 604 of file forest.hpp.
- Returns:
- The first node in the forest.
Definition at line 605 of file forest.hpp.
- Parameters:
-
position | an iterator to the position of insertion. |
x | a value to be copy-constructed into position. |
- Returns:
- An iterator to the new node in its new location.
Definition at line 619 of file forest.hpp.
Inserts the sub-forest [first.base(), last.base()) at position .
- Complexity Guarantees:
- Linear.
- Returns:
- An iterator to the first new node.
Definition at line 885 of file forest.hpp.
- Precondition:
last must be arriveable at from first .
- Returns:
- An iterator to the leading edge of the inserted node.
Definition at line 938 of file forest.hpp.
void push_back |
( |
const T & |
x | ) |
|
void push_front |
( |
const T & |
x | ) |
|
- Returns:
- An iterator to the root of the forest. Cannot be dereferenced.
Definition at line 592 of file forest.hpp.
- Returns:
- The number of nodes in the forest.
- Complexity Guarantees:
- O(1) if size is valid. O(N) if size is not valid. Some instances of splice() result in a forest where the size of the forest is not known by the end of the call. In other cases the size of the forest is cached, thus optimizing the complexity of the size() operation.
- See Also:
- adobe::forest::splice
Definition at line 790 of file forest.hpp.
bool size_valid |
( |
| ) |
const |
All of the elements of x are inserted before position and removed from x .
- Precondition:
position must be a valid iterator in *this
-
x must be a forest that is distinct from *this .
- Returns:
- An iterator to the spliced range. Either an iterator to the first element of
x or position if x is empty.
Definition at line 867 of file forest.hpp.
splice moves the element(s) pointed to by i from x to *this , inserting it before position . The range denoted by i is [leading_of(i), next(trailing_of(i)) ) , any children of i are also moved. If position == leading_of(i) then no splice occurs.
- Precondition:
position may not be within the range denoted by i .
- Postcondition:
- If
&x != *this and i has children then size() and x.size() will be invalidated.
- Returns:
- An iterator to the spliced range (
leading_of(i) ).
Definition at line 876 of file forest.hpp.
splice moves the elements in [first, last) from x to *this , inserting them before position . If position == first.base() then no splice occurs.
- Precondition:
position my not be within the range [first, last) .
- Postcondition:
- If
&x != *this and [first, last) is not empty then size() and x.size() will be invalidated.
- Returns:
- An iterator to the spliced range. Either an iterator to
first or position if [first, last) is empty.
Definition at line 931 of file forest.hpp.
splice moves the elements in [first, last) from x to *this , inserting them before position . If position == first.base() then no splice occurs. The count parameter optionally specifies the distance [first, last) and avoids invalidating the size of the forests.
- Precondition:
position my not be within the range [first, last) .
-
count is the distance from [first, last) or 0.
- Postcondition:
- If c is 0 and
&x != *this and [first, last) is not empty then size() and x.size() will be invalidated.
- Returns:
- An iterator to the spliced range. Either an iterator to
first or position if [first, last) is empty.
Definition at line 899 of file forest.hpp.
Friends And Related Function Documentation
child_iterator< BeadIterator > child_begin |
( |
const BeadIterator & |
iter | ) |
|
|
related |
- Returns:
- the first child for the node being pointed at by the iterator
- Returns:
- one-past-the-last child for the node being pointed at by the iterator
- Parameters:
-
x | the FullorderRange which will be made into a depth FullorderRange |
- Returns:
- A depth FullorderRange
Definition at line 1117 of file forest.hpp.
- Parameters:
-
x | the const FullorderRange which will be made into a const depth FullorderRange |
- Returns:
- A const depth FullorderRange
Definition at line 1136 of file forest.hpp.
- Parameters:
-
x | the FullorderRange to which the filter will be applied |
p | the predicate to be applied to the FullorderIterator |
- Returns:
- A filtered FullorderRange
Definition at line 1024 of file forest.hpp.
- Parameters:
-
x | the const FullorderRange to which the filter will be applied |
p | the predicate to be applied to value_type(R) |
- Returns:
- A filtered FullorderRange
Definition at line 1044 of file forest.hpp.
ForestTraveler find_parent |
( |
ForestTraveler |
traveler | ) |
|
|
related |
- Parameters:
-
traveler | an iterator over a given forest. |
- Returns:
- The parent of
traveler or forest end .
- Complexity Guarantees:
- Linear. Will traverse the siblings of traveler from
[traveler, last_sibling) .
- Precondition:
traveler is dereferenceable (not forest end ).
- Todo:
- (sparent) Open question if precondition should be checked and and function return
traveler . This would rely on a "check root" for travelers.
bool has_children |
( |
const C & |
cursor | ) |
|
|
related |
- Parameters:
-
cursor | The cursor that whose node will be examined for children |
- Complexity Guarantees:
- O(1)
- Returns:
- Whether or not the node pointed to by the cursor has any children
- Parameters:
-
cursor | the cursor whose edge will be examined |
- Returns:
- A cursor identical to the one passed in, save that it will be on the leading edge of the node to which it points.
- Parameters:
-
iter | the iterator whose edge will be flipped |
Pivots the iterator from the leading to the trailing edge, or vice versa. The iterator itself is mutated to reflect the change.
Definition at line 48 of file forest.hpp.
Pivots the iterator from the leading to the trailing edge, or vice versa.
- Parameters:
-
iter | the iterator whose edge will be flipped |
- Returns:
- An iterator identical to the one passed in, save that the edge has been flipped
Definition at line 51 of file forest.hpp.
- Parameters:
-
x | the FullorderRange which will be made into a postorder range |
- Returns:
- A postorder range
Definition at line 1157 of file forest.hpp.
- Parameters:
-
x | the const FullorderRange which will be made into a const postorder range |
- Returns:
- A const postorder range
Definition at line 1176 of file forest.hpp.
- Parameters:
-
x | the FullorderRange which will be made into a preorder range |
- Returns:
- A preorder range
Definition at line 1197 of file forest.hpp.
- Parameters:
-
x | the const FullorderRange which will be made into a const preorder range |
- Returns:
- A const preorder range
Definition at line 1216 of file forest.hpp.
- Parameters:
-
x | the FullorderRange which will be reversed |
- Returns:
- A reverse FullorderRange
Definition at line 1076 of file forest.hpp.
- Parameters:
-
x | the const FullorderRange which will be reversed |
- Returns:
- A const reverse FullorderRange
Definition at line 1095 of file forest.hpp.
C trailing_of |
( |
C |
cursor | ) |
|
|
related |
- Parameters:
-
cursor | the cursor whose edge will be examined |
- Returns:
- A cursor identical to the one passed in, save that it will be on the trailing edge of the node to which it points.
|