| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // This file is part of INSTINCT, the INS Toolkit for Integrated | ||
| 2 | // Navigation Concepts and Training by the Institute of Navigation of | ||
| 3 | // the University of Stuttgart, Germany. | ||
| 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 https://mozilla.org/MPL/2.0/. | ||
| 8 | |||
| 9 | /// @file KeyedMap.hpp | ||
| 10 | /// @brief Similar to KeyedMatrix, but memory is allocated in a map and therefore never reallocated | ||
| 11 | /// @author T. Topp (topp@ins.uni-stuttgart.de) | ||
| 12 | /// @date 2024-10-08 | ||
| 13 | |||
| 14 | #pragma once | ||
| 15 | |||
| 16 | #include <algorithm> | ||
| 17 | #include <map> | ||
| 18 | #include <type_traits> | ||
| 19 | #include <vector> | ||
| 20 | #include <span> | ||
| 21 | #include <fmt/format.h> | ||
| 22 | |||
| 23 | #include "util/Assert.h" | ||
| 24 | #include "util/Container/Unordered_map.hpp" | ||
| 25 | |||
| 26 | namespace NAV | ||
| 27 | { | ||
| 28 | |||
| 29 | /// @brief Similar to KeyedMatrix, but memory is allocated in a map and therefore never reallocated | ||
| 30 | /// @tparam KeyType Type to use as keys | ||
| 31 | /// @tparam Scalar Type to store in the map | ||
| 32 | /// @tparam unordered Wether an unordered_map or a std::map should be used | ||
| 33 | template<typename KeyType, typename Scalar, bool unordered = true> | ||
| 34 | class KeyedMap | ||
| 35 | { | ||
| 36 | public: | ||
| 37 | // ########################################################################################################### | ||
| 38 | // Constructors | ||
| 39 | // ########################################################################################################### | ||
| 40 | // | ||
| 41 | // ########################################################################################################### | ||
| 42 | // Iterators | ||
| 43 | // ########################################################################################################### | ||
| 44 | |||
| 45 | /// @brief Returns an iterator to the first element. | ||
| 46 | /// | ||
| 47 | /// If the buffer is empty, the returned iterator will be equal to end(). | ||
| 48 | decltype(auto) begin() { return _lookup.begin(); } | ||
| 49 | /// @brief Returns an iterator to the first element. | ||
| 50 | /// | ||
| 51 | /// If the buffer is empty, the returned iterator will be equal to end(). | ||
| 52 | [[nodiscard]] decltype(auto) begin() const noexcept { return _lookup.begin(); } | ||
| 53 | /// @brief Returns an iterator to the first element. | ||
| 54 | /// | ||
| 55 | /// If the buffer is empty, the returned iterator will be equal to end(). | ||
| 56 | [[nodiscard]] decltype(auto) cbegin() const noexcept { return _lookup.cbegin(); } | ||
| 57 | |||
| 58 | /// @brief Returns an iterator to the element following the last element of. | ||
| 59 | /// | ||
| 60 | /// This element acts as a placeholder; attempting to access it results in undefined behavior. | ||
| 61 | decltype(auto) end() { return _lookup.end(); } | ||
| 62 | /// @brief Returns an iterator to the element following the last element of. | ||
| 63 | /// | ||
| 64 | /// This element acts as a placeholder; attempting to access it results in undefined behavior. | ||
| 65 | [[nodiscard]] decltype(auto) end() const noexcept { return _lookup.end(); } | ||
| 66 | /// @brief Returns an iterator to the element following the last element of. | ||
| 67 | /// | ||
| 68 | /// This element acts as a placeholder; attempting to access it results in undefined behavior. | ||
| 69 | [[nodiscard]] decltype(auto) cend() const noexcept { return _lookup.cend(); } | ||
| 70 | |||
| 71 | // ########################################################################################################### | ||
| 72 | // Capacity | ||
| 73 | // ########################################################################################################### | ||
| 74 | |||
| 75 | /// @brief Checks if the container has no elements | ||
| 76 | 4 | [[nodiscard]] bool empty() const | |
| 77 | { | ||
| 78 | 4 | return size() == 0; | |
| 79 | } | ||
| 80 | |||
| 81 | /// @brief Returns the number of elements in the container | ||
| 82 | 12 | [[nodiscard]] size_t size() const | |
| 83 | { | ||
| 84 | 12 | return _lookup.size(); | |
| 85 | } | ||
| 86 | |||
| 87 | // ########################################################################################################### | ||
| 88 | // Modifiers | ||
| 89 | // ########################################################################################################### | ||
| 90 | |||
| 91 | /// @brief Erases all elements from the container. After this call, size() returns zero. | ||
| 92 | 4 | void clear() | |
| 93 | { | ||
| 94 | 4 | _lookup.clear(); | |
| 95 | 4 | _data.clear(); | |
| 96 | 4 | } | |
| 97 | |||
| 98 | /// @brief Adds a single element for the key to the data storage | ||
| 99 | /// @param[in] key Key to add | ||
| 100 |
2/4✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
|
12 | void addKey(const KeyType& key) { addKeys(std::vector<KeyType>{ key }); } |
| 101 | |||
| 102 | /// @brief Adds a single element for the key to the data storage | ||
| 103 | /// @param[in] key Key to add | ||
| 104 | /// @param[in] value Value for the key | ||
| 105 |
2/4✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 30 times.
✗ Branch 7 not taken.
|
180 | void addKey(const KeyType& key, const Scalar& value) { addKeys(std::vector<std::pair<KeyType, Scalar>>{ { key, value } }); } |
| 106 | |||
| 107 | /// @brief Adds a continuous vector for the keys to the data storage | ||
| 108 | /// @param[in] keys Keys to add | ||
| 109 | 8 | void addKeys(std::span<const KeyType> keys) | |
| 110 | { | ||
| 111 | 8 | std::vector<std::pair<KeyType, Scalar>> keyValues; | |
| 112 |
1/2✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
|
8 | keyValues.reserve(keys.size()); |
| 113 |
2/2✓ Branch 4 taken 6 times.
✓ Branch 5 taken 4 times.
|
20 | for (const KeyType& key : keys) |
| 114 | { | ||
| 115 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
12 | keyValues.emplace_back(key, Scalar{}); |
| 116 | } | ||
| 117 |
1/2✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
|
8 | addKeys(keyValues); |
| 118 | 8 | } | |
| 119 | |||
| 120 | /// @brief Adds a continuous vector for the keys to the data storage | ||
| 121 | /// @param[in] keys Keys to add | ||
| 122 | /// @param[in] values Values for the keys | ||
| 123 | 4 | void addKeys(std::span<const KeyType> keys, std::span<const Scalar> values) | |
| 124 | { | ||
| 125 |
1/2✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
4 | INS_ASSERT_USER_ERROR(keys.size() == values.size(), "Keys and values vector need to be same size"); |
| 126 | |||
| 127 | 4 | std::vector<std::pair<KeyType, Scalar>> keyValues; | |
| 128 |
1/2✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
4 | keyValues.reserve(keys.size()); |
| 129 |
2/2✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
|
12 | for (size_t i = 0; i < keys.size(); i++) |
| 130 | { | ||
| 131 |
1/2✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
|
8 | keyValues.emplace_back(keys[i], values[i]); |
| 132 | } | ||
| 133 |
1/2✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
4 | addKeys(keyValues); |
| 134 | 4 | } | |
| 135 | |||
| 136 | /// @brief Adds a continuous vector for the keys to the data storage | ||
| 137 | /// @param[in] keyValues Keys and values to add | ||
| 138 | 76 | void addKeys(std::span<const std::pair<KeyType, Scalar>> keyValues) | |
| 139 | { | ||
| 140 |
1/2✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
|
76 | INS_ASSERT_USER_ERROR(!keyValues.empty(), "The vector cannot be empty"); |
| 141 |
1/2✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
|
76 | INS_ASSERT_USER_ERROR(!_data.contains(keyValues.front().first), "Duplicate keys are not allowed"); |
| 142 |
2/2✓ Branch 5 taken 44 times.
✓ Branch 6 taken 38 times.
|
164 | for ([[maybe_unused]] const auto& keyValue : keyValues) |
| 143 | { | ||
| 144 |
2/4✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 44 times.
✗ Branch 4 not taken.
|
88 | INS_ASSERT_USER_ERROR(!_lookup.contains(keyValue.first), "Duplicate subkeys are not allowed"); |
| 145 | } | ||
| 146 | |||
| 147 |
2/4✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 38 times.
✗ Branch 7 not taken.
|
152 | _data.emplace(keyValues.front().first, std::vector<Scalar>(keyValues.size())); |
| 148 |
2/2✓ Branch 1 taken 44 times.
✓ Branch 2 taken 38 times.
|
164 | for (size_t i = 0; i < keyValues.size(); i++) |
| 149 | { | ||
| 150 | 88 | _lookup[keyValues[i].first] = &_data.at(keyValues.front().first).at(i); | |
| 151 | 88 | _data.at(keyValues.front().first).at(i) = keyValues[i].second; | |
| 152 | } | ||
| 153 | 76 | } | |
| 154 | |||
| 155 | // ########################################################################################################### | ||
| 156 | // Lookup | ||
| 157 | // ########################################################################################################### | ||
| 158 | |||
| 159 | /// @brief Returns a reference to the mapped value of the element with specified key. | ||
| 160 | /// If no such element exists, an exception of type std::out_of_range is thrown. | ||
| 161 | /// @param[in] key the key of the element to find | ||
| 162 | /// @return A reference to the mapped value of the requested element. | ||
| 163 | 1044 | Scalar& at(const KeyType& key) | |
| 164 | { | ||
| 165 | 1044 | return *_lookup.at(key); | |
| 166 | } | ||
| 167 | |||
| 168 | /// @brief Returns a reference to the mapped value of the element with specified key. | ||
| 169 | /// If no such element exists, an exception of type std::out_of_range is thrown. | ||
| 170 | /// @param[in] key the key of the element to find | ||
| 171 | /// @return A reference to the mapped value of the requested element. | ||
| 172 | [[nodiscard]] const Scalar& at(const KeyType& key) const | ||
| 173 | { | ||
| 174 | return *_lookup.at(key); | ||
| 175 | } | ||
| 176 | |||
| 177 | /// @brief Returns a reference to the mapped value of the element with specified keys. | ||
| 178 | /// If no such element exists, an exception of type std::out_of_range is thrown. | ||
| 179 | /// @param[in] keys the keys of the element to find | ||
| 180 | /// @return A reference to the mapped value of the requested element. | ||
| 181 | std::vector<Scalar>& at(std::span<const KeyType> keys) | ||
| 182 | { | ||
| 183 | INS_ASSERT_USER_ERROR(!keys.empty(), "The vector cannot be empty"); | ||
| 184 | INS_ASSERT_USER_ERROR(_data.at(keys.front()).size() == keys.size(), "The keys vector stored and requested have different length"); | ||
| 185 | |||
| 186 | return _data.at(keys.front()); | ||
| 187 | } | ||
| 188 | |||
| 189 | /// @brief Returns a reference to the mapped value of the element with specified keys. | ||
| 190 | /// If no such element exists, an exception of type std::out_of_range is thrown. | ||
| 191 | /// @param[in] keys the key of the element to find | ||
| 192 | /// @return A reference to the mapped value of the requested element. | ||
| 193 | [[nodiscard]] const std::vector<Scalar>& at(std::span<const KeyType> keys) const | ||
| 194 | { | ||
| 195 | INS_ASSERT_USER_ERROR(!keys.empty(), "The vector cannot be empty"); | ||
| 196 | INS_ASSERT_USER_ERROR(_data.at(keys.front()).size() == keys.size(), "The keys vector stored and requested have different length"); | ||
| 197 | |||
| 198 | return _data.at(keys.front()); | ||
| 199 | } | ||
| 200 | |||
| 201 | /// @brief Checks if there is an element with key equivalent to `key` in the container. | ||
| 202 | /// @param[in] key key value of the element to search for | ||
| 203 | /// @return true if there is such an element, otherwise false. | ||
| 204 | 8 | [[nodiscard]] bool contains(const KeyType& key) const | |
| 205 | { | ||
| 206 | 8 | return _lookup.contains(key); | |
| 207 | } | ||
| 208 | |||
| 209 | /// @brief Checks if there are elements with keys equivalent to `keys` in the container. | ||
| 210 | /// @param[in] keys keys the elements to search for | ||
| 211 | /// @return true if there is such an element, otherwise false. | ||
| 212 | 2 | [[nodiscard]] bool contains(std::span<const KeyType> keys) const | |
| 213 | { | ||
| 214 | 2 | INS_ASSERT_USER_ERROR(!keys.empty(), "The vector cannot be empty"); | |
| 215 | |||
| 216 | 6 | return std::all_of(keys.begin(), keys.end(), [&](const auto& key) { return _lookup.contains(key); }); | |
| 217 | } | ||
| 218 | |||
| 219 | /// @brief Returns the size of parameters represented by the key | ||
| 220 | /// @param[in] key key value of the element to search for | ||
| 221 | [[nodiscard]] size_t size_of(const KeyType& key) const | ||
| 222 | { | ||
| 223 | return _data.contains(key) ? _data.at(key).size() : (_lookup.contains(key) ? 1 : 0); | ||
| 224 | } | ||
| 225 | |||
| 226 | // ########################################################################################################### | ||
| 227 | // Others | ||
| 228 | // ########################################################################################################### | ||
| 229 | |||
| 230 | /// @brief Collect all keys | ||
| 231 | /// @return The keys stored | ||
| 232 | [[nodiscard]] std::vector<KeyType> keys() const | ||
| 233 | { | ||
| 234 | std::vector<KeyType> keys; | ||
| 235 | keys.reserve(_lookup.size()); | ||
| 236 | for (const auto& keyVal : _lookup) | ||
| 237 | { | ||
| 238 | keys.push_back(keyVal.first); | ||
| 239 | } | ||
| 240 | return keys; | ||
| 241 | } | ||
| 242 | |||
| 243 | private: | ||
| 244 | /// Lookup for individual keys | ||
| 245 | unordered_map<KeyType, Scalar*> _lookup; | ||
| 246 | |||
| 247 | /// Storage container | ||
| 248 | std::conditional_t<unordered, | ||
| 249 | unordered_map<KeyType, std::vector<Scalar>>, | ||
| 250 | std::map<KeyType, std::vector<Scalar>>> | ||
| 251 | _data; | ||
| 252 | }; | ||
| 253 | |||
| 254 | } // namespace NAV | ||
| 255 | |||
| 256 | #ifndef DOXYGEN_IGNORE | ||
| 257 | |||
| 258 | /// @brief Formatter for KeyedMap | ||
| 259 | template<typename KeyType, typename Scalar, bool unordered> | ||
| 260 | struct fmt::formatter<NAV::KeyedMap<KeyType, Scalar, unordered>> : fmt::formatter<std::string> | ||
| 261 | { | ||
| 262 | /// @brief Defines how to format KeyedMap structs | ||
| 263 | /// @param[in] map Struct to format | ||
| 264 | /// @param[in, out] ctx Format context | ||
| 265 | /// @return Output iterator | ||
| 266 | auto format(const NAV::KeyedMap<KeyType, Scalar, unordered>& map, format_context& ctx) const | ||
| 267 | { | ||
| 268 | std::string result; | ||
| 269 | auto length = static_cast<size_t>(map.size()); | ||
| 270 | |||
| 271 | if (length > 0) | ||
| 272 | { | ||
| 273 | std::vector<std::string> rowKeysStr; | ||
| 274 | std::vector<size_t> rowKeysLength; | ||
| 275 | rowKeysStr.reserve(length); | ||
| 276 | rowKeysLength.reserve(length); | ||
| 277 | size_t rowKeysColSpace = 0; | ||
| 278 | for (const auto& keyVal : map) | ||
| 279 | { | ||
| 280 | rowKeysStr.push_back(fmt::format("{}", keyVal.first)); | ||
| 281 | auto rowKeyLength = rowKeysStr.back().length(); | ||
| 282 | rowKeysColSpace = std::max(rowKeysColSpace, rowKeyLength); | ||
| 283 | rowKeysLength.push_back(rowKeyLength); | ||
| 284 | } | ||
| 285 | |||
| 286 | size_t colLength = 9UL; | ||
| 287 | |||
| 288 | result.reserve(length * (rowKeysColSpace + 2 + colLength)); | ||
| 289 | |||
| 290 | size_t r = 0; | ||
| 291 | for (const auto& keyVal : map) | ||
| 292 | { | ||
| 293 | if (rowKeysColSpace > rowKeysLength.at(r)) | ||
| 294 | { | ||
| 295 | result += std::string(rowKeysColSpace - rowKeysLength.at(r), ' '); // Spaces in front of row name (if too short) | ||
| 296 | } | ||
| 297 | result += rowKeysStr.at(r); | ||
| 298 | |||
| 299 | std::string tmp = fmt::format(" {:> {}.{}g}", *keyVal.second, colLength, colLength - 2); | ||
| 300 | if (tmp.length() > colLength) | ||
| 301 | { | ||
| 302 | tmp = fmt::format(" {:> {}.{}g}", *keyVal.second, colLength, colLength - 6); | ||
| 303 | } | ||
| 304 | result += tmp; | ||
| 305 | |||
| 306 | if (r != length - 1) { result += '\n'; } | ||
| 307 | r++; | ||
| 308 | } | ||
| 309 | } | ||
| 310 | |||
| 311 | return fmt::formatter<std::string>::format(result, ctx); | ||
| 312 | } | ||
| 313 | }; | ||
| 314 | |||
| 315 | #endif | ||
| 316 | |||
| 317 | /// @brief Stream insertion operator overload | ||
| 318 | /// @param[in, out] os Output stream object to stream the time into | ||
| 319 | /// @param[in] obj Object to print | ||
| 320 | /// @return Returns the output stream object in order to chain stream insertions | ||
| 321 | template<typename KeyType, typename Scalar, bool unordered> | ||
| 322 | std::ostream& operator<<(std::ostream& os, const NAV::KeyedMap<KeyType, Scalar, unordered>& obj) | ||
| 323 | { | ||
| 324 | return os << fmt::format("{}", obj); | ||
| 325 | } | ||
| 326 |