Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file RailEdge.h
15 : /// @author Jakob Erdmann
16 : /// @date 26.02.2020
17 : ///
18 : // The RailEdge is a wrapper around a ROEdge or a MSEdge used for railway routing
19 : /****************************************************************************/
20 : #pragma once
21 : #include <config.h>
22 : #include <cassert>
23 :
24 : //#define RailEdge_DEBUG_TURNS
25 : //#define RailEdge_DEBUG_INIT
26 : //#define RailEdge_DEBUG_SUCCESSORS
27 : #define RailEdge_DEBUGID ""
28 : //#define RailEdge_DEBUG_COND(obj) ((obj != 0 && (obj)->getID() == RailEdge_DEBUGID))
29 : #define RailEdge_DEBUG_COND(obj) (true)
30 :
31 : #define REVERSAL_SLACK (POSITION_EPS + NUMERICAL_EPS)
32 :
33 : // ===========================================================================
34 : // class definitions
35 : // ===========================================================================
36 : /// @brief the edge type representing backward edges
37 : template<class E, class V>
38 : class RailEdge {
39 : public:
40 : typedef RailEdge<E, V> _RailEdge;
41 : typedef std::vector<std::pair<const _RailEdge*, const _RailEdge*> > ConstEdgePairVector;
42 :
43 244875 : RailEdge(const E* orig) :
44 244875 : myNumericalID(orig->getNumericalID()),
45 244875 : myOriginal(orig),
46 244875 : myTurnaround(nullptr),
47 244875 : myIsVirtual(true)
48 244875 : { }
49 :
50 3607 : RailEdge(const E* turnStart, const E* turnEnd, int numericalID) :
51 3607 : myNumericalID(numericalID),
52 3607 : myID("TrainReversal!" + turnStart->getID() + "->" + turnEnd->getID()),
53 3607 : myOriginal(nullptr),
54 3607 : myTurnaround(nullptr),
55 3607 : myIsVirtual(true),
56 3607 : myMaxLength(turnStart->getLength() - REVERSAL_SLACK),
57 7214 : myStartLength(turnStart->getLength() - REVERSAL_SLACK) {
58 3607 : myViaSuccessors.push_back(std::make_pair(turnEnd->getRailwayRoutingEdge(), nullptr));
59 3607 : }
60 :
61 : /// @brief Destructor.
62 496964 : virtual ~RailEdge() {
63 3607 : delete myTurnaround;
64 749053 : }
65 :
66 : void update(double maxTrainLength, const std::vector<const E*>& replacementEdges) {
67 178530 : if (maxTrainLength > myMaxLength) {
68 5802 : myMaxLength = maxTrainLength;
69 5802 : myReplacementEdges = replacementEdges;
70 : #ifdef RailEdge_DEBUG_INIT
71 : std::cout << " update RailEdge " << getID() << " myMaxLength=" << myMaxLength << " repl=" << toString(myReplacementEdges) << "\n";
72 : #endif
73 : }
74 : }
75 :
76 180257 : void addVirtualTurns(const E* forward, const E* backward,
77 : std::vector<_RailEdge*>& railEdges, int& numericalID, double dist,
78 : double maxTrainLength, const std::vector<const E*>& replacementEdges) {
79 : // search backwards until dist and add virtual turnaround edges with
80 : // replacement edges up to the real turnaround
81 : #ifdef RailEdge_DEBUG_INIT
82 : std::cout << "addVirtualTurns forward=" << forward->getID() << " backward=" << backward->getID() << " dist=" << dist
83 : << " maxLength=" << maxTrainLength << " repl=" << toString(replacementEdges) << "\n";
84 : #endif
85 180257 : if (dist <= 0) {
86 : return;
87 : }
88 731982 : for (const E* prev : forward->getPredecessors()) {
89 617450 : if (prev == backward) {
90 110926 : continue;
91 : }
92 : const E* bidi = prev->getBidiEdge();
93 506524 : if (bidi != nullptr && backward->isConnectedTo(*bidi, SVC_IGNORING)) {
94 199164 : _RailEdge* prevRailEdge = prev->getRailwayRoutingEdge();
95 199164 : if (prevRailEdge->myTurnaround == nullptr) {
96 2565 : prevRailEdge->myTurnaround = new _RailEdge(prev, bidi, numericalID++);
97 2565 : prevRailEdge->myViaSuccessors.push_back(std::make_pair(prevRailEdge->myTurnaround, nullptr));
98 2565 : railEdges.push_back(prevRailEdge->myTurnaround);
99 : #ifdef RailEdge_DEBUG_INIT
100 : std::cout << " RailEdge " << prevRailEdge->getID() << " virtual turnaround " << prevRailEdge->myTurnaround->getID() << "\n";
101 : #endif
102 : }
103 : /*
104 : // doesn't compile though I don't know why
105 : auto itFound = std::find(replacementEdges.begin(), replacementEdges.end(), prev);
106 : bool notFound = itFound == replacementEdges.end();
107 : */
108 : bool notFound = true;
109 1784701 : for (const E* r : replacementEdges) {
110 1606171 : if (r == prev) {
111 : notFound = false;
112 : break;
113 : }
114 : }
115 :
116 199164 : if (notFound) {
117 : // prevent loops in replacementEdges
118 178530 : prevRailEdge->myTurnaround->update(prev->getLength() + maxTrainLength - REVERSAL_SLACK, replacementEdges);
119 1344 : std::vector<const E*> replacementEdges2;
120 178530 : replacementEdges2.push_back(prev);
121 178530 : replacementEdges2.insert(replacementEdges2.end(), replacementEdges.begin(), replacementEdges.end());
122 178530 : addVirtualTurns(prev, bidi, railEdges, numericalID, dist - prev->getLength(),
123 : maxTrainLength + prev->getLength(), replacementEdges2);
124 177186 : }
125 : }
126 : }
127 : }
128 :
129 40106 : void init(std::vector<_RailEdge*>& railEdges, int& numericalID, double maxTrainLength, bool permitReversal) {
130 : // replace turnaround-via with an explicit RailEdge that checks length
131 86987 : for (const auto& viaPair : myOriginal->getViaSuccessors()) {
132 46881 : if (viaPair.first == myOriginal->getBidiEdge()) {
133 1817 : if (!permitReversal) {
134 90 : continue;
135 : }
136 : // direction reversal
137 1727 : if (myTurnaround == nullptr) {
138 1042 : myTurnaround = new _RailEdge(myOriginal, viaPair.first, numericalID++);
139 1042 : myViaSuccessors.push_back(std::make_pair(myTurnaround, nullptr));
140 1042 : railEdges.push_back(myTurnaround);
141 : #ifdef RailEdge_DEBUG_INIT
142 : std::cout << " added new turnaround " << myTurnaround->getID() << "\n";
143 : #endif
144 : }
145 : #ifdef RailEdge_DEBUG_INIT
146 : std::cout << "RailEdge " << getID() << " actual turnaround " << myTurnaround->getID() << "\n";
147 : #endif
148 1727 : myTurnaround->myIsVirtual = false;
149 : // ensure at least one virtual turnaround (at the start of the
150 : // edge) to avoid driving up to the end of long edges
151 1727 : const double initialDist = MAX2(maxTrainLength - getLength(), POSITION_EPS);
152 3856 : addVirtualTurns(myOriginal, viaPair.first, railEdges, numericalID,
153 : initialDist, getLength(), std::vector<const E*> {myOriginal});
154 : } else {
155 90128 : myViaSuccessors.push_back(std::make_pair(viaPair.first->getRailwayRoutingEdge(),
156 45064 : viaPair.second == nullptr ? nullptr : viaPair.second->getRailwayRoutingEdge()));
157 : }
158 : }
159 : #ifdef RailEdge_DEBUG_SUCCESSORS
160 : std::cout << "RailEdge " << getID() << " successors=" << myViaSuccessors.size() << " orig=" << myOriginal->getViaSuccessors().size() << "\n";
161 : for (const auto& viaPair : myViaSuccessors) {
162 : std::cout << " " << viaPair.first->getID() << "\n";
163 : }
164 : #endif
165 40106 : }
166 :
167 : /// @brief Returns the index (numeric id) of the edge
168 : inline int getNumericalID() const {
169 954632 : return myNumericalID;
170 : }
171 :
172 : /// @brief Returns the original edge
173 : const E* getOriginal() const {
174 1946311 : return myOriginal;
175 : }
176 :
177 : /** @brief Returns the id of the edge
178 : * @return The original edge's id
179 : */
180 : const std::string& getID() const {
181 256 : return myOriginal != nullptr ? myOriginal->getID() : myID;
182 : }
183 :
184 460053 : void insertOriginalEdges(double length, std::vector<const E*>& into) const {
185 460053 : if (myOriginal != nullptr) {
186 392036 : into.push_back(myOriginal);
187 : } else {
188 68017 : double seen = myStartLength;
189 : int nPushed = 0;
190 : //std::cout << "insertOriginalEdges e=" << getID() << " length=" << length << " seen=" << seen << " into=" << toString(into) << "\n";
191 68017 : if (seen >= length && !myIsVirtual) {
192 : return;
193 : }
194 : // we need to find a replacement edge that has a real turn
195 112729 : for (const E* edge : myReplacementEdges) {
196 112704 : into.push_back(edge);
197 112704 : nPushed++;
198 112704 : seen += edge->getLength() - REVERSAL_SLACK;
199 : //std::cout << "insertOriginalEdges e=" << getID() << " length=" << length << " seen=" << seen << " into=" << toString(into) << "\n";
200 112704 : if (seen >= length && edge->isConnectedTo(*edge->getBidiEdge(), SVC_IGNORING)) {
201 : break;
202 : }
203 : }
204 59250 : const int last = (int)into.size() - 1;
205 171954 : for (int i = 0; i < nPushed; i++) {
206 112704 : into.push_back(into[last - i]->getBidiEdge());
207 : }
208 : }
209 : }
210 :
211 : /** @brief Returns the length of the edge
212 : * @return The original edge's length
213 : */
214 : double getLength() const {
215 759832 : return myOriginal == nullptr ? 0 : myOriginal->getLength();
216 : }
217 :
218 : //const RailEdge* getBidiEdge() const {
219 : // return myOriginal->getBidiEdge()->getRailwayRoutingEdge();
220 : //}
221 :
222 : bool isInternal() const {
223 756378 : return myOriginal->isInternal();
224 : }
225 :
226 983465 : inline bool prohibits(const V* const vehicle) const {
227 : #ifdef RailEdge_DEBUG_TURNS
228 : if (myOriginal == nullptr && RailEdge_DEBUG_COND(vehicle)) {
229 : std::cout << getID() << " maxLength=" << myMaxLength << " veh=" << vehicle->getID() << " length=" << vehicle->getLength() << "\n";
230 : }
231 : #endif
232 983465 : return vehicle->getLength() > myMaxLength
233 982759 : || (myOriginal != nullptr && myOriginal->prohibits(vehicle))
234 1966224 : || replacementProhibits(vehicle);
235 : }
236 :
237 2142 : bool replacementProhibits(const V* const vehicle) const {
238 1100512 : for (const E* e : myReplacementEdges) {
239 117793 : if (e->prohibits(vehicle)) {
240 : return true;
241 : }
242 : }
243 : return false;
244 : }
245 :
246 :
247 0 : inline bool restricts(const V* const vehicle) const {
248 0 : return (myOriginal != nullptr && myOriginal->restricts(vehicle)) || replacementRestricts(vehicle);
249 : }
250 :
251 0 : bool replacementRestricts(const V* const vehicle) const {
252 0 : for (const E* e : myReplacementEdges) {
253 0 : if (e->restricts(vehicle)) {
254 : return true;
255 : }
256 : }
257 : return false;
258 : }
259 :
260 788946 : const ConstEdgePairVector& getViaSuccessors(SUMOVehicleClass vClass = SVC_IGNORING, bool ignoreTransientPermissions = false) const {
261 788946 : if (vClass == SVC_IGNORING || myOriginal == nullptr || myOriginal->isTazConnector()) { // || !MSNet::getInstance()->hasPermissions()) {
262 80875 : return myViaSuccessors;
263 : }
264 : #ifdef HAVE_FOX
265 708071 : FXMutexLock lock(mySuccessorMutex);
266 : #endif
267 : auto i = myClassesViaSuccessorMap.find(vClass);
268 708071 : if (i != myClassesViaSuccessorMap.end()) {
269 : // can use cached value
270 699691 : return i->second;
271 : }
272 : // instantiate vector
273 8380 : ConstEdgePairVector& result = myClassesViaSuccessorMap[vClass];
274 : // this vClass is requested for the first time. rebuild all successors
275 19245 : for (const auto& viaPair : myViaSuccessors) {
276 10865 : if (viaPair.first->myOriginal == nullptr
277 8902 : || viaPair.first->myOriginal->isTazConnector()
278 19737 : || myOriginal->isConnectedTo(*viaPair.first->myOriginal, vClass, ignoreTransientPermissions)) {
279 10827 : result.push_back(viaPair);
280 : }
281 : }
282 : return result;
283 : }
284 :
285 : bool isVirtual() const {
286 80845 : return myIsVirtual;
287 : }
288 :
289 : private:
290 : const int myNumericalID;
291 : const std::string myID;
292 : const E* myOriginal;
293 : _RailEdge* myTurnaround;
294 : bool myIsVirtual;
295 :
296 : /// @brief actual edges to return when passing this (turnaround) edge - only forward
297 : std::vector<const E*> myReplacementEdges;
298 :
299 : /// @brief maximum train length for passing this (turnaround) edge
300 : double myMaxLength = std::numeric_limits<double>::max();
301 : /// @brief length of the edge where this turn starts
302 : double myStartLength = 0;
303 :
304 : /// @brief The successors available for a given vClass
305 : mutable std::map<SUMOVehicleClass, ConstEdgePairVector> myClassesViaSuccessorMap;
306 :
307 : mutable ConstEdgePairVector myViaSuccessors;
308 :
309 : #ifdef HAVE_FOX
310 : /// @brief Mutex for accessing successor edges
311 : mutable FXMutex mySuccessorMutex;
312 : #endif
313 :
314 : };
|
