ROSE  0.11.96.11
Public Member Functions | List of all members
Sawyer::Tree::ListNode< T > Class Template Referencefinal

Description

template<class T>
class Sawyer::Tree::ListNode< T >

A node containing only a list of children.

This class is used for nodes whose sole purpose is to hold a list of child nodes. Rather than having any dedicated data members, it accesses the children member directly in order to store the ordered list of child pointers. New classes cannot be derived from this class since doing so would enable the derived class to have additional ChildPtr data members that would interfere with the children list.

Although the children data member provides a read-only API for accessing the children, we also need to provde an API that can modify that list. The entire children API is available also from this node directly so that the reading and writing APIs can be invoked consistently on this object.

A parent node that points to a node containing a list as well as nodes that are not lists is declared as follows:

class ChildType1; // some user-defined type derived from Tree::Node
class ChildType2; // ditto
class ChildType3; // ditto
class Parent: public Tree::Node {
public:
Tree::ChildEdge<ChildType1> first; // a.k.a., children[0]
Tree::ChildEdge<Tree::ListNode<ChildType2> list; // a.k.a., children[1]
Tree::ChildEdge<ChildType3> last; // a.k.a., children[2] regardless of list's size
Parent()
: first(this), list(this), last(this) {}
}

A common practice when creating a ListNode is to allocate then node when the parent is constructed:

Parent::Parent()
: first(this), list(this, std::make_shared<Tree::ListNode<ChildType2> >()), last(this) {}

If you follow the recommendation of always allocating ListNode data members, then the 10th child (index 9) of the parent node's list can be accessed without worrying about whether parent->list is a null pointer:

std::shared_ptr<Parent> parent = ...;
std::shared_ptr<ChildType2> item = parent->list->at(9);

Since a ListNode is a type of Node, it has a children data member of type Children. All the functions defined for Children are also defined in ListNode itself, plus ListNode has a number of additional member functions for inserting and removing children–something that's not possible with other Node types.

The ListNode type is final because if users could derive subclasses from it, then those subclasses could add ChildEdge data members that would interfere with the child node counting.

Definition at line 699 of file Tree.h.

#include <Tree.h>

Inheritance diagram for Sawyer::Tree::ListNode< T >:
Inheritance graph
[legend]
Collaboration diagram for Sawyer::Tree::ListNode< T >:
Collaboration graph
[legend]

Public Member Functions

size_t size () const
 Number of children.
 
size_t max_size () const
 Maximum size.
 
size_t capacity () const
 Capacity.
 
bool empty () const
 Empty predicate.
 
void reserve (size_t n)
 Reserve space for more children.
 
void shrink_to_fit ()
 Shrink reservation.
 
const std::shared_ptr< T > at (size_t i) const
 Child at specified index.
 
const std::shared_ptr< T > operator[] (size_t i) const
 Child at specified index.
 
const std::shared_ptr< T > front () const
 First child, if any.
 
const std::shared_ptr< T > back () const
 Last child, if any.
 
std::vector< std::shared_ptr< T > > elmts () const
 Vector of all children.
 
Optional< size_t > index (const std::shared_ptr< T > &node, size_t startAt=0) const
 Find the index for the specified node. More...
 
void clear ()
 Remove all children.
 
void push_back (const std::shared_ptr< T > &newChild)
 Append a child pointer.
 
void insertAt (size_t i, const std::shared_ptr< T > &newChild)
 Insert the node at the specified index. More...
 
void eraseAt (size_t i)
 Erase node at specified index. More...
 
Optional< size_t > erase (const std::shared_ptr< T > &toErase, size_t startAt=0)
 Erase the first occurrence of the specified child. More...
 
void setAt (size_t i, const std::shared_ptr< T > &child)
 Make child edge point to a different child.
 
void setAt (size_t i, std::nullptr_t)
 Make child edge point to a different child.
 
- Public Member Functions inherited from Sawyer::Tree::Node
 Node ()
 Construct an empty node.
 
virtual ~Node ()
 Nodes are polymorphic.
 
 Node (const Node &)=delete
 
Nodeoperator= (const Node &)=delete
 
