tim::graph< T, AllocatorT > Class Template Reference

Arbitrary Graph / Tree (i.e. binary-tree but not binary). It is unlikely that this class will interacted with directly. More...

#include "timemory/storage/graph.hpp"

Collaboration diagram for tim::graph< T, AllocatorT >:

Classes
class	iterator_base
	Base class for iterators, only pointers stored, no traversal logic. 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...

Public Types
using	value_type = T
	Value of the data stored at a node. More...
typedef pre_order_iterator	iterator
	The default iterator types throughout the graph class. More...
typedef const iterator	const_iterator
typedef iterator::difference_type	difference_type

Public Member Functions
	graph ()
	graph (const T &)
	graph (const iterator_base &)
	graph (const graph< T, AllocatorT > &)
	graph (graph< T, AllocatorT > &&) noexcept
	~graph ()
graph< T, AllocatorT > &	operator= (const graph< T, AllocatorT > &)
graph< T, AllocatorT > &	operator= (graph< T, AllocatorT > &&) noexcept
pre_order_iterator	begin () const
	Return iterator to the beginning of the graph. More...
pre_order_iterator	end () const
	Return iterator to the end of the graph. More...
void	clear ()
	Erase all nodes of the graph. More...
template<typename IterT >
IterT	erase (IterT)
	Erase element at position pointed to by iterator, return incremented iterator. More...
void	erase_children (const iterator_base &)
	Erase all children of the node pointed to by iterator. More...
template<typename IterT >
IterT	append_child (IterT position)
	Insert empty node as last/first child of node pointed to by position. More...
template<typename IterT >
IterT	prepend_child (IterT position)
template<typename IterT >
IterT	append_child (IterT position, const T &x)
	Insert node as last/first child of node pointed to by position. More...
template<typename IterT >
IterT	append_child (IterT position, T &&x)
template<typename IterT >
IterT	prepend_child (IterT position, const T &x)
template<typename IterT >
IterT	prepend_child (IterT position, T &&x)
template<typename IterT >
IterT	append_child (IterT position, IterT other_position)
	Append the node (plus its children) at other_position as last/first child of position. More...
template<typename IterT >
IterT	prepend_child (IterT position, IterT other_position)
template<typename IterT >
IterT	append_children (IterT position, sibling_iterator from, const sibling_iterator &to)
	Append the nodes in the from-to range (plus their children) as last/first children of position. More...
template<typename IterT >
IterT	prepend_children (IterT position, sibling_iterator from, sibling_iterator to)
pre_order_iterator	set_head (const T &x)
	Short-hand to insert topmost node in otherwise empty graph. More...
pre_order_iterator	set_head (T &&x)
template<typename IterT >
IterT	insert (IterT position, const T &x)
	Insert node as previous sibling of node pointed to by position. More...
template<typename IterT >
IterT	insert (IterT position, T &&x)
sibling_iterator	insert (sibling_iterator position, const T &x)
	Specialisation of previous member. More...
template<typename IterT >
IterT	insert_subgraph (IterT position, const iterator_base &subgraph)
	Insert node (with children) pointed to by subgraph as previous sibling of node pointed to by position. Does not change the subgraph itself (use move_in or move_in_below for that). More...
template<typename IterT >
IterT	insert_after (IterT position, const T &x)
	Insert node as next sibling of node pointed to by position. More...
template<typename IterT >
IterT	insert_after (IterT position, T &&x)
template<typename IterT >
IterT	insert_subgraph_after (IterT position, const iterator_base &subgraph)
	Insert node (with children) pointed to by subgraph as next sibling of node pointed to by position. More...
template<typename IterT >
IterT	replace (IterT position, const T &x)
	Replace node at 'position' with other node (keeping same children); 'position' becomes invalid. More...
template<typename IterT >
IterT	replace (IterT position, T &&x)
template<typename IterT >
IterT	replace (IterT position, const iterator_base &from)
	Replace node at 'position' with subgraph starting at 'from' (do not erase subgraph at 'from'); see above. More...
sibling_iterator	replace (sibling_iterator orig_begin, const sibling_iterator &orig_end, sibling_iterator new_begin, const sibling_iterator &new_end)
	Replace string of siblings (plus their children) with copy of a new string (with children); see above. More...
template<typename IterT >
IterT	flatten (IterT position)
	Move all children of node at 'position' to be siblings, returns position. More...
template<typename IterT >
IterT	reparent (IterT position, sibling_iterator begin, const sibling_iterator &end)
	Move nodes in range to be children of 'position'. More...
template<typename IterT >
IterT	reparent (IterT position, IterT from)
	Move all child nodes of 'from' to be children of 'position'. More...
template<typename IterT >
IterT	wrap (IterT position, const T &x)
	Replace node with a new node, making the old node (plus subgraph) a child of the new node. More...
template<typename IterT >
IterT	wrap (IterT from, IterT to, const T &x)
	Replace the range of sibling nodes (plus subgraphs), making these children of the new node. More...
template<typename IterT >
IterT	move_after (IterT target, IterT source)
	Move 'source' node (plus its children) to become the next sibling of 'target'. More...
template<typename IterT >
IterT	move_before (IterT target, IterT source)
	Move 'source' node (plus its children) to become the previous sibling of 'target'. More...
sibling_iterator	move_before (sibling_iterator target, sibling_iterator source)
template<typename IterT >
IterT	move_ontop (IterT target, IterT source)
	Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target'). More...
graph	move_out (iterator)
	Extract the subgraph starting at the indicated node, removing it from the original graph. More...
template<typename IterT >
IterT	move_in (IterT, graph &)
	Inverse of take_out: inserts the given graph as previous sibling of indicated node by a move operation, that is, the given graph becomes empty. Returns iterator to the top node. More...
template<typename IterT >
IterT	move_in_below (IterT, graph &)
	As above, but now make the graph a child of the indicated node. More...
template<typename IterT >
IterT	move_in_as_nth_child (IterT, size_t, graph &)
	As above, but now make the graph the nth child of the indicated node (if possible). More...
void	merge (const sibling_iterator &, const sibling_iterator &, sibling_iterator, const sibling_iterator &, bool duplicate_leaves=false, bool first=false)
	Merge with other graph, creating new branches and leaves only if they are not already present. More...
template<typename ComparePred = std::function<bool(sibling_iterator, sibling_iterator)>, typename ReducePred = std::function<void(sibling_iterator, sibling_iterator)>>
void	reduce (const sibling_iterator &, const sibling_iterator &, std::set< sibling_iterator > &, ComparePred &&=[](sibling_iterator lhs, sibling_iterator rhs) { return(*lhs== *rhs);}, ReducePred &&=[](sibling_iterator lhs, sibling_iterator rhs) { *lhs+= *rhs;})
	Reduce duplicate nodes. More...
template<typename IterT >
bool	equal (const IterT &one, const IterT &two, const IterT &three) const
	Compare two ranges of nodes (compares nodes as well as graph structure). More...
template<typename IterT , typename BinaryPredicate >
bool	equal (const IterT &one, const IterT &two, const IterT &three, BinaryPredicate) const
template<typename IterT >
bool	equal_subgraph (const IterT &one, const IterT &two) const
template<typename IterT , typename BinaryPredicate >
bool	equal_subgraph (const IterT &one, const IterT &two, BinaryPredicate) const
graph	subgraph (sibling_iterator from, sibling_iterator to) const
	Extract a new graph formed by the range of siblings plus all their children. More...
void	subgraph (graph &, sibling_iterator from, sibling_iterator to) const
void	swap (sibling_iterator it)
	Exchange the node (plus subgraph) with its sibling node (do nothing if no sibling present). More...
