File indexing completed on 2024-05-12 04:42:17
0001 /* 0002 SPDX-FileCopyrightText: 2020 Volker Krause <vkrause@kde.org> 0003 0004 SPDX-License-Identifier: LGPL-2.0-or-later 0005 */ 0006 0007 #ifndef OSM_DATATYPES_H 0008 #define OSM_DATATYPES_H 0009 0010 #include "kosm_export.h" 0011 #include "internal.h" 0012 #include "languages.h" 0013 #include "stringpool.h" 0014 0015 #include <QByteArray> 0016 #include <QDebug> 0017 #include <QString> 0018 0019 #include <cstdint> 0020 #include <cstring> 0021 #include <vector> 0022 0023 /** Low-level types and functions to work with raw OSM data as efficiently as possible. */ 0024 namespace OSM { 0025 0026 class DataSet; 0027 class Member; 0028 0029 /** OSM element identifier. */ 0030 typedef int64_t Id; 0031 0032 /** Coordinate, stored as 1e7 * degree to avoid floating point precision issues, 0033 * and offset to unsigned values to make the z-order curve work. 0034 * Can be in an invalid state with coordinates out of range, see isValid(). 0035 * @see https://en.wikipedia.org/wiki/Z-order_curve for the z-order curve stuff 0036 */ 0037 class Coordinate { 0038 public: 0039 Coordinate() = default; 0040 explicit constexpr Coordinate(double lat, double lon) 0041 : latitude((lat + 90.0) * 10'000'000) 0042 , longitude((lon + 180.0) * 10'000'000) 0043 {} 0044 explicit constexpr Coordinate(uint32_t lat, uint32_t lon) 0045 : latitude(lat) 0046 , longitude(lon) 0047 {} 0048 0049 /** Create a coordinate from a z-order curve index. */ 0050 explicit constexpr Coordinate(uint64_t z) 0051 : latitude(0) 0052 , longitude(0) 0053 { 0054 for (int i = 0; i < 32; ++i) { 0055 latitude += (z & (1ull << (i * 2))) >> i; 0056 longitude += (z & (1ull << (1 + i * 2))) >> (i + 1); 0057 } 0058 } 0059 0060 [[nodiscard]] constexpr inline bool isValid() const 0061 { 0062 return latitude != std::numeric_limits<uint32_t>::max() && longitude != std::numeric_limits<uint32_t>::max(); 0063 } 0064 [[nodiscard]] constexpr inline bool operator==(Coordinate other) const 0065 { 0066 return latitude == other.latitude && longitude == other.longitude; 0067 } 0068 0069 /** Z-order curve value for this coordinate. */ 0070 [[nodiscard]] constexpr inline uint64_t z() const 0071 { 0072 uint64_t z = 0; 0073 for (int i = 0; i < 32; ++i) { 0074 z += ((uint64_t)latitude & (1 << i)) << i; 0075 z += ((uint64_t)longitude & (1 << i)) << (i + 1); 0076 } 0077 return z; 0078 } 0079 0080 [[nodiscard]] constexpr inline double latF() const 0081 { 0082 return (latitude / 10'000'000.0) - 90.0; 0083 } 0084 [[nodiscard]] constexpr inline double lonF() const 0085 { 0086 return (longitude / 10'000'000.0) - 180.0; 0087 } 0088 0089 uint32_t latitude = std::numeric_limits<uint32_t>::max(); 0090 uint32_t longitude = std::numeric_limits<uint32_t>::max(); 0091 }; 0092 0093 0094 /** Bounding box, ie. a pair of coordinates. */ 0095 class BoundingBox { 0096 public: 0097 constexpr BoundingBox() = default; 0098 constexpr inline BoundingBox(Coordinate c1, Coordinate c2) 0099 : min(c1) 0100 , max(c2) 0101 {} 0102 [[nodiscard]] constexpr inline bool isValid() const 0103 { 0104 return min.isValid() && max.isValid(); 0105 } 0106 [[nodiscard]] constexpr inline bool operator==(BoundingBox other) const 0107 { 0108 return min == other.min && max == other.max; 0109 } 0110 0111 [[nodiscard]] constexpr inline uint32_t width() const 0112 { 0113 return max.longitude - min.longitude; 0114 } 0115 [[nodiscard]] constexpr inline uint32_t height() const 0116 { 0117 return max.latitude - min.latitude; 0118 } 0119 0120 [[nodiscard]] constexpr inline double widthF() const 0121 { 0122 return width() / 10'000'000.0; 0123 } 0124 [[nodiscard]] constexpr inline double heightF() const 0125 { 0126 return height() / 10'000'000.0; 0127 } 0128 0129 [[nodiscard]] constexpr inline Coordinate center() const 0130 { 0131 return Coordinate(min.latitude + height() / 2, min.longitude + width() / 2); 0132 } 0133 0134 Coordinate min; 0135 Coordinate max; 0136 }; 0137 0138 [[nodiscard]] constexpr inline BoundingBox unite(BoundingBox bbox1, BoundingBox bbox2) 0139 { 0140 if (!bbox1.isValid()) { 0141 return bbox2; 0142 } 0143 if (!bbox2.isValid()) { 0144 return bbox1; 0145 } 0146 BoundingBox ret; 0147 ret.min.latitude = std::min(bbox1.min.latitude, bbox2.min.latitude); 0148 ret.min.longitude = std::min(bbox1.min.longitude, bbox2.min.longitude); 0149 ret.max.latitude = std::max(bbox1.max.latitude, bbox2.max.latitude); 0150 ret.max.longitude = std::max(bbox1.max.longitude, bbox2.max.longitude); 0151 return ret; 0152 } 0153 0154 [[nodiscard]] constexpr inline bool intersects(BoundingBox bbox1, BoundingBox bbox2) 0155 { 0156 return !(bbox2.min.latitude > bbox1.max.latitude || bbox2.max.latitude < bbox1.min.latitude 0157 || bbox2.min.longitude > bbox1.max.longitude || bbox2.max.longitude < bbox1.min.longitude); 0158 } 0159 0160 [[nodiscard]] constexpr inline bool contains(BoundingBox bbox, Coordinate coord) 0161 { 0162 return bbox.min.latitude <= coord.latitude && bbox.max.latitude >= coord.latitude 0163 && bbox.min.longitude <= coord.longitude && bbox.max.longitude >= coord.longitude; 0164 } 0165 0166 [[nodiscard]] constexpr inline uint32_t latitudeDistance(BoundingBox bbox1, BoundingBox bbox2) 0167 { 0168 return bbox1.max.latitude < bbox2.min.latitude ? bbox2.min.latitude - bbox1.max.latitude : bbox1.min.latitude - bbox2.max.latitude; 0169 } 0170 0171 [[nodiscard]] constexpr inline uint32_t longitudeDifference(BoundingBox bbox1, BoundingBox bbox2) 0172 { 0173 return bbox1.max.longitude < bbox2.min.longitude ? bbox2.min.longitude - bbox1.max.longitude : bbox1.min.longitude - bbox2.max.longitude; 0174 } 0175 0176 /** A key of an OSM tag. 0177 * See DataSet::tagKey(). 0178 */ 0179 class TagKey : public StringKey {}; 0180 0181 /** An OSM element tag. */ 0182 class Tag { 0183 public: 0184 Tag() = default; 0185 inline Tag(TagKey _key, QByteArray &&_value) 0186 : key(_key) 0187 , value(std::move(_value)) 0188 {} 0189 Tag(const Tag&) = default; 0190 Tag(Tag &&Tag) noexcept = default; 0191 Tag& operator=(const Tag &other) = default; 0192 Tag& operator=(Tag &&other) noexcept = default; 0193 0194 [[nodiscard]] inline constexpr bool operator<(const Tag &other) const { return key < other.key; } 0195 0196 TagKey key; 0197 QByteArray value; 0198 }; 0199 0200 [[nodiscard]] inline constexpr bool operator<(const Tag &lhs, TagKey rhs) { return lhs.key < rhs; } 0201 [[nodiscard]] inline constexpr bool operator<(TagKey lhs, const Tag &rhs) { return lhs < rhs.key; } 0202 0203 /** An OSM node. */ 0204 class KOSM_EXPORT Node { 0205 public: 0206 explicit Node() = default; 0207 Node(const Node&) = default; 0208 Node(Node &&other) noexcept 0209 { 0210 *this = std::move(other); 0211 } 0212 Node& operator=(const Node &other) = default; 0213 Node& operator=(Node &&other) noexcept 0214 { 0215 id = other.id; 0216 coordinate = other.coordinate; 0217 std::swap(tags, other.tags); 0218 return *this; 0219 } 0220 0221 [[nodiscard]] constexpr inline bool operator<(const Node &other) const { return id < other.id; } 0222 0223 [[nodiscard]] QString url() const; 0224 0225 Id id; 0226 Coordinate coordinate; 0227 std::vector<Tag> tags; 0228 }; 0229 0230 /** An OSM way. */ 0231 class KOSM_EXPORT Way { 0232 public: 0233 explicit Way() = default; 0234 Way(const Way&) = default; 0235 Way(Way &&other) noexcept 0236 { 0237 *this = std::move(other); 0238 } 0239 Way& operator=(const Way &other) = default; 0240 Way& operator=(Way &&other) noexcept 0241 { 0242 id = other.id; 0243 bbox = other.bbox; 0244 std::swap(nodes, other.nodes); 0245 std::swap(tags, other.tags); 0246 return *this; 0247 } 0248 0249 constexpr inline bool operator<(const Way &other) const { return id < other.id; } 0250 0251 bool isClosed() const; 0252 0253 QString url() const; 0254 0255 Id id; 0256 mutable BoundingBox bbox; 0257 std::vector<Id> nodes; 0258 std::vector<Tag> tags; 0259 }; 0260 0261 /** Element type. */ 0262 enum class Type : uint8_t { 0263 Null, 0264 Node, 0265 Way, 0266 Relation 0267 }; 0268 0269 /** A relation role name key. 0270 * See DataSet::role(). 0271 */ 0272 class Role : public StringKey 0273 { 0274 public: 0275 constexpr inline Role() = default; 0276 private: 0277 friend class Member; 0278 explicit constexpr inline Role(const char *keyData) : StringKey(keyData) {} 0279 }; 0280 0281 /** A member in a relation. */ 0282 class Member { 0283 public: 0284 [[nodiscard]] inline bool operator==(const Member &other) const { return id == other.id && m_roleAndType == other.m_roleAndType; } 0285 0286 Id id; 0287 0288 [[nodiscard]] constexpr inline Role role() const 0289 { 0290 return Role(m_roleAndType.get()); 0291 } 0292 constexpr inline void setRole(Role role) 0293 { 0294 m_roleAndType.set(role.name()); 0295 } 0296 0297 [[nodiscard]] constexpr inline Type type() const 0298 { 0299 return static_cast<Type>(m_roleAndType.tag()); 0300 } 0301 constexpr inline void setType(Type type) 0302 { 0303 m_roleAndType.setTag(static_cast<uint8_t>(type)); 0304 } 0305 0306 private: 0307 Internal::TaggedPointer<const char> m_roleAndType; 0308 }; 0309 0310 /** An OSM relation. */ 0311 class KOSM_EXPORT Relation { 0312 public: 0313 explicit Relation() = default; 0314 Relation(const Relation&) = default; 0315 Relation(Relation &&other) noexcept 0316 { 0317 *this = std::move(other); 0318 } 0319 Relation& operator=(const Relation &other) = default; 0320 Relation& operator=(Relation &&other) noexcept 0321 { 0322 id = other.id; 0323 bbox = other.bbox; 0324 std::swap(members, other.members); 0325 std::swap(tags, other.tags); 0326 return *this; 0327 } 0328 0329 [[nodiscard]] constexpr inline bool operator<(const Relation &other) const { return id < other.id; } 0330 0331 [[nodiscard]] QString url() const; 0332 0333 Id id; 0334 mutable BoundingBox bbox; 0335 std::vector<Member> members; 0336 std::vector<Tag> tags; 0337 }; 0338 0339 /** A set of nodes, ways and relations. */ 0340 class KOSM_EXPORT DataSet { 0341 public: 0342 explicit DataSet(); 0343 DataSet(const DataSet&) = delete; 0344 DataSet(DataSet &&other) noexcept; 0345 ~DataSet(); 0346 0347 DataSet& operator=(const DataSet&) = delete; 0348 DataSet& operator=(DataSet &&) noexcept; 0349 0350 /** Find a node by its id. 0351 * @returns @c nullptr if the node doesn't exist. 0352 */ 0353 [[nodiscard]] const Node* node(Id id) const; 0354 0355 /** Find a way by its id. 0356 * @returns @c nullptr if the way doesn't exist. 0357 */ 0358 [[nodiscard]] const Way* way(Id id) const; 0359 [[nodiscard]] Way* way(Id id); 0360 0361 /** Find a relation by its id. 0362 * @returns @c nullptr if the relation doesn't exist. 0363 */ 0364 [[nodiscard]] const Relation* relation(Id id) const; 0365 0366 void addNode(Node &&node); 0367 void addWay(Way &&way); 0368 void addRelation(Relation &&rel); 0369 0370 /** Look up a tag key for the given tag name, if it exists. 0371 * If no key exists, an empty/invalid/null key is returned. 0372 * Use this for tag lookup, not for creating/adding tags. 0373 */ 0374 [[nodiscard]] TagKey tagKey(const char *keyName) const; 0375 0376 /** Create a tag key for the given tag name. If none exist yet a new one is created. 0377 * Use this for creating tags, not for lookup, prefer tagKey() for that. 0378 * @param keyMemOpt specifies whether @p keyName is persisent for the lifetime of this 0379 * instance and thus can be used without requiring a copy. If the memory is transient 0380 * the string is copied if needed, and released in the DataSet destructor. 0381 */ 0382 [[nodiscard]] TagKey makeTagKey(const char *keyName, StringMemory keyMemOpt = StringMemory::Transient); 0383 0384 /** Looks up a role name key. 0385 * @see tagKey() 0386 */ 0387 [[nodiscard]] Role role(const char *roleName) const; 0388 /** Creates a role name key. 0389 * @see makeTagKey() 0390 */ 0391 [[nodiscard]] Role makeRole(const char *roleName, StringMemory memOpt = StringMemory::Transient); 0392 0393 /** Create a unique id for internal use (ie. one that will not clash with official OSM ids). */ 0394 [[nodiscard]] Id nextInternalId() const; 0395 0396 std::vector<Node> nodes; 0397 std::vector<Way> ways; 0398 std::vector<Relation> relations; 0399 0400 private: 0401 template <typename T> T stringKey(const char *name, const std::vector<T> ®istry) const; 0402 template <typename T> T makeStringKey(const char *name, StringMemory memOpt, std::vector<T> ®istry); 0403 0404 StringKeyRegistry<TagKey> m_tagKeyRegistry; 0405 StringKeyRegistry<Role> m_roleRegistry; 0406 }; 0407 0408 /** Returns the tag value for @p key of @p elem. */ 0409 template <typename Elem> 0410 [[nodiscard]] inline QByteArray tagValue(const Elem& elem, TagKey key) 0411 { 0412 const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), key); 0413 if (it != elem.tags.end() && (*it).key == key) { 0414 return (*it).value; 0415 } 0416 return {}; 0417 } 0418 0419 /** Returns the tag value for key name @p keyName of @p elem. 0420 * @warning This is slow due to doing a linear search and string comparissons. 0421 * Where possible avoid this in favor of tagValue(). 0422 */ 0423 template <typename Elem> 0424 [[nodiscard]] inline QByteArray tagValue(const Elem& elem, const char *keyName) 0425 { 0426 const auto it = std::find_if(elem.tags.begin(), elem.tags.end(), [keyName](const auto &tag) { return std::strcmp(tag.key.name(), keyName) == 0; }); 0427 if (it != elem.tags.end()) { 0428 return (*it).value; 0429 } 0430 return {}; 0431 } 0432 0433 /** Returns the localized version of the tag value for key name @p keyName of @p elem. 0434 * @warning This is slow due to doing a linear search and string comparissons. 0435 */ 0436 template <typename Elem> 0437 [[nodiscard]] inline QByteArray tagValue(const Elem& elem, const OSM::Languages &languages, const char *keyName) 0438 { 0439 const auto keyLen = std::strlen(keyName); 0440 for (const auto &lang : languages.languages) { 0441 for (const auto &tag : elem.tags) { 0442 if (std::strlen(tag.key.name()) != keyLen + lang.size() + 1) { 0443 continue; 0444 } 0445 if (std::strncmp(tag.key.name(), keyName, keyLen) == 0 && tag.key.name()[keyLen] == ':' 0446 && std::strncmp(tag.key.name() + keyLen + 1, lang.c_str(), lang.size()) == 0) { 0447 return tag.value; 0448 } 0449 } 0450 } 0451 0452 // fall back to generic value, if present 0453 const auto v = tagValue(elem, keyName); 0454 if (!v.isEmpty()) { 0455 return v; 0456 } 0457 0458 // check if there is at least one in any language we can use 0459 const auto it = std::find_if(elem.tags.begin(), elem.tags.end(), [keyName, keyLen](const auto &tag) { 0460 return std::strlen(tag.key.name()) == keyLen + 3 // primitive check whether this is a plausible language rather than some other qualifier 0461 && std::strncmp(tag.key.name(), keyName, keyLen) == 0 0462 && tag.key.name()[keyLen] == ':'; 0463 }); 0464 if (it != elem.tags.end()) { 0465 return (*it).value; 0466 } 0467 return {}; 0468 } 0469 0470 /** Inserts a new tag, or replaces an existing one with the same key. */ 0471 template <typename Elem> 0472 inline void setTag(Elem &elem, Tag &&tag) 0473 { 0474 const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), tag); 0475 if (it == elem.tags.end() || (*it).key != tag.key) { 0476 elem.tags.insert(it, std::move(tag)); 0477 } else { 0478 (*it) = std::move(tag); 0479 } 0480 } 0481 0482 /** Inserts a new tag, or updates an existing one. */ 0483 template <typename Elem> 0484 inline void setTagValue(Elem &elem, TagKey key, QByteArray &&value) 0485 { 0486 setTag(elem, Tag(key, std::move(value))); 0487 } 0488 0489 /** Removes a tag from the given element. */ 0490 template <typename Elem> 0491 inline void removeTag(Elem &elem, TagKey key) 0492 { 0493 const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), key); 0494 if (it != elem.tags.end() && (*it).key == key) { 0495 elem.tags.erase(it); 0496 } 0497 } 0498 0499 template <typename Elem> 0500 [[nodiscard]] inline bool operator<(const Elem &elem, Id id) 0501 { 0502 return elem.id < id; 0503 } 0504 0505 } 0506 0507 KOSM_EXPORT QDebug operator<<(QDebug debug, OSM::Coordinate coord); 0508 KOSM_EXPORT QDebug operator<<(QDebug debug, OSM::BoundingBox bbox); 0509 0510 Q_DECLARE_METATYPE(OSM::BoundingBox) 0511 0512 #endif // OSM_DATATYPES_H