DiaDes  0.1
DIAgnosis of Discrete-Event System
NAryTree.hh
Go to the documentation of this file.
1 
9 #ifndef __DIADES__UTILS__NARYTREE__HH__
10 #define __DIADES__UTILS__NARYTREE__HH__
11 
12 namespace Diades
13 {
14  namespace Utils
15  {
16 
34  template<typename Node, typename Leaf, template<typename, typename> class _Map>
35  class NAryTree
36  {
37  private:
38 
44  {
45  public:
50  virtual bool isLeaf() const = 0;
51 
59  template<typename NodeIterator>
60  bool
61  getLeaf(NodeIterator begin, NodeIterator end, Leaf & result) const
62  {
63 
64 
65  if(begin == end)
66  {
67 
68  if(this->isLeaf())
69  {
70 
71  result = static_cast<const TreeLeaf *> (this)->leaf();
72 
73  return true;
74  }
75  else
76  {
77 
78  return false;
79  }
80  }
81 
82  if(this->isLeaf())
83  {
84 
85  return false;
86  }
87 
88  auto branches = static_cast<const TreeBranches *> (this);
89  auto branchIt = branches->find(*begin);
90  if(branchIt == branches->end())
91  {
92 
93  return false;
94  }
95 
96  return branchIt->second->getLeaf(++begin, end, result);
97  }
98 
99  };
100 
106  class TreeLeaf : public TreeElement
107  {
108  private:
109  Leaf _leaf;
110  public:
111 
112  TreeLeaf(const Leaf & leaf) : _leaf(leaf)
113  {
114  }
115 
120  virtual bool
121  isLeaf() const
122  {
123  return true;
124  }
125 
130  Leaf &
132  {
133  return _leaf;
134  }
135 
140  const Leaf &
141  leaf() const
142  {
143  return _leaf;
144  }
145 
146  };
147 
157  class TreeBranches : public TreeElement
158  {
159  private:
160 
167  using Map = _Map<Node, std::unique_ptr<TreeElement> >;
169 
170 
171  using ConstIterator = typename Map::const_iterator;
172 
173 
174  public:
175 
180  virtual bool
181  isLeaf() const
182  {
183  return false;
184  }
185 
191  begin() const
192  {
193  return _branches.begin();
194  }
195 
201  end() const
202  {
203  return _branches.end();
204  }
205 
212  find(const Node & node) const
213  {
214  return _branches.find(node);
215  }
216 
228  template<typename NodeIterator>
229  Leaf &
230  insertSuccessiveBranches(NodeIterator begin, NodeIterator end, const Leaf & info)
231  {
232  auto it = begin;
233  ++it;
234  if(it == end)
235  {
236 
237  auto result = _branches.emplace(*begin, std::make_unique<TreeLeaf>(info));
238 
239  return static_cast<TreeLeaf *> (result.first->second.get())->leaf();
240  }
241  auto branchIt = _branches.find(*begin);
242  if(branchIt == _branches.end())
243  {
244 
245  auto result = _branches.emplace(*begin, std::make_unique<TreeBranches>());
246  return static_cast<TreeBranches *> (result.first->second.get())->insertSuccessiveBranches(++begin, end, info);
247  }
248 
249  return static_cast<TreeBranches *> (branchIt->second.get())->insertSuccessiveBranches(++begin, end, info);
250  }
251  };
252 
257  std::unique_ptr<TreeBranches> _firstBranches;
258 
259  public:
260 
262  NAryTree() = default;
263 
268  NAryTree(NAryTree const& other) = default;
269 
275  NAryTree& operator=(NAryTree const& other) = default;
280  NAryTree(NAryTree&& other) = default;
286  NAryTree& operator=(NAryTree&& other) = default;
287 
289  ~NAryTree() = default;
290 
302  template<typename NodeIterator>
303  Leaf &
304  insertSuccessiveBranches(NodeIterator begin, NodeIterator end, const Leaf & info)
305  {
306  if(!_firstBranches)
307  {
308 
309  _firstBranches = std::make_unique<TreeBranches>();
310  }
311 
312  return _firstBranches->insertSuccessiveBranches(begin, end, info);
313  }
314 
322  template<typename NodeIterator>
323  bool
324  getLeaf(NodeIterator begin, NodeIterator end, Leaf & result)
325  {
326  if(!_firstBranches)
327  {
328  return false;
329  }
330  return _firstBranches->getLeaf(begin, end, result);
331  }
332 
336  void
338  {
339  if(_firstBranches)
340  {
341  _firstBranches.reset(nullptr);
342  }
343  }
344  };
345 
346  }
347 }
348 
349 
350 
351 
352 #endif /* __DIADES__UTILS__NARYTREE__HH__ */
353 
typename Map::const_iterator ConstIterator
Definition: NAryTree.hh:171
Leaf & insertSuccessiveBranches(NodeIterator begin, NodeIterator end, const Leaf &info)
Definition: NAryTree.hh:304
std::unique_ptr< TreeBranches > _firstBranches
Definition: NAryTree.hh:257
_Map< Node, std::unique_ptr< TreeElement > > Map
Definition: NAryTree.hh:167
virtual bool isLeaf() const
Definition: NAryTree.hh:121
virtual bool isLeaf() const =0
ConstIterator find(const Node &node) const
Definition: NAryTree.hh:212
bool getLeaf(NodeIterator begin, NodeIterator end, Leaf &result) const
Definition: NAryTree.hh:61
NAryTree & operator=(NAryTree const &other)=default
NAryTree()=default
Default constructor.
const Leaf & leaf() const
Definition: NAryTree.hh:141
GraphIterator< Node > NodeIterator
Definition: GraphInt.hh:139
bool getLeaf(NodeIterator begin, NodeIterator end, Leaf &result)
Definition: NAryTree.hh:324
Namespace of the Diades project.
~NAryTree()=default
Destructor.
Leaf & insertSuccessiveBranches(NodeIterator begin, NodeIterator end, const Leaf &info)
Definition: NAryTree.hh:230