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 no elements are present
0086     CELER_FORCEINLINE bool empty() const { return keys_.empty(); }
0087
0088     // Whether this map is initialized
0089     inline explicit operator bool() const;
0090
0091     //! Get duplicate labels to warn about
0092     SpanConstIdT duplicates() const { return make_span(duplicates_); }
0093
0094   private:
0095     std::string type_label_;
0096     VecLabel keys_;
0097     std::vector<IdT> id_data_;
0098     std::vector<size_type> id_offsets_;
0099     std::vector<IdT> duplicates_;
0100     std::unordered_map<std::string, size_type> ids_;
0101 };
0102
0103 //---------------------------------------------------------------------------//
0104 // INLINE DEFINITIONS
0105 //---------------------------------------------------------------------------//
0106 /*!
0107  * Construct from a vector of label+sublabel pairs, with no type.
0108  */
0109 template<class I>
0110 LabelIdMultiMap<I>::LabelIdMultiMap(VecLabel&& keys)
0111     : LabelIdMultiMap{{}, std::move(keys)}
0112 {
0113 }
0114
0115 //---------------------------------------------------------------------------//
0116 /*!
0117  * Construct from a vector of label+sublabel pairs, with a type string.
0118  */
0119 template<class I>
0120 LabelIdMultiMap<I>::LabelIdMultiMap(std::string&& label, VecLabel&& keys)
0121     : type_label_{std::move(label)}, keys_{std::move(keys)}
0122 {
0123     if (keys_.empty())
0124     {
0125         // Sometimes we don't have any items to map. Rely on the
0126         // default-constructed values.
0127         return;
0128     }
0129
0130     // Build list of IDs corresponding to each key
0131     id_data_.resize(keys_.size());
0132     for (auto idx : range<size_type>(keys_.size()))
0133     {
0134         id_data_[idx] = IdT{idx};
0135     }
0136     // Reorder consecutive ID data based on string lexicographic ordering
0137     std::sort(id_data_.begin(), id_data_.end(), [&keys = keys_](IdT a, IdT b) {
0138         return keys[a.unchecked_get()] < keys[b.unchecked_get()];
0139     });
0140
0141     // Reserve space for groups
0142     id_offsets_.reserve(keys_.size() / 2 + 2);
0143     ids_.reserve(id_offsets_.capacity());
0144
0145     // Search for when the label changes
0146     id_offsets_.push_back(0);
0147     ids_.insert({keys_[id_data_[0].unchecked_get()].name, 0});
0148     for (auto idx : range<size_type>(1, id_data_.size()))
0149     {
0150         Label const& prev = keys_[id_data_[idx - 1].unchecked_get()];
0151         Label const& cur = keys_[id_data_[idx].unchecked_get()];
0152         if (prev == cur && !cur.empty())
0153         {
0154             if (duplicates_.empty()
0155                 || keys_[duplicates_.back().unchecked_get()] != prev)
0156             {
0157                 // Push back previous entry if it's not already there
0158                 duplicates_.push_back(id_data_[idx - 1]);
0159             }
0160             duplicates_.push_back(id_data_[idx]);
0161         }
0162         if (prev.name != cur.name)
0163         {
0164             // Add start index of the new name
0165             size_type offset_idx = id_offsets_.size();
0166             id_offsets_.push_back(idx);
0167             auto insert_ok = ids_.insert({cur.name, offset_idx});
0168             CELER_ASSERT(insert_ok.second);
0169         }
0170     }
0171     id_offsets_.push_back(id_data_.size());
0172
0173     CELER_ENSURE(keys_.size() == id_data_.size());
0174     CELER_ENSURE(id_offsets_.size() == ids_.size() + 1);
0175 }
0176
0177 //---------------------------------------------------------------------------//
0178 /*!
0179  * Access the range of IDs corresponding to a label.
0180  *
0181  * This is useful for identifiers that may be repeated in a problem definition
0182  * with uniquifying "extensions", such as pointer addresses from Geant4.
0183  */
0184 template<class I>
0185 auto LabelIdMultiMap<I>::find_all(std::string const& name) const
0186     -> SpanConstIdT
0187 {
0188     auto iter = ids_.find(name);
0189     if (iter == ids_.end())
0190         return {};
0191
0192     size_type offset_idx = iter->second;
0193     CELER_ASSERT(offset_idx + 1 < id_offsets_.size());
0194     size_type start = id_offsets_[offset_idx];
0195     size_type stop = id_offsets_[offset_idx + 1];
0196     CELER_ENSURE(start < stop && stop <= id_data_.size());
0197     return {id_data_.data() + start, stop - start};
0198 }
0199
0200 //---------------------------------------------------------------------------//
0201 /*!
0202  * Find the ID corresponding to a label if exactly one exists.
0203  *
0204  * This will return an invalid ID if no labels match the given name, and it
0205  * will raise an exception if multiple labels do.
0206  */
0207 template<class I>
0208 auto LabelIdMultiMap<I>::find_unique(std::string const& name) const -> IdT
0209 {
0210     auto items = this->find_all(name);
0211     if (items.empty())
0212         return {};
0213     CELER_VALIDATE(items.size() == 1,
0214                    << type_label_ << " '" << name << "' is not unique");
0215     return items.front();
0216 }
0217
0218 //---------------------------------------------------------------------------//
0219 /*!
0220  * Access an ID by exact label (name plus extension).
0221  *
0222  * This returns a \c false OpaqueId if no such label pair exists.
0223  */
0224 template<class I>
0225 auto LabelIdMultiMap<I>::find_exact(Label const& label_sub) const -> IdT
0226 {
0227     auto items = this->find_all(label_sub.name);
0228
0229     // Just do a linear search on sublabels
0230     auto iter = std::find_if(
0231         items.begin(), items.end(), [&keys = keys_, &label_sub](IdT id) {
0232             CELER_EXPECT(id < keys.size());
0233             return keys[id.unchecked_get()].ext == label_sub.ext;
0234         });
0235     if (iter == items.end())
0236     {
0237         // No sublabel matches
0238         return {};
0239     }
0240     CELER_ENSURE(keys_[iter->unchecked_get()] == label_sub);
0241     return *iter;
0242 }
0243
0244 //---------------------------------------------------------------------------//
0245 /*!
0246  * Access the label+sublabel pair for an Id.
0247  *
0248  * This raises an exception if the ID is outside of the valid range.
0249  */
0250 template<class I>
0251 Label const& LabelIdMultiMap<I>::at(IdT id) const
0252 {
0253     CELER_EXPECT(id < this->size());
0254     return keys_[id.unchecked_get()];
0255 }
0256
0257 //---------------------------------------------------------------------------//
0258 /*!
0259  * Whether this map is initialized.
0260  */
0261 template<class I>
0262 CELER_FORCEINLINE LabelIdMultiMap<I>::operator bool() const
0263 {
0264     return !keys_.empty() || !type_label_.empty();
0265 }
0266
0267 //---------------------------------------------------------------------------//
0268 }  // namespace celeritas