void	swap (iterator, iterator)
	Exchange two nodes (plus subgraphs). The iterators will remain valid and keep pointing to the same nodes, which now sit at different locations in the graph. More...
size_t	size () const
	Count the total number of nodes. More...
bool	empty () const
	Check if graph is empty. More...
int	max_depth () const
	Determine the maximal depth of the graph. An empty graph has max_depth=-1. More...
int	max_depth (const iterator_base &) const
	Determine the maximal depth of the graph with top node at the given position. More...
unsigned int	number_of_siblings (const iterator_base &) const
	Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1. More...
bool	is_in_subgraph (const iterator_base &position, const iterator_base &begin, const iterator_base &end) const
	Determine whether node at position is in the subgraphs with root in the range. More...
bool	is_valid (const iterator_base &) const
	Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node. More...
unsigned int	index (sibling_iterator it) const
	Determine the index of a node in the range of siblings to which it belongs. More...
sibling_iterator	sibling (const iterator_base &position, unsigned int) const
	Return iterator to the sibling indicated by index. More...
template<typename Archive >
void	serialize (Archive &ar, const unsigned int)

Static Public Member Functions
static sibling_iterator	begin (const iterator_base &)
	Return sibling iterator to the first child of given node. More...
static sibling_iterator	end (const iterator_base &)
	Return sibling end iterator for children of given node. More...
template<typename IterT >
static IterT	parent (IterT)
	Return iterator to the parent of a node. More...
template<typename IterT >
static IterT	previous_sibling (IterT)
	Return iterator to the previous sibling of a node. More...
template<typename IterT >
static IterT	next_sibling (IterT)
	Return iterator to the next sibling of a node. More...
static int	depth (const iterator_base &)
	Compute the depth to the root or to a fixed other iterator. More...
static int	depth (const iterator_base &, const iterator_base &)
static unsigned int	number_of_children (const iterator_base &)
	Count the number of children of node at position. More...
static bool	is_head (const iterator_base &)
	Determine whether the iterator is one of the 'head' nodes at the top level, i.e. has no parent. More...
static sibling_iterator	child (const iterator_base &position, unsigned int)
	Inverse of 'index': return the n-th child of the node at position. More...

Public Attributes
graph_node *	head
graph_node *	feet

Protected Types
using	graph_node = tgraph_node< T >

Detailed Description

template<typename T, typename AllocatorT>
class tim::graph< T, AllocatorT >

Arbitrary Graph / Tree (i.e. binary-tree but not binary). It is unlikely that this class will interacted with directly.

Definition at line 335 of file graph.hpp.

Member Typedef Documentation

const_iterator

template<typename T , typename AllocatorT >

typedef const iterator tim::graph< T, AllocatorT >::const_iterator

Definition at line 439 of file graph.hpp.

difference_type

template<typename T , typename AllocatorT >

typedef iterator::difference_type tim::graph< T, AllocatorT >::difference_type

Definition at line 440 of file graph.hpp.

graph_node

template<typename T , typename AllocatorT >

using tim::graph< T, AllocatorT >::graph_node = tgraph_node<T>

protected

Definition at line 338 of file graph.hpp.

iterator

template<typename T , typename AllocatorT >

typedef pre_order_iterator tim::graph< T, AllocatorT >::iterator

The default iterator types throughout the graph class.

Definition at line 438 of file graph.hpp.

value_type

template<typename T , typename AllocatorT >

using tim::graph< T, AllocatorT >::value_type = T

Value of the data stored at a node.

Definition at line 342 of file graph.hpp.

Constructor & Destructor Documentation

graph() [1/5]

template<typename T , typename AllocatorT >

tim::graph< T, AllocatorT >::graph

Definition at line 775 of file graph.hpp.

{
    m_head_initialize();
}

graph() [2/5]

template<typename T , typename AllocatorT >

tim::graph< T, AllocatorT >::graph

(

const T &

x

)

Definition at line 783 of file graph.hpp.

{
    m_head_initialize();
    set_head(x);
}

References tim::graph< T, AllocatorT >::set_head().

graph() [3/5]

template<typename T , typename AllocatorT >

tim::graph< T, AllocatorT >::graph

(

const iterator_base &

other

)

Definition at line 809 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::iterator_base::begin(), tim::graph< T, AllocatorT >::replace(), and tim::graph< T, AllocatorT >::set_head().

graph() [4/5]

template<typename T , typename AllocatorT >

tim::graph< T, AllocatorT >::graph

(

const graph< T, AllocatorT > &

other

)

Definition at line 885 of file graph.hpp.

{
    // allocator_traits::reserve(2 + other.size());
    m_head_initialize();
    m_copy(other);
}

graph() [5/5]

template<typename T , typename AllocatorT >

tim::graph< T, AllocatorT >::graph ( graph< T, AllocatorT > &&  x )

noexcept

Definition at line 792 of file graph.hpp.

