Showcase

      
        
         
           #pragma once
#include 
#include 

/**
 * @author Will Bender
 *
 ** Defines an interface to interact with types at runtime.
 */

///////////////////////////////////
/// Type Definitions 

/*
 ** An object that defines a type's definition. 
 ** Pointers may be nullptr
 *
 * This class defines functions that may or may not be implemented by types. When objects that do not have access to
 * type information for template functions, they can use this instead.
 *
 * Contains function pointers to act upon types, and any other information required to operate the data types.
 */
struct MetaType
{
    template
    static MetaType GenerateType();
    
    ///////////////////////////////////
    /// Function pointer definitions
    
    // Note: count iterates through values assuming data is an array.

    // Constructs a value 
    using DefaultConstruct =    void(*)(void* data, uint32_t count);
    // Destructs a value
    using Destruct =            void(*)(void* data, uint32_t count);
    // Moves a value from one memory location to another
    using MoveConstruct =       void(*)(void* src, void* dst, uint32_t count);
    // Moves a value to another initialized structure's location
    using MoveAssign =          void(*)(void* src, void* dst, uint32_t count);
    // Copies a value from an initialized value to a memory location
    using CopyConstruct =       void(*)(void* src, void* dst, uint32_t count);
    // Copies a value from an initialized structure to another initialized structure
    using CopyAssign =          void(*)(void* src, void* dst, uint32_t count);

    
    ///////////////////////////////////
    /// Data

    uint32_t
        mDataSize,      // The size of the data in bytes
        mDataAlignment; // The alignment rules provided by alignas(n)

    
    /// Function Pointers
    
    // Constructs a value 
    DefaultConstruct    mDefaultConstruct;
    // Destructs a value
    Destruct            mDestruct;
    // Moves a value from one memory location to another
    MoveConstruct       mMoveConstruct;
    // Moves a value to another initialized structure's location
    MoveAssign          mMoveAssign;
    // Copies a value from a initialized value to a memory location
    CopyConstruct       mCopyConstruct;
    // Copies a value from an initialized structure to another initialized structure
    CopyAssign          mCopyAssign;
};

///////////////////////////////////
/// Template Implementations

template
MetaType MetaType::GenerateType()
{
    MetaType out{};

    // Fill in size information
    out.mDataSize = sizeof(T);
    out.mDataAlignment = alignof(T);

    
    // Generate lambda functions with known function signatures
    out.mDefaultConstruct = [](void* data, uint32_t count)
    {
        for(uint32_t i = 0; i < count; ++i)
            new (static_cast(data) + i) T();
    };
    out.mDestruct = [](void* data, uint32_t count)
    {
        for(uint32_t i = 0; i < count; ++i)
            static_cast(data)[i].~T();
    };
    out.mMoveConstruct = [](void* src, void* dst, uint32_t count)
    {
        for(uint32_t i = 0; i < count; ++i)
            new (static_cast(dst) + i) T(std::move(*static_cast(src)));
    };
    out.mMoveAssign = [](void* src, void* dst, uint32_t count)
    {
        for(uint32_t i = 0; i < count; ++i)
            static_cast(dst)[i] = std::move(*static_cast(src));
    };
    out.mCopyConstruct = [](void* src, void* dst, uint32_t count)
    {
        for(uint32_t i = 0; i < count; ++i)
            new (static_cast(dst) + i) T(*static_cast(src));
    };
    out.mCopyAssign = [](void* src, void* dst, uint32_t count)
    {
        for(uint32_t i = 0; i < count; ++i)
            static_cast(dst)[i] = static_cast(*src);
    };
    
    return out;
}
 
        
      
    

      
        
         
           /**
 *  @author Will Bender
 */

#pragma once
#include 
#include 
#include 
#include 

/**
 * Slotmap Data Structure
 *
 *  Associative data structure where keys are provided upon data instertion.
 *  Functions as an im-place allocator/arena.
 * 
 * @tparam Value Value type
 */

/**
 * Key type returned by SlotMaps, referenced using `SlotMap::Key`
 *
 * - Index: Index into the `SlotMap`
 * - Generation: The number of times the index in the `SlotMap` has been used.
 *      - Intended to allow for comparisons between two keys, to ensure reused slots to not have identical Keys.
 *
 * DO NOT MODIFY DATA DIRECTLY.
 */
