/*
(c) 2012 +++ Filip Stoklas, aka FipS, http://www.4FipS.com +++
THIS CODE IS FREE - LICENSED UNDER THE MIT LICENSE
ARTICLE URL: http://forums.4fips.com/viewtopic.php?f=3&t=768
*/

#include <vector>
#include <algorithm>
#include <cstdint> // uint16_t, ...
#include <cassert>

/// A simple handle-like index, combination of a table index and magic number for consistency checks.
template <typename Bound_T>
struct Record_index_pod
{
    /// Constructs a new index (we don't have a CTOR for this as we want the index to act as a POD).
    static Record_index_pod make(size_t value, size_t magic)
    {
        assert(value <= Value_max_value && magic <= Magic_max_value); // check for overflow
        const Record_index_pod index = { static_cast<uint16_t>(value), static_cast<uint16_t>(magic) };
        assert(index.value() == value && index.magic() == magic); // double check ;)
        return index;
    }

    /// Returns an invalid index (a kind of null-pointer equivalent).
    static Record_index_pod invalid()
    {
        return make(0, Magic_invalid_value);
    }

    /// Checks for invalid index (it, however, doesn't make any assumptions about the record it might refer to).
    bool valid() const
    {
        return *this != invalid();
    }

    size_t value() const { return _value; }
    size_t magic() const { return _magic; }
    size_t key() const { return _key; }

    bool operator == (const Record_index_pod &rhs) const { return _key == rhs._key; }
    bool operator != (const Record_index_pod &rhs) const { return _key != rhs._key; }
    bool operator < (const Record_index_pod &rhs) const { return _key < rhs._key; }
    bool operator > (const Record_index_pod &rhs) const { return _key > rhs._key; }
    bool operator <= (const Record_index_pod &rhs) const { return _key <= rhs._key; }
    bool operator >= (const Record_index_pod &rhs) const { return _key >= rhs._key; }

    enum // define sizes and limits
    {
        Value_bit_count = 16,
        Magic_bit_count = 16,

        Value_max_value = (1 << Value_bit_count) - 1,
        Magic_max_value = (1 << Magic_bit_count) - 1,

        Magic_invalid_value = 0
    };

    union
    {
        struct // bit fields are much easier to debug than masks...
        {
            uint16_t _value : Value_bit_count;
            uint16_t _magic : Magic_bit_count;
        };

        uint32_t _key; // a composite (value & magic)
    };
};

/// A record pool, it stores records by value and provides safe access to them through the index.
template <typename T, typename Index_T = Record_index_pod<T>>
class Record_pool
{
 public:

    typedef Index_T Index;

    /// Creates a new pool, optionally pre-allocated to the given size.
    explicit Record_pool(size_t size = 0)
    {
        grow(size);
    } 

    /// Adds a new record to the pool, returns its index.
    Index add(const T &rec)
    {
        if(_free_list.empty())
            grow(_table.empty() ? 16 : _table.size()); // grow to 16 if empty

        // pop a free table index
        assert(!_free_list.empty());
        const size_t table_index = _free_list.back();
        _free_list.pop_back();

        // store the record & update the magic number
        assert(table_index < _table.size());
        Entry &entry = _table[table_index];
        entry = Entry(rec, entry.magic + 1, true);
        entry.magic += (entry.magic == Index::Magic_invalid_value) ? 1 : 0; // handle wrapping

        assert(entry.magic != Index::Magic_invalid_value);
        return Index::make(table_index, entry.magic);
    }

    /// Removes an existing record from the pool.
    void remove(Index index)
    {
        assert(has(index));

        // deactivate & return to the free list
        _table[index.value()].active = false;
        _free_list.emplace_back(index.value());
    }

    /// Gets a record at the given index, asserts if not found.
    const T & get(Index index) const
    {
        assert(has(index));
        return _table[index.value()].payload;
    }

    /// Gets a record at the given index, asserts if not found.
    T & get(Index index)
    {
        assert(has(index));
        return _table[index.value()].payload;
    }

    /// Checks whether there's a valid record at the given index. 
    bool has(Index index) const
    {
        const size_t table_index = index.value();
        const size_t magic = index.magic();

        const Entry &entry = _table[table_index];

        return
         magic != Index::Magic_invalid_value &&
         table_index < _table.size() &&
         entry.active &&
         entry.magic == magic
        ;
    }

 private:

    /// Grows the pool by the given size.
    void grow(size_t size)
    {
        if(size == 0)
            return;

        const size_t orig_size = _table.size();
        const size_t new_size = orig_size + size;

        // resize the table using T(), therefore T must be default-constructible
        _table.resize(new_size, Entry(T(), Index::Magic_invalid_value, false));
        _free_list.resize(new_size);

        // generate free indices
        size_t magic = new_size;
        std::generate(
         _free_list.begin() + orig_size,
         _free_list.end(),
         [&magic]()->size_t { return --magic; }
        );
    }

    struct Entry
    {
        T payload; // the actual record
        uint32_t magic : Index::Magic_bit_count; // its corresponding magic number
        bool active : 1; // used / unused pool entry

        Entry(const T &payload, size_t magic, bool active):
        payload(payload), magic(magic), active(active)
        {}
    };

    std::vector<Entry> _table;
    std::vector<size_t> _free_list;
};

/// A demo Entity type managed by Record_pool.
struct Entity
{
    std::string name;
    int x, y;

    Entity() : name(), x(), y() {} ///< Must be default-constructible.
    Entity(const std::string &name, int x, int y) : name(name), x(x), y(y) {}
};

int main()
{
    // introduce a new index type (it's typically done in an interface header)
    struct Entity_pool_index_tag {}; // it's bound to this tag to make the index type-safe
    typedef Record_index_pod<Entity_pool_index_tag> Entity_pool_index;

    // define the pool (it's typically done inside implementation)
    typedef Record_pool<Entity, Entity_pool_index> Entity_pool;
    Entity_pool pool;

    // add a new entity into the pool
    const Entity_pool_index foo_index = pool.add(Entity("foo", 10, 20));
    assert(foo_index.valid()); // 'foo_index' is valid
    assert(pool.has(foo_index)); // 'pool' has 'foo'

    // access the entity using the index
    const Entity &foo = pool.get(foo_index);
    printf("entity : name='%s', pos=[%d, %d]\n", foo.name.c_str(), int(foo.x), int(foo.y));

    // remove the entity from the pool
    pool.remove(foo_index);
    assert(foo_index.valid()); // 'foo_index' is valid
    assert(!pool.has(foo_index)); // 'pool' doesn't have 'foo'

    // add a new entity into the empty pool
    const Entity_pool_index bar_index = pool.add(Entity("bar", 10, 20));
    assert(bar_index.valid()); // 'bar_index' is valid
    assert(pool.has(bar_index)); // 'pool' has 'bar'
    assert(foo_index.valid()); // 'foo_index' is valid
    assert(!pool.has(foo_index)); // 'pool' doesn't have 'foo'
    // pool.get(foo_index); // this would assert/crash

    // note that a new index gets the same 'value', but a different 'magic'
    // (the exact behaviour is just an implementation detail though)
    assert(foo_index.value() == bar_index.value() && foo_index.magic() != bar_index.magic());

    return 0;
}

// output:
// entity : name='foo', pos=[10, 20]