1 #ifndef OSRM_GUIDANCE_TURN_LANE_TYPES_HPP_
2 #define OSRM_GUIDANCE_TURN_LANE_TYPES_HPP_
3
4 #include "util/concurrent_id_map.hpp"
5 #include "util/integer_range.hpp"
6 #include "util/typedefs.hpp"
7
8 #include <boost/functional/hash.hpp>
9
10 #include <bitset>
11 #include <cstddef>
12 #include <cstdint>
13 #include <numeric> //partial_sum
14 #include <vector>
15
16 namespace osrm
17 {
18 namespace extractor
19 {
20
21 namespace TurnLaneType
22 {
23 const constexpr std::size_t NUM_TYPES = 11;
24
laneTypeToName(const std::size_t type_id)25 inline auto laneTypeToName(const std::size_t type_id)
26 {
27 const static char *name[NUM_TYPES] = {"none",
28 "straight",
29 "sharp left",
30 "left",
31 "slight left",
32 "slight right",
33 "right",
34 "sharp right",
35 "uturn",
36 "merge to left",
37 "merge to right"};
38 return name[type_id];
39 }
40
41 typedef std::uint16_t Mask;
42 const constexpr Mask empty = 0u;
43 const constexpr Mask none = 1u << 0u;
44 const constexpr Mask straight = 1u << 1u;
45 const constexpr Mask sharp_left = 1u << 2u;
46 const constexpr Mask left = 1u << 3u;
47 const constexpr Mask slight_left = 1u << 4u;
48 const constexpr Mask slight_right = 1u << 5u;
49 const constexpr Mask right = 1u << 6u;
50 const constexpr Mask sharp_right = 1u << 7u;
51 const constexpr Mask uturn = 1u << 8u;
52 const constexpr Mask merge_to_left = 1u << 9u;
53 const constexpr Mask merge_to_right = 1u << 10u;
54
55 } // namespace TurnLaneType
56
57 typedef std::vector<TurnLaneType::Mask> TurnLaneDescription;
58
59 // hash function for TurnLaneDescription
60 struct TurnLaneDescription_hash
61 {
operator ()osrm::extractor::TurnLaneDescription_hash62 std::size_t operator()(const TurnLaneDescription &lane_description) const
63 {
64 std::size_t seed = 0;
65 boost::hash_range(seed, lane_description.begin(), lane_description.end());
66 return seed;
67 }
68 };
69
70 using LaneDescriptionMap =
71 util::ConcurrentIDMap<TurnLaneDescription, LaneDescriptionID, TurnLaneDescription_hash>;
72
73 using TurnLanesIndexedArray =
74 std::tuple<std::vector<std::uint32_t>, std::vector<TurnLaneType::Mask>>;
75
transformTurnLaneMapIntoArrays(const LaneDescriptionMap & turn_lane_map)76 inline TurnLanesIndexedArray transformTurnLaneMapIntoArrays(const LaneDescriptionMap &turn_lane_map)
77 {
78 // could use some additional capacity? To avoid a copy during processing, though small data so
79 // probably not that important.
80 //
81 // From the map, we construct an adjacency array that allows access from all IDs to the list of
82 // associated Turn Lane Masks.
83 //
84 // turn lane offsets points into the locations of the turn_lane_masks array. We use a standard
85 // adjacency array like structure to store the turn lane masks.
86 std::vector<std::uint32_t> turn_lane_offsets(turn_lane_map.data.size() + 1); // + sentinel
87 for (auto entry = turn_lane_map.data.begin(); entry != turn_lane_map.data.end(); ++entry)
88 turn_lane_offsets[entry->second + 1] = entry->first.size();
89
90 // inplace prefix sum
91 std::partial_sum(turn_lane_offsets.begin(), turn_lane_offsets.end(), turn_lane_offsets.begin());
92
93 // allocate the current masks
94 std::vector<TurnLaneType::Mask> turn_lane_masks(turn_lane_offsets.back());
95 for (auto entry = turn_lane_map.data.begin(); entry != turn_lane_map.data.end(); ++entry)
96 std::copy(entry->first.begin(),
97 entry->first.end(),
98 turn_lane_masks.begin() + turn_lane_offsets[entry->second]);
99
100 return std::make_tuple(std::move(turn_lane_offsets), std::move(turn_lane_masks));
101 }
102
103 } // namespace extractor
104 } // namespace osrm
105
106 #endif /* OSRM_GUIDANCE_TURN_LANE_TYPES_HPP_ */
107