canonical_shape_tile.hpp

Go to the documentation of this file.

#pragma once
 
#include <algorithm>
#include <array>
#include <compare>
#include <vector>
 
#include "porytiles/domain/models/shape_tile.hpp"
 
namespace porytiles {
 
template <typename PixelType>
class CanonicalShapeTile : public ShapeTile<PixelType> {
  public:
    explicit CanonicalShapeTile(const ShapeTile<PixelType> &tile) : ShapeTile<PixelType>{}
    {
        // Helper struct to store candidate tiles with their flip flags
        struct Candidate {
            ShapeTile<PixelType> flipped_tile;
            bool h_flip;
            bool v_flip;
 
            /*
             * Two-phase strict weak ordering: shape first, then full map as tiebreaker. The shape-only phase
             * ensures non-symmetric shapes always select the geometrically minimal flip. The full-map fallback
             * handles symmetric shapes (where all flip variants have identical key sets) by also considering
             * color values. This guarantees that two tiles which are flips of each other with the same colors
             * will converge on the same canonical form rather than each keeping their own color arrangement.
             */
            bool operator<(const Candidate &other) const
            {
                if (ShapeTile<PixelType>::compare_shape_only(flipped_tile, other.flipped_tile)) {
                    return true;
                }
                if (ShapeTile<PixelType>::compare_shape_only(other.flipped_tile, flipped_tile)) {
                    return false;
                }
                return flipped_tile < other.flipped_tile;
            }
        };
 
        std::array flips = {
            std::pair{false, false}, std::pair{false, true}, std::pair{true, false}, std::pair{true, true}};
 
        std::vector<Candidate> candidates;
        candidates.reserve(4);
 
        for (const auto &[h, v] : flips) {
            candidates.push_back({tile.flip(h, v), h, v});
        }
 
        auto min_candidate = *std::min_element(candidates.begin(), candidates.end());
 
        // Assign the canonical tile data
        *static_cast<ShapeTile<PixelType> *>(this) = min_candidate.flipped_tile;
        h_flip_ = min_candidate.h_flip;
        v_flip_ = min_candidate.v_flip;
    }
 
    auto operator<=>(const CanonicalShapeTile &other) const = default;
 
    [[nodiscard]] bool h_flip() const
    {
        return h_flip_;
    }
 
    [[nodiscard]] bool v_flip() const
    {
        return v_flip_;
    }
 
  private:
    bool h_flip_;
    bool v_flip_;
};
 
} // namespace porytiles