{
    m_head_initialize();
    if(x.head->next_sibling != x.feet)
    {  // move graph if non-empty only
        head->next_sibling                 = x.head->next_sibling;
        feet->prev_sibling                 = x.head->prev_sibling;
        x.head->next_sibling->prev_sibling = head;
        x.feet->prev_sibling->next_sibling = feet;
        x.head->next_sibling               = x.feet;
        x.feet->prev_sibling               = x.head;
    }
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::tgraph_node< T >::next_sibling, and tim::tgraph_node< T >::prev_sibling.

~graph()

template<typename T , typename AllocatorT >

tim::graph< T, AllocatorT >::~graph

Definition at line 819 of file graph.hpp.

{
    clear();
    allocator_traits::destroy(m_alloc, head);
    allocator_traits::destroy(m_alloc, feet);
    allocator_traits::deallocate(m_alloc, head, 1);
    allocator_traits::deallocate(m_alloc, feet, 1);
}

References tim::graph< T, AllocatorT >::clear(), tim::invoke::destroy(), tim::graph< T, AllocatorT >::feet, and tim::graph< T, AllocatorT >::head.

Member Function Documentation

append_child() [1/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::append_child ( IterT  position )

inline

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

Definition at line 1078 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, std::move(tgraph_node<T>{}));
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    tmp->parent = position.node;
    if(position.node->last_child != nullptr)
    {
        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         = nullptr;
    return tmp;
}

References tim::graph< T, AllocatorT >::feet, and tim::graph< T, AllocatorT >::head.

Referenced by tim::graph_data< NodeT >::append_child(), tim::graph< T, AllocatorT >::append_child(), tim::graph_data< NodeT >::append_head(), tim::graph_data< NodeT >::emplace_child(), and tim::graph< T, AllocatorT >::merge().

append_child() [2/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::append_child ( IterT  position, const T &  x  )

inline

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

Definition at line 1140 of file graph.hpp.

{
    // If your program fails here you probably used 'append_child' to add the
    // top node to an empty graph. 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 != feet);
    assert(position.node);
 
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, x);
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    tmp->parent = position.node;
    if(position.node->last_child != nullptr)
    {
        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         = nullptr;
    return tmp;
}

References tim::graph< T, AllocatorT >::feet, and tim::graph< T, AllocatorT >::head.

append_child() [3/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::append_child ( IterT  position, IterT  other_position  )

inline

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

Definition at line 1270 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    IterT aargh = append_child(position, value_type{});
    return move_ontop(aargh, other);
}

References tim::graph< T, AllocatorT >::append_child(), tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, and tim::graph< T, AllocatorT >::move_ontop().

append_child() [4/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::append_child ( IterT  position, T &&  x  )

inline

Definition at line 1175 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, std::forward<T>(x));
 
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    tmp->parent = position.node;
    if(position.node->last_child != nullptr)
    {
        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         = nullptr;
    return tmp;
}

References tim::graph< T, AllocatorT >::feet, and tim::graph< T, AllocatorT >::head.

append_children()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::append_children ( IterT  position, sibling_iterator  from, const sibling_iterator &  to  )

inline

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

Definition at line 1300 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    IterT ret = from;
 
    while(from != to)
    {
        insert_subgraph(position.end(), from);
        ++from;
    }
    return ret;
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, and tim::graph< T, AllocatorT >::insert_subgraph().

begin() [1/2]

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::pre_order_iterator tim::graph< T, AllocatorT >::begin

inline

Return iterator to the beginning of the graph.

Definition at line 997 of file graph.hpp.

{
    return pre_order_iterator(head->next_sibling);
}

References tim::graph< T, AllocatorT >::pre_order_iterator::pre_order_iterator(), tim::graph< T, AllocatorT >::head, and tim::tgraph_node< T >::next_sibling.

Referenced by tim::graph_data< NodeT >::begin(), tim::print_graph(), tim::print_graph_bracketed(), tim::print_graph_hierarchy(), tim::print_subgraph(), tim::print_subgraph_bracketed(), tim::print_subgraph_hierarchy(), and tim::graph< T, AllocatorT >::size().

begin() [2/2]

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::sibling_iterator tim::graph< T, AllocatorT >::begin ( const iterator_base &  pos )

static

Return sibling iterator to the first child of given node.

Definition at line 1015 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::iterator_base::end(), and tim::pos.

child()

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::sibling_iterator tim::graph< T, AllocatorT >::child ( const iterator_base &  position, unsigned int  num  )

static

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

Definition at line 2686 of file graph.hpp.

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

References tim::tgraph_node< T >::first_child, tim::tgraph_node< T >::next_sibling, and tim::graph< T, AllocatorT >::iterator_base::node.

clear()

template<typename T , typename AllocatorT >

void tim::graph< T, AllocatorT >::clear

inline

Erase all nodes of the graph.

Definition at line 923 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::pre_order_iterator::pre_order_iterator(), tim::graph< T, AllocatorT >::erase(), tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, and tim::tgraph_node< T >::next_sibling.

Referenced by tim::graph< T, AllocatorT >::~graph(), tim::graph_data< NodeT >::~graph_data(), and tim::graph_data< NodeT >::clear().

depth() [1/2]

template<typename T , typename AllocatorT >

int tim::graph< T, AllocatorT >::depth ( const iterator_base &  it )

static

Compute the depth to the root or to a fixed other iterator.

Definition at line 2374 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::iterator_base::node, and tim::pos.

Referenced by tim::print_subgraph_hierarchy().

depth() [2/2]

template<typename T , typename AllocatorT >

int tim::graph< T, AllocatorT >::depth ( const iterator_base &  it, const iterator_base &  root  )

static

Definition at line 2391 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::iterator_base::node, and tim::pos.

empty()

template<typename T , typename AllocatorT >

bool tim::graph< T, AllocatorT >::empty

inline

Check if graph is empty.

Definition at line 2363 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::iterator_base::begin(), and tim::graph< T, AllocatorT >::iterator_base::end().

Referenced by tim::print_subgraph(), tim::print_subgraph_bracketed(), and tim::print_subgraph_hierarchy().

end() [1/2]

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::pre_order_iterator tim::graph< T, AllocatorT >::end

inline

Return iterator to the end of the graph.

Definition at line 1006 of file graph.hpp.

{
    return pre_order_iterator(feet);
}

References tim::graph< T, AllocatorT >::pre_order_iterator::pre_order_iterator(), and tim::graph< T, AllocatorT >::feet.

Referenced by tim::graph< T, AllocatorT >::iterator_base::begin(), tim::graph_data< NodeT >::end(), tim::print_graph(), tim::print_graph_bracketed(), tim::print_graph_hierarchy(), tim::print_subgraph(), tim::print_subgraph_bracketed(), tim::print_subgraph_hierarchy(), and tim::graph< T, AllocatorT >::size().

end() [2/2]

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::sibling_iterator tim::graph< T, AllocatorT >::end ( const iterator_base &  pos )

static

Return sibling end iterator for children of given node.

Definition at line 1029 of file graph.hpp.

{
    sibling_iterator ret(nullptr);
    ret.m_parent = pos.node;
    return ret;
}

References tim::graph< T, AllocatorT >::sibling_iterator::m_parent, and tim::pos.

equal() [1/2]

template<typename T , typename AllocatorT >

template<typename IterT >

bool tim::graph< T, AllocatorT >::equal ( const IterT &  one, const IterT &  two, const IterT &  three  ) const

inline

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

Definition at line 2298 of file graph.hpp.

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

Referenced by tim::graph< T, AllocatorT >::equal_subgraph().

equal() [2/2]

template<typename T , typename AllocatorT >

template<typename IterT , typename BinaryPredicate >

bool tim::graph< T, AllocatorT >::equal ( const IterT &  one, const IterT &  two, const IterT &  three, BinaryPredicate  fun  ) const

inline

Definition at line 2321 of file graph.hpp.

{
    pre_order_iterator one(one_);
    pre_order_iterator 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;
}

References tim::graph< T, AllocatorT >::is_valid(), and tim::graph< T, AllocatorT >::iterator_base::number_of_children().

equal_subgraph() [1/2]

template<typename T , typename AllocatorT >

template<typename IterT >

bool tim::graph< T, AllocatorT >::equal_subgraph ( const IterT &  one, const IterT &  two  ) const

inline

Definition at line 2310 of file graph.hpp.

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

equal_subgraph() [2/2]

template<typename T , typename AllocatorT >

template<typename IterT , typename BinaryPredicate >

bool tim::graph< T, AllocatorT >::equal_subgraph ( const IterT &  one, const IterT &  two, BinaryPredicate  fun  ) const

inline

Definition at line 2346 of file graph.hpp.

{
    pre_order_iterator one(one_);
    pre_order_iterator 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);
}

References tim::graph< T, AllocatorT >::iterator_base::begin(), tim::graph< T, AllocatorT >::iterator_base::end(), tim::graph< T, AllocatorT >::equal(), and tim::graph< T, AllocatorT >::iterator_base::number_of_children().

erase()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::erase ( IterT  it )

inline

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

Definition at line 958 of file graph.hpp.

{
    graph_node* cur = it.node;
    assert(cur != head);
    assert(cur != feet);
    if(cur == head || cur == feet)
        return it;
    IterT ret = it;
    // ret.skip_children();
    ++ret;
    erase_children(it);
    if(cur->parent && cur->prev_sibling == nullptr)
    {
        cur->parent->first_child = cur->next_sibling;
    }
    else
    {
        cur->prev_sibling->next_sibling = cur->next_sibling;
    }
 
    if(cur->parent && cur->next_sibling == nullptr)
    {
        cur->parent->last_child = cur->prev_sibling;
    }
    else
    {
        cur->next_sibling->prev_sibling = cur->prev_sibling;
    }
 
    allocator_traits::destroy(m_alloc, cur);
    allocator_traits::deallocate(m_alloc, cur, 1);
    it.node = nullptr;
    return ret;
}

References tim::invoke::destroy(), tim::graph< T, AllocatorT >::erase_children(), tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::tgraph_node< T >::next_sibling, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

Referenced by tim::graph< T, AllocatorT >::clear(), tim::graph< T, AllocatorT >::erase_children(), tim::graph< T, AllocatorT >::move_ontop(), tim::graph< T, AllocatorT >::reduce(), and tim::graph< T, AllocatorT >::replace().

erase_children()

template<typename T , typename AllocatorT >

void tim::graph< T, AllocatorT >::erase_children ( const iterator_base &  it )

inline

Erase all children of the node pointed to by iterator.

Definition at line 936 of file graph.hpp.

{
    if(it.node == nullptr)
        return;
 
    graph_node* cur = it.node->first_child;
 
    if(cur)
    {
        while(cur->next_sibling && cur->next_sibling != feet)
            erase(pre_order_iterator(cur->next_sibling));
    }
 
    it.node->first_child = nullptr;
    it.node->last_child  = nullptr;
}

References tim::graph< T, AllocatorT >::pre_order_iterator::pre_order_iterator(), tim::graph< T, AllocatorT >::erase(), tim::graph< T, AllocatorT >::feet, tim::tgraph_node< T >::first_child, tim::tgraph_node< T >::last_child, tim::tgraph_node< T >::next_sibling, and tim::graph< T, AllocatorT >::iterator_base::node.

Referenced by tim::graph< T, AllocatorT >::erase(), tim::graph< T, AllocatorT >::replace(), and tim::graph_data< NodeT >::reset().

flatten()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::flatten ( IterT  position )

inline

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

Definition at line 1719 of file graph.hpp.

{
    if(position.node->first_child == nullptr)
        return position;
 
    graph_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                = nullptr;
    position.node->last_child                 = nullptr;
 
    return position;
}

References tim::tgraph_node< T >::first_child, tim::tgraph_node< T >::next_sibling, and tim::tgraph_node< T >::parent.

index()

template<typename T , typename AllocatorT >

unsigned int tim::graph< T, AllocatorT >::index ( sibling_iterator  it ) const

inline

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

Definition at line 2628 of file graph.hpp.

{
    graph_node* tmp = it.node;
    if(!tmp)
        return static_cast<unsigned int>(-1);
 
    if(tmp->parent != nullptr)
    {
        tmp = tmp->parent->first_child;
    }
    else
    {
        while(tmp->prev_sibling != nullptr)
            tmp = tmp->prev_sibling;
    }
 
    unsigned int ret = 0;
    while(tmp != it.node)
    {
        ++ret;
        tmp = tmp->next_sibling;
    }
 
    return ret;
}

References tim::tgraph_node< T >::next_sibling, tim::graph< T, AllocatorT >::iterator_base::node, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

Referenced by tim::graph< T, AllocatorT >::reduce().

insert() [1/3]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::insert ( IterT  position, const T &  x  )

inline

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

Definition at line 1367 of file graph.hpp.

{
    if(position.node == nullptr)
    {
        position.node = feet;  // Backward compatibility: when calling insert on
                               // a null node, insert before the feet.
    }
    assert(position.node != head);  // Cannot insert before head.
 
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, x);
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    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 == nullptr)
    {
        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;
}

