Palette from Image — C++ source

// palette-from-image — C++ port: dominant-color extraction via median-cut
// quantization. C++17, standard library only. Port of src/lib/palette-extract.ts
// — same logic as this dir's typescript.ts; empty or fully-transparent input
// yields an empty palette.
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <string>
#include <vector>

// One dominant color: averaged RGB plus the pixel count it represents.
struct Swatch {
    int r, g, b;
    size_t population;
};

// An opaque sample pixel (alpha-0 pixels are dropped at sampling time).
struct Pixel {
    uint8_t r, g, b;
};

// Down-sample so large images quantize in bounded time.
constexpr size_t kMaxSamples = 16384;

// The widest single-channel span (0-255) inside a bucket.
int channelRange(const std::vector<Pixel>& bucket) {
    int minR = 255, maxR = 0, minG = 255, maxG = 0, minB = 255, maxB = 0;
    for (const Pixel& p : bucket) {
        minR = std::min<int>(minR, p.r), maxR = std::max<int>(maxR, p.r);
        minG = std::min<int>(minG, p.g), maxG = std::max<int>(maxG, p.g);
        minB = std::min<int>(minB, p.b), maxB = std::max<int>(maxB, p.b);
    }
    return std::max({maxR - minR, maxG - minG, maxB - minB});
}

// Split a bucket in two at the median of its widest channel (ties prefer r,
// then g — mirroring the TS reduce). std::stable_sort keeps equal pixels in
// sampling order, so the split is deterministic.
std::vector<std::vector<Pixel>> splitBucket(std::vector<Pixel> bucket) {
    int minR = 255, maxR = 0, minG = 255, maxG = 0, minB = 255, maxB = 0;
    for (const Pixel& p : bucket) {
        minR = std::min<int>(minR, p.r), maxR = std::max<int>(maxR, p.r);
        minG = std::min<int>(minG, p.g), maxG = std::max<int>(maxG, p.g);
        minB = std::min<int>(minB, p.b), maxB = std::max<int>(maxB, p.b);
    }
    const int ranges[3] = {maxR - minR, maxG - minG, maxB - minB};
    int ch = 0; // r
    if (ranges[1] > ranges[ch]) ch = 1; // g
    if (ranges[2] > ranges[ch]) ch = 2; // b

    std::stable_sort(bucket.begin(), bucket.end(), [ch](const Pixel& a, const Pixel& b) {
        return ch == 0 ? a.r < b.r : ch == 1 ? a.g < b.g : a.b < b.b;
    });
    const size_t mid = bucket.size() / 2;
    return {{bucket.begin(), bucket.begin() + mid}, {bucket.begin() + mid, bucket.end()}};
}

// Round-half-up average of a channel sum over n (TS Math.round semantics).
constexpr int roundAvg(long long sum, size_t n) {
    return static_cast<int>((2 * sum + static_cast<long long>(n)) / (2 * static_cast<long long>(n)));
}

// Extract up to maxColors dominant swatches from raw RGBA pixels (4 bytes
// per pixel, the exact layout of ImageData.data).
std::vector<Swatch> extractPalette(const std::vector<uint8_t>& rgba, int maxColors = 8) {
    const size_t total = rgba.size() / 4;
    if (total == 0 || maxColors < 1) return {};

    // Down-sample with a stride, skipping fully transparent pixels.
    std::vector<Pixel> pixels;
    pixels.reserve(std::min<size_t>(total, kMaxSamples));
    const size_t stride = std::max<size_t>(1, total / kMaxSamples);
    for (size_t i = 0; i < total; i += stride) {
        const size_t o = i * 4;
        if (rgba[o + 3] == 0) continue;
        pixels.push_back({rgba[o], rgba[o + 1], rgba[o + 2]});
    }
    if (pixels.empty()) return {};

    // Median-cut: start from one bucket of everything, split until we have
    // maxColors buckets or no bucket has more than one distinct value.
    std::vector<std::vector<Pixel>> buckets{std::move(pixels)};
    while (buckets.size() < static_cast<size_t>(maxColors)) {
        // Widest-range bucket with more than one distinct value wins.
        size_t best = SIZE_MAX;
        int bestRange = 1; // range 1 (exact duplicates only) never splits further
        for (size_t i = 0; i < buckets.size(); i++) {
            if (const int range = channelRange(buckets[i]); range > bestRange) {
                bestRange = range;
                best = i;
            }
        }
        if (best == SIZE_MAX) break;
        std::vector<Pixel> bucket = std::move(buckets[best]);
        buckets.erase(buckets.begin() + best);
        for (auto& half : splitBucket(std::move(bucket))) buckets.push_back(std::move(half));
    }

    std::vector<Swatch> out;
    for (auto& bucket : buckets) {
        if (bucket.empty()) continue;
        long long sr = 0, sg = 0, sb = 0;
        for (const Pixel& p : bucket) {
            sr += p.r, sg += p.g, sb += p.b;
        }
        out.push_back({roundAvg(sr, bucket.size()), roundAvg(sg, bucket.size()),
                       roundAvg(sb, bucket.size()), bucket.size()});
    }
    // Population-descending, stable — mirrors the TS .sort(b - a) comparator.
    std::stable_sort(out.begin(), out.end(),
                     [](const Swatch& a, const Swatch& b) { return a.population > b.population; });
    return out;
}

// Format a swatch as #rrggbb (lowercase, always two digits per channel).
std::string toHex(const Swatch& s) {
    char buf[8];
    std::snprintf(buf, sizeof buf, "#%02x%02x%02x", s.r, s.g, s.b);
    return buf;
}

// px packs RGBA colors into a flat byte buffer, as ImageData.data lays it out.
std::vector<uint8_t> px(std::initializer_list<std::array<uint8_t, 4>> colors) {
    std::vector<uint8_t> out;
    out.reserve(colors.size() * 4);
    for (const auto& c : colors) out.insert(out.end(), c.begin(), c.end());
    return out;
}

int main() {
    // The lib's canonical vectors: three red pixels and two blue ones, then
    // a 64-step red→blue gradient capped at 6 swatches.
    for (const Swatch& s : extractPalette(px({{255, 0, 0, 255}, {255, 0, 0, 255}, {255, 0, 0, 255},
                                              {0, 0, 255, 255}, {0, 0, 255, 255}})))
        std::printf("two colors: %s x%zu\n", toHex(s).c_str(), s.population);

    std::vector<uint8_t> grad;
    for (int i = 0; i < 64; i++) {
        const uint8_t r = static_cast<uint8_t>(i * 4), b = static_cast<uint8_t>(255 - i * 4);
        grad.insert(grad.end(), {r, 128, b, 255});
    }
    std::vector<Swatch> sw = extractPalette(grad, 6);
    std::printf("gradient -> %zu swatches:\n", sw.size());
    for (const Swatch& s : sw) std::printf("  %-9s x%zu\n", toHex(s).c_str(), s.population);
    return 0;
}