IndexTree.h

Go to the documentation of this file.

/* Copyright 2017 Kristofer Björnson
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
 
#ifndef COM_DAFER45_TBTK_INDEX_TREE
#define COM_DAFER45_TBTK_INDEX_TREE
 
#include "TBTK/Index.h"
#include "TBTK/Serializable.h"
#include "TBTK/Streamable.h"
 
#include <vector>
 
namespace TBTK{
 
class IndexTree : public Serializable, public Streamable{
public:
    IndexTree();
 
    IndexTree(const std::string &serialization, Mode mode);
 
    virtual ~IndexTree();
 
    friend bool operator==(const IndexTree &lhs, const IndexTree &rhs);
 
    friend bool operator!=(const IndexTree &lhs, const IndexTree &rhs);
 
    void add(const Index &index);
 
    void generateLinearMap();
 
    bool getLinearMapIsGenerated() const;
 
    enum class SearchMode{StrictMatch, /*IgnoreWildcards,*/ MatchWildcards};
 
    int getLinearIndex(
        const Index &index,
        SearchMode searchMode = SearchMode::StrictMatch,
        bool returnNegativeForMissingIndex = false
    ) const;
 
    Index getPhysicalIndex(int linearIndex) const;
 
    bool contains(const Index &index);
 
    int getSize() const;
 
    std::vector<unsigned int> getSubindicesMatching(
        int subindexValue,
        const Index &index,
        SearchMode searchMode
    ) const;
 
    std::vector<Index> getIndexList(const Index &pattern) const;
 
    bool equals(const IndexTree &indexTree) const;
 
    class ConstIterator;
private:
    template<bool isConstIterator>
    class _Iterator{
    public:
        typedef typename std::conditional<
            isConstIterator,
            const Index,
            Index
        >::type IndexType;
 
        void operator++();
 
        IndexType operator*();
 
        bool operator==(const _Iterator &rhs) const;
 
        bool operator!=(const _Iterator &rhs) const;
    private:
        typedef typename std::conditional<
            isConstIterator,
            const IndexTree*,
            IndexTree*
        >::type IndexTreePointerType;
 
        IndexTreePointerType indexTree;
 
        std::vector<int> currentIndex;
 
        bool skipNextIndex;
 
        _Iterator(IndexTreePointerType indexTree, bool end = false);
 
        bool searchNext(
            const IndexTree *indexTree,
            unsigned int subindex
        );
 
        friend class Iterator;
        friend class ConstIterator;
    };
public:
    class ConstIterator : public _Iterator<true>{
    private:
        ConstIterator(
            const IndexTree *indexTree,
            bool end = false
        ) : _Iterator<true>(indexTree, end){}
 
        friend class IndexTree;
    };
 
    ConstIterator begin() const;
 
    ConstIterator cbegin() const;
 
    ConstIterator end() const;
 
    ConstIterator cend() const;
 
    virtual std::string toString() const;
 
    std::string serialize(Mode mode) const;
private:
    std::vector<IndexTree> children;
 
    bool indexIncluded;
 
    bool wildcardIndex;
 
    int wildcardType;
 
    bool indexSeparator;
 
    int linearIndex;
 
    int size;
 
    void add(const Index& index, unsigned int subindex);
 
    int generateLinearMap(int i);
 
    int getLinearIndex(
        const Index &index,
        unsigned int subindex,
        SearchMode searchMode,
        bool returnNegativeForMissingIndex
    ) const;
 
    void getPhysicalIndex(
        int linearIndex,
        std::vector<Subindex> &indices
    ) const;
 
    int getMinIndex() const;
 
    int getMaxIndex() const;
};
 
inline bool operator!=(const IndexTree &lhs, const IndexTree &rhs){
    return !(lhs == rhs);
}
 
inline bool IndexTree::getLinearMapIsGenerated() const{
    if(size == -1)
        return false;
    else
        return true;
}
 
inline IndexTree::ConstIterator IndexTree::begin() const{
    return ConstIterator(this);
}
 
inline IndexTree::ConstIterator IndexTree::cbegin() const{
    return ConstIterator(this);
}
 
inline IndexTree::ConstIterator IndexTree::end() const{
    return ConstIterator(this, true);
}
 
inline IndexTree::ConstIterator IndexTree::cend() const{
    return ConstIterator(this, true);
}
 
inline int IndexTree::getSize() const{
    return size;
}
 
template<bool isConstIterator>
IndexTree::_Iterator<isConstIterator>::_Iterator(IndexTreePointerType indexTree, bool end){
    if(end){
        this->indexTree = indexTree;
        currentIndex.push_back(indexTree->children.size());
    }
    else{
        this->indexTree = indexTree;
        currentIndex.push_back(0);
        skipNextIndex = false;
        searchNext(this->indexTree, 0);
    }
}
 
template<bool isConstIterator>
void IndexTree::_Iterator<isConstIterator>::operator++(){
    skipNextIndex = true;
    searchNext(indexTree, 0);
}
 
template<bool isConstIterator>
bool IndexTree::_Iterator<isConstIterator>::searchNext(
    const IndexTree *indexTree,
    unsigned int subindex
){
    if(indexTree->children.size() == 0){
        if(indexTree->indexIncluded){
            if(skipNextIndex)
                skipNextIndex = false;
            else
                return true;
        }
    }
 
    unsigned int  n = currentIndex.at(subindex);
    while(n < indexTree->children.size()){
        if(subindex+1 == currentIndex.size())
            currentIndex.push_back(0);
        if(searchNext(&indexTree->children.at(n), subindex+1))
            return true;
 
        currentIndex.pop_back();
        n = ++currentIndex.back();
    }
 
    return false;
}
 
template<bool isConstIterator>
typename IndexTree::_Iterator<isConstIterator>::IndexType IndexTree::_Iterator<isConstIterator>::operator*(){
    if(currentIndex.at(0) == (int)indexTree->children.size()){
        TBTKExit(
            "IndexTree::_Iterator<isConstIterator>::operator*()",
            "Out of range access. Tried to access an element using"
            << " an Iterator that points beyond the last element.",
            ""
        );
    }
 
    Index index;
 
    const IndexTree *indexTreeBranch = this->indexTree;
    for(unsigned int n = 0; n < currentIndex.size()-1; n++){
        if(indexTreeBranch->indexSeparator)
            index.pushBack(IDX_SEPARATOR);
 
        if(indexTreeBranch->wildcardIndex)
            index.pushBack(indexTreeBranch->wildcardType);
        else
            index.pushBack(currentIndex.at(n));
 
        if(n < currentIndex.size()-1)
            indexTreeBranch = &indexTreeBranch->children.at(currentIndex.at(n));
    }
 
    return index;
}
 
template<bool isConstIterator>
bool IndexTree::_Iterator<isConstIterator>::operator==(const _Iterator &rhs) const{
    if(indexTree != rhs.indexTree)
        return false;
 
    if(currentIndex.size() != rhs.currentIndex.size())
        return false;
 
    for(unsigned int n = 0; n < currentIndex.size(); n++)
        if(currentIndex[n] != rhs.currentIndex[n])
            return false;
 
    return true;
};
 
template<bool isConstIterator>
bool IndexTree::_Iterator<isConstIterator>::operator!=(const _Iterator &rhs) const{
    return !operator==(rhs);
}
 
}; //End of namesapce TBTK
 
#endif