Set.impl.h

#pragma once
 
namespace ToolchefsSTL
{
 
    template<typename T>
    Set<T>::Set(Allocator* allocator) noexcept :
        m_data(nullptr),
        m_allocator(allocator),
        m_length(0),
        m_capacity(0)
    {
 
    }
 
    template<typename T>
    Set<T>::~Set() noexcept
    {
        clear();
    }
 
    template<typename T>
    Set<T>::Set(const Set<T>& rhs) noexcept :
        m_data(nullptr),
        m_allocator(rhs.m_allocator),
        m_length(rhs.m_length),
        m_capacity(rhs.m_length)
    {
        if (m_length == 0) return;
        m_data = static_cast<Set::ptr_type>(m_allocator->malloc(sizeof(T) * m_capacity));
#if __cplusplus >= 201703L
        if (std::is_trivially_copyable_v<T>)
        {
            std::memcpy(m_data, rhs.m_data, sizeof(T) * m_length);
        }
        else
#endif
        {
            for (size_t i = 0; i < m_length; ++i)
            {
                new (m_data + i) T(rhs.m_data[i]);
            }
        }
    }
 
    template<typename T>
    Set<T>& Set<T>::operator=(const Set<T>& rhs) noexcept
    {
        if (this == &rhs) return *this;
        if (rhs.m_length == 0)
        {
            clear();
            return *this;
        }
 
        resize(rhs.m_length);
#if __cplusplus >= 201703L
        if (std::is_trivially_copyable_v<T>)
        {
            std::memcpy(m_data, rhs.m_data, sizeof(T) * m_length);
        }
        else
#endif
        {
            for (size_t i = 0; i < m_length; ++i)
            {
                ;
                m_data[i] = rhs.m_data[i];
            }
        }
        return *this;
    }
 
    template<typename T>
    Set<T>::Set(Set<T>&& rhs) noexcept :
        m_data(rhs.m_data),
        m_allocator(rhs.m_allocator),
        m_length(rhs.m_length),
        m_capacity(rhs.m_capacity)
    {
        rhs.m_length = 0;
        rhs.m_capacity = 0;
        rhs.m_data = nullptr;
    }
 
    template<typename T>
    Set<T>& Set<T>::operator=(Set<T>&& rhs) noexcept
    {
        if (m_data) clear();
        m_data = rhs.m_data;
        m_allocator = rhs.m_allocator;
        m_length = rhs.m_length;
        m_capacity = rhs.m_capacity;
 
        rhs.m_data = nullptr;
        rhs.m_length = 0;
        rhs.m_capacity = 0;
        return *this;
    }
 
    template<typename T>
    bool Set<T>::operator==(const Set& rhs) const noexcept
    {
        if (rhs.m_length != m_length) return false;
        for (size_t i = 0; i < m_length; ++i)
        {
            if (m_data[i] != m_data[i]) return false;
        }
        return true;
    }
 
    template<typename T>
    void Set<T>::insert(const T& element) noexcept
    {
        if (find(element) != end()) return;
        if (m_capacity == m_length) grow();
        new (m_data + m_length++) T(element);
    }
 
 
    template<typename T>
    typename Set<T>::iterator Set<T>::begin() noexcept
    {
        return m_data;
    }
 
    template<typename T>
    typename Set<T>::iterator Set<T>::end() noexcept
    {
        return &m_data[m_length];
    }
 
    template<typename T>
    typename Set<T>::const_iterator Set<T>::cbegin() const noexcept
    {
        return m_data;
    }
 
    template<typename T>
    typename Set<T>::const_iterator Set<T>::cend() const noexcept
    {
        return &m_data[m_length];
    }
 
    template<typename T>
    typename Set<T>::reverse_iterator Set<T>::rbegin() noexcept
    {
        return reverse_iterator(&back());
    }
 
    template<typename T>
    typename Set<T>::reverse_iterator Set<T>::rend() noexcept
    {
        T* front_ptr = &front();
        return reverse_iterator(--front_ptr);
    }
 
    template<typename T>
    typename Set<T>::const_reverse_iterator Set<T>::crbegin() const noexcept
    {
        return const_reverse_iterator(&back());
    }
 
    template<typename T>
    typename Set<T>::const_reverse_iterator Set<T>::crend() const noexcept
    {
        T* front_ptr = const_cast<T*>(&front());
        return const_reverse_iterator(--front_ptr);
    }
 
    template<typename T>
    T& Set<T>::back() noexcept
    {
        return  m_data[m_length - 1];
    }
 
    template<typename T>
    const T& Set<T>::back() const noexcept
    {
        return m_data[m_length - 1];
    }
 
    template<typename T>
    T& Set<T>::front() noexcept
    {
        return m_data[0];
    }
 
    template<typename T>
    const T& Set<T>::front() const noexcept
    {
        return m_data[0];
    }
 
    template<typename T>
    const T* Set<T>::data() const noexcept
    {
        return m_data;
    }
 
