1 /*
2 
3 Copyright (c) 2017, Project OSRM contributors
4 All rights reserved.
5 
6 Redistribution and use in source and binary forms, with or without modification,
7 are permitted provided that the following conditions are met:
8 
9 Redistributions of source code must retain the above copyright notice, this list
10 of conditions and the following disclaimer.
11 Redistributions in binary form must reproduce the above copyright notice, this
12 list of conditions and the following disclaimer in the documentation and/or
13 other materials provided with the distribution.
14 
15 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
19 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
22 ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 
26 */
27 
28 #ifndef OSRM_ENGINE_PHANTOM_NODES_H
29 #define OSRM_ENGINE_PHANTOM_NODES_H
30 
31 #include "extractor/travel_mode.hpp"
32 
33 #include "util/bearing.hpp"
34 #include "util/coordinate.hpp"
35 #include "util/typedefs.hpp"
36 
37 #include <boost/assert.hpp>
38 
39 namespace osrm
40 {
41 namespace engine
42 {
43 
44 struct PhantomNode
45 {
PhantomNodeosrm::engine::PhantomNode46     PhantomNode()
47         : forward_segment_id{SPECIAL_SEGMENTID, false}, reverse_segment_id{SPECIAL_SEGMENTID,
48                                                                            false},
49           forward_weight(INVALID_EDGE_WEIGHT), reverse_weight(INVALID_EDGE_WEIGHT),
50           forward_weight_offset(0), reverse_weight_offset(0),
51           forward_distance(INVALID_EDGE_DISTANCE), reverse_distance(INVALID_EDGE_DISTANCE),
52           forward_distance_offset(0), reverse_distance_offset(0),
53           forward_duration(MAXIMAL_EDGE_DURATION), reverse_duration(MAXIMAL_EDGE_DURATION),
54           forward_duration_offset(0), reverse_duration_offset(0),
55           fwd_segment_position(0), is_valid_forward_source{false}, is_valid_forward_target{false},
56           is_valid_reverse_source{false}, is_valid_reverse_target{false}, bearing(0)
57 
58     {
59     }
60 
GetForwardWeightPlusOffsetosrm::engine::PhantomNode61     EdgeWeight GetForwardWeightPlusOffset() const
62     {
63         BOOST_ASSERT(forward_segment_id.enabled);
64         return forward_weight_offset + forward_weight;
65     }
66 
GetReverseWeightPlusOffsetosrm::engine::PhantomNode67     EdgeWeight GetReverseWeightPlusOffset() const
68     {
69         BOOST_ASSERT(reverse_segment_id.enabled);
70         return reverse_weight_offset + reverse_weight;
71     }
72 
GetForwardDurationosrm::engine::PhantomNode73     EdgeWeight GetForwardDuration() const
74     {
75         BOOST_ASSERT(forward_segment_id.enabled);
76         return forward_duration + forward_duration_offset;
77     }
78 
GetReverseDurationosrm::engine::PhantomNode79     EdgeWeight GetReverseDuration() const
80     {
81         BOOST_ASSERT(reverse_segment_id.enabled);
82         return reverse_duration + reverse_duration_offset;
83     }
84 
85     // DO THIS FOR DISTANCE
86 
GetForwardDistanceosrm::engine::PhantomNode87     EdgeDistance GetForwardDistance() const
88     {
89         // .....                  <-- forward_distance
90         //      ....              <-- offset
91         // .........              <-- desired distance
92         //         x              <-- this is PhantomNode.location
93         // 0----1----2----3----4  <-- EdgeBasedGraph Node segments
94         BOOST_ASSERT(forward_segment_id.enabled);
95         return forward_distance + forward_distance_offset;
96     }
97 
GetReverseDistanceosrm::engine::PhantomNode98     EdgeDistance GetReverseDistance() const
99     {
100         //            ..........  <-- reverse_distance
101         //         ...            <-- offset
102         //         .............  <-- desired distance
103         //         x              <-- this is PhantomNode.location
104         // 0----1----2----3----4  <-- EdgeBasedGraph Node segments
105         BOOST_ASSERT(reverse_segment_id.enabled);
106         return reverse_distance + reverse_distance_offset;
107     }
108 
IsBidirectedosrm::engine::PhantomNode109     bool IsBidirected() const { return forward_segment_id.enabled && reverse_segment_id.enabled; }
110 
IsValidosrm::engine::PhantomNode111     bool IsValid(const unsigned number_of_nodes) const
112     {
113         return location.IsValid() &&
114                ((forward_segment_id.id < number_of_nodes) ||
115                 (reverse_segment_id.id < number_of_nodes)) &&
116                ((forward_weight != INVALID_EDGE_WEIGHT) ||
117                 (reverse_weight != INVALID_EDGE_WEIGHT)) &&
118                ((forward_duration != MAXIMAL_EDGE_DURATION) ||
119                 (reverse_duration != MAXIMAL_EDGE_DURATION)) &&
120                ((forward_distance != INVALID_EDGE_DISTANCE) ||
121                 (reverse_distance != INVALID_EDGE_DISTANCE)) &&
122                (component.id != INVALID_COMPONENTID);
123     }
124 
IsValidosrm::engine::PhantomNode125     bool IsValid(const unsigned number_of_nodes, const util::Coordinate queried_coordinate) const
126     {
127         return queried_coordinate == input_location && IsValid(number_of_nodes);
128     }
129 
IsValidosrm::engine::PhantomNode130     bool IsValid() const { return location.IsValid(); }
131 
IsValidForwardSourceosrm::engine::PhantomNode132     bool IsValidForwardSource() const
133     {
134         return forward_segment_id.enabled && is_valid_forward_source;
135     }
IsValidForwardTargetosrm::engine::PhantomNode136     bool IsValidForwardTarget() const
137     {
138         return forward_segment_id.enabled && is_valid_forward_target;
139     }
IsValidReverseSourceosrm::engine::PhantomNode140     bool IsValidReverseSource() const
141     {
142         return reverse_segment_id.enabled && is_valid_reverse_source;
143     }
IsValidReverseTargetosrm::engine::PhantomNode144     bool IsValidReverseTarget() const
145     {
146         return reverse_segment_id.enabled && is_valid_reverse_target;
147     }
GetBearingosrm::engine::PhantomNode148     short GetBearing(const bool traversed_in_reverse) const
149     {
150         if (traversed_in_reverse)
151             return std::round(util::bearing::reverse(bearing));
152         return std::round(bearing);
153     }
154 
operator ==osrm::engine::PhantomNode155     bool operator==(const PhantomNode &other) const { return location == other.location; }
156 
157     template <class OtherT>
PhantomNodeosrm::engine::PhantomNode158     explicit PhantomNode(const OtherT &other,
159                          ComponentID component,
160                          EdgeWeight forward_weight,
161                          EdgeWeight reverse_weight,
162                          EdgeWeight forward_weight_offset,
163                          EdgeWeight reverse_weight_offset,
164                          EdgeDistance forward_distance,
165                          EdgeDistance reverse_distance,
166                          EdgeDistance forward_distance_offset,
167                          EdgeDistance reverse_distance_offset,
168                          EdgeWeight forward_duration,
169                          EdgeWeight reverse_duration,
170                          EdgeWeight forward_duration_offset,
171                          EdgeWeight reverse_duration_offset,
172                          bool is_valid_forward_source,
173                          bool is_valid_forward_target,
174                          bool is_valid_reverse_source,
175                          bool is_valid_reverse_target,
176                          const util::Coordinate location,
177                          const util::Coordinate input_location,
178                          const unsigned short bearing)
179         : forward_segment_id{other.forward_segment_id},
180           reverse_segment_id{other.reverse_segment_id}, forward_weight{forward_weight},
181           reverse_weight{reverse_weight}, forward_weight_offset{forward_weight_offset},
182           reverse_weight_offset{reverse_weight_offset}, forward_distance{forward_distance},
183           reverse_distance{reverse_distance}, forward_distance_offset{forward_distance_offset},
184           reverse_distance_offset{reverse_distance_offset}, forward_duration{forward_duration},
185           reverse_duration{reverse_duration}, forward_duration_offset{forward_duration_offset},
186           reverse_duration_offset{reverse_duration_offset},
187           component{component.id, component.is_tiny}, location{location},
188           input_location{input_location}, fwd_segment_position{other.fwd_segment_position},
189           is_valid_forward_source{is_valid_forward_source},
190           is_valid_forward_target{is_valid_forward_target},
191           is_valid_reverse_source{is_valid_reverse_source},
192           is_valid_reverse_target{is_valid_reverse_target}, bearing{bearing}
193     {
194     }
195 
196     SegmentID forward_segment_id;
197     SegmentID reverse_segment_id;
198     EdgeWeight forward_weight;
199     EdgeWeight reverse_weight;
200     EdgeWeight forward_weight_offset; // TODO: try to remove -> requires path unpacking changes
201     EdgeWeight reverse_weight_offset; // TODO: try to remove -> requires path unpacking changes
202     EdgeDistance forward_distance;
203     EdgeDistance reverse_distance;
204     EdgeDistance forward_distance_offset; // TODO: try to remove -> requires path unpacking changes
205     EdgeDistance reverse_distance_offset; // TODO: try to remove -> requires path unpacking changes
206     EdgeWeight forward_duration;
207     EdgeWeight reverse_duration;
208     EdgeWeight forward_duration_offset; // TODO: try to remove -> requires path unpacking changes
209     EdgeWeight reverse_duration_offset; // TODO: try to remove -> requires path unpacking changes
210     ComponentID component;
211 
212     util::Coordinate location; // this is the coordinate of x
213     util::Coordinate input_location;
214     unsigned short fwd_segment_position;
215     // is phantom node valid to be used as source or target
216   private:
217     unsigned short is_valid_forward_source : 1;
218     unsigned short is_valid_forward_target : 1;
219     unsigned short is_valid_reverse_source : 1;
220     unsigned short is_valid_reverse_target : 1;
221     unsigned short bearing : 12;
222 };
223 
224 static_assert(sizeof(PhantomNode) == 80, "PhantomNode has more padding then expected");
225 
226 using PhantomNodePair = std::pair<PhantomNode, PhantomNode>;
227 
228 struct PhantomNodeWithDistance
229 {
230     PhantomNode phantom_node;
231     double distance;
232 };
233 
234 struct PhantomNodes
235 {
236     PhantomNode source_phantom;
237     PhantomNode target_phantom;
238 };
239 } // namespace engine
240 } // namespace osrm
241 
242 #endif // PHANTOM_NODES_H
243