Libosmium  2.22.0
Fast and flexible C++ library for working with OpenStreetMap data
relations_map.hpp
Go to the documentation of this file.
1#ifndef OSMIUM_INDEX_RELATIONS_MAP_HPP
2#define OSMIUM_INDEX_RELATIONS_MAP_HPP
3
4/*
5
6This file is part of Osmium (https://osmcode.org/libosmium).
7
8Copyright 2013-2025 Jochen Topf <jochen@topf.org> and others (see README).
9
10Boost Software License - Version 1.0 - August 17th, 2003
11
12Permission is hereby granted, free of charge, to any person or organization
13obtaining a copy of the software and accompanying documentation covered by
14this license (the "Software") to use, reproduce, display, distribute,
15execute, and transmit the Software, and to prepare derivative works of the
16Software, and to permit third-parties to whom the Software is furnished to
17do so, all subject to the following:
18
19The copyright notices in the Software and this entire statement, including
20the above license grant, this restriction and the following disclaimer,
21must be included in all copies of the Software, in whole or in part, and
22all derivative works of the Software, unless such copies or derivative
23works are solely in the form of machine-executable object code generated by
24a source language processor.
25
26THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
27IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
28FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
29SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
30FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
31ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
32DEALINGS IN THE SOFTWARE.
33
34*/
35
38#include <osmium/osm/types.hpp>
39
40#include <algorithm>
41#include <cassert>
42#include <cstddef>
43#include <cstdint>
44#include <limits>
45#include <tuple>
46#include <type_traits>
47#include <utility>
48#include <vector>
49
50namespace osmium {
51
52 namespace index {
53
54 namespace detail {
55
56 template <typename TKey, typename TKeyInternal, typename TValue, typename TValueInternal>
57 class flat_map {
58
59 public:
60
61 using key_type = TKey;
62 using value_type = TValue;
63
64 private:
65
66 struct kv_pair {
67 TKeyInternal key;
68 TValueInternal value;
69
70 explicit kv_pair(const key_type key_id) :
71 key(static_cast<TKeyInternal>(key_id)),
72 value() {
73 }
74
75 kv_pair(const key_type key_id, const value_type value_id) :
76 key(static_cast<TKeyInternal>(key_id)),
77 value(static_cast<TValueInternal>(value_id)) {
78 }
79
80 bool operator<(const kv_pair& other) const noexcept {
81 return std::tie(key, value) < std::tie(other.key, other.value);
82 }
83
84 bool operator==(const kv_pair& other) const noexcept {
85 return std::tie(key, value) == std::tie(other.key, other.value);
86 }
87 }; // struct kv_pair
88
89 std::vector<kv_pair> m_map;
90
91 public:
92
93 using const_iterator = typename std::vector<kv_pair>::const_iterator;
94
95 void set(const key_type key, const value_type value) {
96 m_map.emplace_back(key, value);
97 }
98
99 std::enable_if_t<std::is_same<TKey, TValue>::value> flip_in_place() {
100 for (auto& p : m_map) {
101 using std::swap;
102 swap(p.key, p.value);
103 }
104 }
105
106 flat_map<TValue, TValueInternal, TKey, TKeyInternal> flip_copy() {
107 flat_map<TValue, TValueInternal, TKey, TKeyInternal> map;
108 map.reserve(m_map.size());
109
110 for (const auto& p : m_map) {
111 map.set(p.value, p.key);
112 }
113
114 return map;
115 }
116
117 void sort_unique() {
118 std::sort(m_map.begin(), m_map.end());
119 const auto last = std::unique(m_map.begin(), m_map.end());
120 m_map.erase(last, m_map.end());
121 }
122
123 std::pair<const_iterator, const_iterator> get(const key_type key) const noexcept {
124 return std::equal_range(m_map.begin(), m_map.end(), kv_pair{key}, [](const kv_pair& lhs, const kv_pair& rhs) {
125 return lhs.key < rhs.key;
126 });
127 }
128
129 bool empty() const noexcept {
130 return m_map.empty();
131 }
132
133 std::size_t size() const noexcept {
134 return m_map.size();
135 }
136
137 void reserve(const std::size_t size) {
138 m_map.reserve(size);
139 }
140
141 void clear() {
142 m_map.clear();
143 m_map.shrink_to_fit();
144 }
145
146 typename std::vector<kv_pair>::const_iterator begin() const noexcept {
147 return m_map.cbegin();
148 }
149
150 typename std::vector<kv_pair>::const_iterator end() const noexcept {
151 return m_map.cend();
152 }
153
154 }; // class flat_map
155
156 template <typename VType>
157 using rel_index_map_type = detail::flat_map<osmium::unsigned_object_id_type, VType,
159
160 } // namespace detail
161
188
189 friend class RelationsMapStash;
191
192 detail::rel_index_map_type<uint32_t> m_map32;
193 detail::rel_index_map_type<uint64_t> m_map64;
194
196
197 explicit RelationsMapIndex(detail::rel_index_map_type<uint32_t>&& map) :
198 m_map32(std::move(map)), m_small(true) {
199 }
200
201 explicit RelationsMapIndex(detail::rel_index_map_type<uint64_t>&& map) :
202 m_map64(std::move(map)), m_small(false) {
203 }
204
205 public:
206
208
211
213 RelationsMapIndex& operator=(RelationsMapIndex&& /*other*/) noexcept;
214
215 ~RelationsMapIndex() noexcept = default;
216
231 template <typename TFunc>
232 void for_each(const osmium::unsigned_object_id_type id, TFunc&& func) const {
233 if (m_small) {
234 const auto parents = m_map32.get(id);
235 for (auto it = parents.first; it != parents.second; ++it) {
236 std::forward<TFunc>(func)(it->value);
237 }
238 } else {
239 const auto parents = m_map64.get(id);
240 for (auto it = parents.first; it != parents.second; ++it) {
241 std::forward<TFunc>(func)(it->value);
242 }
243 }
244 }
245
251 bool empty() const noexcept {
252 return m_small ? m_map32.empty() : m_map64.empty();
253 }
254
260 std::size_t size() const noexcept {
261 return m_small ? m_map32.size() : m_map64.size();
262 }
263
264 }; // class RelationsMapIndex
265
266 // defined outside the class on purpose
267 // see https://akrzemi1.wordpress.com/2015/09/11/declaring-the-move-constructor/
268 inline RelationsMapIndex::RelationsMapIndex(RelationsMapIndex&&) noexcept = default; // NOLINT(readability-redundant-inline-specifier)
269 inline RelationsMapIndex& RelationsMapIndex::operator=(RelationsMapIndex&&) noexcept = default; // NOLINT(readability-redundant-inline-specifier)
270
272
273 friend class RelationsMapStash;
274
277
278 RelationsMapIndexes(detail::rel_index_map_type<uint32_t>&& map1, detail::rel_index_map_type<uint32_t>&& map2) :
279 m_member_to_parent(std::move(map1)),
280 m_parent_to_member(std::move(map2)) {
281 }
282
283 RelationsMapIndexes(detail::rel_index_map_type<uint64_t>&& map1, detail::rel_index_map_type<uint64_t>&& map2) :
284 m_member_to_parent(std::move(map1)),
285 m_parent_to_member(std::move(map2)) {
286 }
287
288 public:
289
290 const RelationsMapIndex& member_to_parent() const noexcept {
291 return m_member_to_parent;
292 }
293
294 const RelationsMapIndex& parent_to_member() const noexcept {
295 return m_parent_to_member;
296 }
297
303 bool empty() const noexcept {
304 return m_member_to_parent.empty();
305 }
306
312 std::size_t size() const noexcept {
313 return m_member_to_parent.size();
314 }
315
316 }; // class RelationsMapIndexes
317
324
325 detail::rel_index_map_type<uint32_t> m_map32;
326 detail::rel_index_map_type<uint64_t> m_map64;
327
328#ifndef NDEBUG
329 bool m_valid = true;
330#endif
331
332 static void append32to64(detail::rel_index_map_type<uint32_t>& map32, detail::rel_index_map_type<uint64_t>& map64) {
333 map64.sort_unique();
334 map64.reserve(map64.size() + map32.size());
335 for (const auto& item : map32) {
336 map64.set(item.key, item.value);
337 }
338 map64.sort_unique();
339 map32.clear();
340 }
341
342 public:
343
344 RelationsMapStash() = default;
345
348
350 RelationsMapStash& operator=(RelationsMapStash&& /*other*/) noexcept;
351
352 ~RelationsMapStash() noexcept = default;
353
357 void add(const osmium::unsigned_object_id_type member_id, const osmium::unsigned_object_id_type relation_id) {
358 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
359 constexpr const osmium::unsigned_object_id_type max32 = std::numeric_limits<uint32_t>::max();
360 if (member_id <= max32 && relation_id <= max32) {
361 m_map32.set(member_id, relation_id);
362 } else {
363 m_map64.set(member_id, relation_id);
364 }
365 }
366
370 void add_members(const osmium::Relation& relation) {
371 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
372 for (const auto& member : relation.members()) {
373 if (member.type() == osmium::item_type::relation) {
374 add(member.positive_ref(), relation.positive_id());
375 }
376 }
377 }
378
384 bool empty() const noexcept {
385 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
386 return m_map32.empty() && m_map64.empty();
387 }
388
394 std::size_t size() const noexcept {
395 assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
396 return m_map32.size() + m_map64.size();
397 }
398
405 std::pair<std::size_t, std::size_t> sizes() const noexcept {
406 return std::make_pair(m_map32.size(), m_map64.size());
407 }
408
416 assert(m_valid && "You can't use the RelationsMap any more after calling build_member_to_parent_index()");
417#ifndef NDEBUG
418 m_valid = false;
419#endif
420 m_map32.sort_unique();
421 if (m_map64.empty()) {
422 return RelationsMapIndex{std::move(m_map32)};
423 }
424
426
427 return RelationsMapIndex{std::move(m_map64)};
428 }
429
437 assert(m_valid && "You can't use the RelationsMap any more after calling build_parent_to_member_index()");
438#ifndef NDEBUG
439 m_valid = false;
440#endif
441 m_map32.flip_in_place();
442 m_map32.sort_unique();
443 if (m_map64.empty()) {
444 return RelationsMapIndex{std::move(m_map32)};
445 }
446
447 m_map64.flip_in_place();
449
450 return RelationsMapIndex{std::move(m_map64)};
451 }
452
460 assert(m_valid && "You can't use the RelationsMap any more after calling build_indexes()");
461#ifndef NDEBUG
462 m_valid = false;
463#endif
464 auto reverse_map32 = m_map32.flip_copy();
465 reverse_map32.sort_unique();
466 m_map32.sort_unique();
467 if (m_map64.empty()) {
468 return RelationsMapIndexes{std::move(m_map32), std::move(reverse_map32)};
469 }
470
471 auto reverse_map64 = m_map64.flip_copy();
472 append32to64(reverse_map32, reverse_map64);
474
475 return RelationsMapIndexes{std::move(m_map64), std::move(reverse_map64)};
476 }
477
478 }; // class RelationsMapStash
479
480 // defined outside the class on purpose
481 // see https://akrzemi1.wordpress.com/2015/09/11/declaring-the-move-constructor/
482 inline RelationsMapStash::RelationsMapStash(RelationsMapStash&&) noexcept = default; // NOLINT(readability-redundant-inline-specifier)
483 inline RelationsMapStash& RelationsMapStash::operator=(RelationsMapStash&&) noexcept = default; // NOLINT(readability-redundant-inline-specifier)
484
485 } // namespace index
486
487} // namespace osmium
488
489#endif // OSMIUM_INDEX_RELATIONS_MAP_HPP
Definition: relation.hpp:161
Definition: relations_map.hpp:187
RelationsMapIndex(const RelationsMapIndex &)=delete
RelationsMapIndex(detail::rel_index_map_type< uint64_t > &&map)
Definition: relations_map.hpp:201
std::size_t size() const noexcept
Definition: relations_map.hpp:260
detail::rel_index_map_type< uint64_t > m_map64
Definition: relations_map.hpp:193
void for_each(const osmium::unsigned_object_id_type id, TFunc &&func) const
Definition: relations_map.hpp:232
RelationsMapIndex(detail::rel_index_map_type< uint32_t > &&map)
Definition: relations_map.hpp:197
RelationsMapIndex & operator=(const RelationsMapIndex &)=delete
RelationsMapIndex(RelationsMapIndex &&) noexcept
bool empty() const noexcept
Definition: relations_map.hpp:251
detail::rel_index_map_type< uint32_t > m_map32
Definition: relations_map.hpp:192
bool m_small
Definition: relations_map.hpp:195
Definition: relations_map.hpp:271
const RelationsMapIndex & parent_to_member() const noexcept
Definition: relations_map.hpp:294
const RelationsMapIndex & member_to_parent() const noexcept
Definition: relations_map.hpp:290
std::size_t size() const noexcept
Definition: relations_map.hpp:312
bool empty() const noexcept
Definition: relations_map.hpp:303
RelationsMapIndex m_member_to_parent
Definition: relations_map.hpp:275
RelationsMapIndexes(detail::rel_index_map_type< uint32_t > &&map1, detail::rel_index_map_type< uint32_t > &&map2)
Definition: relations_map.hpp:278
RelationsMapIndexes(detail::rel_index_map_type< uint64_t > &&map1, detail::rel_index_map_type< uint64_t > &&map2)
Definition: relations_map.hpp:283
RelationsMapIndex m_parent_to_member
Definition: relations_map.hpp:276
Definition: relations_map.hpp:323
detail::rel_index_map_type< uint32_t > m_map32
Definition: relations_map.hpp:325
RelationsMapIndex build_member_to_parent_index()
Definition: relations_map.hpp:415
bool m_valid
Definition: relations_map.hpp:329
std::size_t size() const noexcept
Definition: relations_map.hpp:394
RelationsMapIndexes build_indexes()
Definition: relations_map.hpp:459
RelationsMapIndex build_parent_to_member_index()
Definition: relations_map.hpp:436
static void append32to64(detail::rel_index_map_type< uint32_t > &map32, detail::rel_index_map_type< uint64_t > &map64)
Definition: relations_map.hpp:332
detail::rel_index_map_type< uint64_t > m_map64
Definition: relations_map.hpp:326
void add_members(const osmium::Relation &relation)
Definition: relations_map.hpp:370
RelationsMapStash & operator=(const RelationsMapStash &)=delete
std::pair< std::size_t, std::size_t > sizes() const noexcept
Definition: relations_map.hpp:405
RelationsMapStash(RelationsMapStash &&) noexcept
bool empty() const noexcept
Definition: relations_map.hpp:384
RelationsMapStash(const RelationsMapStash &)=delete
void add(const osmium::unsigned_object_id_type member_id, const osmium::unsigned_object_id_type relation_id)
Definition: relations_map.hpp:357
Definition: attr.hpp:342
InputIterator< Reader > end(Reader &)
Definition: reader_iterator.hpp:47
InputIterator< Reader > begin(Reader &reader)
Definition: reader_iterator.hpp:43
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
bool operator==(const Changeset &lhs, const Changeset &rhs)
Definition: changeset.hpp:440
uint64_t unsigned_object_id_type
Type for OSM object (node, way, or relation) IDs where we only allow positive IDs.
Definition: types.hpp:46
bool operator<(const Changeset &lhs, const Changeset &rhs)
Definition: changeset.hpp:451
Definition: location.hpp:555