template
class SlotKey
{ 
public:
    GenerationType mGeneration;
    IndexType mIndex;

    SlotKey() :
        mGeneration(std::numeric_limits::max()), mIndex(std::numeric_limits::max()) {};
    
    /**
     * Construct Key. Do not do this unless you know what you are doing.
     * @param generation generation 
     * @param index index
     */
    SlotKey(unsigned generation, unsigned index);

    /**
     * Copy Key
     * @param other Other Key
     */
    SlotKey(const SlotKey& other) = default;
    
    /**
     * Copy key 
     * @param other Other key
     * @return Key
     */
    SlotKey& operator=(const SlotKey& other) = default;

    /**
     * Return the generation of the current key (See `Key`)
     * @return Generation
     */
    GenerationType GetGeneration() const;
    /**
     * Return the index of the current key (See `Key`)
     * @return Index
     */
    IndexType GetIndex() const;

    friend bool operator==(const SlotKey& lhs, const SlotKey& rhs)
    {
        return lhs.mGeneration == rhs.mGeneration
            && lhs.mIndex == rhs.mIndex;
    }

    friend bool operator!=(const SlotKey& lhs, const SlotKey& rhs)
    {
        return !(lhs == rhs);
    }
};

template 
class SlotMap 
{
public:
    using Value = _Value;
    using IndexType = _IndexType;
    using GenerationType = _GenerationType;
    using Key = SlotKey;

    /**
     * Key with type verification, to ensure keys aren't used outside their
     * allocated SlotMaps
     */
    struct TypedKey
    {
        Key mKey;
        
        /**
         * Copy Key
         * @param other Other Key
         */
        TypedKey() : mKey() {};
        
        TypedKey(const TypedKey& other);

        TypedKey(GenerationType generation, IndexType index) :
            mKey(generation, index) {}
        
        TypedKey(Key key) : mKey(key) {}

        /**
         * Copy key 
         * @param other Other key
         * @return Key
         */
        TypedKey& operator=(const TypedKey& other);;

        /**
         * Return the generation of the current key (See `Key`)
         * @return Generation
         */
        GenerationType GetGeneration() const;
        /**
         * Return the index of the current key (See `Key`)
         * @return Index
         */
        IndexType GetIndex() const;

        friend bool operator==(const TypedKey& lhs, const TypedKey& rhs)
        {
            return lhs.mKey == rhs.mKey;
        }

        friend bool operator!=(const TypedKey& lhs, const TypedKey& rhs)
        {
            return !(lhs == rhs);
        }

    private:
    };

private:
    /**
     * Internal node structure
     * Contains the data for the SlotMap
     */
    struct Node
    {
        Node(Value&& data, unsigned generation);
        Node(const Node& other) = delete;
        Node(Node&& other) noexcept;
        Node& operator=(const Node& other) = delete;
        Node& operator=(Node&& other) noexcept = delete;

        ~Node()
        {
            if (mHasData) uData.~Value();
        }

        union
        {
            Value uData;
            size_t uNextFree;
        };

        unsigned mGeneration = 0;
        bool mHasData;
    };

    // limited to sizeof(IndexType) byte indices
    std::vector mNodes;
    size_t mFreeList;
    mutable uint32_t mSize;
    
public:
    

    // Iterator for `SlotMap`
    class iterator
    {
        iterator(SlotMap* map, size_t index) : mPtr(map), mIndex(index)
        {
        }
        SlotMap* mPtr;
        size_t mIndex;

        friend SlotMap;

    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = Value;
        using pointer = Value*;
        using reference = Value&;

        iterator(const iterator& other) = default;
        iterator(iterator&& other) noexcept = default;
        iterator& operator=(const iterator& other) = default;
        iterator& operator=(iterator&& other) noexcept = default;
        ~iterator() = default;

        // Returns a data reference to the corresponding data contained within the `SlotMap`
        reference operator*();
        // Returns the data pointer to the corresponding data contained within the `SlotMap`
        pointer operator->();
        // Returns a const data reference to the corresponding data contained within the `SlotMap`
        reference operator*() const;
        // Returns a const data pointer to the corresponding data contained within the `SlotMap`
        pointer operator->() const;
        // Increments the iterator;
        iterator& operator++();
        // Increments a new iterator;
        iterator operator++(int);

