stlab.adobe.com Adobe Systems Incorporated

#include <adobe/forest.hpp>

Public Types

typedef adobe::child_iterator< iteratorchild_iterator
 
typedef adobe::child_iterator< const_iteratorconst_child_iterator
 
typedef implementation::forest_const_iterator< T > const_iterator
 
typedef const T * const_pointer
 
typedef edge_iterator< const_iterator, forest_trailing_edgeconst_postorder_iterator
 
typedef edge_iterator< const_iterator, forest_leading_edgeconst_preorder_iterator
 
typedef const T & const_reference
 
typedef reverse_fullorder_iterator< const_iteratorconst_reverse_iterator
 
typedef std::ptrdiff_t difference_type
 
typedef implementation::forest_iterator< T > iterator
 
typedef T * pointer
 
typedef edge_iterator< iterator, forest_trailing_edgepostorder_iterator
 
typedef edge_iterator< iterator, forest_leading_edgepreorder_iterator
 
typedef T & reference
 
typedef std::reverse_iterator< child_iteratorreverse_child_iterator
 
typedef reverse_fullorder_iterator< iteratorreverse_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)
 
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)
 

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 333 of file forest.hpp.

Member Typedef Documentation

§ child_iterator

Definition at line 562 of file forest.hpp.

§ const_child_iterator

§ const_iterator

typedef implementation::forest_const_iterator<T> const_iterator

Definition at line 553 of file forest.hpp.

§ const_pointer

typedef const T* const_pointer

Definition at line 558 of file forest.hpp.

§ const_postorder_iterator

§ const_preorder_iterator

§ const_reference

typedef const T& const_reference

Definition at line 551 of file forest.hpp.

§ const_reverse_iterator

§ difference_type

typedef std::ptrdiff_t difference_type

Definition at line 555 of file forest.hpp.

§ iterator

typedef implementation::forest_iterator<T> iterator

Definition at line 552 of file forest.hpp.

§ pointer

typedef T* pointer

Definition at line 557 of file forest.hpp.

§ postorder_iterator

§ preorder_iterator

§ reference

typedef T& reference

Definition at line 550 of file forest.hpp.

§ reverse_child_iterator

typedef std::reverse_iterator<child_iterator> reverse_child_iterator

Definition at line 568 of file forest.hpp.

§ reverse_iterator

Definition at line 559 of file forest.hpp.

§ size_type

typedef std::size_t size_type

Definition at line 554 of file forest.hpp.

§ value_type

typedef T value_type

Definition at line 556 of file forest.hpp.

Member Function Documentation

§ back() [1/2]

Returns
The last node in the forest.

Definition at line 606 of file forest.hpp.

§ back() [2/2]

Returns
The last node in the forest.

Definition at line 607 of file forest.hpp.

§ begin() [1/2]

Returns
An iterator to the first node in the forest.

Definition at line 594 of file forest.hpp.

§ begin() [2/2]

Returns
An iterator to the first node in the forest.

Definition at line 596 of file forest.hpp.

§ clear()

void clear ( )

Definition at line 610 of file forest.hpp.

§ empty()

bool empty ( ) const

Definition at line 589 of file forest.hpp.

§ end() [1/2]

Returns
An iterator to one-past-the last node in the forest.

Definition at line 595 of file forest.hpp.

§ end() [2/2]

Returns
An iterator to one-past-the last node in the forest.

Definition at line 597 of file forest.hpp.

§ erase() [1/2]

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.

§ erase() [2/2]

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.

§ front() [1/2]

Returns
The first node in the forest.

Definition at line 604 of file forest.hpp.

§ front() [2/2]

Returns
The first node in the forest.

Definition at line 605 of file forest.hpp.

§ insert() [1/2]

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.

§ insert() [2/2]

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.

§ insert_parent()

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.

§ max_size()

size_type max_size ( ) const

Definition at line 587 of file forest.hpp.

§ pop_back()

void pop_back ( )

Definition at line 634 of file forest.hpp.

§ pop_front()

void pop_front ( )

Definition at line 633 of file forest.hpp.

§ push_back()

void push_back ( const T &  x)

Definition at line 632 of file forest.hpp.

§ push_front()

void push_front ( const T &  x)

Definition at line 631 of file forest.hpp.

§ rbegin() [1/2]

reverse_iterator rbegin ( )

Definition at line 599 of file forest.hpp.

§ rbegin() [2/2]

reverse_iterator rbegin ( ) const

Definition at line 601 of file forest.hpp.

§ rend() [1/2]

reverse_iterator rend ( )

Definition at line 600 of file forest.hpp.

§ rend() [2/2]

reverse_iterator rend ( ) const

Definition at line 602 of file forest.hpp.

§ reverse()

void reverse ( child_iterator  first,
child_iterator  last 
)

Definition at line 950 of file forest.hpp.

§ root()

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

Definition at line 592 of file forest.hpp.

§ size() [1/2]

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.

§ size() [2/2]

forest< T >::size_type size ( )

Definition at line 774 of file forest.hpp.

§ size_valid()

bool size_valid ( ) const

Definition at line 588 of file forest.hpp.

§ splice() [1/4]

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.

§ splice() [2/4]

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.

§ splice() [3/4]

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.

§ splice() [4/4]

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.

Friends And Related Function Documentation

§ child_adaptor< forest< T > >

friend class child_adaptor< forest< T > >
friend

Definition at line 547 of file forest.hpp.

§ child_begin()

child_iterator< BeadIterator > child_begin ( const BeadIterator &  iter)
related
Returns
the first child for the node being pointed at by the iterator

§ child_end()

child_iterator< BeadIterator > child_end ( const BeadIterator &  iter)
related
Returns
one-past-the-last child for the node being pointed at by the iterator

§ depth_range() [1/2]

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.

§ depth_range() [2/2]

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.

§ filter_fullorder_range() [1/2]

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.

§ filter_fullorder_range() [2/2]

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.

§ find_parent()

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.

§ has_children()

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

§ leading_of()

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.

§ pivot()

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.

§ pivot_of()

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.

§ postorder_range() [1/2]

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.

§ postorder_range() [2/2]

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.

§ preorder_range() [1/2]

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.

§ preorder_range() [2/2]

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.

§ reverse_fullorder_range() [1/2]

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.

§ reverse_fullorder_range() [2/2]

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.

§ trailing_of()

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