vector_with_ids.h

Go to the documentation of this file.

#pragma once

#include <vector>
#include <unordered_map>

#include <cassert>
#include "vector_with_ids_iterator.h"

BEGIN_NAMESPACE_CONTAINERS

template <typename T>
class VectorWithIds
{
public:
    using iterator = VectorWithIdsIterators::VectorWithIdsIterator<T, VectorWithIdsIterators::ConstTypeSwitch::isNonConst>;
    using const_iterator = VectorWithIdsIterators::VectorWithIdsIterator<T, VectorWithIdsIterators::ConstTypeSwitch::isConst>;

public:
    
    VectorWithIds(std::size_t idMinGenerated = 0, std::size_t idStepSizeGenerated = 1);

    VectorWithIds(const VectorWithIds& other);

    VectorWithIds<T>& operator=(const VectorWithIds& other);

    VectorWithIds(VectorWithIds<T>&& other);

    VectorWithIds<T>& operator=(VectorWithIds<T>&& other);

    T& operator[](std::size_t pos);

    const T& operator[](std::size_t pos) const;

    T& back();

    const T& back() const;

    void clear();

    std::size_t size() const;

    bool empty() const;

    void emplaceBack();

    bool emplaceBackWithId(int32_t id);

    iterator erase(iterator position);

    iterator erase(std::size_t pos);

    void swap(int32_t posA, int32_t posB);

    int32_t getId(int32_t pos) const;


    iterator findById(int32_t id);

    const_iterator findById(int32_t id) const;

    void cloneStructure(const VectorWithIds<T>& other);


    iterator begin()
    {
        return iterator(pairs.begin());
    }

    iterator end()
    {
        return iterator(pairs.end());
    }

    const_iterator begin() const
    {
        return const_iterator(pairs.begin());
    }

    const_iterator end() const
    {
        return const_iterator(pairs.end());
    }

    const_iterator cbegin() const
    {
        return begin();
    }

    const_iterator cend() const
    {
        return end();
    }

private:
    int32_t idMin, idStep;

    std::vector<std::pair<int32_t, T>> pairs;
    std::unordered_map<int32_t, typename std::vector<std::pair<int32_t, T>>::iterator> pairsMap;

    void rebuildPairMap();
};

template <class T>
VectorWithIds<T>::VectorWithIds(std::size_t idMinGenerated, std::size_t idStepSizeGenerated)
{
    idMin = static_cast<int32_t>(idMinGenerated);

    assert(idStepSizeGenerated > 0);
    idStep = static_cast<int32_t>(idStepSizeGenerated);
}

template <typename T>
VectorWithIds<T>::VectorWithIds(const VectorWithIds<T>& other)
{
    idMin = other.idMin;
    idStep = other.idStep;
    pairs = other.pairs;
    rebuildPairMap();
}

template <typename T>
VectorWithIds<T>& VectorWithIds<T>::operator=(const VectorWithIds<T>& other)
{
    if (this != &other)
    {
        idMin = other.idMin;
        idStep = other.idStep;
        pairs = other.pairs;
        rebuildPairMap();
    }
    return *this;
}

template <typename T>
VectorWithIds<T>::VectorWithIds(VectorWithIds<T>&& other)
{
    idMin = other.idMin;
    idStep = other.idStep;

    pairs = std::move(other.pairs);
    rebuildPairMap();

    other.pairsMap.clear();
}

template <typename T>
VectorWithIds<T>& VectorWithIds<T>::operator=(VectorWithIds<T>&& other)
{
    if (this != &other)
    {
        idMin = other.idMin;
        idStep = other.idStep;

        pairs = std::move(other.pairs);
        rebuildPairMap();

        other.pairsMap.clear();
    }
    return *this;
}

template <typename T>
T& VectorWithIds<T>::operator[](std::size_t pos)
{
    return pairs[pos].second;
}

template <typename T>
const T& VectorWithIds<T>::operator[](std::size_t pos) const
{
    return pairs[pos].second;
}

template <typename T>
T& VectorWithIds<T>::back()
{
    return pairs.back().second;
}

