algorithms/meta/SortSubsetCollection.h

0001 // SPDX-License-Identifier: LGPL-3.0-or-later
0002 // Copyright (C) 2026, ePIC Collaboration
0003
0004 #pragma once
0005
0006 #include <algorithms/algorithm.h>
0007 #include <algorithm>
0008 #include <functional>
0009 #include <numeric>
0010 #include <podio/ObjectID.h>
0011 #include <string_view>
0012 #include <type_traits>
0013 #include <utility>
0014 #include <vector>
0015
0016 #include "algorithms/interfaces/WithPodConfig.h"
0017 #include "services/log/Log_service.h"
0018
0019 namespace eicrecon {
0020
0021 template <class T>
0022 using SortSubsetCollectionAlgorithm =
0023     algorithms::Algorithm<typename algorithms::Input<const typename T::collection_type>,
0024                           typename algorithms::Output<typename T::collection_type>>;
0025
0026 template <class T, class AccessorFunctionT>
0027 class SortSubsetCollection : public SortSubsetCollectionAlgorithm<T>,
0028                              public WithPodConfig<NoConfig> {
0029
0030 public:
0031   SortSubsetCollection(std::string_view name, AccessorFunctionT accessor)
0032       : SortSubsetCollectionAlgorithm<T>{name,
0033                                          {"inputCollection"},
0034                                          {"outputCollection"},
0035                                          "Sort collection into a subset output collection"}
0036       , m_accessor(std::move(accessor)) {}
0037
0038   void init() final {};
0039
0040   void process(const typename SortSubsetCollectionAlgorithm<T>::Input& input,
0041                const typename SortSubsetCollectionAlgorithm<T>::Output& output) const final {
0042     const auto [input_collection] = input;
0043     auto [output_collection]      = output;
0044
0045     output_collection->setSubsetCollection();
0046
0047     const std::size_t n = input_collection->size();
0048
0049     // Pre-calculate sort keys once per entry to avoid O(N log N) accessor invocations
0050     using KeyT = std::decay_t<std::invoke_result_t<AccessorFunctionT, T>>;
0051     std::vector<KeyT> keys;
0052     keys.reserve(n);
0053     for (std::size_t i = 0; i < n; ++i) {
0054       keys.push_back(std::invoke(m_accessor, (*input_collection)[i]));
0055     }
0056
0057     // Obtain sorted permutation of indices using pre-calculated keys
0058     std::vector<std::size_t> indices(n);
0059     std::iota(indices.begin(), indices.end(), 0);
0060     std::sort(indices.begin(), indices.end(), [&](std::size_t i, std::size_t j) {
0061       if (keys[i] < keys[j]) {
0062         return true;
0063       }
0064       if (keys[j] < keys[i]) {
0065         return false;
0066       }
0067       const auto id_i = (*input_collection)[i].getObjectID();
0068       const auto id_j = (*input_collection)[j].getObjectID();
0069       if (id_i.collectionID < id_j.collectionID) {
0070         return true;
0071       }
0072       if (id_j.collectionID < id_i.collectionID) {
0073         return false;
0074       }
0075       return id_i.index < id_j.index;
0076     });
0077
0078     for (std::size_t i : indices) {
0079       output_collection->push_back((*input_collection)[i]);
0080     }
0081   };
0082
0083 private:
0084   AccessorFunctionT m_accessor;
0085 };
0086
0087 } // namespace eicrecon