TreeNode.hpp
1 #pragma once
2 #include <score/tools/Debug.hpp>
3 
4 #include <ossia/detail/algorithms.hpp>
5 #include <ossia/detail/ssize.hpp>
6 
7 #include <list>
8 #include <vector>
9 
17 template <typename T>
18 auto& child_at(const std::list<T>& list, int index)
19 {
20  SCORE_ASSERT(index >= 0 && index < std::ssize(list));
21  auto it = list.begin();
22  std::advance(it, index);
23  return *it;
24 }
25 
26 template <typename T>
27 auto& child_at(std::list<T>& list, int index)
28 {
29  SCORE_ASSERT(index >= 0 && index < std::ssize(list));
30  auto it = list.begin();
31  std::advance(it, index);
32  return *it;
33 }
34 
35 template <typename T>
36 int index_of_child(const std::list<T>& list, const T* child)
37 {
38  int i = 0;
39  const auto end = list.end();
40  for(auto it = list.begin(); it != end; ++it)
41  {
42  if(&(*it) == child)
43  return i;
44  i++;
45  }
46 
47  return -1;
48 }
49 
50 template <typename DataType>
51 class TreeNode : public DataType
52 {
53 private:
54  TreeNode* m_parent{};
55  std::list<TreeNode> m_children;
56  using impl_type = std::list<TreeNode>;
57 
58 public:
59  using iterator = typename impl_type::iterator;
60  using const_iterator = typename impl_type::const_iterator;
61 
62  auto begin() noexcept { return m_children.begin(); }
63  auto begin() const noexcept { return cbegin(); }
64  auto cbegin() const noexcept { return m_children.cbegin(); }
65 
66  auto end() noexcept { return m_children.end(); }
67  auto end() const noexcept { return cend(); }
68  auto cend() const noexcept { return m_children.cend(); }
69 
70  TreeNode() = default;
71 
72  // The parent has to be set afterwards.
73  TreeNode(const TreeNode& other) noexcept
74  : DataType(static_cast<const DataType&>(other))
75  , m_parent{other.m_parent}
76  , m_children(other.m_children)
77  {
78  for(auto& child : m_children)
79  child.setParent(this);
80  }
81 
82  TreeNode(TreeNode&& other) noexcept
83  : DataType(std::move(static_cast<DataType&&>(other)))
84  , m_parent{other.m_parent}
85  , m_children(std::move(other.m_children))
86  {
87  for(auto& child : m_children)
88  child.setParent(this);
89  }
90 
91  TreeNode& operator=(const TreeNode& source) noexcept
92  {
93  static_cast<DataType&>(*this) = static_cast<const DataType&>(source);
94  m_parent = source.m_parent;
95 
96  m_children = source.m_children;
97  for(auto& child : m_children)
98  {
99  child.setParent(this);
100  }
101 
102  return *this;
103  }
104 
105  TreeNode& operator=(TreeNode&& source) noexcept
106  {
107  static_cast<DataType&>(*this) = static_cast<DataType&&>(source);
108  m_parent = source.m_parent;
109 
110  m_children = std::move(source.m_children);
111  for(auto& child : m_children)
112  {
113  child.setParent(this);
114  }
115 
116  return *this;
117  }
118 
119  TreeNode(DataType data, TreeNode* parent) noexcept
120  : DataType(std::move(data))
121  , m_parent{parent}
122  {
123  }
124 
125  // Clone
126  explicit TreeNode(TreeNode source, TreeNode* parent) noexcept
127  : TreeNode{std::move(source)}
128  {
129  m_parent = parent;
130  }
131 
132  void push_back(const TreeNode& child) noexcept
133  {
134  m_children.push_back(child);
135 
136  auto& cld = m_children.back();
137  cld.setParent(this);
138  }
139 
140  void push_back(TreeNode&& child) noexcept
141  {
142  m_children.push_back(std::move(child));
143 
144  auto& cld = m_children.back();
145  cld.setParent(this);
146  }
147 
148  template <typename... Args>
149  auto& emplace_back(Args&&... args) noexcept
150  {
151  m_children.emplace_back(std::forward<Args>(args)...);
152 
153  auto& cld = m_children.back();
154  cld.setParent(this);
155  return cld;
156  }
157 
158  template <typename... Args>
159  auto& insert(Args&&... args) noexcept
160  {
161  auto& n = *m_children.insert(std::forward<Args>(args)...);
162  n.setParent(this);
163  return n;
164  }
165 
166  template <typename... Args>
167  auto& emplace(Args&&... args) noexcept
168  {
169  auto& n = *m_children.emplace(std::forward<Args>(args)...);
170  n.setParent(this);
171  return n;
172  }
173 
174  TreeNode* parent() const noexcept { return m_parent; }
175 
176  bool hasChild(std::size_t index) const noexcept { return m_children.size() > index; }
177 
178  TreeNode& childAt(int index) noexcept { return child_at(m_children, index); }
179 
180  const TreeNode& childAt(int index) const noexcept
181  {
182  return child_at(m_children, index);
183  }
184 
185  // returns -1 if not found
186  int indexOfChild(const TreeNode* child) const noexcept
187  {
188  return index_of_child(m_children, child);
189  }
190 
191  auto iterOfChild(const TreeNode* child) noexcept
192  {
193  const auto end = m_children.end();
194  for(auto it = m_children.begin(); it != end; ++it)
195  {
196  if(&*it == child)
197  return it;
198  }
199  return end;
200  }
201 
202  int childCount() const noexcept { return m_children.size(); }
203 
204  bool hasChildren() const noexcept { return !m_children.empty(); }
205 
206  const auto& children() const noexcept { return m_children; }
207 
208  auto takeChildren() noexcept
209  {
210  auto cld = std::move(m_children);
211  m_children.clear();
212 
213  for(auto& child : cld)
214  child.setParent(nullptr);
215 
216  return cld;
217  }
218 
219  void moveChildren(TreeNode& newParent) noexcept
220  {
221  auto cld = std::move(m_children);
222  m_children.clear();
223 
224  for(TreeNode& child : cld)
225  {
226  // This will repoint things correctly
227  newParent.push_back(std::move(child));
228  }
229  }
230 
231  void reserve(std::size_t s) noexcept
232  {
233  // m_children.reserve(s);
234  }
235  void resize(std::size_t s) noexcept { m_children.resize(s); }
236 
237  auto erase(const_iterator it) noexcept { return m_children.erase(it); }
238 
239  auto erase(const_iterator it_beg, const_iterator it_end) noexcept
240  {
241  return m_children.erase(it_beg, it_end);
242  }
243 
244  void setParent(TreeNode* parent) noexcept { m_parent = parent; }
245 
246  template <typename Fun>
247  void visit(Fun f) const noexcept(noexcept(f(std::declval<TreeNode>())))
248  {
249  f(*this);
250 
251  for(const auto& child : m_children)
252  {
253  child.visit(f);
254  }
255  }
256 };
257 
258 // True if gramps is a parent, grand-parent, etc. of node.
259 template <typename Node_T>
260 bool isAncestor(const Node_T& gramps, const Node_T* node) noexcept
261 {
262  auto parent = node->parent();
263  if(!parent)
264  return false;
265 
266  if(node == &gramps)
267  return true;
268 
269  return isAncestor(gramps, parent);
270 }
271 
293 template <typename Node_T>
294 std::vector<Node_T*> filterUniqueParents(std::vector<Node_T*>& nodes) noexcept
295 {
296  std::vector<Node_T*> cleaned_nodes;
297 
298  ossia::remove_duplicates(nodes);
299 
300  cleaned_nodes.reserve(nodes.size());
301 
302  // Only copy the index if it none of its parents
303  // except the invisible root are in the list.
304  for(auto n : nodes)
305  {
306  if(ossia::any_of(nodes, [&](Node_T* other) {
307  if(other == n)
308  return false;
309  return isAncestor(*other, n);
310  }))
311  {
312  continue;
313  }
314  else
315  {
316  cleaned_nodes.push_back(n);
317  }
318  }
319 
320  return cleaned_nodes;
321 }
Definition: TreeNode.hpp:52