template <typename T>
const T& VectorWithIds<T>::back() const
{
    return pairs.back().second;
}

template <typename T>
void VectorWithIds<T>::clear()
{
    pairsMap.clear();
    pairs.clear();
}

template <typename T>
std::size_t VectorWithIds<T>::size() const
{
    return pairs.size();
}

template <typename T>
bool VectorWithIds<T>::empty() const
{
    return pairs.empty();
}

template <typename T>
typename VectorWithIds<T>::iterator VectorWithIds<T>::erase(iterator position)
{
    auto it = pairs.erase(position.pointee);
    rebuildPairMap();
    return iterator(it);
}

template <typename T>
typename VectorWithIds<T>::iterator VectorWithIds<T>::erase(std::size_t pos)
{
    auto it = pairs.erase(pairs.begin() + pos);
    rebuildPairMap();
    return iterator(it);
}

template <typename T>
void VectorWithIds<T>::swap(int32_t posA, int32_t posB)
{
    if (posA != posB)
    {
        std::swap(pairs[posA], pairs[posB]);
        rebuildPairMap();
    }
}

template <typename T>
void VectorWithIds<T>::emplaceBack()
{
    if (pairs.empty())
    {
        // Fill the first index if size is zero
        pairs.emplace_back();
        pairs[0].first = idMin;
    }
    else
    {
        // Find a slot
        bool slotFound = false;
        int32_t slotId = idMin;

        while (!slotFound)
        {
            if (pairsMap.find(slotId) == pairsMap.end())
            {
                slotFound = true;
            }
            else
            {
                slotId += idStep;
            }
        }

        // Insert with free slot
        pairs.emplace_back();
        (pairs.back()).first = slotId;
    }

    rebuildPairMap();
}

template <typename T>
bool VectorWithIds<T>::emplaceBackWithId(int32_t id)
{
    if (pairsMap.find(id) == pairsMap.end())
    {
        pairs.emplace_back();
        (pairs.back()).first = id;
        rebuildPairMap();
        return true;
    }
    return false;
}

template <typename T>
int32_t VectorWithIds<T>::getId(int32_t pos) const
{
    return pairs[pos].first;
}

template <typename T>
typename VectorWithIds<T>::iterator VectorWithIds<T>::findById(int32_t id)
{
    auto pairsMapIter = pairsMap.find(id);

    if (pairsMapIter != pairsMap.end())
    {
        return iterator(pairsMapIter->second);
    }
    return end();
}

template <typename T>
typename VectorWithIds<T>::const_iterator VectorWithIds<T>::findById(int32_t id) const
{
    auto pairsMapIter = pairsMap.find(id);

    if (pairsMapIter != pairsMap.end())
    {
        return const_iterator(pairsMapIter->second);
    }
    else
    {
        return end();
    }
}

template <typename T>
void VectorWithIds<T>::cloneStructure(const VectorWithIds<T>& other)
{
    // Go thorugh
    const int32_t otherSize = static_cast<int32_t>(other.size());
    for (int32_t otherPos = 0; otherPos < otherSize; ++otherPos)
    {
        // Find the same ID in this vector
        int32_t otherId = other.getId(otherPos);

        auto pairsMapIter = pairsMap.find(otherId);

        if (pairsMapIter != pairsMap.end())
        {
            // Reposition
            const auto thisPos = static_cast<int32_t>(std::distance(pairs.begin(), pairsMapIter->second));
            swap(thisPos, otherPos);
        }
        else
        {
            // Create and reposition
            emplaceBackWithId(otherId);
            swap(otherPos, int32_t(pairs.size()) - 1);
        }
    }

    // Delete what is redundant
    if (pairs.size() != other.size())
    {
        pairs.resize(other.size());
        rebuildPairMap();
    }
}

template <typename T>
void VectorWithIds<T>::rebuildPairMap()
{
    pairsMap.clear();
    for (auto pairIter = pairs.begin(); pairIter != pairs.end(); ++pairIter)
    {
        pairsMap.insert(std::make_pair(pairIter->first, pairIter));
    }
}

END_NAMESPACE_CONTAINERS