color_set.hpp

Go to the documentation of this file.

#pragma once
 
#include <bitset>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <string>
 
#include "porytiles/domain/models/color_index.hpp"
#include "porytiles/domain/models/palette.hpp"
 
namespace porytiles {
 
inline constexpr std::size_t num_colors = palette::max_size * palette::num_palettes;
 
class ColorSet {
  public:
    ColorSet() = default;
 
    [[nodiscard]] bool test(ColorIndex index) const;
 
    void set(ColorIndex index, bool value = true);
 
    void reset(ColorIndex index);
 
    [[nodiscard]] const std::bitset<num_colors> &colors() const
    {
        return colors_;
    }
 
    [[nodiscard]] bool operator==(const ColorSet &other) const = default;
 
  private:
    std::bitset<num_colors> colors_;
};
 
[[nodiscard]] ColorSet color_set_union(const ColorSet &a, const ColorSet &b);
 
[[nodiscard]] ColorSet color_set_intersection(const ColorSet &a, const ColorSet &b);
 
[[nodiscard]] std::size_t color_set_count(const ColorSet &set);
 
[[nodiscard]] bool is_subset(const ColorSet &a, const ColorSet &b);
 
[[nodiscard]] std::size_t intersection_size(const ColorSet &a, const ColorSet &b);
 
[[nodiscard]] std::size_t union_size(const ColorSet &a, const ColorSet &b);
 
template <typename Func>
void for_each_color(const ColorSet &set, Func &&func)
{
    static_assert(num_colors % 64 == 0, "num_colors must be a multiple of 64 for efficient word-aligned bit scanning");
 
    const auto &bits = set.colors();
 
    // Process 64 bits at a time using efficient bit scanning:
    //
    //     num_colors = 256, so we have 4 64-bit words
    //
    // Note: The +63 ceiling division is a defensive pattern; not strictly necessary due to the static_assert above.
    constexpr std::size_t words = (num_colors + 63) / 64;
 
    for (std::size_t word = 0; word < words; ++word) {
        // Extract 64-bit chunk from bitset
        std::uint64_t chunk = 0;
        const std::size_t base = word * 64;
        for (std::size_t b = 0; b < 64 && (base + b) < num_colors; ++b) {
            if (bits.test(base + b)) {
                chunk |= (1ULL << b);
            }
        }
 
        // Process only set bits - skip zeros efficiently using Brian Kernighan's technique
        while (chunk != 0) {
            // GCC/Clang builtin to find lowest set bit position (count trailing zeros)
            const int bit = __builtin_ctzll(chunk);
            func(base + static_cast<std::size_t>(bit));
            chunk &= chunk - 1; // Clear lowest set bit
        }
    }
}
 
} // namespace porytiles
 
template <>
struct std::hash<porytiles::ColorSet> {
    [[nodiscard]] std::size_t operator()(const porytiles::ColorSet &color_set) const noexcept
    {
        return std::hash<std::string>{}(color_set.colors().to_string());
    }
};