corecel/cont/LabelIdMultiMap.hh

0001 //------------------------------- -*- C++ -*- -------------------------------//
0002 // Copyright Celeritas contributors: see top-level COPYRIGHT file for details
0003 // SPDX-License-Identifier: (Apache-2.0 OR MIT)
0004 //---------------------------------------------------------------------------//
0005 //! \file corecel/cont/LabelIdMultiMap.hh
0006 //---------------------------------------------------------------------------//
0007 #pragma once
0008
0009 #include <algorithm>
0010 #include <string>
0011 #include <unordered_map>
0012 #include <vector>
0013
0014 #include "corecel/Assert.hh"
0015 #include "corecel/io/Label.hh"
0016
0017 #include "Range.hh"
0018 #include "Span.hh"
0019
0020 namespace celeritas
0021 {
0022 //---------------------------------------------------------------------------//
0023 /*!
0024  * Map IDs to label+sublabel.
0025  *
0026  * Many Geant4 geometry definitions reuse a label for material or volume
0027  * definitions, and we need to track the unique name across multiple codes
0028  * (Geant4, VecGeom+GDML) to differentiate between materials or volumes. This
0029  * class maps a "label" to a name plus a range of "extensions", each of which
0030  * corresponds to a unique ID. It also provides the reverse mapping so that an
0031  * ID can retrieve the corresponding name/extension pair.
0032  *
0033  * There is no requirement that sublabels be ordered adjacent to each other:
0034  * the IDs corresponding to a label may be noncontiguous.
0035  *
0036  * Duplicate labels are allowed but will be added to a list of duplicate IDs
0037  * that can be warned about downstream. Empty labels will be ignored.
0038  *
0039  * If no sublabels or labels are available for a \c find_X call, an empty span
0040  * or "false" OpaqueId will be returned.
0041  *
0042  * The three kinds of \c find methods are named differently to avoid ambiguity:
0043  * - \c find_all returns the full set of IDs that match the given name;
0044  * - \c find_unique is a convenience accessor for locating a volume by name,
0045  *   but it only works if there are no duplicates; and
0046  * - \c find_exact looks for the full label, both name and extension.
0047  */
0048 template<class I>
0049 class LabelIdMultiMap
0050 {
0051   public:
0052     //!@{
0053     //! \name Type aliases
0054     using IdT = I;
0055     using SpanConstIdT = Span<IdT const>;
0056     using VecLabel = std::vector<Label>;
0057     using size_type = typename IdT::size_type;
0058     //!@}
0059
0060   public:
0061     // Empty constructor for delayed build
0062     LabelIdMultiMap() = default;
0063
0064     // Construct from a vector of label+sublabel pairs, with a type string
0065     inline LabelIdMultiMap(std::string&& label, VecLabel&& keys);
0066
0067     // Construct from a vector of label+sublabel pairs, with no type
0068     inline explicit LabelIdMultiMap(VecLabel&& keys);
0069
0070     // Access the range of IDs corresponding to a name
0071     inline SpanConstIdT find_all(std::string const& name) const;
0072
0073     // Find an ID by name, throwing if not unique
0074     inline IdT find_unique(std::string const& name) const;
0075
0076     // Access an ID by name/extension pair
0077     inline IdT find_exact(Label const& label) const;
0078
0079     // Access the label+sublabel pair for an Id
0080     inline Label const& at(IdT id) const;
0081
0082     //! Get the number of elements
0083     CELER_FORCEINLINE size_type size() const { return keys_.size(); }
0084
0085     // Whether this map is initialized
0086     inline explicit operator bool() const;
0087
0088     //! Get duplicate labels to warn about
0089     SpanConstIdT duplicates() const { return make_span(duplicates_); }
0090
0091   private:
0092     std::string type_label_;
0093     VecLabel keys_;
0094     std::vector<IdT> id_data_;
0095     std::vector<size_type> id_offsets_;
0096     std::vector<IdT> duplicates_;
0097     std::unordered_map<std::string, size_type> ids_;
0098 };
0099
0100 //---------------------------------------------------------------------------//
0101 // INLINE DEFINITIONS
0102 //---------------------------------------------------------------------------//
0103 /*!
0104  * Construct from a vector of label+sublabel pairs, with no type.
0105  */
0106 template<class I>
0107 LabelIdMultiMap<I>::LabelIdMultiMap(VecLabel&& keys)
0108     : LabelIdMultiMap{{}, std::move(keys)}
0109 {
0110 }
0111
0112 //---------------------------------------------------------------------------//
0113 /*!
0114  * Construct from a vector of label+sublabel pairs, with a type string.
0115  */
0116 template<class I>
0117 LabelIdMultiMap<I>::LabelIdMultiMap(std::string&& label, VecLabel&& keys)
0118     : type_label_{std::move(label)}, keys_{std::move(keys)}
0119 {
0120     if (keys_.empty())
0121     {
0122         // Sometimes we don't have any items to map. Rely on the
0123         // default-constructed values.
0124         return;
0125     }
0126
0127     // Build list of IDs corresponding to each key
0128     id_data_.resize(keys_.size());
0129     for (auto idx : range<size_type>(keys_.size()))
0130     {
0131         id_data_[idx] = IdT{idx};
0132     }
0133     // Reorder consecutive ID data based on string lexicographic ordering
0134     std::sort(id_data_.begin(), id_data_.end(), [&keys = keys_](IdT a, IdT b) {
0135         return keys[a.unchecked_get()] < keys[b.unchecked_get()];
0136     });
0137
0138     // Reserve space for groups
0139     id_offsets_.reserve(keys_.size() / 2 + 2);
0140     ids_.reserve(id_offsets_.capacity());
0141
0142     // Search for when the label changes
0143     id_offsets_.push_back(0);
0144     ids_.insert({keys_[id_data_[0].unchecked_get()].name, 0});
0145     for (auto idx : range<size_type>(1, id_data_.size()))
0146     {
0147         Label const& prev = keys_[id_data_[idx - 1].unchecked_get()];
0148         Label const& cur = keys_[id_data_[idx].unchecked_get()];
0149         if (prev == cur && !cur.empty())
0150         {
0151             if (duplicates_.empty()
0152                 || keys_[duplicates_.back().unchecked_get()] != prev)
0153             {
0154                 // Push back previous entry if it's not already there
0155                 duplicates_.push_back(id_data_[idx - 1]);
0156             }
0157             duplicates_.push_back(id_data_[idx]);
0158         }
0159         if (prev.name != cur.name)
0160         {
0161             // Add start index of the new name
0162             size_type offset_idx = id_offsets_.size();
0163             id_offsets_.push_back(idx);
0164             auto insert_ok = ids_.insert({cur.name, offset_idx});
0165             CELER_ASSERT(insert_ok.second);
0166         }
0167     }
0168     id_offsets_.push_back(id_data_.size());
0169
0170     CELER_ENSURE(keys_.size() == id_data_.size());
0171     CELER_ENSURE(id_offsets_.size() == ids_.size() + 1);
0172 }
0173
0174 //---------------------------------------------------------------------------//
0175 /*!
0176  * Access the range of IDs corresponding to a label.
0177  *
0178  * This is useful for identifiers that may be repeated in a problem definition
0179  * with uniquifying "extensions", such as pointer addresses from Geant4.
0180  */
0181 template<class I>
0182 auto LabelIdMultiMap<I>::find_all(std::string const& name) const -> SpanConstIdT
0183 {
0184     auto iter = ids_.find(name);
0185     if (iter == ids_.end())
0186         return {};
0187
0188     size_type offset_idx = iter->second;
0189     CELER_ASSERT(offset_idx + 1 < id_offsets_.size());
0190     size_type start = id_offsets_[offset_idx];
0191     size_type stop = id_offsets_[offset_idx + 1];
0192     CELER_ENSURE(start < stop && stop <= id_data_.size());
0193     return {id_data_.data() + start, stop - start};
0194 }
0195
0196 //---------------------------------------------------------------------------//
0197 /*!
0198  * Find the ID corresponding to a label if exactly one exists.
0199  *
0200  * This will return an invalid ID if no labels match the given name, and it
0201  * will raise an exception if multiple labels do.
0202  */
0203 template<class I>
0204 auto LabelIdMultiMap<I>::find_unique(std::string const& name) const -> IdT
0205 {
0206     auto items = this->find_all(name);
0207     if (items.empty())
0208         return {};
0209     CELER_VALIDATE(items.size() == 1,
0210                    << type_label_ << " '" << name << "' is not unique");
0211     return items.front();
0212 }
0213
0214 //---------------------------------------------------------------------------//
0215 /*!
0216  * Access an ID by exact label (name plus extension).
0217  *
0218  * This returns a \c false OpaqueId if no such label pair exists.
0219  */
0220 template<class I>
0221 auto LabelIdMultiMap<I>::find_exact(Label const& label_sub) const -> IdT
0222 {
0223     auto items = this->find_all(label_sub.name);
0224
0225     // Just do a linear search on sublabels
0226     auto iter = std::find_if(
0227         items.begin(), items.end(), [&keys = keys_, &label_sub](IdT id) {
0228             CELER_EXPECT(id < keys.size());
0229             return keys[id.unchecked_get()].ext == label_sub.ext;
0230         });
0231     if (iter == items.end())
0232     {
0233         // No sublabel matches
0234         return {};
0235     }
0236     CELER_ENSURE(keys_[iter->unchecked_get()] == label_sub);
0237     return *iter;
0238 }
0239
0240 //---------------------------------------------------------------------------//
0241 /*!
0242  * Access the label+sublabel pair for an Id.
0243  *
0244  * This raises an exception if the ID is outside of the valid range.
0245  */
0246 template<class I>
0247 Label const& LabelIdMultiMap<I>::at(IdT id) const
0248 {
0249     CELER_EXPECT(id < this->size());
0250     return keys_[id.unchecked_get()];
0251 }
0252
0253 //---------------------------------------------------------------------------//
0254 /*!
0255  * Whether this map is initialized.
0256  */
0257 template<class I>
0258 CELER_FORCEINLINE LabelIdMultiMap<I>::operator bool() const
0259 {
0260     return !keys_.empty() || !type_label_.empty();
0261 }
0262
0263 //---------------------------------------------------------------------------//
0264 }  // namespace celeritas