distances.hpp

Go to the documentation of this file.

#ifndef KNNCOLLE_DISTANCES_HPP
#define KNNCOLLE_DISTANCES_HPP
 
#include <cmath>
#include <cstddef>
#include <string>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <memory>
#include <filesystem>
 
#include "utils.hpp"
 
namespace knncolle {
 
template<typename Data_, typename Distance_>
class DistanceMetric {
public:
    DistanceMetric() = default;
    DistanceMetric(const DistanceMetric&) = default;
    DistanceMetric(DistanceMetric&&) = default;
    DistanceMetric& operator=(const DistanceMetric&) = default;
    DistanceMetric& operator=(DistanceMetric&&) = default;
    virtual ~DistanceMetric() = default;
public:
    virtual Distance_ raw(std::size_t num_dimensions, const Data_* x, const Data_* y) const = 0;
 
    virtual Distance_ normalize(Distance_ raw) const = 0;
 
    virtual Distance_ denormalize(Distance_ norm) const = 0;
 
public:
    virtual void save([[maybe_unused]] const std::filesystem::path& dir) const {
        throw std::runtime_error("saving is not supported");
    }
};
 
inline static constexpr const char* euclidean_distance_save_name = "knncolle::Euclidean";
 
template<typename Data_, typename Distance_>
class EuclideanDistance final : public DistanceMetric<Data_, Distance_> {
public:
    Distance_ raw(std::size_t num_dimensions, const Data_* x, const Data_* y) const {
        Distance_ output = 0;
        for (std::size_t d = 0; d < num_dimensions; ++d) {
            auto delta = static_cast<Distance_>(x[d]) - static_cast<Distance_>(y[d]); // casting to ensure consistent precision/signedness regardless of Data_.
            output += delta * delta;
        }
        return output;
    }
 
    Distance_ normalize(Distance_ raw) const {
        return std::sqrt(raw);
    }
 
    Distance_ denormalize(Distance_ norm) const {
        return norm * norm;
    }
 
    void save(const std::filesystem::path& dir) const {
        quick_save(dir / "DISTANCE", euclidean_distance_save_name, std::strlen(euclidean_distance_save_name));
    }
};
 
inline static constexpr const char* manhattan_distance_save_name = "knncolle::Manhattan";
 
template<typename Data_, typename Distance_>
class ManhattanDistance final : public DistanceMetric<Data_, Distance_> {
public:
    Distance_ raw(std::size_t num_dimensions, const Data_* x, const Data_* y) const {
        Distance_ output = 0;
        for (std::size_t d = 0; d < num_dimensions; ++d) {
            auto delta = static_cast<Distance_>(x[d]) - static_cast<Distance_>(y[d]); // casting to ensure consistent precision/signedness regardless of Data_.
            output += std::abs(delta);
        }
        return output;
    }
 
    Distance_ normalize(Distance_ raw) const {
        return raw;
    }
 
    Distance_ denormalize(Distance_ norm) const {
        return norm;
    }
 
    void save(const std::filesystem::path& dir) const {
        quick_save(dir / "DISTANCE", manhattan_distance_save_name, std::strlen(manhattan_distance_save_name));
    }
};
 
template<typename Data_, typename Distance_>
using LoadDistanceMetricFunction = std::function<DistanceMetric<Data_, Distance_>* (const std::filesystem::path&)>;
 
 
template<typename Data_, typename Distance_>
inline std::unordered_map<std::string, LoadDistanceMetricFunction<Data_, Distance_> >& load_distance_metric_registry() {
    static std::unordered_map<std::string, LoadDistanceMetricFunction<Data_, Distance_> > registry; 
    return registry;
}
 
template<typename Data_, typename Distance_>
void register_load_euclidean_distance() {
    auto& reg = load_distance_metric_registry<Data_, Distance_>();
    reg[euclidean_distance_save_name] = [](const std::filesystem::path&) -> DistanceMetric<Data_, Distance_>* { return new EuclideanDistance<Data_, Distance_>; };
}
 
template<typename Data_, typename Distance_>
void register_load_manhattan_distance() {
    auto& reg = load_distance_metric_registry<Data_, Distance_>();
    reg[manhattan_distance_save_name] = [](const std::filesystem::path&) -> DistanceMetric<Data_, Distance_>* { return new ManhattanDistance<Data_, Distance_>; };
}
 
class LoadDistanceMetricNotFoundError final : public std::runtime_error {
public:
    LoadDistanceMetricNotFoundError(std::string distance, std::filesystem::path path) : 
        std::runtime_error("cannot find a load_distance_metric_registry() function for '" + distance + "' at '" + path.string() + "'"),
        my_distance(std::move(distance)),
        my_path(std::move(path))
    {}
private:
    std::string my_distance;
    std::filesystem::path my_path;
 
public:
    const std::string& get_distance() const {
        return my_distance;
    }
 
    const std::filesystem::path& get_path() const {
        return my_path;
    }
};
 
template<typename Data_, typename Distance_>
DistanceMetric<Data_, Distance_>* load_distance_metric_raw(const std::filesystem::path& dir) {
    const auto metric_path =  dir / "DISTANCE";
    const auto metric_name = quick_load_as_string(metric_path);
 
    const auto& reg = load_distance_metric_registry<Data_, Distance_>(); 
    auto it = reg.find(metric_name);
    if (it == reg.end()) {
        throw LoadDistanceMetricNotFoundError(metric_name, metric_path);
    }
 
    return (it->second)(dir);
}
 
}
 
#endif