        reference get();
        reference get() const;
        
        Key GetKey();

        // Equivalence function
        friend bool operator==(const iterator& a, const iterator& b)
        {
            return a.mPtr == b.mPtr && a.mIndex == b.mIndex;
        }

        // Inequality function
        friend bool operator!=(const iterator& a, const iterator& b)
        {
            return !(a == b);
        }
    };

    // Const iterator for `SlotMap`
    class const_iterator
    {
        const_iterator(SlotMap* map, size_t index) : mPtr(map), mIndex(index)
        {
        }

        const SlotMap* mPtr;
        size_t mIndex;

        friend SlotMap;

    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = Value;
        using pointer = const Value*;
        using reference = const Value&;

        const_iterator(const const_iterator& other) = default;
        const_iterator(const_iterator&& other) noexcept = default;
        const_iterator& operator=(const const_iterator& other) = default;
        const_iterator& operator=(const_iterator&& other) noexcept = default;
        ~const_iterator() = default;

        // Returns a const reference to the corresponding data contained within `SlotMap`
        reference operator*() const;
        // Returns a const pointer to the corresponding data contained within `SlotMap`
        pointer operator->() const;
        // Increments the iterator
        iterator& operator++();
        // Increments a new iterator
        iterator operator++(int);

        reference get() const;

        Key GetKey();

        // Equality Function
        friend bool operator==(const iterator& a, const iterator& b)
        {
            return a.mPtr == b.mPtr && a.mIndex == b.mIndex;
        }

        // Inequality Function
        friend bool operator!=(const iterator& a, const iterator& b)
        {
            return !(a == b);
        }
    };

    // Create a new `SlotMap`
    SlotMap() : mNodes(), mFreeList(SIZE_MAX)
    {
    }
    // Copy an iterator into a `SlotMap`
    template 
    SlotMap(I& data) : mNodes(data.begin(), data.end()), mFreeList(SIZE_MAX)
    {
    }
    // Move `SlotMap` data into another 
    SlotMap(SlotMap&& other) noexcept : mNodes(std::move(other.mNodes)), mFreeList(other.mFreeList)
    {
    }

    // Copy a SlotMap from one to another
    SlotMap(const SlotMap& other) : mNodes(other.mNodes), mFreeList(other.mFreeList)
    {
    }

    SlotMap(std::initializer_list initializerList) : mNodes(initializerList), mFreeList(SIZE_MAX)
    {
    }

    /**
     * Insert new data, returning a `TypedKey`
     * @param data Value to insert
     * @return Key referring to data
     */
    TypedKey insert(Value&& data);
    /**
     * Remove data corresponding to given `Key`
     * @param key Data to remove
     */
    void remove(Key key);
    void remove(TypedKey key);
    /**
     * Attempt to remove data corresponding to given `Key`, return false on error/fail.
     * @param key Data to remove
     * @return Success
     */
    bool TryRemove(Key key);
    bool TryRemove(TypedKey key);
    /**
     * Check if data is contained within the `SlotMap`
     * @param key Data to check
     * @return Contained
     */
    bool contains(const Key& key);
    bool contains(const TypedKey& key);
    /**
     * Remove data in `SlotMap` at location
     * @param iter Iterator to remove at
     */
    iterator erase(iterator& iter);
    /**
     * Remove data in `SlotMap` at location
     * @param iter Iterator to remove at
     */
    const_iterator erase(const_iterator& iter);

    /**
     * Return the iterator at the start of the `SlotMap`
     * @return Iterator at the start
     */
    iterator begin();
    /**
     * Return the iterator at the start of the `SlotMap`
     * @return Constant iterator at the start
     */
    const_iterator begin() const;
    /**
     * Return the iterator at the end of the `SlotMap`
     * @return Iterator at the end
     */
    iterator end();
    /**
     * Return the iterator at the end of the `SlotMap`
     * @return Const iterator at the end
     */
    const_iterator end() const;

