stlab.adobe.com Adobe Systems Incorporated

forest< T > Class Template Reference
[Forest]

A homogeneous hierarchical structure class. More...

#include <adobe/forest.hpp>

List of all members.

Public Types

typedef adobe::child_iterator
< iterator
child_iterator
typedef adobe::child_iterator
< const_iterator
const_child_iterator
typedef
implementation::forest_const_iterator
< T > 
const_iterator
typedef const T * const_pointer
typedef edge_iterator
< const_iterator,
forest_trailing_edge > 
const_postorder_iterator
typedef edge_iterator
< const_iterator,
forest_leading_edge > 
const_preorder_iterator
typedef const T & const_reference
typedef
reverse_fullorder_iterator
< const_iterator
const_reverse_iterator
typedef std::ptrdiff_t difference_type
typedef
implementation::forest_iterator
< T > 
iterator
typedef T * pointer
typedef edge_iterator
< iterator,
forest_trailing_edge > 
postorder_iterator
typedef edge_iterator
< iterator,
forest_leading_edge > 
preorder_iterator
typedef T & reference
typedef std::reverse_iterator
< child_iterator
reverse_child_iterator
typedef
reverse_fullorder_iterator
< iterator
reverse_iterator
typedef std::size_t size_type
typedef T value_type

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)
const_reference front () const
reference front ()
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 () const
reverse_iterator rbegin ()
reverse_iterator rend ()
reverse_iterator rend () const
void reverse (child_iterator first, child_iterator last)
iterator root ()
size_type size ()
size_type size () const
bool size_valid () const
iterator splice (iterator position, forest< T > &x, child_iterator first, child_iterator last)
iterator splice (iterator position, forest< T > &x, iterator i)
iterator splice (iterator position, forest< T > &x, child_iterator first, child_iterator last, size_type count)
iterator splice (iterator position, forest< T > &x)

Friends

class child_adaptor< forest< T > >

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)
leading_of (C cursor)
void pivot (I &iter)
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)
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

Definition at line 562 of file forest.hpp.

typedef implementation::forest_const_iterator<T> const_iterator

Definition at line 553 of file forest.hpp.

typedef const T* const_pointer

Definition at line 558 of file forest.hpp.

typedef edge_iterator<const_iterator, forest_trailing_edge> const_postorder_iterator

Definition at line 573 of file forest.hpp.

typedef edge_iterator<const_iterator, forest_leading_edge> const_preorder_iterator

Definition at line 571 of file forest.hpp.

typedef const T& const_reference

Definition at line 551 of file forest.hpp.

typedef std::ptrdiff_t difference_type

Definition at line 555 of file forest.hpp.

typedef implementation::forest_iterator<T> iterator

Definition at line 552 of file forest.hpp.

typedef T* pointer

Definition at line 557 of file forest.hpp.

typedef edge_iterator<iterator, forest_trailing_edge> postorder_iterator

Definition at line 572 of file forest.hpp.

typedef edge_iterator<iterator, forest_leading_edge> preorder_iterator

Definition at line 570 of file forest.hpp.

typedef T& reference

Definition at line 550 of file forest.hpp.

typedef std::reverse_iterator<child_iterator> reverse_child_iterator

Definition at line 568 of file forest.hpp.

Definition at line 559 of file forest.hpp.

typedef std::size_t size_type

Definition at line 554 of file forest.hpp.

typedef T value_type

Definition at line 556 of file forest.hpp.


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.

adobe::forest::const_iterator begin (  ) const
Returns:
An iterator to the first node in the forest.

Definition at line 596 of file forest.hpp.

void clear (  )

Definition at line 610 of file forest.hpp.

bool empty (  ) const

Definition at line 589 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.

forest< T >::iterator erase ( const iterator position )
Parameters:
positionan 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.

forest< T >::iterator erase ( const iterator first,
const iterator last 
)

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:
firstan iterator to the first node to be erased.
lastan 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.

adobe::forest::const_reference front (  ) const
Returns:
The first node in the forest.

Definition at line 605 of file forest.hpp.

Returns:
The first node in the forest.

Definition at line 604 of file forest.hpp.

adobe::forest::iterator insert ( const iterator position,
const T &  x 
)
Parameters:
positionan iterator to the position of insertion.
xa 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.

forest< T >::iterator insert ( iterator  position,
const_child_iterator  first,
const_child_iterator  last 
)

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.

