piercedKernel.hpp

/*---------------------------------------------------------------------------*\
 *
 *  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_HPP__
#define __BITPIT_PIERCED_KERNEL_HPP__
 
#include <algorithm>
#include <cassert>
#include <limits>
#include <unordered_map>
#include <type_traits>
#include <vector>
 
#include "bitpit_common.hpp"
 
#include "piercedSync.hpp"
#include "piercedKernelIterator.hpp"
#include "piercedKernelRange.hpp"
 
namespace bitpit {
 
template<typename id_t>
class PiercedStorageSyncSlave;
 
class BasePiercedKernel : public PiercedSyncMaster {
 
public:
    virtual ~BasePiercedKernel() = default;
 
protected:
    BasePiercedKernel() = default;
 
};
 
template<typename id_t = long>
class PiercedKernel : public BasePiercedKernel {
 
static_assert(std::is_integral<id_t>::value, "Signed integer required for id.");
static_assert(std::numeric_limits<id_t>::is_signed, "Signed integer required for id.");
 
// Friendships
template<typename PSI_value_t, typename PSI_id_t, typename PSI_value_no_cv_t>
friend class PiercedStorageIterator;
 
template<typename PKI_id_t>
friend class PiercedKernelIterator;
 
template<typename PKR_id_t>
friend class PiercedKernelRange;
 
template<typename BPS_id_t>
friend class PiercedStorageSyncSlave;
 
template<typename PS_value_t, typename PS_id_t>
friend class PiercedStorage;
 
public:
    typedef id_t id_type;
 
    typedef PiercedKernelIterator<id_t> const_iterator;
 
    typedef typename std::vector<id_t>::const_iterator raw_const_iterator;
 
    typedef PiercedKernelRange<id_t> const_range;
 
    using PiercedSyncMaster::SyncMode;
 
    struct positionLess
    {
        positionLess(const PiercedKernel<id_t> &kernel)
        {
            m_kernel = &kernel;
        }
 
        bool operator()(id_t id_1, id_t id_2) const
        {
            return m_kernel->getPos(id_1) < m_kernel->getPos(id_2);
        }
 
        const PiercedKernel<id_t> *m_kernel;
    };
 
    struct positionGreater
    {
        positionGreater(const PiercedKernel<id_t> &kernel)
        {
            m_kernel = &kernel;
        }
 
        bool operator()(id_t id_1, id_t id_2) const
        {
            return m_kernel->getPos(id_1) > m_kernel->getPos(id_2);
        }
 
        const PiercedKernel<id_t> *m_kernel;
    };
 
    class FillAction : public PiercedSyncAction {
 
    public:
        enum FillActionType {
            TYPE_UNDEFINED = PiercedSyncAction::TYPE_UNDEFINED,
            TYPE_OVERWRITE = PiercedSyncAction::TYPE_OVERWRITE,
            TYPE_INSERT    = PiercedSyncAction::TYPE_INSERT,
            TYPE_APPEND    = PiercedSyncAction::TYPE_APPEND
        };
 
        FillAction(FillActionType type)
            : PiercedSyncAction(static_cast<PiercedSyncAction::ActionType>(type))
        {
        };
    };
 
    class MoveAction : public PiercedSyncAction {
 
    public:
        enum MoveActionType {
            TYPE_UNDEFINED = PiercedSyncAction::TYPE_UNDEFINED,
            TYPE_OVERWRITE = PiercedSyncAction::TYPE_MOVE_OVERWRITE,
            TYPE_INSERT    = PiercedSyncAction::TYPE_MOVE_INSERT,
            TYPE_APPEND    = PiercedSyncAction::TYPE_MOVE_APPEND
        };
 
        MoveAction(MoveActionType type)
            : PiercedSyncAction(static_cast<PiercedSyncAction::ActionType>(type))
        {
        };
    };
 
    class SwapAction : public PiercedSyncAction {
 
    public:
        enum SwapActionType {
            TYPE_UNDEFINED = PiercedSyncAction::TYPE_UNDEFINED,
            TYPE_SWAP      = PiercedSyncAction::TYPE_SWAP
        };
 
        SwapAction(SwapActionType type)
            : PiercedSyncAction(static_cast<PiercedSyncAction::ActionType>(type))
        {
        };
    };
 
    class EraseAction : public PiercedSyncAction {
 
    public:
        enum EraseActionType {
            TYPE_UNDEFINED = PiercedSyncAction::TYPE_UNDEFINED,
            TYPE_PIERCE    = PiercedSyncAction::TYPE_PIERCE,
            TYPE_SHRINK    = PiercedSyncAction::TYPE_RESIZE
        };
 
        EraseAction(EraseActionType type)
            : PiercedSyncAction(static_cast<PiercedSyncAction::ActionType>(type))
        {
        };
    };
 
    class ClearAction : public PiercedSyncAction {
 
    public:
        ClearAction()
            : PiercedSyncAction(PiercedSyncAction::TYPE_CLEAR)
        {
        };
    };
 
    class ReserveAction : public PiercedSyncAction {
 
    public:
        ReserveAction()
            : PiercedSyncAction(PiercedSyncAction::TYPE_RESERVE)
        {
        };
    };
 
    class ResizeAction : public PiercedSyncAction {
 
    public:
        enum ResizeActionType {
            TYPE_NOOP    = PiercedSyncAction::TYPE_NOOP,
            TYPE_RESERVE = PiercedSyncAction::TYPE_RESERVE,
            TYPE_CLEAR   = PiercedSyncAction::TYPE_CLEAR,
            TYPE_RESIZE  = PiercedSyncAction::TYPE_RESIZE
        };
 
 
        ResizeAction(ResizeActionType type)
            : PiercedSyncAction(static_cast<PiercedSyncAction::ActionType>(type))
        {
        };
    };
 
    class SortAction : public PiercedSyncAction {
 
    public:
        SortAction()
            : PiercedSyncAction(PiercedSyncAction::TYPE_REORDER)
        {
        };
    };
 
    class SqueezeAction : public PiercedSyncAction {
 
    public:
        SqueezeAction()
            : PiercedSyncAction(PiercedSyncAction::TYPE_REORDER)
        {
        };
    };
 
    class ShrinkToFitAction : public PiercedSyncAction {
 
    public:
        ShrinkToFitAction()
            : PiercedSyncAction(PiercedSyncAction::TYPE_SHRINK_TO_FIT)
        {
        };
    };
 
    // Contructors
    PiercedKernel();
    PiercedKernel(std::size_t n);
    PiercedKernel(const PiercedKernel &other) = default;
    PiercedKernel(PiercedKernel &&other) = default;
 
    // Destructor
    ~PiercedKernel() override;
 
    // Methods that modify the kernel as a whole
    ClearAction clear(bool release = true);
    ReserveAction reserve(std::size_t n);
    ResizeAction resize(std::size_t n);
    SortAction sort();
    SortAction sortAfter(id_t referenceId, bool inclusive);
    SortAction sortBefore(id_t referenceId, bool inclusive);
    SqueezeAction squeeze();
    ShrinkToFitAction shrinkToFit();
 
    void swap(PiercedKernel &other) noexcept;
 
    void flush();
 
    // Methods that extract information about the kernel
    bool contiguous() const;
    void dump() const;
    bool empty() const;
    bool isIteratorSlow();
    std::size_t maxSize() const;
    std::size_t size() const;
    std::size_t capacity() const;
 
    // Methods that extract information about the elements of the kernel
    bool contains(id_t id) const;
    std::size_t count(id_t id) const;
    std::size_t getRawIndex(id_t id) const;
    std::size_t evalFlatIndex(id_t id) const;
 
    std::vector<id_t> getIds(bool ordered = true) const;
    id_t getSizeMarker(std::size_t targetSize, const id_t &fallback = -1);
 
    // Iterators
    const_iterator find(const id_t &id) const noexcept;
 
    const_iterator rawFind(std::size_t pos) const noexcept;
 
    const_iterator begin() const noexcept;
    const_iterator end() const noexcept;
    const_iterator cbegin() const noexcept;
    const_iterator cend() const noexcept;
 
    // Methods that extract information about the kernel
    void checkIntegrity() const;
 
    // Methods that modify the elements stored in the kernel
    void updateId(const id_t &currentId, const id_t &updatedId);
 
    FillAction fillHead(id_t id);
    FillAction fillTail(id_t id);
    FillAction fillAfter(id_t referenceId, id_t id);
    FillAction fillBefore(id_t referenceId, id_t id);
    FillAction fillAppend(id_t id);
    FillAction fillHole(std::size_t hole, id_t id);
    FillAction fillInsert(std::size_t pos, id_t id);
 
    MoveAction moveAfter(id_t referenceId, id_t id, bool flush = false);
    MoveAction moveBefore(id_t referenceId, id_t id, bool flush = false);
 
    SwapAction swap(id_t id_first, id_t id_second);
 
    EraseAction erase(id_t id, bool flush = false);
    EraseAction popBack();
 
    // Methods that extract information about the elements of the kernel
    std::size_t back() const;
    std::size_t front() const;
 
    // Methods to handle the storage
    using PiercedSyncMaster::sync;
    using PiercedSyncMaster::isSynced;
 
    // Dump and restore
    void restore(std::istream &stream);
    void dump(std::ostream &stream) const;
 
protected:
    typedef std::vector<std::size_t> holes_container;
 
    typedef holes_container::iterator holes_iterator;
 
    typedef holes_container::const_iterator holes_const_iterator;
 
    // Methods that extract information about the kernel
    std::size_t rawSize() const;
 
    // Methods that extract information about the elements of the kernel
    std::size_t findPrevUsedPos(std::size_t pos) const;
    std::size_t findNextUsedPos(std::size_t pos) const;
    bool isPosEmpty(std::size_t pos) const;
    std::size_t getPos(id_t id) const;
    std::size_t getFirstUsedPos() const;
    std::size_t getLastUsedPos() const;
 
    // Methods that modify the kernel as a whole
    ClearAction _clear(bool release = true);
    ReserveAction _reserve(std::size_t n);
    ResizeAction _resize(std::size_t n);
    SortAction _sort(std::size_t begin, std::size_t end);
    SqueezeAction _squeeze();
    ShrinkToFitAction _shrinkToFit();
 
    // Methods to handle the storage
    std::vector<PiercedStorageSyncSlave<id_t> *> getStorages();
    std::vector<const PiercedStorageSyncSlave<id_t> *> getStorages() const;
 
private:
    struct PiercedHasher {
        template<typename U>
        constexpr std::size_t operator()(U&& value) const noexcept
        {
            return static_cast<std::size_t>(std::forward<U>(value));
        }
    };
 
    struct idLess
    {
        const std::vector<id_t> &m_ids;
 
        idLess(const std::vector<id_t> &ids)
            : m_ids(ids)
        {
        }
 
        inline bool operator() (std::size_t pos_x, std::size_t pos_y)
        {
            id_t id_x = m_ids[pos_x];
            id_t id_y = m_ids[pos_y];
 
            if (id_x >= 0 && id_y < 0) {
                return true;
            } else if (id_x < 0 && id_y >= 0) {
                return false;
            } else if (id_x >= 0) {
                return (id_x < id_y);
            } else {
                return (id_x > id_y);
            }
        }
    };
 
    static const std::size_t MAX_PENDING_HOLES;
 
    std::vector<id_t> m_ids;
 
    std::unordered_map<id_t, std::size_t, PiercedHasher> m_pos;
 
    std::size_t m_begin_pos;
 
    std::size_t m_end_pos;
 
    std::size_t m_dirty_begin_pos;
 
    holes_container m_holes;
 
    std::size_t m_holes_regular_begin;
 
    std::size_t m_holes_regular_end;
 
    std::size_t m_holes_pending_begin;
 
    std::size_t m_holes_pending_end;
 
    bool m_holes_regular_sorted;
 
    bool m_holes_pending_sorted;
 
    void pierce(std::size_t pos, bool flush = true);
 
    void holesClear(bool release = false);
    void holesClearRegular(bool release = false);
    void holesClearPending(bool release = false);
    void holesResize(std::size_t offset, std::size_t nRegulars, std::size_t nPendings, bool release = true);
    std::size_t holesCount() const;
    std::size_t holesCountPending() const;
    std::size_t holesCountRegular() const;
    void holesFlush();
    void holesSortPending();
    void holesSortRegular();
 
    bool validateId(id_t id);
 
    void setBeginPos(std::size_t pos);
    void setEndPos(std::size_t pos);
 
    void setPosId(std::size_t pos, id_t id);
    void setPosEmptyId(std::size_t pos, std::size_t nextUsedPos);
    void swapPosIds(std::size_t pos_1, id_t id_1, std::size_t pos_2, id_t id_2);
 
    void rawShrink(std::size_t n);
 
};
 
}
 
// Include the implementation
#include "piercedKernel.tpp"
 
 
#endif