tree< T, tree_node_allocator > Class Template Reference

#include <tree.h>

Inheritance diagram for tree< T, tree_node_allocator >:

[legend]

Collaboration diagram for tree< T, tree_node_allocator >:

[legend]

---

Detailed Description

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
class tree< T, tree_node_allocator >

Definition at line 107 of file tree.h.

Public Types
typedef T	value_type
	Value of the data stored at a node.
typedef pre_order_iterator	iterator
	The default iterator types throughout the tree class.
typedef breadth_first_queued_iterator	breadth_first_iterator
Public Member Functions
	tree ()
	tree (const T &)
	tree (const iterator_base &)
	tree (const tree< T, tree_node_allocator > &)
	~tree ()
void	operator= (const tree< T, tree_node_allocator > &)
pre_order_iterator	begin () const
	Return iterator to the beginning of the tree.
pre_order_iterator	end () const
	Return iterator to the end of the tree.
post_order_iterator	begin_post () const
	Return post-order iterator to the beginning of the tree.
post_order_iterator	end_post () const
	Return post-order iterator to the end of the tree.
fixed_depth_iterator	begin_fixed (const iterator_base &, unsigned int) const
	Return fixed-depth iterator to the first node at a given depth.
fixed_depth_iterator	end_fixed (const iterator_base &, unsigned int) const
	Return fixed-depth iterator to end of the nodes at given depth.
breadth_first_queued_iterator	begin_breadth_first () const
	Return breadth-first iterator to the first node at a given depth.
breadth_first_queued_iterator	end_breadth_first () const
	Return breadth-first iterator to end of the nodes at given depth.
sibling_iterator	begin (const iterator_base &) const
	Return sibling iterator to the first child of given node.
sibling_iterator	end (const iterator_base &) const
	Return sibling iterator to the end of the children of a given node.
leaf_iterator	begin_leaf () const
	Return leaf iterator to the first leaf of the tree.
leaf_iterator	end_leaf () const
	Return leaf iterator to the last leaf of the tree.
template<typename iter>
iter	previous_sibling (iter) const
	Return iterator to the previous sibling of a node.
template<typename iter>
iter	next_sibling (iter) const
	Return iterator to the next sibling of a node.
template<typename iter>
iter	next_at_same_depth (iter) const
	Return iterator to the next node at a given depth.
void	clear ()
	Erase all nodes of the tree.
template<typename iter>
iter	erase (iter)
	Erase element at position pointed to by iterator, return incremented iterator.
void	erase_children (const iterator_base &)
	Erase all children of the node pointed to by iterator.
template<typename iter>
iter	append_child (iter position)
	Insert empty node as last/first child of node pointed to by position.
template<typename iter>
iter	prepend_child (iter position)
template<typename iter>
iter	append_child (iter position, const T &x)
	Insert node as last/first child of node pointed to by position.
template<typename iter>
iter	prepend_child (iter position, const T &x)
template<typename iter>
iter	append_child (iter position, iter other_position)
	Append the node (plus its children) at other_position as last/first child of position.
template<typename iter>
iter	prepend_child (iter position, iter other_position)
template<typename iter>
iter	append_children (iter position, sibling_iterator from, sibling_iterator to)
	Append the nodes in the from-to range (plus their children) as last/first children of position.
template<typename iter>
iter	prepend_children (iter position, sibling_iterator from, sibling_iterator to)
pre_order_iterator	set_head (const T &x)
	Short-hand to insert topmost node in otherwise empty tree.
template<typename iter>
iter	insert (iter position, const T &x)
	Insert node as previous sibling of node pointed to by position.
sibling_iterator	insert (sibling_iterator position, const T &x)
	Specialisation of previous member.
template<typename iter>
iter	insert_subtree (iter position, const iterator_base &subtree)
	Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.
template<typename iter>
iter	insert_after (iter position, const T &x)
	Insert node as next sibling of node pointed to by position.
template<typename iter>
iter	insert_subtree_after (iter position, const iterator_base &subtree)
	Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.
template<typename iter>
iter	replace (iter position, const T &x)
	Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
template<typename iter>
iter	replace (iter position, const iterator_base &from)
	Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
sibling_iterator	replace (sibling_iterator orig_begin, sibling_iterator orig_end, sibling_iterator new_begin, sibling_iterator new_end)
	Replace string of siblings (plus their children) with copy of a new string (with children); see above.
template<typename iter>
iter	flatten (iter position)
	Move all children of node at 'position' to be siblings, returns position.
template<typename iter>
iter	reparent (iter position, sibling_iterator begin, sibling_iterator end)
	Move nodes in range to be children of 'position'.
template<typename iter>
iter	reparent (iter position, iter from)
	Move all child nodes of 'from' to be children of 'position'.
template<typename iter>
iter	wrap (iter position, const T &x)
	Replace node with a new node, making the old node a child of the new node.
template<typename iter>
iter	move_after (iter target, iter source)
	Move 'source' node (plus its children) to become the next sibling of 'target'.
template<typename iter>
iter	move_before (iter target, iter source)
	Move 'source' node (plus its children) to become the previous sibling of 'target'.
sibling_iterator	move_before (sibling_iterator target, sibling_iterator source)
template<typename iter>
iter	move_ontop (iter target, iter source)
	Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
void	merge (sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, bool duplicate_leaves=false)
	Merge with other tree, creating new branches and leaves only if they are not already present.
void	sort (sibling_iterator from, sibling_iterator to, bool deep=false)
	Sort (std::sort only moves values of nodes, this one moves children as well).
template<class StrictWeakOrdering>
void	sort (sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)
template<typename iter>
bool	equal (const iter &one, const iter &two, const iter &three) const
	Compare two ranges of nodes (compares nodes as well as tree structure).
template<typename iter, class BinaryPredicate>
bool	equal (const iter &one, const iter &two, const iter &three, BinaryPredicate) const
template<typename iter>
bool	equal_subtree (const iter &one, const iter &two) const
template<typename iter, class BinaryPredicate>
bool	equal_subtree (const iter &one, const iter &two, BinaryPredicate) const
tree	subtree (sibling_iterator from, sibling_iterator to) const
	Extract a new tree formed by the range of siblings plus all their children.
void	subtree (tree &, sibling_iterator from, sibling_iterator to) const
void	swap (sibling_iterator it)
	Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
void	swap (iterator, iterator)
	Exchange two nodes (plus subtrees).
int	size () const
	Count the total number of nodes.
int	size (const iterator_base &) const
	Count the total number of nodes below the indicated node (plus one).
bool	empty () const
	Check if tree is empty.
int	depth (const iterator_base &) const
	Compute the depth to the root.
unsigned int	number_of_siblings (const iterator_base &) const
	Count the number of 'next' siblings of node at iterator.
bool	is_in_subtree (const iterator_base &position, const iterator_base &begin, const iterator_base &end) const
	Determine whether node at position is in the subtrees with root in the range.
bool	is_valid (const iterator_base &) const
	Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.
unsigned int	index (sibling_iterator it) const
	Determine the index of a node in the range of siblings to which it belongs.
sibling_iterator	child (const iterator_base &position, unsigned int) const
	Inverse of 'index': return the n-th child of the node at position.
Static Public Member Functions
template<typename iter>
static iter	parent (iter)
	Return iterator to the parent of a node.
static unsigned int	number_of_children (const iterator_base &)
	Count the number of children of node at position.
Data Fields
tree_node *	head
tree_node *	feet
Protected Types
typedef tree_node_< T >	tree_node
Private Member Functions
void	head_initialise_ ()
void	copy_ (const tree< T, tree_node_allocator > &other)
Private Attributes
tree_node_allocator	alloc_
Data Structures
class	breadth_first_queued_iterator
	Breadth-first iterator, using a queue. More...
class	compare_nodes
	Comparator class for two nodes of a tree (used for sorting and searching). More...
class	fixed_depth_iterator
	Iterator which traverses only the nodes at a given depth from the root. More...
