Libosmium  2.12.2
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 
6 This file is part of Osmium (http://osmcode.org/libosmium).
7 
8 Copyright 2013-2017 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 <algorithm>
37 #include <cassert>
38 #include <cstdint>
39 #include <tuple>
40 #include <vector>
41 
42 #include <osmium/osm/relation.hpp>
43 #include <osmium/osm/types.hpp>
44 
45 namespace osmium {
46 
47  namespace index {
48 
49  namespace detail {
50 
51  template <typename TKey, typename TKeyInternal, typename TValue, typename TValueInternal>
52  class flat_map {
53 
54  public:
55 
56  using key_type = TKey;
57  using value_type = TValue;
58 
59  private:
60 
61  struct kv_pair {
62  TKeyInternal key;
63  TValueInternal value;
64 
65  explicit kv_pair(key_type key_id) :
66  key(static_cast<TKeyInternal>(key_id)),
67  value() {
68  }
69 
70  kv_pair(key_type key_id, value_type value_id) :
71  key(static_cast<TKeyInternal>(key_id)),
72  value(static_cast<TValueInternal>(value_id)) {
73  }
74 
75  bool operator<(const kv_pair& other) const noexcept {
76  return std::tie(key, value) < std::tie(other.key, other.value);
77  }
78 
79  bool operator==(const kv_pair& other) const noexcept {
80  return std::tie(key, value) == std::tie(other.key, other.value);
81  }
82  }; // struct kv_pair
83 
84  std::vector<kv_pair> m_map;
85 
86  public:
87 
88  using const_iterator = typename std::vector<kv_pair>::const_iterator;
89 
90  void set(key_type key, value_type value) {
91  m_map.emplace_back(key, value);
92  }
93 
94  typename std::enable_if<std::is_same<TKey, TValue>::value>::type flip_in_place() {
95  for (auto& p : m_map) {
96  using std::swap;
97  swap(p.key, p.value);
98  }
99  }
100 
101  flat_map<TValue, TValueInternal, TKey, TKeyInternal> flip_copy() {
102  flat_map<TValue, TValueInternal, TKey, TKeyInternal> map;
103  map.reserve(m_map.size());
104 
105  for (const auto& p : m_map) {
106  map.set(p.value, p.key);
107  }
108 
109  return map;
110  }
111 
112  void sort_unique() {
113  std::sort(m_map.begin(), m_map.end());
114  const auto last = std::unique(m_map.begin(), m_map.end());
115  m_map.erase(last, m_map.end());
116  }
117 
118  std::pair<const_iterator, const_iterator> get(key_type key) const noexcept {
119  return std::equal_range(m_map.begin(), m_map.end(), kv_pair{key}, [](const kv_pair& lhs, const kv_pair& rhs) {
120  return lhs.key < rhs.key;
121  });
122  }
123 
124  bool empty() const noexcept {
125  return m_map.empty();
126  }
127 
128  size_t size() const noexcept {
129  return m_map.size();
130  }
131 
132  void reserve(size_t size) {
133  m_map.reserve(size);
134  }
135 
136  }; // class flat_map
137 
138  } // namespace detail
139 
166 
167  friend class RelationsMapStash;
168  friend class RelationsMapIndexes;
169 
170  using map_type = detail::flat_map<osmium::unsigned_object_id_type, uint32_t,
172 
174 
176  m_map(std::move(map)) {
177  }
178 
179  public:
180 
181  RelationsMapIndex() = delete;
182 
183  RelationsMapIndex(const RelationsMapIndex&) = delete;
184  RelationsMapIndex& operator=(const RelationsMapIndex&) = delete;
185 
187  RelationsMapIndex& operator=(RelationsMapIndex&&) = default;
188 
205  template <typename TFunc>
206  void for_each_parent(osmium::unsigned_object_id_type member_id, TFunc&& func) const {
207  const auto parents = m_map.get(member_id);
208  for (auto it = parents.first; it != parents.second; ++it) {
209  std::forward<TFunc>(func)(it->value);
210  }
211  }
212 
227  template <typename TFunc>
228  void for_each(osmium::unsigned_object_id_type id, TFunc&& func) const {
229  const auto parents = m_map.get(id);
230  for (auto it = parents.first; it != parents.second; ++it) {
231  std::forward<TFunc>(func)(it->value);
232  }
233  }
234 
240  bool empty() const noexcept {
241  return m_map.empty();
242  }
243 
249  size_t size() const noexcept {
250  return m_map.size();
251  }
252 
253  }; // class RelationsMapIndex
254 
256 
257  friend class RelationsMapStash;
258 
261 
263  m_member_to_parent(std::move(map1)),
264  m_parent_to_member(std::move(map2)) {
265  }
266 
267  public:
268 
269  const RelationsMapIndex& member_to_parent() const noexcept {
270  return m_member_to_parent;
271  }
272 
273  const RelationsMapIndex& parent_to_member() const noexcept {
274  return m_parent_to_member;
275  }
276 
282  bool empty() const noexcept {
283  return m_member_to_parent.empty();
284  }
285 
291  size_t size() const noexcept {
292  return m_member_to_parent.size();
293  }
294 
295  }; // class RelationsMapIndexes
296 
303 
304  using map_type = detail::flat_map<osmium::unsigned_object_id_type, uint32_t,
306 
308 
309 #ifndef NDEBUG
310  bool m_valid = true;
311 #endif
312 
313  public:
314 
315  RelationsMapStash() = default;
316 
317  RelationsMapStash(const RelationsMapStash&) = delete;
318  RelationsMapStash& operator=(const RelationsMapStash&) = delete;
319 
321  RelationsMapStash& operator=(RelationsMapStash&&) = default;
322 
326  void add(osmium::unsigned_object_id_type member_id, osmium::unsigned_object_id_type relation_id) {
327  assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
328  m_map.set(member_id, relation_id);
329  }
330 
334  void add_members(const osmium::Relation& relation) {
335  assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
336  for (const auto& member : relation.members()) {
337  if (member.type() == osmium::item_type::relation) {
338  m_map.set(member.positive_ref(), relation.positive_id());
339  }
340  }
341  }
342 
348  bool empty() const noexcept {
349  assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
350  return m_map.empty();
351  }
352 
358  size_t size() const noexcept {
359  assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
360  return m_map.size();
361  }
362 
372  assert(m_valid && "You can't use the RelationsMap any more after calling build_index()");
373  m_map.sort_unique();
374 #ifndef NDEBUG
375  m_valid = false;
376 #endif
377  return RelationsMapIndex{std::move(m_map)};
378  }
379 
387  assert(m_valid && "You can't use the RelationsMap any more after calling build_member_to_parent_index()");
388  m_map.sort_unique();
389 #ifndef NDEBUG
390  m_valid = false;
391 #endif
392  return RelationsMapIndex{std::move(m_map)};
393  }
394 
402  assert(m_valid && "You can't use the RelationsMap any more after calling build_parent_to_member_index()");
403  m_map.flip_in_place();
404  m_map.sort_unique();
405 #ifndef NDEBUG
406  m_valid = false;
407 #endif
408  return RelationsMapIndex{std::move(m_map)};
409  }
410 
418  assert(m_valid && "You can't use the RelationsMap any more after calling build_indexes()");
419  auto reverse_map = m_map.flip_copy();
420  reverse_map.sort_unique();
421  m_map.sort_unique();
422 #ifndef NDEBUG
423  m_valid = false;
424 #endif
425  return RelationsMapIndexes{std::move(m_map), std::move(reverse_map)};
426  }
427 
428  }; // class RelationsMapStash
429 
430  } // namespace index
431 
432 } // namespace osmium
433 
434 #endif // OSMIUM_INDEX_RELATIONS_MAP_HPP
type
Definition: entity_bits.hpp:63
RelationMemberList & members()
Definition: relation.hpp:185
const RelationsMapIndex & parent_to_member() const noexcept
Definition: relations_map.hpp:273
constexpr bool operator==(const Box &lhs, const Box &rhs) noexcept
Definition: box.hpp:221
Definition: relation.hpp:168
RelationsMapIndex build_index()
Definition: relations_map.hpp:371
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
void for_each_parent(osmium::unsigned_object_id_type member_id, TFunc &&func) const
Definition: relations_map.hpp:206
Definition: reader_iterator.hpp:39
void swap(Buffer &lhs, Buffer &rhs)
Definition: buffer.hpp:765
Definition: relations_map.hpp:165
RelationsMapIndexes(RelationsMapIndex::map_type &&map1, RelationsMapIndex::map_type &&map2)
Definition: relations_map.hpp:262
Definition: relations_map.hpp:255
RelationsMapIndex build_parent_to_member_index()
Definition: relations_map.hpp:401
size_t size() const noexcept
Definition: relations_map.hpp:358
bool empty() const noexcept
Definition: relations_map.hpp:240
detail::flat_map< osmium::unsigned_object_id_type, uint32_t, osmium::unsigned_object_id_type, uint32_t > map_type
Definition: relations_map.hpp:171
RelationsMapIndexes build_indexes()
Definition: relations_map.hpp:417
RelationsMapIndex(map_type &&map)
Definition: relations_map.hpp:175
bool operator<(const Changeset &lhs, const Changeset &rhs)
Definition: changeset.hpp:447
Namespace for everything in the Osmium library.
Definition: assembler.hpp:63
Definition: attr.hpp:333
RelationsMapIndex m_member_to_parent
Definition: relations_map.hpp:259
void add(osmium::unsigned_object_id_type member_id, osmium::unsigned_object_id_type relation_id)
Definition: relations_map.hpp:326
Definition: relations_map.hpp:302
const RelationsMapIndex & member_to_parent() const noexcept
Definition: relations_map.hpp:269
bool empty() const noexcept
Definition: relations_map.hpp:282
map_type m_map
Definition: relations_map.hpp:173
size_t size() const noexcept
Definition: relations_map.hpp:291
void add_members(const osmium::Relation &relation)
Definition: relations_map.hpp:334
detail::flat_map< osmium::unsigned_object_id_type, uint32_t, osmium::unsigned_object_id_type, uint32_t > map_type
Definition: relations_map.hpp:305
RelationsMapIndex build_member_to_parent_index()
Definition: relations_map.hpp:386
void for_each(osmium::unsigned_object_id_type id, TFunc &&func) const
Definition: relations_map.hpp:228
map_type m_map
Definition: relations_map.hpp:307
size_t size() const noexcept
Definition: relations_map.hpp:249
unsigned_object_id_type positive_id() const noexcept
Get absolute value of the ID of this object.
Definition: object.hpp:131
RelationsMapIndex m_parent_to_member
Definition: relations_map.hpp:260
bool empty() const noexcept
Definition: relations_map.hpp:348