Acts/Seeding/Neighbour.hpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 #include "Acts/Utilities/Grid.hpp"
0012
0013 namespace Acts {
0014
0015 /// @brief A class that helps in processing the neighbours, given a collection of
0016 /// middle space points
0017 /// The idea here is that in the seeding we look for compatible b-m and m-t
0018 /// doublets. One of the requirements is that the bottom/top space point is at a
0019 /// suitable distance (in radius) w.r.t. the middle space point. We know however
0020 /// that the space points in each bin are sorted in radius. That means we can
0021 /// use this sorting in order to reduce the number of space point to consider
0022 /// when looking for compatible doublets.
0023 /// The idea is to keep track of first space point that is in the allowed bin,
0024 /// by storing its position using an iterator itr This helps us since the lower
0025 /// possible buondary is given by the first middle space point (its radius minus
0026 /// the mad deltaR defined by the user). The subsequent middle space point will
0027 /// have a higher radius. That means that there is no point in looking at
0028 /// neighbour space point before itr, since we know they will be out of range.
0029
0030 template <typename grid_t>
0031 struct Neighbour {
0032   /// @brief default constructor
0033   Neighbour() = delete;
0034
0035   /// @brief Constructor
0036   /// @param grid The grid containing the space points
0037   /// @param idx The global index of the bin in the grid
0038   /// @param lowerBound The lower bound of the allowed space point
0039   Neighbour(const grid_t& grid, std::size_t idx, const float lowerBound);
0040
0041   /// The global bin index on the grid
0042   std::size_t index;
0043   /// The iterator containing the position of the first space point in the valid
0044   /// radius range
0045   typename grid_t::value_type::const_iterator itr;
0046 };
0047
0048 template <typename grid_t>
0049 Neighbour<grid_t>::Neighbour(const grid_t& grid, std::size_t idx,
0050                              const float lowerBound)
0051     : index(idx) {
0052   /// Get the space points in this specific global bin
0053   const auto& collection = grid.at(idx);
0054   /// If there are no elements in the bin, we simply set the iterator to begin()
0055   /// and return. In this case begin() == end() so we run on nothing
0056   if (collection.size() == 0) {
0057     itr = collection.begin();
0058     return;
0059   }
0060
0061   /// First check that the first element is not already above the lower bound
0062   /// If so, avoid any computation and set the iterator to begin()
0063   if (collection.front()->radius() > lowerBound) {
0064     itr = collection.begin();
0065   }
0066   /// In case the last element is below the lower bound, that means that there
0067   /// can't be any element in that collection that can be considered a valuable
0068   /// candidate.
0069   /// Set the iterator to end() so that we do not run on this collection
0070   else if (collection.back()->radius() < lowerBound) {
0071     itr = collection.end();
0072   }
0073   /// Cannot decide a priori. We need to find the first element such that it's
0074   /// radius is > lower bound. We use a binary search in this case
0075   else {
0076     // custom binary search which was observed to be faster than
0077     // `std::lower_bound` see https://github.com/acts-project/acts/pull/3095
0078     std::size_t start = 0ul;
0079     std::size_t stop = collection.size() - 1;
0080     while (start <= stop) {
0081       std::size_t mid = (start + stop) / 2;
0082       if (collection[mid]->radius() == lowerBound) {
0083         itr = collection.begin() + mid;
0084         return;
0085       } else if (collection[mid]->radius() > lowerBound) {
0086         if (mid > 0 && collection[mid - 1]->radius() < lowerBound) {
0087           itr = collection.begin() + mid;
0088           return;
0089         }
0090         stop = mid - 1;
0091       } else {
0092         if (mid + 1 < collection.size() &&
0093             collection[mid + 1]->radius() > lowerBound) {
0094           itr = collection.begin() + mid + 1;
0095           return;
0096         }
0097         start = mid + 1;
0098       }
0099     }  // while loop
0100   }
0101 }
0102
0103 }  // namespace Acts