IndexedDataTree.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_INDEXED_DATA_TREE
#define COM_DAFER45_TBTK_INDEXED_DATA_TREE
 
#include "TBTK/ElementNotFoundException.h"
#include "TBTK/Index.h"
#include "TBTK/PseudoSerializable.h"
#include "TBTK/Serializable.h"
#include "TBTK/TBTKMacros.h"
 
#include <complex>
#include <map>
#include <sstream>
 
//This is used to work around incompatibilities between nlohmann::json and
//CUDA. This effectively forbids instantiation of IndexedDataTree in CUDA code.
#ifndef TBTK_DISABLE_NLOHMANN_JSON
#   include "TBTK/json.hpp"
#endif
 
namespace TBTK{
 
template<typename Data>
class IndexedDataTree : public Serializable{
public:
    IndexedDataTree();
 
    IndexedDataTree(const std::string &serialization, Mode mode);
 
    virtual ~IndexedDataTree();
 
    void add(const Data &data, const Index &index);
 
    bool get(Data &data, const Index &index) const;
 
    Data& get(const Index &index);
 
    const Data& get(const Index &index) const;
 
    void clear();
 
    unsigned int getSizeInBytes() const;
 
    virtual std::string serialize(Mode mode) const;
 
    class Iterator;
    class ConstIterator;
private:
    template<bool isConstIterator>
    class _Iterator{
    public:
        typedef typename std::conditional<
            isConstIterator,
            const Data&,
            Data&
        >::type DataReferenceType;
 
        void operator++();
 
        DataReferenceType operator*();
 
        bool operator==(const _Iterator &rhs) const;
 
        bool operator!=(const _Iterator &rhs) const;
 
        const Index& getCurrentIndex() const;
    private:
        typedef typename std::conditional<
            isConstIterator,
            const IndexedDataTree*,
            IndexedDataTree*
        >::type IndexedDataTreePointerType;
 
        IndexedDataTreePointerType indexedDataTree;
 
        Index currentIndex;
 
        _Iterator(IndexedDataTreePointerType indexedDataTree, bool end = false);
 
        friend class Iterator;
        friend class ConstIterator;
    };
public:
    class Iterator : public _Iterator<false>{
    private:
        Iterator(
            IndexedDataTree *indexedDataTree,
            bool end = false
        ) : _Iterator<false>(indexedDataTree, end){};
 
        friend class IndexedDataTree;
    };
 
    class ConstIterator : public _Iterator<true>{
    private:
        ConstIterator(
            const IndexedDataTree *indexedDataTree,
            bool end = false
        ) : _Iterator<true>(indexedDataTree, end){};
 
        friend class IndexedDataTree;
    };
 
    Iterator begin();
 
    ConstIterator begin() const;
 
    ConstIterator cbegin() const;
 
    Iterator end();
 
    ConstIterator end() const;
 
    ConstIterator cend() const;
private:
    std::map<Subindex, IndexedDataTree> children;
 
    bool indexIncluded;
 
    bool indexSeparator;
 
    Data data;
 
    void add(const Data &data, const Index& index, unsigned int subindex);
 
    bool get(Data &data, const Index& index, unsigned int subindex) const;
 
    const Data& get(const Index& index, unsigned int subindex) const;
 
    Index getFirstIndex() const;
 
    bool getFirstIndex(Index &index) const;
 
    Index getNextIndex(const Index &index) const;
 
