datatypes.h 13.7 KB
Newer Older
1
/*
2
    SPDX-FileCopyrightText: 2020 Volker Krause <vkrause@kde.org>
3

4
    SPDX-License-Identifier: LGPL-2.0-or-later
5
6
7
8
9
*/

#ifndef OSM_DATATYPES_H
#define OSM_DATATYPES_H

Volker Krause's avatar
Volker Krause committed
10
#include "kosm_export.h"
11
12
#include "internal.h"

13
#include <QByteArray>
14
#include <QDebug>
15
#include <QLocale>
16
17
18
#include <QString>

#include <cstdint>
Volker Krause's avatar
Volker Krause committed
19
#include <cstring>
20
21
#include <vector>

Volker Krause's avatar
Volker Krause committed
22
/** Low-level types and functions to work with raw OSM data as efficiently as possible. */
23
24
namespace OSM {

Volker Krause's avatar
Volker Krause committed
25
class DataSet;
26
class Member;
Volker Krause's avatar
Volker Krause committed
27

28
29
30
/** OSM element identifier. */
typedef int64_t Id;

31
32
/** Coordinate, stored as 1e7 * degree to avoid floating point precision issues,
 *  and offset to unsigned values to make the z-order curve work.
33
 *  Can be in an invalid state with coordinates out of range, see isValid().
34
 *  @see https://en.wikipedia.org/wiki/Z-order_curve for the z-order curve stuff
35
 */
36
37
38
39
class Coordinate {
public:
    Coordinate() = default;
    explicit constexpr Coordinate(double lat, double lon)
Volker Krause's avatar
Volker Krause committed
40
41
        : latitude((lat + 90.0) * 10'000'000)
        , longitude((lon + 180.0) * 10'000'000)
42
    {}
43
44
45
46
    explicit constexpr Coordinate(uint32_t lat, uint32_t lon)
        : latitude(lat)
        , longitude(lon)
    {}
47

48
49
50
51
52
53
54
55
56
57
58
    /** Create a coordinate from a z-order curve index. */
    explicit constexpr Coordinate(uint64_t z)
        : latitude(0)
        , longitude(0)
    {
        for (int i = 0; i < 32; ++i) {
            latitude += (z & (1ull << (i * 2))) >> i;
            longitude += (z & (1ull << (1 + i * 2))) >> (i + 1);
        }
    }

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
65
66
    constexpr inline bool operator==(Coordinate other) const
    {
        return latitude == other.latitude && longitude == other.longitude;
    }
67
68
69
70
71
72
73
74
75
76

