[osrm][routing] Improve compression of edge id’s data

4 files changed, 102 insertions, 45 deletions

diff --git a/3party/osrm/osrm-backend/RoutingAlgorithms/BasicRoutingInterface.h b/3party/osrm/osrm-backend/RoutingAlgorithms/BasicRoutingInterface.h
index f830d2717a..90d8ae58ec 100644
--- a/3party/osrm/osrm-backend/RoutingAlgorithms/BasicRoutingInterface.h
+++ b/3party/osrm/osrm-backend/RoutingAlgorithms/BasicRoutingInterface.h
@@ -98,7 +98,7 @@ template <class DataFacadeT> class BasicRoutingInterface
         // Stalling
         for (const auto edge : facade->GetAdjacentEdgeRange(node))
         {
-            const EdgeData &data = facade->GetEdgeData(edge);
+            const EdgeData &data = facade->GetEdgeData(edge, node);
             const bool reverse_flag = ((!forward_direction) ? data.forward : data.backward);
             if (reverse_flag)
             {
@@ -119,7 +119,7 @@ template <class DataFacadeT> class BasicRoutingInterface
 
         for (const auto edge : facade->GetAdjacentEdgeRange(node))
         {
-            const EdgeData &data = facade->GetEdgeData(edge);
+            const EdgeData &data = facade->GetEdgeData(edge, node);
             bool forward_directionFlag = (forward_direction ? data.forward : data.backward);
             if (forward_directionFlag)
             {
@@ -181,14 +181,16 @@ template <class DataFacadeT> class BasicRoutingInterface
             // facade->FindEdge does not suffice here in case of shortcuts.
             // The above explanation unclear? Think!
             EdgeID smaller_edge_id = SPECIAL_EDGEID;
+            NodeID smaller_node_id = SPECIAL_NODEID;
             int edge_weight = std::numeric_limits<EdgeWeight>::max();
             for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.first))
             {
-                const int weight = facade->GetEdgeData(edge_id).distance;
+                const int weight = facade->GetEdgeData(edge_id, edge.first).distance;
                 if ((facade->GetTarget(edge_id) == edge.second) && (weight < edge_weight) &&
-                    facade->GetEdgeData(edge_id).forward)
+                    facade->GetEdgeData(edge_id, edge.first).forward)
                 {
                     smaller_edge_id = edge_id;
+                    smaller_node_id = edge.first;
                     edge_weight = weight;
                 }
             }
@@ -204,18 +206,19 @@ template <class DataFacadeT> class BasicRoutingInterface
             {
                 for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.second))
                 {
-                    const int weight = facade->GetEdgeData(edge_id).distance;
+                    const int weight = facade->GetEdgeData(edge_id, edge.second).distance;
                     if ((facade->GetTarget(edge_id) == edge.first) && (weight < edge_weight) &&
-                        facade->GetEdgeData(edge_id).backward)
+                        facade->GetEdgeData(edge_id, edge.second).backward)
                     {
                         smaller_edge_id = edge_id;
+                        smaller_node_id = edge.second;
                         edge_weight = weight;
                     }
                 }
             }
             BOOST_ASSERT_MSG(edge_weight != INVALID_EDGE_WEIGHT, "edge id invalid");
 
-            const EdgeData &ed = facade->GetEdgeData(smaller_edge_id);
+            const EdgeData &ed = facade->GetEdgeData(smaller_edge_id, smaller_node_id);
             if (ed.shortcut)
             { // unpack
                 const NodeID middle_node_id = ed.id;
@@ -344,14 +347,16 @@ template <class DataFacadeT> class BasicRoutingInterface
             recursion_stack.pop();
 
             EdgeID smaller_edge_id = SPECIAL_EDGEID;
+            NodeID smaller_node_id = SPECIAL_NODEID;
             int edge_weight = std::numeric_limits<EdgeWeight>::max();
             for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.first))
             {
-                const int weight = facade->GetEdgeData(edge_id).distance;
+                const int weight = facade->GetEdgeData(edge_id, edge.first).distance;
                 if ((facade->GetTarget(edge_id) == edge.second) && (weight < edge_weight) &&
-                    facade->GetEdgeData(edge_id).forward)
+                    facade->GetEdgeData(edge_id, edge.first).forward)
                 {
                     smaller_edge_id = edge_id;
+                    smaller_node_id = edge.first;
                     edge_weight = weight;
                 }
             }
@@ -360,18 +365,19 @@ template <class DataFacadeT> class BasicRoutingInterface
             {
                 for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.second))
                 {
-                    const int weight = facade->GetEdgeData(edge_id).distance;
+                    const int weight = facade->GetEdgeData(edge_id, edge.second).distance;
                     if ((facade->GetTarget(edge_id) == edge.first) && (weight < edge_weight) &&
-                        facade->GetEdgeData(edge_id).backward)
+                        facade->GetEdgeData(edge_id, edge.second).backward)
                     {
                         smaller_edge_id = edge_id;
+                        smaller_node_id = edge.second;
                         edge_weight = weight;
                     }
                 }
             }
             BOOST_ASSERT_MSG(edge_weight != std::numeric_limits<EdgeWeight>::max(), "edge weight invalid");
 