    /**
     * Index into the slotmap
     * @param key Key to index with
     * @return Iterator at the location
     */
    iterator operator[](const Key& key);
    iterator operator[](const TypedKey& key);
    /**
     * Index into the slotmap
     * @param key Key to index with
     * @return Const iterator at the location
     */
    const_iterator operator[](const Key& key) const;
    const_iterator operator[](const TypedKey& key) const;
    /**
     * Find a value in the slotmap
     * @param key Key to index with
     * @return Iterator at the location
     */
    iterator find(const Key& key);
    iterator find(const TypedKey& key);
    /**
     * Find a value in the slotmap
     * @param key Key to index with
     * @return Const iterator at the location
     */
    const_iterator find(const Key& key) const;
    const_iterator find(const TypedKey& key) const;

    GenerationType GetGeneration(const IndexType& key) const;

    uint32_t Size() const;

};


template
class KeyHasher
{
public:
    std::size_t operator()(const SlotKey& key) const
    {
        size_t seed = std::hash()(key.GetGeneration());
        seed ^= std::hash()(key.GetIndex()) 
            + 0x9e3779b9 + (seed<<6) + (seed>>2);
        return seed;
    }
};

template
class TypedKeyHasher
{
public:
    std::size_t operator()(const typename SlotMap::TypedKey& key) const
    {
        size_t seed = std::hash()(key.GetGeneration());
        seed ^= std::hash()(key.GetIndex()) 
            + 0x9e3779b9 + (seed<<6) + (seed>>2);
        return seed;
    }
};

template 
bool operator==(const typename SlotMap::iterator& a,
                const typename SlotMap::iterator& b)
{
    return a.ptr == b.ptr && a.index == b.index;
}

template 
bool operator!=(const typename SlotMap::iterator& a, const typename SlotMap::iterator& b)
{
    return !(a == b);
}

template 
bool operator==(const typename SlotMap::const_iterator& a, const typename SlotMap::const_iterator& b)
{
    return a.ptr == b.ptr && a.index == b.index;
}

template 
bool operator!=(const typename SlotMap::const_iterator& a, const typename SlotMap::const_iterator& b)
{
    return !(a == b);
}

template 
SlotKey::SlotKey(unsigned generation, unsigned index): mGeneration(generation),
    mIndex(index)
{
}

template 
IndexType SlotKey::GetGeneration() const
{
    return mGeneration;
}

template 
GenerationType SlotKey::GetIndex() const
{
    return mIndex;
}

template 
SlotMap::TypedKey::TypedKey(const TypedKey& other) : mKey(other.mKey)
{
}

template 
typename SlotMap::TypedKey& SlotMap::TypedKey::
operator=(const TypedKey& other)
{
    mKey = other.mKey;
    return *this;
}

template 
GenerationType SlotMap::TypedKey::GetGeneration() const
{
    return mKey.GetGeneration();
}

template 
IndexType SlotMap::TypedKey::GetIndex() const
{
    return mKey.GetIndex();
}

template 
SlotMap::Node::Node(Value&& data, unsigned generation): uData(data), mGeneration(generation), mHasData(true)
{
}

template 
SlotMap::Node::Node(Node&& other) noexcept
{
    mHasData = other.mHasData;
    mGeneration = other.mGeneration;
    if(mHasData)
    {
        uData = other.uData;
    }
    else
    {
        uNextFree = other.uNextFree;
    }
}

template 
bool operator==(const typename SlotMap::Key& lhs,
                const typename SlotMap::Key& rhs)
{
    return lhs.mGeneration == rhs.mGeneration
        && lhs.mIndex == rhs.mIndex;
}

template 
typename SlotMap::iterator::reference SlotMap<
    Value, GenerationType, IndexType>::iterator::operator*()
{
    return mPtr->mNodes[mIndex].uData;
}

template 
typename SlotMap::iterator::pointer SlotMap<
    Value, GenerationType, IndexType>::iterator::operator->()
{
    return &mPtr->mNodes[mIndex].uData;
}

template 
typename SlotMap::iterator::reference SlotMap<
    Value, GenerationType, IndexType>::iterator::operator*() const
{
    return mPtr->mNodes[mIndex].uData;
}

template 
typename SlotMap::iterator::pointer SlotMap<
    Value, GenerationType, IndexType>::iterator::operator->() const
{
    return &mPtr->mNodes[mIndex].uData;
}