    template<typename T>
    void Set<T>::resize(size_t new_length) noexcept
    {
        if (new_length == m_length) return;
        if (new_length == 0)
        {
            clear();
            return;
        }
        if (new_length > m_length)
        {
            reserve(new_length);
            for (size_t i = m_length; i < new_length; ++i)
            {
                new (m_data + i) T();
            }
            m_length = new_length;
        }
        else
        {
            m_capacity = new_length;
            ptr_type new_buffer = static_cast<ptr_type>(m_allocator->malloc(sizeof(T) * new_length));
#if __cplusplus >= 201703L
            if (std::is_trivially_copyable_v<T>)
            {
                std::memcpy(new_buffer, m_data, sizeof(T) * new_length);
            }
            else
#endif
            {
                for (size_t i = 0; i < m_length; ++i)
                {
                    T& item = m_data[i];
                    if (i < new_length)
                        new (new_buffer + i) T(std::move(item));
                    item.~T();
                }
            }
            m_allocator->free(m_data);
            m_data = new_buffer;
            m_length = new_length;
        }
    }
 
    template<typename T>
    void Set<T>::clear() noexcept
    {
        if (!std::is_trivially_destructible<T>::value)
        {
            for (size_t i = 0; i < m_length; ++i)
            {
                m_data[i].~T();
            }
        }
 
        if (m_data)
        {
            m_allocator->free(m_data);
            m_data = nullptr;
        }
 
        m_length = 0;
        m_capacity = 0;
    }
 
    template<typename T>
    void Set<T>::reserve(size_t new_capacity) noexcept
    {
        if (new_capacity <= m_capacity) return;
        m_capacity = new_capacity;
        ptr_type new_buffer = static_cast<ptr_type>(m_allocator->malloc(sizeof(T) * m_capacity));
#if __cplusplus >= 201703L
        if (std::is_trivially_copyable_v<T>)
        {
            std::memcpy(new_buffer, m_data, sizeof(T) * m_length);
        }
        else
#endif
        {
            for (size_t i = 0; i < m_length; ++i)
            {
                T& item = m_data[i];
                new (new_buffer + i) T(std::move(item));
                item.~T();
            }
        }
 
        m_allocator->free(m_data);
        m_data = new_buffer;
    }
 
    template<typename T>
    size_t Set<T>::size() const noexcept
    {
        return m_length;
    }
 
    template<typename T>
    size_t Set<T>::length() const noexcept
    {
        return m_length;
    }
 
    template<typename T>
    size_t Set<T>::capacity() const noexcept
    {
        return m_capacity;
    }
 
    template<typename T>
    void Set<T>::grow() noexcept
    {
        m_capacity = m_capacity == 0 ? 1 : m_capacity << 1;
        ptr_type new_buffer = static_cast<ptr_type>(m_allocator->malloc(sizeof(T) * m_capacity));
#if __cplusplus >= 201703L
        if (std::is_trivially_copyable_v<T>)
        {
            std::memcpy(new_buffer, m_data, sizeof(T) * m_length);
        }
        else
#endif
        {
            for (size_t i = 0; i < m_length; ++i)
            {
                T& item = m_data[i];
                new (new_buffer + i) T(std::move(item));
                item.~T();
            }
        }
 
        m_allocator->free(m_data);
        m_data = new_buffer;
 
    }
 
    template<typename T>
    void Set<T>::erase(const T& element) noexcept
    {
        auto it = find(element);
        if (it == end()) return;
        size_t index(it - m_data);
        if (index >= m_length) return;
        for (size_t i = (index + 1); i < m_length; ++i)
            m_data[i - 1] = std::move(m_data[i]);
        m_length--;
        m_data[m_length].~T();
    }
 
 
 
    template<typename T>
    void Set<T>::erase(iterator it) noexcept
    {
        size_t index(it - m_data);
        if (index >= m_length) return;
        for (size_t i = (index + 1); i < m_length; ++i)
            m_data[i - 1] = std::move(m_data[i]);
        m_length--;
        m_data[m_length].~T();
    }
 
    template<typename T>
    void Set<T>::shrink_to_fit() noexcept
    {
        m_capacity = m_length;
        ptr_type new_buffer = static_cast<ptr_type>(m_allocator->malloc(sizeof(T) * m_capacity));
#if __cplusplus >= 201703L
        if (std::is_trivially_copyable_v<T>)
        {
            std::memcpy(new_buffer, m_data, sizeof(T) * m_length);
        }
        else
#endif
        {
            for (size_t i = 0; i < m_capacity; ++i)
            {
                T& item = m_data[i];
                new (new_buffer + i) T(std::move(item));
                item.~T();
            }
        }
 
        m_allocator->free(m_data);
        m_data = new_buffer;
    }
 
    template<typename T>
    typename Set<T>::iterator Set<T>::find(const T& element) noexcept
    {
        auto end_it = end();
        for (auto it = begin(); it != end_it; ++it)
        {
            if (*it == element) return it;
        }
        return end();
    }
 
    template<typename T>
    typename Set<T>::const_iterator Set<T>::find(const T& element) const noexcept
    {
        auto end_it = cend();
        for (auto it = cbegin(); it != end_it; ++it)
        {
            if (*it == element) return it;
        }
        return cend();
    }
 
    template<typename T>
    bool Set<T>::empty() const noexcept
    {
        return m_length == 0;
    }
 
}