-            const EdgeData &ed = facade->GetEdgeData(smaller_edge_id);
+            const EdgeData &ed = facade->GetEdgeData(smaller_edge_id, smaller_node_id);
             if (ed.shortcut)
             { // unpack
                 const NodeID middle_node_id = ed.id;
diff --git a/3party/osrm/osrm-backend/Server/DataStructures/BaseDataFacade.h b/3party/osrm/osrm-backend/Server/DataStructures/BaseDataFacade.h
index e0113c6fe6..0869cdc307 100644
--- a/3party/osrm/osrm-backend/Server/DataStructures/BaseDataFacade.h
+++ b/3party/osrm/osrm-backend/Server/DataStructures/BaseDataFacade.h
@@ -64,6 +64,8 @@ template <class EdgeDataT> class BaseDataFacade
 
     virtual EdgeDataT &GetEdgeData(const EdgeID e) = 0;
 
+    virtual EdgeDataT &GetEdgeData(const EdgeID e, NodeID node) { static EdgeDataT edge; return edge; }
+
     // virtual const EdgeDataT &GetEdgeData( const EdgeID e ) const = 0;
 
     virtual EdgeID BeginEdges(const NodeID n) const = 0;
diff --git a/3party/osrm/osrm-backend/mapsme/CMakeLists.txt b/3party/osrm/osrm-backend/mapsme/CMakeLists.txt
index ab4df3944c..09fe32e968 100644
--- a/3party/osrm/osrm-backend/mapsme/CMakeLists.txt
+++ b/3party/osrm/osrm-backend/mapsme/CMakeLists.txt
@@ -1,5 +1,12 @@
 file(GLOB_RECURSE SOURCES "*.cpp")
 file(GLOB_RECURSE HEADERS "*.hpp")
 
-add_executable(osrm-mapsme ${SOURCES} ${HEADERS})
-target_link_libraries(osrm-mapsme ${Boost_LIBRARIES} FINGERPRINT GITDESCRIPTION COORDLIB)
+
+set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -DNDEBUG")
+
+add_executable(osrm-mapsme ${SOURCES} ${HEADERS} "${CMAKE_SOURCE_DIR}/../../succinct/rs_bit_vector.cpp")
+target_link_libraries(osrm-mapsme ${Boost_LIBRARIES} FINGERPRINT GITDESCRIPTION COORDLIB
+                      debug "${CMAKE_SOURCE_DIR}/../../../../omim-build-debug/out/debug/libcoding.a"
+                            "${CMAKE_SOURCE_DIR}/../../../../omim-build-debug/out/debug/libbase.a"
+                      general "${CMAKE_SOURCE_DIR}/../../../../omim-build-release/out/release/libcoding.a"
+                              "${CMAKE_SOURCE_DIR}/../../../../omim-build-release/out/release/libbase.a")
diff --git a/3party/osrm/osrm-backend/mapsme/converter.cpp b/3party/osrm/osrm-backend/mapsme/converter.cpp
index dc67df2243..2f77c0ce18 100644
--- a/3party/osrm/osrm-backend/mapsme/converter.cpp
+++ b/3party/osrm/osrm-backend/mapsme/converter.cpp
@@ -6,7 +6,10 @@
 #include "../DataStructures/QueryEdge.h"
 
 #include "../../../../coding/matrix_traversal.hpp"
-//#include "../../../../routing/osrm_data_facade.hpp"
+#include "../../../../coding/internal/file_data.hpp"
+#include "../../../../base/bits.hpp"
+#include "../../../../base/logging.hpp"
+#include "../../../../routing/osrm_data_facade.hpp"
 
 #include "../../../succinct/elias_fano.hpp"
 #include "../../../succinct/elias_fano_compressed_list.hpp"
@@ -71,7 +74,11 @@ void Converter::run(const std::string & name)
       edges.push_back(TraverseMatrixInRowOrder<uint64_t>(nodeCount, node, target, data.backward));
       edgesData.push_back(d);
       shortcuts.push_back(data.shortcut);
-      edgeId.push_back(data.id);
+
+      int id1 = data.id;
+      int id2 = node;
+
+      edgeId.push_back(bits::ZigZagEncode(id2 - id1));
     }
   }
   std::cout << "Edges count: " << edgeId.size() << std::endl;
@@ -109,42 +116,42 @@ void Converter::run(const std::string & name)
   succinct::mapper::freeze(shortcutsVector, fileName.c_str());
 
   /// @todo Restore this checking. Now data facade depends on mwm libraries.