template 
typename SlotMap::iterator& SlotMap<
    Value, GenerationType, IndexType>::iterator::operator++()
{
    if (mIndex >= mPtr->mNodes.size())
    {
        throw std::runtime_error("Incremented iterator on end");
    }

    mIndex++;

    while (!mPtr->mNodes[mIndex].mHasData)
    {
        if (mIndex >= mPtr->mNodes.size())
        {
            return *this;
        }

        mIndex++;
    }
    return *this;
}

template 
typename SlotMap::iterator SlotMap<
    Value, GenerationType, IndexType>::iterator::operator++(int)
{
    iterator out = *this;
    ++(*this);
    return out;
}

template 
typename SlotMap::iterator::reference SlotMap::
iterator::get()
{
    return **this;
}

template 
typename SlotMap::iterator::reference SlotMap::
iterator::get() const
{
    return **this;
}

template 
typename SlotMap::Key SlotMap::iterator::GetKey()
{
    auto& map = mPtr->mNodes[mIndex];
    return Key{map.mGeneration, mIndex};
}

template 
typename SlotMap::const_iterator::reference SlotMap<
    Value, GenerationType, IndexType>::const_iterator::operator*() const
{
    return mPtr->mNodes[mIndex].uData;
}

template 
typename SlotMap::const_iterator::pointer SlotMap<
    Value, GenerationType, IndexType>::const_iterator::operator->() const
{
    return &mPtr->mNodes[mIndex].uData;
}

template 
typename SlotMap::iterator& SlotMap<
    Value, GenerationType, IndexType>::const_iterator::operator++()
{
    if (mIndex >= mPtr->mNodes.size())
    {
        throw std::runtime_error("Incremented iterator on end");
    }

    mIndex++;

    while (!mPtr->mNodes[mIndex].has_data)
    {
        if (mIndex >= mPtr->mNodes.size())
        {
            return *this;
        }

        mIndex++;
    }
    return *this;
}

template 
typename SlotMap::iterator SlotMap<
    Value, GenerationType, IndexType>::const_iterator::operator++(int)
{
    iterator out = *this;
    ++(*this);
    return out;
}

template 
typename SlotMap::const_iterator::reference SlotMap::const_iterator::get() const
{
    return **this;
}

template 
typename SlotMap::Key SlotMap::const_iterator::
GetKey()
{
    auto& map = mPtr->mNodes[mIndex];
    return Key{map.mGeneration, mIndex};   
}

template 
typename SlotMap::TypedKey SlotMap::insert(Value&& data)
{
    if (mFreeList != SIZE_MAX)
    {
        size_t next = mNodes[mFreeList].uNextFree;
        new (&mNodes[mFreeList].uData) Value{std::move(data)};
        Key key(mNodes[mFreeList].mGeneration, static_cast(mFreeList));
        mNodes[mFreeList].mHasData = true;
        mFreeList = next;
        ++mSize;
        return key;
    }

    Key key(0, static_cast(mNodes.size()));
    mNodes.emplace_back(std::move(data), 0);
    ++mSize;
    return TypedKey{key};
}

template 
void SlotMap::remove(Key key)
{
    if (key.mIndex >= mNodes.size())
    {
        throw std::runtime_error("Invalid key - invalid index");
    }

    Node& node = mNodes[key.mIndex];
    if (node.mGeneration != key.mGeneration)
    {
        throw std::runtime_error("Invalid key - object already destroyed");
    }

    node.mGeneration += 1;
    node.uData.~Value();
    node.uNextFree = mFreeList;
    node.mHasData = false;
    mFreeList = key.mIndex;
    --mSize;
}

template 
void SlotMap::remove(TypedKey key)
{
    remove(key.mKey);
}

template 
bool SlotMap::TryRemove(Key key)
{
    if (key.mIndex >= mNodes.size())
    {
        return false;
    }

    Node& node = mNodes[key.mIndex];
    if (node.mGeneration != key.mGeneration)
    {
        return false;
    }

    node.mGeneration += 1;
    node.uData.~Value();
    node.uNextFree = mFreeList;
    node.mHasData = false;
    mFreeList = key.index;

    --mSize;

    return true;
}

template 
bool SlotMap::TryRemove(TypedKey key)
{
    return TryRemove(key.mKey);
}

