remove_unused_centers.hpp

Go to the documentation of this file.

#ifndef KMEANS_REMOVE_UNUSED_CENTERS_HPP
#define KMEANS_REMOVE_UNUSED_CENTERS_HPP
 
#include <vector>
#include <cstddef>
#include <algorithm>
 
#include "sanisizer/sanisizer.hpp"
 
#include "utils.hpp"
 
namespace kmeans {
 
template<typename Index_, typename Cluster_, typename Float_>
Cluster_ remove_unused_centers(
    const std::size_t num_dimensions,
    const Index_ num_observations,
    Cluster_* const clusters,
    const Cluster_ num_centers,
    Float_* const centers,
    std::vector<Index_>& sizes
) {
    bool has_zero = false;
    for (Cluster_ c = 0; c < num_centers; ++c) {
        if (sizes[c] == 0) {
            has_zero = true;
            break;
        }
    }
    if (!has_zero) {
        return num_centers;
    }
 
    auto remapping = sanisizer::create<std::vector<Index_> >(num_centers);
    Cluster_ remaining = 0;
    for (Cluster_ c = 0; c < num_centers; ++c) {
        if (sizes[c]) {
            remapping[c] = remaining;
            if (remaining != c) {
                std::copy_n(
                    centers + sanisizer::product_unsafe<std::size_t>(c, num_dimensions),
                    num_dimensions,
                    centers + sanisizer::product_unsafe<std::size_t>(remaining, num_dimensions)
                );
                sizes[remaining] = sizes[c];
            }
            ++remaining;
        }
    }
 
    // Zeroing the leftovers, just in case.
    std::fill(sizes.begin() + remaining, sizes.end(), 0);
    std::fill(
        centers + sanisizer::product_unsafe<std::size_t>(remaining, num_dimensions),
        centers + sanisizer::product_unsafe<std::size_t>(num_centers, num_dimensions),
        0
    );
 
    for (Index_ o = 0; o < num_observations; ++o) {
        clusters[o] = remapping[clusters[o]];
    }
 
    return remaining;
}
 
}
 
#endif