    /** Z-order curve value for this coordinate. */
    constexpr inline uint64_t z() const
    {
        uint64_t z = 0;
        for (int i = 0; i < 32; ++i) {
            z += ((uint64_t)latitude & (1 << i)) << i;
            z += ((uint64_t)longitude & (1 << i)) << (i + 1);
        }
        return z;
77
78
    }

79
80
    constexpr inline double latF() const
    {
Volker Krause's avatar
Volker Krause committed
81
        return (latitude / 10'000'000.0) - 90.0;
82
83
84
    }
    constexpr inline double lonF() const
    {
Volker Krause's avatar
Volker Krause committed
85
        return (longitude / 10'000'000.0) - 180.0;
86
87
    }

88
89
    uint32_t latitude = std::numeric_limits<uint32_t>::max();
    uint32_t longitude = std::numeric_limits<uint32_t>::max();
90
91
};

92

93
94
95
/** Bounding box, ie. a pair of coordinates. */
class BoundingBox {
public:
96
97
98
99
100
    constexpr BoundingBox() = default;
    constexpr inline BoundingBox(Coordinate c1, Coordinate c2)
        : min(c1)
        , max(c2)
    {}
101
102
103
104
    constexpr inline bool isValid() const
    {
        return min.isValid() && max.isValid();
    }
105
106
107
108
    constexpr inline bool operator==(BoundingBox other) const
    {
        return min == other.min && max == other.max;
    }
109

110
111
112
113
114
115
116
117
118
    constexpr inline uint32_t width() const
    {
        return max.longitude - min.longitude;
    }
    constexpr inline uint32_t height() const
    {
        return max.latitude - min.latitude;
    }

119
120
121
122
123
124
125
126
127
    constexpr inline double widthF() const
    {
        return width() / 10'000'000.0;
    }
    constexpr inline double heightF() const
    {
        return height() / 10'000'000.0;
    }

128
129
130
131
132
    constexpr inline Coordinate center() const
    {
        return Coordinate(min.latitude + height() / 2, min.longitude + width() / 2);
    }

133
134
135
136
    Coordinate min;
    Coordinate max;
};

137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
constexpr inline BoundingBox unite(BoundingBox bbox1, BoundingBox bbox2)
{
    if (!bbox1.isValid()) {
        return bbox2;
    }
    if (!bbox2.isValid()) {
        return bbox1;
    }
    BoundingBox ret;
    ret.min.latitude = std::min(bbox1.min.latitude, bbox2.min.latitude);
    ret.min.longitude = std::min(bbox1.min.longitude, bbox2.min.longitude);
    ret.max.latitude = std::max(bbox1.max.latitude, bbox2.max.latitude);
    ret.max.longitude = std::max(bbox1.max.longitude, bbox2.max.longitude);
    return ret;
}

constexpr inline bool intersects(BoundingBox bbox1, BoundingBox bbox2)
{
155
156
    return !(bbox2.min.latitude > bbox1.max.latitude || bbox2.max.latitude < bbox1.min.latitude
        || bbox2.min.longitude > bbox1.max.longitude || bbox2.max.longitude < bbox1.min.longitude);
157
158
}

159
160
161
162
163
164
constexpr inline bool contains(BoundingBox bbox, Coordinate coord)
{
    return bbox.min.latitude <= coord.latitude && bbox.max.latitude >= coord.latitude
        && bbox.min.longitude <= coord.longitude && bbox.max.longitude >= coord.longitude;
}

165
constexpr inline uint32_t latitudeDistance(BoundingBox bbox1, BoundingBox bbox2)
166
167
168
169
{
    return bbox1.max.latitude < bbox2.min.latitude ? bbox2.min.latitude - bbox1.max.latitude : bbox1.min.latitude - bbox2.max.latitude;
}

170
constexpr inline uint32_t longitudeDifference(BoundingBox bbox1, BoundingBox bbox2)
171
172
173
174
{
    return bbox1.max.longitude < bbox2.min.longitude ? bbox2.min.longitude - bbox1.max.longitude : bbox1.min.longitude - bbox2.max.longitude;
}

175
176
/** Base class for unique string keys. */
class StringKey
Volker Krause's avatar
Volker Krause committed
177
178
179
180
181
182
{
public:
    constexpr inline const char* name() const { return key; }
    constexpr inline bool isNull() const { return !key; }

    // yes, pointer compare is enough here
183
184
185
    inline constexpr bool operator<(StringKey other) const { return key < other.key; }
    inline constexpr bool operator==(StringKey other) const { return key == other.key; }
    inline constexpr bool operator!=(StringKey other) const { return key != other.key; }
Volker Krause's avatar
Volker Krause committed
186

187
protected:
188
    constexpr inline StringKey() = default;
189
    explicit constexpr inline StringKey(const char *keyData) : key(keyData) {}
Volker Krause's avatar
Volker Krause committed
190

191
private:
Volker Krause's avatar
Volker Krause committed
192
193
194
    const char* key = nullptr;
};

195
196
197
198
199
/** A key of an OSM tag.
 *  See DataSet::tagKey().
 */
class TagKey : public StringKey
{
200
public:
201
    constexpr inline TagKey() = default;
202
203
private:
    explicit constexpr inline TagKey(const char *keyData) : StringKey(keyData) {}
204
205
206
    friend class DataSet;
};

207
208
209
/** An OSM element tag. */
class Tag {
public:
Volker Krause's avatar
Volker Krause committed
210
    inline constexpr bool operator<(const Tag &other) const { return key < other.key; }
211

Volker Krause's avatar
Volker Krause committed
212
    TagKey key;
213
    QByteArray value;
214
215
};

216
217
218
inline constexpr bool operator<(const Tag &lhs, TagKey rhs) { return lhs.key < rhs; }
inline constexpr bool operator<(TagKey lhs, const Tag &rhs) { return lhs < rhs.key; }

219
/** An OSM node. */
Volker Krause's avatar
Volker Krause committed
220
class KOSM_EXPORT Node {
221
public:
222
223
    constexpr inline bool operator<(const Node &other) const { return id < other.id; }

224
225
    QString url() const;

226
227
228
229
230
231
    Id id;
    Coordinate coordinate;
    std::vector<Tag> tags;
};

/** An OSM way. */
Volker Krause's avatar
Volker Krause committed
232
class KOSM_EXPORT Way {
233
public:
234
235
    constexpr inline bool operator<(const Way &other) const { return id < other.id; }

236
237
    bool isClosed() const;

238
239
    QString url() const;

240
    Id id;
241
    mutable BoundingBox bbox;
242
    std::vector<Id> nodes;
243
244
245
    std::vector<Tag> tags;
};

246
247
/** Element type. */
enum class Type : uint8_t {
248
    Null,
249
250
251
252
253
    Node,
    Way,
    Relation
};

254
255
256
257
258
/** A relation role name key.
 *  See DataSet::role().
 */
class Role : public StringKey
{
259
public:
260
    constexpr inline Role() = default;
261
262
263
264
private:
    friend class DataSet;
    friend class Member;
    explicit constexpr inline Role(const char *keyData) : StringKey(keyData) {}
265
266
};

267
268
269
/** A member in a relation. */
class Member {
public:
270
    inline bool operator==(const Member &other) const { return id == other.id && m_roleAndType == other.m_roleAndType; }
271

272
    Id id;
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293