template 
bool SlotMap::contains(const Key& key)
{
    if (key.mIndex >= mNodes.size()) return false;
    return mNodes[key.mIndex].mGeneration == key.mGeneration;
}

template 
bool SlotMap::contains(const TypedKey& key)
{
    return contains(key.mKey);
}

template 
typename SlotMap::iterator SlotMap<
    Value, GenerationType, IndexType>::erase(iterator& iter)
{
    if (iter.mPtr != this)
        throw std::runtime_error("Attempted to remove value from incorrect SlotMap");

    if (iter.mPtr == end())
        throw std::runtime_error("Erased called with end iterator");

    if (iter.mIndex >= mNodes.size())
        throw std::runtime_error("Attempted to remove value with invalid index");

    Node& node = mNodes[iter.mIndex];

    node.mGeneration += 1;
    node.uData.~Value();
    node.uNextFree = mFreeList;
    node.mHasData = false;
    mFreeList = iter.mIndex;

    ++iter.mIndex;

    --mSize;

    return iter;
}

template 
typename SlotMap::const_iterator SlotMap::erase(
    const_iterator& iter)
{
    if (iter.mPtr != this)
        throw std::runtime_error("Attempted to remove value from incorrect SlotMap");

    if (iter.mPtr == end())
        throw std::runtime_error("Erased called with end iterator");

    if (iter.mIndex >= mNodes.size())
        throw std::runtime_error("Attempted to remove value with invalid index");

    Node& node = mNodes[iter.mIndex];

    node.mGeneration += 1;
    node.uData.~T();
    node.uNextFree = mFreeList;
    node.mHasData = false;
    mFreeList = iter.mIndex;

    ++iter.mIndex;

    ++mSize;

    return iter;
}

template 
typename SlotMap::iterator SlotMap::begin()
{
    return iterator(this, 0);
}

template 
typename SlotMap::const_iterator SlotMap<
    Value, GenerationType, IndexType>::begin() const
{
    return const_iterator(this, 0);
}

template 
typename SlotMap::iterator SlotMap::end()
{
    return iterator(this, mNodes.size());
}

template 
typename SlotMap::const_iterator SlotMap<
    Value, GenerationType, IndexType>::end() const
{
    return const_iterator(this, mNodes.size());
}

template 
typename SlotMap::iterator SlotMap::operator[
](const Key& key)
{
    return find(key);
}

template 
typename SlotMap::iterator SlotMap::operator[](
    const TypedKey& key)
{
    return (*this)[key.mKey];
}

template 
typename SlotMap::const_iterator SlotMap::operator[
](const Key& key) const
{
    return find(key);
}

template 
typename SlotMap::const_iterator SlotMap::
operator[](const TypedKey& key) const
{
    return (*this)[key.mKey];
}

template 
typename SlotMap::iterator SlotMap<
    Value, GenerationType, IndexType>::find(const Key& key)
{
    if (key.mIndex >= mNodes.size())
    {
        throw std::runtime_error("Invalid key - invalid index");
    }

    Node& node = mNodes[key.mIndex];
    if (node.mGeneration != key.mGeneration)
    {
        throw std::runtime_error("Invalid key - object already destroyed");
    }

    return iterator(this, key.mIndex);
}

template 
typename SlotMap::iterator SlotMap::find(
    const TypedKey& key)
{
    return find(key.mKey);
}

template 
typename SlotMap::const_iterator SlotMap::find(
    const Key& key) const
{
    if (key.mIndex >= mNodes.size())
    {
        throw std::runtime_error("Invalid key - invalid index");
    }

    const Node& node = mNodes[key.mIndex];
    if (node.mGeneration != key.mGeneration)
    {
        throw std::runtime_error("Invalid key - object already destroyed");
    }

    return const_iterator(this, key.mIndex);
}

template 
typename SlotMap::const_iterator SlotMap::find(
    const TypedKey& key) const
{
    return find(key.mKey);
}

template 
typename SlotMap<_Value, _IndexType, _GenerationType>::GenerationType SlotMap<_Value, _IndexType, _GenerationType>::
GetGeneration(const IndexType& key) const
{
    return mNodes[key].mGeneration;
}

template 
uint32_t SlotMap<_Value, _IndexType, _GenerationType>::Size() const
{
    return mSize;
}