-  /*
+
   std::cout << "--- Test packed data" << std::endl;
-  routing::OsrmDataFacade<QueryEdge::EdgeData> facadeNew(name);
+  std::string fPath = name + ".mwm";
+
+  {
+    FilesContainerW routingCont(fPath);
+
+    auto appendFile = [&] (string const & tag)
+    {
+      string const fileName = name + "." + tag;
+      LOG(LINFO, ("Append file", fileName, "with tag", tag));
+      routingCont.Write(fileName, tag);
+    };
+
+    appendFile(ROUTING_SHORTCUTS_FILE_TAG);
+    appendFile(ROUTING_EDGEDATA_FILE_TAG);
+    appendFile(ROUTING_MATRIX_FILE_TAG);
+    appendFile(ROUTING_EDGEID_FILE_TAG);
+
+    routingCont.Finish();
+  }
+
+
+  FilesMappingContainer container;
+  container.Open(fPath);
+  typedef routing::OsrmDataFacade<QueryEdge::EdgeData> DataFacadeT;
+  DataFacadeT facadeNew;
+  facadeNew.Load(container);
 
   std::cout << "Check node count " << facade.GetNumberOfNodes() << " == " << facadeNew.GetNumberOfNodes() <<  "...";
   PrintStatus(facade.GetNumberOfNodes() == facadeNew.GetNumberOfNodes());
   std::cout << "Check edges count " << facade.GetNumberOfEdges() << " == " << facadeNew.GetNumberOfEdges() << "...";
   PrintStatus(facade.GetNumberOfEdges() == facadeNew.GetNumberOfEdges());
 
-  std::cout << "Check edges data ...";
-  bool error = false;
-  assert(facade.GetNumberOfEdges() == facadeNew.GetNumberOfEdges());
-  for (uint32_t e = 0; e < facade.GetNumberOfEdges(); ++e)
-  {
-    QueryEdge::EdgeData d1 = facade.GetEdgeData(e);
-    QueryEdge::EdgeData d2 = facadeNew.GetEdgeData(e);
-
-    if (d1.backward != d2.backward ||
-        d1.forward != d2.forward ||
-        d1.distance != d2.distance ||
-        d1.id != d2.id ||
-        d1.shortcut != d2.shortcut)
-    {
-      std::cout << "Edge num: " << e << std::endl;
-      std::cout << "d1 (backward: " << (uint32_t)d1.backward << ", forward: " << (uint32_t)d1.forward << ", distance: "
-                << (uint32_t)d1.distance << ", id: " << (uint32_t)d1.id << ", shortcut: " << (uint32_t)d1.shortcut << std::endl;
-      std::cout << "d2 (backward: " << (uint32_t)d2.backward << ", forward: " << (uint32_t)d2.forward << ", distance: "
-                << (uint32_t)d2.distance << ", id: " << (uint32_t)d2.id << ", shortcut: " << (uint32_t)d2.shortcut << std::endl;
-      error = true;
-      break;
-    }
-  }
-  PrintStatus(!error);
-
   std::cout << "Check graph structure...";
-  error = false;
+  bool error = false;
   for (uint32_t node = 0; node < facade.GetNumberOfNodes(); ++node)
   {
     EdgeRange r1 = facade.GetAdjacentEdgeRange(node);
@@ -161,7 +168,42 @@ void Converter::run(const std::string & name)
     }
   }
   PrintStatus(!error);
-  */
+
+  std::cout << "Check edges data ...";
+  error = false;
+  assert(facade.GetNumberOfEdges() == facadeNew.GetNumberOfEdges());
+  for (uint32_t i = 0; i < facade.GetNumberOfNodes(); ++i)
+  {
+    for (auto e : facade.GetAdjacentEdgeRange(i))
+    {
+      QueryEdge::EdgeData d1 = facade.GetEdgeData(e);
+      QueryEdge::EdgeData d2 = facadeNew.GetEdgeData(e, i);
+
+      if (d1.backward != d2.backward ||
+          d1.forward != d2.forward ||
+          d1.distance != d2.distance ||
+          d1.id != d2.id ||
+          d1.shortcut != d2.shortcut)
+      {
+        stringstream ss;
+        ss << "File name: " << name << std::endl;
+        ss << "Edge num: " << e << std::endl;
+        ss << "d1 (backward: " << (uint32_t)d1.backward << ", forward: " << (uint32_t)d1.forward << ", distance: "
+           << (uint32_t)d1.distance << ", id: " << (uint32_t)d1.id << ", shortcut: " << (uint32_t)d1.shortcut << std::endl;
+        ss << "d2 (backward: " << (uint32_t)d2.backward << ", forward: " << (uint32_t)d2.forward << ", distance: "
+           << (uint32_t)d2.distance << ", id: " << (uint32_t)d2.id << ", shortcut: " << (uint32_t)d2.shortcut << std::endl;
+        error = true;
+
+        my::DeleteFileX(fPath);
+
+        LOG(LCRITICAL, (ss.str()));
+        break;
+      }
+    }
+  }
+  PrintStatus(!error);
+
+  my::DeleteFileX(fPath);
 }
 
 }