forked from heremaps/flatdata
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStructGraph.h
More file actions
363 lines (342 loc) · 9.46 KB
/
StructGraph.h
File metadata and controls
363 lines (342 loc) · 9.46 KB
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
#pragma once
#include "GraphGenerator.h"
#include <algorithm>
#include <vector>
/// A graph that simple reinterpret_casts C++'s internal data representation to byte streams
/// This is not very portable (different compiler, ABI, target can produce different results), but
/// is a golden standard for performance.
class StructGraph
{
struct InternalEdgeData
{
ExternalId id;
uint32_t from;
uint32_t to;
uint32_t length;
uint32_t speed_pos : 8; // 8
uint32_t speed_neg : 8; // 16
uint32_t is_a : 1;
uint32_t is_b : 1;
uint32_t is_c : 1;
uint32_t is_d : 1;
uint32_t is_e_pos : 1;
uint32_t is_e_neg : 1;
uint32_t is_f_pos : 1;
uint32_t is_f_neg : 1; // 24
uint32_t is_g_pos : 1;
uint32_t is_g_neg : 1; // 26
uint32_t frc : 3; // 29
};
struct InternalEdge
{
uint32_t id : 31;
uint32_t dir : 1;
};
struct InternalNode
{
Coordinates coords;
uint32_t first_edge;
};
public:
class NodeRange;
class Edge
{
public:
InternalId
id( ) const
{
return InternalId{m_id};
}
ExternalId
external_id( ) const
{
return m_data->id;
}
uint32_t
length_m( ) const
{
return m_data->length;
}
bool
is_a( ) const
{
return m_data->is_a;
}
bool
is_b( ) const
{
return m_data->is_b;
}
bool
is_c( ) const
{
return m_data->is_c;
}
bool
is_d( ) const
{
return m_data->is_d;
}
bool
is_e( Direction dir ) const
{
return dir == Direction::POSITIVE ? m_data->is_e_pos : m_data->is_e_neg;
}
bool
is_f( Direction dir ) const
{
return dir == Direction::POSITIVE ? m_data->is_f_pos : m_data->is_f_neg;
}
bool
is_g( Direction dir ) const
{
return dir == Direction::POSITIVE ? m_data->is_g_pos : m_data->is_g_neg;
}
uint8_t
frc( ) const
{
return m_data->frc;
}
uint8_t
speed_km_h( Direction dir ) const
{
return dir == Direction::POSITIVE ? m_data->speed_pos : m_data->speed_neg;
}
NodeRange from_node( ) const;
NodeRange to_node( ) const;
private:
friend class StructGraph;
Edge( const InternalEdgeData* data, uint32_t id, const StructGraph* graph )
: m_data( data )
, m_id( id )
, m_graph( graph )
{
}
const InternalEdgeData* m_data;
uint32_t m_id;
const StructGraph* m_graph;
};
class EdgeRange
{
public:
EdgeRange( )
: m_current( )
, m_end( )
, m_graph( )
{
}
void
operator++( )
{
m_current++;
}
void
operator++( int )
{
m_current++;
}
bool
valid( ) const
{
return m_current < m_end;
}
size_t
size( ) const
{
return m_end - m_current;
}
Direction
dir( ) const
{
return static_cast< Direction >( m_graph->m_edges[ m_current ].dir );
}
Edge
data( ) const
{
uint32_t id = m_graph->m_edges[ m_current ].id;
return Edge( m_graph->m_data + id, id, m_graph );
}
private:
friend class StructGraph;
EdgeRange( uint32_t current, uint32_t end, const StructGraph* graph )
: m_current( current )
, m_end( end )
, m_graph( graph )
{
}
uint32_t m_current;
uint32_t m_end;
const StructGraph* m_graph;
};
class NodeRange
{
public:
NodeRange( )
: m_current( )
, m_end( )
, m_graph( )
{
}
void
operator++( )
{
m_current++;
}
void
operator++( int )
{
m_current++;
}
bool
valid( ) const
{
return m_current < m_end;
}
size_t
size( ) const
{
return m_end - m_current;
}
NodeId
id( ) const
{
return NodeId{m_current};
}
Coordinates
coordinates( ) const
{
return m_graph->m_nodes[ m_current ].coords;
}
EdgeRange
edges( ) const
{
return EdgeRange( m_graph->m_nodes[ m_current ].first_edge,
m_graph->m_nodes[ m_current + 1 ].first_edge, m_graph );
}
private:
friend class StructGraph;
NodeRange( uint32_t current, uint32_t end, const StructGraph* graph )
: m_current( current )
, m_end( end )
, m_graph( graph )
{
}
uint32_t m_current;
uint32_t m_end;
const StructGraph* m_graph;
};
public:
StructGraph( const char* data )
{
m_node_count = ( (const uint32_t*)data )[ 0 ];
m_edge_count = ( (const uint32_t*)data )[ 1 ];
data += 2 * sizeof( uint32_t );
m_nodes = (const InternalNode*)data;
data += sizeof( InternalNode ) * ( m_node_count + 1 ); // sentinel
m_edges = (const InternalEdge*)data;
data += sizeof( InternalEdge ) * m_edge_count * 2;
m_data = (const InternalEdgeData*)data;
data += sizeof( InternalEdgeData ) * m_edge_count;
}
template < typename Graph >
static std::vector< char >
create( const Graph& graph )
{
std::vector< char > result;
size_t size = 2 * sizeof( uint32_t ) + sizeof( InternalNode ) * ( graph.node_count( ) + 1 )
+ sizeof( InternalEdge ) * graph.edge_count( ) * 2
+ sizeof( InternalEdgeData ) * graph.edge_count( );
result.reserve( size );
result.resize( size );
char* data = result.data( );
( (uint32_t*)data )[ 0 ] = graph.node_count( );
( (uint32_t*)data )[ 1 ] = graph.edge_count( );
data += 2 * sizeof( uint32_t );
InternalNode* nodes = (InternalNode*)data;
data += sizeof( InternalNode ) * ( graph.node_count( ) + 1 ); // sentinel
InternalEdge* edges = (InternalEdge*)data;
data += sizeof( InternalEdge ) * graph.edge_count( ) * 2;
InternalEdgeData* edge_data = (InternalEdgeData*)data;
nodes[ 0 ].first_edge = 0;
size_t edge_pos = 0;
for ( auto node = graph.nodes( ); node.valid( ); node++ )
{
nodes[ node.id( ).id ].coords = node.coordinates( );
for ( auto e = node.edges( ); e.valid( ); e++ )
{
edges[ edge_pos ].id = e.data( ).id( ).id;
edges[ edge_pos ].dir = static_cast< uint32_t >( e.dir( ) );
edge_pos++;
}
nodes[ node.id( ).id + 1 ].first_edge = edge_pos;
}
for ( uint32_t i = 0; i < graph.edge_count( ); i++ )
{
auto edge = graph.edge( InternalId{i} );
auto& target = edge_data[ i ];
target.id = edge.external_id( );
target.speed_pos = edge.speed_km_h( Direction::POSITIVE );
target.speed_neg = edge.speed_km_h( Direction::NEGATIVE );
target.is_a = edge.is_a( );
target.is_b = edge.is_b( );
target.is_c = edge.is_c( );
target.is_d = edge.is_d( );
target.is_e_pos = edge.is_e( Direction::POSITIVE );
target.is_e_neg = edge.is_e( Direction::NEGATIVE );
target.is_f_pos = edge.is_f( Direction::POSITIVE );
target.is_f_neg = edge.is_f( Direction::NEGATIVE );
target.is_g_pos = edge.is_g( Direction::POSITIVE );
target.is_g_neg = edge.is_g( Direction::NEGATIVE );
target.frc = edge.frc( );
target.length = edge.length_m( );
target.from = edge.from_node( ).id( ).id;
target.to = edge.to_node( ).id( ).id;
}
return result;
}
uint32_t
node_count( ) const
{
return m_node_count;
}
uint32_t
edge_count( ) const
{
return m_edge_count;
}
NodeRange
nodes( ) const
{
return NodeRange( 0, m_node_count, this );
}
Edge
find( ExternalId id ) const
{
auto pos = std::lower_bound( m_data, m_data + m_edge_count, id,
[]( const InternalEdgeData& left, const ExternalId& right ) {
return left.id.id < right.id;
} );
return Edge( pos, pos - m_data, this );
}
Edge
edge( InternalId id ) const
{
return Edge( m_data + id.id, id.id, this );
}
private:
uint32_t m_node_count;
uint32_t m_edge_count;
const InternalNode* m_nodes;
const InternalEdge* m_edges;
const InternalEdgeData* m_data;
};
inline StructGraph::NodeRange
StructGraph::Edge::from_node( ) const
{
return NodeRange( m_data->from, m_data->from + 1, m_graph );
}
inline StructGraph::NodeRange
StructGraph::Edge::to_node( ) const
{
return NodeRange( m_data->to, m_data->to + 1, m_graph );
}