32#include "timemory/tpls/cereal/cereal.hpp"
67#if defined(TIMEMORY_WINDOWS) || defined(TIMEMORY_NVCC_COMPILER)
87 template <
typename Archive>
90 ar(cereal::make_nvp(
"data",
data));
105: data(std::move(val))
113template <
typename T,
typename AllocatorT>
159 operator
bool()
const {
return node !=
nullptr; }
162 T* operator->()
const;
168 void skip_children();
169 void skip_children(
bool skip);
173 TIMEMORY_NODISCARD sibling_iterator
begin()
const;
174 TIMEMORY_NODISCARD sibling_iterator
end()
const;
182 bool m_skip_current_children =
false;
239 bool operator==(const sibling_iterator&) const;
240 bool operator!=(const sibling_iterator&) const;
241 sibling_iterator& operator++();
242 sibling_iterator& operator--();
243 sibling_iterator operator++(
int);
244 sibling_iterator operator--(
int);
245 sibling_iterator& operator+=(
unsigned int);
246 sibling_iterator& operator-=(
unsigned int);
247 sibling_iterator operator+(
unsigned int);
324 const sibling_iterator& to);
327 sibling_iterator to);
335 inline IterT
insert(IterT position, const T& x);
337 inline IterT
insert(IterT position, T&& x);
340 inline sibling_iterator
insert(sibling_iterator position, const T& x);
362 inline IterT
replace(IterT position, const T& x);
374 inline sibling_iterator
replace(sibling_iterator orig_begin,
375 const sibling_iterator& orig_end,
376 sibling_iterator new_begin,
377 const sibling_iterator& new_end);
387 const sibling_iterator&
end);
395 inline IterT
wrap(IterT position, const T& x);
400 inline IterT
wrap(IterT from, IterT to, const T& x);
439 inline
void merge(const sibling_iterator&, const sibling_iterator&, sibling_iterator,
440 const sibling_iterator&,
bool duplicate_leaves =
false,
445 typename ComparePred =
std::function<
bool(sibling_iterator, sibling_iterator)>,
446 typename ReducePred =
std::function<
void(sibling_iterator, sibling_iterator)>>
448 const sibling_iterator&, const sibling_iterator&,
std::set<sibling_iterator>&,
449 ComparePred&& = [](sibling_iterator lhs,
450 sibling_iterator rhs) {
return (*lhs == *rhs); },
451 ReducePred&& = [](sibling_iterator lhs, sibling_iterator rhs) { *lhs += *rhs; });
454 template <
typename IterT>
455 inline bool equal(
const IterT& one,
const IterT& two,
const IterT& three)
const;
456 template <
typename IterT,
typename BinaryPredicate>
457 inline bool equal(
const IterT& one,
const IterT& two,
const IterT& three,
458 BinaryPredicate)
const;
459 template <
typename IterT>
461 template <
typename IterT,
typename BinaryPredicate>
462 inline bool equal_subgraph(
const IterT& one,
const IterT& two, BinaryPredicate)
const;
472 inline void swap(sibling_iterator it);
480 TIMEMORY_NODISCARD
inline size_t size()
const;
483 TIMEMORY_NODISCARD
inline bool empty()
const;
520 TIMEMORY_NODISCARD
inline unsigned int index(sibling_iterator it)
const;
529 template <
typename Archive>
532 for(
auto itr =
begin(); itr !=
end(); ++itr)
533 ar(cereal::make_nvp(
"node", *itr));
542 inline void m_head_initialize();
545 using allocator_traits = std::allocator_traits<AllocatorT>;
546 using allocator_pointer = std::shared_ptr<AllocatorT>;
548 std::vector<allocator_pointer> m_stolen_alloc = {};
555template <
typename T,
typename AllocatorT>
563template <
typename T,
typename AllocatorT>
572template <
typename T,
typename AllocatorT>
582template <
typename T,
typename AllocatorT>
590 allocator_traits::deallocate(*m_alloc,
head, 1);
591 allocator_traits::deallocate(*m_alloc,
feet, 1);
593 while(!m_stolen_alloc.empty())
595 auto _v = m_stolen_alloc.back();
596 m_stolen_alloc.pop_back();
604template <
typename T,
typename AllocatorT>
608 head = allocator_traits::allocate(*m_alloc, 1,
nullptr);
610 feet = allocator_traits::allocate(*m_alloc, 1,
nullptr);
612 allocator_traits::construct(*m_alloc,
feet, std::move(tgraph_node<T>{}));
629template <
typename T,
typename AllocatorT>
642template <
typename T,
typename AllocatorT>
646 if(it.
node ==
nullptr)
663template <
typename T,
typename AllocatorT>
664template <
typename IterT>
698 allocator_traits::deallocate(*m_alloc, cur, 1);
706template <
typename T,
typename AllocatorT>
715template <
typename T,
typename AllocatorT>
724template <
typename T,
typename AllocatorT>
728 assert(
pos.node !=
nullptr);
729 if(
pos.node->first_child ==
nullptr)
733 return pos.node->first_child;
738template <
typename T,
typename AllocatorT>
749template <
typename T,
typename AllocatorT>
750template <
typename IterT>
754 assert(position.node !=
nullptr);
755 return IterT(position.node->parent);
760template <
typename T,
typename AllocatorT>
761template <
typename IterT>
765 assert(position.node !=
nullptr);
767 ret.node = position.node->prev_sibling;
773template <
typename T,
typename AllocatorT>
774template <
typename IterT>
778 assert(position.node !=
nullptr);
780 ret.node = position.node->next_sibling;
786template <
typename T,
typename AllocatorT>
787template <
typename IterT>
791 assert(position.node !=
head);
792 assert(position.node !=
feet);
793 assert(position.node);
795 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
796 allocator_traits::construct(*m_alloc, tmp, std::move(
tgraph_node<T>{}));
800 tmp->
parent = position.node;
801 if(position.node->last_child !=
nullptr)
803 position.node->last_child->next_sibling = tmp;
810 position.node->last_child = tmp;
817template <
typename T,
typename AllocatorT>
818template <
typename IterT>
822 assert(position.node !=
head);
823 assert(position.node !=
feet);
824 assert(position.node);
826 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
827 allocator_traits::construct(*m_alloc, tmp, std::move(
tgraph_node<T>{}));
831 tmp->
parent = position.node;
832 if(position.node->first_child !=
nullptr)
834 position.node->first_child->prev_sibling = tmp;
841 position.node->prev_child = tmp;
848template <
typename T,
typename AllocatorT>
849template <
typename IterT>
857 assert(position.node !=
head);
858 assert(position.node !=
feet);
859 assert(position.node);
861 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
862 allocator_traits::construct(*m_alloc, tmp, x);
866 tmp->
parent = position.node;
867 if(position.node->last_child !=
nullptr)
869 position.node->last_child->next_sibling = tmp;
876 position.node->last_child = tmp;
883template <
typename T,
typename AllocatorT>
884template <
typename IterT>
888 assert(position.node !=
head);
889 assert(position.node !=
feet);
890 assert(position.node);
892 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
893 allocator_traits::construct(*m_alloc, tmp, std::forward<T>(x));
898 tmp->
parent = position.node;
899 if(position.node->last_child !=
nullptr)
901 position.node->last_child->next_sibling = tmp;
908 position.node->last_child = tmp;
915template <
typename T,
typename AllocatorT>
916template <
typename IterT>
920 assert(position.node !=
head);
921 assert(position.node !=
feet);
922 assert(position.node);
924 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
925 allocator_traits::construct(*m_alloc, tmp, x);
929 tmp->
parent = position.node;
930 if(position.node->first_child !=
nullptr)
932 position.node->first_child->prev_sibling = tmp;
939 position.node->first_child = tmp;
946template <
typename T,
typename AllocatorT>
947template <
typename IterT>
951 assert(position.node !=
head);
952 assert(position.node !=
feet);
953 assert(position.node);
955 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
956 allocator_traits::construct(*m_alloc, tmp, std::forward<T>(x));
961 tmp->
parent = position.node;
962 if(position.node->first_child !=
nullptr)
964 position.node->first_child->prev_sibling = tmp;
971 position.node->first_child = tmp;
978template <
typename T,
typename AllocatorT>
979template <
typename IterT>
983 assert(position.node !=
head);
984 assert(position.node !=
feet);
985 assert(position.node);
993template <
typename T,
typename AllocatorT>
994template <
typename IterT>
998 assert(position.node !=
head);
999 assert(position.node !=
feet);
1000 assert(position.node);
1008template <
typename T,
typename AllocatorT>
1009template <
typename IterT>
1014 assert(position.node !=
head);
1015 assert(position.node !=
feet);
1016 assert(position.node);
1030template <
typename T,
typename AllocatorT>
1031template <
typename IterT>
1036 assert(position.node !=
head);
1037 assert(position.node !=
feet);
1038 assert(position.node);
1048 }
while(to != from);
1055template <
typename T,
typename AllocatorT>
1065template <
typename T,
typename AllocatorT>
1075template <
typename T,
typename AllocatorT>
1076template <
typename IterT>
1080 if(position.node ==
nullptr)
1082 position.node =
feet;
1085 assert(position.node !=
head);
1087 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
1088 allocator_traits::construct(*m_alloc, tmp, x);
1092 tmp->
parent = position.node->parent;
1095 position.node->prev_sibling = tmp;
1100 tmp->
parent->first_child = tmp;
1109template <
typename T,
typename AllocatorT>
1110template <
typename IterT>
1114 if(position.node ==
nullptr)
1116 position.node =
feet;
1119 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
1120 allocator_traits::construct(*m_alloc, tmp, std::forward<T>(x));
1125 tmp->
parent = position.node->parent;
1128 position.node->prev_sibling = tmp;
1133 tmp->
parent->first_child = tmp;
1142template <
typename T,
typename AllocatorT>
1146 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
1147 allocator_traits::construct(*m_alloc, tmp, x);
1152 if(position.
node ==
nullptr)
1156 tmp->
parent->last_child = tmp;
1168 tmp->
parent->first_child = tmp;
1177template <
typename T,
typename AllocatorT>
1178template <
typename IterT>
1182 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
1183 allocator_traits::construct(*m_alloc, tmp, x);
1187 tmp->
parent = position.node->parent;
1190 position.node->next_sibling = tmp;
1195 tmp->
parent->last_child = tmp;
1206template <
typename T,
typename AllocatorT>
1207template <
typename IterT>
1211 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
1212 allocator_traits::construct(*m_alloc, tmp, std::forward<T>(x));
1217 tmp->
parent = position.node->parent;
1220 position.node->next_sibling = tmp;
1225 tmp->
parent->last_child = tmp;
1236template <
typename T,
typename AllocatorT>
1237template <
typename IterT>
1244 return replace(it, _subgraph);
1249template <
typename T,
typename AllocatorT>
1250template <
typename IterT>
1258 return replace(it, _subgraph);
1276template <
typename T,
typename AllocatorT>
1277template <
typename IterT>
1282 allocator_traits::construct(*m_alloc, position.node, x);
1288template <
typename T,
typename AllocatorT>
1289template <
typename IterT>
1294 allocator_traits::construct(*m_alloc, position.node, std::forward<T>(x));
1300template <
typename T,
typename AllocatorT>
1301template <
typename IterT>
1305 assert(position.node !=
head);
1314 graph_node* tmp = allocator_traits::allocate(*m_alloc, 1,
nullptr);
1315 allocator_traits::construct(*m_alloc, tmp, (*from));
1320 if(current_to->
parent !=
nullptr)
1321 current_to->
parent->first_child = tmp;
1330 if(current_to->
parent !=
nullptr)
1331 current_to->
parent->last_child = tmp;
1340 allocator_traits::deallocate(*m_alloc, current_to, 1);
1350 assert(current_from !=
nullptr);
1358 while(current_from->
next_sibling ==
nullptr && current_from != start_from)
1360 current_from = current_from->
parent;
1362 assert(current_from !=
nullptr);
1365 if(current_from != last && current_from)
1370 }
while(current_from != last && current_from);
1377template <
typename T,
typename AllocatorT>
1386 while((++orig_begin) != orig_end)
1389 while((++new_begin) != new_end)
1404 if(new_first == new_last)
1414 if(next == orig_last)
1427template <
typename T,
typename AllocatorT>
1428template <
typename IterT>
1432 if(position.node->first_child ==
nullptr)
1438 tmp->
parent = position.node->parent;
1441 if(position.node->next_sibling)
1443 position.node->last_child->next_sibling = position.node->next_sibling;
1444 position.node->next_sibling->prev_sibling = position.node->last_child;
1448 position.node->parent->last_child = position.node->last_child;
1450 position.node->next_sibling = position.node->first_child;
1451 position.node->next_sibling->prev_sibling = position.node;
1452 position.node->first_child =
nullptr;
1453 position.node->last_child =
nullptr;
1460template <
typename T,
typename AllocatorT>
1461template <
typename IterT>
1469 assert(first != position.node);
1474 while((++_begin) != _end)
1495 if(position.node->first_child ==
nullptr)
1497 position.node->first_child = first;
1503 position.node->last_child->next_sibling = first;
1505 position.node->last_child = last;
1512 pos->parent = position.node;
1523template <
typename T,
typename AllocatorT>
1524template <
typename IterT>
1528 if(from.node->first_child ==
nullptr)
1530 return reparent(position, from.node->first_child,
end(from));
1535template <
typename T,
typename AllocatorT>
1536template <
typename IterT>
1540 assert(position.node !=
nullptr);
1544 IterT ret =
insert(position, x);
1551template <
typename T,
typename AllocatorT>
1552template <
typename IterT>
1556 assert(from.node !=
nullptr);
1557 IterT ret =
insert(from, x);
1564template <
typename T,
typename AllocatorT>
1565template <
typename IterT>
1607 dst->
parent->last_child = src;
1618template <
typename T,
typename AllocatorT>
1619template <
typename IterT>
1661 dst->
parent->first_child = src;
1672template <
typename T,
typename AllocatorT>
1673template <
typename IterT>
1716 if(b_prev_sibling !=
nullptr)
1724 if(b_next_sibling !=
nullptr)
1740template <
typename T,
typename AllocatorT>
1767template <
typename T,
typename AllocatorT>
1768template <
typename IterT>
1790 walk->
parent = loc.node->parent;
1791 if(walk == other_last_head)
1800 return other_first_head;
1805template <
typename T,
typename AllocatorT>
1806template <
typename IterT>
1818 if(loc.node->first_child ==
nullptr)
1820 loc.node->first_child = other_first_head;
1827 loc.node->first_child->prev_sibling = other_last_head;
1829 loc.node->first_child = other_first_head;
1841 throw std::range_error(
1842 "graph: move_in_as_nth_child position out of range");
1851 loc.node->last_child = other_last_head;
1867 if(walk == other_last_head)
1876 return other_first_head;
1881template <
typename T,
typename AllocatorT>
1885 bool duplicate_leaves,
bool first)
1887 while(from1 != from2)
1891 decltype(nsiblings) count =
nullptr;
1894 if(itr && from1 && *itr == *from1)
1899 if(count > nsiblings)
1910 if(duplicate_leaves)
1931 }
while(!from1 && from1 != from2);
1937template <
typename T,
typename AllocatorT>
1938template <
typename ComparePred,
typename ReducePred>
1941 std::set<sibling_iterator>& _erase, ComparePred&& _compare,
1942 ReducePred&& _reduce)
1956 uint32_t idx =
index(litr);
1957 for(uint32_t i = 0; i < nsiblings; ++i)
1968 if(litr.node == ritr.
node)
1971 if(_erase.find(ritr) != _erase.end())
1974 if(_compare(litr, ritr))
1981 reduce(aitr.begin(),
feet, _erase, _compare, _reduce);
1983 _erase.insert(ritr);
1984 reduce(litr.begin(),
feet, _erase, _compare, _reduce);
1985 _reduce(litr, ritr);
1992 for(
auto& itr : _erase)
1995 if(_erase.size() > 0)
2006template <
typename T,
typename AllocatorT>
2007template <
typename IterT>
2010 const IterT& three_)
const
2012 std::equal_to<T> comp;
2013 return equal(one_, two, three_, comp);
2018template <
typename T,
typename AllocatorT>
2019template <
typename IterT>
2023 std::equal_to<T> comp;
2029template <
typename T,
typename AllocatorT>
2030template <
typename IterT,
typename BinaryPredicate>
2033 BinaryPredicate fun)
const
2040 while(one != two &&
is_valid(three))
2042 if(!fun(*one, *three))
2054template <
typename T,
typename AllocatorT>
2055template <
typename IterT,
typename BinaryPredicate>
2058 BinaryPredicate fun)
const
2063 if(!fun(*one, *two))
2072template <
typename T,
typename AllocatorT>
2083template <
typename T,
typename AllocatorT>
2088 assert(
pos !=
nullptr);
2090 while(
pos->parent !=
nullptr)
2100template <
typename T,
typename AllocatorT>
2105 assert(
pos !=
nullptr);
2107 while(
pos->parent !=
nullptr &&
pos != root.
node)
2117template <
typename T,
typename AllocatorT>
2130template <
typename T,
typename AllocatorT>
2136 if(tmp ==
nullptr || tmp ==
head || tmp ==
feet)
2164 maxdepth =
std::max(curdepth, maxdepth);
2170template <
typename T,
typename AllocatorT>
2178 unsigned int ret = 1;
2179 while((
pos =
pos->next_sibling))
2186template <
typename T,
typename AllocatorT>
2191 unsigned int ret = 0;
2193 while(
pos->next_sibling &&
pos->next_sibling !=
head &&
pos->next_sibling !=
feet)
2200 while(
pos->prev_sibling &&
pos->prev_sibling !=
head &&
pos->prev_sibling !=
feet)
2211template <
typename T,
typename AllocatorT>
2244template <
typename T,
typename AllocatorT>
2311template <
typename T,
typename AllocatorT>
2326template <
typename T,
typename AllocatorT>
2337template <
typename T,
typename AllocatorT>
2343 return static_cast<unsigned int>(-1);
2345 if(tmp->
parent !=
nullptr)
2347 tmp = tmp->
parent->first_child;
2355 unsigned int ret = 0;
2356 while(tmp != it.
node)
2367template <
typename T,
typename AllocatorT>
2375 if(tmp->
parent !=
nullptr)
2377 tmp = tmp->
parent->first_child;
2385 while((num--) != 0u)
2387 assert(tmp !=
nullptr);
2395template <
typename T,
typename AllocatorT>
2400 while((num--) != 0u)
2402 assert(tmp !=
nullptr);
2411template <
typename T,
typename AllocatorT>
2419template <
typename T,
typename AllocatorT>
2427template <
typename T,
typename AllocatorT>
2435template <
typename T,
typename AllocatorT>
2438 return &(node->data);
2443template <
typename T,
typename AllocatorT>
2448 if(other.
node != this->node)
2459template <
typename T,
typename AllocatorT>
2464 if(other.
node == this->node)
2475template <
typename T,
typename AllocatorT>
2479 if(other.
node != this->node)
2490template <
typename T,
typename AllocatorT>
2494 if(other.
node == this->node)
2505template <
typename T,
typename AllocatorT>
2509 if(node->first_child ==
nullptr)
2519template <
typename T,
typename AllocatorT>
2530template <
typename T,
typename AllocatorT>
2534 m_skip_current_children =
true;
2539template <
typename T,
typename AllocatorT>
2543 m_skip_current_children = skip;
2548template <
typename T,
typename AllocatorT>
2556 unsigned int ret = 1;
2557 while(
pos != node->last_child)
2568template <
typename T,
typename AllocatorT>
2575template <
typename T,
typename AllocatorT>
2582template <
typename T,
typename AllocatorT>
2589template <
typename T,
typename AllocatorT>
2594 if(this->
node ==
nullptr)
2611template <
typename T,
typename AllocatorT>
2615 assert(this->node !=
nullptr);
2616 if(!this->m_skip_current_children && this->node->first_child !=
nullptr)
2618 this->node = this->node->first_child;
2622 this->m_skip_current_children =
false;
2623 while(this->node->next_sibling ==
nullptr)
2625 this->node = this->node->parent;
2626 if(this->node ==
nullptr)
2629 this->node = this->node->next_sibling;
2636template <
typename T,
typename AllocatorT>
2640 assert(this->node !=
nullptr);
2641 if(this->node->prev_sibling)
2643 this->node = this->node->prev_sibling;
2644 while(this->node->last_child)
2645 this->node = this->node->last_child;
2649 this->node = this->node->parent;
2650 if(this->node ==
nullptr)
2658template <
typename T,
typename AllocatorT>
2669template <
typename T,
typename AllocatorT>
2680template <
typename T,
typename AllocatorT>
2694template <
typename T,
typename AllocatorT>
2708template <
typename T,
typename AllocatorT>
2723template <
typename T,
typename AllocatorT>
2732template <
typename T,
typename AllocatorT>
2741template <
typename T,
typename AllocatorT>
2750template <
typename T,
typename AllocatorT>
2755 if(this->node ==
nullptr)
2757 if(this->node->parent !=
nullptr)
2758 m_parent = this->node->
parent;
2763template <
typename T,
typename AllocatorT>
2768 this->node = this->node->next_sibling;
2774template <
typename T,
typename AllocatorT>
2780 this->node = this->node->prev_sibling;
2785 this->node = m_parent->last_child;
2792template <
typename T,
typename AllocatorT>
2803template <
typename T,
typename AllocatorT>
2814template <
typename T,
typename AllocatorT>
2828template <
typename T,
typename AllocatorT>
2842template <
typename T,
typename AllocatorT>
2857template <
typename T,
typename AllocatorT>
2861 return (m_parent) ? m_parent->
last_child :
nullptr;
2866template <
typename T,
typename AllocatorT>
2884template <
typename T>
2890template <
typename T>
2893 std::ostream&
os = std::cout);
2900template <
typename T>
2910 if(nhead != head_count)
2921template <
typename T>
2926 static int _depth = 0;
2930 auto m_depth = _depth++;
2932 for(
int i = 0; i < m_depth; ++i)
2937 os <<
"\n" << indent << *root;
2942 os <<
"\n" << indent << *root;
2948 for(children = t.
begin(root), nsiblings = 0; children != t.
end(root);
2949 ++children, ++nsiblings)
2954 if(nsiblings != sibling_count)
2966template <
typename T,
typename Formatter = std::function<std::
string(const T&)>>
2972template <
typename T,
typename Formatter = std::function<std::
string(const T&)>>
2979template <
typename T,
typename Formatter>
2989 if(nhead != head_count)
2998template <
typename T>
3002 auto _formatter = [](
const T& obj) {
3003 std::stringstream ss;
3013 if(nhead != head_count)
3022template <
typename T,
typename Formatter>
3031 os << format(*root);
3037 if(str.length() > 0)
3043 for(children = t.
begin(root), nsiblings = 0; children != t.
end(root);
3044 ++children, ++nsiblings)
3049 if(nsiblings != sibling_count)
3059template <
typename T,
typename Formatter = std::function<std::
string(const T&)>>
3062 std::ostream& str = std::cout);
3066template <
typename T,
typename Formatter = std::function<std::
string(const T&)>>
3070 std::ostream& str = std::cout);
3074template <
typename T,
typename Formatter>
3084 if(nhead != head_count)
3093template <
typename T,
typename Formatter>
3102 os << format(*root);
3108 if(str.length() > 0)
3109 os << str <<
"\n" << std::setw(2 * (t.
depth(root) + 1)) <<
"|_";
3114 for(children = t.
begin(root), nsiblings = 0; children != t.
end(root);
3115 ++children, ++nsiblings)
3120 if(nsiblings != sibling_count)
3122 os <<
"\n" << std::setw(2 * (t.
depth(root) + 1)) <<
"|_";
Base class for iterators, only pointers stored, no traversal logic.
std::bidirectional_iterator_tag iterator_category
iterator_base(iterator_base &&) noexcept=default
iterator_base(const iterator_base &)=default
sibling_iterator end() const
ptrdiff_t difference_type
void skip_children()
When called, the next increment/decrement skips children of this node.
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
sibling_iterator begin() const
Depth-first iterator, first accessing the node, then its children.
pre_order_iterator & operator++()
bool operator!=(const pre_order_iterator &) const
pre_order_iterator & operator--()
pre_order_iterator(pre_order_iterator &&) noexcept=default
pre_order_iterator operator+(unsigned int)
bool operator==(const pre_order_iterator &) const
pre_order_iterator & operator+=(unsigned int)
pre_order_iterator & next_skip_children()
pre_order_iterator(const pre_order_iterator &)=default
pre_order_iterator & operator-=(unsigned int)
Iterator which traverses only the nodes which are siblings of each other.
sibling_iterator & operator--()
sibling_iterator & operator-=(unsigned int)
sibling_iterator & operator+=(unsigned int)
sibling_iterator(sibling_iterator &&) noexcept=default
sibling_iterator operator+(unsigned int)
graph_node * range_last() const
sibling_iterator & operator++()
bool operator!=(const sibling_iterator &) const
bool operator==(const sibling_iterator &) const
sibling_iterator(const sibling_iterator &)=default
Arbitrary Graph / Tree (i.e. binary-tree but not binary). It is unlikely that this class will interac...
void clear()
Erase all nodes of the graph.
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
bool equal_subgraph(const IterT &one, const IterT &two, BinaryPredicate) const
IterT append_child(IterT position)
Insert empty node as last/first child of node pointed to by position.
size_t size() const
Count the total number of nodes.
IterT move_before(IterT target, IterT source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
bool empty() const
Check if graph is empty.
graph(const this_type &)=delete
void swap(sibling_iterator it)
Exchange the node (plus subgraph) with its sibling node (do nothing if no sibling present).
iterator::difference_type difference_type
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.
IterT erase(IterT)
Erase element at position pointed to by iterator, return incremented iterator.
IterT insert_after(IterT position, const T &x)
Insert node as next sibling of node pointed to by position.
static IterT next_sibling(IterT)
Return iterator to the next sibling of a node.
pre_order_iterator end() const
Return iterator to the end of the graph.
IterT move_in(IterT, graph &)
Inverse of take_out: inserts the given graph as previous sibling of indicated node by a move operatio...
graph(this_type &&) noexcept=default
IterT prepend_child(IterT position)
static IterT previous_sibling(IterT)
Return iterator to the previous sibling of a node.
static int depth(const iterator_base &)
Compute the depth to the root or to a fixed other 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.
int max_depth() const
Determine the maximal depth of the graph. An empty graph has max_depth=-1.
IterT prepend_children(IterT position, sibling_iterator from, sibling_iterator to)
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.
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.
IterT reparent(IterT position, sibling_iterator begin, const sibling_iterator &end)
Move nodes in range to be children of 'position'.
static int depth(const iterator_base &, const iterator_base &)
pre_order_iterator iterator
The default iterator types throughout the graph class.
bool equal(const IterT &one, const IterT &two, const IterT &three) const
Compare two ranges of nodes (compares nodes as well as graph structure).
static sibling_iterator child(const iterator_base &position, unsigned int)
Inverse of 'index': return the n-th child of the node at position.
void steal_resources(this_type &rhs)
bool equal_subgraph(const IterT &one, const IterT &two) const
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.
static unsigned int number_of_children(const iterator_base &)
Count the number of children of node at position.
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.
IterT replace(IterT position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
IterT move_ontop(IterT target, IterT source)
Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
void serialize(Archive &ar, const unsigned int)
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).
void subgraph(graph &, sibling_iterator from, sibling_iterator to) const
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty graph.
graph subgraph(sibling_iterator from, sibling_iterator to) const
Extract a new graph formed by the range of siblings plus all their children.
IterT flatten(IterT position)
Move all children of node at 'position' to be siblings, returns position.
graph(const iterator_base &)
bool equal(const IterT &one, const IterT &two, const IterT &three, BinaryPredicate) const
static IterT parent(IterT)
Return iterator to the parent of a node.
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...
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.
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.
IterT insert(IterT position, const T &x)
Insert node as previous sibling of node pointed to by position.
T value_type
Value of the data stored at a node.
IterT move_in_below(IterT, graph &)
As above, but now make the graph a child of the indicated node.
sibling_iterator sibling(const iterator_base &position, unsigned int) const
Return iterator to the sibling indicated by index.
void swap(iterator, iterator)
Exchange two nodes (plus subgraphs). The iterators will remain valid and keep pointing to the same no...
unsigned int index(sibling_iterator it) const
Determine the index of a node in the range of siblings to which it belongs.
pre_order_iterator begin() const
Return iterator to the beginning of the graph.
int max_depth(const iterator_base &) const
Determine the maximal depth of the graph with top node at the given position.
graph move_out(iterator)
Extract the subgraph starting at the indicated node, removing it from the original graph.
IterT move_after(IterT target, IterT source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
bool is_valid(const iterator_base &) const
Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.
A node in the graph, combining links to other nodes as well as the actual data.
tgraph_node(tgraph_node &&)=default
tgraph_node< T > * last_child
tgraph_node< T > * next_sibling
void serialize(Archive &ar, const unsigned int)
tgraph_node & operator=(tgraph_node &&)=default
tgraph_node< T > * prev_sibling
tgraph_node< T > * parent
tgraph_node< T > * first_child
tgraph_node(const tgraph_node &)=delete
tgraph_node & operator=(const tgraph_node &)=delete
::tim::statistics< Tp > max(::tim::statistics< Tp > lhs, const Tp &rhs)
auto destroy(TupleT< Tp... > &obj)
Lhs operator*(Lhs, const Rhs &)
void print_graph(const tim::graph< T > &t, Formatter format, std::ostream &str=std::cout)
void print_graph_bracketed(const graph< T > &t, std::ostream &os=std::cout)
tim::mpl::apply< std::string > string
void print_graph_hierarchy(const tim::graph< T > &t, Formatter format, std::ostream &str=std::cout)
const std::string std::ostream * os
void print_subgraph_bracketed(const graph< T > &t, typename graph< T >::iterator root, std::ostream &os=std::cout)
void print_subgraph(const tim::graph< T > &t, Formatter format, typename tim::graph< T >::iterator root, std::ostream &str=std::cout)
void print_subgraph_hierarchy(const tim::graph< T > &t, Formatter format, typename tim::graph< T >::iterator root, std::ostream &str=std::cout)
Declare the storage types.
static auto release(std::shared_ptr< AllocT > &_v)
typename typename typename