Ticket #1707: EntityMap.3.h

#ifndef INCLUDED_ENTITYMAP
#define INCLUDED_ENTITYMAP

/**
 * A fast replacement for map<entity_id_t, T>.
 * We make the following assumptions:
 *  - entity id's (keys) are unique and are inserted in increasing order
 *  - an entity id that was removed is never added again
 *  - modifications (add / delete) are far less frequent then look-ups
 *  - preformance for iteration is important
 */
template<typename T> class EntityMap
{
public:
    // Map interface:
    // Member types
    typedef entity_id_t key_type;
    typedef T mapped_type;
    typedef std::pair<entity_id_t, T> value_type;

    typedef typename std::vector<value_type>::difference_type difference_type;
    typedef typename std::vector<value_type>::size_type size_type;

private:
    std::vector<value_type> m_Data;
    size_t m_Size;

public:
    inline EntityMap() : m_Data(), m_Size(0)
    {
    }

    inline EntityMap(const EntityMap& m) : m_Data(m.m_Data), m_Size(m.m_Size)
    {
    }

    // Iterators
    template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
    {
        U* val;
        inline _iter(U* init) : val(init) { }
        inline U& operator *( ) { return *val; }
        inline U* operator ->( ) { return val; }
        inline _iter& operator++( )
        {
            while ((val++)->first == INVALID_ENTITY) {}
            return *this;
        }
        inline _iter& operator++(int)
        {
            U* ptr = val;
            ++val;
            return ptr;
        }
        inline bool operator != ( _iter other ) { return val != other.val; }
        inline bool operator == ( _iter other ) { return val == other.val; }
        inline operator _iter<U const>() const { return _iter<U const>(val); }
    };

    typedef _iter<value_type> iterator;
    typedef _iter<value_type const> const_iterator;

    inline iterator begin()
    {
        iterator it(&*m_Data.begin());
        if (size() != 0 && it->first == INVALID_ENTITY)
            ++it;
        return it;
    }
    inline iterator end()
    {
        if (size() == 0) return begin();
        return iterator(&*m_Data.end());
    }
    inline const_iterator begin() const
    {
        const_iterator it(&*m_Data.begin());
        if (size() != 0 && it->first == INVALID_ENTITY)
            ++it;
        return it;
    }
    inline const_iterator end() const
    {
        if (size() == 0) return begin();
        return const_iterator(&*m_Data.end());
    }

    // Capacity
    inline bool empty() const                   { return m_Size == 0;   }
    inline size_type size() const               { return m_Size;        }

    // Modification
    std::pair<iterator, bool> insert(const value_type& val)
    {
        difference_type index = val.first;
        bool new_index = false; // was a new element created?
        if (index >= (int)m_Data.size())
        {
            m_Data.resize(index + 1);
            new_index = true;
            ++m_Size;
        }
        m_Data[index] = val;
        return std::make_pair(iterator(&m_Data[index]), new_index); // false: element existed
    }

    void erase(iterator it)
    {
        // only reliable way right now? or we could try ~T() and memset null?
        it->first = INVALID_ENTITY; // mark it as 'invalid entity_id'
        it->second.~T(); // call dtor
        new (&it->second) T(); // call placement new
        if (it == (&m_Data.back()))
            m_Data.pop_back();
        --m_Size;
    }

    size_type erase(const key_type& key)
    {
        iterator it = find(key);
        if (it != end())
            erase(it);
        return 1;
    }

    inline void swap(EntityMap &map)
    {
        m_Data.swap(map.m_Data);
    }

    inline void clear()
    {
        m_Size = 0;
        m_Data.clear();
    }

    // Operations
    inline iterator find(const key_type& key)
    {
        if (key < m_Data.size())
        {
            const value_type& val = m_Data[key];
            if (val.first != INVALID_ENTITY) // is this a valid element?
                return iterator(&m_Data[key]);
        }
        return end(); // not found
    }

    inline const_iterator find(const key_type& key) const
    {
        if (key < m_Data.size())
        {
            const value_type& val = m_Data[key];
            if (val.first != INVALID_ENTITY) // is this a valid element?
                return const_iterator(&m_Data[key]);
        }
        return end(); // not found
    }

    inline size_type count(const key_type& key) const
    {
        return find(key) == end() ? 0 : 1;
    }
};
#endif