Acts/TrackFinding/SeedDeduplicator.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 <cassert>
0012 #include <cstddef>
0013 #include <cstdint>
0014 #include <limits>
0015 #include <span>
0016 #include <vector>
0017
0018 namespace Acts {
0019
0020 /// @brief Flags seeds whose measurements one accepted track already holds
0021 ///
0022 /// Measurements are dense keys in `[0, nMeasKeys)`. The caller chooses which
0023 /// keys a seed contributes. The keys are plain indices and not `SourceLink`s,
0024 /// because a `SourceLink` has no hash and no equality comparison.
0025 ///
0026 /// Each key has a weight, 1 by default. The weight can for example be the
0027 /// number of measured local coordinates, so that a pixel measurement counts 2
0028 /// and a strip measurement counts 1. A seed with the summed weight `seedScore`
0029 /// is a duplicate if one track holds keys of the summed weight
0030 ///
0031 ///   `min(seedScore, max(1, minScore, seedScore - maxMissingScore))`.
0032 ///
0033 /// The scores of different tracks do not add up. Seeds can be queried in any
0034 /// order.
0035 class SeedDeduplicator {
0036  public:
0037   /// Type of the dense measurement key
0038   using MeasurementKey = std::uint32_t;
0039   /// Type of the weight of a key
0040   using Weight = std::uint8_t;
0041   /// Type of a summed weight
0042   using Score = std::uint32_t;
0043
0044   /// Configuration of the duplicate threshold
0045   ///
0046   /// The default requires every key. A cut on `minScore` alone needs
0047   /// `maxMissingScore` at its maximum.
0048   struct Config {
0049     /// Minimum shared score that makes a seed a duplicate
0050     Score minScore = 0;
0051     /// Maximum score of the seed that the track may miss
0052     Score maxMissingScore = 0;
0053   };
0054
0055   /// Constructor
0056   /// @param config The threshold configuration
0057   explicit SeedDeduplicator(const Config& config);
0058
0059   /// Remove all tracks and set the key range. Every weight becomes 1.
0060   /// @param nMeasKeys The number of measurement keys, every key must be below
0061   ///                  this number
0062   void reset(std::size_t nMeasKeys);
0063
0064   /// @return The number of accepted tracks
0065   std::size_t nTracks() const { return m_nTracks; }
0066
0067   /// Set the weight of a key
0068   /// @param measKey The measurement key
0069   /// @param weight The weight of the key
0070   void setWeight(MeasurementKey measKey, Weight weight) {
0071     assert(measKey < m_weights.size() && "Key out of range");
0072     m_weights[measKey] = weight;
0073   }
0074
0075   /// @param measKey The measurement key
0076   /// @return The weight of the key
0077   Weight weight(MeasurementKey measKey) const {
0078     assert(measKey < m_weights.size() && "Key out of range");
0079     return m_weights[measKey];
0080   }
0081
0082   /// Accept a track
0083   /// @param measKeys The keys of the measurements on the track
0084   void addTrack(std::span<const MeasurementKey> measKeys);
0085
0086   /// Check if one accepted track holds enough of the seed keys
0087   /// @param measKeys The keys of the seed, each key at most once
0088   /// @return True if the seed is a duplicate
0089   bool isDuplicate(std::span<const MeasurementKey> measKeys) const;
0090
0091  private:
0092   static constexpr std::uint32_t kNone =
0093       std::numeric_limits<std::uint32_t>::max();
0094   /// Number of tracks per seed query that need no heap allocation. This value
0095   /// is not tuned. A query with more tracks moves the list to the heap and
0096   /// gives the same result.
0097   static constexpr std::size_t kInlineTracks = 8;
0098
0099   /// @param seedScore The summed weight of the seed keys
0100   /// @return The score that one track must share with the seed to make the
0101   ///         seed a duplicate
0102   Score duplicateThreshold(Score seedScore) const;
0103
0104   /// One accepted track on one key
0105   struct Node {
0106     /// The index of the track
0107     std::uint32_t track;
0108     /// The next node of the same key, or `kNone`
0109     std::uint32_t next;
0110   };
0111
0112   Config m_cfg;
0113
0114   /// The latest node for each key, or `kNone`
0115   std::vector<std::uint32_t> m_trackHeads;
0116   std::vector<Weight> m_weights;
0117   std::vector<Node> m_nodes;
0118   std::size_t m_nTracks = 0;
0119 };
0120
0121 }  // namespace Acts