Analysis Software
Documentation for sPHENIX simulation software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GeometryHierarchyMap.hpp
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file GeometryHierarchyMap.hpp
1 // This file is part of the Acts project.
2 //
3 // Copyright (C) 2020 CERN for the benefit of the Acts project
4 //
5 // This Source Code Form is subject to the terms of the Mozilla Public
6 // License, v. 2.0. If a copy of the MPL was not distributed with this
7 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 
9 #pragma once
10 
12 
13 #include <algorithm>
14 #include <cassert>
15 #include <initializer_list>
16 #include <iterator>
17 #include <stdexcept>
18 #include <utility>
19 #include <vector>
20 
21 namespace Acts {
22 
61 template <typename value_t>
63  public:
65  using InputElement = typename std::pair<GeometryIdentifier, value_t>;
66  using Iterator = typename std::vector<value_t>::const_iterator;
67  using Size = typename std::vector<value_t>::size_type;
68  using Value = value_t;
69 
73  GeometryHierarchyMap(std::vector<InputElement> elements);
77  GeometryHierarchyMap(std::initializer_list<InputElement> elements);
78 
79  // defaulted constructors and assignment operators
80  GeometryHierarchyMap() = default;
83  ~GeometryHierarchyMap() = default;
86 
88  Iterator begin() const { return m_values.begin(); }
90  Iterator end() const { return m_values.end(); }
92  bool empty() const { return m_values.empty(); }
94  Size size() const { return m_values.size(); }
95 
99  GeometryIdentifier idAt(Size index) const { return m_ids.at(index); }
103  const Value& valueAt(Size index) const { return m_values.at(index); }
104 
114  Iterator find(GeometryIdentifier id) const;
115 
116  private:
117  // NOTE this class assumes that it knows the ordering of the levels within
118  // the geometry id. if the geometry id changes, this code has to be
119  // adapted too. the asserts ensure that such a change is caught.
120  static_assert(GeometryIdentifier().setVolume(1).value() <
121  GeometryIdentifier().setVolume(1).setBoundary(1).value(),
122  "Incompatible GeometryIdentifier hierarchy");
123  static_assert(GeometryIdentifier().setBoundary(1).value() <
124  GeometryIdentifier().setBoundary(1).setLayer(1).value(),
125  "Incompatible GeometryIdentifier hierarchy");
126  static_assert(GeometryIdentifier().setLayer(1).value() <
127  GeometryIdentifier().setLayer(1).setApproach(1).value(),
128  "Incompatible GeometryIdentifier hierarchy");
129  static_assert(GeometryIdentifier().setApproach(1).value() <
130  GeometryIdentifier().setApproach(1).setSensitive(1).value(),
131  "Incompatible GeometryIdentifier hierarchy");
132 
134 
135  // encoded ids for all elements for faster lookup.
136  std::vector<Identifier> m_ids;
137  // validity bit masks for the ids: which parts to use for comparison
138  std::vector<Identifier> m_masks;
139  std::vector<Value> m_values;
140 
143  // construct id from encoded value with all bits set
145  // manually iterate over identifier levels starting from the lowest
146  if (id.sensitive() != 0u) {
147  // all levels are valid; keep all bits set.
148  return allSet.setExtra(0u).value();
149  }
150  if (id.approach() != 0u) {
151  return allSet.setExtra(0u).setSensitive(0u).value();
152  }
153  if (id.layer() != 0u) {
154  return allSet.setExtra(0u).setSensitive(0u).setApproach(0u).value();
155  }
156  if (id.boundary() != 0u) {
157  return allSet.setExtra(0u)
158  .setSensitive(0u)
159  .setApproach(0u)
160  .setLayer(0u)
161  .value();
162  }
163  if (id.volume() != 0u) {
164  return allSet.setExtra(0u)
165  .setSensitive(0u)
166  .setApproach(0u)
167  .setLayer(0u)
168  .setBoundary(0u)
169  .value();
170  }
171  // no valid levels; all bits are zero.
172  return Identifier(0u);
173  }
175  static constexpr Identifier makeHighestLevelMask() {
176  return makeLeadingLevelsMask(GeometryIdentifier(0u).setVolume(1u));
177  }
179  static constexpr bool equalWithinMask(Identifier lhs, Identifier rhs,
180  Identifier mask) {
181  return (lhs & mask) == (rhs & mask);
182  }
184  template <typename iterator_t>
186 
191  template <typename iterator_t>
192  void fill(iterator_t beg, iterator_t end);
193 };
194 
195 // implementations
196 
197 template <typename value_t>
199  std::vector<InputElement> elements) {
200  sortAndCheckDuplicates(elements.begin(), elements.end());
201  fill(elements.begin(), elements.end());
202 }
203 
204 template <typename value_t>
206  std::initializer_list<InputElement> elements)
208  std::vector<InputElement>(elements.begin(), elements.end())) {}
209 
210 template <typename value_t>
211 template <typename iterator_t>
213  iterator_t beg, iterator_t end) {
214  // ensure elements are sorted by identifier
215  std::sort(beg, end, [=](const auto& lhs, const auto& rhs) {
216  return lhs.first < rhs.first;
217  });
218  // check that all elements have unique identifier
219  auto dup = std::adjacent_find(beg, end, [](const auto& lhs, const auto& rhs) {
220  return lhs.first == rhs.first;
221  });
222  if (dup != end) {
223  throw std::invalid_argument("Input elements contain duplicates");
224  }
225 }
226 
227 template <typename value_t>
228 template <typename iterator_t>
230  iterator_t end) {
231  const auto n = std::distance(beg, end);
232  m_ids.clear();
233  m_ids.reserve(n);
234  m_masks.clear();
235  m_masks.reserve(n);
236  m_values.clear();
237  m_values.reserve(n);
238  for (; beg != end; ++beg) {
239  m_ids.push_back(beg->first.value());
240  m_masks.push_back(makeLeadingLevelsMask(beg->first.value()));
241  m_values.push_back(std::move(beg->second));
242  }
243 }
244 
245 template <typename value_t>
247  -> Iterator {
248  assert((m_ids.size() == m_values.size()) and
249  "Inconsistent container state: #ids != # values");
250  assert((m_masks.size() == m_values.size()) and
251  "Inconsistent container state: #masks != #values");
252 
253  // we can not search for the element directly since the relevant one
254  // might be stored at a higher level. ids for higher levels would always
255  // be sorted before the requested id. searching for the first element
256  // after the requested ensures that we include the full hierarchy.
257  const auto it = std::upper_bound(m_ids.begin(), m_ids.end(), id.value());
258  auto i = std::distance(m_ids.begin(), it);
259 
260  // now go up the hierarchy to find the first matching element.
261  // example: the container stores four identifiers
262  //
263  // 2|x|x (volume-only)
264  // 2|2|1 (volume, layer, and sensitive)
265  // 2|3|x (volume and layer)
266  // 2|3|4 (volume, layer, and sensitive)
267  //
268  // where | marks level boundaries. searching for either 2|3|4, 2|3|7, or
269  // 2|4|x would first point to 2|3|4 and thus needs to go up the hierarchy.
270  while (0 < i) {
271  // index always starts after item of interest due to upper bound search
272  --i;
273 
274  // if the input id does not even match at the highest hierarchy level
275  // with the current comparison id, then have reached the end of this
276  // hierarchy. having a special check for the highest level avoids an
277  // unbounded search window all the way to the beginning of the container for
278  // the global default entry.
279  if (not equalWithinMask(id.value(), m_ids[i], makeHighestLevelMask())) {
280  // check if a global default entry exists
281  if (m_ids.front() == Identifier(0u)) {
282  return begin();
283  } else {
284  return end();
285  }
286  }
287 
288  // since the search is going backwards in the sorted container, it
289  // progresses from more specific to less specific elements. the first
290  // match is automatically the appropriate one.
291  if (equalWithinMask(id.value(), m_ids[i], m_masks[i])) {
292  return std::next(begin(), i);
293  }
294  }
295 
296  // all options are exhausted and no matching element was found.
297  return end();
298 }
299 
300 } // namespace Acts