Utils.h

/**************************************************************************
 * basf2 (Belle II Analysis Software Framework)                           *
 * Author: The Belle II Collaboration                                     *
 *                                                                        *
 * See git log for contributors and copyright holders.                    *
 * This file is licensed under LGPL-3.0, see LICENSE.md.                  *
 **************************************************************************/
#pragma once
 
#include <Math/Vector3D.h>
 
#include <cstddef>
#include <vector>
 
namespace Belle2::GNNFinder::Utils {

  typedef struct KDTHit {
    double x;
    double y;
    int hitIndex;
    double squaredDistanceTo(const KDTHit& other) const
    {
      double dx = x - other.x;
      double dy = y - other.y;
      return dx * dx + dy * dy;
    }
  } KDTHit;

  typedef struct KDTNode {
    KDTHit hit;
    KDTNode* left;
    KDTNode* right;
    bool used;
    int dim;
  } KDTNode;

  class KDTNodePool {
  private:
    std::vector<KDTNode*> m_pool;
    size_t m_index;
 
  public:
    explicit KDTNodePool(size_t capacity);

    ~KDTNodePool();

    KDTNodePool(const KDTNodePool&) = delete;

    KDTNodePool& operator=(const KDTNodePool&) = delete;

    KDTNode* allocate();

    void reset();
 
  };

  class HitOrderer {
 
  private:
    static KDTNode* buildKDTree(std::vector<KDTHit>::iterator begin, std::vector<KDTHit>::iterator end, const int depth,
                                KDTNodePool& pool, const size_t insertionSortThreshold = 10);

    template<typename Iterator, typename Compare>
    static inline void insertionSort(Iterator begin, Iterator end, Compare cmp);

    static void freeKDTree(KDTNode* node);

    static void nearestNeighbor(const KDTNode* node, const KDTHit& query, KDTHit& best, double& bestDist);

    static bool markUsed(KDTNode* node, const KDTHit& hit);
 
 
  public:
    static std::vector<int> orderHits(const double startingX, const double startingY,
                                      std::vector<KDTHit> kdtHits);

    HitOrderer() = default;

    ~HitOrderer() = default;
  };

  std::pair<double, double> intersectCylinderXY(const ROOT::Math::XYZVector& pos,
                                                const ROOT::Math::XYZVector& mom,
                                                const double targetR);
 
}