    constexpr inline Role role() const
    {
        return Role(m_roleAndType.get());
    }
    constexpr inline void setRole(Role role)
    {
        m_roleAndType.set(role.name());
    }

    constexpr inline Type type() const
    {
        return static_cast<Type>(m_roleAndType.tag());
    }
    constexpr inline void setType(Type type)
    {
        m_roleAndType.setTag(static_cast<uint8_t>(type));
    }

private:
    Internal::TaggedPointer<const char> m_roleAndType;
294
295
};

296
/** An OSM relation. */
Volker Krause's avatar
Volker Krause committed
297
class KOSM_EXPORT Relation {
298
public:
299
300
    constexpr inline bool operator<(const Relation &other) const { return id < other.id; }

301
302
    QString url() const;

303
    Id id;
304
    mutable BoundingBox bbox;
305
    std::vector<Member> members;
306
307
308
309
    std::vector<Tag> tags;
};

/** A set of nodes, ways and relations. */
Volker Krause's avatar
Volker Krause committed
310
class KOSM_EXPORT DataSet {
311
public:
Volker Krause's avatar
Volker Krause committed
312
313
314
315
316
317
318
319
    explicit DataSet();
    DataSet(const DataSet&) = delete;
    DataSet(DataSet &&other);
    ~DataSet();

    DataSet& operator=(const DataSet&) = delete;
    DataSet& operator=(DataSet &&);

320
321
322
323
324
325
326
327
328
    /** Find a node by its id.
     *  @returns @c nullptr if the node doesn't exist.
     */
    const Node* node(Id id) const;

    /** Find a way by its id.
     *  @returns @c nullptr if the way doesn't exist.
     */
    const Way* way(Id id) const;
329
    Way* way(Id id);
330
331
332
333
334
335

    /** Find a relation by its id.
     *  @returns @c nullptr if the relation doesn't exist.
     */
    const Relation* relation(Id id) const;

336
    void addNode(Node &&node);
Volker Krause's avatar
Volker Krause committed
337
    void addWay(Way &&way);
338
    void addRelation(Relation &&rel);
339

Volker Krause's avatar
Volker Krause committed
340
341
342
343
344
345
    /** Look up a tag key for the given tag name, if it exists.
     *  If no key exists, an empty/invalid/null key is returned.
     *  Use this for tag lookup, not for creating/adding tags.
     */
    TagKey tagKey(const char *keyName) const;

346
    enum StringMemory { StringIsPersistent, StringIsTransient };
Volker Krause's avatar
Volker Krause committed
347
348
349
350
351
352
    /** Create a tag key for the given tag name. If none exist yet a new one is created.
     *  Use this for creating tags, not for lookup, prefer tagKey() for that.
     *  @param keyMemOpt specifies whether @p keyName is persisent for the lifetime of this
     *  instance and thus can be used without requiring a copy. If the memory is transient
     *  the string is copied if needed, and released in the DataSet destructor.
     */
353
354
355
356
357
358
359
360
361
362
    TagKey makeTagKey(const char *keyName, StringMemory keyMemOpt = StringIsTransient);

