mgl_array_2d.h

[詳解]

// SPDX-License-Identifier: Zlib
/* ------------------------------------------------------------------------- */
/* ------------------------------------------------------------------------- */
 
#ifndef INCGUARD_MGL_ARRAY_2D_H_1746562234
#define INCGUARD_MGL_ARRAY_2D_H_1746562234
 
#include <memory>
#include <type_traits>
#include <utility>
 
#include <mgl/common/mgl_range.h>
#include <mgl/memory/mgl_memory.h>
#include <mgl/memory/mgl_memory_utility.h>
#include <mgl/system/mgl_system_debug_macro.h>
 
namespace MGL
{
/* ------------------------------------------------------------------------- */
/* ------------------------------------------------------------------------- */
template <class ValueType, class IndexType = size_t>
class Array2D
{
public:
    // 配列の要素はデフォルト構築可能でなければならない
    static_assert(std::is_default_constructible_v<ValueType>, "Array2D element must be constructible by default.");
 
    // インデックスは整数型である必要がある
    static_assert(std::is_integral_v<IndexType>, "IndexType must be integral value.");
 
    // コピーは禁止
    Array2D(Array2D &) = delete;
    Array2D &operator=(Array2D &) = delete;
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    Array2D(Memory::ClearMode clearMode = Memory::ClearMode::Auto) noexcept
        : Array2D(0, 0, clearMode)
    {
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    Array2D(IndexType width, IndexType height, Memory::ClearMode clearMode = Memory::ClearMode::Auto) noexcept
    {
        Allocate(width, height, clearMode);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    Array2D(IndexType width, IndexType height, const ValueType &invalidValue, Memory::ClearMode clearMode = Memory::ClearMode::Auto) noexcept
    {
        Allocate(width, height, clearMode);
        SetInvalidValue(invalidValue);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    Array2D(IndexType width, IndexType height, ValueType &&invalidValue, Memory::ClearMode clearMode = Memory::ClearMode::Auto) noexcept
    {
        Allocate(width, height, clearMode);
        SetInvalidValue(std::move(invalidValue));
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    Array2D(Array2D &&rhs) noexcept
    {
        *this = std::move(rhs);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    Array2D &operator=(Array2D &&rhs) noexcept
    {
        Deallocate();
 
        // NOLINTBEGIN(cppcoreguidelines-prefer-member-initializer) : 上のDeallocate()が呼べなくなるので無理
        _width = rhs._width;
        _height = rhs._height;
        _arraySize = rhs._arraySize;
        _top = rhs._top;
        _tail = rhs._tail;
        // NOLINTEND(cppcoreguidelines-prefer-member-initializer)
 
        rhs._width = 0;
        rhs._height = 0;
        rhs._arraySize = 0;
        rhs._top = nullptr;
        rhs._tail = nullptr;
 
        return *this;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    ~Array2D() noexcept
    {
        Deallocate();
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    bool New(IndexType width, IndexType height, Memory::ClearMode clearMode = Memory::ClearMode::Auto) noexcept
    {
        // 末尾（無効値）が存在している場合はそれを保つように生成
        if (_tail != nullptr)
        {
            auto invalidValue = std::move(*_tail);    // アロケート中に消えるので別のメモリ空間に移動しておく
            if (Allocate(width, height, clearMode))
            {
                SetInvalidValue(std::move(invalidValue));
                return true;
            }
            return false;
        }
        // 末尾が存在していない場合は普通に生成
        else
        {
            // Note: 実はここには到達しない（コンストラクタがアロケートして無効値も生成されるため）
            return Allocate(width, height, clearMode);
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    bool Renew(Memory::ClearMode clearMode = Memory::ClearMode::Auto) noexcept
    {
        return New(_width, _height, clearMode);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    constexpr void Fill(const ValueType &value) noexcept
    {
        for (auto *e = begin(); e != end(); ++e)
        {
            *e = value;
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] static constexpr std::pair<IndexType, IndexType> MakePair(IndexType x, IndexType y) noexcept
    {
        return {x, y};
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr const ValueType &Get(IndexType x, IndexType y) const noexcept
    {
        return _top[GetIndex(x, y)];
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] const ValueType &Get(const std::pair<IndexType, IndexType> &pair) const noexcept
    {
        return Get(pair.first, pair.second);
    }
 
#if __cplusplus >= 202211L    // 添字演算子の多次元サポートはC++23以降で利用可能
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] const ValueType &operator[](IndexType x, IndexType y) const noexcept
    {
        return Get(x, y);
    }
#endif
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] const ValueType &operator[](const std::pair<IndexType, IndexType> &pair) const noexcept
    {
        return Get(pair.first, pair.second);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr ValueType *GetPtr(IndexType x, IndexType y) noexcept
    {
        auto index = GetIndex(x, y);
        if (index >= _arraySize)
        {
            return nullptr;
        }
 
        return &_top[index];
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr ValueType *GetPtr(const std::pair<IndexType, IndexType> &pair) noexcept
    {
        return GetPtr(pair.first, pair.second);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    constexpr bool Set(IndexType x, IndexType y, const ValueType &value) noexcept
    {
        if (auto *e = GetPtr(x, y); e != nullptr)
        {
            *e = value;
            return true;
        }
 
        return false;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    constexpr bool Set(const std::pair<IndexType, IndexType> &pair, const ValueType &value) noexcept
    {
        return Set(pair.first, pair.second, value);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    constexpr bool Set(IndexType x, IndexType y, const ValueType &&value) noexcept
    {
        if (auto *e = GetPtr(x, y); e != nullptr)
        {
            *e = std::move(value);
            return true;
        }
 
        return false;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    constexpr bool Set(const std::pair<IndexType, IndexType> &pair, const ValueType &&value) noexcept
    {
        return Set(pair.first, pair.second, std::forward<ValueType>(value));
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class Body>
    constexpr bool Write(IndexType x, IndexType y, Body body) noexcept
    {
        if (auto *e = GetPtr(x, y); e != nullptr)
        {
            if constexpr (std::is_invocable_r_v<void, decltype(body), ValueType &>)
            {
                body(*e);
                return true;
            }
            else
            {
                static_assert(std::false_type::value, "Write function is not matching arguments.");
                return false;
            }
        }
 
        return false;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class Body>
    constexpr bool Write(const std::pair<IndexType, IndexType> &pair, Body body) noexcept
    {
        return Write(pair.first, pair.second, body);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class LoopBody>
    constexpr void ForEach(LoopBody body) noexcept
    {
        for (IndexType y = 0; y < _height; ++y)
        {
            for (IndexType x = 0; x < _width; ++x)
            {
                if (!InvokeLoopBody(body, x, y))
                {
                    return;
                }
            }
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class LoopBody>
    constexpr void ForEach(LoopBody body) const noexcept
    {
        for (IndexType y = 0; y < _height; ++y)
        {
            for (IndexType x = 0; x < _width; ++x)
            {
                if (!InvokeLoopBody(body, x, y))
                {
                    return;
                }
            }
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class LoopBody>
    constexpr void ForRange(IndexType beginX, IndexType beginY, IndexType endX, IndexType endY, LoopBody body) noexcept
    {
        if (_arraySize == 0)
        {
            return;
        }
 
        Range<IndexType> rangeX(
            std::clamp(beginX, static_cast<IndexType>(0), GetWidth() - 1),
            std::clamp(endX, static_cast<IndexType>(0), GetWidth() - 1));
 
        Range<IndexType> rangeY(
            std::clamp(beginY, static_cast<IndexType>(0), GetHeight() - 1),
            std::clamp(endY, static_cast<IndexType>(0), GetHeight() - 1));
 
        for (auto y = rangeY.Begin(); rangeY.Contains(y); y = rangeY.Next(y))
        {
            for (auto x = rangeX.Begin(); rangeX.Contains(x); x = rangeX.Next(x))
            {
                if (!InvokeLoopBody(body, x, y))
                {
                    return;
                }
            }
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class LoopBody>
    constexpr void ForRange(
        const std::pair<IndexType, IndexType> &begin,
        const std::pair<IndexType, IndexType> &end,
        LoopBody body) noexcept
    {
        ForRange(begin.first, begin.second, end.first, end.second, body);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class LoopBody>
    constexpr void ForRange(IndexType beginX, IndexType beginY, IndexType endX, IndexType endY, LoopBody body) const noexcept
    {
        if (_arraySize == 0)
        {
            return;
        }
 
        Range<IndexType> rangeX(
            std::clamp(beginX, 0, GetWidth() - 1),
            std::clamp(endX, 0, GetWidth() - 1));
 
        Range<IndexType> rangeY(
            std::clamp(beginY, 0, GetHeight() - 1),
            std::clamp(endY, 0, GetHeight() - 1));
 
        for (auto y = rangeY.Begin(); rangeY.Contains(y); y = rangeY.Next(y))
        {
            for (auto x = rangeX.Begin(); rangeX.Contains(x); x = rangeX.Next(x))
            {
                if (!InvokeLoopBody(body, x, y))
                {
                    return;
                }
            }
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class LoopBody>
    constexpr void ForRange(
        const std::pair<IndexType, IndexType> &begin,
        const std::pair<IndexType, IndexType> &end,
        LoopBody body) const noexcept
    {
        ForRange(begin.first, begin.second, end.first, end.second, body);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr bool Contains(const ValueType &element) const noexcept
    {
        return Contains(std::addressof(element));
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr bool Contains(const ValueType *element) const noexcept
    {
        // Note:
        // ValueType型の実体をを内包するValueType型は作れないはずなので、
        // 各要素のアドレスと一致するかのチェックは不要なはず。
 
        auto topAddress = reinterpret_cast<uintptr_t>(_top);
        auto elemAddress = reinterpret_cast<uintptr_t>(element);
        auto tailAddress = reinterpret_cast<uintptr_t>(_tail);
 
        return (topAddress <= elemAddress) && (elemAddress < tailAddress);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    constexpr void SetInvalidValue(const ValueType &value) noexcept
    {
        if (_tail != nullptr)
        {
            *_tail = value;
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    constexpr void SetInvalidValue(ValueType &&value) noexcept
    {
        if (_tail != nullptr)
        {
            *_tail = std::move(value);
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr IndexType GetWidth() const noexcept
    {
        return _width;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr IndexType GetHeight() const noexcept
    {
        return _height;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr size_t GetArraySize() const noexcept
    {
        return _arraySize;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr ValueType *begin() const noexcept
    {
        return _top;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr ValueType *end() const noexcept
    {
        return _tail;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr const ValueType *cbegin() const noexcept
    {
        return _top;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr const ValueType *cend() const noexcept
    {
        return _tail;
    }
 
private:
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    bool Allocate(IndexType width, IndexType height, Memory::ClearMode clearMode) noexcept
    {
        // IndexTypeが符号付きの場合、負の値を0に補正する
        if constexpr (std::is_signed_v<IndexType>)
        {
            width = std::max(0, width);
            height = std::max(0, height);
        }
 
        // 行または列のサイズに0が指定されている場合はサイズ0の配列とみなす
        if ((width == 0) || (height == 0))
        {
            width = height = 0;
        }
        auto arraySize = static_cast<size_t>(width) * static_cast<size_t>(height);
 
        // 生成済みかつ同サイズであればアロケートを省略
        if ((_top != nullptr) && (_arraySize == arraySize))
        {
            // 全てのデストラクタを呼び出す
            std::destroy_n(_top, _arraySize + 1);
 
            // メモリ領域をクリア
            _top = Memory::Utility::InitializeArrayBuffer<ValueType>(_top, _arraySize + 1, clearMode);
        }
        // 未生成、またはサイズが異なる場合は一旦削除して際生成
        else
        {
            // 一旦削除
            Deallocate();
 
            // アロケータからメモリを確保
            const auto size = sizeof(ValueType) * (arraySize + 1);
            auto *ptr = Memory::Allocate(size);
            MGL_ASSERT(ptr, "Memory allocation failed.");
            if (ptr == nullptr)
            {
                return false;
            }
 
            // メモリ領域をクリア
            _top = Memory::Utility::InitializeArrayBuffer<ValueType>(ptr, arraySize + 1, clearMode);
 
            // 確保したメモリリソースをもとに各メンバを初期化
            _tail = std::addressof(_top[arraySize]);
            _width = width;
            _height = height;
            _arraySize = arraySize;
        }
 
        return true;
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    void Deallocate() noexcept
    {
        if (_top != nullptr)
        {
            std::destroy_n(_top, _arraySize + 1);
            Memory::Deallocate(_top);
            _top = _tail = nullptr;
            _arraySize = 0;
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    [[nodiscard]] constexpr size_t GetIndex(IndexType x, IndexType y) const noexcept
    {
        // 符号付きの場合、どちらか一方が負の値だったら失敗
        if constexpr (std::is_signed_v<IndexType>)
        {
            if (x < 0 || y < 0)
            {
                return _arraySize;
            }
        }
 
        // どちらか一方が指定サイズより大きければ失敗
        if (x >= _width)
        {
            return _arraySize;
        }
        if (y >= _height)
        {
            return _arraySize;
        }
 
        return static_cast<size_t>(y * _width + x);
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class LoopBody>
    constexpr bool InvokeLoopBody(LoopBody body, IndexType x, IndexType y) noexcept
    {
        // 座標付き、中断あり
        if constexpr (std::is_invocable_r_v<bool, decltype(body), IndexType, IndexType, ValueType &>)
        {
            return body(x, y, _top[GetIndex(x, y)]);
        }
        // 座標付き、中断なし
        else if constexpr (std::is_invocable_r_v<void, decltype(body), IndexType, IndexType, ValueType &>)
        {
            body(x, y, _top[GetIndex(x, y)]);
            return true;
        }
        // 座標なし、中断あり
        else if constexpr (std::is_invocable_r_v<bool, decltype(body), ValueType &>)
        {
            return body(_top[GetIndex(x, y)]);
        }
        // 座標なし、中断なし
        else if constexpr (std::is_invocable_r_v<void, decltype(body), ValueType &>)
        {
            body(_top[GetIndex(x, y)]);
            return true;
        }
        // それ以外は不適格
        else
        {
            static_assert(std::false_type::value, "Loop body is not matching arguments.");
            return false;
        }
    }
 
    /* ------------------------------------------------------------------------- */
    /* ------------------------------------------------------------------------- */
    template <class LoopBody>
    constexpr bool InvokeLoopBody(LoopBody body, IndexType x, IndexType y) const noexcept
    {
        // 座標付き、中断あり
        if constexpr (std::is_invocable_r_v<bool, decltype(body), IndexType, IndexType, const ValueType &>)
        {
            return body(x, y, _top[GetIndex(x, y)]);
        }
        // 座標付き、中断なし
        else if constexpr (std::is_invocable_r_v<void, decltype(body), IndexType, IndexType, const ValueType &>)
        {
            body(x, y, _top[GetIndex(x, y)]);
            return true;
        }
        // 座標なし、中断あり
        else if constexpr (std::is_invocable_r_v<bool, decltype(body), const ValueType &>)
        {
            return body(_top[GetIndex(x, y)]);
        }
        // 座標なし、中断なし
        else if constexpr (std::is_invocable_r_v<void, decltype(body), const ValueType &>)
        {
            body(_top[GetIndex(x, y)]);
            return true;
        }
        // それ以外は不適格
        else
        {
            static_assert(std::false_type::value, "Loop body is not matching arguments.");
            return false;
        }
    }
 
    IndexType _width{0};
    IndexType _height{0};
    size_t _arraySize{0};
    ValueType *_top{nullptr};
    ValueType *_tail{nullptr};
};
}    // namespace MGL
 
#endif    // INCGUARD_MGL_ARRAY_2D_H_1746562234
 
// vim: et ts=4 sw=4 sts=4