DiaDes  0.1
DIAgnosis of Discrete-Event System
GraphNodeSetTable.hh
Go to the documentation of this file.
1 #ifndef __DIADES__GRAPH__GRAPHNODESETTABLE__HH__
2 #define __DIADES__GRAPH__GRAPHNODESETTABLE__HH__
3 #include <memory>
4 #include <list>
5 #include <diades/utils/Exceptions.hh>
6 #include <diades/graph/GraphNodeSet.hh>
7 
8 using namespace std;
9 
10 namespace Diades {
11  namespace Graph {
12 
18  template<typename T>
19  class NodeElement {
20  public:
21 
22  static string typeName() {
23  return "Graph::NodeElement";
24  }
25  typedef Diades::Utils::Exception<NodeElement> Exception;
26  using Children = std::map<Node, std::unique_ptr<NodeElement>>;
27  private:
28  Node _node;
29  T _inf;
30  bool _tag;
31  Children _children;
32 
33 
34  public:
35 
40  NodeElement() : _node(), _inf(), _tag(false), _children() {
41  }
42 
49  NodeElement(Node n) : _node(n), _inf(), _tag(false), _children() {
50  require(Exception, n.valid(),
51  "NodeElement: the node is not valid");
52 
53  }
54 
62  NodeElement(Node n, const T & inf) : _node(n), _inf(inf), _tag(true), _children() {
63  }
64 
68  ~NodeElement() {
69  // while(!_children.empty())
70  // {
71  // if(_children.front() != 0)
72  // {
73  // delete _children.front();
74  // }
75  // _children.pop_front();
76  // }
77  }
78 
82  bool isTagged() const {
83  return _tag;
84  }
85 
89  const Node & node() const {
90  return _node;
91  }
92 
97  T & setInfo(const T & inf) {
98  _inf = inf;
99  _tag = true;
100  return _inf;
101  }
102 
107  const T & getInfo() const {
108  require(Exception, isTagged(),
109  "getInfo: the current nodeElement does not contain any information");
110  return _inf;
111  }
112 
117  T & getInfo() {
118  require(Exception, isTagged(),
119  "getInfo: the current nodeElement does not contain any information");
120  return _inf;
121  }
122 
126  Children & children() {
127  return _children;
128  }
129 
133  const Children & children() const {
134  return _children;
135  }
136 
137  // /**
138  // * NodeElement insertion
139  // * @param n a Node
140  // * @param inf info to insert
141  // * @param found true if the insertion is effective
142  // * @return the child NodeElement of the current NodeElement
143  // * that is associated with Node n. If this NodeElement was
144  // * not present then it is inserted in an ordered manner (Node order)
145  // * and the information inf is copied in. If the NodeElement was already
146  // * there, it is just returned, info is then simply ignored.
147  // */
148  // NodeElement * insertChildIfNotFound(Node n, const T & inf, bool & found) {
149  // auto result = insertChildIfNotFound(n, found);
150  // if (!found) {
151  // result->setInfo(inf);
152  // }
153  // return result;
154  // }
155 
165  NodeElement * insertChildIfNotFound(Node n, bool & found) {
166  typename Children::iterator it;
167  bool notFound;
168  std::tie(it, notFound) = _children.emplace(n, new NodeElement(n));
169  found = !notFound;
170  return it->second.get();
171  }
172 
180  NodeElement * getChild(Node n) {
181  auto it = _children.find(n);
182  return (it == _children.end()) ? nullptr : it->second.get();
183  }
184 
192  const NodeElement * getChild(Node n) const {
193  auto it = _children.find(n);
194  return (it == _children.end()) ? nullptr : it->second.get();
195  }
196  };
197 
201  template<typename T>
202  inline ostream& operator<<(ostream &os, const NodeElement<T> & nodeElement) {
203  os << "***************************************************" << endl;
204  os << "Start NodeElement: " << &nodeElement << endl;
205  os << "***************************************************" << endl;
206  os << "\t node: " << nodeElement.node() << endl;
207  os << "\t children: " << endl;
208  for (auto it = nodeElement.children().begin();
209  it != nodeElement.children().end();
210  ++it) {
211  os << **it << endl;
212  }
213  os << "***************************************************" << endl;
214  os << "End NodeElement: " << &nodeElement << endl;
215  os << "***************************************************" << endl;
216  return os;
217  }
218 
228  template <typename T>
229  class GraphNodeSetTable {
230  public:
231 
232  static string typeName() {
233  return "Graph::GraphNodeSetTable";
234  }
235  typedef Diades::Utils::Exception<GraphNodeSetTable> Exception;
236  using Children = typename NodeElement<T>::Children;
237  using NdElement = NodeElement<T>;
238  private:
239  NdElement _root;
240  T _defaultInfo;
241  public:
242 
247  GraphNodeSetTable() : _root(), _defaultInfo() {
248  }
249 
253  ~GraphNodeSetTable() {
254  }
255 
262  const T & getInfo(const GraphNodeSet & ns, bool & found) const {
263  if (ns.isEmpty()) {
264  found = _root.isTagged();
265  if (found) {
266  return _root.getInfo();
267  }
268  } else {
269  // ns is not empty, we search for it in the table
270  found = false;
271  GraphNodeSet::Iterator nodeSetIt = ns.begin();
272 
273  NdElement * currentNodeElement = &_root;
274  while (nodeSetIt != ns.end() && (currentNodeElement != nullptr)) {
275  currentNodeElement = currentNodeElement->getChild(*nodeSetIt);
276  ++nodeSetIt;
277  }
278  found = currentNodeElement != nullptr && currentNodeElement->isTagged();
279  if (found) {
280  return currentNodeElement->getInfo();
281  }
282  }
283  return _defaultInfo;
284  }
285 
292  T & getInfo(const GraphNodeSet & ns, bool & found) {
293  if (ns.isEmpty()) {
294  found = _root.isTagged();
295  if (found) {
296  return _root.getInfo();
297  }
298  } else {
299  // ns is not empty, we search for it in the table
300  found = false;
301  GraphNodeSet::Iterator nodeSetIt = ns.begin();
302 
303  NdElement * currentNodeElement = &_root;
304  while (nodeSetIt != ns.end() && (currentNodeElement != nullptr)) {
305  currentNodeElement = currentNodeElement->getChild(*nodeSetIt);
306  ++nodeSetIt;
307  }
308  found = currentNodeElement != nullptr && currentNodeElement->isTagged();
309  if (found) {
310  return currentNodeElement->getInfo();
311  }
312  }
313  return _defaultInfo;
314  }
315 
324  T & insertIfNotFound(const GraphNodeSet & ns,
325  const T & info,
326  bool & found) {
327  if (ns.isEmpty()) {
328  found = _root.isTagged();
329  if (!found) {
330  return _root.setInfo(info);
331  }
332  return _root.getInfo();
333  } else {
334  // ns is not empty, we search for it in the table
335  found = false;
336  GraphNodeSet::Iterator nodeSetIt = ns.begin();
337 
338  NdElement * currentNodeElement = &_root;
339  while (nodeSetIt != ns.end()) {
340  GraphNodeSet::Iterator nextNodeSetIt = nodeSetIt;
341  ++nextNodeSetIt;
342  if (nextNodeSetIt == ns.end()) {
343  currentNodeElement = currentNodeElement->insertChildIfNotFound(*nodeSetIt, found);
344 
345  if (!currentNodeElement->isTagged()) {
346  currentNodeElement->setInfo(info);
347  }
348 
349  } else {
350  currentNodeElement = currentNodeElement->insertChildIfNotFound(*nodeSetIt, found);
351  }
352  ++nodeSetIt;
353  }
354  return currentNodeElement->getInfo();
355  }
356  return _defaultInfo;
357  }
358 
359 
363  //void printTable() const;
364  };
365  };
366 };
367 // private:
368 
369 // /**
370 // * @param ns a GraphNodeSet
371 // * @param it a GraphNodeSetIterator on ns
372 // * @param currentListNode list of NodeElement
373 // * @param nodeIt an iterator on the currentListNode
374 // * @param info an Information to associate with ns
375 // *
376 // * This method is used when the table does not contain 'ns' and insert it.
377 // *
378 // **/
379 // T & insertNs(const GraphNodeSet & ns,
380 // GraphNodeSet::Iterator & it,
381 // Children & currentChildren,
382 // typename Children::iterator & nodeIt,
383 // const T & info) {
384 // // auto * currentListNode2 = &currentListNode;
385 // // auto currentNodeIt = nodeIt;
386 // // GraphNodeSet::Iterator nextIt = it;
387 // // GraphNodeSet::Iterator currentStateIt = it;
388 // // while(currentStateIt != ns.end())
389 // // {
390 // // ++nextIt;
391 // //
392 // //
393 // //#ifdef __ASSERT
394 // // int previousSize = currentListNode2->size();
395 // //#endif
396 // // if(nextIt == ns.end())
397 // // {
398 // // currentNodeIt = currentListNode2->emplace(currentNodeIt,new NodeElement<T>(*currentStateIt,info));
399 // // }
400 // // else
401 // // {
402 // // currentNodeIt = currentListNode2->emplace(currentNodeIt,new NodeElement<T>(*currentStateIt));
403 // // }
404 // //
405 // //
406 // //
407 // //
408 // // assertion(Exception, currentListNode2->size() - previousSize == 1,
409 // // "insertNs: the insertion has failed");
410 // // currentListNode2 = &((*currentNodeIt)->children());
411 // // assertion(Exception, currentListNode2->empty(),
412 // // "insertNs: problem of memory managment");
413 // // currentNodeIt = currentListNode2->end();
414 // // ++currentStateIt;
415 // // }
416 // // return (*currentNodeIt)->getInfo();
417 // // }
418 // //
419 // };
420 
421 
422 
423 // template<typename T> const T & GraphNodeSetTable<T>::getInfo(const GraphNodeSet & ns, bool & found) const
424 // {
425 // if(ns.isEmpty())
426 // {
427 // if(_roots.empty() || _roots.front()->node().valid())
428 // {
429 // found = false;
430 // }
431 // else
432 // {
433 // found = true;
434 // return _roots.front()->getInfo();
435 // }
436 // }
437 //
438 // else
439 // {
440 // found = false;
441 // GraphNodeSet::Iterator it = ns.begin();
442 // GraphNodeSet::Iterator nextIt = it;
443 // const Children & currentListNode = _roots;
444 // typename Children::const_iterator currentNodeIt = currentListNode.begin();
445 //
446 // while(it != ns.end())
447 // {
448 // if(currentNodeIt == currentListNode.end())
449 // {
450 // found = false;
451 // }
452 // else
453 // {
454 // NodeElement<T> & currentNode = *currentNodeIt;
455 // if( *it < currentNode.node() )
456 // {
457 // found = false;
458 // }
459 // else
460 // {
461 // if(*it == currentNode.node())
462 // {
463 // nextIt = it;
464 // ++nextIt;
465 // if(nextIt != ns.end())
466 // {
467 // currentListNode = currentNode.children();
468 // currentNodeIt = currentListNode.begin();
469 // }
470 // else
471 // {
472 // found = currentNode.isTagged();
473 // if(found)
474 // {
475 // return currentNode.getInfo();
476 // }
477 // }
478 // ++it;
479 // }
480 // else
481 // {
482 // ++currentNodeIt;
483 // }
484 // }
485 // }
486 // }
487 // }
488 // return _defaultInfo;
489 // }
490 //
491 //
492 // template<class T>
493 // T & GraphNodeSetTable<T>::insertIfNotFound(const GraphNodeSet & ns, const T & info, bool & found)
494 // {
495 // if(ns.isEmpty())
496 // {
497 // if(_roots.empty() || _roots.front()->node().valid())
498 // {
499 // found = false;
500 // _roots.emplace_front(new NodeElement<T>());
501 // _roots.front()->setInfo(info);
502 // }
503 // else
504 // {
505 // found = true;
506 // }
507 // return _roots.front()->getInfo();
508 // }
509 //
510 // else
511 // {
512 // found = false;
513 // GraphNodeSet::Iterator it = ns.begin();
514 // GraphNodeSet::Iterator nextIt = it;
515 // Children * currentListNode = &_roots;
516 // typename Children::iterator currentNodeIt = currentListNode->begin();
517 //
518 // while(it != ns.end())
519 // {
520 // if(currentNodeIt == currentListNode->end())
521 // {
522 // return insertNs(ns,it,*currentListNode,currentNodeIt,info);
523 // }
524 // else
525 // {
526 // NodeElement<T> & currentNode = **currentNodeIt;
527 // if( *it < currentNode.node() )
528 // {
529 // return insertNs(ns,it,*currentListNode,currentNodeIt,info);
530 //
531 // }
532 // else
533 // {
534 // if(*it == currentNode.node())
535 // {
536 // nextIt = it;
537 // ++nextIt;
538 // if(nextIt != ns.end())
539 // {
540 // currentListNode = &currentNode.children();
541 // currentNodeIt = currentListNode->begin();
542 // }
543 // else
544 // {
545 // found = currentNode.isTagged();
546 // if(found)
547 // {
548 // return currentNode.getInfo();
549 // }
550 // else
551 // {
552 // return currentNode.setInfo(info);
553 // }
554 // }
555 // ++it;
556 // }
557 // else
558 // {
559 // ++currentNodeIt;
560 // }
561 // }
562 // }
563 // }
564 // }
565 // return _defaultInfo;
566 // }
567 //
568 //
569 // template<class T>
570 // T & GraphNodeSetTable<T>::insertNs(const GraphNodeSet & ns, GraphNodeSet::Iterator & it,
571 // Children & currentListNode,
572 // typename Children::iterator & nodeIt,
573 // const T & info)
574 // {
575 // auto * currentListNode2 = &currentListNode;
576 // auto currentNodeIt = nodeIt;
577 // GraphNodeSet::Iterator nextIt = it;
578 // GraphNodeSet::Iterator currentStateIt = it;
579 // while(currentStateIt != ns.end())
580 // {
581 // ++nextIt;
582 //
583 //
584 //#ifdef __ASSERT
585 // int previousSize = currentListNode2->size();
586 //#endif
587 // if(nextIt == ns.end())
588 // {
589 // currentNodeIt = currentListNode2->emplace(currentNodeIt,new NodeElement<T>(*currentStateIt,info));
590 // }
591 // else
592 // {
593 // currentNodeIt = currentListNode2->emplace(currentNodeIt,new NodeElement<T>(*currentStateIt));
594 // }
595 //
596 //
597 //
598 //
599 // assertion(Exception, currentListNode2->size() - previousSize == 1,
600 // "insertNs: the insertion has failed");
601 // currentListNode2 = &((*currentNodeIt)->children());
602 // assertion(Exception, currentListNode2->empty(),
603 // "insertNs: problem of memory managment");
604 // currentNodeIt = currentListNode2->end();
605 // ++currentStateIt;
606 // }
607 // return (*currentNodeIt)->getInfo();
608 // }
609 //
665 
666 // };
667 // };
668 
669 #endif /*__DIADES__GRAPH__GRAPHNODESETTABLE__HH__*/
Diades::Graph::GraphNodeSetTable::GraphNodeSetTable
GraphNodeSetTable()
info object that is returned in case an specific info is not found, undetermined value ...
Definition: GraphNodeSetTable.hh:247
Diades::Graph::GraphNodeSetTable::getInfo
const T & getInfo(const GraphNodeSet &ns, bool &found) const
Definition: GraphNodeSetTable.hh:262
Diades::Graph::NodeElement::_inf
T _inf
node of the NodeElement
Definition: GraphNodeSetTable.hh:29
Diades::Graph::Node::valid
bool valid() const
Definition: NodeImpl.hh:23
Diades::Graph::NodeElement::insertChildIfNotFound
NodeElement * insertChildIfNotFound(Node n, bool &found)
Definition: GraphNodeSetTable.hh:165
Diades::Graph::NodeElement::NodeElement
NodeElement(Node n, const T &inf)
Definition: GraphNodeSetTable.hh:62
std
STL namespace.
Diades::Graph::NodeElement::getChild
NodeElement * getChild(Node n)
Definition: GraphNodeSetTable.hh:180
Diades::Graph::GraphNodeSetTable::Exception
Diades::Utils::Exception< GraphNodeSetTable > Exception
Definition: GraphNodeSetTable.hh:235
Diades::Graph::GraphNodeSetTable::Children
typename NodeElement< T >::Children Children
Definition: GraphNodeSetTable.hh:236
Diades::Graph::NodeElement::NodeElement
NodeElement()
list of node children
Definition: GraphNodeSetTable.hh:40
Diades::Graph::GraphNodeSetTable::getInfo
T & getInfo(const GraphNodeSet &ns, bool &found)
Definition: GraphNodeSetTable.hh:292
Diades::Graph::NodeElement::getChild
const NodeElement * getChild(Node n) const
Definition: GraphNodeSetTable.hh:192
Diades::Graph::NodeElement::Exception
Diades::Utils::Exception< NodeElement > Exception
Definition: GraphNodeSetTable.hh:25
Diades::Graph::NodeElement::Children
std::map< Node, std::unique_ptr< NodeElement > > Children
Definition: GraphNodeSetTable.hh:26
require
#define require(Exception, expr, message)
Definition: Assertion.hh:90
Diades
Namespace of the Diades project.
Diades::Graph::GraphNodeSet::Iterator
set< Node >::const_iterator Iterator
Definition: GraphNodeSet.hh:41
Diades::Graph::NodeElement::_tag
bool _tag
informtaion of the NodeElement
Definition: GraphNodeSetTable.hh:30
Graph
boost::adjacency_list Graph
Definition: ScaleFree.cc:9
Diades::Graph::NodeElement::_children
Children _children
is the information there or not ?
Definition: GraphNodeSetTable.hh:31
Diades::Graph::NodeElement::children
const Children & children() const
Definition: GraphNodeSetTable.hh:133
Diades::Graph::GraphNodeSetTable::_defaultInfo
T _defaultInfo
root of the tree, if it is tagged then it encodes the presence of the empty set
Definition: GraphNodeSetTable.hh:240
Diades::Graph::GraphNodeSetTable::insertIfNotFound
T & insertIfNotFound(const GraphNodeSet &ns, const T &info, bool &found)
Definition: GraphNodeSetTable.hh:324
Diades::Graph::NodeElement::node
const Node & node() const
Definition: GraphNodeSetTable.hh:89
Generated on Tue May 12 2020 15:52:04 for DiaDes by   doxygen 1.8.13