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