HoppingAmplitudeTree.h

Go to the documentation of this file.

/* Copyright 2016 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_TREE_NODE
#define COM_DAFER45_TBTK_TREE_NODE
 
#include "TBTK/HoppingAmplitude.h"
#include "TBTK/IndexTree.h"
#include "TBTK/Serializable.h"
 
#include <vector>
 
namespace TBTK{
 
class HoppingAmplitudeTree : virtual public Serializable{
public:
    HoppingAmplitudeTree();
 
    HoppingAmplitudeTree(
        const std::vector<unsigned int> &capacity
    );
 
    HoppingAmplitudeTree(const std::string &serialization, Mode mode);
 
    virtual ~HoppingAmplitudeTree();
 
    void add(HoppingAmplitude ha);
 
    int getBasisSize() const;
 
    HoppingAmplitudeTree* getSubTree(const Index &subspace);
 
    const HoppingAmplitudeTree* getSubTree(const Index &subspace) const;
 
    bool isProperSubspace(const Index &subspace) const;
 
    IndexTree getSubspaceIndices() const;
 
    Index getSubspaceIndex(const Index &index) const;
 
    int getFirstIndexInSubspace(const Index &subspaceIndex) const;
 
    int getLastIndexInSubspace(const Index &subspaceIndex) const;
 
    const std::vector<HoppingAmplitude>& getHoppingAmplitudes(
        Index index
    ) const;
 
    int getBasisIndex(const Index &index) const;
 
    Index getPhysicalIndex(int basisIndex) const;
 
    void generateBasisIndices();
 
    std::vector<Index> getIndexList(const Index &pattern) const;
 
    std::vector<Index> getIndexListMultiplePatterns(
        const std::vector<Index> &patterns
    ) const;
 
    void sort(HoppingAmplitudeTree *rootNode);
 
    void print();
 
    class Iterator;
    class ConstIterator;
private:
    template<bool isConstIterator>
    class _Iterator{
    public:
        typedef typename std::conditional<
            isConstIterator,
            const HoppingAmplitude&,
            HoppingAmplitude&
        >::type HoppingAmplitudeReferenceType;
 
        void operator++();
 
        HoppingAmplitudeReferenceType operator*();
 
        bool operator==(const _Iterator &rhs) const;
 
        bool operator!=(const _Iterator &rhs) const;
 
        int getMinBasisIndex() const;
 
        int getMaxBasisIndex() const;
 
        int getNumBasisIndices() const;
    private:
        typedef typename std::conditional<
            isConstIterator,
            const HoppingAmplitudeTree*,
            HoppingAmplitudeTree*
        >::type HoppingAmplitudeTreePointerType;
 
        HoppingAmplitudeTreePointerType tree;
 
        std::vector<int> currentIndex;
 
        int currentHoppingAmplitude;
 
        friend class Iterator;
        friend class ConstIterator;
 
        _Iterator(HoppingAmplitudeTreePointerType tree, bool end = false);
 
        bool searchNext(
            HoppingAmplitudeTreePointerType hoppingAmplitudeTree,
            int subindex
        );
    };
public:
    class Iterator : public _Iterator<false>{
    private:
        Iterator(
            HoppingAmplitudeTree *hoppingAmplitudeTree,
            bool end = false
        ) : _Iterator<false>(hoppingAmplitudeTree, end){};
 
        friend class HoppingAmplitudeTree;
    };
 
    class ConstIterator : public _Iterator<true>{
    private:
        ConstIterator(
            const HoppingAmplitudeTree *hoppingAmplitudeTree,
            bool end = false
        ) : _Iterator<true>(hoppingAmplitudeTree, end){};
 
        friend class HoppingAmplitudeTree;
    };
 
    Iterator begin();
 
    ConstIterator begin() const;
 
    ConstIterator cbegin() const;
 
    Iterator end();
 
    ConstIterator end() const;
 
    ConstIterator cend() const;
 
    virtual std::string serialize(Mode mode) const;
 
    unsigned int getSizeInBytes() const;
private:
    int basisIndex;
 
    int basisSize;
 
    bool isPotentialBlockSeparator;
 
    std::vector<HoppingAmplitude> hoppingAmplitudes;
 
    std::vector<HoppingAmplitudeTree> children;
 
    static const HoppingAmplitudeTree emptyTree;
 
    void _add(HoppingAmplitude &ha, unsigned int subindex);
 
    const HoppingAmplitudeTree* getSubTree(
        const Index &subspace,
        unsigned int subindex
    ) const;
 
    bool _isProperSubspace(
        const Index &subspace,
        unsigned int subindex
    ) const;
 
    void getBlockIndices(IndexTree &blockIndices, Index index) const;
 
    void getBlockIndex(
        const Index &index,
        unsigned int subindex,
        Index &blockIndex
    ) const;
 
    const std::vector<HoppingAmplitude>& _getHoppingAmplitudes(
        Index index,
        unsigned int subindex
    ) const;
 
    int _getBasisIndex(const Index &index, unsigned int subindex) const;
 
    void _getPhysicalIndex(int basisIndex, std::vector<Subindex> &indices) const;
 
    int getMinIndex() const;
 
    int getMaxIndex() const;
 
    int generateBasisIndices(int i);
 
    void print(unsigned int subindex);
 
    HoppingAmplitude getFirstHA() const;
};
 
inline int HoppingAmplitudeTree::getBasisSize() const{
    return basisSize;
}
 
inline int HoppingAmplitudeTree::getFirstIndexInSubspace(
    const Index &subspaceIndex
) const{
    TBTKAssert(
        isProperSubspace(subspaceIndex),
        "HoppingAmplitudeTree::getFirstIndexInSubspace()",
        "The index " << subspaceIndex.toString() << " is not an Index"
        << " of a proper subspace.",
        ""
    );
 
    const HoppingAmplitudeTree *subspace = getSubTree(subspaceIndex);
 
    return subspace->getMinIndex();
}
 
inline int HoppingAmplitudeTree::getLastIndexInSubspace(
    const Index &subspaceIndex
) const{
    TBTKAssert(
        isProperSubspace(subspaceIndex),
        "HoppingAmplitudeTree::getLastIndexInSubspace()",
        "The index " << subspaceIndex.toString() << " is not an Index"
        << " of a proper subspace.",
        ""
    );
 
    const HoppingAmplitudeTree *subspace = getSubTree(subspaceIndex);
 
    return subspace->getMaxIndex();
}
 
inline HoppingAmplitudeTree::Iterator HoppingAmplitudeTree::begin(){
    return Iterator(this);
}
 
inline HoppingAmplitudeTree::ConstIterator HoppingAmplitudeTree::begin() const{
    return ConstIterator(this);
}
 
inline HoppingAmplitudeTree::ConstIterator HoppingAmplitudeTree::cbegin() const{
    return ConstIterator(this);
}
 
inline HoppingAmplitudeTree::Iterator HoppingAmplitudeTree::end(){
    return Iterator(this, true);
}
 
inline HoppingAmplitudeTree::ConstIterator HoppingAmplitudeTree::end() const{
    return ConstIterator(this, true);
}
 
inline HoppingAmplitudeTree::ConstIterator HoppingAmplitudeTree::cend() const{
    return ConstIterator(this, true);
}
 
inline unsigned int HoppingAmplitudeTree::getSizeInBytes() const{
    unsigned int size = 0;
    for(unsigned int n = 0; n < hoppingAmplitudes.size(); n++)
        size += hoppingAmplitudes[n].getSizeInBytes();
    for(unsigned int n = 0; n < children.size(); n++)
        size += children[n].getSizeInBytes();
 
    size += (
        hoppingAmplitudes.capacity() - hoppingAmplitudes.size()
    )*sizeof(HoppingAmplitude);
 
    size += (
        children.capacity() - children.size()
    )*sizeof(HoppingAmplitudeTree);
 
    return size + sizeof(HoppingAmplitudeTree);
}
 
template<bool isConstIterator>
HoppingAmplitudeTree::_Iterator<isConstIterator>::_Iterator(
    HoppingAmplitudeTreePointerType tree,
    bool end
)
{
    if(end){
        this->tree = tree;
        if(tree->children.size() == 0){
            currentHoppingAmplitude = -1;
        }
        else{
            currentIndex.push_back(tree->children.size());
            currentHoppingAmplitude = -1;
        }
    }
    else{
        this->tree = tree;
        if(tree->children.size() == 0){
            //Handle the special case when the data is stored on the head
            //node. Can for example be the case when iterating over a
            //single leaf node.
            currentHoppingAmplitude = -1;
            searchNext(tree, -1);
        }
        else{
            currentIndex.push_back(0);
            currentHoppingAmplitude = -1;
            searchNext(tree, 0);
        }
    }
}
 
template<bool isConstIterator>
void HoppingAmplitudeTree::_Iterator<isConstIterator>::operator++(){
    if(tree->children.size() == 0){
        //Handle the special case when the data is stored on the head
        //node. Can for example be the case when iterating over a
        //single leaf node.
        searchNext(tree, -1);
    }
    else{
        searchNext(tree, 0);
    }
}
 
template<bool isConstIterator>
bool HoppingAmplitudeTree::_Iterator<isConstIterator>::searchNext(
    HoppingAmplitudeTreePointerType hoppingAmplitudeTree,
    int subindex
){
    if(subindex+1 == (int)currentIndex.size()){
        //If the node level corresponding to the current index is
        //reached, try to execute leaf node actions.
 
        if(currentHoppingAmplitude != -1){
            //The iterator is in the process of iterating over
            //HoppingAmplitudes on this leaf node. Try to iterate further.
 
            currentHoppingAmplitude++;
            if(currentHoppingAmplitude == (int)hoppingAmplitudeTree->hoppingAmplitudes.size()){
                //Last HoppingAmplitude already reached. Reset
                //currentHoppingAmplitude and return false to
                //indicate that no more HoppingAMplitudes exist
                //on this node.
                currentHoppingAmplitude = -1;
                return false;
            }
            else{
                //Return true to indicate that the next
                //HoppingAmplitude succesfully has been found.
                return true;
            }
        }
 
        //We are here guaranteed that the iterator is not currently in
        //a state where it is iterating over HoppingAmplitudes on this
        //node.
 
        if(hoppingAmplitudeTree->children.size() == 0){
            //The node has no children and is therefore either a
            //leaf node with HoppingAmplitudes stored on it, or an
            //empty dummy node.
 
            if(hoppingAmplitudeTree->hoppingAmplitudes.size() != 0){
                //There are HoppingAMplitudes on this node,
                //initialize the iterator to start iterating
                //over these. Return true to indicate that a
                //HoppingAmplitude was found.
                currentHoppingAmplitude = 0;
                return true;
            }
            else{
                //The node is an empty dymmy node. Return false
                //to indicate that no more HoppingAmplitudes
                //exist on this node.
                return false;
            }
        }
    }
 
    //We are here guaranteed that this is not a leaf or dummy node. We know
    //this because either the tests inside the previous if-statements
    //failed, or we are iterating through children that already have been
    //visited on an earlier call to searchNext if the outer if-statement
    //itself failed.
 
    //Perform depth first search for the next HoppingAmplitude. Starts from
    //the child node reffered to by currentIndex.
    unsigned int n = currentIndex.at(subindex);
    while(n < hoppingAmplitudeTree->children.size()){
        if(subindex+1 == (int)currentIndex.size()){
            //The deepest point visited so far on this branch has
            //been reached. Initialize the depth first search for
            //child n to start from child n's zeroth child.
            currentIndex.push_back(0);
        }
        if(searchNext(&hoppingAmplitudeTree->children.at(n), subindex+1)){
            //Depth first search on child n succeded at finding a
            //HoppingAmplitude. Return true to indicate success.
            return true;
        }
        //Child n does not have any more HoppingAmplitudes. Pop
        //the subindex corresponding to child n's node level and
        //increment the subindex corresponding to this node level to
        //prepare for depth first search of child n+1.
        currentIndex.pop_back();
        n = ++currentIndex.back();
    }
 
    //Return false to indicate that no more HoppingAmplitudes could be
    //found on this node.
    return false;
}
 
template<bool isConstIterator>
typename HoppingAmplitudeTree::_Iterator<
    isConstIterator
>::HoppingAmplitudeReferenceType HoppingAmplitudeTree::_Iterator<
    isConstIterator
>::operator*(){
    if(currentIndex.size() == 0){
        //Handle the special case when the data is stored on the head
        //node. Can for example be the case when iterating over a
        //single leaf node.
        if(currentHoppingAmplitude == -1){
            TBTKExit(
                "HoppingAmplitudeTree::_Iterator::operator*()",
                "Out of range access. Tried to access an"
                << " element using an iterator that points"
                << " beyond the last element.",
                ""
            );
        }
        else{
            return tree->hoppingAmplitudes.at(currentHoppingAmplitude);
        }
    }
 
    if(currentIndex.at(0) == (int)tree->children.size()){
        TBTKExit(
            "HoppingAmplitudeTree::_Iterator::operator*()",
            "Out of range access. Tried to access an"
            << " element using an iterator that points"
            << " beyond the last element.",
            ""
        );
    }
    const HoppingAmplitudeTree *tn = this->tree;
    for(unsigned int n = 0; n < currentIndex.size()-1; n++){
        tn = &tn->children.at(currentIndex.at(n));
    }
 
    return tn->hoppingAmplitudes.at(currentHoppingAmplitude);
}
 
template<bool isConstIterator>
bool HoppingAmplitudeTree::_Iterator<isConstIterator>::operator==(const _Iterator &rhs) const{
    if(
        this->tree == rhs.tree
        && currentIndex.size() == rhs.currentIndex.size()
    ){
        for(unsigned int n = 0; n < currentIndex.size(); n++){
            if(currentIndex[n] != rhs.currentIndex[n])
                return false;
        }
 
        if(currentHoppingAmplitude == rhs.currentHoppingAmplitude)
            return true;
        else
            return false;
    }
    else{
        return false;
    }
}
 
template<bool isConstIterator>
bool HoppingAmplitudeTree::_Iterator<isConstIterator>::operator!=(
    const _Iterator &rhs
) const{
    return !operator==(rhs);
}
 
template<bool isConstIterator>
int HoppingAmplitudeTree::_Iterator<isConstIterator>::getMinBasisIndex() const{
    return tree->getMinIndex();
}
 
template<bool isConstIterator>
int HoppingAmplitudeTree::_Iterator<isConstIterator>::getMaxBasisIndex() const{
    return tree->getMaxIndex();
}
 
template<bool isConstIterator>
int HoppingAmplitudeTree::_Iterator<isConstIterator>::getNumBasisIndices(
) const{
    if(getMaxBasisIndex() == -1)
        return 0;
    else
        return 1 + getMaxBasisIndex() - getMinBasisIndex();
}
 
};  //End of namespace TBTK
 
#endif