corecel/cont/LabelIdMultiMap.hh

0001 //----------------------------------*-C++-*----------------------------------//
0002 // Copyright 2022-2024 UT-Battelle, LLC, and other Celeritas developers.
0003 // See the top-level COPYRIGHT file for details.
0004 // SPDX-License-Identifier: (Apache-2.0 OR MIT)
0005 //---------------------------------------------------------------------------//
0006 //! \file corecel/cont/LabelIdMultiMap.hh
0007 //---------------------------------------------------------------------------//
0008 #pragma once
0009
0010 #include <algorithm>
0011 #include <string>
0012 #include <unordered_map>
0013 #include <vector>
0014
0015 #include "corecel/Assert.hh"
0016 #include "corecel/io/Label.hh"
0017
0018 #include "Range.hh"
0019 #include "Span.hh"
0020
0021 namespace celeritas
0022 {
0023 //---------------------------------------------------------------------------//
0024 /*!
0025  * Map IDs to label+sublabel.
0026  *
0027  * Many Geant4 geometry definitions reuse a label for material or volume
0028  * definitions, and we need to track the unique name across multiple codes
0029  * (Geant4, VecGeom+GDML) to differentiate between materials or volumes. This
0030  * class maps a "label" to a range of "sublabels", each of which corresponds to
0031  * a unique ID. It also provides the reverse mapping so that an ID can retrieve
0032  * the corresponding label/sublabel pair.
0033  *
0034  * There is no requirement that sublabels be ordered adjacent to each other:
0035  * the IDs corresponding to a label may be noncontiguous.
0036  *
0037  * Duplicate labels are allowed but will be added to a list of duplicate IDs
0038  * that can be warned about downstream. Empty labels will be ignored.
0039  *
0040  * If no sublabels or labels are available, an empty span or "false" OpaqueId
0041  * will be returned.
0042  */
0043 template<class I>
0044 class LabelIdMultiMap
0045 {
0046   public:
0047     //!@{
0048     //! \name Type aliases
0049     using IdT = I;
0050     using SpanConstIdT = Span<IdT const>;
0051     using VecLabel = std::vector<Label>;
0052     using size_type = typename IdT::size_type;
0053     //!@}
0054
0055   public:
0056     // Empty constructor for delayed build
0057     LabelIdMultiMap() = default;
0058
0059     // Construct from a vector of label+sublabel pairs
0060     explicit LabelIdMultiMap(VecLabel keys);
0061
0062     // Access the range of IDs corresponding to a label
0063     inline SpanConstIdT find_all(std::string const& label) const;
0064
0065     // Access an ID by label/sublabel pair
0066     inline IdT find(Label const& label_sub) const;
0067
0068     // Access the label+sublabel pair for an Id
0069     inline Label const& get(IdT id) const;
0070
0071     //! Get duplicate labels to warn about
0072     SpanConstIdT duplicates() const { return make_span(duplicates_); }
0073
0074     //! Get the number of elements
0075     size_type size() const { return keys_.size(); }
0076
0077   private:
0078     VecLabel keys_;
0079     std::vector<IdT> id_data_;
0080     std::vector<size_type> id_offsets_;
0081     std::vector<IdT> duplicates_;
0082     std::unordered_map<std::string, size_type> ids_;
0083 };
0084
0085 //---------------------------------------------------------------------------//
0086 // INLINE DEFINITIONS
0087 //---------------------------------------------------------------------------//
0088 /*!
0089  * Construct with defaults.
0090  */
0091 template<class I>
0092 LabelIdMultiMap<I>::LabelIdMultiMap(VecLabel keys) : keys_(std::move(keys))
0093 {
0094     if (keys_.empty())
0095     {
0096         // Sometimes we don't have any items to map. Rely on the
0097         // default-constructed values.
0098         return;
0099     }
0100
0101     // Build list of IDs corresponding to each key
0102     id_data_.resize(keys_.size());
0103     for (auto idx : range<size_type>(keys_.size()))
0104     {
0105         id_data_[idx] = IdT{idx};
0106     }
0107     // Reorder consecutive ID data based on string lexicographic ordering
0108     std::sort(id_data_.begin(), id_data_.end(), [this](IdT a, IdT b) {
0109         return this->keys_[a.unchecked_get()] < this->keys_[b.unchecked_get()];
0110     });
0111
0112     // Reserve space for groups
0113     id_offsets_.reserve(keys_.size() / 2 + 2);
0114     ids_.reserve(id_offsets_.capacity());
0115
0116     // Search for when the label changes
0117     id_offsets_.push_back(0);
0118     ids_.insert({keys_[id_data_[0].unchecked_get()].name, 0});
0119     for (auto idx : range<size_type>(1, id_data_.size()))
0120     {
0121         Label const& prev = keys_[id_data_[idx - 1].unchecked_get()];
0122         Label const& cur = keys_[id_data_[idx].unchecked_get()];
0123         if (prev == cur && !cur.empty())
0124         {
0125             if (duplicates_.empty()
0126                 || keys_[duplicates_.back().unchecked_get()] != prev)
0127             {
0128                 // Push back previous entry if it's not already there
0129                 duplicates_.push_back(id_data_[idx - 1]);
0130             }
0131             duplicates_.push_back(id_data_[idx]);
0132         }
0133         if (prev.name != cur.name)
0134         {
0135             // Add start index of the new name
0136             size_type offset_idx = id_offsets_.size();
0137             id_offsets_.push_back(idx);
0138             auto insert_ok = ids_.insert({cur.name, offset_idx});
0139             CELER_ASSERT(insert_ok.second);
0140         }
0141     }
0142     id_offsets_.push_back(id_data_.size());
0143
0144     CELER_ENSURE(keys_.size() == id_data_.size());
0145     CELER_ENSURE(id_offsets_.size() == ids_.size() + 1);
0146 }
0147
0148 //---------------------------------------------------------------------------//
0149 /*!
0150  * Access the range of IDs corresponding to a label.
0151  */
0152 template<class I>
0153 auto LabelIdMultiMap<I>::find_all(std::string const& name) const -> SpanConstIdT
0154 {
0155     auto iter = ids_.find(name);
0156     if (iter == ids_.end())
0157         return {};
0158
0159     size_type offset_idx = iter->second;
0160     CELER_ASSERT(offset_idx + 1 < id_offsets_.size());
0161     size_type start = id_offsets_[offset_idx];
0162     size_type stop = id_offsets_[offset_idx + 1];
0163     CELER_ENSURE(start < stop && stop <= id_data_.size());
0164     return {id_data_.data() + start, stop - start};
0165 }
0166
0167 //---------------------------------------------------------------------------//
0168 /*!
0169  * Access an ID by label/sublabel pair.
0170  *
0171  * This returns a \c false OpaqueId if no such label pair exists.
0172  */
0173 template<class I>
0174 auto LabelIdMultiMap<I>::find(Label const& label_sub) const -> IdT
0175 {
0176     auto items = this->find_all(label_sub.name);
0177
0178     // Just do a linear search on sublabels
0179     auto iter
0180         = std::find_if(items.begin(), items.end(), [this, &label_sub](IdT id) {
0181               CELER_EXPECT(id < this->keys_.size());
0182               return this->keys_[id.unchecked_get()].ext == label_sub.ext;
0183           });
0184     if (iter == items.end())
0185     {
0186         // No sublabel matches
0187         return {};
0188     }
0189     CELER_ENSURE(keys_[iter->unchecked_get()] == label_sub);
0190     return *iter;
0191 }
0192
0193 //---------------------------------------------------------------------------//
0194 /*!
0195  * Access the label+sublabel pair for an Id.
0196  *
0197  * This raises an exception if the ID is outside of the valid range.
0198  */
0199 template<class I>
0200 Label const& LabelIdMultiMap<I>::get(IdT id) const
0201 {
0202     CELER_EXPECT(id < this->size());
0203     return keys_[id.unchecked_get()];
0204 }
0205
0206 //---------------------------------------------------------------------------//
0207 }  // namespace celeritas