References tim::graph< T, AllocatorT >::feet, and tim::graph< T, AllocatorT >::head.

Referenced by tim::graph< T, AllocatorT >::insert_subgraph(), tim::graph< T, AllocatorT >::set_head(), and tim::graph< T, AllocatorT >::wrap().

insert() [2/3]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::insert ( IterT  position, T &&  x  )

inline

Definition at line 1401 of file graph.hpp.

{
    if(position.node == nullptr)
    {
        position.node = feet;  // Backward compatibility: when calling insert on
                               // a null node, insert before the feet.
    }
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, std::forward<T>(x));
 
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    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 == nullptr)
    {
        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;
}

References tim::graph< T, AllocatorT >::feet.

insert() [3/3]

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::sibling_iterator tim::graph< T, AllocatorT >::insert ( sibling_iterator  position, const T &  x  )

inline

Specialisation of previous member.

Definition at line 1433 of file graph.hpp.

{
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, x);
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    tmp->next_sibling = position.node;
    if(position.node == nullptr)
    {  // iterator points to end of a subgraph
        tmp->parent             = position.m_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 == nullptr)
    {
        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;
}

insert_after() [1/2]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::insert_after ( IterT  position, const T &  x  )

inline

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

Definition at line 1469 of file graph.hpp.

{
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, x);
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    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 == nullptr)
    {
        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;
}

Referenced by tim::graph_data< NodeT >::add_dummy(), and tim::graph< T, AllocatorT >::insert_subgraph_after().

insert_after() [2/2]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::insert_after ( IterT  position, T &&  x  )

inline

Definition at line 1498 of file graph.hpp.

{
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, std::forward<T>(x));
 
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    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 == nullptr)
    {
        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;
}

insert_subgraph()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::insert_subgraph ( IterT  position, const iterator_base &  subgraph  )

inline

Insert node (with children) pointed to by subgraph as previous sibling of node pointed to by position. Does not change the subgraph itself (use move_in or move_in_below for that).

Definition at line 1528 of file graph.hpp.

{
    // insert dummy
    IterT it = insert(position, value_type{});
    // replace dummy with subgraph
    return replace(it, _subgraph);
}

References tim::graph< T, AllocatorT >::insert(), and tim::graph< T, AllocatorT >::replace().

Referenced by tim::graph< T, AllocatorT >::append_children(), tim::graph< T, AllocatorT >::merge(), tim::graph< T, AllocatorT >::prepend_children(), and tim::graph< T, AllocatorT >::replace().

insert_subgraph_after()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::insert_subgraph_after ( IterT  position, const iterator_base &  subgraph  )

inline

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

Definition at line 1541 of file graph.hpp.

{
    // insert dummy
    IterT it = insert_after(position, value_type{});
    // replace dummy with subgraph
    return replace(it, _subgraph);
}

References tim::graph< T, AllocatorT >::insert_after(), and tim::graph< T, AllocatorT >::replace().

Referenced by tim::graph< T, AllocatorT >::reduce().

is_head()

template<typename T , typename AllocatorT >

bool tim::graph< T, AllocatorT >::is_head ( const iterator_base &  it )

static

Determine whether the iterator is one of the 'head' nodes at the top level, i.e. has no parent.

Definition at line 2617 of file graph.hpp.

{
    if(it.node->parent == nullptr)
        return true;
    return false;
}

References tim::graph< T, AllocatorT >::iterator_base::node, and tim::tgraph_node< T >::parent.

Referenced by tim::graph_data< NodeT >::pop_graph().

is_in_subgraph()

template<typename T , typename AllocatorT >

bool tim::graph< T, AllocatorT >::is_in_subgraph ( const iterator_base &  position, const iterator_base &  begin, const iterator_base &  end  ) const

inline

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

is_valid()

template<typename T , typename AllocatorT >

bool tim::graph< T, AllocatorT >::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 2602 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, and tim::graph< T, AllocatorT >::iterator_base::node.

Referenced by tim::graph< T, AllocatorT >::equal(), and tim::graph< T, AllocatorT >::reduce().

max_depth() [1/2]

template<typename T , typename AllocatorT >

int tim::graph< T, AllocatorT >::max_depth

inline

Determine the maximal depth of the graph. An empty graph has max_depth=-1.

Definition at line 2408 of file graph.hpp.

