1 #ifndef OSMIUM_INDEX_RELATIONS_MAP_HPP 2 #define OSMIUM_INDEX_RELATIONS_MAP_HPP 3 4 /* 5 6 This file is part of Osmium (https://osmcode.org/libosmium). 7 8 Copyright 2013-2021 Jochen Topf <jochen@topf.org> and others (see README). 9 10 Boost Software License - Version 1.0 - August 17th, 2003 11 12 Permission is hereby granted, free of charge, to any person or organization 13 obtaining a copy of the software and accompanying documentation covered by 14 this license (the "Software") to use, reproduce, display, distribute, 15 execute, and transmit the Software, and to prepare derivative works of the 16 Software, and to permit third-parties to whom the Software is furnished to 17 do so, all subject to the following: 18 19 The copyright notices in the Software and this entire statement, including 20 the above license grant, this restriction and the following disclaimer, 21 must be included in all copies of the Software, in whole or in part, and 22 all derivative works of the Software, unless such copies or derivative 23 works are solely in the form of machine-executable object code generated by 24 a source language processor. 25 26 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 27 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 28 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT 29 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE 30 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, 31 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 32 DEALINGS IN THE SOFTWARE. 33 34 */ 35 36 #include <osmium/osm/item_type.hpp> 37 #include <osmium/osm/relation.hpp> 38 #include <osmium/osm/types.hpp> 39 40 #include <algorithm> 41 #include <cassert> 42 #include <cstddef> 43 #include <cstdint> 44 #include <tuple> 45 #include <type_traits> 46 #include <utility> 47 #include <vector> 48 49 namespace osmium { 50 51 namespace index { 52 53 namespace detail { 54 55 template <typename TKey, typename TKeyInternal, typename TValue, typename TValueInternal> 56 class flat_map { 57 58 public: 59 60 using key_type = TKey; 61 using value_type = TValue; 62 63 private: 64 65 struct kv_pair { 66 TKeyInternal key; 67 TValueInternal value; 68 kv_pairosmium::index::detail::flat_map::kv_pair69 explicit kv_pair(const key_type key_id) : 70 key(static_cast<TKeyInternal>(key_id)), 71 value() { 72 } 73 kv_pairosmium::index::detail::flat_map::kv_pair74 kv_pair(const key_type key_id, const value_type value_id) : 75 key(static_cast<TKeyInternal>(key_id)), 76 value(static_cast<TValueInternal>(value_id)) { 77 } 78 operator <osmium::index::detail::flat_map::kv_pair79 bool operator<(const kv_pair& other) const noexcept { 80 return std::tie(key, value) < std::tie(other.key, other.value); 81 } 82 operator ==osmium::index::detail::flat_map::kv_pair83 bool operator==(const kv_pair& other) const noexcept { 84 return std::tie(key, value) == std::tie(other.key, other.value); 85 } 86 }; // struct kv_pair 87 88 std::vector<kv_pair> m_map; 89 90 public: 91 92 using const_iterator = typename std::vector<kv_pair>::const_iterator; 93 set(const key_type key,const value_type value)94 void set(const key_type key, const value_type value) { 95 m_map.emplace_back(key, value); 96 } 97 flip_in_place()98 typename std::enable_if<std::is_same<TKey, TValue>::value>::type flip_in_place() { 99 for (auto& p : m_map) { 100 using std::swap; 101 swap(p.key, p.value); 102 } 103 } 104 flip_copy()105 flat_map<TValue, TValueInternal, TKey, TKeyInternal> flip_copy() { 106 flat_map<TValue, TValueInternal, TKey, TKeyInternal> map; 107 map.reserve(m_map.size()); 108 109 for (const auto& p : m_map) { 110 map.set(p.value, p.key); 111 } 112 113 return map; 114 } 115 sort_unique()116 void sort_unique() { 117 std::sort(m_map.begin(), m_map.end()); 118 const auto last = std::unique(m_map.begin(), m_map.end()); 119 m_map.erase(last, m_map.end()); 120 } 121 get(const key_type key) const122 std::pair<const_iterator, const_iterator> get(const key_type key) const noexcept { 123 return std::equal_range(m_map.begin(), m_map.end(), kv_pair{key}, [](const kv_pair& lhs, const kv_pair& rhs) { 124 return lhs.key < rhs.key; 125 }); 126 } 127 empty() const128 bool empty() const noexcept { 129 return m_map.empty(); 130 } 131 size() const132 std::size_t size() const noexcept { 133 return m_map.size(); 134 } 135 reserve(const std::size_t size)136 void reserve(const std::size_t size) { 137 m_map.reserve(size); 138 } 139 140 }; // class flat_map 141 142 } // namespace detail 143 144 /** 145 * Index for looking up parent relation IDs given a member relation ID 146 * or the other way around. 147 * 148 * You can not instantiate such an index yourself, instead you need to 149 * instantiate a RelationsMapStash, fill it and then create an index 150 * from it: 151 * 152 * @code 153 * RelationsMapStash stash; 154 * ... 155 * for_each_relation(const osmium::Relation& relation) { 156 * stash.add_members(relation); 157 * } 158 * ... 159 * const auto index = stash.build_member_to_parent_index(); 160 * ... 161 * osmium::unsigned_object_id_type member_id = ...; 162 * index.for_each(member_id, [](osmium::unsigned_object_id_type parent_id) { 163 * ... 164 * }); 165 * ... 166 * @endcode 167 * 168 */ 169 class RelationsMapIndex { 170 171 friend class RelationsMapStash; 172 friend class RelationsMapIndexes; 173 174 using map_type = detail::flat_map<osmium::unsigned_object_id_type, uint32_t, 175 osmium::unsigned_object_id_type, uint32_t>; 176 177 map_type m_map; 178 RelationsMapIndex(map_type && map)179 explicit RelationsMapIndex(map_type&& map) : 180 m_map(std::move(map)) { 181 } 182 183 public: 184 185 RelationsMapIndex() = delete; 186 187 RelationsMapIndex(const RelationsMapIndex&) = delete; 188 RelationsMapIndex& operator=(const RelationsMapIndex&) = delete; 189 190 RelationsMapIndex(RelationsMapIndex&& /*other*/) noexcept(std::is_nothrow_move_constructible<map_type>::value); 191 RelationsMapIndex& operator=(RelationsMapIndex&& /*other*/) noexcept(std::is_nothrow_move_assignable<map_type>::value); 192 193 ~RelationsMapIndex() noexcept = default; 194 195 /** 196 * Find the given relation id in the index and call the given 197 * function with all parent relation ids. 198 * 199 * @code 200 * osmium::unsigned_object_id_type member_id = 17; 201 * index.for_each_parent(member_id, [](osmium::unsigned_object_id_type id) { 202 * ... 203 * }); 204 * @endcode 205 * 206 * @deprecated Use for_each() instead. 207 * 208 * Complexity: Logarithmic in the number of elements in the index. 209 * (Lookup uses binary search.) 210 */ 211 template <typename TFunc> for_each_parent(const osmium::unsigned_object_id_type member_id,TFunc && func) const212 void for_each_parent(const osmium::unsigned_object_id_type member_id, TFunc&& func) const { 213 const auto parents = m_map.get(member_id); 214 for (auto it = parents.first; it != parents.second; ++it) { 215 func(it->value); 216 } 217 } 218 219 /** 220 * Find the given relation id in the index and call the given 221 * function with all related relation ids. 222 * 223 * @code 224 * osmium::unsigned_object_id_type id = 17; 225 * index.for_each(id, [](osmium::unsigned_object_id_type rid) { 226 * ... 227 * }); 228 * @endcode 229 * 230 * Complexity: Logarithmic in the number of elements in the index. 231 * (Lookup uses binary search.) 232 */ 233 template <typename TFunc> for_each(const osmium::unsigned_object_id_type id,TFunc && func) const234 void for_each(const osmium::unsigned_object_id_type id, TFunc&& func) const { 235 const auto parents = m_map.get(id); 236 for (auto it = parents.first; it != parents.second; ++it) { 237 func(it->value); 238 } 239 } 240 241 /** 242 * Is this index empty? 243 * 244 * Complexity: Constant. 245 */ empty() const246 bool empty() const noexcept { 247 return m_map.empty(); 248 } 249 250 /** 251 * How many entries are in this index? 252 * 253 * Complexity: Constant. 254 */ size() const255 std::size_t size() const noexcept { 256 return m_map.size(); 257 } 258 259 }; // class RelationsMapIndex 260 261 // defined outside the class on purpose 262 // see https://akrzemi1.wordpress.com/2015/09/11/declaring-the-move-constructor/ 263 inline RelationsMapIndex::RelationsMapIndex(RelationsMapIndex&&) noexcept(std::is_nothrow_move_constructible<map_type>::value) = default; 264 inline RelationsMapIndex& RelationsMapIndex::operator=(RelationsMapIndex&&) noexcept(std::is_nothrow_move_assignable<map_type>::value) = default; 265 266 class RelationsMapIndexes { 267 268 friend class RelationsMapStash; 269 270 RelationsMapIndex m_member_to_parent; 271 RelationsMapIndex m_parent_to_member; 272 RelationsMapIndexes(RelationsMapIndex::map_type && map1,RelationsMapIndex::map_type && map2)273 RelationsMapIndexes(RelationsMapIndex::map_type&& map1, RelationsMapIndex::map_type&& map2) : 274 m_member_to_parent(std::move(map1)), 275 m_parent_to_member(std::move(map2)) { 276 } 277 278 public: 279 member_to_parent() const280 const RelationsMapIndex& member_to_parent() const noexcept { 281 return m_member_to_parent; 282 } 283 parent_to_member() const284 const RelationsMapIndex& parent_to_member() const noexcept { 285 return m_parent_to_member; 286 } 287 288 /** 289 * Is this index empty? 290 * 291 * Complexity: Constant. 292 */ empty() const293 bool empty() const noexcept { 294 return m_member_to_parent.empty(); 295 } 296 297 /** 298 * How many entries are in this index? 299 * 300 * Complexity: Constant. 301 */ size() const302 std::size_t size() const noexcept { 303 return m_member_to_parent.size(); 304 } 305 306 }; // class RelationsMapIndexes 307 308 /** 309 * The RelationsMapStash is used to build up the data needed to create 310 * an index of member relation ID to parent relation ID or the other 311 * way around. See the RelationsMapIndex class for more. 312 */ 313 class RelationsMapStash { 314 315 using map_type = detail::flat_map<osmium::unsigned_object_id_type, uint32_t, 316 osmium::unsigned_object_id_type, uint32_t>; 317 318 map_type m_map; 319 320 #ifndef NDEBUG 321 bool m_valid = true; 322 #endif 323 324 public: 325 326 RelationsMapStash() = default; 327 328 RelationsMapStash(const RelationsMapStash&) = delete; 329 RelationsMapStash& operator=(const RelationsMapStash&) = delete; 330 331 RelationsMapStash(RelationsMapStash&& /*other*/) noexcept(std::is_nothrow_move_constructible<map_type>::value); 332 RelationsMapStash& operator=(RelationsMapStash&& /*other*/) noexcept(std::is_nothrow_move_assignable<map_type>::value); 333 334 ~RelationsMapStash() noexcept = default; 335 336 /** 337 * Add mapping from member to parent relation in the stash. 338 */ add(const osmium::unsigned_object_id_type member_id,const osmium::unsigned_object_id_type relation_id)339 void add(const osmium::unsigned_object_id_type member_id, const osmium::unsigned_object_id_type relation_id) { 340 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()"); 341 m_map.set(member_id, relation_id); 342 } 343 344 /** 345 * Add mapping from all members to given parent relation in the stash. 346 */ add_members(const osmium::Relation & relation)347 void add_members(const osmium::Relation& relation) { 348 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()"); 349 for (const auto& member : relation.members()) { 350 if (member.type() == osmium::item_type::relation) { 351 m_map.set(member.positive_ref(), relation.positive_id()); 352 } 353 } 354 } 355 356 /** 357 * Is this stash empty? 358 * 359 * Complexity: Constant. 360 */ empty() const361 bool empty() const noexcept { 362 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()"); 363 return m_map.empty(); 364 } 365 366 /** 367 * How many entries are in this stash? 368 * 369 * Complexity: Constant. 370 */ size() const371 std::size_t size() const noexcept { 372 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()"); 373 return m_map.size(); 374 } 375 376 /** 377 * Build an index for member to parent lookups from the contents 378 * of this stash and return it. 379 * 380 * After you get the index you can not use the stash any more! 381 * 382 * @deprecated Use build_member_to_parent_index() instead. 383 */ build_index()384 RelationsMapIndex build_index() { 385 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()"); 386 m_map.sort_unique(); 387 #ifndef NDEBUG 388 m_valid = false; 389 #endif 390 return RelationsMapIndex{std::move(m_map)}; 391 } 392 393 /** 394 * Build an index for member to parent lookups from the contents 395 * of this stash and return it. 396 * 397 * After you get the index you can not use the stash any more! 398 */ build_member_to_parent_index()399 RelationsMapIndex build_member_to_parent_index() { 400 assert(m_valid && "You can't use the RelationsMap any more after calling build_member_to_parent_index()"); 401 m_map.sort_unique(); 402 #ifndef NDEBUG 403 m_valid = false; 404 #endif 405 return RelationsMapIndex{std::move(m_map)}; 406 } 407 408 /** 409 * Build an index for parent to member lookups from the contents 410 * of this stash and return it. 411 * 412 * After you get the index you can not use the stash any more! 413 */ build_parent_to_member_index()414 RelationsMapIndex build_parent_to_member_index() { 415 assert(m_valid && "You can't use the RelationsMap any more after calling build_parent_to_member_index()"); 416 m_map.flip_in_place(); 417 m_map.sort_unique(); 418 #ifndef NDEBUG 419 m_valid = false; 420 #endif 421 return RelationsMapIndex{std::move(m_map)}; 422 } 423 424 /** 425 * Build indexes for member-to-parent and parent-to-member lookups 426 * from the contents of this stash and return them. 427 * 428 * After you get the index you can not use the stash any more! 429 */ build_indexes()430 RelationsMapIndexes build_indexes() { 431 assert(m_valid && "You can't use the RelationsMap any more after calling build_indexes()"); 432 auto reverse_map = m_map.flip_copy(); 433 reverse_map.sort_unique(); 434 m_map.sort_unique(); 435 #ifndef NDEBUG 436 m_valid = false; 437 #endif 438 return RelationsMapIndexes{std::move(m_map), std::move(reverse_map)}; 439 } 440 441 }; // class RelationsMapStash 442 443 // defined outside the class on purpose 444 // see https://akrzemi1.wordpress.com/2015/09/11/declaring-the-move-constructor/ 445 inline RelationsMapStash::RelationsMapStash(RelationsMapStash&&) noexcept(std::is_nothrow_move_constructible<map_type>::value) = default; 446 inline RelationsMapStash& RelationsMapStash::operator=(RelationsMapStash&&) noexcept(std::is_nothrow_move_assignable<map_type>::value) = default; 447 448 } // namespace index 449 450 } // namespace osmium 451 452 #endif // OSMIUM_INDEX_RELATIONS_MAP_HPP 453