[routing] Improve A* progress in UI for LeapsOnly mode

6 files changed, 225 insertions, 145 deletions

diff --git a/routing/base/astar_progress.hpp b/routing/base/astar_progress.hpp
index c932b5ced6..ffcfec0e84 100644
--- a/routing/base/astar_progress.hpp
+++ b/routing/base/astar_progress.hpp
@@ -1,66 +1,129 @@
 #pragma once
 
+#include "geometry/mercator.hpp"
 #include "geometry/point2d.hpp"
 
-#include "geometry/mercator.hpp"
+#include "base/assert.hpp"
+#include "base/logging.hpp"
+
+#include <iterator>
+#include <list>
 
 namespace routing
 {
-class AStarProgress
+class AStarSubProgress
 {
 public:
-  AStarProgress(float startValue, float stopValue)
-      : m_startValue(startValue), m_stopValue(stopValue) {}
-
-  void Initialize(m2::PointD const & startPoint, m2::PointD const & finalPoint)
+  AStarSubProgress(m2::PointD const & start, m2::PointD const & finish, double contributionCoef)
+    : m_contributionCoef(contributionCoef), m_startPoint(start), m_finalPoint(finish)
   {
-    m_startPoint = startPoint;
-    m_finalPoint = finalPoint;
-    m_initialDistance = MercatorBounds::DistanceOnEarth(startPoint, finalPoint);
-    m_forwardDistance = m_initialDistance;
-    m_backwardDistance = m_initialDistance;
-    m_lastValue = m_startValue;
+    ASSERT_NOT_EQUAL(m_contributionCoef, 0.0, ());
+
+    m_fullDistance = MercatorBounds::DistanceOnEarth(start, finish);
+    m_forwardDistance = m_fullDistance;
+    m_backwardDistance = m_fullDistance;
   }
 
-  float GetProgressForDirectedAlgo(m2::PointD const & point)
+  explicit AStarSubProgress(double contributionCoef)
+      : m_contributionCoef(contributionCoef)
   {
-    return CheckConstraints(
-        1.0 - MercatorBounds::DistanceOnEarth(point, m_finalPoint) / m_initialDistance);
+    ASSERT_NOT_EQUAL(m_contributionCoef, 0.0, ());
   }
 
-  float GetProgressForBidirectedAlgo(m2::PointD const & point, m2::PointD const & target)
+  double UpdateProgress(m2::PointD const & current, m2::PointD const & end)
   {
-    if (target == m_finalPoint)
-      m_forwardDistance = MercatorBounds::DistanceOnEarth(point, target);
-    else if (target == m_startPoint)
-      m_backwardDistance = MercatorBounds::DistanceOnEarth(point, target);
-    else
-      ASSERT(false, ());
-    return CheckConstraints(2.0 - (m_forwardDistance + m_backwardDistance) / m_initialDistance);
+    ASSERT_NOT_EQUAL(m_fullDistance, 0.0, ());
+
+    double dist = MercatorBounds::DistanceOnEarth(current, end);
+    double & toUpdate = end == m_finalPoint ? m_forwardDistance : m_backwardDistance;
+
+    toUpdate = std::min(toUpdate, dist);
+
+    double part = 2.0 - (m_forwardDistance + m_backwardDistance) / m_fullDistance;
+    part = base::clamp(part, 0.0, 1.0);
+    double newProgress =  m_contributionCoef * part;
+
+    m_currentProgress = std::max(newProgress, m_currentProgress);
+
+    return m_currentProgress;
   }
 
-  float GetLastValue() const { return m_lastValue; }
+  double UpdateProgress(double subSubProgressValue)
+  {
+    return m_currentProgress + m_contributionCoef * subSubProgressValue;
+  }
 
-private:
-  float CheckConstraints(float const & roadPart)
+  void Flush(double progress)
   {
-    float mappedValue = m_startValue + (m_stopValue - m_startValue) * roadPart;
-    mappedValue = base::clamp(mappedValue, m_startValue, m_stopValue);
-    if (mappedValue > m_lastValue)
-      m_lastValue = mappedValue;
-    return m_lastValue;
+    m_currentProgress += m_contributionCoef * progress;
   }
 
-  float m_forwardDistance;
-  float m_backwardDistance;
-  float m_initialDistance;
-  float m_lastValue;
+  double GetMaxContribution() const { return m_contributionCoef; }
+
+private:
+
+  double m_currentProgress = 0.0;
+
+  double m_contributionCoef = 0.0;
+
+  double m_fullDistance = 0.0;
+
+  double m_forwardDistance = 0.0;
+  double m_backwardDistance = 0.0;
 
   m2::PointD m_startPoint;
   m2::PointD m_finalPoint;
-
-  float const m_startValue;
-  float const m_stopValue;
 };
 
+class AStarProgress
+{
+public:
+
+  AStarProgress()
+  {
+    m_subProgresses.emplace_back(AStarSubProgress(1.0));
+  }
+
+  void AppendSubProgress(AStarSubProgress const & subProgress)
+  {
+    m_subProgresses.emplace_back(subProgress);
+  }
+
+  void EraseLastSubProgress()
+  {
+    ASSERT(m_subProgresses.begin() != m_subProgresses.end(), ());
+    ASSERT(m_subProgresses.begin() != std::prev(m_subProgresses.end()), ());
+
+    auto prevLast = std::prev(std::prev(m_subProgresses.end()));
+    prevLast->Flush(m_subProgresses.back().GetMaxContribution());
+
+    CHECK(!m_subProgresses.empty(), ());
+    auto last = std::prev(m_subProgresses.end());
+    m_subProgresses.erase(last);
+  }
+
+  double UpdateProgress(m2::PointD const & current, m2::PointD const & end)
+  {
+    return UpdateProgressImpl(m_subProgresses.begin(), current, end) * 100.0;
+  }
+
+  double GetLastValue() const { return m_lastValue * 100.0; }
+
+private:
+
+  using ListItem = std::list<AStarSubProgress>::iterator;
+
+  double UpdateProgressImpl(ListItem subProgress, m2::PointD const & current,
+                            m2::PointD const & end)
+  {
+    if (std::next(subProgress) != m_subProgresses.end())
+      return subProgress->UpdateProgress(UpdateProgressImpl(std::next(subProgress), current, end));
+
+    return subProgress->UpdateProgress(current, end);
+  }
+
+  double m_lastValue = 0.0;
+
+  std::list<AStarSubProgress> m_subProgresses;
+};
 }  //  namespace routing
