TBTK
Need a break? Support the development by playing Polarity Puzzles
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 
228  std::vector<Index> getIndexListMultiplePatterns(
229  const std::vector<Index> &patterns
230  ) const;
231 
233  void sort(HoppingAmplitudeTree *rootNode);
234 
237  void print();
238 
239  class Iterator;
240  class ConstIterator;
241 private:
245  template<bool isConstIterator>
246  class _Iterator{
247  public:
250  typedef typename std::conditional<
251  isConstIterator,
252  const HoppingAmplitude&,
253  HoppingAmplitude&
254  >::type HoppingAmplitudeReferenceType;
255 
257  void operator++();
258 
260  HoppingAmplitudeReferenceType operator*();
261 
263  bool operator==(const _Iterator &rhs) const;
264 
266  bool operator!=(const _Iterator &rhs) const;
267 
269  int getMinBasisIndex() const;
270 
272  int getMaxBasisIndex() const;
273 
275  int getNumBasisIndices() const;
276  private:
279  typedef typename std::conditional<
280  isConstIterator,
281  const HoppingAmplitudeTree*,
282  HoppingAmplitudeTree*
283  >::type HoppingAmplitudeTreePointerType;
284 
286  HoppingAmplitudeTreePointerType tree;
287 
289  std::vector<int> currentIndex;
290 
293  int currentHoppingAmplitude;
294 
296  friend class Iterator;
297  friend class ConstIterator;
298 
300  _Iterator(HoppingAmplitudeTreePointerType tree, bool end = false);
301 
305  bool searchNext(
306  HoppingAmplitudeTreePointerType hoppingAmplitudeTree,
307  int subindex
308  );
309  };
310 public:
313  class Iterator : public _Iterator<false>{
314  private:
315  Iterator(
316  HoppingAmplitudeTree *hoppingAmplitudeTree,
317  bool end = false
318  ) : _Iterator<false>(hoppingAmplitudeTree, end){};
319 
322  friend class HoppingAmplitudeTree;
323  };
324 
327  class ConstIterator : public _Iterator<true>{
328  private:
330  const HoppingAmplitudeTree *hoppingAmplitudeTree,
331  bool end = false
332  ) : _Iterator<true>(hoppingAmplitudeTree, end){};
333 
336  friend class HoppingAmplitudeTree;
337  };
338 
343  Iterator begin();
344 
349  ConstIterator begin() const;
350 
355  ConstIterator cbegin() const;
356 
361  Iterator end();
362 
367  ConstIterator end() const;
368 
373  ConstIterator cend() const;
374 
380  virtual std::string serialize(Mode mode) const;
381 
385  unsigned int getSizeInBytes() const;
386 private:
388  int basisIndex;
389 
391  int basisSize;
392 
409  bool isPotentialBlockSeparator;
410 
414  std::vector<HoppingAmplitude> hoppingAmplitudes;
415 
418  std::vector<HoppingAmplitudeTree> children;
419 
422  static const HoppingAmplitudeTree emptyTree;
423 
426  void _add(HoppingAmplitude &ha, unsigned int subindex);
427 
431  const Index &subspace,
432  unsigned int subindex
433  ) const;
434 
438  bool _isProperSubspace(
439  const Index &subspace,
440  unsigned int subindex
441  ) const;
442 
446  void getBlockIndices(IndexTree &blockIndices, Index index) const;
447 
451  void getBlockIndex(
452  const Index &index,
453  unsigned int subindex,
454  Index &blockIndex
455  ) const;
456 
460  const std::vector<HoppingAmplitude>& _getHoppingAmplitudes(
461  Index index,
462  unsigned int subindex
463  ) const;
464 
468  int _getBasisIndex(const Index &index, unsigned int subindex) const;
469 
473  void _getPhysicalIndex(int basisIndex, std::vector<Subindex> &indices) const;
474 
476  int getMinIndex() const;
477 
479  int getMaxIndex() const;
480 
484  int generateBasisIndices(int i);
485 
489  void print(unsigned int subindex);
490 
493  HoppingAmplitude getFirstHA() const;
494 };
495 
497  return basisSize;
498 }
499 
501  const Index &subspaceIndex
502 ) const{
503  TBTKAssert(
504  isProperSubspace(subspaceIndex),
505  "HoppingAmplitudeTree::getFirstIndexInSubspace()",
506  "The index " << subspaceIndex.toString() << " is not an Index"
507  << " of a proper subspace.",
508  ""
509  );
510 
511  const HoppingAmplitudeTree *subspace = getSubTree(subspaceIndex);
512 
513  return subspace->getMinIndex();
514 }
515 
517  const Index &subspaceIndex
518 ) const{
519  TBTKAssert(
520  isProperSubspace(subspaceIndex),
521  "HoppingAmplitudeTree::getLastIndexInSubspace()",
522  "The index " << subspaceIndex.toString() << " is not an Index"
523  << " of a proper subspace.",
524  ""
525  );
526 
527  const HoppingAmplitudeTree *subspace = getSubTree(subspaceIndex);
528 
529  return subspace->getMaxIndex();
530 }
531 
533  return Iterator(this);
534 }
535 
537  return ConstIterator(this);
538 }
539 
541  return ConstIterator(this);
542 }
543 
545  return Iterator(this, true);
546 }
547 
549  return ConstIterator(this, true);
550 }
551 
553  return ConstIterator(this, true);
554 }
555 
556 inline unsigned int HoppingAmplitudeTree::getSizeInBytes() const{
557  unsigned int size = 0;
558  for(unsigned int n = 0; n < hoppingAmplitudes.size(); n++)
559  size += hoppingAmplitudes[n].getSizeInBytes();
560  for(unsigned int n = 0; n < children.size(); n++)
561  size += children[n].getSizeInBytes();
562 
563  size += (
564  hoppingAmplitudes.capacity() - hoppingAmplitudes.size()
565  )*sizeof(HoppingAmplitude);
566 
567  size += (
568  children.capacity() - children.size()
569  )*sizeof(HoppingAmplitudeTree);
570 
571  return size + sizeof(HoppingAmplitudeTree);
572 }
573 
574 template<bool isConstIterator>
575 HoppingAmplitudeTree::_Iterator<isConstIterator>::_Iterator(
576  HoppingAmplitudeTreePointerType tree,
577  bool end
578 )
579 {
580  if(end){
581  this->tree = tree;
582  if(tree->children.size() == 0){
583  currentHoppingAmplitude = -1;
584  }
585  else{
586  currentIndex.push_back(tree->children.size());
587  currentHoppingAmplitude = -1;
588  }
589  }
590  else{
591  this->tree = tree;
592  if(tree->children.size() == 0){
593  //Handle the special case when the data is stored on the head
594  //node. Can for example be the case when iterating over a
595  //single leaf node.
596  currentHoppingAmplitude = -1;
597  searchNext(tree, -1);
598  }
599  else{
600  currentIndex.push_back(0);
601  currentHoppingAmplitude = -1;
602  searchNext(tree, 0);
603  }
604  }
605 }
606 
607 template<bool isConstIterator>
608 void HoppingAmplitudeTree::_Iterator<isConstIterator>::operator++(){
609  if(tree->children.size() == 0){
610  //Handle the special case when the data is stored on the head
611  //node. Can for example be the case when iterating over a
612  //single leaf node.
613  searchNext(tree, -1);
614  }
615  else{
616  searchNext(tree, 0);
617  }
618 }
619 
620 template<bool isConstIterator>
621 bool HoppingAmplitudeTree::_Iterator<isConstIterator>::searchNext(
622  HoppingAmplitudeTreePointerType hoppingAmplitudeTree,
623  int subindex
624 ){
625  if(subindex+1 == (int)currentIndex.size()){
626  //If the node level corresponding to the current index is
627  //reached, try to execute leaf node actions.
628 
629  if(currentHoppingAmplitude != -1){
630  //The iterator is in the process of iterating over
631  //HoppingAmplitudes on this leaf node. Try to iterate further.
632 
633  currentHoppingAmplitude++;
634  if(currentHoppingAmplitude == (int)hoppingAmplitudeTree->hoppingAmplitudes.size()){
635  //Last HoppingAmplitude already reached. Reset
636  //currentHoppingAmplitude and return false to
637  //indicate that no more HoppingAMplitudes exist
638  //on this node.
639  currentHoppingAmplitude = -1;
640  return false;
641  }
642  else{
643  //Return true to indicate that the next
644  //HoppingAmplitude succesfully has been found.
645  return true;
646  }
647  }
648 
649  //We are here guaranteed that the iterator is not currently in
650  //a state where it is iterating over HoppingAmplitudes on this
651  //node.
652 
653  if(hoppingAmplitudeTree->children.size() == 0){
654  //The node has no children and is therefore either a
655  //leaf node with HoppingAmplitudes stored on it, or an
656  //empty dummy node.
657 
658  if(hoppingAmplitudeTree->hoppingAmplitudes.size() != 0){
659  //There are HoppingAMplitudes on this node,
660  //initialize the iterator to start iterating
661  //over these. Return true to indicate that a
662  //HoppingAmplitude was found.
663  currentHoppingAmplitude = 0;
664  return true;
665  }
666  else{
667  //The node is an empty dymmy node. Return false
668  //to indicate that no more HoppingAmplitudes
669  //exist on this node.
670  return false;
671  }
672  }
673  }
674 
675  //We are here guaranteed that this is not a leaf or dummy node. We know
676  //this because either the tests inside the previous if-statements
677  //failed, or we are iterating through children that already have been
678  //visited on an earlier call to searchNext if the outer if-statement
679  //itself failed.
680 
681  //Perform depth first search for the next HoppingAmplitude. Starts from
682  //the child node reffered to by currentIndex.
683  unsigned int n = currentIndex.at(subindex);
684  while(n < hoppingAmplitudeTree->children.size()){
685  if(subindex+1 == (int)currentIndex.size()){
686  //The deepest point visited so far on this branch has
687  //been reached. Initialize the depth first search for
688  //child n to start from child n's zeroth child.
689  currentIndex.push_back(0);
690  }
691  if(searchNext(&hoppingAmplitudeTree->children.at(n), subindex+1)){
692  //Depth first search on child n succeded at finding a
693  //HoppingAmplitude. Return true to indicate success.
694  return true;
695  }
696  //Child n does not have any more HoppingAmplitudes. Pop
697  //the subindex corresponding to child n's node level and
698  //increment the subindex corresponding to this node level to
699  //prepare for depth first search of child n+1.
700  currentIndex.pop_back();
701  n = ++currentIndex.back();
702  }
703 
704  //Return false to indicate that no more HoppingAmplitudes could be
705  //found on this node.
706  return false;
707 }
708 
709 template<bool isConstIterator>
710 typename HoppingAmplitudeTree::_Iterator<
711  isConstIterator
712 >::HoppingAmplitudeReferenceType HoppingAmplitudeTree::_Iterator<
713  isConstIterator
714 >::operator*(){
715  if(currentIndex.size() == 0){
716  //Handle the special case when the data is stored on the head
717  //node. Can for example be the case when iterating over a
718  //single leaf node.
719  if(currentHoppingAmplitude == -1){
720  TBTKExit(
721  "HoppingAmplitudeTree::_Iterator::operator*()",
722  "Out of range access. Tried to access an"
723  << " element using an iterator that points"
724  << " beyond the last element.",
725  ""
726  );
727  }
728  else{
729  return tree->hoppingAmplitudes.at(currentHoppingAmplitude);
730  }
731  }
732 
733  if(currentIndex.at(0) == (int)tree->children.size()){
734  TBTKExit(
735  "HoppingAmplitudeTree::_Iterator::operator*()",
736  "Out of range access. Tried to access an"
737  << " element using an iterator that points"
738  << " beyond the last element.",
739  ""
740  );
741  }
742  const HoppingAmplitudeTree *tn = this->tree;
743  for(unsigned int n = 0; n < currentIndex.size()-1; n++){
744  tn = &tn->children.at(currentIndex.at(n));
745  }
746 
747  return tn->hoppingAmplitudes.at(currentHoppingAmplitude);
748 }
749 
750 template<bool isConstIterator>
751 bool HoppingAmplitudeTree::_Iterator<isConstIterator>::operator==(const _Iterator &rhs) const{
752  if(
753  this->tree == rhs.tree
754  && currentIndex.size() == rhs.currentIndex.size()
755  ){
756  for(unsigned int n = 0; n < currentIndex.size(); n++){
757  if(currentIndex[n] != rhs.currentIndex[n])
758  return false;
759  }
760 
761  if(currentHoppingAmplitude == rhs.currentHoppingAmplitude)
762  return true;
763  else
764  return false;
765  }
766  else{
767  return false;
768  }
769 }
770 
771 template<bool isConstIterator>
772 bool HoppingAmplitudeTree::_Iterator<isConstIterator>::operator!=(
773  const _Iterator &rhs
774 ) const{
775  return !operator==(rhs);
776 }
777 
778 template<bool isConstIterator>
779 int HoppingAmplitudeTree::_Iterator<isConstIterator>::getMinBasisIndex() const{
780  return tree->getMinIndex();
781 }
782 
783 template<bool isConstIterator>
784 int HoppingAmplitudeTree::_Iterator<isConstIterator>::getMaxBasisIndex() const{
785  return tree->getMaxIndex();
786 }
787 
788 template<bool isConstIterator>
789 int HoppingAmplitudeTree::_Iterator<isConstIterator>::getNumBasisIndices(
790 ) const{
791  if(getMaxBasisIndex() == -1)
792  return 0;
793  else
794  return 1 + getMaxBasisIndex() - getMinBasisIndex();
795 }
796 
797 }; //End of namespace TBTK
798 
799 #endif
int getFirstIndexInSubspace(const Index &subspaceIndex) const
Definition: HoppingAmplitudeTree.h:500
std::vector< Index > getIndexList(const Index &pattern) const
Node in tree used by HoppingAmplitudeSet to store HoppingAmplitudes .
Definition: HoppingAmplitudeTree.h:40
unsigned int getSizeInBytes() const
Definition: HoppingAmplitudeTree.h:556
const std::vector< HoppingAmplitude > & getHoppingAmplitudes(Index index) const
Hopping amplitude from state &#39;from&#39; to state &#39;to&#39;.
Definition: Serializable.h:43
int getLastIndexInSubspace(const Index &subspaceIndex) const
Definition: HoppingAmplitudeTree.h:516
int getBasisSize() const
Definition: HoppingAmplitudeTree.h:496
Data structure for mapping physical indices to a linear index.
virtual std::string serialize(Mode mode) const
void add(HoppingAmplitude ha)
std::string toString() const
Definition: Index.h:349
Index getSubspaceIndex(const Index &index) const
ConstIterator cbegin() const
Definition: HoppingAmplitudeTree.h:540
std::vector< Index > getIndexListMultiplePatterns(const std::vector< Index > &patterns) const
int getBasisIndex(const Index &index) const
ConstIterator cend() const
Definition: HoppingAmplitudeTree.h:552
HoppingAmplitudeTree * getSubTree(const Index &subspace)
Definition: HoppingAmplitudeTree.h:313
bool isProperSubspace(const Index &subspace) const
Hopping amplitude from state &#39;from&#39; to state &#39;to&#39;.
Definition: HoppingAmplitude.h:53
Iterator begin()
Definition: HoppingAmplitudeTree.h:532
Data structure for mapping physical indices to linear indices.
Definition: IndexTree.h:35
Physical index.
Definition: Index.h:44
Iterator end()
Definition: HoppingAmplitudeTree.h:544
Definition: Boolean.h:32
Definition: HoppingAmplitudeTree.h:327
void sort(HoppingAmplitudeTree *rootNode)
const Vector2d operator*(double lhs, const Vector2d &rhs)
Definition: Vector2d.h:129
Mode
Definition: Serializable.h:47
IndexTree getSubspaceIndices() const
Index getPhysicalIndex(int basisIndex) const
Abstract base class for serializable objects.
bool operator!=(const IndexTree &lhs, const IndexTree &rhs)
Definition: IndexTree.h:391