forest< T >::iterator insert_parent ( child_iterator  first,
child_iterator  last,
const T &  x 
)
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.

size_type max_size (  ) const

Definition at line 587 of file forest.hpp.

void pop_back (  )

Definition at line 634 of file forest.hpp.

void pop_front (  )

Definition at line 633 of file forest.hpp.

void push_back ( const T &  x )

Definition at line 632 of file forest.hpp.

void push_front ( const T &  x )

Definition at line 631 of file forest.hpp.

reverse_iterator rbegin (  ) const

Definition at line 601 of file forest.hpp.

reverse_iterator rbegin (  )

Definition at line 599 of file forest.hpp.

reverse_iterator rend (  )

Definition at line 600 of file forest.hpp.

reverse_iterator rend (  ) const

Definition at line 602 of file forest.hpp.

void reverse ( child_iterator  first,
child_iterator  last 
)

Definition at line 950 of file forest.hpp.

Returns:
An iterator to the root of the forest. Cannot be dereferenced.

Definition at line 592 of file forest.hpp.

forest< T >::size_type size (  )

Definition at line 774 of file forest.hpp.

forest< T >::size_type size (  ) const
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

Definition at line 588 of file forest.hpp.

forest< T >::iterator splice ( iterator  position,
forest< T > &  x,
child_iterator  first,
child_iterator  last 
)

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.

forest< T >::iterator splice ( iterator  position,
forest< T > &  x,
iterator  i 
)

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.

forest< T >::iterator splice ( iterator  position,
forest< T > &  x,
child_iterator  first,
child_iterator  last,
size_type  count 
)

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.

forest< T >::iterator splice ( iterator  position,
forest< T > &  x 
)

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.


Friends And Related Function Documentation

friend class child_adaptor< forest< T > > [friend]

Definition at line 547 of file forest.hpp.

child_iterator< BeadIterator > child_begin ( const BeadIterator &  iter ) [related]
Returns:
the first child for the node being pointed at by the iterator
child_iterator< BeadIterator > child_end ( const BeadIterator &  iter ) [related]
Returns:
one-past-the-last child for the node being pointed at by the iterator
std::pair< depth_fullorder_iterator< typename boost::range_iterator< R >::type >, depth_fullorder_iterator< typename boost::range_iterator< R >::type > > depth_range ( R &  x ) [related]
Parameters:
xthe FullorderRange which will be made into a depth FullorderRange
Returns:
A depth FullorderRange

Definition at line 1117 of file forest.hpp.

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 ) [related]
Parameters:
xthe const FullorderRange which will be made into a const depth FullorderRange
Returns:
A const depth FullorderRange

Definition at line 1136 of file forest.hpp.

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 
) [related]
Parameters:
xthe FullorderRange to which the filter will be applied
pthe predicate to be applied to the FullorderIterator
Returns:
A filtered FullorderRange

Definition at line 1024 of file forest.hpp.

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 
) [related]
Parameters:
xthe const FullorderRange to which the filter will be applied
pthe 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:
traveleran 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:
cursorThe 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
C leading_of ( cursor ) [related]
Parameters:
cursorthe 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.
void pivot ( I &  iter ) [related]
Parameters:
iterthe 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.

I pivot_of ( iter ) [related]

Pivots the iterator from the leading to the trailing edge, or vice versa.

Parameters:
iterthe 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.

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 ) [related]
Parameters:
xthe FullorderRange which will be made into a postorder range
Returns:
A postorder range

Definition at line 1157 of file forest.hpp.

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 ) [related]
Parameters:
xthe const FullorderRange which will be made into a const postorder range
Returns:
A const postorder range

Definition at line 1176 of file forest.hpp.

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 ) [related]
Parameters:
xthe FullorderRange which will be made into a preorder range
Returns:
A preorder range

Definition at line 1197 of file forest.hpp.

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 ) [related]
Parameters:
xthe const FullorderRange which will be made into a const preorder range
Returns:
A const preorder range

Definition at line 1216 of file forest.hpp.

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 ) [related]
Parameters:
xthe const FullorderRange which will be reversed
Returns:
A const reverse FullorderRange

Definition at line 1095 of file forest.hpp.

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 ) [related]
Parameters:
xthe FullorderRange which will be reversed
Returns:
A reverse FullorderRange

Definition at line 1076 of file forest.hpp.

C trailing_of ( cursor ) [related]
Parameters:
cursorthe 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.

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google