    bool getNextIndex(
        const Index &currentIndex,
        Index &nextIndex
    ) const;
};
 
//This is used to work around incompatibilities between nlohmann::json and
//CUDA. This effectively forbids instantiation of IndexedDataTree in CUDA code.
#ifndef TBTK_DISABLE_NLOHMANN_JSON
 
template<typename Data>
IndexedDataTree<Data>::IndexedDataTree(){
    indexIncluded = false;
    indexSeparator = false;
}
 
template<typename Data>
inline IndexedDataTree<Data>::IndexedDataTree(
    const std::string &serialization,
    Mode mode
){
    TBTKAssert(
        validate(serialization, "IndexedDataTree", mode),
        "IndexedDataTree<bool>::IndexedDataTree()",
        "Unable to parse string as IndexedDataTree<bool> '"
        << serialization << "'.",
        ""
    );
 
    switch(mode){
    case Mode::JSON:
    {
        try{
            nlohmann::json j = nlohmann::json::parse(
                serialization
            );
            indexIncluded = j.at("indexIncluded").get<bool>();
            indexSeparator = j.at("indexSeparator").get<bool>();
            data = Serializable::deserialize<Data>(
                j.at("data").get<std::string>(),
                mode
            );
            nlohmann::json jsonChildren = j.at("children");
            for(
                nlohmann::json::const_iterator iterator
                    = jsonChildren.cbegin();
                iterator != jsonChildren.cend();
                ++iterator
            ){
                children.insert({
                    Subindex(
                        iterator.key(),
                        Serializable::Mode::JSON
                    ),
                    IndexedDataTree(
                        iterator.value().dump(),
                        Serializable::Mode::JSON
                    )
                });
            }
        }
        catch(nlohmann::json::exception &e){
            TBTKExit(
                "IndexedDataTree<bool>::IndexedDataTree()",
                "Unable to parse string as"
                << " IndexedDataTree<bool> '"
                << serialization << "'.",
                ""
            );
        }
 
        break;
    }
    default:
        TBTKExit(
            "IndexedDataTree<Data>::IndexedDataTree()",
            "Only Serializable::Mode::JSON is supported yet.",
            ""
        );
    }
}
 
template<typename Data>
IndexedDataTree<Data>::~IndexedDataTree(){
}
 
template<typename Data>
void IndexedDataTree<Data>::add(const Data &data, const Index &index){
    add(data, index, 0);
}
 
template<typename Data>
void IndexedDataTree<Data>::add(
    const Data &data,
    const Index &index,
    unsigned int subindex
){
    if(subindex < index.getSize()){
        //If the current subindex is not the last, the Index is
        //propagated to the next node level.
 
        //Get current subindex
        Subindex currentIndex = index.at(subindex);
 
        if(currentIndex.isIndexSeparator()){
            if(children.size() == 0){
                indexSeparator = true;
            }
            else{
                TBTKAssert(
                    indexSeparator,
                    "IndexedDataTree:add()",
                    "Invalid index '" << index.toString()
                    << "'. Another Index has already been"
                    << " added to the tree that has a"
                    << " conflicting index at the index"
                    << " separator at subindex '"
                    << subindex << "'.",
                    "Note that a separation point between"
                    << " two indices counts as a subindex."
                );
            }
 
            indexSeparator = false;
            add(data, index, subindex+1);
            indexSeparator = true;
            return;
        }
        else{
            TBTKAssert(
                !indexSeparator,
                "IndexedDataTree:add()",
                "Invalid index '" << index.toString() << "'."
                << " Another Index has already been added to"
                << " the tree that has a conflicting index"
                << " separator at subindex '"
                << subindex << "'.",
                "Note that a separation point between two"
                << " indices counts as a subindex."
            );
        }
 
        TBTKAssert(
            currentIndex >= 0,
            "IndexedDataTree::add()",
            "Invalid Index. Negative indices not allowed, but the"
            << "index " << index.toString() << " have a negative"
            << " index" << " in position " << subindex << ".",
            "Compound indices such as {{1, 2, 3}, {4, 5, 6}} are"
            << " separated by IDX_SEPARATOR with the value '"
            << IDX_SEPARATOR << "' and are" << " represented as {1"
            << ", 2, 3, " << IDX_SEPARATOR << ", 4, 5, 6}. This is"
            << " the only allowed instance of negative numbers."
        );
 
        //Error detection:
        //If the current node has the indexIncluded flag set, another
        //Index with fewer subindices than the current Index have
        //previously been added to this node. This is an error because
        //different number of subindices is only allowed if the Indices
        //differ in one of their common indices.
        TBTKAssert(
            !indexIncluded,
            "IndexedDataTree::add()",
            "Incompatible indices. The Index " << index.toString()
            << " cannot be added because an Index of length "
            << subindex + 1 << " which exactly agrees with the "
            << subindex + 1 << " first indices of the current"
            << " Index has already been added.",
            ""
        );
 
        children[currentIndex].add(data, index, subindex+1);
    }
    else{
        //If the current subindex is the last, the index is marked as
        //included.
 
        //Error detection:
        //If children is non-zero, another Data with more subindices
        //have already been added to this node. This is an error
        //because different number of subindices is only allowed if the
        // indices differ in one of their common indices.
        TBTKAssert(
            children.size() == 0,
            "IndexedDataTree::add()",
            "Incompatible indices. The Index " << index.toString()
            << " cannot be added because a longer Index which"
            << " exactly agrees with the current Index in the"
            << " common indices has already been added.",
            ""
        );
 
        indexIncluded = true;
        this->data = data;
    }
}
 
template<typename Data>
bool IndexedDataTree<Data>::get(Data &data, const Index &index) const{
    return get(data, index, 0);
}
 
template<typename Data>
bool IndexedDataTree<Data>::get(
    Data &data,
    const Index &index,
    unsigned int subindex
) const{
    if(subindex < index.getSize()){
        //If the current subindex is not the last, continue to the next
        //node level.
 
        //Return false because this is a leaf node without the
        //indexIncluded flag set. This means it must have been added to
        //pad the parents child vector and not as a consequence of an
        //actual Index having been associated with the node.
        if(children.size() == 0 && !indexIncluded)
            return false;
 
        //Get current subindex.
        Subindex currentIndex = index.at(subindex);
 
        if(currentIndex.isIndexSeparator()){
            if(indexSeparator){
                return get(data, index, subindex+1);
            }
            else{
                TBTKExit(
                    "IndexedDataTree::get()",
                    "Invalid Index. Found IDX_SEPARATOR at"
                    << " subindex '" << subindex << "',"
                    << " but the node is not an index"
                    << " separator.",
                    ""
                );
            }
        }
 
        TBTKAssert(
            currentIndex >= 0,
            "IndexedDataTree::add()",
            "Invalid Index. Negative indices not allowed, but the"
            << " index " << index.toString() << " have a negative"
            << " index in position " << subindex << ".",
            ""
        );
 
        try{
            return children.at(currentIndex).get(data, index, subindex+1);
        }
        catch(std::out_of_range &e){
            return false;
        }
    }
    else{
        //If the current subindex is the last, try to extract the data.
        //Return true if successful but false if the data does not
        //exist.
        if(indexIncluded){
            data = this->data;
 
            return true;
        }
        else{
            return false;
        }
    }
}
 
template<typename Data>
Data& IndexedDataTree<Data>::get(const Index &index){
    //Casting is safe because we do not guarantee that the IndexedDataTree
    //is not modified. Casting away const from the returned reference is
    //therefore not a violation of any promisse made by this function.
    //See also "Avoiding Duplication in const and Non-const Member
    //Function" in S. Meyers, Effective C++.
    return const_cast<Data&>(
        static_cast<const IndexedDataTree<Data>*>(this)->get(index, 0)
    );
}
 
template<typename Data>
const Data& IndexedDataTree<Data>::get(const Index &index) const{
    return get(index, 0);
}
 
template<typename Data>
const Data& IndexedDataTree<Data>::get(
    const Index &index,
    unsigned int subindex
) const{
    if(subindex < index.getSize()){
        //If the current subindex is not the last, continue to the next
        //node level.
 
        //Throw ElementNotFoundException if the Index is not included.
        //This statement is executed if this is a leaf node without the
        //indexIncluded flag set. This means it must have been added to
        //pad the parents child vector and not as a consequence of an
        //actual Index having been associated with the node.
        if(children.size() == 0 && !indexIncluded){
            throw ElementNotFoundException(
                "IndexedDataTree()",
                TBTKWhere,
                "Tried to get element with Index '"
                + index.toString() + "', but no such element"
                + " exists.",
                ""
            );
        }
 
        //Get current subindex.
        Subindex currentIndex = index.at(subindex);
 
        if(currentIndex.isIndexSeparator()){
            if(indexSeparator){
                return get(index, subindex+1);
            }
            else{
                TBTKExit(
                    "IndexedDataTree::get()",
                    "Invalid Index. Found IDX_SEPARATOR at"
                    << " subindex '" << subindex << "',"
                    << " but the node is not an index"
                    << " separator.",
                    ""
                );
            }
        }
 
        TBTKAssert(
            currentIndex >= 0,
            "IndexedDataTree::get()",
            "Invalid Index. Negative indices not allowed, but the"
            << "index " << index.toString() << " have a negative"
            << " index" << " in position " << subindex << ".",
            "Compound indices such as {{1, 2, 3}, {4, 5, 6}} are"
            << " separated by IDX_SEPARATOR with the value '"
            << IDX_SEPARATOR << "' and are" << " represented as {1"
            << ", 2, 3, " << IDX_SEPARATOR << ", 4, 5, 6}. This is"
            << " the only allowed instance of negative numbers."
        );
 
        try{
            return children.at(currentIndex).get(index, subindex+1);
        }
        catch(std::out_of_range &e){
            throw ElementNotFoundException(
                "IndexedDataTree()",
                TBTKWhere,
                "Tried to get element with Index '"
                + index.toString() + "', but no such element"
                + " exists.",
                ""
            );
        }
    }
    else{
        //If the current subindex is the last, try to extract the data.
        //Return data if successful but throw ElementNotFoundException if the
        //data does not exist.
        if(indexIncluded){
            return data;
        }
        else{
            throw ElementNotFoundException(
                "IndexedDataTree()",
                TBTKWhere,
                "Tried to get element with Index '"
                + index.toString() + "', but no such element"
                + " exists.",
                ""
            );
        }
    }
}
 
template<typename Data>
Index IndexedDataTree<Data>::getFirstIndex() const{
    Index index;
    getFirstIndex(index);
 
    return index;
}
 
template<typename Data>
bool IndexedDataTree<Data>::getFirstIndex(Index &index) const{
    if(indexIncluded)
        return true;
 
    if(indexSeparator)
        index.pushBack(IDX_SEPARATOR);
 
    for(
        typename std::map<
            Subindex,
            IndexedDataTree
        >::const_iterator iterator = children.cbegin();
        iterator != children.cend();
        ++iterator
    ){
        Subindex subindex = iterator->first;
        index.pushBack(subindex);
        if(iterator->second.getFirstIndex(index))
            return true;
 
        index.popBack();
    }
 
    if(indexSeparator)
        index.popBack();
 
    return false;
}
 
template<typename Data>
Index IndexedDataTree<Data>::getNextIndex(const Index &index) const{
    if(index.getSize() == 0)
        return Index();
 
    Index nextIndex;
    getNextIndex(index, nextIndex);
 
    return nextIndex;
}
 
template<typename Data>
bool IndexedDataTree<Data>::getNextIndex(
    const Index &currentIndex,
    Index &nextIndex
) const{
    if(indexIncluded){
        if(currentIndex.equals(nextIndex))
            return false;
 
        return true;
    }
 
    if(indexSeparator)
        nextIndex.pushBack(IDX_SEPARATOR);
 
    bool hasSameIndexStructure = true;
    if(currentIndex.getSize() > nextIndex.getSize()){
        for(unsigned int n = 0; n < nextIndex.getSize(); n++){
            if(currentIndex[n] != nextIndex[n]){
                hasSameIndexStructure = false;
                break;
            }
        }
    }
    else{
        hasSameIndexStructure = false;
    }
 
    typename std::map<Subindex, IndexedDataTree>::const_iterator iterator;
    if(hasSameIndexStructure)
        iterator = children.find(currentIndex[nextIndex.getSize()]);
    else
        iterator = children.cbegin();
    while(iterator != children.cend()){
        nextIndex.pushBack(iterator->first);
        if(iterator->second.getNextIndex(currentIndex, nextIndex))
            return true;
        nextIndex.popBack();
 
        ++iterator;
    }
 
    if(indexSeparator)
        nextIndex.popBack();
 
    return false;
}
 
template<typename Data>
void IndexedDataTree<Data>::clear(){
    indexIncluded = false;
    children.clear();
}
 
template<typename Data>
unsigned int IndexedDataTree<Data>::getSizeInBytes() const{
    unsigned int size = sizeof(IndexedDataTree<Data>);
    for(
        typename std::map<
            Subindex,
            IndexedDataTree
        >::const_iterator iterator = children.cbegin();
        iterator != children.cend();
        ++iterator
    ){
        size += iterator->second.getSizeInBytes();
    }
 
    return size;
}
 
template<typename Data>
inline std::string IndexedDataTree<Data>::serialize(Mode mode) const{
    switch(mode){
    case Mode::JSON:
    {
        nlohmann::json j;
        j["id"] = "IndexedDataTree";
        j["indexIncluded"] = indexIncluded;
        j["indexSeparator"] = indexSeparator;
        j["data"] = Serializable::serialize(data, mode);
        j["children"] = nlohmann::json();
        for(
            typename std::map<
                Subindex,
                IndexedDataTree
            >::const_iterator iterator = children.cbegin();
            iterator != children.cend();
            ++iterator
        ){
            j["children"][
                iterator->first.serialize(
                    Serializable::Mode::JSON
                )
            ] = nlohmann::json::parse(
                iterator->second.serialize(
                    Serializable::Mode::JSON
                )
            );
        }
 
        return j.dump();
    }
    default:
        TBTKExit(
            "IndexedDataTree<Data>::serialize()",
            "Only Serializable::Mode::JSON is supported yet.",
            ""
        );
    }
}
 
template<typename Data>
typename IndexedDataTree<Data>::Iterator IndexedDataTree<Data>::begin(){
    return Iterator(this);
}
 
template<typename Data>
typename IndexedDataTree<Data>::ConstIterator IndexedDataTree<
    Data
>::begin() const{
    return ConstIterator(this);
}
 
template<typename Data>
typename IndexedDataTree<Data>::ConstIterator IndexedDataTree<
    Data
>::cbegin() const{
    return ConstIterator(this);
}
 
template<typename Data>
typename IndexedDataTree<Data>::Iterator IndexedDataTree<Data>::end(){
    return Iterator(this, true);
}
 
template<typename Data>
typename IndexedDataTree<Data>::ConstIterator IndexedDataTree<Data>::end() const{
    return ConstIterator(this, true);
}
 
template<typename Data>
typename IndexedDataTree<Data>::ConstIterator IndexedDataTree<Data>::cend() const{
    return ConstIterator(this, true);
}
 
template<typename Data> template<bool isConstIterator>
void IndexedDataTree<Data>::_Iterator<isConstIterator>::operator++(){
    currentIndex = indexedDataTree->getNextIndex(currentIndex);
}
 
template<typename Data> template<bool isConstIterator>
typename IndexedDataTree<Data>::template _Iterator<
    isConstIterator
>::DataReferenceType IndexedDataTree<Data>::_Iterator<
    isConstIterator
>::operator*(){
    return indexedDataTree->get(currentIndex);
}
 
template<typename Data> template<bool isConstIterator>
bool IndexedDataTree<Data>::_Iterator<isConstIterator>::operator==(
    const IndexedDataTree<Data>::_Iterator<isConstIterator> &rhs
) const{
    if(
        indexedDataTree == rhs.indexedDataTree
        && currentIndex.equals(rhs.currentIndex)
    ){
        return true;
    }
    else{
        return false;
    }
}
 
template<typename Data> template<bool isConstIterator>
bool IndexedDataTree<Data>::_Iterator<isConstIterator>::operator!=(
    const IndexedDataTree<Data>::_Iterator<isConstIterator> &rhs
) const{
    if(
        indexedDataTree != rhs.indexedDataTree
        || !currentIndex.equals(rhs.currentIndex)
    ){
        return true;
    }
    else{
        return false;
    }
}
 
template<typename Data> template<bool isConstIterator>
const Index& IndexedDataTree<Data>::_Iterator<
    isConstIterator
>::getCurrentIndex(
) const{
    return currentIndex;
}
 
template<typename Data> template<bool isConstIterator>
IndexedDataTree<Data>::_Iterator<isConstIterator>::_Iterator(
    IndexedDataTreePointerType indexedDataTree,
    bool end
){
    this->indexedDataTree = indexedDataTree;
    if(end)
        currentIndex = Index();
    else
        currentIndex = indexedDataTree->getFirstIndex();
}
 
//This is used to work around incompatibilities between nlohmann::json and
//CUDA. This effectively forbids instantiation of IndexedDataTree in CUDA code.
#endif
 
}; //End of namesapce TBTK
 
#endif