class	iterator_base
	Base class for iterators, only pointers stored, no traversal logic. More...
class	iterator_base_less
	Comparator class for iterators (compares pointer values; why doesn't this work automatically?). More...
class	leaf_iterator
	Iterator which traverses only the leaves. More...
class	post_order_iterator
	Depth-first iterator, first accessing the children, then the node itself. More...
class	pre_order_iterator
	Depth-first iterator, first accessing the node, then its children. More...
class	sibling_iterator
	Iterator which traverses only the nodes which are siblings of each other. More...

---

Member Typedef Documentation

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

typedef tree_node_<T> tree< T, tree_node_allocator >::tree_node [protected]

Definition at line 109 of file tree.h.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

typedef T tree< T, tree_node_allocator >::value_type

Value of the data stored at a node.

Definition at line 112 of file tree.h.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

typedef pre_order_iterator tree< T, tree_node_allocator >::iterator

The default iterator types throughout the tree class.

Definition at line 217 of file tree.h.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

typedef breadth_first_queued_iterator tree< T, tree_node_allocator >::breadth_first_iterator

Definition at line 218 of file tree.h.

---

Constructor & Destructor Documentation

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::tree

(

)

[inline]

Definition at line 500 of file tree.h.

References tree< T, tree_node_allocator >::head_initialise_().

   {
   head_initialise_();
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::tree

(

const T &

x

)

[inline]

Definition at line 506 of file tree.h.

References tree< T, tree_node_allocator >::head_initialise_(), and tree< T, tree_node_allocator >::set_head().

   {
   head_initialise_();
   set_head(x);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::tree

(

const iterator_base &

other

)

[inline]

Definition at line 513 of file tree.h.

References tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::head_initialise_(), tree< T, tree_node_allocator >::replace(), and tree< T, tree_node_allocator >::set_head().

   {
   head_initialise_();
   set_head((*other));
   replace(begin(), other);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::tree

(

const tree< T, tree_node_allocator > &

other

)

[inline]

Definition at line 554 of file tree.h.

References tree< T, tree_node_allocator >::copy_(), and tree< T, tree_node_allocator >::head_initialise_().

   {
   head_initialise_();
   copy_(other);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::~tree

(

)

[inline]

Definition at line 521 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, tree< T, tree_node_allocator >::clear(), tree< T, tree_node_allocator >::feet, and tree< T, tree_node_allocator >::head.

   {
   clear();
   alloc_.deallocate(head,1);
   alloc_.deallocate(feet,1);
   }

Here is the call graph for this function:

---

Member Function Documentation

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::operator=

(

const tree< T, tree_node_allocator > &

other

)

[inline]

Definition at line 548 of file tree.h.

References tree< T, tree_node_allocator >::copy_().

   {
   copy_(other);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::begin

(

)

const [inline]

Return iterator to the beginning of the tree.

Definition at line 639 of file tree.h.

References tree< T, tree_node_allocator >::head, and tree_node_< T >::next_sibling.

Referenced by addClassCpp(), addFunctionCpp(), applyModification(), classAssignement(), className(), clean_pattern(), tree< T, tree_node_allocator >::copy_(), copy_branch(), tree< T, tree_node_allocator >::empty(), tree< T, tree_node_allocator >::equal_subtree(), exportXML(), Ast::fillAstInformation(), Ast::functionBoxing(), Ast::functionMapping(), functionReturnValue(), getNodeIter(), getNodeValue(), Ast::getSubVariables(), insert_branch(), Ast::nbNestedVariables(), Ast2Php::operator()(), Ast2Cpp::operator()(), ControlFlow::operator()(), RenameVariable::operator()(), RenameFunction::operator()(), RenameClass::operator()(), NumberSunkDiffuseInputs::operator()(), NumberDiffuseInputs::operator()(), NumberInput::operator()(), NumberResources::operator()(), NumberSinks::operator()(), kptree::print_subtree_bracketed(), kptree::print_tree_bracketed(), tree< T, tree_node_allocator >::size(), Ast::skeleton(), tree< T, tree_node_allocator >::sort(), Ast::sourceBoxing(), tree< T, tree_node_allocator >::subtree(), Ast::trace(), tree< T, tree_node_allocator >::tree(), writeCPP(), writeSiblingsCPP(), and writeSiblingsXML().

   {
   return pre_order_iterator(head->next_sibling);
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::end

(

)

const [inline]

Return iterator to the end of the tree.

Definition at line 645 of file tree.h.

References tree< T, tree_node_allocator >::feet.

Referenced by addClassCpp(), addFunctionCpp(), applyModification(), tree< T, tree_node_allocator >::begin(), classAssignement(), className(), clean_pattern(), tree< T, tree_node_allocator >::copy_(), copy_branch(), tree< T, tree_node_allocator >::empty(), tree< T, tree_node_allocator >::equal_subtree(), exportXML(), Ast::fillAstInformation(), Ast::functionBoxing(), Ast::functionMapping(), functionReturnValue(), Ast::getLeftVariable(), getNodeIter(), getNodeValue(), Ast::getRightVariables(), Ast::getSimpleVariable(), Ast::getSubVariables(), insert_branch(), Ast::nbNestedVariables(), Ast2Php::operator()(), Ast2Cpp::operator()(), ControlFlow::operator()(), RenameVariable::operator()(), RenameFunction::operator()(), RenameClass::operator()(), NumberSunkDiffuseInputs::operator()(), NumberResources::operator()(), NumberSinks::operator()(), kptree::print_subtree_bracketed(), kptree::print_tree_bracketed(), tree< T, tree_node_allocator >::reparent(), tree< T, tree_node_allocator >::size(), Ast::skeleton(), tree< T, tree_node_allocator >::sort(), Ast::sourceBoxing(), tree< T, tree_node_allocator >::subtree(), subVarName(), writeCPP(), writeSiblingsCPP(), and writeSiblingsXML().

   {
   return pre_order_iterator(feet);
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::begin_post

(

)

const [inline]

Return post-order iterator to the beginning of the tree.

Definition at line 663 of file tree.h.

References tree< T, tree_node_allocator >::feet, tree_node_< T >::first_child, tree< T, tree_node_allocator >::head, and tree_node_< T >::next_sibling.

   {
   tree_node *tmp=head->next_sibling;
   if(tmp!=feet) {
      while(tmp->first_child)
         tmp=tmp->first_child;
      }
   return post_order_iterator(tmp);
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::end_post

(

)

const [inline]

Return post-order iterator to the end of the tree.

Definition at line 674 of file tree.h.

References tree< T, tree_node_allocator >::feet.

   {
   return post_order_iterator(feet);
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::fixed_depth_iterator tree< T, tree_node_allocator >::begin_fixed	(	const iterator_base &	pos,
		unsigned int	dp
	)			const [inline]

Return fixed-depth iterator to the first node at a given depth.

Definition at line 680 of file tree.h.

References tree_node_< T >::first_child, and tree_node_< T >::next_sibling.

   {
   tree_node *tmp=pos.node;
   unsigned int curdepth=0;
   while(curdepth<dp) { // go down one level
      while(tmp->first_child==0) {
         tmp=tmp->next_sibling;
         if(tmp==0)
            throw std::range_error("tree: begin_fixed out of range");
         }
      tmp=tmp->first_child;
      ++curdepth;
      }
   return tmp;
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::fixed_depth_iterator tree< T, tree_node_allocator >::end_fixed	(	const iterator_base &	pos,
		unsigned int	dp
	)			const [inline]

Return fixed-depth iterator to end of the nodes at given depth.

Definition at line 697 of file tree.h.

References tree_node_< T >::first_child, and tree_node_< T >::next_sibling.

   {
   assert(1==0); // FIXME: not correct yet
   tree_node *tmp=pos.node;
   unsigned int curdepth=1;
   while(curdepth<dp) { // go down one level
      while(tmp->first_child==0) {
         tmp=tmp->next_sibling;
         if(tmp==0)
            throw std::range_error("tree: end_fixed out of range");
         }
      tmp=tmp->first_child;
      ++curdepth;
      }
   return tmp;
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::begin_breadth_first

(

)

const [inline]

Return breadth-first iterator to the first node at a given depth.

Definition at line 651 of file tree.h.

References tree< T, tree_node_allocator >::head, and tree_node_< T >::next_sibling.

   {
   return breadth_first_queued_iterator(head->next_sibling);
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::end_breadth_first

(

)

const [inline]

Return breadth-first iterator to end of the nodes at given depth.

Definition at line 657 of file tree.h.

   {
   return breadth_first_queued_iterator();
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::begin

(

const iterator_base &

pos

)

const [inline]

Return sibling iterator to the first child of given node.

Definition at line 715 of file tree.h.

References tree< T, tree_node_allocator >::end().

   {
   assert(pos.node!=0);
   if(pos.node->first_child==0) {
      return end(pos);
      }
   return pos.node->first_child;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::end

(

const iterator_base &

pos

)

const [inline]

Return sibling iterator to the end of the children of a given node.

Definition at line 725 of file tree.h.

References tree< T, tree_node_allocator >::sibling_iterator::parent_.

   {
   sibling_iterator ret(0);
   ret.parent_=pos.node;
   return ret;
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::begin_leaf

(

)

const [inline]

Return leaf iterator to the first leaf of the tree.

Definition at line 733 of file tree.h.

References tree< T, tree_node_allocator >::feet, tree_node_< T >::first_child, tree< T, tree_node_allocator >::head, and tree_node_< T >::next_sibling.

Referenced by NumberSunkDiffuseInputs::operator()(), NumberDiffuseInputs::operator()(), and NumberInput::operator()().

   {
   tree_node *tmp=head->next_sibling;
   if(tmp!=feet) {
      while(tmp->first_child)
         tmp=tmp->first_child;
      }
   return leaf_iterator(tmp);
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::end_leaf

(

)

const [inline]

Return leaf iterator to the last leaf of the tree.

Definition at line 744 of file tree.h.

References tree< T, tree_node_allocator >::feet.

Referenced by NumberSunkDiffuseInputs::operator()(), NumberDiffuseInputs::operator()(), and NumberInput::operator()().

   {
   return leaf_iterator(feet);
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::parent

(

iter

position

)

[inline, static]

Return iterator to the parent of a node.

Definition at line 751 of file tree.h.

Referenced by functionReturnValue(), insert_statement(), Ast::is_skeleton_node(), tree< T, tree_node_allocator >::merge(), ControlFlow::operator()(), RenameFunction::operator()(), RenameClass::operator()(), NumberSunkDiffuseInputs::operator()(), NumberDiffuseInputs::operator()(), NumberInput::operator()(), tree< T, tree_node_allocator >::replace(), rewind(), Ast::skeleton(), Ast::trace(), and writeSiblingsCPP().

   {
   assert(position.node!=0);
   return iter(position.node->parent);
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::previous_sibling

(

iter

position

)

const [inline]

Return iterator to the previous sibling of a node.

Definition at line 759 of file tree.h.

   {
   assert(position.node!=0);
   iter ret(position);
   ret.node=position.node->prev_sibling;
   return ret;
   }

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::next_sibling

(

iter

position

)

const [inline]

Return iterator to the next sibling of a node.

Definition at line 769 of file tree.h.

   {
   assert(position.node!=0);
   iter ret(position);
   ret.node=position.node->next_sibling;
   return ret;
   }

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::next_at_same_depth

(

iter

position

)

const [inline]

Return iterator to the next node at a given depth.

Definition at line 779 of file tree.h.

   {
   assert(position.node!=0);
   iter ret(position);

   if(position.node->next_sibling) {
      ret.node=position.node->next_sibling;
      }
   else { 
      int relative_depth=0;
      upper:
      do {
         ret.node=ret.node->parent;
         if(ret.node==0) return ret;
         --relative_depth;
         } while(ret.node->next_sibling==0);
      lower:
      ret.node=ret.node->next_sibling;
      while(ret.node->first_child==0) {
         if(ret.node->next_sibling==0)
            goto upper;
         ret.node=ret.node->next_sibling;
         if(ret.node==0) return ret;
         }
      while(relative_depth<0 && ret.node->first_child!=0) {
         ret.node=ret.node->first_child;
         ++relative_depth;
         }
      if(relative_depth<0) {
         if(ret.node->next_sibling==0) goto upper;
         else                          goto lower;
         }
      }
   return ret;
   }

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::clear

(

)

[inline]

Erase all nodes of the tree.

Definition at line 582 of file tree.h.

References tree< T, tree_node_allocator >::erase(), tree< T, tree_node_allocator >::feet, tree< T, tree_node_allocator >::head, and tree_node_< T >::next_sibling.

Referenced by tree< T, tree_node_allocator >::copy_(), and tree< T, tree_node_allocator >::~tree().

   {
   if(head)
      while(head->next_sibling!=feet)
         erase(pre_order_iterator(head->next_sibling));
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::erase

(

iter

it

)

[inline]

Erase element at position pointed to by iterator, return incremented iterator.

Definition at line 612 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, tree_node_< T >::data, kp::destructor(), tree< T, tree_node_allocator >::erase_children(), tree< T, tree_node_allocator >::head, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

Referenced by clean_pattern(), tree< T, tree_node_allocator >::clear(), move_branch(), tree< T, tree_node_allocator >::move_ontop(), and tree< T, tree_node_allocator >::replace().

   {
   tree_node *cur=it.node;
   assert(cur!=head);
   iter ret=it;
   ret.skip_children();
   ++ret;
   erase_children(it);
   if(cur->prev_sibling==0) {
      cur->parent->first_child=cur->next_sibling;
      }
   else {
      cur->prev_sibling->next_sibling=cur->next_sibling;
      }
   if(cur->next_sibling==0) {
      cur->parent->last_child=cur->prev_sibling;
      }
   else {
      cur->next_sibling->prev_sibling=cur->prev_sibling;
      }

   kp::destructor(&cur->data);
   alloc_.deallocate(cur,1);
   return ret;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::erase_children

(

const iterator_base &

it

)

[inline]

Erase all children of the node pointed to by iterator.

Definition at line 590 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, tree_node_< T >::data, kp::destructor(), and tree_node_< T >::next_sibling.

Referenced by tree< T, tree_node_allocator >::erase(), and tree< T, tree_node_allocator >::replace().

   {
// std::cout << "erase_children " << it.node << std::endl;
   if(it.node==0) return;

   tree_node *cur=it.node->first_child;
   tree_node *prev=0;

   while(cur!=0) {
      prev=cur;
      cur=cur->next_sibling;
      erase_children(pre_order_iterator(prev));
      kp::destructor(&prev->data);
      alloc_.deallocate(prev,1);
      }
   it.node->first_child=0;
   it.node->last_child=0;
// std::cout << "exit" << std::endl;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::append_child

(

iter

position

)

[inline]

Insert empty node as last/first child of node pointed to by position.

Definition at line 817 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, tree_node_< T >::first_child, tree< T, tree_node_allocator >::head, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

Referenced by tree< T, tree_node_allocator >::append_child(), copy_branch(), insert_branch(), insert_statement(), tree< T, tree_node_allocator >::merge(), tree< T, tree_node_allocator >::replace(), and Ast::walk().

   {
   assert(position.node!=head);
   assert(position.node);

   tree_node *tmp=alloc_.allocate(1,0);
   kp::constructor(&tmp->data);
   tmp->first_child=0;
   tmp->last_child=0;

   tmp->parent=position.node;
   if(position.node->last_child!=0) {
      position.node->last_child->next_sibling=tmp;
      }
   else {
      position.node->first_child=tmp;
      }
   tmp->prev_sibling=position.node->last_child;
   position.node->last_child=tmp;
   tmp->next_sibling=0;
   return tmp;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::prepend_child

(

iter

position

)

[inline]

Definition at line 842 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, tree_node_< T >::first_child, tree< T, tree_node_allocator >::head, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

Referenced by tree< T, tree_node_allocator >::prepend_child().

   {
   assert(position.node!=head);
   assert(position.node);

   tree_node *tmp=alloc_.allocate(1,0);
   kp::constructor(&tmp->data);
   tmp->first_child=0;
   tmp->last_child=0;

   tmp->parent=position.node;
   if(position.node->first_child!=0) {
      position.node->first_child->prev_sibling=tmp;
      }
   else {
      position.node->last_child=tmp;
      }
   tmp->next_sibling=position.node->first_child;
   position.node->prev_child=tmp;
   tmp->prev_sibling=0;
   return tmp;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::append_child	(	iter	position,
		const T &	x
	)			[inline]

Insert node as last/first child of node pointed to by position.

Definition at line 867 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, tree_node_< T >::first_child, tree< T, tree_node_allocator >::head, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

   {
   // If your program fails here you probably used 'append_child' to add the top
   // node to an empty tree. From version 1.45 the top element should be added
   // using 'insert'. See the documentation for further information, and sorry about
   // the API change.
   assert(position.node!=head);
   assert(position.node);

   tree_node* tmp = alloc_.allocate(1,0);
   kp::constructor(&tmp->data, x);
   tmp->first_child=0;
   tmp->last_child=0;

   tmp->parent=position.node;
   if(position.node->last_child!=0) {
      position.node->last_child->next_sibling=tmp;
      }
   else {
      position.node->first_child=tmp;
      }
   tmp->prev_sibling=position.node->last_child;
   position.node->last_child=tmp;
   tmp->next_sibling=0;
   return tmp;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::prepend_child	(	iter	position,
		const T &	x
	)			[inline]

Definition at line 896 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, tree_node_< T >::first_child, tree< T, tree_node_allocator >::head, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

   {
   assert(position.node!=head);
   assert(position.node);

   tree_node* tmp = alloc_.allocate(1,0);
   kp::constructor(&tmp->data, x);
   tmp->first_child=0;
   tmp->last_child=0;

   tmp->parent=position.node;
   if(position.node->first_child!=0) {
      position.node->first_child->prev_sibling=tmp;
      }
   else {
      position.node->last_child=tmp;
      }
   tmp->next_sibling=position.node->first_child;
   position.node->first_child=tmp;
   tmp->prev_sibling=0;
   return tmp;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::append_child	(	iter	position,
		iter	other_position
	)			[inline]

Append the node (plus its children) at other_position as last/first child of position.

Definition at line 921 of file tree.h.

References tree< T, tree_node_allocator >::append_child(), tree< T, tree_node_allocator >::head, and tree< T, tree_node_allocator >::replace().

   {
   assert(position.node!=head);
   assert(position.node);

   sibling_iterator aargh=append_child(position, value_type());
   return replace(aargh, other);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::prepend_child	(	iter	position,
		iter	other_position
	)			[inline]

Definition at line 932 of file tree.h.

References tree< T, tree_node_allocator >::head, tree< T, tree_node_allocator >::prepend_child(), and tree< T, tree_node_allocator >::replace().

   {
   assert(position.node!=head);
   assert(position.node);

   sibling_iterator aargh=prepend_child(position, value_type());
   return replace(aargh, other);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::append_children	(	iter	position,
		sibling_iterator	from,
		sibling_iterator	to
	)			[inline]

Append the nodes in the from-to range (plus their children) as last/first children of position.

Definition at line 943 of file tree.h.

References tree< T, tree_node_allocator >::head, and tree< T, tree_node_allocator >::insert_subtree().

   {
   assert(position.node!=head);
   assert(position.node);

   iter ret=from;

   while(from!=to) {
      insert_subtree(position.end(), from);
      ++from;
      }
   return ret;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::prepend_children	(	iter	position,
		sibling_iterator	from,
		sibling_iterator	to
	)			[inline]

Definition at line 959 of file tree.h.

References tree< T, tree_node_allocator >::head, and tree< T, tree_node_allocator >::insert_subtree().

   {
   assert(position.node!=head);
   assert(position.node);

   iter ret=from;

   while(from!=to) {
      insert_subtree(position.begin(), from);
      ++from;
      }
   return ret;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::set_head

(

const T &

x

)

[inline]

Short-hand to insert topmost node in otherwise empty tree.

Definition at line 974 of file tree.h.

References tree< T, tree_node_allocator >::feet, tree< T, tree_node_allocator >::head, tree< T, tree_node_allocator >::insert(), and tree_node_< T >::next_sibling.

Referenced by tree< T, tree_node_allocator >::subtree(), and tree< T, tree_node_allocator >::tree().

   {
   assert(head->next_sibling==feet);
   return insert(iterator(feet), x);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::insert	(	iter	position,
		const T &	x
	)			[inline]

Insert node as previous sibling of node pointed to by position.

Definition at line 982 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, tree< T, tree_node_allocator >::feet, tree_node_< T >::first_child, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

Referenced by tree< T, tree_node_allocator >::copy_(), tree< T, tree_node_allocator >::insert_subtree(), tree< T, tree_node_allocator >::set_head(), and tree< T, tree_node_allocator >::wrap().

   {
   if(position.node==0) {
      position.node=feet; // Backward compatibility: when calling insert on a null node,
                          // insert before the feet.
      }
   tree_node* tmp = alloc_.allocate(1,0);
   kp::constructor(&tmp->data, x);
   tmp->first_child=0;
   tmp->last_child=0;

   tmp->parent=position.node->parent;
   tmp->next_sibling=position.node;
   tmp->prev_sibling=position.node->prev_sibling;
   position.node->prev_sibling=tmp;

   if(tmp->prev_sibling==0) {
      if(tmp->parent) // when inserting nodes at the head, there is no parent
         tmp->parent->first_child=tmp;
      }
   else
      tmp->prev_sibling->next_sibling=tmp;
   return tmp;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::insert	(	sibling_iterator	position,
		const T &	x
	)			[inline]

Specialisation of previous member.

Definition at line 1008 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, tree_node_< T >::first_child, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree< T, tree_node_allocator >::iterator_base::node, tree_node_< T >::parent, tree< T, tree_node_allocator >::sibling_iterator::parent_, tree_node_< T >::prev_sibling, and tree< T, tree_node_allocator >::sibling_iterator::range_last().

   {
   tree_node* tmp = alloc_.allocate(1,0);
   kp::constructor(&tmp->data, x);
   tmp->first_child=0;
   tmp->last_child=0;

   tmp->next_sibling=position.node;
   if(position.node==0) { // iterator points to end of a subtree
      tmp->parent=position.parent_;
      tmp->prev_sibling=position.range_last();
      tmp->parent->last_child=tmp;
      }
   else {
      tmp->parent=position.node->parent;
      tmp->prev_sibling=position.node->prev_sibling;
      position.node->prev_sibling=tmp;
      }

   if(tmp->prev_sibling==0) {
      if(tmp->parent) // when inserting nodes at the head, there is no parent
         tmp->parent->first_child=tmp;
      }
   else
      tmp->prev_sibling->next_sibling=tmp;
   return tmp;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::insert_subtree	(	iter	position,
		const iterator_base &	subtree
	)			[inline]

Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.

Definition at line 1062 of file tree.h.

References tree< T, tree_node_allocator >::insert(), and tree< T, tree_node_allocator >::replace().

Referenced by tree< T, tree_node_allocator >::append_children(), tree< T, tree_node_allocator >::merge(), tree< T, tree_node_allocator >::prepend_children(), and tree< T, tree_node_allocator >::replace().

   {
   // insert dummy
   iter it=insert(position, value_type());
   // replace dummy with subtree
   return replace(it, subtree);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::insert_after	(	iter	position,
		const T &	x
	)			[inline]

Insert node as next sibling of node pointed to by position.

Definition at line 1038 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, tree_node_< T >::first_child, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

Referenced by tree< T, tree_node_allocator >::insert_subtree_after().

   {
   tree_node* tmp = alloc_.allocate(1,0);
   kp::constructor(&tmp->data, x);
   tmp->first_child=0;
   tmp->last_child=0;

   tmp->parent=position.node->parent;
   tmp->prev_sibling=position.node;
   tmp->next_sibling=position.node->next_sibling;
   position.node->next_sibling=tmp;

   if(tmp->next_sibling==0) {
      if(tmp->parent) // when inserting nodes at the head, there is no parent
         tmp->parent->last_child=tmp;
      }
   else {
      tmp->next_sibling->prev_sibling=tmp;
      }
   return tmp;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::insert_subtree_after	(	iter	position,
		const iterator_base &	subtree
	)			[inline]

Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.

Definition at line 1072 of file tree.h.

References tree< T, tree_node_allocator >::insert_after(), and tree< T, tree_node_allocator >::replace().

   {
   // insert dummy
   iter it=insert_after(position, value_type());
   // replace dummy with subtree
   return replace(it, subtree);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::replace	(	iter	position,
		const T &	x
	)			[inline]

Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.

Definition at line 1092 of file tree.h.

References kp::constructor(), and kp::destructor().

Referenced by tree< T, tree_node_allocator >::append_child(), tree< T, tree_node_allocator >::copy_(), tree< T, tree_node_allocator >::insert_subtree(), tree< T, tree_node_allocator >::insert_subtree_after(), tree< T, tree_node_allocator >::prepend_child(), tree< T, tree_node_allocator >::subtree(), and tree< T, tree_node_allocator >::tree().

   {
   kp::destructor(&position.node->data);
   kp::constructor(&position.node->data, x);
   return position;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<class iter>

iter tree< T, tree_node_allocator >::replace	(	iter	position,
		const iterator_base &	from
	)			[inline]

Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.

Definition at line 1101 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, tree< T, tree_node_allocator >::append_child(), kp::constructor(), tree_node_< T >::data, kp::destructor(), tree< T, tree_node_allocator >::erase_children(), tree_node_< T >::first_child, tree< T, tree_node_allocator >::head, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree< T, tree_node_allocator >::parent(), tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

   {
   assert(position.node!=head);
   tree_node *current_from=from.node;
   tree_node *start_from=from.node;
   tree_node *current_to  =position.node;

   // replace the node at position with head of the replacement tree at from
// std::cout << "warning!" << position.node << std::endl;
   erase_children(position);  
// std::cout << "no warning!" << std::endl;
   tree_node* tmp = alloc_.allocate(1,0);
   kp::constructor(&tmp->data, (*from));
   tmp->first_child=0;
   tmp->last_child=0;
   if(current_to->prev_sibling==0) {
      if(current_to->parent!=0)
         current_to->parent->first_child=tmp;
      }
   else {
      current_to->prev_sibling->next_sibling=tmp;
      }
   tmp->prev_sibling=current_to->prev_sibling;
   if(current_to->next_sibling==0) {
      if(current_to->parent!=0)
         current_to->parent->last_child=tmp;
      }
   else {
      current_to->next_sibling->prev_sibling=tmp;
      }
   tmp->next_sibling=current_to->next_sibling;
   tmp->parent=current_to->parent;
   kp::destructor(&current_to->data);
   alloc_.deallocate(current_to,1);
   current_to=tmp;
   
   // only at this stage can we fix 'last'
   tree_node *last=from.node->next_sibling;

   pre_order_iterator toit=tmp;
   // copy all children
   do {
      assert(current_from!=0);
      if(current_from->first_child != 0) {
         current_from=current_from->first_child;
         toit=append_child(toit, current_from->data);
         }
      else {
         while(current_from->next_sibling==0 && current_from!=start_from) {
            current_from=current_from->parent;
            toit=parent(toit);
            assert(current_from!=0);
            }
         current_from=current_from->next_sibling;
         if(current_from!=last) {
            toit=append_child(parent(toit), current_from->data);
            }
         }
      } while(current_from!=last);

   return current_to;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::replace	(	sibling_iterator	orig_begin,
		sibling_iterator	orig_end,
		sibling_iterator	new_begin,
		sibling_iterator	new_end
	)			[inline]

Replace string of siblings (plus their children) with copy of a new string (with children); see above.

Definition at line 1165 of file tree.h.

References tree< T, tree_node_allocator >::erase(), tree< T, tree_node_allocator >::insert_subtree(), tree_node_< T >::next_sibling, and tree< T, tree_node_allocator >::iterator_base::node.

   {
   tree_node *orig_first=orig_begin.node;
   tree_node *new_first=new_begin.node;
   tree_node *orig_last=orig_first;
   while((++orig_begin)!=orig_end)
      orig_last=orig_last->next_sibling;
   tree_node *new_last=new_first;
   while((++new_begin)!=new_end)
      new_last=new_last->next_sibling;

   // insert all siblings in new_first..new_last before orig_first
   bool first=true;
   pre_order_iterator ret;
   while(1==1) {
      pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
      if(first) {
         ret=tt;
         first=false;
         }
      if(new_first==new_last)
         break;
      new_first=new_first->next_sibling;
      }

   // erase old range of siblings
   bool last=false;
   tree_node *next=orig_first;
   while(1==1) {
      if(next==orig_last) 
         last=true;
      next=next->next_sibling;
      erase((pre_order_iterator)orig_first);
      if(last) 
         break;
      orig_first=next;
      }
   return ret;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::flatten

(

iter

position

)

[inline]

Move all children of node at 'position' to be siblings, returns position.

Definition at line 1211 of file tree.h.

References tree_node_< T >::next_sibling, and tree_node_< T >::parent.

   {
   if(position.node->first_child==0)
      return position;

   tree_node *tmp=position.node->first_child;
   while(tmp) {
      tmp->parent=position.node->parent;
      tmp=tmp->next_sibling;
      } 
   if(position.node->next_sibling) {
      position.node->last_child->next_sibling=position.node->next_sibling;
      position.node->next_sibling->prev_sibling=position.node->last_child;
      }
   else {
      position.node->parent->last_child=position.node->last_child;
      }
   position.node->next_sibling=position.node->first_child;
   position.node->next_sibling->prev_sibling=position.node;
   position.node->first_child=0;
   position.node->last_child=0;

   return position;
   }

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::reparent	(	iter	position,
		sibling_iterator	begin,
		sibling_iterator	end
	)			[inline]

Move nodes in range to be children of 'position'.

Definition at line 1239 of file tree.h.

References tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree< T, tree_node_allocator >::iterator_base::node, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

Referenced by tree< T, tree_node_allocator >::reparent(), Ast::skeleton(), and tree< T, tree_node_allocator >::wrap().

   {
   tree_node *first=begin.node;
   tree_node *last=first;

   assert(first!=position.node);
   
   if(begin==end) return begin;
   // determine last node
   while((++begin)!=end) {
      last=last->next_sibling;
      }
   // move subtree
   if(first->prev_sibling==0) {
      first->parent->first_child=last->next_sibling;
      }
   else {
      first->prev_sibling->next_sibling=last->next_sibling;
      }
   if(last->next_sibling==0) {
      last->parent->last_child=first->prev_sibling;
      }
   else {
      last->next_sibling->prev_sibling=first->prev_sibling;
      }
   if(position.node->first_child==0) {
      position.node->first_child=first;
      position.node->last_child=last;
      first->prev_sibling=0;
      }
   else {
      position.node->last_child->next_sibling=first;
      first->prev_sibling=position.node->last_child;
      position.node->last_child=last;
      }
   last->next_sibling=0;

   tree_node *pos=first;
   while(1==1) {
      pos->parent=position.node;
      if(pos==last) break;
      pos=pos->next_sibling;
      }

   return first;
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::reparent	(	iter	position,
		iter	from
	)			[inline]

Move all child nodes of 'from' to be children of 'position'.

Definition at line 1287 of file tree.h.

References tree< T, tree_node_allocator >::end(), and tree< T, tree_node_allocator >::reparent().

   {
   if(from.node->first_child==0) return position;
   return reparent(position, from.node->first_child, end(from));
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::wrap	(	iter	position,
		const T &	x
	)			[inline]

Replace node with a new node, making the old node a child of the new node.

Definition at line 1294 of file tree.h.

References tree< T, tree_node_allocator >::insert(), and tree< T, tree_node_allocator >::reparent().

   {
   assert(position.node!=0);
   sibling_iterator fr=position, to=position;
   ++to;
   iter ret = insert(position, x);
   reparent(ret, fr, to);
   return ret;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::move_after	(	iter	target,
		iter	source
	)			[inline]

Move 'source' node (plus its children) to become the next sibling of 'target'.

Definition at line 1305 of file tree.h.

References tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

   {
   tree_node *dst=target.node;
   tree_node *src=source.node;
   assert(dst);
   assert(src);

   if(dst==src) return source;
   if(dst->next_sibling)
      if(dst->next_sibling==src) // already in the right spot
         return source;

   // take src out of the tree
   if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
   else                     src->parent->first_child=src->next_sibling;
   if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
   else                     src->parent->last_child=src->prev_sibling;

   // connect it to the new point
   if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
   else                     dst->parent->last_child=src;
   src->next_sibling=dst->next_sibling;
   dst->next_sibling=src;
   src->prev_sibling=dst;
   src->parent=dst->parent;
   return src;
   }

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::move_before	(	iter	target,
		iter	source
	)			[inline]

Move 'source' node (plus its children) to become the previous sibling of 'target'.

Definition at line 1334 of file tree.h.

References tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

   {
   tree_node *dst=target.node;
   tree_node *src=source.node;
   assert(dst);
   assert(src);

   if(dst==src) return source;
   if(dst->prev_sibling)
      if(dst->prev_sibling==src) // already in the right spot
         return source;

   // take src out of the tree
   if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
   else                     src->parent->first_child=src->next_sibling;
   if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
   else                     src->parent->last_child=src->prev_sibling;

   // connect it to the new point
   if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
   else                     dst->parent->first_child=src;
   src->prev_sibling=dst->prev_sibling;
   dst->prev_sibling=src;
   src->next_sibling=dst;
   src->parent=dst->parent;
   return src;
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::move_before	(	sibling_iterator	target,
		sibling_iterator	source
	)			[inline]

Definition at line 1364 of file tree.h.

References tree_node_< T >::first_child, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree< T, tree_node_allocator >::iterator_base::node, tree_node_< T >::parent, tree< T, tree_node_allocator >::sibling_iterator::parent_, and tree_node_< T >::prev_sibling.

   {
   tree_node *dst=target.node;
   tree_node *src=source.node;
   tree_node *dst_prev_sibling;
   if(dst==0) { // must then be an end iterator
      dst_prev_sibling=target.parent_->last_child;
      assert(dst_prev_sibling);
      }
   else dst_prev_sibling=dst->prev_sibling;
   assert(src);

   if(dst==src) return source;
   if(dst_prev_sibling)
      if(dst_prev_sibling==src) // already in the right spot
         return source;

   // take src out of the tree
   if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
   else                     src->parent->first_child=src->next_sibling;
   if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
   else                     src->parent->last_child=src->prev_sibling;

   // connect it to the new point
   if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
   else                    target.parent_->first_child=src;
   src->prev_sibling=dst_prev_sibling;
   if(dst) {
      dst->prev_sibling=src;
      src->parent=dst->parent;
      }
   src->next_sibling=dst;
   return src;
   }

template<class T, class tree_node_allocator>

template<typename iter>

iter tree< T, tree_node_allocator >::move_ontop	(	iter	target,
		iter	source
	)			[inline]

Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').

Definition at line 1401 of file tree.h.

References tree< T, tree_node_allocator >::erase(), tree_node_< T >::first_child, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

   {
   tree_node *dst=target.node;
   tree_node *src=source.node;
   assert(dst);
   assert(src);

   if(dst==src) return source;

   // remember connection points
   tree_node *b_prev_sibling=dst->prev_sibling;
   tree_node *b_next_sibling=dst->next_sibling;
   tree_node *b_parent=dst->parent;

   // remove target
   erase(target);

   // take src out of the tree
   if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
   else                     src->parent->first_child=src->next_sibling;
   if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
   else                     src->parent->last_child=src->prev_sibling;

   // connect it to the new point
   if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
   else                  b_parent->first_child=src;
   if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
   else                  b_parent->last_child=src;
   src->prev_sibling=b_prev_sibling;
   src->next_sibling=b_next_sibling;
   src->parent=b_parent;
   return src;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::merge	(	sibling_iterator	to1,
		sibling_iterator	to2,
		sibling_iterator	from1,
		sibling_iterator	from2,
		bool	duplicate_leaves = false
	)			[inline]

Merge with other tree, creating new branches and leaves only if they are not already present.

Definition at line 1436 of file tree.h.

References tree< T, tree_node_allocator >::append_child(), tree< T, tree_node_allocator >::iterator_base::begin(), tree< T, tree_node_allocator >::iterator_base::end(), tree< T, tree_node_allocator >::insert_subtree(), and tree< T, tree_node_allocator >::parent().

   {
   sibling_iterator fnd;
   while(from1!=from2) {
      if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
         if(from1.begin()==from1.end()) { // full depth reached
            if(duplicate_leaves)
               append_child(parent(to1), (*from1));
            }
         else { // descend further
            merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
            }
         }
      else { // element missing
         insert_subtree(to2, from1);
         }
      ++from1;
      }
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::sort	(	sibling_iterator	from,
		sibling_iterator	to,
		bool	deep = false
	)			[inline]

Sort (std::sort only moves values of nodes, this one moves children as well).

Definition at line 1460 of file tree.h.

Referenced by tree< T, tree_node_allocator >::sort().

   {
   std::less<T> comp;
   sort(from, to, comp, deep);
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<class StrictWeakOrdering>

void tree< T, tree_node_allocator >::sort	(	sibling_iterator	from,
		sibling_iterator	to,
		StrictWeakOrdering	comp,
		bool	deep = false
	)			[inline]

Definition at line 1468 of file tree.h.

References tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::end(), tree_node_< T >::next_sibling, tree< T, tree_node_allocator >::iterator_base::node, tree_node_< T >::parent, tree_node_< T >::prev_sibling, and tree< T, tree_node_allocator >::sort().

   {
   if(from==to) return;
   // make list of sorted nodes
   // CHECK: if multiset stores equivalent nodes in the order in which they
   // are inserted, then this routine should be called 'stable_sort'.
   std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
   sibling_iterator it=from, it2=to;
   while(it != to) {
      nodes.insert(it.node);
      ++it;
      }
   // reassemble
   --it2;

   // prev and next are the nodes before and after the sorted range
   tree_node *prev=from.node->prev_sibling;
   tree_node *next=it2.node->next_sibling;
   typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
   if(prev==0) {
      if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
         (*nit)->parent->first_child=(*nit);
      }
   else prev->next_sibling=(*nit);

   --eit;
   while(nit!=eit) {
      (*nit)->prev_sibling=prev;
      if(prev)
         prev->next_sibling=(*nit);
      prev=(*nit);
      ++nit;
      }
   // prev now points to the last-but-one node in the sorted range
   if(prev)
      prev->next_sibling=(*eit);

   // eit points to the last node in the sorted range.
   (*eit)->next_sibling=next;
   (*eit)->prev_sibling=prev; // missed in the loop above
   if(next==0) {
      if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
         (*eit)->parent->last_child=(*eit);
      }
   else next->prev_sibling=(*eit);

   if(deep) {  // sort the children of each node too
      sibling_iterator bcs(*nodes.begin());
      sibling_iterator ecs(*eit);
      ++ecs;
      while(bcs!=ecs) {
         sort(begin(bcs), end(bcs), comp, deep);
         ++bcs;
         }
      }
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

bool tree< T, tree_node_allocator >::equal	(	const iter &	one,
		const iter &	two,
		const iter &	three
	)			const [inline]

Compare two ranges of nodes (compares nodes as well as tree structure).

Definition at line 1528 of file tree.h.

Referenced by tree< T, tree_node_allocator >::equal_subtree().

   {
   std::equal_to<T> comp;
   return equal(one_, two, three_, comp);
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

template<typename iter, class BinaryPredicate>

bool tree< T, tree_node_allocator >::equal	(	const iter &	one,
		const iter &	two,
		const iter &	three,
		BinaryPredicate	fun
	)			const [inline]

Definition at line 1544 of file tree.h.

References tree< T, tree_node_allocator >::is_valid(), and tree< T, tree_node_allocator >::iterator_base::number_of_children().

   {
   pre_order_iterator one(one_), three(three_);

// if(one==two && is_valid(three) && three.number_of_children()!=0)
//    return false;
   while(one!=two && is_valid(three)) {
      if(!fun(*one,*three))
         return false;
      if(one.number_of_children()!=three.number_of_children()) 
         return false;
      ++one;
      ++three;
      }
   return true;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

template<typename iter>

bool tree< T, tree_node_allocator >::equal_subtree	(	const iter &	one,
		const iter &	two
	)			const [inline]

Definition at line 1536 of file tree.h.

   {
   std::equal_to<T> comp;
   return equal_subtree(one_, two_, comp);
   }

template<class T, class tree_node_allocator>

template<typename iter, class BinaryPredicate>

bool tree< T, tree_node_allocator >::equal_subtree	(	const iter &	one,
		const iter &	two,
		BinaryPredicate	fun
	)			const [inline]

Definition at line 1563 of file tree.h.

References tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::end(), tree< T, tree_node_allocator >::equal(), and tree< T, tree_node_allocator >::number_of_children().

   {
   pre_order_iterator one(one_), two(two_);

   if(!fun(*one,*two)) return false;
   if(number_of_children(one)!=number_of_children(two)) return false;
   return equal(begin(one),end(one),begin(two),fun);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator > tree< T, tree_node_allocator >::subtree	(	sibling_iterator	from,
		sibling_iterator	to
	)			const [inline]

Extract a new tree formed by the range of siblings plus all their children.

Definition at line 1573 of file tree.h.

References tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::end(), tree< T, tree_node_allocator >::replace(), and tree< T, tree_node_allocator >::set_head().

   {
   tree tmp;
   tmp.set_head(value_type());
   tmp.replace(tmp.begin(), tmp.end(), from, to);
   return tmp;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::subtree	(	tree< T, tree_node_allocator > &	tmp,
		sibling_iterator	from,
		sibling_iterator	to
	)			const [inline]

Definition at line 1582 of file tree.h.

References tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::end(), tree< T, tree_node_allocator >::replace(), and tree< T, tree_node_allocator >::set_head().

   {
   tmp.set_head(value_type());
   tmp.replace(tmp.begin(), tmp.end(), from, to);
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::swap

(

sibling_iterator

it

)

[inline]

Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).

Definition at line 1675 of file tree.h.

References tree_node_< T >::next_sibling, tree< T, tree_node_allocator >::iterator_base::node, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

Referenced by tree< T, tree_node_allocator >::swap().

   {
   tree_node *nxt=it.node->next_sibling;
   if(nxt) {
      if(it.node->prev_sibling)
         it.node->prev_sibling->next_sibling=nxt;
      else
         it.node->parent->first_child=nxt;
      nxt->prev_sibling=it.node->prev_sibling;
      tree_node *nxtnxt=nxt->next_sibling;
      if(nxtnxt)
         nxtnxt->prev_sibling=it.node;
      else
         it.node->parent->last_child=it.node;
      nxt->next_sibling=it.node;
      it.node->prev_sibling=nxt;
      it.node->next_sibling=nxtnxt;
      }
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::swap	(	iterator	one,
		iterator	two
	)			[inline]

Exchange two nodes (plus subtrees).

Definition at line 1696 of file tree.h.

References tree_node_< T >::first_child, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree< T, tree_node_allocator >::iterator_base::node, tree_node_< T >::parent, tree_node_< T >::prev_sibling, and tree< T, tree_node_allocator >::swap().

   {
   // if one and two are adjacent siblings, use the sibling swap
   if(one.node->next_sibling==two.node) swap(one);
   else if(two.node->next_sibling==one.node) swap(two);
   else {
      tree_node *nxt1=one.node->next_sibling;
      tree_node *nxt2=two.node->next_sibling;
      tree_node *pre1=one.node->prev_sibling;
      tree_node *pre2=two.node->prev_sibling;
      tree_node *par1=one.node->parent;
      tree_node *par2=two.node->parent;

      // reconnect
      one.node->parent=par2;
      one.node->next_sibling=nxt2;
      if(nxt2) nxt2->prev_sibling=one.node;
      else     par2->last_child=one.node;
      one.node->prev_sibling=pre2;
      if(pre2) pre2->next_sibling=one.node;
      else     par2->first_child=one.node;    

      two.node->parent=par1;
      two.node->next_sibling=nxt1;
      if(nxt1) nxt1->prev_sibling=two.node;
      else     par1->last_child=two.node;
      two.node->prev_sibling=pre1;
      if(pre1) pre1->next_sibling=two.node;
      else     par1->first_child=two.node;
      }
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

int tree< T, tree_node_allocator >::size

(

)

const [inline]

Count the total number of nodes.

Definition at line 1589 of file tree.h.

References tree< T, tree_node_allocator >::begin(), and tree< T, tree_node_allocator >::end().

   {
   int i=0;
   pre_order_iterator it=begin(), eit=end();
   while(it!=eit) {
      ++i;
      ++it;
      }
   return i;
   }

Here is the call graph for this function:

template<class T, class tree_node_allocator>

int tree< T, tree_node_allocator >::size

(

const iterator_base &

top

)

const [inline]

Count the total number of nodes below the indicated node (plus one).

Definition at line 1601 of file tree.h.

   {
   int i=0;
   pre_order_iterator it=top, eit=top;
   eit.skip_children();
   ++eit;
   while(it!=eit) {
      ++i;
      ++it;
      }
   return i;
   }

template<class T, class tree_node_allocator>

bool tree< T, tree_node_allocator >::empty

(

)

const [inline]

Check if tree is empty.

Definition at line 1615 of file tree.h.

References tree< T, tree_node_allocator >::begin(), and tree< T, tree_node_allocator >::end().

Referenced by exportXML(), kptree::print_subtree_bracketed(), writeCPP(), writeSiblingsCPP(), and writeSiblingsXML().

   {
   pre_order_iterator it=begin(), eit=end();
   return (it==eit);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

int tree< T, tree_node_allocator >::depth

(

const iterator_base &

it

)

const [inline]

Compute the depth to the root.

Definition at line 1622 of file tree.h.

References tree_node_< T >::parent.

   {
   tree_node* pos=it.node;
   assert(pos!=0);
   int ret=0;
   while(pos->parent!=0) {
      pos=pos->parent;
      ++ret;
      }
   return ret;
   }

template<class T, class tree_node_allocator>

unsigned int tree< T, tree_node_allocator >::number_of_children

(

const iterator_base &

it

)

[inline, static]

Count the number of children of node at position.

Definition at line 1635 of file tree.h.

References tree_node_< T >::next_sibling.

Referenced by addClassCpp(), addFunctionCpp(), copy_branch(), Ast::detectAssignment(), tree< T, tree_node_allocator >::equal_subtree(), Ast::fillAstInformation(), functionReturnValue(), Ast::getLeftVariable(), Ast::getRightVariables(), Ast::getSimpleVariable(), Ast::getSubVariables(), insert_branch(), isAChildrenOf(), NumberSunkDiffuseInputs::operator()(), NumberDiffuseInputs::operator()(), NumberInput::operator()(), kptree::print_subtree_bracketed(), subVarName(), writeSiblingsCPP(), and writeSiblingsXML().

   {
   tree_node *pos=it.node->first_child;
   if(pos==0) return 0;
   
   unsigned int ret=1;
//   while(pos!=it.node->last_child) {
//      ++ret;
//      pos=pos->next_sibling;
//      }
   while((pos=pos->next_sibling))
      ++ret;
   return ret;
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

unsigned int tree< T, tree_node_allocator >::number_of_siblings

(

const iterator_base &

it

)

const [inline]

Count the number of 'next' siblings of node at iterator.

Definition at line 1651 of file tree.h.

References tree< T, tree_node_allocator >::feet, tree< T, tree_node_allocator >::head, tree_node_< T >::next_sibling, and tree_node_< T >::prev_sibling.

Referenced by kptree::print_tree_bracketed().

   {
   tree_node *pos=it.node;
   unsigned int ret=0;
   // count forward
   while(pos->next_sibling && 
         pos->next_sibling!=head &&
         pos->next_sibling!=feet) {
      ++ret;
      pos=pos->next_sibling;
      }
   // count backward
   pos=it.node;
   while(pos->prev_sibling && 
         pos->prev_sibling!=head &&
         pos->prev_sibling!=feet) {
      ++ret;
      pos=pos->prev_sibling;
      }
   
   return ret;
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

bool tree< T, tree_node_allocator >::is_in_subtree	(	const iterator_base &	position,
		const iterator_base &	begin,
		const iterator_base &	end
	)			const [inline]

Determine whether node at position is in the subtrees with root in the range.

Definition at line 1743 of file tree.h.

   {
   // FIXME: this should be optimised.
   pre_order_iterator tmp=begin;
   while(tmp!=end) {
      if(tmp==it) return true;
      ++tmp;
      }
   return false;
   }

template<class T, class tree_node_allocator>

bool tree< T, tree_node_allocator >::is_valid

(

const iterator_base &

it

)

const [inline]

Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.

Definition at line 1756 of file tree.h.

References tree< T, tree_node_allocator >::feet, and tree< T, tree_node_allocator >::head.

Referenced by tree< T, tree_node_allocator >::equal().

   {
   if(it.node==0 || it.node==feet || it.node==head) return false;
   else return true;
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

unsigned int tree< T, tree_node_allocator >::index

(

sibling_iterator

it

)

const [inline]

Determine the index of a node in the range of siblings to which it belongs.

Definition at line 1763 of file tree.h.

References tree< T, tree_node_allocator >::head, tree< T, tree_node_allocator >::iterator_base::node, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

   {
   unsigned int ind=0;
   if(it.node->parent==0) {
      while(it.node->prev_sibling!=head) {
         it.node=it.node->prev_sibling;
         ++ind;
         }
      }
   else {
      while(it.node->prev_sibling!=0) {
         it.node=it.node->prev_sibling;
         ++ind;
         }
      }
   return ind;
   }

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::child	(	const iterator_base &	position,
		unsigned int	num
	)			const [inline]

Inverse of 'index': return the n-th child of the node at position.

Definition at line 1783 of file tree.h.

References tree_node_< T >::next_sibling.

Referenced by addClassCpp(), addFunctionCpp(), Ast::detectAssignment(), Ast::fillAstInformation(), forward(), Ast::getLeftVariable(), Ast::getRightVariables(), Ast::getSimpleVariable(), Ast::getSubVariables(), insert_statement(), isAChildrenOf(), ControlFlow::operator()(), NumberSunkDiffuseInputs::operator()(), subVarName(), and writeSiblingsCPP().

   {
   tree_node *tmp=it.node->first_child;
   while(num--) {
      assert(tmp!=0);
      tmp=tmp->next_sibling;
      }
   return tmp;
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::head_initialise_

(

)

[inline, private]

Definition at line 529 of file tree.h.

References tree< T, tree_node_allocator >::alloc_, tree< T, tree_node_allocator >::feet, tree_node_< T >::first_child, tree< T, tree_node_allocator >::head, tree_node_< T >::last_child, tree_node_< T >::next_sibling, tree_node_< T >::parent, and tree_node_< T >::prev_sibling.

Referenced by tree< T, tree_node_allocator >::tree().

   { 
   head = alloc_.allocate(1,0); // MSVC does not have default second argument 
   feet = alloc_.allocate(1,0);

   head->parent=0;
   head->first_child=0;
   head->last_child=0;
   head->prev_sibling=0; //head;
   head->next_sibling=feet; //head;

   feet->parent=0;
   feet->first_child=0;
   feet->last_child=0;
   feet->prev_sibling=head;
   feet->next_sibling=0;
   }

Here is the caller graph for this function:

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::copy_

(

const tree< T, tree_node_allocator > &

other

)

[inline, private]

Definition at line 561 of file tree.h.

References tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::clear(), tree< T, tree_node_allocator >::end(), tree< T, tree_node_allocator >::insert(), tree< T, tree_node_allocator >::replace(), and tree< T, tree_node_allocator >::iterator_base::skip_children().

Referenced by tree< T, tree_node_allocator >::operator=(), and tree< T, tree_node_allocator >::tree().

   {
   clear();
   pre_order_iterator it=other.begin(), to=begin();
   while(it!=other.end()) {
      to=insert(to, (*it));
      it.skip_children();
      ++it;
      }
   to=begin();
   it=other.begin();
   while(it!=other.end()) {
      to=replace(to, it);
      to.skip_children();
      it.skip_children();
      ++to;
      ++it;
      }
   }

Here is the call graph for this function:

Here is the caller graph for this function:

---

Field Documentation

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

tree_node* tree< T, tree_node_allocator >::head

Definition at line 435 of file tree.h.

Referenced by tree< T, tree_node_allocator >::append_child(), tree< T, tree_node_allocator >::append_children(), tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::begin_breadth_first(), tree< T, tree_node_allocator >::begin_leaf(), tree< T, tree_node_allocator >::begin_post(), tree< T, tree_node_allocator >::clear(), tree< T, tree_node_allocator >::erase(), tree< T, tree_node_allocator >::head_initialise_(), tree< T, tree_node_allocator >::index(), tree< T, tree_node_allocator >::is_valid(), tree< T, tree_node_allocator >::number_of_siblings(), tree< T, tree_node_allocator >::prepend_child(), tree< T, tree_node_allocator >::prepend_children(), tree< T, tree_node_allocator >::replace(), tree< T, tree_node_allocator >::set_head(), and tree< T, tree_node_allocator >::~tree().

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

tree_node * tree< T, tree_node_allocator >::feet

Definition at line 435 of file tree.h.

Referenced by tree< T, tree_node_allocator >::begin_leaf(), tree< T, tree_node_allocator >::begin_post(), tree< T, tree_node_allocator >::clear(), tree< T, tree_node_allocator >::end(), tree< T, tree_node_allocator >::end_leaf(), tree< T, tree_node_allocator >::end_post(), tree< T, tree_node_allocator >::head_initialise_(), tree< T, tree_node_allocator >::insert(), tree< T, tree_node_allocator >::is_valid(), tree< T, tree_node_allocator >::number_of_siblings(), tree< T, tree_node_allocator >::set_head(), and tree< T, tree_node_allocator >::~tree().

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

tree_node_allocator tree< T, tree_node_allocator >::alloc_ [private]

Definition at line 437 of file tree.h.

Referenced by tree< T, tree_node_allocator >::append_child(), tree< T, tree_node_allocator >::erase(), tree< T, tree_node_allocator >::erase_children(), tree< T, tree_node_allocator >::head_initialise_(), tree< T, tree_node_allocator >::insert(), tree< T, tree_node_allocator >::insert_after(), tree< T, tree_node_allocator >::prepend_child(), tree< T, tree_node_allocator >::replace(), and tree< T, tree_node_allocator >::~tree().

---

The documentation for this class was generated from the following file:

• php-oracle/tree.h

---