TBTK
HoppingAmplitudeTree.h
Go to the documentation of this file.
1 /* Copyright 2016 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 
24 #ifndef COM_DAFER45_TBTK_TREE_NODE
25 #define COM_DAFER45_TBTK_TREE_NODE
26 
27 #include "TBTK/HoppingAmplitude.h"
28 #include "TBTK/IndexTree.h"
29 #include "TBTK/Serializable.h"
30 
31 #include <vector>
32 
33 namespace TBTK{
34 
40 class HoppingAmplitudeTree : virtual public Serializable{
41 public:
44 
54  const std::vector<unsigned int> &capacity
55  );
56 
64  HoppingAmplitudeTree(const std::string &serialization, Mode mode);
65 
67  virtual ~HoppingAmplitudeTree();
68 
72  void add(HoppingAmplitude ha);
73 
78  int getBasisSize() const;
79 
98  HoppingAmplitudeTree* getSubTree(const Index &subspace);
99 
118  const HoppingAmplitudeTree* getSubTree(const Index &subspace) const;
119 
144  bool isProperSubspace(const Index &subspace) const;
145 
150 
156  Index getSubspaceIndex(const Index &index) const;
157 
164  int getFirstIndexInSubspace(const Index &subspaceIndex) const;
165 
172  int getLastIndexInSubspace(const Index &subspaceIndex) const;
173 
181  const std::vector<HoppingAmplitude>& getHoppingAmplitudes(
182  Index index
183  ) const;
184 
193  int getBasisIndex(const Index &index) const;
194 
202  Index getPhysicalIndex(int basisIndex) const;
203 
206  void generateBasisIndices();
207 
217  std::vector<Index> getIndexList(const Index &pattern) const;
218 
220  void sort(HoppingAmplitudeTree *rootNode);
221 
224  void print();
225 
226  class Iterator;
227  class ConstIterator;
228 private:
232  template<bool isConstIterator>
233  class _Iterator{
234  public:
237  typedef typename std::conditional<
238  isConstIterator,
239  const HoppingAmplitude&,
240  HoppingAmplitude&
241  >::type HoppingAmplitudeReferenceType;
242 
244  void operator++();
245 
247  HoppingAmplitudeReferenceType operator*();
248 
250  bool operator==(const _Iterator &rhs) const;
251 
253  bool operator!=(const _Iterator &rhs) const;
254 
256  int getMinBasisIndex() const;
257 
259  int getMaxBasisIndex() const;
260 
262  int getNumBasisIndices() const;
263  private:
266  typedef typename std::conditional<
267  isConstIterator,
268  const HoppingAmplitudeTree*,
269  HoppingAmplitudeTree*
270  >::type HoppingAmplitudeTreePointerType;
271 
273  HoppingAmplitudeTreePointerType tree;
274 
276  std::vector<int> currentIndex;
277 
280  int currentHoppingAmplitude;
281 
283  friend class Iterator;
284  friend class ConstIterator;
285 
287  _Iterator(HoppingAmplitudeTreePointerType tree, bool end = false);
288 
292  bool searchNext(
293  HoppingAmplitudeTreePointerType hoppingAmplitudeTree,
294  int subindex
295  );
296  };
297 public:
300  class Iterator : public _Iterator<false>{
301  private:
302  Iterator(
303  HoppingAmplitudeTree *hoppingAmplitudeTree,
304  bool end = false
305  ) : _Iterator<false>(hoppingAmplitudeTree, end){};
306 
309  friend class HoppingAmplitudeTree;
310  };
311 
314  class ConstIterator : public _Iterator<true>{
315  private:
317  const HoppingAmplitudeTree *hoppingAmplitudeTree,
318  bool end = false
319  ) : _Iterator<true>(hoppingAmplitudeTree, end){};
320 
323  friend class HoppingAmplitudeTree;
324  };
325 
330  Iterator begin();
331 
336  ConstIterator begin() const;
337 
342  ConstIterator cbegin() const;
343 
348  Iterator end();
349 
354  ConstIterator end() const;
355 
360  ConstIterator cend() const;
361 
367  virtual std::string serialize(Mode mode) const;
368 
372  unsigned int getSizeInBytes() const;
373 private:
375  int basisIndex;
376 
378  int basisSize;
379 
396  bool isPotentialBlockSeparator;
397 
401  std::vector<HoppingAmplitude> hoppingAmplitudes;
402 
405  std::vector<HoppingAmplitudeTree> children;
406 
409  static const HoppingAmplitudeTree emptyTree;
410 
413  void _add(HoppingAmplitude &ha, unsigned int subindex);
414 
418  const Index &subspace,
419  unsigned int subindex
420  ) const;
421 
425  bool _isProperSubspace(
426  const Index &subspace,
427  unsigned int subindex
428  ) const;
429 
433  void getBlockIndices(IndexTree &blockIndices, Index index) const;
434 
438  void getBlockIndex(
439  const Index &index,
440  unsigned int subindex,
441  Index &blockIndex
442  ) const;
443 
447  const std::vector<HoppingAmplitude>& _getHoppingAmplitudes(
448  Index index,
449  unsigned int subindex
450  ) const;
451 
455  int _getBasisIndex(const Index &index, unsigned int subindex) const;
456 
460  void _getPhysicalIndex(int basisIndex, std::vector<int> *indices) const;
461 
463  int getMinIndex() const;
464 
466  int getMaxIndex() const;
467 
471  int generateBasisIndices(int i);
472 
476  void print(unsigned int subindex);
477 
480  HoppingAmplitude getFirstHA() const;
481 };
482 
484  return basisSize;
485 }
486 
488  const Index &subspaceIndex
489 ) const{
490  TBTKAssert(
491  isProperSubspace(subspaceIndex),
492  "HoppingAmplitudeTree::getFirstIndexInSubspace()",
493  "The index " << subspaceIndex.toString() << " is not an Index"
494  << " of a proper subspace.",
495  ""
496  );
497 
498  const HoppingAmplitudeTree *subspace = getSubTree(subspaceIndex);
499 
500  return subspace->getMinIndex();
501 }
502 
504  const Index &subspaceIndex
505 ) const{
506  TBTKAssert(
507  isProperSubspace(subspaceIndex),
508  "HoppingAmplitudeTree::getLastIndexInSubspace()",
509  "The index " << subspaceIndex.toString() << " is not an Index"
510  << " of a proper subspace.",
511  ""
512  );
513 
514  const HoppingAmplitudeTree *subspace = getSubTree(subspaceIndex);
515 
516  return subspace->getMaxIndex();
517 }
518 
520  return Iterator(this);
521 }
522 
524  return ConstIterator(this);
525 }
526 
528  return ConstIterator(this);
529 }
530 
532  return Iterator(this, true);
533 }
534 
536  return ConstIterator(this, true);
537 }
538 
540  return ConstIterator(this, true);
541 }
542 
543 inline unsigned int HoppingAmplitudeTree::getSizeInBytes() const{
544  unsigned int size = 0;
545  for(unsigned int n = 0; n < hoppingAmplitudes.size(); n++)
546  size += hoppingAmplitudes[n].getSizeInBytes();
547  for(unsigned int n = 0; n < children.size(); n++)
548  size += children[n].getSizeInBytes();
549 
550  size += (
551  hoppingAmplitudes.capacity() - hoppingAmplitudes.size()
552  )*sizeof(HoppingAmplitude);
553 
554  size += (
555  children.capacity() - children.size()
556  )*sizeof(HoppingAmplitudeTree);
557 
558  return size + sizeof(HoppingAmplitudeTree);
559 }
560 
561 template<bool isConstIterator>
562 HoppingAmplitudeTree::_Iterator<isConstIterator>::_Iterator(
563  HoppingAmplitudeTreePointerType tree,
564  bool end
565 )
566 {
567  if(end){
568  this->tree = tree;
569  if(tree->children.size() == 0){
570  currentHoppingAmplitude = -1;
571  }
572  else{
573  currentIndex.push_back(tree->children.size());
574  currentHoppingAmplitude = -1;
575  }
576  }
577  else{
578  this->tree = tree;
579  if(tree->children.size() == 0){
580  //Handle the special case when the data is stored on the head
581  //node. Can for example be the case when iterating over a
582  //single leaf node.
583  currentHoppingAmplitude = -1;
584  searchNext(tree, -1);
585  }
586  else{
587  currentIndex.push_back(0);
588  currentHoppingAmplitude = -1;
589  searchNext(tree, 0);
590  }
591  }
592 }
593 
594 template<bool isConstIterator>
595 void HoppingAmplitudeTree::_Iterator<isConstIterator>::operator++(){
596  if(tree->children.size() == 0){
597  //Handle the special case when the data is stored on the head
598  //node. Can for example be the case when iterating over a
599  //single leaf node.
600  searchNext(tree, -1);
601  }
602  else{
603  searchNext(tree, 0);
604  }
605 }
606 
607 template<bool isConstIterator>
608 bool HoppingAmplitudeTree::_Iterator<isConstIterator>::searchNext(
609  HoppingAmplitudeTreePointerType hoppingAmplitudeTree,
610  int subindex
611 ){
612  if(subindex+1 == (int)currentIndex.size()){
613  //If the node level corresponding to the current index is
614  //reached, try to execute leaf node actions.
615 
616  if(currentHoppingAmplitude != -1){
617  //The iterator is in the process of iterating over
618  //HoppingAmplitudes on this leaf node. Try to iterate further.
619 
620  currentHoppingAmplitude++;
621  if(currentHoppingAmplitude == (int)hoppingAmplitudeTree->hoppingAmplitudes.size()){
622  //Last HoppingAmplitude already reached. Reset
623  //currentHoppingAmplitude and return false to
624  //indicate that no more HoppingAMplitudes exist
625  //on this node.
626  currentHoppingAmplitude = -1;
627  return false;
628  }
629  else{
630  //Return true to indicate that the next
631  //HoppingAmplitude succesfully has been found.
632  return true;
633  }
634  }
635 
636  //We are here guaranteed that the iterator is not currently in
637  //a state where it is iterating over HoppingAmplitudes on this
638  //node.
639 
640  if(hoppingAmplitudeTree->children.size() == 0){
641  //The node has no children and is therefore either a
642  //leaf node with HoppingAmplitudes stored on it, or an
643  //empty dummy node.
644 
645  if(hoppingAmplitudeTree->hoppingAmplitudes.size() != 0){
646  //There are HoppingAMplitudes on this node,
647  //initialize the iterator to start iterating
648  //over these. Return true to indicate that a
649  //HoppingAmplitude was found.
650  currentHoppingAmplitude = 0;
651  return true;
652  }
653  else{
654  //The node is an empty dymmy node. Return false
655  //to indicate that no more HoppingAmplitudes
656  //exist on this node.
657  return false;
658  }
659  }
660  }
661 
662  //We are here guaranteed that this is not a leaf or dummy node. We know
663  //this because either the tests inside the previous if-statements
664  //failed, or we are iterating through children that already have been
665  //visited on an earlier call to searchNext if the outer if-statement
666  //itself failed.
667 
668  //Perform depth first search for the next HoppingAmplitude. Starts from
669  //the child node reffered to by currentIndex.
670  unsigned int n = currentIndex.at(subindex);
671  while(n < hoppingAmplitudeTree->children.size()){
672  if(subindex+1 == (int)currentIndex.size()){
673  //The deepest point visited so far on this branch has
674  //been reached. Initialize the depth first search for
675  //child n to start from child n's zeroth child.
676  currentIndex.push_back(0);
677  }
678  if(searchNext(&hoppingAmplitudeTree->children.at(n), subindex+1)){
679  //Depth first search on child n succeded at finding a
680  //HoppingAmplitude. Return true to indicate success.
681  return true;
682  }
683  //Child n does not have any more HoppingAmplitudes. Pop
684  //the subindex corresponding to child n's node level and
685  //increment the subindex corresponding to this node level to
686  //prepare for depth first search of child n+1.
687  currentIndex.pop_back();
688  n = ++currentIndex.back();
689  }
690 
691  //Return false to indicate that no more HoppingAmplitudes could be
692  //found on this node.
693  return false;
694 }
695 
696 template<bool isConstIterator>
697 typename HoppingAmplitudeTree::_Iterator<
698  isConstIterator
699 >::HoppingAmplitudeReferenceType HoppingAmplitudeTree::_Iterator<
700  isConstIterator
701 >::operator*(){
702  if(currentIndex.size() == 0){
703  //Handle the special case when the data is stored on the head
704  //node. Can for example be the case when iterating over a
705  //single leaf node.
706  if(currentHoppingAmplitude == -1){
707  TBTKExit(
708  "HoppingAmplitudeTree::_Iterator::operator*()",
709  "Out of range access. Tried to access an"
710  << " element using an iterator that points"
711  << " beyond the last element.",
712  ""
713  );
714  }
715  else{
716  return tree->hoppingAmplitudes.at(currentHoppingAmplitude);
717  }
718  }
719 
720  if(currentIndex.at(0) == (int)tree->children.size()){
721  TBTKExit(
722  "HoppingAmplitudeTree::_Iterator::operator*()",
723  "Out of range access. Tried to access an"
724  << " element using an iterator that points"
725  << " beyond the last element.",
726  ""
727  );
728  }
729  const HoppingAmplitudeTree *tn = this->tree;
730  for(unsigned int n = 0; n < currentIndex.size()-1; n++){
731  tn = &tn->children.at(currentIndex.at(n));
732  }
733 
734  return tn->hoppingAmplitudes.at(currentHoppingAmplitude);
735 }
736 
737 template<bool isConstIterator>
738 bool HoppingAmplitudeTree::_Iterator<isConstIterator>::operator==(const _Iterator &rhs) const{
739  if(
740  this->tree == rhs.tree
741  && currentIndex.size() == rhs.currentIndex.size()
742  ){
743  for(unsigned int n = 0; n < currentIndex.size(); n++){
744  if(currentIndex[n] != rhs.currentIndex[n])
745  return false;
746  }
747 
748  if(currentHoppingAmplitude == rhs.currentHoppingAmplitude)
749  return true;
750  else
751  return false;
752  }
753  else{
754  return false;
755  }
756 }
757 
758 template<bool isConstIterator>
759 bool HoppingAmplitudeTree::_Iterator<isConstIterator>::operator!=(
760  const _Iterator &rhs
761 ) const{
762  return !operator==(rhs);
763 }
764 
765 template<bool isConstIterator>
766 int HoppingAmplitudeTree::_Iterator<isConstIterator>::getMinBasisIndex() const{
767  return tree->getMinIndex();
768 }
769 
770 template<bool isConstIterator>
771 int HoppingAmplitudeTree::_Iterator<isConstIterator>::getMaxBasisIndex() const{
772  return tree->getMaxIndex();
773 }
774 
775 template<bool isConstIterator>
776 int HoppingAmplitudeTree::_Iterator<isConstIterator>::getNumBasisIndices(
777 ) const{
778  if(getMaxBasisIndex() == -1)
779  return 0;
780  else
781  return 1 + getMaxBasisIndex() - getMinBasisIndex();
782 }
783 
784 }; //End of namespace TBTK
785 
786 #endif
ConstIterator cbegin() const
Definition: HoppingAmplitudeTree.h:527
FockStateRuleSet operator*(const LadderOperator< BitRegister > &ladderOperator, const FockStateRuleSet &fockStateRuleSet)
Definition: FockStateRuleSet.h:103
Node in tree used by HoppingAmplitudeSet to store HoppingAmplitudes .
Definition: HoppingAmplitudeTree.h:40
std::vector< Index > getIndexList(const Index &pattern) const
int getLastIndexInSubspace(const Index &subspaceIndex) const
Definition: HoppingAmplitudeTree.h:503
Index getSubspaceIndex(const Index &index) const
Hopping amplitude from state &#39;from&#39; to state &#39;to&#39;.
ConstIterator cend() const
Definition: HoppingAmplitudeTree.h:539
Definition: Serializable.h:40
int getFirstIndexInSubspace(const Index &subspaceIndex) const
Definition: HoppingAmplitudeTree.h:487
Data structure for mapping physical indices to a linear index.
void add(HoppingAmplitude ha)
int getBasisSize() const
Definition: HoppingAmplitudeTree.h:483
Index getPhysicalIndex(int basisIndex) const
const std::vector< HoppingAmplitude > & getHoppingAmplitudes(Index index) const
HoppingAmplitudeTree * getSubTree(const Index &subspace)
Definition: HoppingAmplitudeTree.h:300
unsigned int getSizeInBytes() const
Definition: HoppingAmplitudeTree.h:543
Hopping amplitude from state &#39;from&#39; to state &#39;to&#39;.
Definition: HoppingAmplitude.h:49
Iterator begin()
Definition: HoppingAmplitudeTree.h:519
bool isProperSubspace(const Index &subspace) const
Data structure for mapping physical indices to linear indices.
Definition: IndexTree.h:34
Flexible physical index.
Definition: Index.h:69
Iterator end()
Definition: HoppingAmplitudeTree.h:531
Definition: ModelFactory.h:35
Definition: HoppingAmplitudeTree.h:314
void sort(HoppingAmplitudeTree *rootNode)
Mode
Definition: Serializable.h:44
virtual std::string serialize(Mode mode) const
IndexTree getSubspaceIndices() const
int getBasisIndex(const Index &index) const
Abstract base class for serializable objects.
std::string toString() const
Definition: Index.h:282