TBTK
Need a break? Support the development by playing Polarity Puzzles
IndexTree.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_INDEX_TREE
24 #define COM_DAFER45_TBTK_INDEX_TREE
25 
26 #include "TBTK/Index.h"
27 #include "TBTK/Serializable.h"
28 #include "TBTK/Streamable.h"
29 
30 #include <vector>
31 
32 namespace TBTK{
33 
35 class IndexTree : public Serializable, public Streamable{
36 public:
38  IndexTree();
39 
46  IndexTree(const std::string &serialization, Mode mode);
47 
49  virtual ~IndexTree();
50 
58  friend bool operator==(const IndexTree &lhs, const IndexTree &rhs);
59 
67  friend bool operator!=(const IndexTree &lhs, const IndexTree &rhs);
68 
99  void add(const Index &index);
100 
107  void generateLinearMap();
108 
112  bool getLinearMapIsGenerated() const;
113 
116  enum class SearchMode{StrictMatch, /*IgnoreWildcards,*/ MatchWildcards};
117 
154  int getLinearIndex(
155  const Index &index,
156  SearchMode searchMode = SearchMode::StrictMatch,
157  bool returnNegativeForMissingIndex = false
158  ) const;
159 
166  Index getPhysicalIndex(int linearIndex) const;
167 
174  bool contains(const Index &index);
175 
181  int getSize() const;
182 
206  std::vector<unsigned int> getSubindicesMatching(
207  int subindexValue,
208  const Index &index,
209  SearchMode searchMode
210  ) const;
211 
220  std::vector<Index> getIndexList(const Index &pattern) const;
221 
229  bool equals(const IndexTree &indexTree) const;
230 
231  class ConstIterator;
232 private:
235  template<bool isConstIterator>
236  class _Iterator{
237  public:
240  typedef typename std::conditional<
241  isConstIterator,
242  const Index,
243  Index
244  >::type IndexType;
245 
247  void operator++();
248 
250  IndexType operator*();
251 
253  bool operator==(const _Iterator &rhs) const;
254 
256  bool operator!=(const _Iterator &rhs) const;
257  private:
260  typedef typename std::conditional<
261  isConstIterator,
262  const IndexTree*,
263  IndexTree*
264  >::type IndexTreePointerType;
265 
267  IndexTreePointerType indexTree;
268 
270  std::vector<int> currentIndex;
271 
277  bool skipNextIndex;
278 
280  _Iterator(IndexTreePointerType indexTree, bool end = false);
281 
285  bool searchNext(
286  const IndexTree *indexTree,
287  unsigned int subindex
288  );
289 
291  friend class Iterator;
292  friend class ConstIterator;
293  };
294 public:
297  class ConstIterator : public _Iterator<true>{
298  private:
300  const IndexTree *indexTree,
301  bool end = false
302  ) : _Iterator<true>(indexTree, end){}
303 
305  friend class IndexTree;
306  };
307 
311  ConstIterator begin() const;
312 
316  ConstIterator cbegin() const;
317 
321  ConstIterator end() const;
322 
326  ConstIterator cend() const;
327 
329  virtual std::string toString() const;
330 
332  std::string serialize(Mode mode) const;
333 private:
335  std::vector<IndexTree> children;
336 
339  bool indexIncluded;
340 
343  bool wildcardIndex;
344 
347  int wildcardType;
348 
352  bool indexSeparator;
353 
355  int linearIndex;
356 
358  int size;
359 
362  void add(const Index& index, unsigned int subindex);
363 
366  int generateLinearMap(int i);
367 
370  int getLinearIndex(
371  const Index &index,
372  unsigned int subindex,
373  SearchMode searchMode,
374  bool returnNegativeForMissingIndex
375  ) const;
376 
379  void getPhysicalIndex(
380  int linearIndex,
381  std::vector<Subindex> &indices
382  ) const;
383 
385  int getMinIndex() const;
386 
388  int getMaxIndex() const;
389 };
390 
391 inline bool operator!=(const IndexTree &lhs, const IndexTree &rhs){
392  return !(lhs == rhs);
393 }
394 
396  if(size == -1)
397  return false;
398  else
399  return true;
400 }
401 
403  return ConstIterator(this);
404 }
405 
407  return ConstIterator(this);
408 }
409 
411  return ConstIterator(this, true);
412 }
413 
415  return ConstIterator(this, true);
416 }
417 
418 inline int IndexTree::getSize() const{
419  return size;
420 }
421 
422 template<bool isConstIterator>
423 IndexTree::_Iterator<isConstIterator>::_Iterator(IndexTreePointerType indexTree, bool end){
424  if(end){
425  this->indexTree = indexTree;
426  currentIndex.push_back(indexTree->children.size());
427  }
428  else{
429  this->indexTree = indexTree;
430  currentIndex.push_back(0);
431  skipNextIndex = false;
432  searchNext(this->indexTree, 0);
433  }
434 }
435 
436 template<bool isConstIterator>
437 void IndexTree::_Iterator<isConstIterator>::operator++(){
438  skipNextIndex = true;
439  searchNext(indexTree, 0);
440 }
441 
442 template<bool isConstIterator>
443 bool IndexTree::_Iterator<isConstIterator>::searchNext(
444  const IndexTree *indexTree,
445  unsigned int subindex
446 ){
447  if(indexTree->children.size() == 0){
448  if(indexTree->indexIncluded){
449  if(skipNextIndex)
450  skipNextIndex = false;
451  else
452  return true;
453  }
454  }
455 
456  unsigned int n = currentIndex.at(subindex);
457  while(n < indexTree->children.size()){
458  if(subindex+1 == currentIndex.size())
459  currentIndex.push_back(0);
460  if(searchNext(&indexTree->children.at(n), subindex+1))
461  return true;
462 
463  currentIndex.pop_back();
464  n = ++currentIndex.back();
465  }
466 
467  return false;
468 }
469 
470 template<bool isConstIterator>
471 typename IndexTree::_Iterator<isConstIterator>::IndexType IndexTree::_Iterator<isConstIterator>::operator*(){
472  if(currentIndex.at(0) == (int)indexTree->children.size()){
473  TBTKExit(
474  "IndexTree::_Iterator<isConstIterator>::operator*()",
475  "Out of range access. Tried to access an element using"
476  << " an Iterator that points beyond the last element.",
477  ""
478  );
479  }
480 
481  Index index;
482 
483  const IndexTree *indexTreeBranch = this->indexTree;
484  for(unsigned int n = 0; n < currentIndex.size()-1; n++){
485  if(indexTreeBranch->indexSeparator)
486  index.pushBack(IDX_SEPARATOR);
487 
488  if(indexTreeBranch->wildcardIndex)
489  index.pushBack(indexTreeBranch->wildcardType);
490  else
491  index.pushBack(currentIndex.at(n));
492 
493  if(n < currentIndex.size()-1)
494  indexTreeBranch = &indexTreeBranch->children.at(currentIndex.at(n));
495  }
496 
497  return index;
498 }
499 
500 template<bool isConstIterator>
501 bool IndexTree::_Iterator<isConstIterator>::operator==(const _Iterator &rhs) const{
502  if(indexTree != rhs.indexTree)
503  return false;
504 
505  if(currentIndex.size() != rhs.currentIndex.size())
506  return false;
507 
508  for(unsigned int n = 0; n < currentIndex.size(); n++)
509  if(currentIndex[n] != rhs.currentIndex[n])
510  return false;
511 
512  return true;
513 };
514 
515 template<bool isConstIterator>
516 bool IndexTree::_Iterator<isConstIterator>::operator!=(const _Iterator &rhs) const{
517  return !operator==(rhs);
518 }
519 
520 }; //End of namesapce TBTK
521 
522 #endif
523 
TBTK::IndexTree::getSize
int getSize() const
Definition: IndexTree.h:418
TBTK::Streamable
Definition: Streamable.h:30
TBTK::IndexTree::begin
ConstIterator begin() const
Definition: IndexTree.h:402
TBTK::IndexTree::toString
virtual std::string toString() const
TBTK::IndexTree::getIndexList
std::vector< Index > getIndexList(const Index &pattern) const
Index.h
Physical index.
TBTK::Serializable::Index
friend class Index
Definition: Serializable.h:200
TBTK::IndexTree::getLinearIndex
int getLinearIndex(const Index &index, SearchMode searchMode=SearchMode::StrictMatch, bool returnNegativeForMissingIndex=false) const
TBTK::IndexTree::getPhysicalIndex
Index getPhysicalIndex(int linearIndex) const
TBTK::IndexTree::cbegin
ConstIterator cbegin() const
Definition: IndexTree.h:406
TBTK::IndexTree::add
void add(const Index &index)
TBTK::Serializable
Definition: Serializable.h:43
TBTK::IndexTree::generateLinearMap
void generateLinearMap()
TBTK::IndexTree::equals
bool equals(const IndexTree &indexTree) const
TBTK::operator!=
bool operator!=(const IndexTree &lhs, const IndexTree &rhs)
Definition: IndexTree.h:391
TBTK::IndexTree::SearchMode
SearchMode
Definition: IndexTree.h:116
Serializable.h
Abstract base class for serializable objects.
TBTK::IndexTree::end
ConstIterator end() const
Definition: IndexTree.h:410
Streamable.h
Abstract base class for classes that can be written to a stream.
TBTK::IndexTree::IndexTree
IndexTree()
TBTK::IndexTree
Data structure for mapping physical indices to linear indices.
Definition: IndexTree.h:35
TBTK::IndexTree::getSubindicesMatching
std::vector< unsigned int > getSubindicesMatching(int subindexValue, const Index &index, SearchMode searchMode) const
TBTK::IndexTree::getLinearMapIsGenerated
bool getLinearMapIsGenerated() const
Definition: IndexTree.h:395
TBTK::IndexTree::ConstIterator
Definition: IndexTree.h:297
TBTK::operator*
const Vector2d operator*(double lhs, const Vector2d &rhs)
Definition: Vector2d.h:129
TBTK::IndexTree::operator==
friend bool operator==(const IndexTree &lhs, const IndexTree &rhs)
TBTK::IndexTree::cend
ConstIterator cend() const
Definition: IndexTree.h:414
TBTK::Serializable::Mode
Mode
Definition: Serializable.h:47
TBTK::IndexTree::serialize
std::string serialize(Mode mode) const
TBTK::IndexTree::operator!=
friend bool operator!=(const IndexTree &lhs, const IndexTree &rhs)
Definition: IndexTree.h:391
TBTK::Index
Physical index.
Definition: Index.h:44
TBTK::IndexTree::~IndexTree
virtual ~IndexTree()
TBTK::IndexTree::contains
bool contains(const Index &index)