TBTK
Need a break? Support the development by playing Polarity Puzzles
IndexedDataTree.h
Go to the documentation of this file.
1 /* Copyright 2017 Kristofer Björnson
2  *
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
23 #ifndef COM_DAFER45_TBTK_INDEXED_DATA_TREE
24 #define COM_DAFER45_TBTK_INDEXED_DATA_TREE
25 
26 #include "TBTK/ElementNotFoundException.h"
27 #include "TBTK/Index.h"
29 #include "TBTK/Serializable.h"
30 #include "TBTK/TBTKMacros.h"
31 
32 #include <complex>
33 #include <map>
34 #include <sstream>
35 
36 //This is used to work around incompatibilities between nlohmann::json and
37 //CUDA. This effectively forbids instantiation of IndexedDataTree in CUDA code.
38 #ifndef TBTK_DISABLE_NLOHMANN_JSON
39 # include "TBTK/json.hpp"
40 #endif
41 
42 namespace TBTK{
43 
44 template<typename Data>
46 public:
49 
57  IndexedDataTree(const std::string &serialization, Mode mode);
58 
60  virtual ~IndexedDataTree();
61 
67  void add(const Data &data, const Index &index);
68 
77  bool get(Data &data, const Index &index) const;
78 
87  Data& get(const Index &index);
88 
97  const Data& get(const Index &index) const;
98 
100  void clear();
101 
105  unsigned int getSizeInBytes() const;
106 
112  virtual std::string serialize(Mode mode) const;
113 
114  class Iterator;
115  class ConstIterator;
116 private:
119  template<bool isConstIterator>
120  class _Iterator{
121  public:
124  typedef typename std::conditional<
125  isConstIterator,
126  const Data&,
127  Data&
128  >::type DataReferenceType;
129 
131  void operator++();
132 
134  DataReferenceType operator*();
135 
137  bool operator==(const _Iterator &rhs) const;
138 
140  bool operator!=(const _Iterator &rhs) const;
141 
143  const Index& getCurrentIndex() const;
144  private:
147  typedef typename std::conditional<
148  isConstIterator,
149  const IndexedDataTree*,
151  >::type IndexedDataTreePointerType;
152 
154  IndexedDataTreePointerType indexedDataTree;
155 
157  Index currentIndex;
158 
161  _Iterator(IndexedDataTreePointerType indexedDataTree, bool end = false);
162 
164  friend class Iterator;
165  friend class ConstIterator;
166  };
167 public:
170  class Iterator : public _Iterator<false>{
171  private:
172  Iterator(
173  IndexedDataTree *indexedDataTree,
174  bool end = false
175  ) : _Iterator<false>(indexedDataTree, end){};
176 
178  friend class IndexedDataTree;
179  };
180 
183  class ConstIterator : public _Iterator<true>{
184  private:
186  const IndexedDataTree *indexedDataTree,
187  bool end = false
188  ) : _Iterator<true>(indexedDataTree, end){};
189 
191  friend class IndexedDataTree;
192  };
193 
198  Iterator begin();
199 
204  ConstIterator begin() const;
205 
210  ConstIterator cbegin() const;
211 
215  Iterator end();
216 
220  ConstIterator end() const;
221 
225  ConstIterator cend() const;
226 private:
228  std::map<Subindex, IndexedDataTree> children;
229 
232  bool indexIncluded;
233 
237  bool indexSeparator;
238 
240  Data data;
241 
244  void add(const Data &data, const Index& index, unsigned int subindex);
245 
248  bool get(Data &data, const Index& index, unsigned int subindex) const;
249 
252  const Data& get(const Index& index, unsigned int subindex) const;
253 
255  Index getFirstIndex() const;
256 
259  bool getFirstIndex(Index &index) const;
260 
263  Index getNextIndex(const Index &index) const;
264 
268  bool getNextIndex(
269  const Index &currentIndex,
270  Index &nextIndex
271  ) const;
272 };
273 
274 //This is used to work around incompatibilities between nlohmann::json and
275 //CUDA. This effectively forbids instantiation of IndexedDataTree in CUDA code.
276 #ifndef TBTK_DISABLE_NLOHMANN_JSON
277 
278 template<typename Data>
280  indexIncluded = false;
281  indexSeparator = false;
282 }
283 
284 template<typename Data>
286  const std::string &serialization,
287  Mode mode
288 ){
289  TBTKAssert(
290  validate(serialization, "IndexedDataTree", mode),
291  "IndexedDataTree<bool>::IndexedDataTree()",
292  "Unable to parse string as IndexedDataTree<bool> '"
293  << serialization << "'.",
294  ""
295  );
296 
297  switch(mode){
298  case Mode::JSON:
299  {
300  try{
301  nlohmann::json j = nlohmann::json::parse(
302  serialization
303  );
304  indexIncluded = j.at("indexIncluded").get<bool>();
305  indexSeparator = j.at("indexSeparator").get<bool>();
306  data = Serializable::deserialize<Data>(
307  j.at("data").get<std::string>(),
308  mode
309  );
310  nlohmann::json jsonChildren = j.at("children");
311  for(
312  nlohmann::json::const_iterator iterator
313  = jsonChildren.cbegin();
314  iterator != jsonChildren.cend();
315  ++iterator
316  ){
317  children.insert({
318  Subindex(
319  iterator.key(),
320  Serializable::Mode::JSON
321  ),
323  iterator.value().dump(),
324  Serializable::Mode::JSON
325  )
326  });
327  }
328  }
329  catch(nlohmann::json::exception &e){
330  TBTKExit(
331  "IndexedDataTree<bool>::IndexedDataTree()",
332  "Unable to parse string as"
333  << " IndexedDataTree<bool> '"
334  << serialization << "'.",
335  ""
336  );
337  }
338 
339  break;
340  }
341  default:
342  TBTKExit(
343  "IndexedDataTree<Data>::IndexedDataTree()",
344  "Only Serializable::Mode::JSON is supported yet.",
345  ""
346  );
347  }
348 }
349 
350 template<typename Data>
352 }
353 
354 template<typename Data>
355 void IndexedDataTree<Data>::add(const Data &data, const Index &index){
356  add(data, index, 0);
357 }
358 
359 template<typename Data>
361  const Data &data,
362  const Index &index,
363  unsigned int subindex
364 ){
365  if(subindex < index.getSize()){
366  //If the current subindex is not the last, the Index is
367  //propagated to the next node level.
368 
369  //Get current subindex
370  Subindex currentIndex = index.at(subindex);
371 
372  if(currentIndex.isIndexSeparator()){
373  if(children.size() == 0){
374  indexSeparator = true;
375  }
376  else{
377  TBTKAssert(
378  indexSeparator,
379  "IndexedDataTree:add()",
380  "Invalid index '" << index.toString()
381  << "'. Another Index has already been"
382  << " added to the tree that has a"
383  << " conflicting index at the index"
384  << " separator at subindex '"
385  << subindex << "'.",
386  "Note that a separation point between"
387  << " two indices counts as a subindex."
388  );
389  }
390 
391  indexSeparator = false;
392  add(data, index, subindex+1);
393  indexSeparator = true;
394  return;
395  }
396  else{
397  TBTKAssert(
398  !indexSeparator,
399  "IndexedDataTree:add()",
400  "Invalid index '" << index.toString() << "'."
401  << " Another Index has already been added to"
402  << " the tree that has a conflicting index"
403  << " separator at subindex '"
404  << subindex << "'.",
405  "Note that a separation point between two"
406  << " indices counts as a subindex."
407  );
408  }
409 
410  TBTKAssert(
411  currentIndex >= 0,
412  "IndexedDataTree::add()",
413  "Invalid Index. Negative indices not allowed, but the"
414  << "index " << index.toString() << " have a negative"
415  << " index" << " in position " << subindex << ".",
416  "Compound indices such as {{1, 2, 3}, {4, 5, 6}} are"
417  << " separated by IDX_SEPARATOR with the value '"
418  << IDX_SEPARATOR << "' and are" << " represented as {1"
419  << ", 2, 3, " << IDX_SEPARATOR << ", 4, 5, 6}. This is"
420  << " the only allowed instance of negative numbers."
421  );
422 
423  //Error detection:
424  //If the current node has the indexIncluded flag set, another
425  //Index with fewer subindices than the current Index have
426  //previously been added to this node. This is an error because
427  //different number of subindices is only allowed if the Indices
428  //differ in one of their common indices.
429  TBTKAssert(
430  !indexIncluded,
431  "IndexedDataTree::add()",
432  "Incompatible indices. The Index " << index.toString()
433  << " cannot be added because an Index of length "
434  << subindex + 1 << " which exactly agrees with the "
435  << subindex + 1 << " first indices of the current"
436  << " Index has already been added.",
437  ""
438  );
439 
440  children[currentIndex].add(data, index, subindex+1);
441  }
442  else{
443  //If the current subindex is the last, the index is marked as
444  //included.
445 
446  //Error detection:
447  //If children is non-zero, another Data with more subindices
448  //have already been added to this node. This is an error
449  //because different number of subindices is only allowed if the
450  // indices differ in one of their common indices.
451  TBTKAssert(
452  children.size() == 0,
453  "IndexedDataTree::add()",
454  "Incompatible indices. The Index " << index.toString()
455  << " cannot be added because a longer Index which"
456  << " exactly agrees with the current Index in the"
457  << " common indices has already been added.",
458  ""
459  );
460 
461  indexIncluded = true;
462  this->data = data;
463  }
464 }
465 
466 template<typename Data>
467 bool IndexedDataTree<Data>::get(Data &data, const Index &index) const{
468  return get(data, index, 0);
469 }
470 
471 template<typename Data>
473  Data &data,
474  const Index &index,
475  unsigned int subindex
476 ) const{
477  if(subindex < index.getSize()){
478  //If the current subindex is not the last, continue to the next
479  //node level.
480 
481  //Return false because this is a leaf node without the
482  //indexIncluded flag set. This means it must have been added to
483  //pad the parents child vector and not as a consequence of an
484  //actual Index having been associated with the node.
485  if(children.size() == 0 && !indexIncluded)
486  return false;
487 
488  //Get current subindex.
489  Subindex currentIndex = index.at(subindex);
490 
491  if(currentIndex.isIndexSeparator()){
492  if(indexSeparator){
493  return get(data, index, subindex+1);
494  }
495  else{
496  TBTKExit(
497  "IndexedDataTree::get()",
498  "Invalid Index. Found IDX_SEPARATOR at"
499  << " subindex '" << subindex << "',"
500  << " but the node is not an index"
501  << " separator.",
502  ""
503  );
504  }
505  }
506 
507  TBTKAssert(
508  currentIndex >= 0,
509  "IndexedDataTree::add()",
510  "Invalid Index. Negative indices not allowed, but the"
511  << " index " << index.toString() << " have a negative"
512  << " index in position " << subindex << ".",
513  ""
514  );
515 
516  try{
517  return children.at(currentIndex).get(data, index, subindex+1);
518  }
519  catch(std::out_of_range &e){
520  return false;
521  }
522  }
523  else{
524  //If the current subindex is the last, try to extract the data.
525  //Return true if successful but false if the data does not
526  //exist.
527  if(indexIncluded){
528  data = this->data;
529 
530  return true;
531  }
532  else{
533  return false;
534  }
535  }
536 }
537 
538 template<typename Data>
539 Data& IndexedDataTree<Data>::get(const Index &index){
540  //Casting is safe because we do not guarantee that the IndexedDataTree
541  //is not modified. Casting away const from the returned reference is
542  //therefore not a violation of any promisse made by this function.
543  //See also "Avoiding Duplication in const and Non-const Member
544  //Function" in S. Meyers, Effective C++.
545  return const_cast<Data&>(
546  static_cast<const IndexedDataTree<Data>*>(this)->get(index, 0)
547  );
548 }
549 
550 template<typename Data>
551 const Data& IndexedDataTree<Data>::get(const Index &index) const{
552  return get(index, 0);
553 }
554 
555 template<typename Data>
556 const Data& IndexedDataTree<Data>::get(
557  const Index &index,
558  unsigned int subindex
559 ) const{
560  if(subindex < index.getSize()){
561  //If the current subindex is not the last, continue to the next
562  //node level.
563 
564  //Throw ElementNotFoundException if the Index is not included.
565  //This statement is executed if this is a leaf node without the
566  //indexIncluded flag set. This means it must have been added to
567  //pad the parents child vector and not as a consequence of an
568  //actual Index having been associated with the node.
569  if(children.size() == 0 && !indexIncluded){
571  "IndexedDataTree()",
572  TBTKWhere,
573  "Tried to get element with Index '"
574  + index.toString() + "', but no such element"
575  + " exists.",
576  ""
577  );
578  }
579 
580  //Get current subindex.
581  Subindex currentIndex = index.at(subindex);
582 
583  if(currentIndex.isIndexSeparator()){
584  if(indexSeparator){
585  return get(index, subindex+1);
586  }
587  else{
588  TBTKExit(
589  "IndexedDataTree::get()",
590  "Invalid Index. Found IDX_SEPARATOR at"
591  << " subindex '" << subindex << "',"
592  << " but the node is not an index"
593  << " separator.",
594  ""
595  );
596  }
597  }
598 
599  TBTKAssert(
600  currentIndex >= 0,
601  "IndexedDataTree::get()",
602  "Invalid Index. Negative indices not allowed, but the"
603  << "index " << index.toString() << " have a negative"
604  << " index" << " in position " << subindex << ".",
605  "Compound indices such as {{1, 2, 3}, {4, 5, 6}} are"
606  << " separated by IDX_SEPARATOR with the value '"
607  << IDX_SEPARATOR << "' and are" << " represented as {1"
608  << ", 2, 3, " << IDX_SEPARATOR << ", 4, 5, 6}. This is"
609  << " the only allowed instance of negative numbers."
610  );
611 
612  try{
613  return children.at(currentIndex).get(index, subindex+1);
614  }
615  catch(std::out_of_range &e){
616  throw ElementNotFoundException(
617  "IndexedDataTree()",
618  TBTKWhere,
619  "Tried to get element with Index '"
620  + index.toString() + "', but no such element"
621  + " exists.",
622  ""
623  );
624  }
625  }
626  else{
627  //If the current subindex is the last, try to extract the data.
628  //Return data if successful but throw ElementNotFoundException if the
629  //data does not exist.
630  if(indexIncluded){
631  return data;
632  }
633  else{
634  throw ElementNotFoundException(
635  "IndexedDataTree()",
636  TBTKWhere,
637  "Tried to get element with Index '"
638  + index.toString() + "', but no such element"
639  + " exists.",
640  ""
641  );
642  }
643  }
644 }
645 
646 template<typename Data>
647 Index IndexedDataTree<Data>::getFirstIndex() const{
648  Index index;
649  getFirstIndex(index);
650 
651  return index;
652 }
653 
654 template<typename Data>
655 bool IndexedDataTree<Data>::getFirstIndex(Index &index) const{
656  if(indexIncluded)
657  return true;
658 
659  if(indexSeparator)
660  index.pushBack(IDX_SEPARATOR);
661 
662  for(
663  typename std::map<
664  Subindex,
665  IndexedDataTree
666  >::const_iterator iterator = children.cbegin();
667  iterator != children.cend();
668  ++iterator
669  ){
670  Subindex subindex = iterator->first;
671  index.pushBack(subindex);
672  if(iterator->second.getFirstIndex(index))
673  return true;
674 
675  index.popBack();
676  }
677 
678  if(indexSeparator)
679  index.popBack();
680 
681  return false;
682 }
683 
684 template<typename Data>
685 Index IndexedDataTree<Data>::getNextIndex(const Index &index) const{
686  if(index.getSize() == 0)
687  return Index();
688 
689  Index nextIndex;
690  getNextIndex(index, nextIndex);
691 
692  return nextIndex;
693 }
694 
695 template<typename Data>
696 bool IndexedDataTree<Data>::getNextIndex(
697  const Index &currentIndex,
698  Index &nextIndex
699 ) const{
700  if(indexIncluded){
701  if(currentIndex.equals(nextIndex))
702  return false;
703 
704  return true;
705  }
706 
707  if(indexSeparator)
708  nextIndex.pushBack(IDX_SEPARATOR);
709 
710  bool hasSameIndexStructure = true;
711  if(currentIndex.getSize() > nextIndex.getSize()){
712  for(unsigned int n = 0; n < nextIndex.getSize(); n++){
713  if(currentIndex[n] != nextIndex[n]){
714  hasSameIndexStructure = false;
715  break;
716  }
717  }
718  }
719  else{
720  hasSameIndexStructure = false;
721  }
722 
723  typename std::map<Subindex, IndexedDataTree>::const_iterator iterator;
724  if(hasSameIndexStructure)
725  iterator = children.find(currentIndex[nextIndex.getSize()]);
726  else
727  iterator = children.cbegin();
728  while(iterator != children.cend()){
729  nextIndex.pushBack(iterator->first);
730  if(iterator->second.getNextIndex(currentIndex, nextIndex))
731  return true;
732  nextIndex.popBack();
733 
734  ++iterator;
735  }
736 
737  if(indexSeparator)
738  nextIndex.popBack();
739 
740  return false;
741 }
742 
743 template<typename Data>
745  indexIncluded = false;
746  children.clear();
747 }
748 
749 template<typename Data>
751  unsigned int size = sizeof(IndexedDataTree<Data>);
752  for(
753  typename std::map<
754  Subindex,
756  >::const_iterator iterator = children.cbegin();
757  iterator != children.cend();
758  ++iterator
759  ){
760  size += iterator->second.getSizeInBytes();
761  }
762 
763  return size;
764 }
765 
766 template<typename Data>
767 inline std::string IndexedDataTree<Data>::serialize(Mode mode) const{
768  switch(mode){
769  case Mode::JSON:
770  {
771  nlohmann::json j;
772  j["id"] = "IndexedDataTree";
773  j["indexIncluded"] = indexIncluded;
774  j["indexSeparator"] = indexSeparator;
775  j["data"] = Serializable::serialize(data, mode);
776  j["children"] = nlohmann::json();
777  for(
778  typename std::map<
779  Subindex,
781  >::const_iterator iterator = children.cbegin();
782  iterator != children.cend();
783  ++iterator
784  ){
785  j["children"][
786  iterator->first.serialize(
787  Serializable::Mode::JSON
788  )
789  ] = nlohmann::json::parse(
790  iterator->second.serialize(
791  Serializable::Mode::JSON
792  )
793  );
794  }
795 
796  return j.dump();
797  }
798  default:
799  TBTKExit(
800  "IndexedDataTree<Data>::serialize()",
801  "Only Serializable::Mode::JSON is supported yet.",
802  ""
803  );
804  }
805 }
806 
807 template<typename Data>
809  return Iterator(this);
810 }
811 
812 template<typename Data>
814  Data
815 >::begin() const{
816  return ConstIterator(this);
817 }
818 
819 template<typename Data>
820 typename IndexedDataTree<Data>::ConstIterator IndexedDataTree<
821  Data
822 >::cbegin() const{
823  return ConstIterator(this);
824 }
825 
826 template<typename Data>
828  return Iterator(this, true);
829 }
830 
831 template<typename Data>
833  return ConstIterator(this, true);
834 }
835 
836 template<typename Data>
838  return ConstIterator(this, true);
839 }
840 
841 template<typename Data> template<bool isConstIterator>
843  currentIndex = indexedDataTree->getNextIndex(currentIndex);
844 }
845 
846 template<typename Data> template<bool isConstIterator>
847 typename IndexedDataTree<Data>::template _Iterator<
848  isConstIterator
849 >::DataReferenceType IndexedDataTree<Data>::_Iterator<
850  isConstIterator
851 >::operator*(){
852  return indexedDataTree->get(currentIndex);
853 }
854 
855 template<typename Data> template<bool isConstIterator>
856 bool IndexedDataTree<Data>::_Iterator<isConstIterator>::operator==(
857  const IndexedDataTree<Data>::_Iterator<isConstIterator> &rhs
858 ) const{
859  if(
860  indexedDataTree == rhs.indexedDataTree
861  && currentIndex.equals(rhs.currentIndex)
862  ){
863  return true;
864  }
865  else{
866  return false;
867  }
868 }
869 
870 template<typename Data> template<bool isConstIterator>
871 bool IndexedDataTree<Data>::_Iterator<isConstIterator>::operator!=(
872  const IndexedDataTree<Data>::_Iterator<isConstIterator> &rhs
873 ) const{
874  if(
875  indexedDataTree != rhs.indexedDataTree
876  || !currentIndex.equals(rhs.currentIndex)
877  ){
878  return true;
879  }
880  else{
881  return false;
882  }
883 }
884 
885 template<typename Data> template<bool isConstIterator>
886 const Index& IndexedDataTree<Data>::_Iterator<
887  isConstIterator
888 >::getCurrentIndex(
889 ) const{
890  return currentIndex;
891 }
892 
893 template<typename Data> template<bool isConstIterator>
894 IndexedDataTree<Data>::_Iterator<isConstIterator>::_Iterator(
895  IndexedDataTreePointerType indexedDataTree,
896  bool end
897 ){
898  this->indexedDataTree = indexedDataTree;
899  if(end)
900  currentIndex = Index();
901  else
902  currentIndex = indexedDataTree->getFirstIndex();
903 }
904 
905 //This is used to work around incompatibilities between nlohmann::json and
906 //CUDA. This effectively forbids instantiation of IndexedDataTree in CUDA code.
907 #endif
908 
909 }; //End of namesapce TBTK
910 
911 #endif
TBTK::IndexedDataTree::serialize
virtual std::string serialize(Mode mode) const
Definition: IndexedDataTree.h:767
TBTK::IndexedDataTree::~IndexedDataTree
virtual ~IndexedDataTree()
Definition: IndexedDataTree.h:351
TBTK::IndexedDataTree
Definition: IndexedDataTree.h:45
TBTK::IndexedDataTree::add
void add(const Data &data, const Index &index)
Definition: IndexedDataTree.h:355
TBTK::IndexedDataTree::begin
Iterator begin()
Definition: IndexedDataTree.h:808
TBTK::IndexedDataTree::getSizeInBytes
unsigned int getSizeInBytes() const
Definition: IndexedDataTree.h:750
TBTK::IndexedDataTree::cbegin
ConstIterator cbegin() const
Definition: IndexedDataTree.h:822
TBTK::Index::toString
std::string toString() const
Definition: Index.h:349
Index.h
Physical index.
TBTK::Subindex::isIndexSeparator
bool isIndexSeparator() const
Definition: Subindex.h:449
TBTK::IndexedDataTree::Iterator
Definition: IndexedDataTree.h:170
TBTK::IndexedDataTree::end
Iterator end()
Definition: IndexedDataTree.h:827
TBTK::IndexedDataTree::get
bool get(Data &data, const Index &index) const
Definition: IndexedDataTree.h:467
TBTK::Serializable::serialize
virtual std::string serialize(Mode mode) const =0
TBTK::Serializable
Definition: Serializable.h:43
TBTK::ElementNotFoundException
Definition: ElementNotFoundException.h:10
TBTK::operator!=
bool operator!=(const IndexTree &lhs, const IndexTree &rhs)
Definition: IndexTree.h:391
Serializable.h
Abstract base class for serializable objects.
TBTK::IndexedDataTree::clear
void clear()
Definition: IndexedDataTree.h:744
TBTK::IndexedDataTree::IndexedDataTree
IndexedDataTree()
Definition: IndexedDataTree.h:279
TBTK::IndexedDataTree::ConstIterator
Definition: IndexedDataTree.h:183
TBTK::Subindex
An entry in an Index.
Definition: Subindex.h:91
TBTKMacros.h
Precompiler macros.
PseudoSerializable.h
Base class for psudo-serializable objects.
TBTK::operator*
const Vector2d operator*(double lhs, const Vector2d &rhs)
Definition: Vector2d.h:129
TBTK::Index::getSize
unsigned int getSize() const
Definition: Index.h:482
TBTK::Index::at
Subindex & at(unsigned int n)
Definition: Index.h:474
TBTK::Serializable::Mode
Mode
Definition: Serializable.h:47
TBTK::Index
Physical index.
Definition: Index.h:44
TBTK::IndexedDataTree::cend
ConstIterator cend() const
Definition: IndexedDataTree.h:837