KOSMIndoorMap

datatypes.h
1 /*
2  SPDX-FileCopyrightText: 2020 Volker Krause <[email protected]>
3 
4  SPDX-License-Identifier: LGPL-2.0-or-later
5 */
6 
7 #ifndef OSM_DATATYPES_H
8 #define OSM_DATATYPES_H
9 
10 #include "kosm_export.h"
11 #include "internal.h"
12 #include "stringpool.h"
13 
14 #include <QByteArray>
15 #include <QDebug>
16 #include <QLocale>
17 #include <QString>
18 
19 #include <cstdint>
20 #include <cstring>
21 #include <vector>
22 
23 /** Low-level types and functions to work with raw OSM data as efficiently as possible. */
24 namespace OSM {
25 
26 class DataSet;
27 class Member;
28 
29 /** OSM element identifier. */
30 typedef int64_t Id;
31 
32 /** Coordinate, stored as 1e7 * degree to avoid floating point precision issues,
33  * and offset to unsigned values to make the z-order curve work.
34  * Can be in an invalid state with coordinates out of range, see isValid().
35  * @see https://en.wikipedia.org/wiki/Z-order_curve for the z-order curve stuff
36  */
37 class Coordinate {
38 public:
39  Coordinate() = default;
40  explicit constexpr Coordinate(double lat, double lon)
41  : latitude((lat + 90.0) * 10'000'000)
42  , longitude((lon + 180.0) * 10'000'000)
43  {}
44  explicit constexpr Coordinate(uint32_t lat, uint32_t lon)
45  : latitude(lat)
46  , longitude(lon)
47  {}
48 
49  /** Create a coordinate from a z-order curve index. */
50  explicit constexpr Coordinate(uint64_t z)
51  : latitude(0)
52  , longitude(0)
53  {
54  for (int i = 0; i < 32; ++i) {
55  latitude += (z & (1ull << (i * 2))) >> i;
56  longitude += (z & (1ull << (1 + i * 2))) >> (i + 1);
57  }
58  }
59 
60  constexpr inline bool isValid() const
61  {
62  return latitude != std::numeric_limits<uint32_t>::max() && longitude != std::numeric_limits<uint32_t>::max();
63  }
64  constexpr inline bool operator==(Coordinate other) const
65  {
66  return latitude == other.latitude && longitude == other.longitude;
67  }
68 
69  /** Z-order curve value for this coordinate. */
70  constexpr inline uint64_t z() const
71  {
72  uint64_t z = 0;
73  for (int i = 0; i < 32; ++i) {
74  z += ((uint64_t)latitude & (1 << i)) << i;
75  z += ((uint64_t)longitude & (1 << i)) << (i + 1);
76  }
77  return z;
78  }
79 
80  constexpr inline double latF() const
81  {
82  return (latitude / 10'000'000.0) - 90.0;
83  }
84  constexpr inline double lonF() const
85  {
86  return (longitude / 10'000'000.0) - 180.0;
87  }
88 
89  uint32_t latitude = std::numeric_limits<uint32_t>::max();
90  uint32_t longitude = std::numeric_limits<uint32_t>::max();
91 };
92 
93 
94 /** Bounding box, ie. a pair of coordinates. */
95 class BoundingBox {
96 public:
97  constexpr BoundingBox() = default;
98  constexpr inline BoundingBox(Coordinate c1, Coordinate c2)
99  : min(c1)
100  , max(c2)
101  {}
102  constexpr inline bool isValid() const
103  {
104  return min.isValid() && max.isValid();
105  }
106  constexpr inline bool operator==(BoundingBox other) const
107  {
108  return min == other.min && max == other.max;
109  }
110 
111  constexpr inline uint32_t width() const
112  {
113  return max.longitude - min.longitude;
114  }
115  constexpr inline uint32_t height() const
116  {
117  return max.latitude - min.latitude;
118  }
119 
120  constexpr inline double widthF() const
121  {
122  return width() / 10'000'000.0;
123  }
124  constexpr inline double heightF() const
125  {
126  return height() / 10'000'000.0;
127  }
128 
129  constexpr inline Coordinate center() const
130  {
131  return Coordinate(min.latitude + height() / 2, min.longitude + width() / 2);
132  }
133 
134  Coordinate min;
135  Coordinate max;
136 };
137 
138 constexpr inline BoundingBox unite(BoundingBox bbox1, BoundingBox bbox2)
139 {
140  if (!bbox1.isValid()) {
141  return bbox2;
142  }
143  if (!bbox2.isValid()) {
144  return bbox1;
145  }
146  BoundingBox ret;
147  ret.min.latitude = std::min(bbox1.min.latitude, bbox2.min.latitude);
148  ret.min.longitude = std::min(bbox1.min.longitude, bbox2.min.longitude);
149  ret.max.latitude = std::max(bbox1.max.latitude, bbox2.max.latitude);
150  ret.max.longitude = std::max(bbox1.max.longitude, bbox2.max.longitude);
151  return ret;
152 }
153 
154 constexpr inline bool intersects(BoundingBox bbox1, BoundingBox bbox2)
155 {
156  return !(bbox2.min.latitude > bbox1.max.latitude || bbox2.max.latitude < bbox1.min.latitude
157  || bbox2.min.longitude > bbox1.max.longitude || bbox2.max.longitude < bbox1.min.longitude);
158 }
159 
160 constexpr inline bool contains(BoundingBox bbox, Coordinate coord)
161 {
162  return bbox.min.latitude <= coord.latitude && bbox.max.latitude >= coord.latitude
163  && bbox.min.longitude <= coord.longitude && bbox.max.longitude >= coord.longitude;
164 }
165 
166 constexpr inline uint32_t latitudeDistance(BoundingBox bbox1, BoundingBox bbox2)
167 {
168  return bbox1.max.latitude < bbox2.min.latitude ? bbox2.min.latitude - bbox1.max.latitude : bbox1.min.latitude - bbox2.max.latitude;
169 }
170 
171 constexpr inline uint32_t longitudeDifference(BoundingBox bbox1, BoundingBox bbox2)
172 {
173  return bbox1.max.longitude < bbox2.min.longitude ? bbox2.min.longitude - bbox1.max.longitude : bbox1.min.longitude - bbox2.max.longitude;
174 }
175 
176 /** A key of an OSM tag.
177  * See DataSet::tagKey().
178  */
179 class TagKey : public StringKey {};
180 
181 /** An OSM element tag. */
182 class Tag {
183 public:
184  inline constexpr bool operator<(const Tag &other) const { return key < other.key; }
185 
186  TagKey key;
187  QByteArray value;
188 };
189 
190 inline constexpr bool operator<(const Tag &lhs, TagKey rhs) { return lhs.key < rhs; }
191 inline constexpr bool operator<(TagKey lhs, const Tag &rhs) { return lhs < rhs.key; }
192 
193 /** An OSM node. */
194 class KOSM_EXPORT Node {
195 public:
196  constexpr inline bool operator<(const Node &other) const { return id < other.id; }
197 
198  QString url() const;
199 
200  Id id;
201  Coordinate coordinate;
202  std::vector<Tag> tags;
203 };
204 
205 /** An OSM way. */
206 class KOSM_EXPORT Way {
207 public:
208  constexpr inline bool operator<(const Way &other) const { return id < other.id; }
209 
210  bool isClosed() const;
211 
212  QString url() const;
213 
214  Id id;
215  mutable BoundingBox bbox;
216  std::vector<Id> nodes;
217  std::vector<Tag> tags;
218 };
219 
220 /** Element type. */
221 enum class Type : uint8_t {
222  Null,
223  Node,
224  Way,
225  Relation
226 };
227 
228 /** A relation role name key.
229  * See DataSet::role().
230  */
231 class Role : public StringKey
232 {
233 public:
234  constexpr inline Role() = default;
235 private:
236  friend class Member;
237  explicit constexpr inline Role(const char *keyData) : StringKey(keyData) {}
238 };
239 
240 /** A member in a relation. */
241 class Member {
242 public:
243  inline bool operator==(const Member &other) const { return id == other.id && m_roleAndType == other.m_roleAndType; }
244 
245  Id id;
246 
247  constexpr inline Role role() const
248  {
249  return Role(m_roleAndType.get());
250  }
251  constexpr inline void setRole(Role role)
252  {
253  m_roleAndType.set(role.name());
254  }
255 
256  constexpr inline Type type() const
257  {
258  return static_cast<Type>(m_roleAndType.tag());
259  }
260  constexpr inline void setType(Type type)
261  {
262  m_roleAndType.setTag(static_cast<uint8_t>(type));
263  }
264 
265 private:
267 };
268 
269 /** An OSM relation. */
270 class KOSM_EXPORT Relation {
271 public:
272  constexpr inline bool operator<(const Relation &other) const { return id < other.id; }
273 
274  QString url() const;
275 
276  Id id;
277  mutable BoundingBox bbox;
278  std::vector<Member> members;
279  std::vector<Tag> tags;
280 };
281 
282 /** A set of nodes, ways and relations. */
283 class KOSM_EXPORT DataSet {
284 public:
285  explicit DataSet();
286  DataSet(const DataSet&) = delete;
287  DataSet(DataSet &&other);
288  ~DataSet();
289 
290  DataSet& operator=(const DataSet&) = delete;
291  DataSet& operator=(DataSet &&);
292 
293  /** Find a node by its id.
294  * @returns @c nullptr if the node doesn't exist.
295  */
296  const Node* node(Id id) const;
297 
298  /** Find a way by its id.
299  * @returns @c nullptr if the way doesn't exist.
300  */
301  const Way* way(Id id) const;
302  Way* way(Id id);
303 
304  /** Find a relation by its id.
305  * @returns @c nullptr if the relation doesn't exist.
306  */
307  const Relation* relation(Id id) const;
308 
309  void addNode(Node &&node);
310  void addWay(Way &&way);
311  void addRelation(Relation &&rel);
312 
313  /** Look up a tag key for the given tag name, if it exists.
314  * If no key exists, an empty/invalid/null key is returned.
315  * Use this for tag lookup, not for creating/adding tags.
316  */
317  TagKey tagKey(const char *keyName) const;
318 
319  /** Create a tag key for the given tag name. If none exist yet a new one is created.
320  * Use this for creating tags, not for lookup, prefer tagKey() for that.
321  * @param keyMemOpt specifies whether @p keyName is persisent for the lifetime of this
322  * instance and thus can be used without requiring a copy. If the memory is transient
323  * the string is copied if needed, and released in the DataSet destructor.
324  */
325  TagKey makeTagKey(const char *keyName, StringMemory keyMemOpt = StringMemory::Transient);
326 
327  /** Looks up a role name key.
328  * @see tagKey()
329  */
330  Role role(const char *roleName) const;
331  /** Creates a role name key.
332  * @see makeTagKey()
333  */
334  Role makeRole(const char *roleName, StringMemory memOpt = StringMemory::Transient);
335 
336  /** Create a unique id for internal use (ie. one that will not clash with official OSM ids). */
337  Id nextInternalId() const;
338 
339  std::vector<Node> nodes;
340  std::vector<Way> ways;
341  std::vector<Relation> relations;
342 
343 private:
344  template <typename T> T stringKey(const char *name, const std::vector<T> &registry) const;
345  template <typename T> T makeStringKey(const char *name, StringMemory memOpt, std::vector<T> &registry);
346 
347  StringKeyRegistry<TagKey> m_tagKeyRegistry;
348  StringKeyRegistry<Role> m_roleRegistry;
349 };
350 
351 /** Returns the tag value for @p key of @p elem. */
352 template <typename Elem>
353 inline QByteArray tagValue(const Elem& elem, TagKey key)
354 {
355  const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), key);
356  if (it != elem.tags.end() && (*it).key == key) {
357  return (*it).value;
358  }
359  return {};
360 }
361 
362 /** Returns the tag value for key name @p keyName of @p elem.
363  * @warning This is slow due to doing a linear search and string comparissons.
364  * Where possible avoid this in favor of tagValue().
365  */
366 template <typename Elem>
367 inline QByteArray tagValue(const Elem& elem, const char *keyName)
368 {
369  const auto it = std::find_if(elem.tags.begin(), elem.tags.end(), [keyName](const auto &tag) { return std::strcmp(tag.key.name(), keyName) == 0; });
370  if (it != elem.tags.end()) {
371  return (*it).value;
372  }
373  return {};
374 }
375 
376 /** Returns the localized version of the tag value for key name @p keyName of @p elem.
377  * @warning This is slow due to doing a linear search and string comparissons.
378  */
379 template <typename Elem>
380 inline QByteArray tagValue(const Elem& elem, const char *keyName, const QLocale &locale)
381 {
382  QByteArray key(keyName);
383  key.push_back(':');
384  const auto baseLen = key.size();
385  for (const auto &lang : locale.uiLanguages()) {
386  key.resize(baseLen);
387  key.append(lang.toUtf8());
388  const auto it = std::find_if(elem.tags.begin(), elem.tags.end(), [key](const auto &tag) { return std::strcmp(tag.key.name(), key.constData()) == 0; });
389  if (it != elem.tags.end()) {
390  return (*it).value;
391  }
392 
393  const auto idx = lang.indexOf(QLatin1Char('-'));
394  if (idx > 0) {
395  key.resize(baseLen);
396  key.append(lang.leftRef(idx).toUtf8());
397  const auto it = std::find_if(elem.tags.begin(), elem.tags.end(), [key](const auto &tag) { return std::strcmp(tag.key.name(), key.constData()) == 0; });
398  if (it != elem.tags.end()) {
399  return (*it).value;
400  }
401  }
402  }
403 
404  // fall back to generic value, if present
405  const auto v = tagValue(elem, keyName);
406  if (!v.isEmpty()) {
407  return v;
408  }
409 
410  // check if there is at least one in any language we can use
411  key.resize(baseLen);
412  const auto it = std::find_if(elem.tags.begin(), elem.tags.end(), [key, baseLen](const auto &tag) { return std::strncmp(tag.key.name(), key.constData(), baseLen) == 0; });
413  if (it != elem.tags.end()) {
414  return (*it).value;
415  }
416  return {};
417 }
418 
419 /** Inserts a new tag, or replaces an existing one with the same key. */
420 template <typename Elem>
421 inline void setTag(Elem &elem, Tag &&tag)
422 {
423  const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), tag);
424  if (it == elem.tags.end() || (*it).key != tag.key) {
425  elem.tags.insert(it, std::move(tag));
426  } else {
427  (*it) = std::move(tag);
428  }
429 }
430 
431 /** Inserts a new tag, or updates an existing one. */
432 template <typename Elem>
433 inline void setTagValue(Elem &elem, TagKey key, const QByteArray &value)
434 {
435  Tag tag{ key, value };
436  setTag(elem, std::move(tag));
437 }
438 
439 /** Removes a tag from the given element. */
440 template <typename Elem>
441 inline void removeTag(Elem &elem, TagKey key)
442 {
443  const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), key);
444  if (it != elem.tags.end() && (*it).key == key) {
445  elem.tags.erase(it);
446  }
447 }
448 
449 template <typename Elem>
450 inline bool operator<(const Elem &elem, Id id)
451 {
452  return elem.id < id;
453 }
454 
455 }
456 
457 KOSM_EXPORT QDebug operator<<(QDebug debug, OSM::Coordinate coord);
458 KOSM_EXPORT QDebug operator<<(QDebug debug, OSM::BoundingBox bbox);
459 
460 #endif // OSM_DATATYPES_H
Registry of unique string keys.
Definition: stringpool.h:39
Base class for unique string keys.
Definition: stringpool.h:71
void setTag(Elem &elem, Tag &&tag)
Inserts a new tag, or replaces an existing one with the same key.
Definition: datatypes.h:421
void removeTag(Elem &elem, TagKey key)
Removes a tag from the given element.
Definition: datatypes.h:441
Coordinate, stored as 1e7 * degree to avoid floating point precision issues, and offset to unsigned v...
Definition: datatypes.h:37
void resize(int size)
int indexOf(char ch, int from) const const
A key of an OSM tag.
Definition: datatypes.h:179
void setTagValue(Elem &elem, TagKey key, const QByteArray &value)
Inserts a new tag, or updates an existing one.
Definition: datatypes.h:433
QByteArray tagValue(const Elem &elem, TagKey key)
Returns the tag value for key of elem.
Definition: datatypes.h:353
An OSM node.
Definition: datatypes.h:194
const char * constData() const const
int64_t Id
OSM element identifier.
Definition: datatypes.h:27
QByteArray & append(char ch)
void push_back(char ch)
An OSM element tag.
Definition: datatypes.h:182
An OSM way.
Definition: datatypes.h:206
QDataStream & operator<<(QDataStream &out, const KDateTime::Spec &spec)
constexpr Coordinate(uint64_t z)
Create a coordinate from a z-order curve index.
Definition: datatypes.h:50
A relation role name key.
Definition: datatypes.h:231
Type
Element type.
Definition: datatypes.h:221
constexpr uint64_t z() const
Z-order curve value for this coordinate.
Definition: datatypes.h:70
An OSM relation.
Definition: datatypes.h:270
A set of nodes, ways and relations.
Definition: datatypes.h:283
QStringList uiLanguages() const const
Bounding box, ie.
Definition: datatypes.h:95
int size() const const
Low-level types and functions to work with raw OSM data as efficiently as possible.
A member in a relation.
Definition: datatypes.h:241
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Mon Sep 27 2021 23:05:52 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.