diff --git a/routing/checkpoints.cpp b/routing/checkpoints.cpp
index db7c281ee1..461ebae2ba 100644
--- a/routing/checkpoints.cpp
+++ b/routing/checkpoints.cpp
@@ -44,6 +44,14 @@ void Checkpoints::PassNextPoint()
   CHECK(!IsFinished(), ());
   ++m_passedIdx;
 }
+double Checkpoints::GetPathLength() const
+{
+  double dist = 0.0;
+  for (size_t i = 1; i < m_points.size(); ++i)
+    dist += MercatorBounds::DistanceOnEarth(m_points[i - 1], m_points[i]);
+
+  return dist;
+}
 
 std::string DebugPrint(Checkpoints const & checkpoints)
 {
diff --git a/routing/checkpoints.hpp b/routing/checkpoints.hpp
index 4ac771e367..e0e905833c 100644
--- a/routing/checkpoints.hpp
+++ b/routing/checkpoints.hpp
@@ -28,6 +28,8 @@ public:
   size_t GetNumSubroutes() const { return m_points.size() - 1; }
   bool IsFinished() const { return m_passedIdx >= GetNumSubroutes(); }
 
+  double GetPathLength() const;
+
   void PassNextPoint();
 
 private:
diff --git a/routing/index_router.cpp b/routing/index_router.cpp
index ec9c7e3ead..d18cca0f2c 100644
--- a/routing/index_router.cpp
+++ b/routing/index_router.cpp
@@ -40,6 +40,7 @@
 #include "base/assert.hpp"
 #include "base/exception.hpp"
 #include "base/logging.hpp"
+#include "base/scope_guard.hpp"
 #include "base/stl_helpers.hpp"
 
 #include <algorithm>
@@ -58,8 +59,11 @@ namespace
 {
 size_t constexpr kMaxRoadCandidates = 12;
 float constexpr kProgressInterval = 2;
+uint32_t constexpr kVisitPeriodForLeaps = 10;
 uint32_t constexpr kVisitPeriod = 40;
 
+double constexpr kLeapsStageContribution = 0.3;
+
 // If user left the route within this range(meters), adjust the route. Else full rebuild.
 double constexpr kAdjustRangeM = 5000.0;
 // Full rebuild if distance(meters) is less.
@@ -179,36 +183,6 @@ void GetOutdatedMwms(DataSource & dataSource, vector<string> & outdatedMwms)
   }
 }
 
