ECCE @ EIC Software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MultiIndex.hpp
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file MultiIndex.hpp
1 // This file is part of the Acts project.
2 //
3 // Copyright (C) 2019 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 
11 #include <array>
12 #include <cassert>
13 #include <climits>
14 #include <ostream>
15 #include <type_traits>
16 #include <utility>
17 
18 namespace Acts {
19 
28 template <typename T, std::size_t... BitsPerLevel>
29 class MultiIndex {
30  public:
31  static_assert(std::is_integral_v<T> and std::is_unsigned_v<T>,
32  "The underlying storage type must be an unsigned integer");
33  static_assert(0 < sizeof...(BitsPerLevel),
34  "At least one level must be defined");
35  static_assert((sizeof(T) * CHAR_BIT) == (... + BitsPerLevel),
36  "The sum of bits per level must match the underlying storage");
37 
39  using Value = T;
40  enum : std::size_t {
41  NumLevels = sizeof...(BitsPerLevel),
42  };
43 
45  static constexpr MultiIndex Zeros() { return MultiIndex(0u); }
53  template <typename... Us>
54  static constexpr MultiIndex Encode(Us&&... us) {
55  static_assert(sizeof...(Us) <= NumLevels,
56  "Can only encode as many levels as in the MultiIndex");
57 
58  MultiIndex index(0u);
59  std::size_t lvl = 0;
60  for (Value val : std::array<Value, sizeof...(Us)>{us...}) {
61  index.set(lvl++, val);
62  }
63  return index;
64  }
65 
67  constexpr MultiIndex(Value encoded) : m_value(encoded) {}
69  MultiIndex() = default;
70  MultiIndex(const MultiIndex&) = default;
71  MultiIndex(MultiIndex&) = default;
72  MultiIndex& operator=(const MultiIndex&) = default;
73  MultiIndex& operator=(MultiIndex&&) = default;
75  constexpr MultiIndex& operator=(Value encoded) {
76  m_value = encoded;
77  return *this;
78  }
79 
81  constexpr Value value() const { return m_value; }
83  constexpr Value level(std::size_t lvl) const {
84  assert((lvl < NumLevels) and "Index level outside allowed range");
85  return (m_value >> shift(lvl)) & mask(lvl);
86  }
88  constexpr MultiIndex& set(std::size_t lvl, Value val) {
89  assert((lvl < NumLevels) and "Index level outside allowed range");
90  // mask of valid bits at the encoded positions for the index level
91  Value shiftedMask = (mask(lvl) << shift(lvl));
92  // value of the index level shifted to its encoded position
93  Value shiftedValue = (val << shift(lvl));
94  // combine existing values with the value for the index level
95  m_value = (m_value & ~shiftedMask) | (shiftedValue & shiftedMask);
96  return *this;
97  }
98 
100  constexpr MultiIndex makeNextSibling(std::size_t lvl) const {
101  assert((lvl < NumLevels) and "Index level outside allowed range");
102  // remove lower levels by shifting the upper levels to the left edge
103  Value upper = (m_value >> shift(lvl));
104  // increase to create sibling and shift back to zero lower levels again
105  return ((upper + 1u) << shift(lvl));
106  }
108  constexpr MultiIndex makeLastDescendant(std::size_t lvl) const {
109  assert((lvl < NumLevels) and "Index level outside allowed range");
110  // mask everything below the selected level
111  Value maskLower = (Value(1u) << shift(lvl)) - 1u;
112  // replace the masked lower levels w/ ones
113  return (m_value & ~maskLower) | maskLower;
114  }
115 
116  private:
117  // per-level mask and right-most bit position for shifting
118  static constexpr std::array<std::size_t, NumLevels> s_bits{BitsPerLevel...};
119  static constexpr std::size_t shift(std::size_t lvl) {
120  std::size_t s = 0u;
121  // sum up all bits below the requested level
122  for (std::size_t i = (lvl + 1); i < s_bits.size(); ++i) {
123  s += s_bits[i];
124  }
125  return s;
126  }
127  static constexpr Value mask(std::size_t lvl) {
128  return (Value(1u) << s_bits[lvl]) - 1u;
129  }
130 
132 
133  friend constexpr bool operator<(MultiIndex lhs, MultiIndex rhs) {
134  return lhs.m_value < rhs.m_value;
135  }
136  friend constexpr bool operator==(MultiIndex lhs, MultiIndex rhs) {
137  return lhs.m_value == rhs.m_value;
138  }
139  friend inline std::ostream& operator<<(std::ostream& os, MultiIndex idx) {
140  // one level is always defined
141  os << idx.level(0u);
142  for (std::size_t lvl = 1; lvl < NumLevels; ++lvl) {
143  os << '|' << idx.level(lvl);
144  }
145  return os;
146  }
147 };
148 
149 } // namespace Acts
150 
151 // specialize std::hash so MultiIndex can be used e.g. in an unordered_map
152 namespace std {
153 template <typename Storage, std::size_t... BitsPerLevel>
154 struct hash<Acts::MultiIndex<Storage, BitsPerLevel...>> {
156  noexcept {
157  return std::hash<Storage>()(idx.value());
158  }
159 };
160 } // namespace std