piercedKernel.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_PIERCED_KERNEL_TPP__
#define __BITPIT_PIERCED_KERNEL_TPP__
 
namespace bitpit {
 
// Definition of static constants of PiercedKernel
template<typename id_t>
const std::size_t PiercedKernel<id_t>::MAX_PENDING_HOLES = 16384;
 
template<typename id_t>
PiercedKernel<id_t>::PiercedKernel()
    : BasePiercedKernel()
{
    clear();
}
 
template<typename id_t>
PiercedKernel<id_t>::PiercedKernel(std::size_t n)
    : BasePiercedKernel()
{
    clear();
 
    reserve(n);
}
 
template<typename id_t>
PiercedKernel<id_t>::~PiercedKernel()
{
    for (PiercedStorageSyncSlave<id_t> *storage : getStorages()) {
        storage->unsetKernel();
    }
}
 
template<typename id_t>
void PiercedKernel<id_t>::updateId(const id_t &currentId, const id_t &updatedId)
{
    // Validate the id
    validateId(updatedId);
 
    // Update the id
    setPosId(getPos(currentId), updatedId);
    m_pos.erase(currentId);
}
 
template<typename id_t>
typename PiercedKernel<id_t>::ClearAction PiercedKernel<id_t>::clear(bool release)
{
    ClearAction syncAction = _clear(release);
 
    // Update the storage
    processSyncAction(syncAction);
 
    return syncAction;
}
 
 
template<typename id_t>
typename PiercedKernel<id_t>::ClearAction PiercedKernel<id_t>::_clear(bool release)
{
    // Clear positions
    m_ids.clear();
    m_pos.clear();
    if (release) {
        std::vector<id_t>().swap(m_ids);
        std::unordered_map<id_t, std::size_t, PiercedHasher>().swap(m_pos);
    }
 
    // Reset begin and end
    setBeginPos(0);
    setEndPos(0);
 
    // Clear holes
    holesClear(release);
 
    // There are no dirty positions
    m_dirty_begin_pos = m_end_pos;
 
    // Generate the sync action
    ClearAction syncAction;
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::ReserveAction PiercedKernel<id_t>::reserve(std::size_t n)
{
    ReserveAction syncAction = _reserve(n);
 
    // Update the storage
    processSyncAction(syncAction);
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::ReserveAction PiercedKernel<id_t>::_reserve(std::size_t n)
{
    // Update the kernel
    m_ids.reserve(n);
    m_pos.reserve(n);
 
    // Generate the sync action
    ReserveAction syncAction;
    syncAction.info[PiercedSyncAction::INFO_SIZE] = n;
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::ResizeAction PiercedKernel<id_t>::resize(std::size_t n)
{
    ResizeAction syncAction = _resize(n);
 
    // Update the storage
    processSyncAction(syncAction);
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::ResizeAction PiercedKernel<id_t>::_resize(std::size_t n)
{
    // If the size of the kernel is already the requested size there is
    // nothing to do.
    if (n == size()) {
        ResizeAction syncAction(ResizeAction::TYPE_NOOP);
 
        return syncAction;
    }
 
    // A request for a size equal to 0 is equivalent to a clear.
    if (n == 0) {
        _clear();
 
        ResizeAction syncAction(ResizeAction::TYPE_CLEAR);
 
        return syncAction;
    }
 
    // If the requested size is greater that the current size we may need to
    // reserve space to allow the kernel to reach the requested size.
    if (n > size()) {
        _reserve(n);
 
        ResizeAction syncAction(ResizeAction::TYPE_RESERVE);
        syncAction.info[PiercedSyncAction::INFO_SIZE] = rawSize();
 
        return syncAction;
    }
 
    // If the requested size is smaller that the current size
    // we need to perform a real resize.
 
    // Flush holes
    holesFlush();
 
    // Find the id of the last element
    id_t last_stored_id = getSizeMarker(n - 1);
 
    // Find the last position
    std::size_t last_used_pos = getPos(last_stored_id);
 
    // Shrink the kernel
    rawShrink(last_used_pos + 1);
 
    // Generate the sync action
    ResizeAction syncAction(ResizeAction::TYPE_RESIZE);
    syncAction.info[PiercedSyncAction::INFO_SIZE] = rawSize();
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::SortAction PiercedKernel<id_t>::sort()
{
    SortAction syncAction = _sort(m_begin_pos, m_end_pos);
 
    // Update the storage
    processSyncAction(syncAction);
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::SortAction PiercedKernel<id_t>::sortAfter(id_t referenceId, bool inclusive)
{
    // Get the reference position
    std::size_t referencePos = getPos(referenceId);
    if (!inclusive) {
        referencePos++;
    }
 
    // Sorte the
    SortAction syncAction = _sort(referencePos, m_end_pos);
 
    // Update the storage
    processSyncAction(syncAction);
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::SortAction PiercedKernel<id_t>::sortBefore(id_t referenceId, bool inclusive)
{
    // Get the reference position
    std::size_t referencePos = getPos(referenceId);
    if (inclusive) {
        referencePos++;
    }
 
    // Sort the container
    SortAction syncAction = _sort(m_begin_pos, referencePos);
 
    // Update the storage
    processSyncAction(syncAction);
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::SortAction PiercedKernel<id_t>::_sort(std::size_t beginPos, std::size_t endPos)
{
    // Squeeze the kernel
    //
    // After the squeeze there will be no holes in the kernel.
    SqueezeAction squeezeAction = _squeeze();
    const std::vector<std::size_t> &squeezePermutations = *(squeezeAction.data);
    bool squeezed = (squeezeAction.data.get() != nullptr);
 
    // Get updated kernel size
    std::size_t updatedKernelRawSize = rawSize();
 
    // Update the sort range
    if (squeezed) {
        std::size_t previousBeginPos = beginPos;
        std::size_t previousEndPos   = endPos;
        for (std::size_t i = m_begin_pos; i < m_end_pos; ++i) {
            std::size_t previousPos = squeezePermutations[i];
            if (previousPos == previousBeginPos) {
                beginPos = i;
            }
            if ((previousPos + 1) == previousEndPos) {
                endPos = i + 1;
                break;
            }
        }
    }
 
    // Evaluates the sort permutations
    std::vector<std::size_t> sortPermutations(updatedKernelRawSize);
    for (std::size_t i = 0; i < updatedKernelRawSize; ++i) {
        sortPermutations[i] = i;
    }
 
    std::sort(sortPermutations.begin() + beginPos, sortPermutations.begin() + endPos, idLess(m_ids));
 
    // Create the sync action
    SortAction syncAction;
    syncAction.info[PiercedSyncAction::INFO_SIZE] = updatedKernelRawSize;
    if (squeezed) {
        syncAction.importData(std::vector<std::size_t>(squeezePermutations));
        std::vector<std::size_t> &permutations = *(syncAction.data);
        for (std::size_t i = beginPos; i < endPos; ++i) {
            permutations[i] = squeezePermutations[sortPermutations[i]];
        }
    } else {
        syncAction.importData(std::vector<std::size_t>(sortPermutations));
    }
 
    // Sort the ids
    //
    // NOTE: the reorder function will destroy the permutation vector
    utils::reorderVector<id_t>(sortPermutations, m_ids, updatedKernelRawSize);
 
    // Update the positions
    m_pos.clear();
    for (std::size_t i = 0; i < updatedKernelRawSize; ++i) {
        m_pos[m_ids[i]] = i;
    }
 
    // Return the permutations
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::SqueezeAction PiercedKernel<id_t>::squeeze()
{
    SqueezeAction syncAction = _squeeze();
 
    // Update the storage
    processSyncAction(syncAction);
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::SqueezeAction PiercedKernel<id_t>::_squeeze()
{
    // Flush changes
    flush();
 
    // Sort the holes
    //
    // After being flushed, the container will contain only regular holes.
    holesSortRegular();
 
    // Get kernel size
    std::size_t kernelSize    = size();
    std::size_t kernelRawSize = rawSize();
 
    // Initialize the sync action
    SqueezeAction syncAction;
    syncAction.info[PiercedSyncAction::INFO_SIZE] = kernelSize;
 
    // Compact the kernel
    std::size_t nHoles = holesCount();
    if (nHoles != 0) {
        // Initialize sync data
        syncAction.importData(std::vector<std::size_t>(kernelRawSize));
        std::vector<std::size_t> &permutations = *(syncAction.data);
 
        // Move the elements
        std::size_t firstPosToUpdate;
        if (m_begin_pos == 0) {
            firstPosToUpdate = m_holes[m_holes_regular_end - 1];
        } else {
            firstPosToUpdate = 0;
        }
 
        for (std::size_t pos = 0; pos < firstPosToUpdate; ++pos) {
            permutations[pos] = pos;
        }
 
        std::size_t offset = 0;
        for (std::size_t pos = firstPosToUpdate; pos < m_end_pos; pos++) {
            if (offset < nHoles && m_holes[m_holes_regular_end - offset - 1] == pos) {
                permutations[m_end_pos - 1 - offset] = pos;
                ++offset;
                continue;
            }
 
            id_t id = m_ids[pos];
            std::size_t updatedPos = pos - offset;
 
            setPosId(updatedPos, id);
            setPosEmptyId(pos, pos + 1);
            permutations[updatedPos] = pos;
        }
 
        for (std::size_t pos = m_end_pos; pos < rawSize(); ++pos) {
            permutations[pos] = pos;
        }
 
        // Clear the holes
        holesClear(true);
 
        // Reset begin position
        setBeginPos(0);
 
        // Shrink the kernel
        rawShrink(kernelSize);
    }
 
    // Shrink to fit
    _shrinkToFit();
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::ShrinkToFitAction PiercedKernel<id_t>::shrinkToFit()
{
    ShrinkToFitAction syncAction = _shrinkToFit();
 
    // Update the storage
    processSyncAction(syncAction);
 
    return syncAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::ShrinkToFitAction PiercedKernel<id_t>::_shrinkToFit()
{
    // Update the kernel
    m_ids.shrink_to_fit();
 
    // Generate the sync action
    ShrinkToFitAction syncAction;
 
    return syncAction;
}
 
template<typename id_t>
void PiercedKernel<id_t>::swap(PiercedKernel &other) noexcept
{
    PiercedSyncMaster::swap(other);
 
    std::swap(other.m_begin_pos, m_begin_pos);
    std::swap(other.m_end_pos, m_end_pos);
    std::swap(other.m_dirty_begin_pos, m_dirty_begin_pos);
    std::swap(other.m_ids, m_ids);
    std::swap(other.m_pos, m_pos);
    std::swap(other.m_holes, m_holes);
    std::swap(other.m_holes_regular_begin, m_holes_regular_begin);
    std::swap(other.m_holes_regular_end, m_holes_regular_end);
    std::swap(other.m_holes_regular_sorted, m_holes_regular_sorted);
    std::swap(other.m_holes_pending_begin, m_holes_pending_begin);
    std::swap(other.m_holes_pending_end, m_holes_pending_end);
    std::swap(other.m_holes_pending_sorted, m_holes_pending_sorted);
}
 
template<typename id_t>
void PiercedKernel<id_t>::flush()
{
    // Flush pending holes
    holesFlush();
}
 
template<typename id_t>
void PiercedKernel<id_t>::dump() const
{
    std::cout << "----------------[ DUMP ]----------------" << std::endl;
 
    std::cout << std::endl;
    std::cout << " size: " << size() << std::endl;
 
    std::cout << " m_holes_regular_begin: " << m_holes_regular_begin << std::endl;
    std::cout << " m_holes_regular_end  : " << m_holes_regular_end << std::endl;
 
    std::cout << std::endl;
    std::cout << " Regular holes: " << std::endl;
    for (std::size_t k = m_holes_regular_begin; k < m_holes_regular_end; ++k) {
        std::cout << m_holes[k] << std::endl;
    }
 
    std::cout << std::endl;
    std::cout << " m_holes_pending_begin: " << m_holes_pending_begin << std::endl;
    std::cout << " m_holes_pending_end  : " << m_holes_pending_end << std::endl;
 
    std::cout << std::endl;
    std::cout << " Pending holes" << std::endl;
    for (std::size_t k = m_holes_pending_begin; k < m_holes_pending_end; ++k) {
        std::cout << m_holes[k] << std::endl;
    }
 
    std::cout << std::endl;
    std::cout << " m_begin_pos: " << m_begin_pos << std::endl;
    std::cout << " m_end_pos: " <<  m_end_pos << std::endl;
    std::cout << " Stored ids: " << std::endl;
    if (rawSize() > 0) {
        for (std::size_t k = 0; k < m_end_pos; ++k) {
            std::cout << m_ids[k] << std::endl;
        }
    } else {
        std::cout << "None" << std::endl;
    }
 
    std::cout << std::endl;
    std::cout << " Poistion map: " << std::endl;
    if (size() > 0) {
        for (auto itr = m_pos.cbegin(); itr != m_pos.cend(); ++itr) {
            std::cout << itr->first << " -> " << itr->second << std::endl;
        }
    } else {
        std::cout << "None" << std::endl;
    }
 
    std::cout << "----------------------------------------" << std::endl;
}
 
template<typename id_t>
void PiercedKernel<id_t>::checkIntegrity() const
{
    // Check if the elements and their position match
    for (const auto &entry : m_pos) {
        id_t id = entry.first;
        std::size_t pos = entry.second;
        if (m_ids[pos] != id) {
            std::cout << " Position " << pos << " should contain the element with id " << id << std::endl;
            std::cout << " but it contains the element with id " << m_ids[pos] << std::endl;
            throw std::runtime_error("Integrity check error");
        }
    }
 
    for (std::size_t pos = m_begin_pos; pos < m_end_pos; ++pos) {
        id_t id = m_ids[pos];
        if (id >= 0) {
            if (m_pos.count(id) == 0) {
                std::cout << " Position " << pos << " contains the element with id " << id << std::endl;
                std::cout << " but the position map doesn't contain that element" << std::endl;
                throw std::runtime_error("Integrity check error");
            } else if (m_pos.at(id) != pos) {
                std::cout << " Position " << pos << " contains the element with id " << id << std::endl;
                std::cout << " but the position map claims that the element is at position " << m_pos.at(id) << std::endl;
                throw std::runtime_error("Integrity check error");
            }
        }
    }
 
    // Check if the number of elements visited by the iterator matches the size of the kernel
    std::size_t n = 0;
    for (auto it = begin(); it != end(); ++it) {
        ++n;
    }
 
    if (n != size()) {
        std::cout << " The number of elements visited by the iterator doesn't match the size of the kernel" << std::endl;
        std::cout << " The iterator has visited " << n << "elements" << std::endl;
        std::cout << " The size of the kernel is " << size() << std::endl;
        throw std::runtime_error("Integrity check error");
    }
 
    // Check the consistency of the ids of elements associated with empty positions
    //
    // The id of an empty element contains the distance, measured in number of elements, between
    // the current element and the next element the iterator should jump to (the distance is
    // negative). If the id of an element is lower than -1, the ids of the following elements
    // should be consecutive until they reach -1.
    if (!empty()) {
        std::size_t pos = 0;
        while (pos < m_ids.size() - 1) {
            for (std::size_t i = pos; i < m_ids.size(); ++i) {
                // Skip non-empty positions
                if (m_ids[i] >= 0) {
                    pos = i + 1;
                    break;
                }
 
                // Skip empty positions with a distance from a non-empty element equal to one
                if (m_ids[i + 1] >= 0 && m_ids[i] == - 1) {
                    pos = i + 2;
                    break;
                }
 
                // Check if ids are consecutive
                if ((m_ids[i] - m_ids[i + 1] != -1) && m_ids[i] != -1) {
                    std::cout << " The ids associated with empty positions are not consecutive" << std::endl;
                    std::cout << " Position " << i << " is associated with id " << m_ids[i] << std::endl;
                    std::cout << " Position " << (i + 1) << " is associated with id " << m_ids[i + 1] << std::endl;
                    throw std::runtime_error("Integrity check error");
                }
            }
        }
    }
}
 
template<typename id_t>
bool PiercedKernel<id_t>::contiguous() const
{
    return (holesCount() == 0);
}
 
template<typename id_t>
bool PiercedKernel<id_t>::empty() const
{
    return m_pos.empty();
}
 
template<typename id_t>
bool PiercedKernel<id_t>::isIteratorSlow()
{
    return (m_dirty_begin_pos < m_end_pos);
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::maxSize() const
{
    return m_ids.max_size();
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::size() const
{
    return m_pos.size();
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::rawSize() const
{
    return m_ids.size();
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::capacity() const
{
    return m_ids.capacity();
}
 
template<typename id_t>
bool PiercedKernel<id_t>::contains(id_t id) const
{
    return (m_pos.count(id) != 0);
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::count(id_t id) const
{
    return m_pos.count(id);
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::getRawIndex(id_t id) const
{
    return getPos(id);
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::evalFlatIndex(id_t id) const
{
    std::size_t pos  = getPos(id);
 
    // Initialize flat id with the position of the element
    std::size_t flat = pos;
 
    // Subtract pending holes before position
    if (holesCountPending() > 0) {
        holes_const_iterator pending_begin_itr = m_holes.cbegin() + m_holes_pending_begin;
        holes_const_iterator pending_end_itr   = m_holes.cbegin() + m_holes_pending_end;
 
        std::size_t nHolesBefore = 0;
        for (auto itr = pending_begin_itr; itr != pending_end_itr; ++itr) {
            if (*itr <= pos) {
                ++nHolesBefore;
            }
        }
 
        flat -= nHolesBefore;
    }
 
    // Subtract regular holes before position
    if (holesCountRegular() > 0) {
        holes_const_iterator regular_begin_itr = m_holes.cbegin() + m_holes_regular_begin;
        holes_const_iterator regular_end_itr   = m_holes.cbegin() + m_holes_regular_end;
 
        std::size_t nHolesBefore = 0;
        for (auto itr = regular_begin_itr; itr != regular_end_itr; ++itr) {
            if (*itr <= pos) {
                ++nHolesBefore;
            }
        }
 
        flat -= nHolesBefore;
    }
 
    // Done
    return flat;
}
 
template<typename id_t>
std::vector<id_t> PiercedKernel<id_t>::getIds(bool ordered) const
{
    std::size_t nIds = size();
 
    // Initialize the vector
    std::vector<id_t> ids;
    if (nIds == 0) {
        return ids;
    }
 
    // Resize the vector
    ids.resize(nIds);
 
    // Extract the ids
    std::size_t n   = 0;
    std::size_t pos = m_begin_pos;
    while (true) {
        ids[n] = m_ids[pos];
        if (n == nIds - 1) {
            break;
        }
 
        n++;
        pos = findNextUsedPos(pos);
    }
 
    // Sort the ids
    if (ordered) {
        std::sort(ids.begin(), ids.end());
    }
 
    return ids;
}
 
template<typename id_t>
id_t PiercedKernel<id_t>::getSizeMarker(std::size_t targetSize, const id_t &fallback)
{
    // If the size is zero, we return the first element, if the target
    // size is equal to the size minus one we return the last element,
    // if the target size is greater or equal the current kernel size
    // we return the fallback value.
    if (targetSize >= size()) {
        return fallback;
    } else if (targetSize == 0) {
        return m_ids[m_begin_pos];
    } else if (targetSize == (size() - 1)) {
        return m_ids[m_end_pos - 1];
    }
 
    // Sort the holes
    holesSortRegular();
    holesSortPending();
 
    // Iterate to find the position before wihch there is the
    // requeste number of element.
    holes_iterator regular_begin_itr = m_holes.begin() + m_holes_regular_begin;
    holes_iterator regular_hole_itr  = m_holes.begin() + m_holes_regular_end;
 
    holes_iterator pending_begin_itr = m_holes.begin() + m_holes_pending_begin;
    holes_iterator pending_hole_itr  = m_holes.begin() + m_holes_pending_end;
 
    std::size_t nEmpties  = 0;
    std::size_t markerPos = targetSize;
    while (true) {
        if (isPosEmpty(markerPos)) {
            markerPos = findNextUsedPos(markerPos - 1);
        }
 
        // Count the number of holes and pending deletes before the
        // current marker position
        if (regular_hole_itr != regular_begin_itr) {
            holes_iterator itr_previous = regular_hole_itr;
            regular_hole_itr = std::upper_bound(regular_begin_itr, regular_hole_itr, markerPos, std::greater<std::size_t>());
            nEmpties += std::distance(regular_hole_itr, itr_previous);
        }
 
        if (pending_hole_itr != pending_begin_itr) {
            holes_iterator itr_previous = pending_hole_itr;
            pending_hole_itr = std::upper_bound(pending_begin_itr, pending_hole_itr, markerPos, std::greater<std::size_t>());
            nEmpties += std::distance(pending_hole_itr, itr_previous);
        }
 
        // Get the marker size
        //
        // If we have reached the target size we can exit, otherwise
        // we update the marker and we continue iterating
        std::size_t markerSize = markerPos - nEmpties;
        if (markerSize == targetSize) {
            break;
        } else {
            markerPos += targetSize - markerSize;
        }
    }
 
    return m_ids[markerPos];
}
 
template<typename id_t>
typename PiercedKernel<id_t>::const_iterator PiercedKernel<id_t>::find(const id_t &id) const noexcept
{
    auto iterator = m_pos.find(id);
    if (iterator != m_pos.end()) {
        return rawFind(iterator->second);
    } else {
        return end();
    }
}
 
template<typename id_t>
typename PiercedKernel<id_t>::const_iterator PiercedKernel<id_t>::rawFind(std::size_t pos) const noexcept
{
    return const_iterator(this, pos);
}
 
template<typename id_t>
typename PiercedKernel<id_t>::const_iterator PiercedKernel<id_t>::begin() const noexcept
{
    return cbegin();
}
 
template<typename id_t>
typename PiercedKernel<id_t>::const_iterator PiercedKernel<id_t>::end() const noexcept
{
    return cend();
}
 
template<typename id_t>
typename PiercedKernel<id_t>::const_iterator PiercedKernel<id_t>::cbegin() const noexcept
{
    return rawFind(m_begin_pos);
}
 
template<typename id_t>
typename PiercedKernel<id_t>::const_iterator PiercedKernel<id_t>::cend() const noexcept
{
    return rawFind(m_end_pos);
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::getPos(id_t id) const
{
    return m_pos.at(id);
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::getFirstUsedPos() const
{
    if (empty()) {
        throw std::out_of_range("Vector is empty");
    }
 
    return m_begin_pos;
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::getLastUsedPos() const
{
    if (empty()) {
        throw std::out_of_range("Vector is empty");
    }
 
    return m_end_pos - 1;
}
 
 
template<typename id_t>
typename PiercedKernel<id_t>::FillAction PiercedKernel<id_t>::fillHead(id_t id)
{
    // Check if there is a pending hole that can be filled
    if (m_holes_pending_begin != m_holes_pending_end) {
        // Sort pending holes
        holesSortPending();
 
        // The last hole is the one with the lowest position
        return fillHole(m_holes_pending_end - 1, id);
    }
 
    // Check if there is a regular hole that can be filled
    if (m_holes_regular_begin != m_holes_regular_end) {
        // Sort regular holes
        holesSortRegular();
 
        // The last hole is the one with the lowest position
        return fillHole(m_holes_regular_end - 1, id);
    }
 
    // There are no holes that can be filled
    return fillAppend(id);
}
 
template<typename id_t>
typename PiercedKernel<id_t>::FillAction PiercedKernel<id_t>::fillTail(id_t id)
{
    // Check if there is a pending hole that can be filled
    if (m_holes_pending_begin != m_holes_pending_end) {
        // Sort pending holes
        holesSortPending();
 
        // The first hole is the one with the highest position
        return fillHole(m_holes_pending_begin, id);
    }
 
    // Check if there is a regular hole that can be filled
    if (m_holes_regular_begin != m_holes_regular_end) {
        // Sort regular holes
        holesSortRegular();
 
        // The first hole is the one with the lowest position
        return fillHole(m_holes_regular_begin, id);
    }
 
    // There are no holes that can be filled
    return fillAppend(id);
}
 
template<typename id_t>
typename PiercedKernel<id_t>::FillAction PiercedKernel<id_t>::fillAfter(id_t referenceId, id_t id)
{
    // Get the reference position
    std::size_t referencePos = getPos(referenceId);
 
    // Check if there is a pending hole that can be filled
    if (m_holes_pending_begin != m_holes_pending_end) {
        // Sort pending holes
        holesSortPending();
 
        // The first hole is the one with the highest position, if the
        // position of this hole is greater than the reference position
        // it is possible to use it.
        std::size_t hole = m_holes_pending_begin;
        if (m_holes[hole] > referencePos) {
            return fillHole(hole, id);
        }
    }
 
    // Check if there is a regular hole that can be filled
    if (m_holes_regular_begin != m_holes_regular_end) {
        // Sort regular holes
        holesSortRegular();
 
        // The first hole is the one with the highest position, if the
        // position of this hole is greater than the reference position
        // it is possible to use it.
        std::size_t hole = m_holes_regular_begin;
        if (m_holes[hole] > referencePos) {
            return fillHole(hole, id);
        }
    }
 
    // There are no holes that can be filled
    return fillAppend(id);
}
 
template<typename id_t>
typename PiercedKernel<id_t>::FillAction PiercedKernel<id_t>::fillBefore(id_t referenceId, id_t id)
{
    // Get the reference position
    std::size_t referencePos = getPos(referenceId);
 
    // Check if there is a pending hole that can be filled
    if (m_holes_pending_begin != m_holes_pending_end) {
        // Sort pending holes
        holesSortPending();
 
        // The last hole is the one with the lowest position, if the
        // position of this hole is greater than the reference position
        // it is possible to use it.
        std::size_t hole = m_holes_pending_end - 1;
        if (m_holes[hole] < referencePos) {
            return fillHole(hole, id);
        }
    }
 
    // Check if there is a regular hole that can be filled
    if (m_holes_regular_begin != m_holes_regular_end) {
        // Sort regular holes
        holesSortRegular();
 
        // The last hole is the one with the lowest position, if the
        // position of this hole is greater than the reference position
        // it is possible to use it.
        std::size_t hole = m_holes_regular_end - 1;
        if (m_holes[hole] < referencePos) {
            return fillHole(hole, id);
        }
    }
 
    // There are no holes that can be filled
    return fillInsert(referencePos, id);
}
 
template<typename id_t>
typename PiercedKernel<id_t>::FillAction PiercedKernel<id_t>::fillAppend(id_t id)
{
    // Check if the id is valid
    validateId(id);
 
    // Add the id
    m_ids.emplace_back(id);
 
    // Update last used position
    setEndPos(rawSize());
 
    // Update the id map
    m_pos[id] = m_end_pos - 1;
 
    // Update the storage
    FillAction fillAction(FillAction::TYPE_APPEND);
    fillAction.info[PiercedSyncAction::INFO_POS] = m_end_pos - 1;
    processSyncAction(fillAction);
 
    // Return the fill action
    return fillAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::FillAction PiercedKernel<id_t>::fillHole(std::size_t hole, id_t id)
{
    // Validate the id
    validateId(id);
 
    // Get the position of the hole
    std::size_t pos = m_holes[hole];
 
    // Fill the hole
    setPosId(pos, id);
 
    // Remove the holes from the kernel
    if (hole >= m_holes_pending_begin) {
        int nPendings = holesCountPending();
        if (nPendings > 1) {
            if (hole == (m_holes_pending_end - 1)) {
                --m_holes_pending_end;
            } else if (hole == m_holes_pending_begin) {
                ++m_holes_pending_begin;
            } else {
                throw std::out_of_range("Only holes at the beginning or at the end of the kernel can be filled");
            }
        } else {
            holesClearPending();
        }
    } else {
        int nRegulars = holesCountRegular();
        if (nRegulars > 1) {
            if (hole == (m_holes_regular_end - 1)) {
                --m_holes_regular_end;
            } else if (hole == m_holes_regular_begin) {
                ++m_holes_regular_begin;
            } else {
                throw std::out_of_range("Only holes at the beginning or at the end of the kernel can be filled");
            }
        } else {
            holesClearRegular();
        }
    }
 
    // Update the begin position
    //
    // There are no holes past the end of the vector, this means that only
    // the begin position may need an update.
    if (pos < m_begin_pos) {
        setBeginPos(pos);
    }
 
    // Update the position of the empty elements before the current one
    //
    // It is necessary to ensure that the empty elements just before the
    // current one are correctly set, otherwise it will not be possible
    // to iterate through the kernel.
    std::size_t previousPos = pos;
    while (previousPos > 0) {
        --previousPos;
        if (!isPosEmpty(previousPos)) {
            break;
        }
 
        id_t previousId = m_ids[previousPos];
        if (previousId == -1 || (std::size_t) std::abs(previousId) == (pos - previousPos)) {
            break;
        }
 
        setPosEmptyId(previousPos, pos);
    }
 
    // Update the storage
    FillAction fillAction(FillAction::TYPE_OVERWRITE);
    fillAction.info[PiercedSyncAction::INFO_POS] = pos;
    processSyncAction(fillAction);
 
    // Return the fill action
    return fillAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::FillAction PiercedKernel<id_t>::fillInsert(std::size_t pos, id_t id)
{
    // If the position at which we want to insert an element is a hole there
    // was an error somewhere. Before inserting a new position the hole needs
    // to be filled first.
    if (isPosEmpty(pos)) {
        throw std::out_of_range("Before inserting a new position the hole needs to be filled first");
    }
 
    // We cannot insert elements past the last position
    if (pos >= m_end_pos) {
        throw std::out_of_range("Unable to insert elements past the last position");
    }
 
    // Check if the id is valid
    validateId(id);
 
    // Add the id
    m_ids.emplace(m_ids.begin() + pos, id);
 
    // Update last used position
    setEndPos(rawSize());
 
    // Update the id map
    for (std::size_t i = pos + 1; i < m_end_pos; ++i) {
        id_t id_i = m_ids[i];
        if (id_i >= 0) {
            m_pos[id_i] = i;
        }
    }
    m_pos[id] = pos;
 
    // Update the regular holes
    if (m_holes_regular_begin != m_holes_regular_end) {
        holes_iterator regular_begin_itr = m_holes.begin() + m_holes_regular_begin;
        holes_iterator regular_end_itr   = m_holes.begin() + m_holes_regular_end;
 
        holes_iterator update_begin_itr = regular_begin_itr;
        holes_iterator update_end_itr   = upper_bound(regular_begin_itr, regular_end_itr, pos, std::greater<std::size_t>());
        for (auto itr = update_begin_itr; itr != update_end_itr; itr++) {
            (*itr)++;
        }
    }
 
    // Update the pending holes
    if (m_holes_pending_begin != m_holes_pending_end) {
        holes_iterator pending_begin_itr = m_holes.begin() + m_holes_pending_begin;
        holes_iterator pending_end_itr   = m_holes.begin() + m_holes_pending_end;
 
        holes_iterator update_begin_itr = pending_begin_itr;
        holes_iterator update_end_itr   = upper_bound(pending_begin_itr, pending_end_itr, pos, std::greater<std::size_t>());
        for (auto itr = update_begin_itr; itr != update_end_itr; itr++) {
            (*itr)++;
        }
    }
 
    // Update the storage
    FillAction fillAction(FillAction::TYPE_INSERT);
    fillAction.info[PiercedSyncAction::INFO_POS] = pos;
    processSyncAction(fillAction);
 
    // Return the fill action
    return fillAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::MoveAction PiercedKernel<id_t>::moveAfter(id_t referenceId, id_t id, bool flush)
{
    assert(referenceId != id);
 
    // Disables the synchronization
    bool syncEnabled = isSyncEnabled();
    if (syncEnabled) {
        setSyncEnabled(false);
    }
 
    // Pierce the position
    std::size_t initialPos = getPos(id);
    pierce(initialPos, flush);
 
    // Insert the element in the updated position
    FillAction fillAction = fillAfter(referenceId, id);
 
    // Re-enables the synchronization
    if (syncEnabled) {
        setSyncEnabled(true);
    }
 
    // Update the storage
    typename MoveAction::MoveActionType moveActionType;
    switch (static_cast<typename FillAction::FillActionType>(fillAction.type)) {
 
    case FillAction::TYPE_APPEND:
        moveActionType = MoveAction::TYPE_APPEND;
        break;
 
    case FillAction::TYPE_INSERT:
        moveActionType = MoveAction::TYPE_INSERT;
        break;
 
    case FillAction::TYPE_OVERWRITE:
        moveActionType = MoveAction::TYPE_OVERWRITE;
        break;
 
    default:
        BITPIT_UNREACHABLE("This action is not handled");
        moveActionType = MoveAction::TYPE_UNDEFINED;
        break;
 
    }
 
    MoveAction moveAction(moveActionType);
    moveAction.info[PiercedSyncAction::INFO_POS_FIRST]  = initialPos;
    moveAction.info[PiercedSyncAction::INFO_POS_SECOND] = fillAction.info[PiercedSyncAction::INFO_POS];
    processSyncAction(moveAction);
 
    // Return the move action
    return moveAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::MoveAction PiercedKernel<id_t>::moveBefore(id_t referenceId, id_t id, bool flush)
{
    assert(referenceId != id);
 
    // Disables the synchronization
    bool syncEnabled = isSyncEnabled();
    if (syncEnabled) {
        setSyncEnabled(false);
    }
 
    // Pierce the position
    std::size_t initialPos = getPos(id);
    pierce(initialPos, flush);
 
    // Insert the element in the updated position
    FillAction fillAction = fillBefore(referenceId, id);
 
    // Re-enables the synchronization
    if (syncEnabled) {
        setSyncEnabled(true);
    }
 
    // Update the storage
    typename MoveAction::MoveActionType moveActionType;
    switch (static_cast<typename FillAction::FillActionType>(fillAction.type)) {
 
    case FillAction::TYPE_APPEND:
        moveActionType = MoveAction::TYPE_APPEND;
        break;
 
    case FillAction::TYPE_INSERT:
        moveActionType = MoveAction::TYPE_INSERT;
        break;
 
    case FillAction::TYPE_OVERWRITE:
        moveActionType = MoveAction::TYPE_OVERWRITE;
        break;
 
    default:
        BITPIT_UNREACHABLE("This action is not handled");
        moveActionType = MoveAction::TYPE_UNDEFINED;
        break;
 
    }
 
    MoveAction moveAction(moveActionType);
    moveAction.info[PiercedSyncAction::INFO_POS_FIRST]  = initialPos;
    moveAction.info[PiercedSyncAction::INFO_POS_SECOND] = fillAction.info[PiercedSyncAction::INFO_POS];
    processSyncAction(moveAction);
 
    // Return the move action
    return moveAction;
}
 
 
template<typename id_t>
typename PiercedKernel<id_t>::SwapAction PiercedKernel<id_t>::swap(id_t id_first, id_t id_second)
{
    // Positions
    std::size_t pos_first  = m_pos.at(id_first);
    std::size_t pos_second = m_pos.at(id_second);
 
    // Swap the positions
    swapPosIds(pos_first, id_first, pos_second, id_second);
 
    // Update the storage
    SwapAction swapAction(SwapAction::TYPE_SWAP);
    swapAction.info[PiercedSyncAction::INFO_POS_FIRST]  = pos_first;
    swapAction.info[PiercedSyncAction::INFO_POS_SECOND] = pos_second;
    processSyncAction(swapAction);
 
    // Return the swap action
    return swapAction;
}
 
template<typename id_t>
typename PiercedKernel<id_t>::EraseAction PiercedKernel<id_t>::erase(id_t id, bool flush)
{
    // Position
    std::size_t pos = m_pos.at(id);
 
    // Pierce the position
    pierce(pos, flush);
 
    // Update the storage
    if (pos + 1 < m_end_pos) {
        EraseAction pierceAction(EraseAction::TYPE_PIERCE);
        pierceAction.info[PiercedSyncAction::INFO_POS]      = pos;
        pierceAction.info[PiercedSyncAction::INFO_POS_NEXT] = findNextUsedPos(pos);
        processSyncAction(pierceAction);
 
        return pierceAction;
    } else {
        EraseAction resizeAction(EraseAction::TYPE_SHRINK);
        resizeAction.info[PiercedSyncAction::INFO_SIZE] = rawSize();
        processSyncAction(resizeAction);
 
        return resizeAction;
    }
}
 
template<typename id_t>
typename PiercedKernel<id_t>::EraseAction PiercedKernel<id_t>::popBack()
{
    // The kernel cannt be empty
    if (empty()) {
        throw std::out_of_range("Vector is empty");
    }
 
    // Erase the last element
    std::size_t updatedRawSize;
    if (size() == 1) {
        updatedRawSize = 0;
    } else {
        updatedRawSize = findPrevUsedPos(m_end_pos - 1) + 1;
    }
 
    rawShrink(updatedRawSize);
 
    // Return the erase action
    EraseAction eraseAction(EraseAction::TYPE_SHRINK);
    eraseAction.info[PiercedSyncAction::INFO_SIZE] = rawSize();
    processSyncAction(eraseAction);
 
    return eraseAction;
}
 
template<typename id_t>
void PiercedKernel<id_t>::pierce(std::size_t pos, bool flush)
{
    // If removing the last position, there is no need to add the
    // position to the holes, it's enough to update the last position
    // counter or clear the kernel if this was the last hole.
    if (pos + 1 == m_end_pos) {
        std::size_t updatedRawSize;
        if (size() == 1) {
            updatedRawSize = 0;
        } else {
            updatedRawSize = findPrevUsedPos(m_end_pos - 1) + 1;
        }
 
        rawShrink(updatedRawSize);
 
        return;
    }
 
    // Remove the id from the map
    id_t id = m_ids[pos];
    m_pos.erase(id);
 
    // Reset the position
    std::size_t nextUsedPos = findNextUsedPos(pos);
    setPosEmptyId(pos, nextUsedPos);
    m_dirty_begin_pos = std::min(pos, m_dirty_begin_pos);
 
    // If removing the first position, update the counter
    if (pos == m_begin_pos) {
        std::size_t begin = findNextUsedPos(m_begin_pos);
        setBeginPos(begin);
    }
 
    // If the list of pending holes is full, flush the holes.
    if (m_holes_pending_end == m_holes.size()) {
        holesFlush();
    }
 
    // Add the hole at the end of the pending holes
    m_holes[m_holes_pending_end] = pos;
    m_holes_pending_end++;
 
    // Check if pending holes are still sorted
    if (m_holes_pending_sorted) {
        std::size_t nPendings = holesCountPending();
        if (nPendings > 1 && (m_holes[m_holes_pending_end - 1] > m_holes[m_holes_pending_end - 2])) {
            m_holes_pending_sorted = false;
        }
    }
 
    // Flush
    if (flush) {
        holesFlush();
    }
}
 
template<typename id_t>
void PiercedKernel<id_t>::holesClear(bool release)
{
    // Clear the holes
    holesResize(0, 0, 0, release);
 
    // There are no holes, therefore all holes are sorted
    m_holes_regular_sorted = true;
    m_holes_pending_sorted = true;
}
 
template<typename id_t>
void PiercedKernel<id_t>::holesClearRegular(bool release)
{
    // Release the memory
    if (release) {
        m_holes.shrink_to_fit();
    }
 
    // Reset regulr holes iterators
    m_holes_regular_begin = 0;
    m_holes_regular_end   = m_holes_regular_begin;
 
    // There are no holes, therefore all holes are sorted
    m_holes_regular_sorted = true;
}
 
template<typename id_t>
void PiercedKernel<id_t>::holesClearPending(bool release)
{
    // Clear section of the kernel associated with the pending holes
    long offset    = m_holes_regular_begin;
    long nRegulars = holesCountRegular();
    holesResize(offset, nRegulars, 0, release);
 
    // There are no pending holes, therefore pending holes are sorted
    m_holes_pending_sorted = true;
}
 
template<typename id_t>
void PiercedKernel<id_t>::holesResize(std::size_t offset, std::size_t nRegulars, std::size_t nPendings, bool release)
{
    if (release) {
        m_holes.shrink_to_fit();
    }
 
    m_holes.resize(offset + nRegulars + MAX_PENDING_HOLES);
 
    m_holes_regular_begin = offset;
    m_holes_regular_end   = m_holes_regular_begin + nRegulars;
    m_holes_pending_begin = m_holes_regular_end;
    m_holes_pending_end   = m_holes_pending_begin + nPendings;
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::holesCount() const
{
    return holesCountPending() + holesCountRegular();
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::holesCountPending() const
{
    return (m_holes_pending_end - m_holes_pending_begin);
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::holesCountRegular() const
{
    return (m_holes_regular_end - m_holes_regular_begin);
}
 
template<typename id_t>
void PiercedKernel<id_t>::holesFlush()
{
    // If there are no pending holes there is nothing to do
    if (m_holes_pending_begin == m_holes_pending_end) {
        return;
    }
 
    // Update the id of the empty elements
    //
    // The list of pending holes is sorted, in this way we can iterate
    // from the last pending hole in the kernel to the first one.
    // We start updating the id of the last pending hole, updating also
    // the id of the contiguous holes before that one. Then we advance
    // to the next hole, skipping the positions that have already been
    // updated.
    holesSortPending();
 
    std::size_t hole = m_holes_pending_begin;
    std::size_t pos = m_end_pos;
    do {
        if (m_holes[hole] >= pos) {
            hole++;
            continue;
        }
 
        pos = m_holes[hole];
        std::size_t next_used_pos = findNextUsedPos(pos);
        do {
            setPosEmptyId(pos, next_used_pos);
            if (pos > 0) {
                pos--;
            } else {
                break;
            }
        } while (isPosEmpty(pos));
    } while (pos > 0 && hole != m_holes_pending_end);
 
    // Move the pending holes into the list of regular holes
    for (std::size_t hole = m_holes_pending_begin; hole < m_holes_pending_end; ++hole) {
        std::size_t pos = m_holes[hole];
 
        // If there is space available at the beginning of the holes, try
        // using pending holes to fill that gap.
        if (m_holes_regular_begin != 0) {
            --m_holes_regular_begin;
            m_holes[m_holes_regular_begin] = pos;
 
            // Regular holes are no more sorted
            if (m_holes_regular_sorted) {
                m_holes_regular_sorted = false;
            }
        } else {
            if (hole != m_holes_regular_end) {
                m_holes[m_holes_regular_end] = pos;
            }
            ++m_holes_regular_end;
            ++m_holes_pending_begin;
 
            // Check if regular holes are still sorted
            if (m_holes_regular_sorted) {
                std::size_t nRegulars = holesCountRegular();
                if (nRegulars > 1 && (m_holes[m_holes_regular_end - 1] > m_holes[m_holes_regular_end - 2])) {
                    m_holes_regular_sorted = false;
                }
            }
        }
    }
 
    // Move the holes at the beginning of the vector
    std::size_t nRegulars = holesCountRegular();
    if (nRegulars != 0 && m_holes_regular_begin != 0) {
        for (std::size_t k = 0; k < nRegulars; ++k) {
            m_holes[k] = m_holes[m_holes_regular_begin + k];
        }
 
        m_holes_regular_begin = 0;
        m_holes_regular_end   = m_holes_regular_begin + nRegulars;
    }
 
    // Resize the vector
    holesClearPending();
 
    // There are no more dirty positions
    m_dirty_begin_pos = m_end_pos;
}
 
 
template<typename id_t>
void PiercedKernel<id_t>::holesSortPending()
{
    if (m_holes_pending_sorted) {
        return;
    }
 
    holes_iterator pending_begin_itr = m_holes.begin() + m_holes_pending_begin;
    holes_iterator pending_end_itr   = m_holes.begin() + m_holes_pending_end;
    std::sort(pending_begin_itr, pending_end_itr, std::greater<std::size_t>());
    m_holes_pending_sorted = true;
}
 
template<typename id_t>
void PiercedKernel<id_t>::holesSortRegular()
{
    if (m_holes_regular_sorted) {
        return;
    }
 
    holes_iterator regular_begin_itr = m_holes.begin() + m_holes_regular_begin;
    holes_iterator regular_end_itr   = m_holes.begin() + m_holes_regular_end;
    std::sort(regular_begin_itr, regular_end_itr, std::greater<std::size_t>());
    m_holes_regular_sorted = true;
}
 
template<typename id_t>
bool PiercedKernel<id_t>::validateId(id_t id)
{
    // Ids needs to be positive
    if (id < 0) {
        throw std::out_of_range("Negative id");
    }
 
    // Handle duplicate ids
    if (contains(id)) {
        throw std::out_of_range("Duplicate id");
    }
 
    // Id is valid
    return true;
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::back() const
{
    if (empty()) {
        throw std::out_of_range("Vector is empty");
    }
 
    return (m_end_pos - 1);
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::front() const
{
    if (empty()) {
        throw std::out_of_range("Vector is empty");
    }
 
    return m_begin_pos;
}
 
template<typename id_t>
std::vector<PiercedStorageSyncSlave<id_t> *> PiercedKernel<id_t>::getStorages()
{
    std::size_t storageIdx = 0;
    std::vector<PiercedStorageSyncSlave<id_t> *> storges(m_slaves.size());
    for (auto &slaveEntry : m_slaves) {
        PiercedSyncSlave *slave = slaveEntry.first;
        PiercedStorageSyncSlave<id_t> *piercedStorage = dynamic_cast<PiercedStorageSyncSlave<id_t> *>(slave);
        if (piercedStorage) {
            storges[storageIdx] = piercedStorage;
            ++storageIdx;
        }
    }
 
    return storges;
}
 
template<typename id_t>
std::vector<const PiercedStorageSyncSlave<id_t> *> PiercedKernel<id_t>::getStorages() const
{
    std::size_t storageIdx = 0;
    std::vector<PiercedStorageSyncSlave<id_t> *> storges(m_slaves.size());
    for (const auto &slaveEntry : m_slaves) {
        const PiercedSyncSlave *slave = slaveEntry.first;
        const PiercedStorageSyncSlave<id_t> *piercedStorage = dynamic_cast<const PiercedStorageSyncSlave<id_t> *>(slave);
        if (piercedStorage) {
            storges[storageIdx] = piercedStorage;
            ++storageIdx;
 
        }
    }
 
    return storges;
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::findPrevUsedPos(std::size_t pos) const
{
    std::size_t prev_pos = pos;
    while (true) {
        if (prev_pos == m_begin_pos) {
            throw std::out_of_range("Already in the firts position");
        }
        prev_pos--;
 
        id_t prev_id = m_ids[prev_pos];
        if (prev_id >= 0) {
            return prev_pos;
        }
    }
}
 
template<typename id_t>
std::size_t PiercedKernel<id_t>::findNextUsedPos(std::size_t pos) const
{
    std::size_t next_pos   = pos;
    std::size_t next_delta = 1;
    while (true) {
        if (next_pos + 1 == m_end_pos) {
            throw std::out_of_range("Already in the last position");
        }
        next_pos += next_delta;
 
        id_t next_id = m_ids[next_pos];
        if (next_id >= 0) {
            return next_pos;
        } else {
            next_delta = - next_id;
        }
    }
}
 
template<typename id_t>
bool PiercedKernel<id_t>::isPosEmpty(std::size_t pos) const
{
    return (m_ids[pos] < 0);
}
 
template<typename id_t>
void PiercedKernel<id_t>::setPosId(std::size_t pos, id_t id)
{
    m_ids[pos] = id;
    m_pos[id]  = pos;
}
 
template<typename id_t>
void PiercedKernel<id_t>::setPosEmptyId(std::size_t pos, std::size_t nextUsedPos)
{
    assert(nextUsedPos > pos);
 
    // Early return if we are updating the last position
    //
    // When updating the last position, the id can only be set to point to the next position
    // (i.e., set equal to -1).
    if (pos == (m_end_pos - 1)) {
        m_ids[pos] = id_t(-1);
        return;
    }
 
    // Set the id of the position
    //
    // The id of an empty element contains the distance, measured in number of elements, between
    // the current element and the next element the iterator should jump to (the distance is
    // negative). If the next position is non-empty or a regular hole, the value of the id will
    // be set in such a way to point to the next non-empty element (this will make the iterator
    // as fast as possible). If the next position is a pending hole, we need to set the id to
    // -1, otherwise we may break the iterator. For example,
    //
    //      ID    1  2  3 -1  4 -1 -1  5
    //     POS    0  1  2  3  4  5  6  7
    //
    // when setting the id associated with position 4, it should be set to -1 and not to -3,
    // otherwise if the position 5 will be filled, the iterator will not able to reach it (it
    // will reach position 4 and will wrongly skip to position 7).
    id_t offset = id_t(pos - nextUsedPos);
    if (m_ids[pos + 1] == offset + 1) {
        m_ids[pos] = offset;
    } else {
        m_ids[pos] = id_t(-1);
    }
}
 
template<typename id_t>
void PiercedKernel<id_t>::swapPosIds(std::size_t pos_1, id_t id_1, std::size_t pos_2, id_t id_2)
{
    std::swap(m_ids[pos_1], m_ids[pos_2]);
    std::swap(m_pos[id_1], m_pos[id_2]);
}
 
template<typename id_t>
void PiercedKernel<id_t>::setBeginPos(std::size_t pos)
{
    m_begin_pos = pos;
}
 
template<typename id_t>
void PiercedKernel<id_t>::setEndPos(std::size_t pos)
{
    m_end_pos = pos;
}
 
template<typename id_t>
void PiercedKernel<id_t>::rawShrink(std::size_t n)
{
    // We can only shrink the kernel
    if (n > m_end_pos) {
        throw std::out_of_range("The kernel can only be shrunk");
    }
 
    // Check if we actually need to shrink the kernel
    if (n == m_end_pos) {
        return;
    }
 
    // When the new last position is before the first one this is equivalent
    // to a clear
    if (n < (m_begin_pos + 1)) {
        _clear();
        return;
    }
 
    // Delete the ids of the elements that will be removed
    for (std::size_t pos = n; pos < m_end_pos; ++pos) {
        id_t id = m_ids[pos];
        if (id >= 0) {
            m_pos.erase(id);
        }
    }
 
    // Resize the internal vectors
    m_ids.resize(n);
 
    // Update the last position
    setEndPos(n);
 
    // Update the holes
    if (holesCount() != 0) {
        // Remove regular holes beyond the updated last position
        holesSortRegular();
        holes_iterator regular_begin_itr = m_holes.begin() + m_holes_regular_begin;
        holes_iterator regular_end_itr   = m_holes.begin() + m_holes_regular_end;
        regular_begin_itr = std::lower_bound(regular_begin_itr, regular_end_itr, m_end_pos - 1, std::greater<std::size_t>());
        m_holes_regular_begin = std::distance(m_holes.begin(), regular_begin_itr);
        if (m_holes_regular_begin == m_holes_regular_end) {
            m_holes_regular_begin = 0;
            m_holes_regular_end   = m_holes_regular_begin;
        }
 
        // Remove pending holes beyond the updated last position
        holesSortPending();
        holes_iterator pending_begin_itr = m_holes.begin() + m_holes_pending_begin;
        holes_iterator pending_end_itr   = m_holes.begin() + m_holes_pending_end;
        pending_begin_itr = std::lower_bound(pending_begin_itr, pending_end_itr, m_end_pos - 1, std::greater<std::size_t>());
        m_holes_pending_begin = std::distance(m_holes.begin(), pending_begin_itr);
        if (m_holes_pending_begin == m_holes_pending_end) {
            m_holes_pending_begin = m_holes_regular_end;
            m_holes_pending_end   = m_holes_pending_begin;
        }
    }
}
 
template<typename id_t>
void PiercedKernel<id_t>::restore(std::istream &stream)
{
    // Ids data
    std::size_t nIds;
    utils::binary::read(stream, nIds);
    m_pos.reserve(nIds);
    for (std::size_t n = 0; n < nIds; ++n) {
        id_t id;
        utils::binary::read(stream, id);
 
        std::size_t pos;
        utils::binary::read(stream, pos);
 
        m_pos.insert({id, pos});
    }
 
    // Postions data
    std::size_t nPositions;
    utils::binary::read(stream, nPositions);
    m_ids.resize(nPositions);
    for (std::size_t n = 0; n < nPositions; ++n) {
        std::size_t id;
        utils::binary::read(stream, id);
 
        m_ids[n] = id;
    }
 
    utils::binary::read(stream, m_begin_pos);
    utils::binary::read(stream, m_end_pos);
    utils::binary::read(stream, m_dirty_begin_pos);
 
    // Holes data
    std::size_t nHoles;
    utils::binary::read(stream, nHoles);
    m_holes.resize(nHoles);
    for (std::size_t n = 0; n < nHoles; ++n) {
        std::size_t pos;
        utils::binary::read(stream, pos);
 
        m_holes[n] = pos;
    }
 
    utils::binary::read(stream, m_holes_regular_begin);
    utils::binary::read(stream, m_holes_regular_end);
    utils::binary::read(stream, m_holes_pending_begin);
    utils::binary::read(stream, m_holes_pending_end);
    utils::binary::read(stream, m_holes_regular_sorted);
    utils::binary::read(stream, m_holes_pending_sorted);
 
    // Synchronization data
    PiercedSyncMaster::restore(stream);
}
 
template<typename id_t>
void PiercedKernel<id_t>::dump(std::ostream &stream) const
{
    // Ids data
    std::size_t nIds = m_pos.size();
    utils::binary::write(stream, nIds);
    for (const auto &entry : m_pos) {
        utils::binary::write(stream, entry.first);
        utils::binary::write(stream, entry.second);
    }
 
    // Postions data
    std::size_t nPositions = m_ids.size();
    utils::binary::write(stream, nPositions);
    for (std::size_t pos : m_ids) {
        utils::binary::write(stream, pos);
    }
 
    utils::binary::write(stream, m_begin_pos);
    utils::binary::write(stream, m_end_pos);
    utils::binary::write(stream, m_dirty_begin_pos);
 
    // Holes data
    std::size_t nHoles = m_holes.size();
    utils::binary::write(stream, nHoles);
    for (std::size_t hole : m_holes) {
        utils::binary::write(stream, hole);
    }
 
    utils::binary::write(stream, m_holes_regular_begin);
    utils::binary::write(stream, m_holes_regular_end);
    utils::binary::write(stream, m_holes_pending_begin);
    utils::binary::write(stream, m_holes_pending_end);
    utils::binary::write(stream, m_holes_regular_sorted);
    utils::binary::write(stream, m_holes_pending_sorted);
 
    // Synchronization data
    PiercedSyncMaster::dump(stream);
}
 
}
 
#endif