-struct ProgressRange final
-{
-  float const startValue;
-  float const stopValue;
-};
-
-ProgressRange CalcProgressRange(Checkpoints const & checkpoints, size_t subrouteIdx)
-{
-  double fullDistance = 0.0;
-  double startDistance = 0.0;
-  double finishDistance = 0.0;
-
-  for (size_t i = 0; i < checkpoints.GetNumSubroutes(); ++i)
-  {
-    double const distance =
-        MercatorBounds::DistanceOnEarth(checkpoints.GetPoint(i), checkpoints.GetPoint(i + 1));
-    fullDistance += distance;
-    if (i < subrouteIdx)
-      startDistance += distance;
-    if (i <= subrouteIdx)
-      finishDistance += distance;
-  }
-
-  if (fullDistance == 0.0)
-    return {100.0, 100.0};
-
-  return {static_cast<float>(startDistance / fullDistance * 100.0),
-          static_cast<float>(finishDistance / fullDistance * 100.0)};
-}
-
 void PushPassedSubroutes(Checkpoints const & checkpoints, vector<Route::SubrouteAttrs> & subroutes)
 {
   for (size_t i = 0; i < checkpoints.GetPassedIdx(); ++i)
@@ -419,6 +393,8 @@ RouterResultCode IndexRouter::DoCalculateRoute(Checkpoints const & checkpoints,
   vector<Route::SubrouteAttrs> subroutes;
   PushPassedSubroutes(checkpoints, subroutes);
   unique_ptr<IndexGraphStarter> starter;
+  AStarProgress progress;
+  double const checkpointsLength = checkpoints.GetPathLength();
 
   for (size_t i = checkpoints.GetPassedIdx(); i < checkpoints.GetNumSubroutes(); ++i)
   {
@@ -447,7 +423,14 @@ RouterResultCode IndexRouter::DoCalculateRoute(Checkpoints const & checkpoints,
                                       isStartSegmentStrictForward, *graph);
 
     vector<Segment> subroute;
-    auto const result = CalculateSubroute(checkpoints, i, delegate, subrouteStarter, subroute);
+    double const contributionCoef =
+        MercatorBounds::DistanceOnEarth(startCheckpoint, finishCheckpoint) / checkpointsLength;
+
+    AStarSubProgress subProgress(startCheckpoint, finishCheckpoint, contributionCoef);
+    progress.AppendSubProgress(subProgress);
+    auto const result = CalculateSubroute(checkpoints, i, delegate, progress, subrouteStarter,
+                                          subroute);
+    progress.EraseLastSubProgress();
 
     if (result != RouterResultCode::NoError)
       return result;
@@ -519,6 +502,7 @@ vector<Segment> ProcessJoints(vector<JointSegment> const & jointsPath,
 RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
                                                 size_t subrouteIdx,
                                                 RouterDelegate const & delegate,
+                                                AStarProgress & progress,
                                                 IndexGraphStarter & starter,
                                                 vector<Segment> & subroute)
 {
@@ -545,30 +529,6 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
 
   LOG(LINFO, ("Routing in mode:", starter.GetGraph().GetMode()));
 
-  auto const progressRange = CalcProgressRange(checkpoints, subrouteIdx);
-  AStarProgress progress(progressRange.startValue, progressRange.stopValue);
-  progress.Initialize(starter.GetStartJunction().GetPoint(),
-                      starter.GetFinishJunction().GetPoint());
-
-  uint32_t visitCount = 0;
-  auto lastValue = progress.GetLastValue();
-
-  auto onVisitJunction = [&](Segment const & from, Segment const & to) {
-    if (++visitCount % kVisitPeriod != 0)
-      return;
-
-    m2::PointD const & pointFrom = starter.GetPoint(from, true /* front */);
-    m2::PointD const & pointTo = starter.GetPoint(to, true /* front */);
-    auto const newValue = progress.GetProgressForBidirectedAlgo(pointFrom, pointTo);
-    if (newValue - lastValue > kProgressInterval)
-    {
-      lastValue = newValue;
-      delegate.OnProgress(newValue);
-    }
-
-    delegate.OnPointCheck(pointFrom);
-  };
-
   auto checkLength = [&starter](RouteWeight const & weight) { return starter.CheckLength(weight); };
 
   base::HighResTimer timer;
@@ -577,6 +537,9 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
   {
     IndexGraphStarterJoints<IndexGraphStarter> jointStarter(starter, starter.GetStartSegment(), starter.GetFinishSegment());
     RoutingResult<JointSegment, RouteWeight> routingResult;
+
+    uint32_t visitCount = 0;
+    auto lastValue = progress.GetLastValue();
     auto const onVisitJunctionJoints = [&](JointSegment const & from, JointSegment const & to)
     {
       ++visitCount;
@@ -585,7 +548,7 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
 
       m2::PointD const & pointFrom = jointStarter.GetPoint(from, true /* front */);
       m2::PointD const & pointTo = jointStarter.GetPoint(to, true /* front */);
-      auto const newValue = progress.GetProgressForBidirectedAlgo(pointFrom, pointTo);
+      auto const newValue = progress.UpdateProgress(pointFrom, pointTo);
       if (newValue - lastValue > kProgressInterval)
       {
         lastValue = newValue;
@@ -616,6 +579,33 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
     using Edge = IndexGraphStarter::Edge;
     using Weight = IndexGraphStarter::Weight;
 
+    uint32_t visitCount = 0;
+    auto lastValue = progress.GetLastValue();
+    if (mode == WorldGraphMode::LeapsOnly)
+    {
+      AStarSubProgress leapsProgress(checkpoints.GetPoint(subrouteIdx),
+                                     checkpoints.GetPoint(subrouteIdx + 1),
+                                     kLeapsStageContribution);
+      progress.AppendSubProgress(leapsProgress);
+    }
+
+    auto eachCount = mode == WorldGraphMode::LeapsOnly ? kVisitPeriodForLeaps : kVisitPeriod;
+    auto onVisitJunction = [&](Segment const & from, Segment const & to) {
+      if (++visitCount % eachCount != 0)
+        return;
+
+      m2::PointD const & pointFrom = starter.GetPoint(from, true /* front */);
+      m2::PointD const & pointTo = starter.GetPoint(to, true /* front */);
+      auto const newValue = progress.UpdateProgress(pointFrom, pointTo);
+      if (newValue - lastValue > kProgressInterval)
+      {
+        lastValue = newValue;
+        delegate.OnProgress(newValue);
+      }
+
+      delegate.OnPointCheck(pointFrom);
+    };
+
     RoutingResult<Segment, RouteWeight> routingResult;
     AStarAlgorithm<Vertex, Edge, Weight>::Params params(
       starter, starter.GetStartSegment(), starter.GetFinishSegment(), nullptr /* prevRoute */,
@@ -627,9 +617,10 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
     if (result != RouterResultCode::NoError)
       return result;
 
-    RouterResultCode const leapsResult = ProcessLeapsJoints(routingResult.m_path, delegate, 
+    progress.EraseLastSubProgress();
+    RouterResultCode const leapsResult = ProcessLeapsJoints(routingResult.m_path, delegate,
                                                             starter.GetGraph().GetMode(), 
-                                                            starter, subroute);
+                                                            starter, progress, subroute);
 
     if (leapsResult != RouterResultCode::NoError)
       return leapsResult;
@@ -673,10 +664,6 @@ RouterResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints,
 
   starter.Append(*m_lastFakeEdges);
 
-  AStarProgress progress(0, 95);
-  progress.Initialize(starter.GetStartJunction().GetPoint(),
-                      starter.GetFinishJunction().GetPoint());
-
   vector<SegmentEdge> prevEdges;
   CHECK_LESS_OR_EQUAL(lastSubroute.GetEndSegmentIdx(), steps.size(), ());
   for (size_t i = lastSubroute.GetBeginSegmentIdx(); i < lastSubroute.GetEndSegmentIdx(); ++i)
@@ -692,11 +679,6 @@ RouterResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints,
       return;
 
     m2::PointD const & point = starter.GetPoint(vertex, true /* front */);
-    auto const lastValue = progress.GetLastValue();
-    auto const newValue = progress.GetProgressForDirectedAlgo(point);
-    if (newValue - lastValue > kProgressInterval)
-      delegate.OnProgress(newValue);
-
     delegate.OnPointCheck(point);
   };
 
@@ -831,11 +813,11 @@ bool IndexRouter::FindBestSegment(m2::PointD const & point, m2::PointD const & d
   return true;
 }
 
-
 RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
                                                  RouterDelegate const & delegate,
                                                  WorldGraphMode prevMode,
                                                  IndexGraphStarter & starter,
+                                                 AStarProgress & progress,
                                                  vector<Segment> & output)
 {
   if (prevMode != WorldGraphMode::LeapsOnly)
@@ -844,6 +826,12 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
     return RouterResultCode::NoError;
   }
 
+  SCOPE_GUARD(progressGuard, [&progress]() {
+    progress.EraseLastSubProgress();
+  });
+
+  progress.AppendSubProgress(AStarSubProgress(1.0 - kLeapsStageContribution));
+
   CHECK_GREATER_OR_EQUAL(input.size(), 4,
                          ("Route in LeapsOnly mode must have at least start and finish leaps."));
 
@@ -920,10 +908,39 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
     using Edge = IndexGraphStarterJoints<IndexGraphStarter>::Edge;
     using Weight = IndexGraphStarterJoints<IndexGraphStarter>::Weight;
 
+    double contribCoef = static_cast<double>(end - start + 1) /
+                         static_cast<double>(input.size());
+    auto startPoint = starter.GetPoint(input[start], true /* front */);
+    auto endPoint = starter.GetPoint(input[end], true /* front */);
+    progress.AppendSubProgress({startPoint, endPoint, contribCoef});
+    SCOPE_GUARD(progressGuard, [&progress]() {
+      progress.EraseLastSubProgress();
+    });
+
+    uint32_t visitCount = 0;
+    auto lastValue = progress.GetLastValue();
+    auto const onVisitJunctionJoints = [&](JointSegment const & from, JointSegment const & to)
+    {
+      ++visitCount;
+      if (visitCount % kVisitPeriod != 0)
+        return;
+
+      m2::PointD const & pointFrom = jointStarter.GetPoint(from, true /* front */);
+      m2::PointD const & pointTo = jointStarter.GetPoint(to, true /* front */);
+      auto const newValue = progress.UpdateProgress(pointFrom, pointTo);
+      if (newValue - lastValue > kProgressInterval)
+      {
+        lastValue = newValue;
+        delegate.OnProgress(newValue);
+      }
+
+      delegate.OnPointCheck(pointFrom);
+    };
+
     AStarAlgorithm<Vertex, Edge, Weight>::Params params(
       jointStarter, jointStarter.GetStartJoint(), jointStarter.GetFinishJoint(),
       nullptr /* prevRoute */, delegate,
-      {} /* onVisitedVertexCallback */, checkLength);
+      onVisitJunctionJoints, checkLength);
 
     return FindPath<Vertex, Edge, Weight>(params, mwmIds, routingResult, mode);
   };
@@ -950,6 +967,7 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
       return true;
     }
 
+
     LOG(LINFO, ("Can not find path",
       "from:",
       MercatorBounds::ToLatLon(starter.GetPoint(input[start], input[start].IsForward())),
diff --git a/routing/index_router.hpp b/routing/index_router.hpp
index 8e309f5738..4ff70ffcf6 100644
--- a/routing/index_router.hpp
+++ b/routing/index_router.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "routing/base/astar_algorithm.hpp"
+#include "routing/base/astar_progress.hpp"
 #include "routing/base/routing_result.hpp"
 
 #include "routing/cross_mwm_graph.hpp"
@@ -25,6 +26,8 @@
 
 #include "geometry/tree4d.hpp"
 
+#include "base/astar_progress.hpp"
+
 #include <functional>
 #include <memory>
 #include <set>
@@ -86,8 +89,8 @@ private:
                                     m2::PointD const & startDirection,
                                     RouterDelegate const & delegate, Route & route);
   RouterResultCode CalculateSubroute(Checkpoints const & checkpoints, size_t subrouteIdx,
-                                     RouterDelegate const & delegate, IndexGraphStarter & graph,
-                                     std::vector<Segment> & subroute);
+                                     RouterDelegate const & delegate, AStarProgress & progress,
+                                     IndexGraphStarter & graph, std::vector<Segment> & subroute);
 
   RouterResultCode AdjustRoute(Checkpoints const & checkpoints,
                                m2::PointD const & startDirection,
@@ -112,7 +115,7 @@ private:
   // ProcessLeaps replaces each leap with calculated route through mwm.
   RouterResultCode ProcessLeapsJoints(vector<Segment> const & input, RouterDelegate const & delegate,
                                       WorldGraphMode prevMode, IndexGraphStarter & starter,
-                                      vector<Segment> & output);
+                                      AStarProgress & progress, vector<Segment> & output);
   RouterResultCode RedressRoute(std::vector<Segment> const & segments,
                                 RouterDelegate const & delegate, IndexGraphStarter & starter,
                                 Route & route) const;
diff --git a/routing/routing_tests/astar_progress_test.cpp b/routing/routing_tests/astar_progress_test.cpp
index 84daaf70fb..05f37afb6a 100644
--- a/routing/routing_tests/astar_progress_test.cpp
+++ b/routing/routing_tests/astar_progress_test.cpp
@@ -12,12 +12,12 @@ UNIT_TEST(DirectedAStarProgressCheck)
   m2::PointD finish = m2::PointD(0, 3);
   m2::PointD middle = m2::PointD(0, 2);
 
-  AStarProgress progress(0, 100);
-  progress.Initialize(start, finish);
-  TEST_LESS(progress.GetProgressForDirectedAlgo(start), 0.1f, ());
-  TEST_LESS(progress.GetProgressForDirectedAlgo(middle), 50.5f, ());
-  TEST_GREATER(progress.GetProgressForDirectedAlgo(middle), 49.5f, ());
-  TEST_GREATER(progress.GetProgressForDirectedAlgo(finish), 99.9f, ());
+  AStarProgress progress;
+  progress.AppendSubProgress({start, finish, 1.0 /* contributionCoef */});
+  TEST_LESS(progress.UpdateProgress(start, finish), 0.1f, ());
+  TEST_LESS(progress.UpdateProgress(middle, finish), 50.5f, ());
+  TEST_GREATER(progress.UpdateProgress(middle, finish), 49.5f, ());
+  TEST_GREATER(progress.UpdateProgress(finish, finish), 99.9f, ());
 }
 
 UNIT_TEST(DirectedAStarDegradationCheck)
@@ -26,14 +26,14 @@ UNIT_TEST(DirectedAStarDegradationCheck)
   m2::PointD finish = m2::PointD(0, 3);
   m2::PointD middle = m2::PointD(0, 2);
 
-  AStarProgress progress(0, 100);
-  progress.Initialize(start, finish);
-  auto value1 = progress.GetProgressForDirectedAlgo(middle);
-  auto value2 = progress.GetProgressForDirectedAlgo(start);
+  AStarProgress progress;
+  progress.AppendSubProgress({start, finish, 1.0 /* contributionCoef */});
+  auto value1 = progress.UpdateProgress(middle, finish);
+  auto value2 = progress.UpdateProgress(start, finish);
   TEST_LESS_OR_EQUAL(value1, value2, ());
 
-  progress.Initialize(start, finish);
-  auto value3 = progress.GetProgressForDirectedAlgo(start);
+  progress.AppendSubProgress({start, finish, 1.0 /* contributionCoef */});
+  auto value3 = progress.UpdateProgress(start, finish);
   TEST_GREATER_OR_EQUAL(value1, value3, ());
 }
 
@@ -44,25 +44,11 @@ UNIT_TEST(RangeCheckTest)
   m2::PointD preStart = m2::PointD(0, 0);
   m2::PointD postFinish = m2::PointD(0, 6);
 
-  AStarProgress progress(0, 100);
-  progress.Initialize(start, finish);
-  TEST_EQUAL(progress.GetProgressForDirectedAlgo(preStart), 0.0, ());
-  TEST_EQUAL(progress.GetProgressForDirectedAlgo(postFinish), 0.0, ());
-  TEST_EQUAL(progress.GetProgressForDirectedAlgo(finish), 100.0, ());
-}
-
-UNIT_TEST(DirectedAStarProgressCheckAtShiftedInterval)
-{
-  m2::PointD start = m2::PointD(0, 1);
-  m2::PointD finish = m2::PointD(0, 3);
-  m2::PointD middle = m2::PointD(0, 2);
-
-  AStarProgress progress(50, 250);
-  progress.Initialize(start, finish);
-  TEST_LESS(progress.GetProgressForDirectedAlgo(start), 50.1f, ());
-  TEST_LESS(progress.GetProgressForDirectedAlgo(middle), 150.5f, ());
-  TEST_GREATER(progress.GetProgressForDirectedAlgo(middle), 145.5f, ());
-  TEST_GREATER(progress.GetProgressForDirectedAlgo(finish), 245.9f, ());
+  AStarProgress progress;
+  progress.AppendSubProgress({start, finish, 1.0 /* contributionCoef */});
+  TEST_EQUAL(progress.UpdateProgress(preStart, finish), 0.0, ());
+  TEST_EQUAL(progress.UpdateProgress(postFinish, finish), 0.0, ());
+  TEST_EQUAL(progress.UpdateProgress(finish, finish), 100.0, ());
 }
 
 UNIT_TEST(BidirectedAStarProgressCheck)
@@ -72,10 +58,10 @@ UNIT_TEST(BidirectedAStarProgressCheck)
   m2::PointD fWave = m2::PointD(0, 1);
   m2::PointD bWave = m2::PointD(0, 3);
 
-  AStarProgress progress(0.0f, 100.0f);
-  progress.Initialize(start, finish);
-  progress.GetProgressForBidirectedAlgo(fWave, finish);
-  float result = progress.GetProgressForBidirectedAlgo(bWave, start);
+  AStarProgress progress;
+  progress.AppendSubProgress({start, finish, 1.0 /* contributionCoef */});
+  progress.UpdateProgress(fWave, finish);
+  float result = progress.UpdateProgress(bWave, start);
   TEST_GREATER(result, 49.5, ());
   TEST_LESS(result, 50.5, ());
 }