{
    int maxd = -1;
    for(graph_node* it = head->next_sibling; it != feet; it = it->next_sibling)
        maxd = std::max(maxd, max_depth(it));
 
    return maxd;
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, and tim::tgraph_node< T >::next_sibling.

max_depth() [2/2]

template<typename T , typename AllocatorT >

int tim::graph< T, AllocatorT >::max_depth ( const iterator_base &  pos ) const

inline

Determine the maximal depth of the graph with top node at the given position.

Definition at line 2421 of file graph.hpp.

{
    graph_node* tmp = pos.node;
 
    if(tmp == nullptr || tmp == head || tmp == feet)
        return -1;
 
    int curdepth = 0;
    int maxdepth = 0;
    while(true)
    {  // try to walk the bottom of the graph
        while(tmp->first_child == nullptr)
        {
            if(tmp == pos.node)
                return maxdepth;
            if(tmp->next_sibling == nullptr)
            {
                // try to walk up and then right again
                do
                {
                    tmp = tmp->parent;
                    if(tmp == nullptr)
                        return maxdepth;
                    --curdepth;
                } while(tmp->next_sibling == nullptr);
            }
            if(tmp == pos.node)
                return maxdepth;
            tmp = tmp->next_sibling;
        }
        tmp = tmp->first_child;
        ++curdepth;
        maxdepth = std::max(curdepth, maxdepth);
    }
}

References tim::graph< T, AllocatorT >::feet, tim::tgraph_node< T >::first_child, tim::graph< T, AllocatorT >::head, tim::tgraph_node< T >::next_sibling, tim::tgraph_node< T >::parent, and tim::pos.

merge()

template<typename T , typename AllocatorT >

void tim::graph< T, AllocatorT >::merge ( const sibling_iterator &  to1, const sibling_iterator &  to2, sibling_iterator  from1, const sibling_iterator &  from2, bool  duplicate_leaves = false, bool  first = false  )

inline

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

Definition at line 2172 of file graph.hpp.

{
    while(from1 != from2)
    {
        sibling_iterator    fnd;
        auto                nsiblings = number_of_siblings(to1);
        decltype(nsiblings) count     = nullptr;
        for(sibling_iterator itr = to1; itr != to2; ++itr, ++count)
        {
            if(itr && from1 && *itr == *from1)
            {
                fnd = itr;
                break;
            }
            if(count > nsiblings)
            {
                fnd = to2;
                break;
            }
        }
        // auto fnd = std::find(to1, to2, *from1);
        if(fnd != to2)  // element found
        {
            if(from1.begin() == from1.end())  // full depth reached
            {
                if(duplicate_leaves)
                    append_child(parent(to1), (*from1));
            }
            else  // descend further
            {
                if(!first)
                    *fnd += *from1;
                if(from1 != from2)
                {
                    merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(),
                          duplicate_leaves);
                }
            }
        }
        else
        {  // element missing
            insert_subgraph(to2, from1);
        }
        do
        {
            ++from1;
        } while(!from1 && from1 != from2);
    }
}

References tim::graph< T, AllocatorT >::append_child(), tim::graph< T, AllocatorT >::iterator_base::begin(), tim::graph< T, AllocatorT >::iterator_base::end(), tim::graph< T, AllocatorT >::insert_subgraph(), tim::graph< T, AllocatorT >::number_of_siblings(), and tim::graph< T, AllocatorT >::parent().

move_after()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::move_after ( IterT  target, IterT  source  )

inline

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

Definition at line 1856 of file graph.hpp.

