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 the 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 util/Sawyer/Tree.h.

#include <util/Sawyer/Tree.h>

Inheritance diagram for Sawyer::Tree::ListNode< T >:

[legend]

Collaboration diagram for Sawyer::Tree::ListNode< T >:

[legend]

Public Member Functions
size_t	size () const
	Number of children. More...

size_t	max_size () const
	Maximum size. More...

size_t	capacity () const
	Capacity. More...

bool	empty () const
	Empty predicate. More...

void	reserve (size_t n)
	Reserve space for more children. More...

void	shrink_to_fit ()
	Shrink reservation. More...

const std::shared_ptr< T >	at (size_t i) const
	Child at specified index. More...

const std::shared_ptr< T >	operator[] (size_t i) const
	Child at specified index. More...

const std::shared_ptr< T >	front () const
	First child, if any. More...

const std::shared_ptr< T >	back () const
	Last child, if any. More...

std::vector< std::shared_ptr< T > >	elmts () const
	Vector of all children. More...

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. More...

void	push_back (const std::shared_ptr< T > &newChild)
	Append a child pointer. More...

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. More...

virtual	~Node ()
	Nodes are polymorphic. More...

	Node (const Node &)=delete

Node &	operator= (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. More...

Children	children
	Vector of pointers to children. More...

Member Function Documentation

template<class T >

size_t Sawyer::Tree::ListNode< T >::size ( void ) const

inline

Number of children.

Definition at line 706 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Node::children, and Sawyer::Tree::Children::size().

template<class T >

size_t Sawyer::Tree::ListNode< T >::max_size ( ) const

inline

Maximum size.

Definition at line 711 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Node::children, and Sawyer::Tree::Children::max_size().

template<class T >

size_t Sawyer::Tree::ListNode< T >::capacity ( ) const

inline

Capacity.

Definition at line 716 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Children::capacity(), and Sawyer::Tree::Node::children.

template<class T >

bool Sawyer::Tree::ListNode< T >::empty ( ) const

inline

Empty predicate.

Definition at line 721 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Node::children, and Sawyer::Tree::Children::empty().

template<class T >

void Sawyer::Tree::ListNode< T >::reserve ( size_t n )

inline

Reserve space for more children.

Definition at line 726 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Node::children, and Sawyer::Tree::Children::reserve().

template<class T >

void Sawyer::Tree::ListNode< T >::shrink_to_fit ( )

inline

Shrink reservation.

Definition at line 731 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Node::children, and Sawyer::Tree::Children::shrink_to_fit().

template<class T >

const std::shared_ptr<T> Sawyer::Tree::ListNode< T >::at ( size_t i ) const

inline

Child at specified index.

Definition at line 736 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Children::at(), and Sawyer::Tree::Node::children.

template<class T >

const std::shared_ptr<T> Sawyer::Tree::ListNode< T >::operator[] ( size_t i ) const

inline

Child at specified index.

Definition at line 741 of file util/Sawyer/Tree.h.

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

template<class T >

const std::shared_ptr<T> Sawyer::Tree::ListNode< T >::front ( ) const

inline

First child, if any.

Definition at line 746 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Node::children, and Sawyer::Tree::Children::front().

template<class T >

const std::shared_ptr<T> Sawyer::Tree::ListNode< T >::back ( ) const

inline

Last child, if any.

Definition at line 751 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Children::back(), and Sawyer::Tree::Node::children.

template<class T >

std::vector< std::shared_ptr< T > > Sawyer::Tree::ListNode< T >::elmts ( ) const

Vector of all children.

Definition at line 1162 of file util/Sawyer/Tree.h.

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 util/Sawyer/Tree.h.

template<class T >

void Sawyer::Tree::ListNode< T >::clear ( )

inline

Remove all children.

Definition at line 769 of file util/Sawyer/Tree.h.

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

template<class T >

void Sawyer::Tree::ListNode< T >::push_back ( const std::shared_ptr< T > & newChild )

inline

Append a child pointer.

Definition at line 774 of file util/Sawyer/Tree.h.

References Sawyer::Tree::Node::children, and Sawyer::Tree::Children::size().

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 util/Sawyer/Tree.h.

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

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 util/Sawyer/Tree.h.

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

template<class T >