index_generator.tpp

/*---------------------------------------------------------------------------*\
 *
 *  bitpit
 *
 *  Copyright (C) 2015-2021 OPTIMAD engineering Srl
 *
 *  -------------------------------------------------------------------------
 *  License
 *  This file is part of bitpit.
 *
 *  bitpit is free software: you can redistribute it and/or modify it
 *  under the terms of the GNU Lesser General Public License v3 (LGPL)
 *  as published by the Free Software Foundation.
 *
 *  bitpit is distributed in the hope that it will be useful, but WITHOUT
 *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 *  FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
 *  License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with bitpit. If not, see <http://www.gnu.org/licenses/>.
 *
\*---------------------------------------------------------------------------*/
 
#ifndef __BITPIT_INDEX_GENERATOR_TPP__
#define __BITPIT_INDEX_GENERATOR_TPP__
 
namespace bitpit {
 
template<typename id_t>
const typename IndexGenerator<id_t>::id_type IndexGenerator<id_t>::NULL_ID = std::numeric_limits<typename IndexGenerator<id_t>::id_type>::min();

template<typename id_t>
IndexGenerator<id_t>::IndexGenerator()
    : m_latest(NULL_ID), m_lowest(NULL_ID), m_highest(NULL_ID)
{
 
}

    \return A new unique index.
*/
template<typename id_t>
typename IndexGenerator<id_t>::id_type IndexGenerator<id_t>::generate()
{
    // If the trash is empty generate a new id otherwise recycle the first id
    // in the trash.
    if (m_trash.empty()) {
        if (m_lowest == NULL_ID) {
            m_lowest  = 0;
            m_highest = 0;
            m_latest = m_lowest;
        } else if (m_lowest > 0) {
            --m_lowest;
            m_latest = m_lowest;
        } else {
            assert(m_highest < std::numeric_limits<id_type>::max());
            ++m_highest;
            m_latest = m_highest;
        }
    } else {
        m_latest = *(m_trash.begin());
        m_trash.erase(m_trash.begin());
    }
 
    return m_latest;
}

template<typename id_t>
typename IndexGenerator<id_t>::id_type IndexGenerator<id_t>::getLatest()
{
    return m_latest;
}

template<typename id_t>
typename IndexGenerator<id_t>::id_type IndexGenerator<id_t>::getHighest()
{
    return m_highest;
}

template<typename id_t>
bool IndexGenerator<id_t>::isAssigned(id_type id)
{
    // If the latest id is valid, it is assigned by definition
    if (m_latest >= 0 && id == m_latest) {
        return true;
    }
 
    // Ids past the highest one are not assigned
    if (id > m_highest) {
        return false;
    }
 
    // Ids before the lowest one are not assigned
    if (id < m_lowest) {
        return false;
    }
 
    // The id is assigned only if is not in the trash
    if (m_trash.count(id) > 0) {
        return false;
    }
 
    return true;
}

template<typename id_t>
void IndexGenerator<id_t>::setAssigned(typename IndexGenerator<id_t>::id_type id)
{
    // Check if the id has already been assigned
    if (isAssigned(id)) {
        throw std::runtime_error("Requested id has already been assigned.");
    }
 
    // If the id is past the highest assigned id we need to trash all the ids
    // from the highest assigned to this one (the generator only handles
    // contiguous ids), otherwise look for the id in the trash and, if found,
    // recycle it (if the id is not in the trash, this means it was already
    // an assigned id).
    if (m_highest == NULL_ID && m_lowest == NULL_ID) {
        m_lowest  = id;
        m_highest = id;
    } else if (id > m_highest) {
        typename std::set<id_type>::iterator trashIterator = m_trash.end();
        for (id_type wasteId = m_highest + 1; wasteId < id; ++wasteId) {
            trashIterator = m_trash.insert(trashIterator, wasteId);
        }
 
        m_highest = id;
    } else if (id < m_lowest) {
        typename std::set<id_type>::iterator trashIterator = m_trash.end();
        for (id_type wasteId = id + 1; wasteId < m_lowest; ++wasteId) {
            trashIterator = m_trash.insert(trashIterator, wasteId);
        }
 
        m_lowest = id;
    } else {
        assert(m_trash.count(id) > 0);
        eraseFromTrash(id);
    }
 
    // This is the latest assigned id
    m_latest = id;
}

template<typename id_t>
void IndexGenerator<id_t>::trash(typename IndexGenerator<id_t>::id_type id)
{
    assert(id != NULL_ID);
    assert(m_trash.count(id) == 0);
    assert(id >= m_lowest && id <= m_highest);
 
    // If we are trashing the highest or the lowest id we can update the
    // limits of the generator, otherwise we add the id to the trash.
    if (id == m_highest && id == m_lowest) {
        // If highest and lowest values are equal it means that we have
        // generated only one id. Since we are now trashing the only id
        // that has been generated, the trash must be emtpy.
        assert(m_trash.empty());
 
        m_lowest  = NULL_ID;
        m_highest = NULL_ID;
    } else if (id == m_highest) {
        --m_highest;
        auto trashIterator = m_trash.end();
        while (!m_trash.empty()) {
            --trashIterator;
            if (*trashIterator != m_highest) {
                break;
            }
 
            trashIterator = m_trash.erase(trashIterator);
            if (m_highest != 0) {
                --m_highest;
            } else {
                assert(m_trash.empty());
                m_highest = NULL_ID;
                break;
            }
        }
    } else if (id == m_lowest) {
        ++m_lowest;
        auto trashIterator = m_trash.begin();
        while (!m_trash.empty()) {
            if (*trashIterator != m_lowest) {
                break;
            }
 
            trashIterator = m_trash.erase(trashIterator);
            ++m_lowest;
        }
    } else {
        m_trash.insert(id);
    }
 
    // We only keep track of the latest assigned id, if we trash that id we
    // have no information of the previous assigned id.
    if (id == m_latest) {
        m_latest = NULL_ID;
    }
}

template<typename id_t>
void IndexGenerator<id_t>::reset()
{
    m_latest  = NULL_ID;
    m_lowest  = NULL_ID;
    m_highest = NULL_ID;
 
    m_trash.clear();
}

template<typename id_t>
void IndexGenerator<id_t>::eraseFromTrash(id_type id)
{
    // Erase the index
    m_trash.erase(id);
}

template<typename id_t>
int IndexGenerator<id_t>::getBinaryArchiveVersion() const
{
    return 1;
}

template<typename id_t>
void IndexGenerator<id_t>::dump(std::ostream &stream) const
{
    utils::binary::write(stream, getBinaryArchiveVersion());
    utils::binary::write(stream, m_latest);
    utils::binary::write(stream, m_lowest);
    utils::binary::write(stream, m_highest);
 
    utils::binary::write(stream, m_trash.size());
    for (id_type id : m_trash) {
        utils::binary::write(stream, id);
    }
}

template<typename id_t>
void IndexGenerator<id_t>::restore(std::istream &stream)
{
    // Version
    int version;
    utils::binary::read(stream, version);
    if (version != getBinaryArchiveVersion()) {
        throw std::runtime_error ("The version of the file does not match the required version");
    }
 
    // Generator data
    utils::binary::read(stream, m_latest);
    utils::binary::read(stream, m_lowest);
    utils::binary::read(stream, m_highest);
 
    size_t nTrashedIds;
    utils::binary::read(stream, nTrashedIds);
 
    std::set<id_type>().swap(m_trash);
 
    for (size_t i = 0; i < nTrashedIds; ++i) {
        id_type id;
        utils::binary::read(stream, id);
        m_trash.insert(id);
    }
}
 
}
 
#endif