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)
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:

• Regular
• ReversibleContainer
• FrontInsertionSequence
• BackInsertionSequence

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 adobe::child_iterator<iterator> child_iterator

Definition at line 562 of file forest.hpp.

typedef adobe::child_iterator<const_iterator> const_child_iterator

Definition at line 567 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 reverse_fullorder_iterator<const_iterator> const_reverse_iterator

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

typedef reverse_fullorder_iterator<iterator> reverse_iterator

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

adobe::forest::reference back

(

)

Returns:

The last node in the forest.

Definition at line 606 of file forest.hpp.

adobe::forest::const_reference back

(

)

const

Returns:

The last node in the forest.

Definition at line 607 of file forest.hpp.

adobe::forest::iterator begin

(

)

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.

adobe::forest::iterator end

(

)

Returns:

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

Definition at line 595 of file forest.hpp.

adobe::forest::const_iterator end

(

)

const

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:

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.

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:

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.

adobe::forest::const_reference front

(

)

const

Returns:

The first node in the forest.

Definition at line 605 of file forest.hpp.

adobe::forest::reference front

(

)

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:

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.

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.

adobe::forest::iterator root

(

)

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:

x	the 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:

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.

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
	)		[related]

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.

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
	)		[related]

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

C leading_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 leading edge of the node to which it points.

void pivot

(

I &

iter )

[related]

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.

I pivot_of

(

I

iter )

[related]

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.

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:

x	the 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:

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.

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:

x	the 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:

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.

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:

x	the 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:

x	the FullorderRange which will be reversed

Returns:

A reverse FullorderRange

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