{
    graph_node* dst = target.node;
    graph_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 graph
    if(src->prev_sibling != nullptr)
    {
        src->prev_sibling->next_sibling = src->next_sibling;
    }
    else
    {
        src->parent->first_child = src->next_sibling;
    }
    if(src->next_sibling != nullptr)
    {
        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 != nullptr)
    {
        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;
}

References tim::tgraph_node< T >::next_sibling, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

move_before() [1/2]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::move_before ( IterT  target, IterT  source  )

inline

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

Definition at line 1910 of file graph.hpp.

{
    graph_node* dst = target.node;
    graph_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 graph
    if(src->prev_sibling != nullptr)
    {
        src->prev_sibling->next_sibling = src->next_sibling;
    }
    else
    {
        src->parent->first_child = src->next_sibling;
    }
    if(src->next_sibling != nullptr)
    {
        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 != nullptr)
    {
        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;
}

References tim::tgraph_node< T >::next_sibling, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

move_before() [2/2]

template<typename T , typename AllocatorT >

sibling_iterator tim::graph< T, AllocatorT >::move_before ( sibling_iterator  target, sibling_iterator  source  )

inline

move_in()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::move_in ( IterT  loc, graph< T, AllocatorT > &  other  )

inline

Inverse of take_out: inserts the given graph as previous sibling of indicated node by a move operation, that is, the given graph becomes empty. Returns iterator to the top node.

Definition at line 2059 of file graph.hpp.

{
    if(other.head->next_sibling == other.feet)
        return loc;  // other graph is empty
 
    graph_node* other_first_head = other.head->next_sibling;
    graph_node* other_last_head  = other.feet->prev_sibling;
 
    sibling_iterator prev(loc);
    --prev;
 
    prev.node->next_sibling        = other_first_head;
    loc.node->prev_sibling         = other_last_head;
    other_first_head->prev_sibling = prev.node;
    other_last_head->next_sibling  = loc.node;
 
    // Adjust parent pointers.
    graph_node* walk = other_first_head;
    while(true)
    {
        walk->parent = loc.node->parent;
        if(walk == other_last_head)
            break;
        walk = walk->next_sibling;
    }
 
    // Close other graph.
    other.head->next_sibling = other.feet;
    other.feet->prev_sibling = other.head;
 
    return other_first_head;
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::tgraph_node< T >::next_sibling, tim::graph< T, AllocatorT >::iterator_base::node, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

move_in_as_nth_child()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::move_in_as_nth_child ( IterT  loc, size_t  n, graph< T, AllocatorT > &  other  )

inline

As above, but now make the graph the nth child of the indicated node (if possible).

Definition at line 2097 of file graph.hpp.

{
    if(other.head->next_sibling == other.feet)
        return loc;  // other graph is empty
 
    graph_node* other_first_head = other.head->next_sibling;
    graph_node* other_last_head  = other.feet->prev_sibling;
 
    if(n == 0)
    {
        if(loc.node->first_child == nullptr)
        {
            loc.node->first_child          = other_first_head;
            loc.node->last_child           = other_last_head;
            other_last_head->next_sibling  = nullptr;
            other_first_head->prev_sibling = nullptr;
        }
        else
        {
            loc.node->first_child->prev_sibling = other_last_head;
            other_last_head->next_sibling       = loc.node->first_child;
            loc.node->first_child               = other_first_head;
            other_first_head->prev_sibling      = nullptr;
        }
    }
    else
    {
        --n;
        graph_node* walk = loc.node->first_child;
        while(true)
        {
            if(walk == nullptr)
            {
                throw std::range_error(
                    "graph: move_in_as_nth_child position out of range");
            }
            if(n == 0)
                break;
            --n;
            walk = walk->next_sibling;
        }
        if(walk->next_sibling == nullptr)
        {
            loc.node->last_child = other_last_head;
        }
        else
        {
            walk->next_sibling->prev_sibling = other_last_head;
        }
        other_last_head->next_sibling  = walk->next_sibling;
        walk->next_sibling             = other_first_head;
        other_first_head->prev_sibling = walk;
    }
 
    // Adjust parent pointers.
    graph_node* walk = other_first_head;
    while(true)
    {
        walk->parent = loc.node;
        if(walk == other_last_head)
            break;
        walk = walk->next_sibling;
    }
 
    // Close other graph.
    other.head->next_sibling = other.feet;
    other.feet->prev_sibling = other.head;
 
    return other_first_head;
}

References tim::graph< T, AllocatorT >::feet, tim::tgraph_node< T >::first_child, tim::graph< T, AllocatorT >::head, tim::tgraph_node< T >::last_child, tim::tgraph_node< T >::next_sibling, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

move_in_below()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::move_in_below ( IterT  , graph< T, AllocatorT > &    )

inline

As above, but now make the graph a child of the indicated node.

move_ontop()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::move_ontop ( IterT  target, IterT  source  )

inline

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

Definition at line 1964 of file graph.hpp.

{
    graph_node* dst = target.node;
    graph_node* src = source.node;
    assert(dst);
    assert(src);
 
    if(dst == src)
        return source;
 
    //  if(dst==src->prev_sibling) {
    //
    //      }
 
    // remember connection points
    graph_node* b_prev_sibling = dst->prev_sibling;
    graph_node* b_next_sibling = dst->next_sibling;
    graph_node* b_parent       = dst->parent;
 
    // remove target
    erase(target);
 
    // take src out of the graph
    if(src->prev_sibling != nullptr)
    {
        src->prev_sibling->next_sibling = src->next_sibling;
    }
    else
    {
        src->parent->first_child = src->next_sibling;
    }
    if(src->next_sibling != nullptr)
    {
        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 != nullptr)
    {
        b_prev_sibling->next_sibling = src;
    }
    else
    {
        b_parent->first_child = src;
    }
    if(b_next_sibling != nullptr)
    {
        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;
}

References tim::graph< T, AllocatorT >::erase(), tim::tgraph_node< T >::first_child, tim::tgraph_node< T >::last_child, tim::tgraph_node< T >::next_sibling, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

Referenced by tim::graph< T, AllocatorT >::append_child(), and tim::graph< T, AllocatorT >::prepend_child().

move_out()

template<typename T , typename AllocatorT >

graph< T, AllocatorT > tim::graph< T, AllocatorT >::move_out ( iterator  source )

inline

Extract the subgraph starting at the indicated node, removing it from the original graph.

Definition at line 2031 of file graph.hpp.

{
    graph ret;
 
    // Move source node into the 'ret' graph.
    ret.head->next_sibling = source.node;
    ret.feet->prev_sibling = source.node;
    source.node->parent    = nullptr;
 
    // Close the links in the current graph.
    if(source.node->prev_sibling != nullptr)
        source.node->prev_sibling->next_sibling = source.node->next_sibling;
 
    if(source.node->next_sibling != nullptr)
        source.node->next_sibling->prev_sibling = source.node->prev_sibling;
 
    // Fix source prev/next links.
    source.node->prev_sibling = ret.head;
    source.node->next_sibling = ret.feet;
 
    return ret;  // A good compiler will move this, not copy.
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::tgraph_node< T >::next_sibling, tim::graph< T, AllocatorT >::iterator_base::node, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

next_sibling()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::next_sibling ( IterT  position )

static

Return iterator to the next sibling of a node.

Definition at line 1065 of file graph.hpp.

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

number_of_children()

template<typename T , typename AllocatorT >

unsigned int tim::graph< T, AllocatorT >::number_of_children ( const iterator_base &  it )

static

Count the number of children of node at position.

Definition at line 2461 of file graph.hpp.

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

References tim::tgraph_node< T >::first_child, tim::graph< T, AllocatorT >::iterator_base::node, and tim::pos.

Referenced by tim::print_subgraph(), tim::print_subgraph_bracketed(), and tim::print_subgraph_hierarchy().

number_of_siblings()

template<typename T , typename AllocatorT >

unsigned int tim::graph< T, AllocatorT >::number_of_siblings ( const iterator_base &  it ) const

inline

Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1.

Definition at line 2477 of file graph.hpp.

{
    graph_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;
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::graph< T, AllocatorT >::iterator_base::node, and tim::pos.

Referenced by tim::graph< T, AllocatorT >::merge(), tim::print_graph(), tim::print_graph_bracketed(), tim::print_graph_hierarchy(), tim::print_subgraph(), tim::print_subgraph_bracketed(), tim::print_subgraph_hierarchy(), and tim::graph< T, AllocatorT >::reduce().

operator=() [1/2]

template<typename T , typename AllocatorT >

graph< T, AllocatorT > & tim::graph< T, AllocatorT >::operator=

(

const graph< T, AllocatorT > &

other

)

Definition at line 857 of file graph.hpp.

{
    if(this != &other)
        m_copy(other);
    return *this;
}

operator=() [2/2]

template<typename T , typename AllocatorT >

graph< T, AllocatorT > & tim::graph< T, AllocatorT >::operator= ( graph< T, AllocatorT > &&  x )

noexcept

Definition at line 868 of file graph.hpp.

{
    if(this != &x)
    {
        head->next_sibling                 = x.head->next_sibling;
        feet->prev_sibling                 = x.head->prev_sibling;
        x.head->next_sibling->prev_sibling = head;
        x.feet->prev_sibling->next_sibling = feet;
        x.head->next_sibling               = x.feet;
        x.feet->prev_sibling               = x.head;
    }
    return *this;
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::tgraph_node< T >::next_sibling, and tim::tgraph_node< T >::prev_sibling.

parent()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::parent ( IterT  position )

static

Return iterator to the parent of a node.

Definition at line 1041 of file graph.hpp.

{
    assert(position.node != nullptr);
    return IterT(position.node->parent);
}

Referenced by tim::graph< T, AllocatorT >::merge().

prepend_child() [1/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::prepend_child ( IterT  position )

inline

Definition at line 1109 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, std::move(tgraph_node<T>{}));
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    tmp->parent = position.node;
    if(position.node->first_child != nullptr)
    {
        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         = nullptr;
    return tmp;
}

References tim::graph< T, AllocatorT >::feet, and tim::graph< T, AllocatorT >::head.

Referenced by tim::graph< T, AllocatorT >::prepend_child().

prepend_child() [2/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::prepend_child ( IterT  position, const T &  x  )

inline

Definition at line 1207 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, x);
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    tmp->parent = position.node;
    if(position.node->first_child != nullptr)
    {
        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          = nullptr;
    return tmp;
}

References tim::graph< T, AllocatorT >::feet, and tim::graph< T, AllocatorT >::head.

prepend_child() [3/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::prepend_child ( IterT  position, IterT  other_position  )

inline

Definition at line 1285 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    IterT aargh = prepend_child(position, value_type{});
    return move_ontop(aargh, other);
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::graph< T, AllocatorT >::move_ontop(), and tim::graph< T, AllocatorT >::prepend_child().

prepend_child() [4/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::prepend_child ( IterT  position, T &&  x  )

inline

Definition at line 1238 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, std::forward<T>(x));
 
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
 
    tmp->parent = position.node;
    if(position.node->first_child != nullptr)
    {
        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          = nullptr;
    return tmp;
}

References tim::graph< T, AllocatorT >::feet, and tim::graph< T, AllocatorT >::head.

prepend_children()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::prepend_children ( IterT  position, sibling_iterator  from, sibling_iterator  to  )

inline

Definition at line 1322 of file graph.hpp.

{
    assert(position.node != head);
    assert(position.node != feet);
    assert(position.node);
 
    if(from == to)
        return from;  // should return end of graph?
 
    IterT ret;
    do
    {
        --to;
        ret = insert_subgraph(position.begin(), to);
    } while(to != from);
 
    return ret;
}

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, and tim::graph< T, AllocatorT >::insert_subgraph().

previous_sibling()

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::previous_sibling ( IterT  position )

static

Return iterator to the previous sibling of a node.

Definition at line 1052 of file graph.hpp.

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

reduce()

template<typename T , typename AllocatorT >

template<typename ComparePred , typename ReducePred >

void tim::graph< T, AllocatorT >::reduce ( const sibling_iterator &  lhs, const sibling_iterator &  , std::set< sibling_iterator > &  _erase, ComparePred &&  _compare = [](sibling_iterator lhs,                           sibling_iterator rhs) { return (*lhs == *rhs); }, ReducePred &&  _reduce = [](sibling_iterator lhs, sibling_iterator rhs) { *lhs += *rhs; }  )

inline

Reduce duplicate nodes.

Definition at line 2229 of file graph.hpp.

{
    if(!is_valid(lhs))
        return;
 
    for(pre_order_iterator litr = lhs; litr != feet; ++litr)
    {
        if(!litr)
            continue;
 
        uint32_t nsiblings = number_of_siblings(litr);
        if(nsiblings < 2)
            continue;
 
        uint32_t idx = index(litr);
        for(uint32_t i = 0; i < nsiblings; ++i)
        {
            if(i == idx)
                continue;
 
            sibling_iterator ritr = sibling(litr, i);
 
            if(!ritr)
                continue;
 
            // skip if same iterator
            if(litr.node == ritr.node)
                continue;
 
            if(_erase.find(ritr) != _erase.end())
                continue;
 
            if(_compare(litr, ritr))
            {
                pre_order_iterator pritr(ritr);
                // printf("\n");
                // pre_order_iterator critr = pritr.begin();
                // auto aitr = append_child(litr, critr);
                auto aitr = insert_subgraph_after(litr, pritr);
                reduce(aitr.begin(), feet, _erase, _compare, _reduce);
                // insert_subgraph_after(litr, pritr);
                _erase.insert(ritr);
                reduce(litr.begin(), feet, _erase, _compare, _reduce);
                _reduce(litr, ritr);
                // this->erase(ritr);
 
                // break;
            }
        }
 
        for(auto& itr : _erase)
            this->erase(itr);
 
        if(_erase.size() > 0)
        {
            _erase.clear();
            break;
        }
        // reduce(litr.begin(), feet, _erase, _compare, _reduce);
    }
}

References tim::graph< T, AllocatorT >::erase(), tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::index(), tim::graph< T, AllocatorT >::insert_subgraph_after(), tim::graph< T, AllocatorT >::is_valid(), tim::graph< T, AllocatorT >::iterator_base::node, tim::graph< T, AllocatorT >::number_of_siblings(), and tim::graph< T, AllocatorT >::sibling().

reparent() [1/2]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::reparent ( IterT  position, IterT  from  )

inline

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

Definition at line 1815 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::iterator_base::end(), and tim::graph< T, AllocatorT >::reparent().

reparent() [2/2]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::reparent ( IterT  position, sibling_iterator  begin, const sibling_iterator &  end  )

inline

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

Definition at line 1752 of file graph.hpp.

{
    graph_node* first = _begin.node;
    graph_node* last  = first;
 
    assert(first != position.node);
 
    if(_begin == _end)
        return _begin;
    // determine last node
    while((++_begin) != _end)
    {
        last = last->next_sibling;
    }
    // move subgraph
    if(first->prev_sibling == nullptr)
    {
        first->parent->first_child = last->next_sibling;
    }
    else
    {
        first->prev_sibling->next_sibling = last->next_sibling;
    }
    if(last->next_sibling == nullptr)
    {
        last->parent->last_child = first->prev_sibling;
    }
    else
    {
        last->next_sibling->prev_sibling = first->prev_sibling;
    }
    if(position.node->first_child == nullptr)
    {
        position.node->first_child = first;
        position.node->last_child  = last;
        first->prev_sibling        = nullptr;
    }
    else
    {
        position.node->last_child->next_sibling = first;
        first->prev_sibling                     = position.node->last_child;
        position.node->last_child               = last;
    }
    last->next_sibling = nullptr;
 
    graph_node* pos = first;
    for(;;)
    {
        pos->parent = position.node;
        if(pos == last)
            break;
        pos = pos->next_sibling;
    }
 
    return first;
}

References tim::tgraph_node< T >::last_child, tim::tgraph_node< T >::next_sibling, tim::graph< T, AllocatorT >::iterator_base::node, tim::tgraph_node< T >::parent, tim::pos, and tim::tgraph_node< T >::prev_sibling.

Referenced by tim::graph< T, AllocatorT >::reparent(), and tim::graph< T, AllocatorT >::wrap().

replace() [1/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::replace ( IterT  position, const iterator_base &  from  )

inline

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

Definition at line 1592 of file graph.hpp.

{
    assert(position.node != head);
    graph_node* current_from = from.node;
    graph_node* start_from   = from.node;
    graph_node* current_to   = position.node;
 
    // replace the node at position with head of the replacement graph at from
    //  std::cout << "warning!" << position.node << std::endl;
    erase_children(position);
    //  std::cout << "no warning!" << std::endl;
    graph_node* tmp = allocator_traits::allocate(m_alloc, 1, nullptr);
    allocator_traits::construct(m_alloc, tmp, (*from));
    tmp->first_child = nullptr;
    tmp->last_child  = nullptr;
    if(current_to->prev_sibling == nullptr)
    {
        if(current_to->parent != nullptr)
            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 == nullptr)
    {
        if(current_to->parent != nullptr)
            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;
    allocator_traits::destroy(m_alloc, current_to);
    allocator_traits::deallocate(m_alloc, current_to, 1);
    current_to = tmp;
 
    // only at this stage can we fix 'last'
    graph_node* last = from.node->next_sibling;
 
    pre_order_iterator toit = tmp;
    // copy all children
    do
    {
        assert(current_from != nullptr);
        if(current_from->first_child != nullptr)
        {
            current_from = current_from->first_child;
            toit         = append_child(toit, current_from->data);
        }
        else
        {
            while(current_from->next_sibling == nullptr && current_from != start_from)
            {
                current_from = current_from->parent;
                toit         = parent(toit);
                assert(current_from != nullptr);
            }
            current_from = current_from->next_sibling;
            if(current_from != last && current_from)
            {
                toit = append_child(parent(toit), current_from->data);
            }
        }
    } while(current_from != last && current_from);
 
    return current_to;
}

References tim::graph< T, AllocatorT >::erase_children(), tim::graph< T, AllocatorT >::head, and tim::graph< T, AllocatorT >::iterator_base::node.

replace() [2/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::replace ( IterT  position, const T &  x  )

inline

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

Definition at line 1568 of file graph.hpp.

{
    allocator_traits::destroy(m_alloc, position.node);
    allocator_traits::construct(m_alloc, position.node, x);
    return position;
}

References tim::invoke::destroy().

Referenced by tim::graph< T, AllocatorT >::graph(), tim::graph< T, AllocatorT >::insert_subgraph(), and tim::graph< T, AllocatorT >::insert_subgraph_after().

replace() [3/4]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::replace ( IterT  position, T &&  x  )

inline

Definition at line 1580 of file graph.hpp.

{
    allocator_traits::destroy(m_alloc, position.node);
    allocator_traits::construct(m_alloc, position.node, std::forward<T>(x));
    return position;
}

References tim::invoke::destroy().

replace() [4/4]

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::sibling_iterator tim::graph< T, AllocatorT >::replace ( sibling_iterator  orig_begin, const sibling_iterator &  orig_end, sibling_iterator  new_begin, const 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 1668 of file graph.hpp.

{
    graph_node* orig_first = orig_begin.node;
    graph_node* new_first  = new_begin.node;
    graph_node* orig_last  = orig_first;
    while((++orig_begin) != orig_end)
        orig_last = orig_last->next_sibling;
    graph_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(true)
    {
        pre_order_iterator tt = insert_subgraph(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;
    graph_node* next = orig_first;
    while(true)
    {
        if(next == orig_last)
            last = true;
        next = next->next_sibling;
        erase((pre_order_iterator) orig_first);
        if(last)
            break;
        orig_first = next;
    }
    return ret;
}

References tim::graph< T, AllocatorT >::pre_order_iterator::pre_order_iterator(), tim::graph< T, AllocatorT >::erase(), tim::graph< T, AllocatorT >::insert_subgraph(), tim::tgraph_node< T >::next_sibling, and tim::graph< T, AllocatorT >::iterator_base::node.

serialize()

template<typename T , typename AllocatorT >

template<typename Archive >

void tim::graph< T, AllocatorT >::serialize ( Archive &  ar, const unsigned int    )

inline

Definition at line 755 of file graph.hpp.

    {
        for(auto itr = begin(); itr != end(); ++itr)
            ar(cereal::make_nvp("node", *itr));
    }

References tim::graph< T, AllocatorT >::iterator_base::begin(), and tim::graph< T, AllocatorT >::iterator_base::end().

set_head() [1/2]

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::pre_order_iterator tim::graph< T, AllocatorT >::set_head ( const T &  x )

inline

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

Definition at line 1346 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::graph< T, AllocatorT >::insert(), and tim::tgraph_node< T >::next_sibling.

Referenced by tim::graph< T, AllocatorT >::graph(), and tim::graph_data< NodeT >::graph_data().

set_head() [2/2]

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::pre_order_iterator tim::graph< T, AllocatorT >::set_head ( T &&  x )

inline

Definition at line 1356 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::feet, tim::graph< T, AllocatorT >::head, tim::graph< T, AllocatorT >::insert(), and tim::tgraph_node< T >::next_sibling.

sibling()

template<typename T , typename AllocatorT >

graph< T, AllocatorT >::sibling_iterator tim::graph< T, AllocatorT >::sibling ( const iterator_base &  position, unsigned int  num  ) const

inline

Return iterator to the sibling indicated by index.

Definition at line 2658 of file graph.hpp.

{
    graph_node* tmp = it.node;
    if(!tmp)
        return sibling_iterator(nullptr);
 
    if(tmp->parent != nullptr)
    {
        tmp = tmp->parent->first_child;
    }
    else
    {
        while(tmp->prev_sibling != nullptr)
            tmp = tmp->prev_sibling;
    }
 
    while((num--) != 0u)
    {
        assert(tmp != nullptr);
        tmp = tmp->next_sibling;
    }
    return tmp;
}

References tim::tgraph_node< T >::next_sibling, tim::graph< T, AllocatorT >::iterator_base::node, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

Referenced by tim::graph< T, AllocatorT >::reduce().

size()

template<typename T , typename AllocatorT >

size_t tim::graph< T, AllocatorT >::size

inline

Count the total number of nodes.

Definition at line 3157 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::begin(), and tim::graph< T, AllocatorT >::end().

subgraph() [1/2]

template<typename T , typename AllocatorT >

void tim::graph< T, AllocatorT >::subgraph ( graph< T, AllocatorT > &  , sibling_iterator  from, sibling_iterator  to  ) const

inline

subgraph() [2/2]

template<typename T , typename AllocatorT >

graph tim::graph< T, AllocatorT >::subgraph ( sibling_iterator  from, sibling_iterator  to  ) const

inline

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

swap() [1/2]

template<typename T , typename AllocatorT >

void tim::graph< T, AllocatorT >::swap ( iterator  one, iterator  two  )

inline

Exchange two nodes (plus subgraphs). The iterators will remain valid and keep pointing to the same nodes, which now sit at different locations in the graph.

Definition at line 2535 of file graph.hpp.

{
    // 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
    {
        graph_node* nxt1 = one.node->next_sibling;
        graph_node* nxt2 = two.node->next_sibling;
        graph_node* pre1 = one.node->prev_sibling;
        graph_node* pre2 = two.node->prev_sibling;
        graph_node* par1 = one.node->parent;
        graph_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;
        }
    }
}

References tim::tgraph_node< T >::first_child, tim::tgraph_node< T >::last_child, tim::tgraph_node< T >::next_sibling, tim::graph< T, AllocatorT >::iterator_base::node, tim::tgraph_node< T >::parent, tim::tgraph_node< T >::prev_sibling, and tim::graph< T, AllocatorT >::swap().

swap() [2/2]

template<typename T , typename AllocatorT >

void tim::graph< T, AllocatorT >::swap ( sibling_iterator  it )

inline

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

Definition at line 2502 of file graph.hpp.

{
    graph_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;
        graph_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;
    }
}

References tim::tgraph_node< T >::next_sibling, tim::graph< T, AllocatorT >::iterator_base::node, tim::tgraph_node< T >::parent, and tim::tgraph_node< T >::prev_sibling.

Referenced by tim::graph< T, AllocatorT >::swap().

wrap() [1/2]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::wrap ( IterT  from, IterT  to, const T &  x  )

inline

Replace the range of sibling nodes (plus subgraphs), making these children of the new node.

Definition at line 1843 of file graph.hpp.

{
    assert(from.node != nullptr);
    IterT ret = insert(from, x);
    reparent(ret, from, to);
    return ret;
}

References tim::graph< T, AllocatorT >::insert(), and tim::graph< T, AllocatorT >::reparent().

wrap() [2/2]

template<typename T , typename AllocatorT >

template<typename IterT >

IterT tim::graph< T, AllocatorT >::wrap ( IterT  position, const T &  x  )

inline

Replace node with a new node, making the old node (plus subgraph) a child of the new node.

Definition at line 1827 of file graph.hpp.

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

References tim::graph< T, AllocatorT >::insert(), and tim::graph< T, AllocatorT >::reparent().

Member Data Documentation

feet

template<typename T , typename AllocatorT >

graph_node* tim::graph< T, AllocatorT >::feet

Definition at line 750 of file graph.hpp.

Referenced by tim::graph< T, AllocatorT >::graph(), tim::graph< T, AllocatorT >::~graph(), tim::graph< T, AllocatorT >::append_child(), tim::graph< T, AllocatorT >::append_children(), tim::graph< T, AllocatorT >::clear(), tim::graph< T, AllocatorT >::end(), tim::graph< T, AllocatorT >::erase(), tim::graph< T, AllocatorT >::erase_children(), tim::graph< T, AllocatorT >::insert(), tim::graph< T, AllocatorT >::is_valid(), tim::graph< T, AllocatorT >::max_depth(), tim::graph< T, AllocatorT >::move_in(), tim::graph< T, AllocatorT >::move_in_as_nth_child(), tim::graph< T, AllocatorT >::move_out(), tim::graph< T, AllocatorT >::number_of_siblings(), tim::graph< T, AllocatorT >::operator=(), tim::graph< T, AllocatorT >::prepend_child(), tim::graph< T, AllocatorT >::prepend_children(), tim::graph< T, AllocatorT >::reduce(), and tim::graph< T, AllocatorT >::set_head().

head

template<typename T , typename AllocatorT >

graph_node* tim::graph< T, AllocatorT >::head

Definition at line 749 of file graph.hpp.

Referenced by tim::graph< T, AllocatorT >::graph(), tim::graph< T, AllocatorT >::~graph(), tim::graph< T, AllocatorT >::append_child(), tim::graph< T, AllocatorT >::append_children(), tim::graph< T, AllocatorT >::begin(), tim::graph< T, AllocatorT >::clear(), tim::graph< T, AllocatorT >::erase(), tim::graph< T, AllocatorT >::insert(), tim::graph< T, AllocatorT >::is_valid(), tim::graph< T, AllocatorT >::max_depth(), tim::graph< T, AllocatorT >::move_in(), tim::graph< T, AllocatorT >::move_in_as_nth_child(), tim::graph< T, AllocatorT >::move_out(), tim::graph< T, AllocatorT >::number_of_siblings(), tim::graph< T, AllocatorT >::operator=(), tim::graph< T, AllocatorT >::prepend_child(), tim::graph< T, AllocatorT >::prepend_children(), tim::graph< T, AllocatorT >::replace(), and tim::graph< T, AllocatorT >::set_head().

---

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

• timemory/storage/graph.hpp