Tree.h
1 /*
2 
3 MIT License
4 
5 Copyright (c) 2017 FMI Open Development / Markus Peura, first.last@fmi.fi
6 
7 Permission is hereby granted, free of charge, to any person obtaining a copy
8 of this software and associated documentation files (the "Software"), to deal
9 in the Software without restriction, including without limitation the rights
10 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 copies of the Software, and to permit persons to whom the Software is
12 furnished to do so, subject to the following conditions:
13 
14 The above copyright notice and this permission notice shall be included in all
15 copies or substantial portions of the Software.
16 
17 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 SOFTWARE.
24 
25 */
26 /*
27 Part of Rack development has been done in the BALTRAD projects part-financed
28 by the European Union (European Regional Development Fund and European
29 Neighbourhood Partnership Instrument, Baltic Sea Region Programme 2007-2013)
30 */
31 
32 #ifndef DRAIN_TREE_NAME
33 #warning "Use TreeOrdered.h or TreeUnordered.h to include this file."
34 #endif
35 
36 
37 #include <iterator>
38 #include <string>
39 #include <map>
40 
41 
42 #include <drain/Log.h>
43 #include <drain/Type.h>
44 #include <drain/TypeUtils.h>
45 
46 #include "Path.h"
47 
48 #include "TreeUtils.h"
49 
50 namespace drain {
51 
52 
53 
55 
160 
182 template <class T, bool EXCLUSIVE=false, class P=drain::Path<std::string,'/'> > // , class C=std::less<std::string>
183 class DRAIN_TREE_NAME { // : public AmbiValue<T,typename P::elem_t> { //: public TreeBase {
184 public:
185 
187  typedef T node_data_t;
188  typedef P path_t;
189  typedef typename path_t::elem_t key_t;
190 
191  typedef std::pair<key_t,tree_t> pair_t;
192 
193  typedef DRAIN_TREE_CONTAINER(key_t,tree_t) container_t;
194 
195  typedef typename container_t::iterator iterator;
196  typedef typename container_t::const_iterator const_iterator;
197 
199  inline
200  DRAIN_TREE_NAME(){}; // : separator(separator) {}; //parent(*this),
201 
203  inline
204  DRAIN_TREE_NAME(const node_data_t &data) : data(data){}; //, separator(t.separator) {}; //parent(*this),
205 
207  inline
208  DRAIN_TREE_NAME(const DRAIN_TREE_NAME &t) : data(t.data){}; //, separator(t.separator) {}; //parent(*this),
209 
210  virtual inline
211  ~DRAIN_TREE_NAME(){};
212 
213 
215  node_data_t data;
216 
217 
218  // AMBIVALUED
219  virtual inline
220  bool hasMultipleData() const {
221  // Reteurn false, if own, local data
222  return data.empty();
223  };
224 
225  virtual inline
226  const node_data_t & getData() const {return data;};
227 
228  virtual inline
229  node_data_t & getData(){return data;};
230 
231  virtual inline
232  const node_data_t & getData(const key_t & key) const {
233  return retrieveChild(key).data;
234  };
235 
236  virtual inline
237  node_data_t & getData(const key_t & key){
238  return retrieveChild(key).data;
239  };
240 
241 
242 
244  inline
245  typename container_t::const_iterator begin() const { return children.begin(); };
246 
248  inline
249  typename container_t::const_iterator end() const { return children.end(); };
250 
252  inline
253  typename container_t::iterator begin(){ return children.begin(); };
254 
256  inline
257  typename container_t::iterator end(){ return children.end(); };
258 
259 
260  // REMOVE
261  static inline
262  bool isExclusive(){
263  return EXCLUSIVE;
264  }
265 
266  // REMOVE
267  static inline
268  bool isMulti(){
269  #ifdef DRAIN_TREE_MULTI
270  return true;
271  #else
272  return false;
273  #endif
274  }
275 
276  static inline
277  bool isOrdered(){
278  #ifdef DRAIN_TREE_ORDERED
279  return true;
280  #else
281  return false;
282  #endif
283  }
284 
285  /*
286  static inline
287  const std::string className(){
288  const std::string s = drain::StringBuilder<>(
289  isOrdered()?"Ordered":"Unordered",
290  isMulti()?"Multi":"","Tree",
291  isExclusive()?"(Exclusive)":"",
292  '<', drain::Type::call<drain::simpleName>(typeid(node_data_t)), '>');
293  return s;
294  }
295  */
296 
298 
302  // TODO: what to do with the separator?
303  inline
304  tree_t &operator=(const tree_t &t){
305  if (&t != this){
306  data = t.data;
307  //if (EXCLUSIVE){ ...or consider deep copy?
308  clearChildren();
309  //}
310  }
311  return *this;
312  };
313 
315  // Needed? See next.
316  /* THIS CAUSES PROBLEMS. with int x = tree; vs. tree = x;
317  inline
318  tree_t & operator=(const node_data_t &v){
319  data = v;
320  if (EXCLUSIVE){
321  clearChildren();
322  }
323  return *this;
324  };
325  */
326 
327  template <class S>
328  inline
329  tree_t & operator=(const std::initializer_list<S> &l){
330  data = l;
331  if (EXCLUSIVE){
332  clearChildren();
333  }
334  return *this;
335  }
336 
338  template <class T2>
339  inline
340  tree_t & operator=(const T2 &v){
341  data = v;
342  if (EXCLUSIVE){
343  clearChildren();
344  }
345  return *this;
346  }
347 
349  typedef std::pair<key_t,node_data_t> node_pair_t;
350  inline
351  tree_t & operator<<(const node_pair_t & entry){
352  if (EXCLUSIVE){
353  clearData();
354  }
355  tree_t & child = retrieveChild(entry.first);
356  child.data = entry.second;
357  return child;
358  }
359 
360  inline
361  tree_t & ensureChild(const node_pair_t & entry){
362  if (hasChild(entry.first)){
363  return retrieveChild(entry.first);
364  }
365  else {
366  return (*this << entry);
367  }
368  }
369 
370 
371  inline
372  operator const node_data_t &() const {
373  return data;
374  };
375 
376  inline
377  operator node_data_t &(){
378  return data;
379  };
380 
381 
383  inline
384  tree_t & operator[](const key_t & key){
385  return retrieveChild(key);
386  }
387 
389  inline
390  const tree_t & operator[](const key_t & key) const {
391  return retrieveChild(key);
392  }
393 
394 
396 
402  inline
403  tree_t & operator()(const path_t & path){
404  /*
405  if (superDebug){
406  std::cout << __FILE__ << "tree_t & operator()(const path_t & path)" << '\n';
407  }
408  */
409  return get(path.begin(), path.end());
410  }
411 
413 
421  template <class S>
422  inline
423  tree_t & operator()(const S & arg){
424  return operator()(path_t(arg));
425  }
426 
428 
431  inline
432  tree_t & operator()(const char *arg){
433  return operator()(path_t(arg));
434  // return operator()(std::string(arg));
435  }
436 
438 
444  inline
445  const tree_t & operator()(const path_t & path) const {
446  return get(path.begin(), path.end());
447  }
448 
450  template <class S>
451  inline
452  const tree_t & operator()(const S & arg) const {
453  return operator()(path_t(arg));
454  }
455 
457  inline
458  const tree_t & operator()(const char *arg) const {
459  return operator()(path_t(arg));
460  //return operator()(std::string(arg));
461  }
462 
464 
469  inline
470  void clear(){
471  clearData();
472  clearChildren();
473  };
474 
480  inline
481  void clearData(){
482  // Future option: data.clear() (applies to many stl classes, like strings and containers)
483  data = getEmpty().data;
484  };
485 
487 
492  inline
493  void clearChildren(){ // RAISE/virtualize
494  children.clear();
495  };
496 
497  /*
498  void eraseChild(const key_t & key){
499  children.erase(key);
500  }
501  */
502 
504 
509  // ??-> If an ending slash is included, then groups but no datasets will be erased. (?)
510  void erase(const path_t & path){ // RAISE/virtualize
511 
512  // drain::Logger mout(__FILE__, __FUNCTION__);
513 
514  // Idea: first assign the leaf, and step one back.
515  typename path_t::const_iterator pit = path.end();
516  if (pit == path.begin())
517  return;
518  else {
519  // Move 'it' back one step, to point to the leaf (the last element in chain).
520  --pit;
521 
522  // Safe (identity) if it == path.begin():
523  tree_t & parent = this->get(path.begin(), pit);
524 
525  #ifdef DRAIN_TREE_ORDERED // map
526 
527  // TODO: generalize "find" for find first, etc
528  parent.children.erase(*pit);
529 
530  #else
531 
532  //drain::Logger(__FILE__, __LINE__, __FUNCTION__).error("unimplemented code");
533  for (iterator it = children.begin(); it != children.end(); ++it){
534  if (it->first == *pit){
535  drain::Logger(__FILE__, __LINE__, __FUNCTION__).attention("deleting (one) ", *pit);
536  parent.children.erase(it);
537  return;
538  }
539  }
540 
541 
542  #endif
543 
544  //parent.eraseChild(*it);
545 
546  }
547 
548  }
549 
552  virtual inline
553  const tree_t & getEmpty() const {
554  return emptyNode;
555  }
556 
558  // Note: Current implementation does not check node (data). Could apply:
559  // Ambiguous?
560  virtual inline
561  bool empty() const {
562  // consider #ifdef DRAIN_TREE_SMART_DATA
563  // return (data.empty() && children.empty())
564  // #else
565  // data == defaultNode.data?
566  return (data.empty() && !hasChildren());
567  // endif
568  };
569 
570  inline
571  bool hasChildren() const {
572  return !children.empty();
573  }
574 
576 
589  virtual inline
590  int hasChildren(const key_t &key) const {
591 
592  #ifdef DRAIN_TREE_ORDERED // map
593 
594  if (!isMulti()){
595  return (children.find(key) == children.end()) ? 0 : 1;
596  }
597  // no-break for OrderedMultipleTree
598 
599  #endif
600 
601  // OrderedMultipleTree (passed through from the above #ifdef-#endif)
602  // OrderedMultipleTree
603  // UnorderedMultipleTree
604 
605  size_t count = 0;
606  for (const auto & entry: children){
607  if (entry.first == key){
608  ++count;
609  }
610  }
611  return count;
612 
613  };
614 
616 
624  virtual inline
625  bool hasChild(const key_t &key) const {
626  #ifdef DRAIN_TREE_ORDERED // map
627 
628  return (children.find(key) != children.end());
629 
630  #else
631 
632  for (const auto & entry: children){
633  if (entry.first == key){
634  return true;
635  }
636  }
637  return false;
638 
639  #endif
640  };
641 
642 
643  inline
644  bool hasPath(const path_t & path) const {
645  return hasPath(path.begin(), path.end());
646  }
647 
648  // protect:
649  /*
650  key_t getNewChildKey() const {
651  // Consider error (unimplemented)
652  return key_t();
653  }
654  */
655 
657 
666  virtual
667  tree_t & addChild(const key_t & key = key_t()){ // Added default empty 2024/04
668 
669  if (key.empty()) // Should be exceptional... Warning?
670  return *this;
671 
672  if (EXCLUSIVE)
673  this->clearData();
674 
675  #ifdef DRAIN_TREE_ORDERED
676  iterator it = children.find(key);
677  if (it != children.end()){
678  return it->second;
679  }
680  else {
681  return children.insert(children.begin(), pair_t(key, tree_t()))->second;
682  }
683  //return children[key];
684 
685  #else
686 
687  // Try searching first
688  if (!isMulti()){
689  for (auto & entry: children){
690  if (entry.first == key){
691  return entry.second;
692  }
693  }
694  }
695 
696  // Add:
697  children.push_back(pair_t(key, tree_t()));
698  return children.back().second;
699 
700  #endif
701  };
702 
703 
704  // retrieveChild(key, create ALWAYS / IF_NOT_FOUND
705 
706  virtual
707  tree_t & retrieveChild(const key_t & key){
708 
709  if (key.empty())
710  return *this;
711 
712  // ! if (EXCLUSIVE) this->clearData();
713 
714  #ifdef DRAIN_TREE_ORDERED
715  // Old policy restored; keys must implement empty(), an empty key is indentified to the current node.
716 
717  // return children[key];
718  iterator it = children.find(key);
719  if (it != children.end()){
720  return it->second;
721  }
722  else {
723  return children.insert(children.begin(), pair_t(key, tree_t()))->second;
724  }
725 
726  #else
727 
728  for (auto & entry: children){
729  if (entry.first == key){
730  return entry.second;
731  }
732  }
733  // if (EXCLUSIVE) this->clearData();
734  children.push_back(pair_t(key, tree_t()));
735  return children.back().second;
736 
737  #endif
738  };
739 
740 
741  virtual
742  const tree_t & retrieveChild(const key_t & key) const {
743 
744  if (key.empty())
745  return *this;
746 
747  #ifdef DRAIN_TREE_ORDERED
748  const const_iterator it = children.find(key);
749  if (it != children.end()){
750  return it->second;
751  }
752  #else // traverse
753  for (const auto & entry: children){
754  if (entry.first == key){
755  return entry.second;
756  }
757  }
758  #endif
759 
760  return getEmpty();
761  };
762 
763 
764  // Functions perhaps less relevant ....................................
765 
767 
770  inline
771  container_t & getChildren() { return children; };
772 
774  inline
775  const container_t & getChildren() const { return children; };
776 
777 
778 
779  // New
781  inline
782  const node_data_t *operator->() const {
783  return &data;
784  };
785 
787  inline
788  node_data_t *operator->(){
789  return &data;
790  };
791 
793  inline
794  void swap(tree_t &t){
795  children.swap(t.children);
796  }
797 
798 protected:
799 
800  container_t children;
801 
802  static
803  const tree_t emptyNode;
804 
806 
810  bool hasPath(typename path_t::const_iterator it, typename path_t::const_iterator eit) const {
811 
812  if (it == eit) // empty path
813  return true;
814 
815  const typename path_t::elem_t elem = *it;
816 
817  if (elem.empty())
818  return hasPath(++it, eit);
819  else if (!hasChild(elem))
820  return false;
821 
822  return this->operator [](elem).hasPath(++it, eit);
823 
824  }
825 
827 
829  inline
830  tree_t & get(typename path_t::const_iterator it, typename path_t::const_iterator eit) {
831 
832  // Path empty => self-reference
833  if (it == eit)
834  return *this;
835 
836  // Path element is empty => proceed to next element
837  if (it->empty())
838  return get(++it, eit);
839 
840  tree_t & child = operator[](*it);
841  return child.get(++it, eit);
842 
843  }
844 
845 
846 
848 
851  inline
852  const tree_t & get(typename path_t::const_iterator it, typename path_t::const_iterator eit) const {
853 
854  // Path empty => self-reference
855  if (eit == it) // order, 2023/04
856  return *this;
857 
858  // Path element is empty => skip it (proceed to next element)
859  if (it->empty())
860  return get(++it, eit);
861 
862  // NEW ~faulty? data1/data1/data1/...
863 
864  if (hasChild(*it)){
865  //return retrieveChild(*it); <- ADD <- .get(++it, eit); ?
866  return retrieveChild(*it).get(++it, eit);
867  }
868  else {
869  return getEmpty();
870  }
871 
872  // OLD (limited to map container, reconsider NEW, above!)
873  /*
874  typename tree_t::const_iterator child_it = this->children.find(*it);
875  if (child_it == this->children.end())
876  return getEmpty();
877  else
878  return child_it->second.get(++it, eit);
879  */
880 
881  /*
882  if (!hasChild(*it))
883  return getEmpty();
884  const tree_t & child = operator[](*it); // use find? Or better, direct child[key]
885  //const tree_t & child = this->children[*it]; // use find? Or better, direct child[key] 2023/04
886 
887  return child.get(++it, eit);
888  */
889  }
890 
891 
892 
893 };
894 
895 template <class T, bool EXCLUSIVE, class P>
896 const DRAIN_TREE_NAME<T,EXCLUSIVE, P> DRAIN_TREE_NAME<T,EXCLUSIVE,P>::emptyNode;
897 
898 
899 
900 // Certified.
901 template <class T, bool EXCLUSIVE, class P>
902 struct TypeName<DRAIN_TREE_NAME<T,EXCLUSIVE, P> > {
903 
905 
906  static
907  const std::string & str(){
908 
909  static const std::string name = drain::StringBuilder<>(
910  tree_t::isOrdered()?"Ordered":"Unordered",
911  tree_t::isMulti()?"Multi":"","Tree",
912  tree_t::isExclusive()?"(Exclusive)":"",
913  '<', TypeName<typename tree_t::node_data_t>::str(), '>'); // recursion...
914  //'<', drain::Type::call<drain::simpleName>(typeid(typename tree_t::node_data_t)), '>');
915  return name;
916  }
917 
918  /*
919  static
920  const char* get(){
921  return str().c_str();
922  };
923  */
924 
925 };
926 
927 //template <class F>
928 /* -> JSON?
929 template <class T, bool EXCLUSIVE, class P>
930 inline
931 ReferenceT & link(DRAIN_TREE_NAME<T,EXCLUSIVE, P> &p){
932  try {
933  //this->setPtr(p);
934  }
935  catch (const std::exception & e){
936  // Logger(__FILE__, __LINE__, __FUNCTION__).error("unsupported type: ", drain::TypeName<F>::str()); // , " msg:", e.what()
937  // Logger(__FILE__, __LINE__, __FUNCTION__).error("unsupported type: ", typeid(F).name(), " msg:", e.what());
938  // std::cerr << __FILE__ << ':' << __FUNCTION__ << ": unsupported type: " << typeid(F).name() << std::endl;
939  // throw std::runtime_error("unsupported type");
940  }
941  return *this;
942 }
943 */
944 
945 } // drain::
946 
947 
A templated class for directed rooted trees.
Definition: Tree.h:183
virtual int hasChildren(const key_t &key) const
The number of children with name key.
Definition: Tree.h:590
void clearChildren()
Clears the children of this node. Does not clear data.
Definition: Tree.h:493
void swap(tree_t &t)
Replace children (but no data?)
Definition: Tree.h:794
const tree_t & operator()(const S &arg) const
Returns a descendant if that exists, else returns an empty node. Otherwise like non-const counterpart...
Definition: Tree.h:452
const tree_t & operator()(const path_t &path) const
Returns a descendant if that exists, else returns an empty node. Otherwise like non-const counterpart...
Definition: Tree.h:445
container_t::const_iterator end() const
Child iterator pointing beyond the last child.
Definition: Tree.h:249
node_data_t * operator->()
Fast access to data, applied widely in TreeXML (HTML/SVG)
Definition: Tree.h:788
const node_data_t * operator->() const
Fast access to data, applied widely in TreeXML (HTML/SVG)
Definition: Tree.h:782
container_t & getChildren()
Returns the map containing the children.
Definition: Tree.h:771
node_data_t data
Contents (data) of the node.
Definition: Tree.h:211
container_t::iterator begin()
Child iterator pointing to the first child.
Definition: Tree.h:253
tree_t & operator()(const path_t &path)
Returns a descendant. Creates one if not existing already.
Definition: Tree.h:403
virtual bool empty() const
Check if the tree structure is empty.
Definition: Tree.h:561
const container_t & getChildren() const
Returns the map containing the children.
Definition: Tree.h:775
const tree_t & operator()(const char *arg) const
Redirects the call to operator()(const std::string & arg) .
Definition: Tree.h:458
const tree_t & operator[](const key_t &key) const
Child addressing operator.
Definition: Tree.h:390
tree_t & operator[](const key_t &key)
Child addressing operator.
Definition: Tree.h:384
DRAIN_TREE_NAME(const DRAIN_TREE_NAME &t)
Copy constructor; copy only node data at the root.
Definition: Tree.h:208
tree_t & get(typename path_t::const_iterator it, typename path_t::const_iterator eit)
Returns a descendant. Creates one, if not present.
Definition: Tree.h:830
virtual tree_t & addChild(const key_t &key=key_t())
Add a child node. If unordered and UNIQUE, reuse existing nodes.
Definition: Tree.h:667
bool hasPath(typename path_t::const_iterator it, typename path_t::const_iterator eit) const
Checks if there is a node with a given path name.
Definition: Tree.h:810
void erase(const path_t &path)
Deletes a descendant node and hence its subtrees.
Definition: Tree.h:510
tree_t & operator=(const tree_t &t)
Copies the data of another node. Does not copy the children.
Definition: Tree.h:304
DRAIN_TREE_NAME()
Default constructor.
Definition: Tree.h:200
void clearData()
Definition: Tree.h:481
virtual bool hasChild(const key_t &key) const
Check if the tree node has a direct descendant with name key.
Definition: Tree.h:625
void clear()
Clear children and node data.
Definition: Tree.h:470
std::pair< key_t, node_data_t > node_pair_t
Experimental. Given pair<elem, data> assigns child[elem] = data;.
Definition: Tree.h:349
tree_t & operator()(const S &arg)
Returns a descendant. Creates one if not existing already.
Definition: Tree.h:423
tree_t & operator=(const T2 &v)
Assigns a value to contents.
Definition: Tree.h:340
container_t::const_iterator begin() const
Child iterator pointing to the first child.
Definition: Tree.h:245
container_t::iterator end()
Child iterator end.
Definition: Tree.h:257
DRAIN_TREE_NAME(const node_data_t &data)
Copy constructor; copy only node data at the root.
Definition: Tree.h:204
virtual const tree_t & getEmpty() const
Definition: Tree.h:553
tree_t & operator=(const std::initializer_list< S > &l)
Assigns value to contents.
Definition: Tree.h:329
tree_t & operator()(const char *arg)
Redirects the call to operator()(const std::string & arg) .
Definition: Tree.h:432
const tree_t & get(typename path_t::const_iterator it, typename path_t::const_iterator eit) const
Given the descendant pointed to by a given path segment.
Definition: Tree.h:852
LogSourc e is the means for a function or any program segment to "connect" to a Log.
Definition: Log.h:308
Logger & attention(const TT &... args)
Possible error, but execution can continue. Special type of Logger::warn().
Definition: Log.h:472
Definition: Path.h:112
Definition: StringBuilder.h:58
Definition: DataSelector.cpp:1277
Definition: Type.h:542
static const std::string name
Default implementation: name returned by std::type_info::name()
Definition: Type.h:558