Program Listing for File CoverTree.hpp

↰ Return to documentation for file (include\DimRedTools\CoverTree.hpp)

#ifndef DIMREDTOOLS_INCLUDE_DIMREDTOOLS_COVERTREE_HPP_
#define DIMREDTOOLS_INCLUDE_DIMREDTOOLS_COVERTREE_HPP_

#include "DimRedTools.hpp"
#include <cfloat>

namespace dim_red {

class CoverTree : public NearestNeighbors {
public:
    CoverTree(const Eigen::Ref<const Matrix> &x, double base = 1.3,
              const std::string &metric = "euclidean");

    ~CoverTree();

    std::pair<Vector, IntVector> query(const Eigen::Ref<const Vector> &point, int k,
                                       bool sort_results = true) const override;

    std::pair<Vector, IntVector> queryRadius(const Eigen::Ref<const Vector> &point, double radius,
                                             bool sort_results = false) const override;

private:
    struct Node {
        const int point;
        const double max_distance = 0.0;
        const std::vector<Node *> *const children = nullptr;

        Node(const Node &) = delete;
    };

    struct DistanceSet {
        const int point;
        std::vector<double> distances;

        DistanceSet(const DistanceSet &) = delete;
    };

    struct DistanceNode {
        const double distance;
        const Node *node;
    };

    void deleteNode(Node *node) const;

    Node *build();

    Node *batchInsert(int point, int max_scale, int top_scale,
                      std::vector<DistanceSet *> *point_set,
                      std::vector<DistanceSet *> *consumed_set) const;

    double getCoverRadius(int scale) const;

    int getScale(double value) const;

    double maxDistance(const std::vector<DistanceSet *> &v) const;

    void split(int max_scale, std::vector<DistanceSet *> *point_set,
               std::vector<DistanceSet *> *far_set) const;

    void distanceSplit(int new_point, int max_scale, std::vector<DistanceSet *> *point_set,
                       std::vector<DistanceSet *> *new_point_set) const;

    std::pair<Vector, IntVector> search(const Eigen::Ref<const Vector> &point, int k, double radius,
                                        bool k_nearest, bool sort_results) const;

    const Eigen::Ref<const Matrix> data_;
    Metric distance_;
    double base_;
    double inv_log_base_;
    Node *root_;
};

}  // namespace dim_red

#endif  // DIMREDTOOLS_INCLUDE_DIMREDTOOLS_COVERTREE_HPP_