    /** Looks up a role name key.
     *  @see tagKey()
     */
    Role role(const char *roleName) const;
    /** Creates a role name key.
     *  @see makeTagKey()
     */
    Role makeRole(const char *roleName, StringMemory memOpt = StringIsTransient);
Volker Krause's avatar
Volker Krause committed
363

364
365
366
    /** Create a unique id for internal use (ie. one that will not clash with official OSM ids). */
    Id nextInternalId() const;

367
368
369
    std::vector<Node> nodes;
    std::vector<Way> ways;
    std::vector<Relation> relations;
Volker Krause's avatar
Volker Krause committed
370
371

private:
372
373
374
    template <typename T> T stringKey(const char *name, const std::vector<T> &registry) const;
    template <typename T> T makeStringKey(const char *name, StringMemory memOpt, std::vector<T> &registry);

Volker Krause's avatar
Volker Krause committed
375
    std::vector<TagKey> m_tagKeyRegistry;
376
    std::vector<Role> m_roleRegistry;
Volker Krause's avatar
Volker Krause committed
377
    std::vector<char*> m_stringPool;
378
379
};

380
381
/** Returns the tag value for @p key of @p elem. */
template <typename Elem>
382
inline QByteArray tagValue(const Elem& elem, TagKey key)
383
{
384
    const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), key);
385
    if (it != elem.tags.end() && (*it).key == key) {
386
387
388
389
390
        return (*it).value;
    }
    return {};
}

Volker Krause's avatar
Volker Krause committed
391
392
393
394
395
/** Returns the tag value for key name @p keyName of @p elem.
 *  @warning This is slow due to doing a linear search and string comparissons.
 *  Where possible avoid this in favor of tagValue().
 */
template <typename Elem>
396
inline QByteArray tagValue(const Elem& elem, const char *keyName)
Volker Krause's avatar
Volker Krause committed
397
398
399
400
401
402
403
404
{
    const auto it = std::find_if(elem.tags.begin(), elem.tags.end(), [keyName](const auto &tag) { return std::strcmp(tag.key.name(), keyName) == 0; });
    if (it != elem.tags.end()) {
        return (*it).value;
    }
    return {};
}

405
406
407
408
/** Returns the localized version of the tag value for key name @p keyName of @p elem.
 *  @warning This is slow due to doing a linear search and string comparissons.
 */
template <typename Elem>
409
inline QByteArray tagValue(const Elem& elem, const char *keyName, const QLocale &locale)
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
{
    QByteArray key(keyName);
    key.push_back(':');
    const auto baseLen = key.size();
    for (const auto &lang : locale.uiLanguages()) {
        key.resize(baseLen);
        key.append(lang.toUtf8());
        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; });
        if (it != elem.tags.end()) {
            return (*it).value;
        }

        const auto idx = lang.indexOf(QLatin1Char('-'));
        if (idx > 0) {
            key.resize(baseLen);
            key.append(lang.leftRef(idx).toUtf8());
            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; });
            if (it != elem.tags.end()) {
                return (*it).value;
            }
        }
    }

433
434
435
436
437
438
439
440
441
442
443
444
445
    // fall back to generic value, if present
    const auto v = tagValue(elem, keyName);
    if (!v.isEmpty()) {
        return v;
    }

    // check if there is at least one in any language we can use
    key.resize(baseLen);
    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; });
    if (it != elem.tags.end()) {
        return (*it).value;
    }
    return {};
446
447
}

448
449
450
451
452
453
454
455
456
457
458
459
460
461
/** Inserts a new tag, or replaces an existing one with the same key. */
template <typename Elem>
inline void setTag(Elem &elem, Tag &&tag)
{
    const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), tag);
    if (it == elem.tags.end() || (*it).key != tag.key) {
        elem.tags.insert(it, std::move(tag));
    } else {
        (*it) = std::move(tag);
    }
}

/** Inserts a new tag, or updates an existing one. */
template <typename Elem>
462
inline void setTagValue(Elem &elem, TagKey key, const QByteArray &value)
463
464
465
466
467
{
    Tag tag{ key, value };
    setTag(elem, std::move(tag));
}

468
469
470
471
472
473
template <typename Elem>
inline bool operator<(const Elem &elem, Id id)
{
    return elem.id < id;
}

474
475
}

Volker Krause's avatar
Volker Krause committed
476
477
KOSM_EXPORT QDebug operator<<(QDebug debug, OSM::Coordinate coord);
KOSM_EXPORT QDebug operator<<(QDebug debug, OSM::BoundingBox bbox);
478

479
#endif // OSM_DATATYPES_H