diff options
29 files changed, 356 insertions, 175 deletions
diff --git a/generator/routing_index_generator.cpp b/generator/routing_index_generator.cpp index 9a52353b7d..a96df99732 100644 --- a/generator/routing_index_generator.cpp +++ b/generator/routing_index_generator.cpp @@ -140,6 +140,7 @@ public: // AStarAlgorithm types aliases: using TVertexType = Segment; using TEdgeType = SegmentEdge; + using TWeightType = RouteWeight; explicit DijkstraWrapper(IndexGraph & graph) : m_graph(graph) {} @@ -155,9 +156,9 @@ public: m_graph.GetEdgeList(vertex, false /* isOutgoing */, edges); } - double HeuristicCostEstimate(TVertexType const & /* from */, TVertexType const & /* to */) + TWeightType HeuristicCostEstimate(TVertexType const & /* from */, TVertexType const & /* to */) { - return 0.0; + return GetAStarWeightZero<TWeightType>(); } private: @@ -177,10 +178,10 @@ bool RegionsContain(vector<m2::RegionD> const & regions, m2::PointD const & poin // Calculate distance from the starting border point to the transition along the border. // It could be measured clockwise or counterclockwise, direction doesn't matter. -double CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders, - CrossMwmConnectorSerializer::Transition const & transition) +RouteWeight CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders, + CrossMwmConnectorSerializer::Transition const & transition) { - double distance = 0.0; + RouteWeight distance = GetAStarWeightZero<RouteWeight>(); for (m2::RegionD const & region : borders) { @@ -194,11 +195,11 @@ double CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders, if (m2::RegionD::IsIntersect(transition.GetBackPoint(), transition.GetFrontPoint(), *prev, curr, intersection)) { - distance += prev->Length(intersection); + distance += RouteWeight(prev->Length(intersection)); return distance; } - distance += prev->Length(curr); + distance += RouteWeight(prev->Length(curr)); prev = &curr; } } @@ -288,7 +289,7 @@ void FillWeights(string const & path, string const & mwmFile, string const & cou MwmValue mwmValue(LocalCountryFile(path, platform::CountryFile(country), 0 /* version */)); DeserializeIndexGraph(mwmValue, kCarMask, graph); - map<Segment, map<Segment, double>> weights; + map<Segment, map<Segment, RouteWeight>> weights; auto const numEnters = connector.GetEnters().size(); size_t foundCount = 0; size_t notFoundCount = 0; @@ -323,11 +324,11 @@ void FillWeights(string const & path, string const & mwmFile, string const & cou connector.FillWeights([&](Segment const & enter, Segment const & exit) { auto it0 = weights.find(enter); if (it0 == weights.end()) - return CrossMwmConnector::kNoRoute; + return RouteWeight(CrossMwmConnector::kNoRoute); auto it1 = it0->second.find(exit); if (it1 == it0->second.end()) - return CrossMwmConnector::kNoRoute; + return RouteWeight(CrossMwmConnector::kNoRoute); return it1->second; }); diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt index e5d0091dcc..3a3abab457 100644 --- a/routing/CMakeLists.txt +++ b/routing/CMakeLists.txt @@ -12,6 +12,7 @@ set( async_router.cpp async_router.hpp base/astar_algorithm.hpp + base/astar_weight.hpp base/followed_polyline.cpp base/followed_polyline.hpp bicycle_directions.cpp @@ -92,6 +93,8 @@ set( route.cpp route.hpp route_point.hpp + route_weight.cpp + route_weight.hpp router.cpp router.hpp router_delegate.cpp diff --git a/routing/base/astar_algorithm.hpp b/routing/base/astar_algorithm.hpp index ebd27b4085..072ae2e5a3 100644 --- a/routing/base/astar_algorithm.hpp +++ b/routing/base/astar_algorithm.hpp @@ -1,30 +1,31 @@ #pragma once +#include "routing/base/astar_weight.hpp" + #include "base/assert.hpp" #include "base/cancellable.hpp" -#include "std/algorithm.hpp" -#include "std/functional.hpp" -#include "std/iostream.hpp" -#include "std/limits.hpp" -#include "std/map.hpp" -#include "std/queue.hpp" -#include "std/vector.hpp" + +#include <algorithm> +#include <iostream> +#include <map> +#include <queue> +#include <vector> namespace routing { -template <typename TVertexType> +template <typename TVertexType, typename TWeightType> struct RoutingResult { - vector<TVertexType> path; - double distance; + std::vector<TVertexType> path; + TWeightType distance; - RoutingResult() : distance(0) {} + RoutingResult() : distance(GetAStarWeightZero<TWeightType>()) {} void Clear() { path.clear(); - distance = 0; + distance = GetAStarWeightZero<TWeightType>(); } }; @@ -35,6 +36,7 @@ public: using TGraphType = TGraph; using TVertexType = typename TGraphType::TVertexType; using TEdgeType = typename TGraphType::TEdgeType; + using TWeightType = typename TGraphType::TWeightType; enum class Result { @@ -43,7 +45,7 @@ public: Cancelled }; - friend ostream & operator<<(ostream & os, Result const & result) + friend std::ostream & operator<<(std::ostream & os, Result const & result) { switch (result) { @@ -76,7 +78,7 @@ public: return m_distanceMap.find(vertex) != m_distanceMap.cend(); } - double GetDistance(TVertexType const & vertex) const + TWeightType GetDistance(TVertexType const & vertex) const { auto const & it = m_distanceMap.find(vertex); if (it == m_distanceMap.cend()) @@ -85,7 +87,7 @@ public: return it->second; } - void SetDistance(TVertexType const & vertex, double distance) + void SetDistance(TVertexType const & vertex, TWeightType const & distance) { m_distanceMap[vertex] = distance; } @@ -95,11 +97,11 @@ public: m_parents[parent] = child; } - void ReconstructPath(TVertexType const & v, vector<TVertexType> & path) const; + void ReconstructPath(TVertexType const & v, std::vector<TVertexType> & path) const; private: - map<TVertexType, double> m_distanceMap; - map<TVertexType, TVertexType> m_parents; + std::map<TVertexType, TWeightType> m_distanceMap; + std::map<TVertexType, TVertexType> m_parents; }; // VisitVertex returns true: wave will continue @@ -114,30 +116,31 @@ public: VisitVertex && visitVertex, Context & context) const; Result FindPath(TGraphType & graph, TVertexType const & startVertex, - TVertexType const & finalVertex, RoutingResult<TVertexType> & result, + TVertexType const & finalVertex, RoutingResult<TVertexType, TWeightType> & result, my::Cancellable const & cancellable = my::Cancellable(), TOnVisitedVertexCallback onVisitedVertexCallback = nullptr) const; Result FindPathBidirectional(TGraphType & graph, TVertexType const & startVertex, TVertexType const & finalVertex, - RoutingResult<TVertexType> & result, + RoutingResult<TVertexType, TWeightType> & result, my::Cancellable const & cancellable = my::Cancellable(), TOnVisitedVertexCallback onVisitedVertexCallback = nullptr) const; // Adjust route to the previous one. // adjustLimit - distance limit for wave propagation, measured in same units as graph edges length. typename AStarAlgorithm<TGraph>::Result AdjustRoute( - TGraphType & graph, TVertexType const & startVertex, vector<TEdgeType> const & prevRoute, - double adjustLimit, RoutingResult<TVertexType> & result, my::Cancellable const & cancellable, - TOnVisitedVertexCallback onVisitedVertexCallback) const; + TGraphType & graph, TVertexType const & startVertex, std::vector<TEdgeType> const & prevRoute, + TWeightType const & adjustLimit, RoutingResult<TVertexType, TWeightType> & result, + my::Cancellable const & cancellable, TOnVisitedVertexCallback onVisitedVertexCallback) const; private: // Periodicity of switching a wave of bidirectional algorithm. static uint32_t constexpr kQueueSwitchPeriod = 128; // Precision of comparison weights. - static double constexpr kEpsilon = 1e-6; - static double constexpr kInfiniteDistance = numeric_limits<double>::max(); + static TWeightType constexpr kEpsilon = GetAStarWeightEpsilon<TWeightType>(); + static TWeightType constexpr kZeroDistance = GetAStarWeightZero<TWeightType>(); + static TWeightType constexpr kInfiniteDistance = GetAStarWeightMax<TWeightType>(); class PeriodicPollCancellable final { @@ -160,12 +163,15 @@ private: // comment for FindPath for more information. struct State { - State(TVertexType const & vertex, double distance) : vertex(vertex), distance(distance) {} + State(TVertexType const & vertex, TWeightType const & distance) + : vertex(vertex), distance(distance) + { + } inline bool operator>(State const & rhs) const { return distance > rhs.distance; } TVertexType vertex; - double distance; + TWeightType distance; }; // BidirectionalStepContext keeps all the information that is needed to @@ -183,7 +189,7 @@ private: pS = ConsistentHeuristic(bestVertex); } - double TopDistance() const + TWeightType TopDistance() const { ASSERT(!queue.empty(), ()); return bestDistance.at(queue.top().vertex); @@ -192,10 +198,10 @@ private: // p_f(v) = 0.5*(π_f(v) - π_r(v)) + 0.5*π_r(t) // p_r(v) = 0.5*(π_r(v) - π_f(v)) + 0.5*π_f(s) // p_r(v) + p_f(v) = const. Note: this condition is called consistence. - double ConsistentHeuristic(TVertexType const & v) const + TWeightType ConsistentHeuristic(TVertexType const & v) const { - double const piF = graph.HeuristicCostEstimate(v, finalVertex); - double const piR = graph.HeuristicCostEstimate(v, startVertex); + auto const piF = graph.HeuristicCostEstimate(v, finalVertex); + auto const piR = graph.HeuristicCostEstimate(v, startVertex); if (forward) { /// @todo careful: with this "return" here and below in the Backward case @@ -210,7 +216,7 @@ private: } } - void GetAdjacencyList(TVertexType const & v, vector<TEdgeType> & adj) + void GetAdjacencyList(TVertexType const & v, std::vector<TEdgeType> & adj) { if (forward) graph.GetOutgoingEdgesList(v, adj); @@ -222,26 +228,34 @@ private: TVertexType const & startVertex; TVertexType const & finalVertex; TGraph & graph; - double const m_piRT; - double const m_piFS; + TWeightType const m_piRT; + TWeightType const m_piFS; - priority_queue<State, vector<State>, greater<State>> queue; - map<TVertexType, double> bestDistance; - map<TVertexType, TVertexType> parent; + std::priority_queue<State, std::vector<State>, std::greater<State>> queue; + std::map<TVertexType, TWeightType> bestDistance; + std::map<TVertexType, TVertexType> parent; TVertexType bestVertex; - double pS; + TWeightType pS; }; - static void ReconstructPath(TVertexType const & v, map<TVertexType, TVertexType> const & parent, - vector<TVertexType> & path); + static void ReconstructPath(TVertexType const & v, + std::map<TVertexType, TVertexType> const & parent, + std::vector<TVertexType> & path); static void ReconstructPathBidirectional(TVertexType const & v, TVertexType const & w, - map<TVertexType, TVertexType> const & parentV, - map<TVertexType, TVertexType> const & parentW, - vector<TVertexType> & path); + std::map<TVertexType, TVertexType> const & parentV, + std::map<TVertexType, TVertexType> const & parentW, + std::vector<TVertexType> & path); }; template <typename TGraph> +constexpr typename TGraph::TWeightType AStarAlgorithm<TGraph>::kEpsilon; +template <typename TGraph> +constexpr typename TGraph::TWeightType AStarAlgorithm<TGraph>::kInfiniteDistance; +template <typename TGraph> +constexpr typename TGraph::TWeightType AStarAlgorithm<TGraph>::kZeroDistance; + +template <typename TGraph> template <typename VisitVertex, typename AdjustEdgeWeight> void AStarAlgorithm<TGraph>::PropagateWave(TGraphType & graph, TVertexType const & startVertex, VisitVertex && visitVertex, @@ -250,12 +264,12 @@ void AStarAlgorithm<TGraph>::PropagateWave(TGraphType & graph, TVertexType const { context.Clear(); - priority_queue<State, vector<State>, greater<State>> queue; + std::priority_queue<State, std::vector<State>, std::greater<State>> queue; - context.SetDistance(startVertex, 0.0); - queue.push(State(startVertex, 0.0)); + context.SetDistance(startVertex, kZeroDistance); + queue.push(State(startVertex, kZeroDistance)); - vector<TEdgeType> adj; + std::vector<TEdgeType> adj; while (!queue.empty()) { @@ -271,12 +285,12 @@ void AStarAlgorithm<TGraph>::PropagateWave(TGraphType & graph, TVertexType const graph.GetOutgoingEdgesList(stateV.vertex, adj); for (auto const & edge : adj) { - State stateW(edge.GetTarget(), 0.0); + State stateW(edge.GetTarget(), kZeroDistance); if (stateV.vertex == stateW.vertex) continue; - double const edgeWeight = adjustEdgeWeight(stateV.vertex, edge); - double const newReducedDist = stateV.distance + edgeWeight; + auto const edgeWeight = adjustEdgeWeight(stateV.vertex, edge); + auto const newReducedDist = stateV.distance + edgeWeight; if (newReducedDist >= context.GetDistance(stateW.vertex) - kEpsilon) continue; @@ -315,7 +329,7 @@ void AStarAlgorithm<TGraph>::PropagateWave(TGraphType & graph, TVertexType const template <typename TGraph> typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPath( TGraphType & graph, TVertexType const & startVertex, TVertexType const & finalVertex, - RoutingResult<TVertexType> & result, my::Cancellable const & cancellable, + RoutingResult<TVertexType, TWeightType> & result, my::Cancellable const & cancellable, TOnVisitedVertexCallback onVisitedVertexCallback) const { result.Clear(); @@ -345,13 +359,13 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPath( }; auto adjustEdgeWeight = [&](TVertexType const & vertex, TEdgeType const & edge) { - double const len = edge.GetWeight(); - double const piV = graph.HeuristicCostEstimate(vertex, finalVertex); - double const piW = graph.HeuristicCostEstimate(edge.GetTarget(), finalVertex); - double const reducedLen = len + piW - piV; + auto const len = edge.GetWeight(); + auto const piV = graph.HeuristicCostEstimate(vertex, finalVertex); + auto const piW = graph.HeuristicCostEstimate(edge.GetTarget(), finalVertex); + auto const reducedLen = len + piW - piV; CHECK(reducedLen >= -kEpsilon, ("Invariant violated:", reducedLen, "<", -kEpsilon)); - return max(reducedLen, 0.0); + return std::max(reducedLen, kZeroDistance); }; PropagateWave(graph, startVertex, visitVertex, adjustEdgeWeight, context); @@ -370,7 +384,7 @@ template <typename TGraph> typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirectional( TGraphType & graph, TVertexType const & startVertex, TVertexType const & finalVertex, - RoutingResult<TVertexType> & result, + RoutingResult<TVertexType, TWeightType> & result, my::Cancellable const & cancellable, TOnVisitedVertexCallback onVisitedVertexCallback) const { @@ -381,14 +395,14 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect BidirectionalStepContext backward(false /* forward */, startVertex, finalVertex, graph); bool foundAnyPath = false; - double bestPathReducedLength = 0.0; - double bestPathRealLength = 0.0; + auto bestPathReducedLength = kZeroDistance; + auto bestPathRealLength = kZeroDistance; - forward.bestDistance[startVertex] = 0.0; - forward.queue.push(State(startVertex, 0.0 /* distance */)); + forward.bestDistance[startVertex] = kZeroDistance; + forward.queue.push(State(startVertex, kZeroDistance)); - backward.bestDistance[finalVertex] = 0.0; - backward.queue.push(State(finalVertex, 0.0 /* distance */)); + backward.bestDistance[finalVertex] = kZeroDistance; + backward.queue.push(State(finalVertex, kZeroDistance)); // To use the search code both for backward and forward directions // we keep the pointers to everything related to the search in the @@ -397,7 +411,7 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect BidirectionalStepContext * cur = &forward; BidirectionalStepContext * nxt = &backward; - vector<TEdgeType> adj; + std::vector<TEdgeType> adj; // It is not necessary to check emptiness for both queues here // because if we have not found a path by the time one of the @@ -413,12 +427,12 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect return Result::Cancelled; if (steps % kQueueSwitchPeriod == 0) - swap(cur, nxt); + std::swap(cur, nxt); if (foundAnyPath) { - double const curTop = cur->TopDistance(); - double const nxtTop = nxt->TopDistance(); + auto const curTop = cur->TopDistance(); + auto const nxtTop = nxt->TopDistance(); // The intuition behind this is that we cannot obtain a path shorter // than the left side of the inequality because that is how any path we find @@ -454,17 +468,17 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect cur->GetAdjacencyList(stateV.vertex, adj); for (auto const & edge : adj) { - State stateW(edge.GetTarget(), 0.0); + State stateW(edge.GetTarget(), kZeroDistance); if (stateV.vertex == stateW.vertex) continue; - double const len = edge.GetWeight(); - double const pV = cur->ConsistentHeuristic(stateV.vertex); - double const pW = cur->ConsistentHeuristic(stateW.vertex); - double const reducedLen = len + pW - pV; + auto const len = edge.GetWeight(); + auto const pV = cur->ConsistentHeuristic(stateV.vertex); + auto const pW = cur->ConsistentHeuristic(stateW.vertex); + auto const reducedLen = len + pW - pV; CHECK(reducedLen >= -kEpsilon, ("Invariant violated:", reducedLen, "<", -kEpsilon)); - double const newReducedDist = stateV.distance + max(reducedLen, 0.0); + auto const newReducedDist = stateV.distance + std::max(reducedLen, kZeroDistance); auto const itCur = cur->bestDistance.find(stateW.vertex); if (itCur != cur->bestDistance.end() && newReducedDist >= itCur->second - kEpsilon) @@ -473,10 +487,10 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect auto const itNxt = nxt->bestDistance.find(stateW.vertex); if (itNxt != nxt->bestDistance.end()) { - double const distW = itNxt->second; + auto const distW = itNxt->second; // Reduced length that the path we've just found has in the original graph: // find the reduced length of the path's parts in the reduced forward and backward graphs. - double const curPathReducedLength = newReducedDist + distW; + auto const curPathReducedLength = newReducedDist + distW; // No epsilon here: it is ok to overshoot slightly. if (!foundAnyPath || bestPathReducedLength > curPathReducedLength) { @@ -504,9 +518,9 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect template <typename TGraph> typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::AdjustRoute( - TGraphType & graph, TVertexType const & startVertex, vector<TEdgeType> const & prevRoute, - double adjustLimit, RoutingResult<TVertexType> & result, my::Cancellable const & cancellable, - TOnVisitedVertexCallback onVisitedVertexCallback) const + TGraphType & graph, TVertexType const & startVertex, std::vector<TEdgeType> const & prevRoute, + TWeightType const & adjustLimit, RoutingResult<TVertexType, TWeightType> & result, + my::Cancellable const & cancellable, TOnVisitedVertexCallback onVisitedVertexCallback) const { CHECK(!prevRoute.empty(), ()); @@ -515,11 +529,11 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::AdjustRoute( onVisitedVertexCallback = [](TVertexType const &, TVertexType const &) {}; bool wasCancelled = false; - double minDistance = kInfiniteDistance; + auto minDistance = kInfiniteDistance; TVertexType returnVertex; - map<TVertexType, double> remainingDistances; - double remainingDistance = 0.0; + std::map<TVertexType, TWeightType> remainingDistances; + auto remainingDistance = kZeroDistance; for (auto it = prevRoute.crbegin(); it != prevRoute.crend(); ++it) { @@ -547,7 +561,7 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::AdjustRoute( auto it = remainingDistances.find(vertex); if (it != remainingDistances.cend()) { - double const fullDistance = distance + it->second; + auto const fullDistance = distance + it->second; if (fullDistance < minDistance) { minDistance = fullDistance; @@ -593,8 +607,8 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::AdjustRoute( // static template <typename TGraph> void AStarAlgorithm<TGraph>::ReconstructPath(TVertexType const & v, - map<TVertexType, TVertexType> const & parent, - vector<TVertexType> & path) + std::map<TVertexType, TVertexType> const & parent, + std::vector<TVertexType> & path) { path.clear(); TVertexType cur = v; @@ -612,12 +626,13 @@ void AStarAlgorithm<TGraph>::ReconstructPath(TVertexType const & v, // static template <typename TGraph> void AStarAlgorithm<TGraph>::ReconstructPathBidirectional( - TVertexType const & v, TVertexType const & w, map<TVertexType, TVertexType> const & parentV, - map<TVertexType, TVertexType> const & parentW, vector<TVertexType> & path) + TVertexType const & v, TVertexType const & w, + std::map<TVertexType, TVertexType> const & parentV, + std::map<TVertexType, TVertexType> const & parentW, std::vector<TVertexType> & path) { - vector<TVertexType> pathV; + std::vector<TVertexType> pathV; ReconstructPath(v, parentV, pathV); - vector<TVertexType> pathW; + std::vector<TVertexType> pathW; ReconstructPath(w, parentW, pathW); path.clear(); path.reserve(pathV.size() + pathW.size()); @@ -627,7 +642,7 @@ void AStarAlgorithm<TGraph>::ReconstructPathBidirectional( template <typename TGraph> void AStarAlgorithm<TGraph>::Context::ReconstructPath(TVertexType const & v, - vector<TVertexType> & path) const + std::vector<TVertexType> & path) const { AStarAlgorithm<TGraph>::ReconstructPath(v, m_parents, path); } diff --git a/routing/base/astar_weight.hpp b/routing/base/astar_weight.hpp new file mode 100644 index 0000000000..2d8c725462 --- /dev/null +++ b/routing/base/astar_weight.hpp @@ -0,0 +1,35 @@ +#pragma once + +#include <limits> + +namespace routing +{ +template <typename WeightType> +constexpr WeightType GetAStarWeightZero(); + +template <> +constexpr double GetAStarWeightZero<double>() +{ + return 0.0; +} + +// Precision of comparison weights. +template <typename WeightType> +constexpr WeightType GetAStarWeightEpsilon(); + +template <> +constexpr double GetAStarWeightEpsilon<double>() +{ + return 1e-6; +} + +template <typename WeightType> +constexpr WeightType GetAStarWeightMax(); + +template <> +constexpr double GetAStarWeightMax<double>() +{ + return std::numeric_limits<double>::max(); +} + +} // namespace routing diff --git a/routing/cross_mwm_connector.cpp b/routing/cross_mwm_connector.cpp index 23bcc316a9..64297d37a0 100644 --- a/routing/cross_mwm_connector.cpp +++ b/routing/cross_mwm_connector.cpp @@ -150,7 +150,7 @@ void CrossMwmConnector::AddEdge(Segment const & segment, Weight weight, std::vector<SegmentEdge> & edges) const { if (weight != static_cast<Weight>(kNoRoute)) - edges.emplace_back(segment, static_cast<double>(weight)); + edges.emplace_back(segment, RouteWeight(static_cast<double>(weight))); } CrossMwmConnector::Transition const & CrossMwmConnector::GetTransition( diff --git a/routing/cross_mwm_connector.hpp b/routing/cross_mwm_connector.hpp index ad42bba97f..1b5d49ac72 100644 --- a/routing/cross_mwm_connector.hpp +++ b/routing/cross_mwm_connector.hpp @@ -62,9 +62,9 @@ public: { for (Segment const & exit : m_exits) { - double const weight = calcWeight(enter, exit); + RouteWeight const weight = calcWeight(enter, exit); // Edges weights should be >= astar heuristic, so use std::ceil. - m_weights.push_back(static_cast<Weight>(std::ceil(weight))); + m_weights.push_back(static_cast<Weight>(std::ceil(weight.GetWeight()))); } } } diff --git a/routing/cross_mwm_osrm_graph.cpp b/routing/cross_mwm_osrm_graph.cpp index 4edc11bcb2..58c7aae429 100644 --- a/routing/cross_mwm_osrm_graph.cpp +++ b/routing/cross_mwm_osrm_graph.cpp @@ -103,8 +103,8 @@ void AddSegmentEdge(NumMwmIds const & numMwmIds, OsrmFtSegMapping const & segMap double constexpr kAstarHeuristicFactor = 100000; //// Osrm multiplies seconds to 10, so we need to divide it back. double constexpr kOSRMWeightToSecondsMultiplier = 0.1; - edges.emplace_back(segment, - osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier * kAstarHeuristicFactor); + edges.emplace_back(segment, RouteWeight(osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier * + kAstarHeuristicFactor)); } } // namespace diff --git a/routing/cross_mwm_road_graph.hpp b/routing/cross_mwm_road_graph.hpp index 058e55450d..271fddc943 100644 --- a/routing/cross_mwm_road_graph.hpp +++ b/routing/cross_mwm_road_graph.hpp @@ -126,6 +126,7 @@ public: using TCachingKey = pair<TWrittenNodeId, Index::MwmId>; using TVertexType = BorderCross; using TEdgeType = CrossWeightedEdge; + using TWeightType = double; struct Hash { diff --git a/routing/cross_mwm_router.cpp b/routing/cross_mwm_router.cpp index 1523a84b4d..df4e6a15c6 100644 --- a/routing/cross_mwm_router.cpp +++ b/routing/cross_mwm_router.cpp @@ -13,7 +13,7 @@ namespace /// Function to run AStar Algorithm from the base. IRouter::ResultCode CalculateRoute(BorderCross const & startPos, BorderCross const & finalPos, CrossMwmRoadGraph & roadGraph, RouterDelegate const & delegate, - RoutingResult<BorderCross> & route) + RoutingResult<BorderCross, double /* WeightType */> & route) { using TAlgorithm = AStarAlgorithm<CrossMwmRoadGraph>; @@ -90,7 +90,7 @@ IRouter::ResultCode CalculateCrossMwmPath(TRoutingNodes const & startGraphNodes, return IRouter::EndPointNotFound; // Finding path through maps. - RoutingResult<BorderCross> tempRoad; + RoutingResult<BorderCross, double /* WeightType */> tempRoad; code = CalculateRoute({startNode, startNode}, {finalNode, finalNode}, roadGraph, delegate, tempRoad); cost = tempRoad.distance; if (code != IRouter::NoError) diff --git a/routing/index_graph.cpp b/routing/index_graph.cpp index bc9ec4a76f..27f91c479e 100644 --- a/routing/index_graph.cpp +++ b/routing/index_graph.cpp @@ -109,14 +109,16 @@ void IndexGraph::GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge GetEdgeList(segment, false /* isOutgoing */, edges); } -double IndexGraph::HeuristicCostEstimate(Segment const & from, Segment const & to) +RouteWeight IndexGraph::HeuristicCostEstimate(Segment const & from, Segment const & to) { - return m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)); + return RouteWeight( + m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */))); } -double IndexGraph::CalcSegmentWeight(Segment const & segment) +RouteWeight IndexGraph::CalcSegmentWeight(Segment const & segment) { - return m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId())); + return RouteWeight( + m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId()))); } void IndexGraph::GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing, @@ -161,16 +163,16 @@ void IndexGraph::GetNeighboringEdge(Segment const & from, Segment const & to, bo if (m_roadAccess.GetSegmentType(to) != RoadAccess::Type::Yes) return; - double const weight = CalcSegmentWeight(isOutgoing ? to : from) + - GetPenalties(isOutgoing ? from : to, isOutgoing ? to : from); + RouteWeight const weight = CalcSegmentWeight(isOutgoing ? to : from) + + GetPenalties(isOutgoing ? from : to, isOutgoing ? to : from); edges.emplace_back(to, weight); } -double IndexGraph::GetPenalties(Segment const & u, Segment const & v) const +RouteWeight IndexGraph::GetPenalties(Segment const & u, Segment const & v) const { if (IsUTurn(u, v)) - return m_estimator->GetUTurnPenalty(); + return RouteWeight(m_estimator->GetUTurnPenalty()); - return 0.0; + return RouteWeight(0.0); } } // namespace routing diff --git a/routing/index_graph.hpp b/routing/index_graph.hpp index 6cb01899bd..ecf171aa0c 100644 --- a/routing/index_graph.hpp +++ b/routing/index_graph.hpp @@ -26,6 +26,7 @@ public: // AStarAlgorithm types aliases: using TVertexType = Segment; using TEdgeType = SegmentEdge; + using TWeightType = RouteWeight; IndexGraph() = default; explicit IndexGraph(unique_ptr<GeometryLoader> loader, shared_ptr<EdgeEstimator> estimator); @@ -52,7 +53,7 @@ public: // Interface for AStarAlgorithm: void GetOutgoingEdgesList(Segment const & segment, vector<SegmentEdge> & edges); void GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge> & edges); - double HeuristicCostEstimate(Segment const & from, Segment const & to); + RouteWeight HeuristicCostEstimate(Segment const & from, Segment const & to); void PushFromSerializer(Joint::Id jointId, RoadPoint const & rp) { @@ -72,12 +73,12 @@ public: } private: - double CalcSegmentWeight(Segment const & segment); + RouteWeight CalcSegmentWeight(Segment const & segment); void GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing, vector<SegmentEdge> & edges); void GetNeighboringEdge(Segment const & from, Segment const & to, bool isOutgoing, vector<SegmentEdge> & edges); - double GetPenalties(Segment const & u, Segment const & v) const; + RouteWeight GetPenalties(Segment const & u, Segment const & v) const; m2::PointD const & GetPoint(Segment const & segment, bool front) { return GetGeometry().GetRoad(segment.GetFeatureId()).GetPoint(segment.GetPointId(front)); diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp index 27270a4af9..ed2fc3b63f 100644 --- a/routing/index_graph_starter.cpp +++ b/routing/index_graph_starter.cpp @@ -141,7 +141,7 @@ void IndexGraphStarter::GetFakeToNormalEdge(FakeVertex const & fakeVertex, bool { auto const segment = fakeVertex.GetSegmentWithDirection(forward); m2::PointD const & pointTo = GetPoint(segment, true /* front */); - double const weight = m_graph.GetEstimator().CalcLeapWeight(fakeVertex.GetPoint(), pointTo); + RouteWeight const weight(m_graph.GetEstimator().CalcLeapWeight(fakeVertex.GetPoint(), pointTo)); edges.emplace_back(segment, weight); } @@ -155,16 +155,16 @@ void IndexGraphStarter::GetNormalToFakeEdge(Segment const & segment, FakeVertex { if (m_graph.IsTransition(segment, isOutgoing)) { - edges.emplace_back(fakeSegment, - m_graph.GetEstimator().CalcLeapWeight(pointFrom, fakeVertex.GetPoint())); + edges.emplace_back(fakeSegment, RouteWeight(m_graph.GetEstimator().CalcLeapWeight( + pointFrom, fakeVertex.GetPoint()))); } return; } if (fakeVertex.Fits(segment)) { - edges.emplace_back(fakeSegment, - m_graph.GetEstimator().CalcLeapWeight(pointFrom, fakeVertex.GetPoint())); + edges.emplace_back(fakeSegment, RouteWeight(m_graph.GetEstimator().CalcLeapWeight( + pointFrom, fakeVertex.GetPoint()))); } } @@ -180,8 +180,8 @@ void IndexGraphStarter::ConnectLeapToTransitions(Segment const & segment, bool i // So |isEnter| below should be set to true. m_graph.ForEachTransition( segment.GetMwmId(), !isOutgoing /* isEnter */, [&](Segment const & transition) { - edges.emplace_back(transition, m_graph.GetEstimator().CalcLeapWeight( - segmentPoint, GetPoint(transition, isOutgoing))); + edges.emplace_back(transition, RouteWeight(m_graph.GetEstimator().CalcLeapWeight( + segmentPoint, GetPoint(transition, isOutgoing)))); }); } } // namespace routing diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp index 95f7f239b5..8912c1b539 100644 --- a/routing/index_graph_starter.hpp +++ b/routing/index_graph_starter.hpp @@ -19,6 +19,7 @@ public: // AStarAlgorithm types aliases: using TVertexType = IndexGraph::TVertexType; using TEdgeType = IndexGraph::TEdgeType; + using TWeightType = IndexGraph::TWeightType; class FakeVertex final { @@ -100,10 +101,10 @@ public: GetEdgesList(segment, false /* isOutgoing */, edges); } - double HeuristicCostEstimate(TVertexType const & from, TVertexType const & to) + RouteWeight HeuristicCostEstimate(TVertexType const & from, TVertexType const & to) { - return m_graph.GetEstimator().CalcHeuristic(GetPoint(from, true /* front */), - GetPoint(to, true /* front */)); + return RouteWeight(m_graph.GetEstimator().CalcHeuristic(GetPoint(from, true /* front */), + GetPoint(to, true /* front */))); } double CalcSegmentWeight(Segment const & segment) const diff --git a/routing/index_router.cpp b/routing/index_router.cpp index 4ff89d0083..83e2f7328d 100644 --- a/routing/index_router.cpp +++ b/routing/index_router.cpp @@ -108,7 +108,7 @@ IRouter::ResultCode FindPath( typename Graph::TVertexType const & start, typename Graph::TVertexType const & finish, RouterDelegate const & delegate, Graph & graph, typename AStarAlgorithm<Graph>::TOnVisitedVertexCallback const & onVisitedVertexCallback, - RoutingResult<typename Graph::TVertexType> & routingResult) + RoutingResult<typename Graph::TVertexType, typename Graph::TWeightType> & routingResult) { AStarAlgorithm<Graph> algorithm; return ConvertResult<Graph>(algorithm.FindPathBidirectional(graph, start, finish, routingResult, @@ -469,7 +469,7 @@ IRouter::ResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoin delegate.OnPointCheck(pointFrom); }; - RoutingResult<Segment> routingResult; + RoutingResult<Segment, RouteWeight> routingResult; IRouter::ResultCode const result = FindPath(starter.GetStart(), starter.GetFinish(), delegate, starter, onVisitJunction, routingResult); if (result != IRouter::NoError) @@ -519,7 +519,8 @@ IRouter::ResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints, for (size_t i = lastSubroute.GetBeginSegmentIdx(); i < lastSubroute.GetEndSegmentIdx(); ++i) { auto const & step = steps[i]; - prevEdges.emplace_back(step.GetSegment(), starter.CalcSegmentWeight(step.GetSegment())); + prevEdges.emplace_back(step.GetSegment(), + RouteWeight(starter.CalcSegmentWeight(step.GetSegment()))); } uint32_t visitCount = 0; @@ -538,9 +539,10 @@ IRouter::ResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints, }; AStarAlgorithm<IndexGraphStarter> algorithm; - RoutingResult<Segment> result; - auto resultCode = ConvertResult<IndexGraphStarter>(algorithm.AdjustRoute( - starter, starter.GetStart(), prevEdges, kAdjustLimitSec, result, delegate, onVisitJunction)); + RoutingResult<Segment, RouteWeight> result; + auto resultCode = ConvertResult<IndexGraphStarter>( + algorithm.AdjustRoute(starter, starter.GetStart(), prevEdges, RouteWeight(kAdjustLimitSec), + result, delegate, onVisitJunction)); if (resultCode != IRouter::NoError) return resultCode; @@ -672,7 +674,7 @@ IRouter::ResultCode IndexRouter::ProcessLeaps(vector<Segment> const & input, ("Different mwm ids for leap enter and exit, i:", i, "size of input:", input.size())); IRouter::ResultCode result = IRouter::InternalError; - RoutingResult<Segment> routingResult; + RoutingResult<Segment, RouteWeight> routingResult; // In case of leaps from the start to its mwm transition and from finish mwm transition // route calculation should be made on the world graph (WorldGraph::Mode::NoLeaps). if ((current.GetMwmId() == starter.GetStartVertex().GetMwmId() diff --git a/routing/road_graph.hpp b/routing/road_graph.hpp index 4924e22bf2..b84db0e3ac 100644 --- a/routing/road_graph.hpp +++ b/routing/road_graph.hpp @@ -131,6 +131,7 @@ public: // CheckGraphConnectivity() types aliases: using Vertex = Junction; using Edge = routing::Edge; + using Weight = double; enum class Mode { diff --git a/routing/road_graph_router.cpp b/routing/road_graph_router.cpp index 252cfc5769..7615aac1d1 100644 --- a/routing/road_graph_router.cpp +++ b/routing/road_graph_router.cpp @@ -193,7 +193,7 @@ IRouter::ResultCode RoadGraphRouter::CalculateRoute(Checkpoints const & checkpoi m_roadGraph->AddFakeEdges(startPos, startVicinity); m_roadGraph->AddFakeEdges(finalPos, finalVicinity); - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; IRoutingAlgorithm::Result const resultCode = m_algorithm->CalculateRoute(*m_roadGraph, startPos, finalPos, delegate, result); diff --git a/routing/route_weight.cpp b/routing/route_weight.cpp new file mode 100644 index 0000000000..f962b6d345 --- /dev/null +++ b/routing/route_weight.cpp @@ -0,0 +1,17 @@ +#include "routing/route_weight.hpp" + +using namespace std; + +namespace routing +{ +ostream & operator<<(ostream & os, RouteWeight const & routeWeight) +{ + os << routeWeight.GetWeight(); + return os; +} + +RouteWeight operator*(double lhs, RouteWeight const & rhs) +{ + return RouteWeight(lhs * rhs.GetWeight()); +} +} // namespace routing diff --git a/routing/route_weight.hpp b/routing/route_weight.hpp new file mode 100644 index 0000000000..adebf609bc --- /dev/null +++ b/routing/route_weight.hpp @@ -0,0 +1,73 @@ +#pragma once + +#include "routing/base/astar_weight.hpp" + +#include <iostream> +#include <limits> + +namespace routing +{ +class RouteWeight final +{ +public: + RouteWeight() = default; + + constexpr explicit RouteWeight(double weight) : m_weight(weight) {} + + double GetWeight() const { return m_weight; } + + bool operator<(RouteWeight const & rhs) const { return m_weight < rhs.m_weight; } + + bool operator==(RouteWeight const & rhs) const { return !((*this) < rhs) && !(rhs < (*this)); } + + bool operator!=(RouteWeight const & rhs) const { return !((*this) == rhs); } + + bool operator>(RouteWeight const & rhs) const { return rhs < (*this); } + + bool operator>=(RouteWeight const & rhs) const { return !((*this) < rhs); } + + RouteWeight operator+(RouteWeight const & rhs) const + { + return RouteWeight(m_weight + rhs.m_weight); + } + + RouteWeight operator-(RouteWeight const & rhs) const + { + return RouteWeight(m_weight - rhs.m_weight); + } + + RouteWeight & operator+=(RouteWeight const & rhs) + { + m_weight += rhs.m_weight; + return *this; + } + + RouteWeight operator-() const { return RouteWeight(-m_weight); } + +private: + double m_weight = 0.0; +}; + +std::ostream & operator<<(std::ostream & os, RouteWeight const & routeWeight); + +RouteWeight operator*(double lhs, RouteWeight const & rhs); + +template <> +constexpr RouteWeight GetAStarWeightMax<RouteWeight>() +{ + return RouteWeight(std::numeric_limits<double>::max()); +} + +template <> +constexpr RouteWeight GetAStarWeightZero<RouteWeight>() +{ + return RouteWeight(0.0); +} + +template <> +constexpr RouteWeight GetAStarWeightEpsilon<RouteWeight>() +{ + return RouteWeight(GetAStarWeightEpsilon<double>()); +} + +} // namespace routing diff --git a/routing/routing.pro b/routing/routing.pro index 2c11c4358c..823bcdd534 100644 --- a/routing/routing.pro +++ b/routing/routing.pro @@ -51,6 +51,7 @@ SOURCES += \ road_graph_router.cpp \ road_index.cpp \ route.cpp \ + route_weight.cpp \ router.cpp \ router_delegate.cpp \ routing_algorithm.cpp \ @@ -72,6 +73,7 @@ SOURCES += \ HEADERS += \ async_router.hpp \ base/astar_algorithm.hpp \ + base/astar_weight.hpp \ base/followed_polyline.hpp \ bicycle_directions.hpp \ checkpoints.hpp \ @@ -115,6 +117,7 @@ HEADERS += \ road_point.hpp \ route.hpp \ route_point.hpp \ + route_weight.hpp \ router.hpp \ router_delegate.hpp \ routing_algorithm.hpp \ diff --git a/routing/routing_algorithm.cpp b/routing/routing_algorithm.cpp index 334e521bd7..8540a834ba 100644 --- a/routing/routing_algorithm.cpp +++ b/routing/routing_algorithm.cpp @@ -50,6 +50,7 @@ class RoadGraph public: using TVertexType = Junction; using TEdgeType = WeightedEdge; + using TWeightType = double; RoadGraph(IRoadGraph const & roadGraph) : m_roadGraph(roadGraph) @@ -135,7 +136,7 @@ IRoutingAlgorithm::Result AStarRoutingAlgorithm::CalculateRoute(IRoadGraph const Junction const & startPos, Junction const & finalPos, RouterDelegate const & delegate, - RoutingResult<Junction> & path) + RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path) { AStarProgress progress(0, 95); uint32_t visitCount = 0; @@ -164,7 +165,7 @@ IRoutingAlgorithm::Result AStarRoutingAlgorithm::CalculateRoute(IRoadGraph const IRoutingAlgorithm::Result AStarBidirectionalRoutingAlgorithm::CalculateRoute( IRoadGraph const & graph, Junction const & startPos, Junction const & finalPos, - RouterDelegate const & delegate, RoutingResult<Junction> & path) + RouterDelegate const & delegate, RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path) { AStarProgress progress(0, 95); uint32_t visitCount = 0; diff --git a/routing/routing_algorithm.hpp b/routing/routing_algorithm.hpp index 437494734e..1101ee2782 100644 --- a/routing/routing_algorithm.hpp +++ b/routing/routing_algorithm.hpp @@ -27,7 +27,7 @@ public: virtual Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, Junction const & finalPos, RouterDelegate const & delegate, - RoutingResult<Junction> & path) = 0; + RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path) = 0; }; string DebugPrint(IRoutingAlgorithm::Result const & result); @@ -39,7 +39,7 @@ public: // IRoutingAlgorithm overrides: Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, Junction const & finalPos, RouterDelegate const & delegate, - RoutingResult<Junction> & path) override; + RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path) override; }; // AStar-bidirectional routing algorithm implementation @@ -49,7 +49,7 @@ public: // IRoutingAlgorithm overrides: Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, Junction const & finalPos, RouterDelegate const & delegate, - RoutingResult<Junction> & path) override; + RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path) override; }; } // namespace routing diff --git a/routing/routing_tests/astar_algorithm_test.cpp b/routing/routing_tests/astar_algorithm_test.cpp index 40c40b6015..7a0f82bbc2 100644 --- a/routing/routing_tests/astar_algorithm_test.cpp +++ b/routing/routing_tests/astar_algorithm_test.cpp @@ -26,6 +26,7 @@ class UndirectedGraph public: using TVertexType = unsigned; using TEdgeType = Edge; + using TWeightType = double; void AddEdge(unsigned u, unsigned v, unsigned w) { @@ -63,7 +64,7 @@ void TestAStar(UndirectedGraph & graph, vector<unsigned> const & expectedRoute, { TAlgorithm algo; - RoutingResult<unsigned> actualRoute; + RoutingResult<unsigned /* VertexType */, double /* WeightType */> actualRoute; TEST_EQUAL(TAlgorithm::Result::OK, algo.FindPath(graph, 0u, 4u, actualRoute), ()); TEST_EQUAL(expectedRoute, actualRoute.path, ()); TEST_ALMOST_EQUAL_ULPS(expectedDistance, actualRoute.distance, ()); @@ -105,7 +106,7 @@ UNIT_TEST(AdjustRoute) vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}}; TAlgorithm algo; - RoutingResult<unsigned> result; + RoutingResult<unsigned /* VertexType */, double /* WeightType */> result; auto code = algo.AdjustRoute(graph, 6 /* start */, prevRoute, 1.0 /* limit */, result, my::Cancellable(), nullptr /* onVisitedVertexCallback */); @@ -126,7 +127,7 @@ UNIT_TEST(AdjustRouteNoPath) vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}}; TAlgorithm algo; - RoutingResult<unsigned> result; + RoutingResult<unsigned /* VertexType */, double /* WeightType */> result; auto code = algo.AdjustRoute(graph, 6 /* start */, prevRoute, 1.0 /* limit */, result, my::Cancellable(), nullptr /* onVisitedVertexCallback */); @@ -147,7 +148,7 @@ UNIT_TEST(AdjustRouteOutOfLimit) vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}}; TAlgorithm algo; - RoutingResult<unsigned> result; + RoutingResult<unsigned /* VertexType */, double /* WeightType */> result; auto code = algo.AdjustRoute(graph, 6 /* start */, prevRoute, 1.0 /* limit */, result, my::Cancellable(), nullptr /* onVisitedVertexCallback */); diff --git a/routing/routing_tests/astar_router_test.cpp b/routing/routing_tests/astar_router_test.cpp index 2645807d58..516e479dc0 100644 --- a/routing/routing_tests/astar_router_test.cpp +++ b/routing/routing_tests/astar_router_test.cpp @@ -30,7 +30,7 @@ void TestAStarRouterMock(Junction const & startPos, Junction const & finalPos, InitRoadGraphMockSourceWithTest2(graph); RouterDelegate delegate; - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; TRoutingAlgorithm algorithm; TEST_EQUAL(TRoutingAlgorithm::Result::OK, algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ()); @@ -98,7 +98,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_RouteIsFound) MakeJunctionForTesting(m2::PointD(0, 60)), MakeJunctionForTesting(m2::PointD(40, 100))}; RouterDelegate delegate; - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; TRoutingAlgorithm algorithm; TEST_EQUAL(TRoutingAlgorithm::Result::OK, algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ()); @@ -167,7 +167,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_RoutesInConnectedComponents) { RouterDelegate delegate; Junction const finalPos = roadInfo_2[j].m_junctions[0]; - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; TEST_EQUAL(TRoutingAlgorithm::Result::NoPath, algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ()); TEST_EQUAL(TRoutingAlgorithm::Result::NoPath, @@ -183,7 +183,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_RoutesInConnectedComponents) { RouterDelegate delegate; Junction const finalPos = roadInfo_1[j].m_junctions[0]; - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; TEST_EQUAL(TRoutingAlgorithm::Result::OK, algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ()); TEST_EQUAL(TRoutingAlgorithm::Result::OK, @@ -199,7 +199,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_RoutesInConnectedComponents) { RouterDelegate delegate; Junction const finalPos = roadInfo_2[j].m_junctions[0]; - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; TEST_EQUAL(TRoutingAlgorithm::Result::OK, algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ()); TEST_EQUAL(TRoutingAlgorithm::Result::OK, @@ -227,7 +227,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_PickTheFasterRoad1) // path3 = 1/5 + 8/4 + 1/5 = 2.4 RouterDelegate delegate; - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; TRoutingAlgorithm algorithm; TEST_EQUAL(TRoutingAlgorithm::Result::OK, algorithm.CalculateRoute(graph, MakeJunctionForTesting(m2::PointD(2, 2)), @@ -262,7 +262,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_PickTheFasterRoad2) // path3 = 1/5 + 8/4.4 + 1/5 = 2.2 RouterDelegate delegate; - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; TRoutingAlgorithm algorithm; TEST_EQUAL(TRoutingAlgorithm::Result::OK, algorithm.CalculateRoute(graph, MakeJunctionForTesting(m2::PointD(2, 2)), @@ -293,7 +293,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_PickTheFasterRoad3) // path3 = 1/5 + 8/4.9 + 1/5 = 2.03 RouterDelegate delegate; - RoutingResult<Junction> result; + RoutingResult<Junction, double /* WeightType */> result; TRoutingAlgorithm algorithm; TEST_EQUAL(TRoutingAlgorithm::Result::OK, algorithm.CalculateRoute(graph, MakeJunctionForTesting(m2::PointD(2, 2)), diff --git a/routing/routing_tests/cross_mwm_connector_test.cpp b/routing/routing_tests/cross_mwm_connector_test.cpp index 4260c49e3c..8d3c886ab5 100644 --- a/routing/routing_tests/cross_mwm_connector_test.cpp +++ b/routing/routing_tests/cross_mwm_connector_test.cpp @@ -143,7 +143,7 @@ UNIT_TEST(TwoWayExit) UNIT_TEST(Serialization) { - float constexpr kEdgesWeight = 4444; + RouteWeight constexpr kEdgesWeight = RouteWeight(4444.0); vector<uint8_t> buffer; { @@ -159,7 +159,7 @@ UNIT_TEST(Serialization) CrossMwmConnectorSerializer::AddTransition(transition, kCarMask, carConnector); carConnector.FillWeights( - [](Segment const & enter, Segment const & exit) { return kEdgesWeight; }); + [&](Segment const & enter, Segment const & exit) { return kEdgesWeight; }); serial::CodingParams const codingParams; MemWriter<vector<uint8_t>> writer(buffer); @@ -244,9 +244,15 @@ UNIT_TEST(Serialization) UNIT_TEST(WeightsSerialization) { size_t constexpr kNumTransitions = 3; - vector<double> const weights = { - 4.0, 20.0, CrossMwmConnector::kNoRoute, 12.0, CrossMwmConnector::kNoRoute, 40.0, 48.0, - 24.0, 12.0}; + vector<RouteWeight> const weights = {RouteWeight(4.0), + RouteWeight(20.0), + RouteWeight(CrossMwmConnector::kNoRoute), + RouteWeight(12.0), + RouteWeight(CrossMwmConnector::kNoRoute), + RouteWeight(40.0), + RouteWeight(48.0), + RouteWeight(24.0), + RouteWeight(12.0)}; TEST_EQUAL(weights.size(), kNumTransitions * kNumTransitions, ()); vector<uint8_t> buffer; @@ -305,7 +311,7 @@ UNIT_TEST(WeightsSerialization) for (uint32_t exitId = 0; exitId < kNumTransitions; ++exitId) { auto const weight = weights[weightIdx]; - if (weight != CrossMwmConnector::kNoRoute) + if (weight != RouteWeight(CrossMwmConnector::kNoRoute)) { expectedEdges.emplace_back(Segment(mwmId, exitId, 1 /* segmentIdx */, false /* forward */), weight); diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp index 8700d7c869..66efd2efad 100644 --- a/routing/routing_tests/index_graph_tools.cpp +++ b/routing/routing_tests/index_graph_tools.cpp @@ -275,13 +275,13 @@ AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & sta double & timeSec) { AStarAlgorithm<IndexGraphStarter> algorithm; - RoutingResult<Segment> routingResult; + RoutingResult<Segment, RouteWeight> routingResult; auto const resultCode = algorithm.FindPathBidirectional( starter, starter.GetStart(), starter.GetFinish(), routingResult, {} /* cancellable */, {} /* onVisitedVertexCallback */); - timeSec = routingResult.distance; + timeSec = routingResult.distance.GetWeight(); roadPoints = routingResult.path; return resultCode; } diff --git a/routing/segment.hpp b/routing/segment.hpp index cd476c7e7b..e8001894e1 100644 --- a/routing/segment.hpp +++ b/routing/segment.hpp @@ -2,10 +2,11 @@ #include "routing/num_mwm_id.hpp" #include "routing/road_point.hpp" +#include "routing/route_weight.hpp" -#include "std/cstdint.hpp" -#include "std/sstream.hpp" -#include "std/string.hpp" +#include <cstdint> +#include <sstream> +#include <string> namespace routing { @@ -74,9 +75,12 @@ private: class SegmentEdge final { public: - SegmentEdge(Segment const & target, double weight) : m_target(target), m_weight(weight) {} + SegmentEdge(Segment const & target, RouteWeight const & weight) + : m_target(target), m_weight(weight) + { + } Segment const & GetTarget() const { return m_target; } - double GetWeight() const { return m_weight; } + RouteWeight const & GetWeight() const { return m_weight; } bool operator==(SegmentEdge const & edge) const { @@ -93,20 +97,20 @@ public: private: // Target is vertex going to for outgoing edges, vertex going from for ingoing edges. Segment m_target; - double m_weight; + RouteWeight m_weight; }; -inline string DebugPrint(Segment const & segment) +inline std::string DebugPrint(Segment const & segment) { - ostringstream out; + std::ostringstream out; out << "Segment(" << segment.GetMwmId() << ", " << segment.GetFeatureId() << ", " << segment.GetSegmentIdx() << ", " << segment.IsForward() << ")"; return out.str(); } -inline string DebugPrint(SegmentEdge const & edge) +inline std::string DebugPrint(SegmentEdge const & edge) { - ostringstream out; + std::ostringstream out; out << "Edge(" << DebugPrint(edge.GetTarget()) << ", " << edge.GetWeight() << ")"; return out.str(); } diff --git a/routing/world_graph.cpp b/routing/world_graph.cpp index c7090bcfec..a831e219a8 100644 --- a/routing/world_graph.cpp +++ b/routing/world_graph.cpp @@ -55,9 +55,10 @@ void WorldGraph::GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge GetEdgeList(segment, false /* isOutgoing */, false /* isLeap */, edges); } -double WorldGraph::HeuristicCostEstimate(Segment const & from, Segment const & to) +RouteWeight WorldGraph::HeuristicCostEstimate(Segment const & from, Segment const & to) { - return m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)); + return RouteWeight( + m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */))); } void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges) @@ -69,7 +70,7 @@ void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, vector<Segme m2::PointD const & from = GetPoint(segment, true /* front */); m2::PointD const & to = GetPoint(twin, true /* front */); double const weight = m_estimator->CalcHeuristic(from, to); - edges.emplace_back(twin, weight); + edges.emplace_back(twin, RouteWeight(weight)); } } diff --git a/routing/world_graph.hpp b/routing/world_graph.hpp index 8d3ecb10ca..d1c88dc4f3 100644 --- a/routing/world_graph.hpp +++ b/routing/world_graph.hpp @@ -20,6 +20,7 @@ public: // AStarAlgorithm types aliases: using TVertexType = IndexGraph::TVertexType; using TEdgeType = IndexGraph::TEdgeType; + using TWeightType = IndexGraph::TWeightType; // CheckGraphConnectivity() types aliases: using Vertex = TVertexType; @@ -56,7 +57,7 @@ public: // Interface for AStarAlgorithm: void GetOutgoingEdgesList(Segment const & segment, vector<SegmentEdge> & edges); void GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge> & edges); - double HeuristicCostEstimate(Segment const & from, Segment const & to); + RouteWeight HeuristicCostEstimate(Segment const & from, Segment const & to); template <typename Fn> void ForEachTransition(NumMwmId numMwmId, bool isEnter, Fn && fn) diff --git a/xcode/routing/routing.xcodeproj/project.pbxproj b/xcode/routing/routing.xcodeproj/project.pbxproj index 64f9bcf08d..104e3468e0 100644 --- a/xcode/routing/routing.xcodeproj/project.pbxproj +++ b/xcode/routing/routing.xcodeproj/project.pbxproj @@ -56,6 +56,9 @@ 3462FDAD1DC1E5BF00906FD7 /* libopening_hours.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 3462FDAC1DC1E5BF00906FD7 /* libopening_hours.a */; }; 349D1CE01E3F589900A878FD /* restrictions_serialization.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 349D1CDE1E3F589900A878FD /* restrictions_serialization.cpp */; }; 349D1CE11E3F589900A878FD /* restrictions_serialization.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 349D1CDF1E3F589900A878FD /* restrictions_serialization.hpp */; }; + 40A111CD1F2F6776005E6AD5 /* route_weight.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 40A111CB1F2F6776005E6AD5 /* route_weight.cpp */; }; + 40A111CE1F2F6776005E6AD5 /* route_weight.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 40A111CC1F2F6776005E6AD5 /* route_weight.hpp */; }; + 40A111D01F2F9704005E6AD5 /* astar_weight.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 40A111CF1F2F9704005E6AD5 /* astar_weight.hpp */; }; 56099E291CC7C97D00A7772A /* loaded_path_segment.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E251CC7C97D00A7772A /* loaded_path_segment.hpp */; }; 56099E2A1CC7C97D00A7772A /* routing_result_graph.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E261CC7C97D00A7772A /* routing_result_graph.hpp */; }; 56099E2B1CC7C97D00A7772A /* turn_candidate.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E271CC7C97D00A7772A /* turn_candidate.hpp */; }; @@ -322,6 +325,9 @@ 349D1CDF1E3F589900A878FD /* restrictions_serialization.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = restrictions_serialization.hpp; sourceTree = "<group>"; }; 34F558351DBF2A2600A4FC11 /* common-debug.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; name = "common-debug.xcconfig"; path = "../common-debug.xcconfig"; sourceTree = "<group>"; }; 34F558361DBF2A2600A4FC11 /* common-release.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; name = "common-release.xcconfig"; path = "../common-release.xcconfig"; sourceTree = "<group>"; }; + 40A111CB1F2F6776005E6AD5 /* route_weight.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = route_weight.cpp; sourceTree = "<group>"; }; + 40A111CC1F2F6776005E6AD5 /* route_weight.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = route_weight.hpp; sourceTree = "<group>"; }; + 40A111CF1F2F9704005E6AD5 /* astar_weight.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = astar_weight.hpp; sourceTree = "<group>"; }; 56099E251CC7C97D00A7772A /* loaded_path_segment.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = loaded_path_segment.hpp; sourceTree = "<group>"; }; 56099E261CC7C97D00A7772A /* routing_result_graph.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = routing_result_graph.hpp; sourceTree = "<group>"; }; 56099E271CC7C97D00A7772A /* turn_candidate.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = turn_candidate.hpp; sourceTree = "<group>"; }; @@ -592,6 +598,7 @@ 671F58BA1B874EA20032311E /* base */ = { isa = PBXGroup; children = ( + 40A111CF1F2F9704005E6AD5 /* astar_weight.hpp */, 671F58BB1B874EC80032311E /* followed_polyline.cpp */, 671F58BC1B874EC80032311E /* followed_polyline.hpp */, A1616E2D1B6B60B3003F078E /* astar_progress.hpp */, @@ -732,6 +739,8 @@ 675343FA1A3F640D00A0A8C3 /* routing */ = { isa = PBXGroup; children = ( + 40A111CB1F2F6776005E6AD5 /* route_weight.cpp */, + 40A111CC1F2F6776005E6AD5 /* route_weight.hpp */, 5694CEC51EBA25F7004576D3 /* road_access_serialization.cpp */, 5694CEC61EBA25F7004576D3 /* road_access_serialization.hpp */, 5694CEC71EBA25F7004576D3 /* road_access.cpp */, @@ -927,12 +936,14 @@ 670EE5721B664796001E8064 /* directions_engine.hpp in Headers */, 56C439291E93BF8C00998E29 /* cross_mwm_graph.hpp in Headers */, 0C81E1541F02589800DC66DF /* traffic_stash.hpp in Headers */, + 40A111D01F2F9704005E6AD5 /* astar_weight.hpp in Headers */, 0C8705051E0182F200BCAF71 /* route_point.hpp in Headers */, A1876BC71BB19C4300C9C743 /* speed_camera.hpp in Headers */, 56EA2FD51D8FD8590083F01A /* routing_helpers.hpp in Headers */, 0C15B8021F02A61B0058E253 /* checkpoints.hpp in Headers */, 0C5F5D211E798B0400307B98 /* cross_mwm_connector_serialization.hpp in Headers */, 0C0DF9221DE898B70055A22F /* index_graph_starter.hpp in Headers */, + 40A111CE1F2F6776005E6AD5 /* route_weight.hpp in Headers */, 0C090C881E4E276700D52AFD /* world_graph.hpp in Headers */, 0C08AA351DF83223004195DD /* index_graph_serialization.hpp in Headers */, 5694CECD1EBA25F7004576D3 /* road_access.hpp in Headers */, @@ -1185,6 +1196,7 @@ 0C81E1531F02589800DC66DF /* traffic_stash.cpp in Sources */, 0CF5E8AA1E8EA7A1001ED497 /* coding_test.cpp in Sources */, 675344191A3F644F00A0A8C3 /* osrm2feature_map.cpp in Sources */, + 40A111CD1F2F6776005E6AD5 /* route_weight.cpp in Sources */, 670D049E1B0B4A970013A7AC /* nearest_edge_finder.cpp in Sources */, 0C5F5D251E798B3800307B98 /* cross_mwm_connector_test.cpp in Sources */, 674F9BD61B0A580E00704FFA /* turns_generator.cpp in Sources */, |