src/TrackFinding/SeedDeduplicator.cpp

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 #include "Acts/TrackFinding/SeedDeduplicator.hpp"
0010
0011 #include <algorithm>
0012 #include <stdexcept>
0013
0014 #include <boost/container/small_vector.hpp>
0015
0016 namespace Acts {
0017
0018 SeedDeduplicator::SeedDeduplicator(const Config& config) : m_cfg(config) {}
0019
0020 void SeedDeduplicator::reset(std::size_t nMeasKeys) {
0021   if (nMeasKeys >= kNone) {
0022     throw std::invalid_argument("SeedDeduplicator: too many keys");
0023   }
0024   m_trackHeads.assign(nMeasKeys, kNone);
0025   m_weights.assign(nMeasKeys, 1);
0026   m_nodes.clear();
0027   m_nTracks = 0;
0028 }
0029
0030 SeedDeduplicator::Score SeedDeduplicator::duplicateThreshold(
0031     Score seedScore) const {
0032   const Score relative =
0033       seedScore > m_cfg.maxMissingScore ? seedScore - m_cfg.maxMissingScore : 0;
0034   return std::min(seedScore, std::max({Score{1}, m_cfg.minScore, relative}));
0035 }
0036
0037 void SeedDeduplicator::addTrack(std::span<const MeasurementKey> measKeys) {
0038   const auto track = static_cast<std::uint32_t>(m_nTracks);
0039   for (const MeasurementKey measKey : measKeys) {
0040     assert(measKey < m_trackHeads.size() && "Key out of range");
0041     const std::uint32_t head = m_trackHeads[measKey];
0042     // a key that occurs twice on a track counts once
0043     if (head != kNone && m_nodes[head].track == track) {
0044       continue;
0045     }
0046     m_trackHeads[measKey] = static_cast<std::uint32_t>(m_nodes.size());
0047     m_nodes.push_back({track, head});
0048   }
0049   ++m_nTracks;
0050 }
0051
0052 bool SeedDeduplicator::isDuplicate(
0053     std::span<const MeasurementKey> measKeys) const {
0054   Score seedScore = 0;
0055   for (const MeasurementKey measKey : measKeys) {
0056     seedScore += weight(measKey);
0057   }
0058   if (seedScore == 0) {
0059     return false;
0060   }
0061   const Score threshold = duplicateThreshold(seedScore);
0062
0063   // the score that each track shares with the seed, for each track which holds
0064   // at least one seed key
0065   struct TrackScore {
0066     std::uint32_t track;
0067     Score sharedScore;
0068   };
0069   boost::container::small_vector<TrackScore, kInlineTracks> scores;
0070   Score bestSharedScore = 0;
0071   Score remaining = seedScore;
0072   for (const MeasurementKey measKey : measKeys) {
0073     const Weight w = weight(measKey);
0074     for (std::uint32_t node = m_trackHeads[measKey]; node != kNone;
0075          node = m_nodes[node].next) {
0076       const std::uint32_t track = m_nodes[node].track;
0077       auto it = std::ranges::find(scores, track, &TrackScore::track);
0078       if (it == scores.end()) {
0079         it = scores.insert(scores.end(), {track, 0});
0080       }
0081       it->sharedScore += w;
0082       if (it->sharedScore >= threshold) {
0083         return true;
0084       }
0085       bestSharedScore = std::max(bestSharedScore, it->sharedScore);
0086     }
0087     remaining -= w;
0088     // no track can reach the threshold with the keys that are left. This
0089     // check runs after each seed key, so it also stops the loop early for a
0090     // seed whose first keys no track holds.
0091     if (bestSharedScore + remaining < threshold) {
0092       return false;
0093     }
0094   }
0095   return false;
0096 }
0097
0098 }  // namespace Acts