template<class Functor >
TraversalAction traverse (Functor functor)
 Traverse the tree starting at this node and following child pointers. More...
 
template<class Functor >
TraversalAction traverse (Functor functor) const
 Traverse the tree starting at this node and following child pointers. More...
 
template<class T , class Functor >
TraversalAction traverseType (Functor functor)
 Traverse the tree restricted by type. More...
 
template<class T , class Functor >
TraversalAction traverseType (Functor functor) const
 Traverse the tree restricted by type. More...
 
template<class Functor >
TraversalAction traverseParents (Functor functor)
 Traverse the tree by following parent pointers. More...
 
template<class Functor >
TraversalAction traverseParents (Functor functor) const
 Traverse the tree by following parent pointers. More...
 
template<class Predicate >
NodePtr find (Predicate predicate)
 Traverse an tree to find the first node satisfying the predicate.
 
template<class Predicate >
NodePtr find (Predicate predicate) const
 Traverse an tree to find the first node satisfying the predicate.
 
template<class T >
std::shared_ptr< T > findType ()
 Find first child that's the specified type.
 
template<class T >
std::shared_ptr< T > findType () const
 Find first child that's the specified type.
 
template<class T , class Predicate >
std::shared_ptr< T > findType (Predicate predicate)
 Find first child of specified type satisfying the predicate.
 
template<class T , class Predicate >
std::shared_ptr< T > findType (Predicate predicate) const
 Find first child of specified type satisfying the predicate.
 
template<class Predicate >
NodePtr findParent (Predicate predicate)
 Find closest ancestor that satifies the predicate.
 
template<class Predicate >
NodePtr findParent (Predicate predicate) const
 Find closest ancestor that satifies the predicate.
 
template<class T >
std::shared_ptr< T > findParentType ()
 Find closest ancestor of specified type.
 
template<class T >
std::shared_ptr< T > findParentType () const
 Find closest ancestor of specified type.
 
template<class T , class Predicate >
std::shared_ptr< T > findParentType (Predicate predicate)
 Find closest ancestor of specified type that satisfies the predicate.
 
template<class T , class Predicate >
std::shared_ptr< T > findParentType (Predicate predicate) const
 Find closest ancestor of specified type that satisfies the predicate.
 

Additional Inherited Members

- Public Attributes inherited from Sawyer::Tree::Node
ParentEdge parent
 Pointer to the parent node, if any.
 
Children children
 Vector of pointers to children.
 

Member Function Documentation

◆ index()

template<class T >
Optional< size_t > Sawyer::Tree::ListNode< T >::index ( const std::shared_ptr< T > &  node,
size_t  startAt = 0 
) const

Find the index for the specified node.

Finds the index for the first child at or after startAt and returns its index. Returns nothing if the specified node is not found.

Definition at line 1172 of file Tree.h.

◆ insertAt()

template<class T >
void Sawyer::Tree::ListNode< T >::insertAt ( size_t  i,
const std::shared_ptr< T > &  newChild 
)
inline

Insert the node at the specified index.

The node must not already have a parent. The index must be greater than or equal to zero and less than or equal to the current number of nodes. Upon return, the node that was inserted will be found at index i.

Definition at line 794 of file Tree.h.

References Sawyer::Tree::Node::children.

◆ eraseAt()

template<class T >
void Sawyer::Tree::ListNode< T >::eraseAt ( size_t  i)
inline

Erase node at specified index.

If the index is out of range then nothing happens.

Definition at line 801 of file Tree.h.

References Sawyer::Tree::Node::children.

◆ erase()

template<class T >
Optional< size_t > Sawyer::Tree::ListNode< T >::erase ( const std::shared_ptr< T > &  toErase,
size_t  startAt = 0 
)

Erase the first occurrence of the specified child.

Erases the first occurrence of the specified child at or after the starting index.

If a child was erased, then return the index of the erased child.

Definition at line 1182 of file Tree.h.


The documentation for this class was generated from the following file:
Sawyer::Tree::Node::parent
ParentEdge parent
Pointer to the parent node, if any.
Definition: Tree.h:484