1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
#pragma once
#include "coding/bit_streams.hpp"
#include "coding/elias_coder.hpp"
#include "coding/file_writer.hpp"
#include "coding/reader.hpp"
#include "coding/varint.hpp"
#include "coding/write_to_sink.hpp"
#include "base/assert.hpp"
#include "base/bits.hpp"
#include "std/algorithm.hpp"
#include "std/string.hpp"
#include "std/vector.hpp"
namespace routing
{
/// \brief Restriction to modify road graph.
struct Restriction
{
static uint32_t const kInvalidFeatureId;
/// \brief Types of road graph restrictions.
/// \note Despite the fact more that 10 restriction tags are present in osm all of them
/// could be split into two categories.
/// * no_left_turn, no_right_turn, no_u_turn and so on go to "No" category.
/// * only_left_turn, only_right_turn and so on go to "Only" category.
/// That's enough to rememeber if
/// * there's only way to pass the junction is driving along the restriction (Only)
/// * driving along the restriction is prohibited (No)
enum class Type
{
No, // Going according such restriction is prohibited.
Only, // Only going according such restriction is permitted
};
Restriction(Type type, vector<uint32_t> const & links) : m_featureIds(links), m_type(type) {}
bool IsValid() const;
bool operator==(Restriction const & restriction) const;
bool operator<(Restriction const & restriction) const;
// Links of the restriction in feature ids term.
vector<uint32_t> m_featureIds;
Type m_type;
};
using RestrictionVec = vector<Restriction>;
string ToString(Restriction::Type const & type);
string DebugPrint(Restriction::Type const & type);
string DebugPrint(Restriction const & restriction);
struct RoutingHeader
{
RoutingHeader() { Reset(); }
template <class Sink>
void Serialize(Sink & sink) const
{
WriteToSink(sink, m_version);
WriteToSink(sink, m_reserved);
WriteToSink(sink, m_noRestrictionCount);
WriteToSink(sink, m_onlyRestrictionCount);
}
template <class Source>
void Deserialize(Source & src)
{
m_version = ReadPrimitiveFromSource<uint16_t>(src);
m_reserved = ReadPrimitiveFromSource<uint16_t>(src);
m_noRestrictionCount = ReadPrimitiveFromSource<uint32_t>(src);
m_onlyRestrictionCount = ReadPrimitiveFromSource<uint32_t>(src);
}
void Reset()
{
m_version = 0;
m_reserved = 0;
m_noRestrictionCount = 0;
m_onlyRestrictionCount = 0;
}
uint16_t m_version;
uint16_t m_reserved;
uint32_t m_noRestrictionCount;
uint32_t m_onlyRestrictionCount;
};
static_assert(sizeof(RoutingHeader) == 12, "Wrong header size of routing section.");
class RestrictionSerializer
{
public:
template <class Sink>
static void Serialize(RoutingHeader const & header,
routing::RestrictionVec::const_iterator begin,
routing::RestrictionVec::const_iterator end, Sink & sink)
{
auto const firstOnlyIt = begin + header.m_noRestrictionCount;
SerializeSingleType(begin, firstOnlyIt, sink);
SerializeSingleType(firstOnlyIt, end, sink);
}
template <class Source>
static void Deserialize(RoutingHeader const & header, routing::RestrictionVec & restrictions,
Source & src)
{
DeserializeSingleType(routing::Restriction::Type::No, header.m_noRestrictionCount,
restrictions, src);
DeserializeSingleType(routing::Restriction::Type::Only, header.m_onlyRestrictionCount,
restrictions, src);
}
private:
static uint32_t const kDefaultFeatureId = 0;
/// \brief Serializes a range of restrictions form |begin| to |end| to |sink|.
/// \param begin is an iterator to the first item to serialize.
/// \param end is an iterator to the element after the last element to serialize.
/// \note All restrictions should have the same type.
template <class Sink>
static void SerializeSingleType(routing::RestrictionVec::const_iterator begin,
routing::RestrictionVec::const_iterator end, Sink & sink)
{
if (begin == end)
return;
CHECK(is_sorted(begin, end), ());
routing::Restriction::Type const type = begin->m_type;
uint32_t prevFirstLinkFeatureId = 0;
BitWriter<FileWriter> bits(sink);
for (; begin != end; ++begin)
{
CHECK_EQUAL(type, begin->m_type, ());
routing::Restriction const & restriction = *begin;
CHECK(restriction.IsValid(), ());
CHECK_LESS(1, restriction.m_featureIds.size(), ("No sense in zero or one link restrictions."));
coding::DeltaCoder::Encode(bits, restriction.m_featureIds.size() - 1 /* number of link is two or more */);
CHECK_LESS_OR_EQUAL(prevFirstLinkFeatureId, restriction.m_featureIds[0], ());
coding::DeltaCoder::Encode(bits,
restriction.m_featureIds[0] - prevFirstLinkFeatureId + 1 /* making it greater than zero */);
for (size_t i = 1; i < restriction.m_featureIds.size(); ++i)
{
uint32_t const delta = bits::ZigZagEncode(static_cast<int32_t>(restriction.m_featureIds[i]) -
static_cast<int32_t>(restriction.m_featureIds[i - 1]));
coding::DeltaCoder::Encode(bits, delta + 1 /* making it greater than zero */);
}
prevFirstLinkFeatureId = restriction.m_featureIds[0];
}
}
template <class Source>
static bool DeserializeSingleType(routing::Restriction::Type type, uint32_t count,
routing::RestrictionVec & restrictions, Source & src)
{
uint32_t prevFirstLinkFeatureId = 0;
BitReader<Source> bits(src);
for (size_t i = 0; i < count; ++i)
{
uint32_t const biasedLinkNumber = coding::DeltaCoder::Decode(bits);
if (biasedLinkNumber == 0)
{
LOG(LERROR, ("Decoded link restriction number is zero."));
return false;
}
size_t const numLinks = biasedLinkNumber + 1 /* number of link is two or more */;
routing::Restriction restriction(type, {} /* links */);
restriction.m_featureIds.resize(numLinks);
uint32_t const biasedFirstFeatureId = coding::DeltaCoder::Decode(bits);
if (biasedFirstFeatureId == 0)
{
LOG(LERROR, ("Decoded first link restriction feature id delta is zero."));
return false;
}
restriction.m_featureIds[0] = prevFirstLinkFeatureId + biasedFirstFeatureId - 1;
for (size_t i = 1; i < numLinks; ++i)
{
uint32_t const biasedDelta = coding::DeltaCoder::Decode(bits);
if (biasedDelta == 0)
{
LOG(LERROR, ("Decoded link restriction feature id delta is zero."));
return false;
}
uint32_t const delta = biasedDelta - 1;
restriction.m_featureIds[i] = static_cast<uint32_t>(
bits::ZigZagDecode(delta) + restriction.m_featureIds[i - 1]);
}
prevFirstLinkFeatureId = restriction.m_featureIds[0];
restrictions.push_back(restriction);
}
return true;
}
};
} // namespace routing
|
