[coding] Added a serialization method for traffic coords.

7 files changed, 320 insertions, 2 deletions

diff --git a/coding/CMakeLists.txt b/coding/CMakeLists.txt
index 240d3d9bf4..ab8966f134 100644
--- a/coding/CMakeLists.txt
+++ b/coding/CMakeLists.txt
@@ -62,6 +62,8 @@ set(
   streams_common.hpp
   streams_sink.hpp
   succinct_mapper.hpp
+  traffic.cpp
+  traffic.hpp  
   uri.cpp
   uri.hpp
   url_encode.hpp
diff --git a/coding/coding.pro b/coding/coding.pro
index c2af2eb04f..2ab0b4cbaa 100644
--- a/coding/coding.pro
+++ b/coding/coding.pro
@@ -28,6 +28,7 @@ SOURCES += \
     reader_writer_ops.cpp \
     simple_dense_coding.cpp \
     sha2.cpp \
+    traffic.cpp \
     uri.cpp \
 #    varint_vector.cpp \
     zip_creator.cpp \
@@ -83,6 +84,7 @@ HEADERS += \
     streams_common.hpp \
     streams_sink.hpp \
     succinct_mapper.hpp \
+    traffic.hpp \
     uri.hpp \
     url_encode.hpp \
     value_opt_string.hpp \
diff --git a/coding/coding_tests/CMakeLists.txt b/coding/coding_tests/CMakeLists.txt
index 3e8da7c2da..b01c25f140 100644
--- a/coding/coding_tests/CMakeLists.txt
+++ b/coding/coding_tests/CMakeLists.txt
@@ -30,6 +30,7 @@ set(
   sha2_test.cpp
   simple_dense_coding_test.cpp
   succinct_mapper_test.cpp
+  traffic_test.cpp
   uri_test.cpp
   url_encode_test.cpp
   value_opt_string_test.cpp
@@ -44,4 +45,4 @@ set(
 
 omim_add_test(coding_tests ${SRC})
 
-omim_link_libraries(coding_tests coding base minizip tomcrypt succinct ${LIBZ})
+omim_link_libraries(coding_tests coding base geometry minizip tomcrypt succinct ${LIBZ})
diff --git a/coding/coding_tests/coding_tests.pro b/coding/coding_tests/coding_tests.pro
index 46049648d0..dce6ba1e49 100644
--- a/coding/coding_tests/coding_tests.pro
+++ b/coding/coding_tests/coding_tests.pro
@@ -6,7 +6,7 @@ TEMPLATE = app
 
 ROOT_DIR = ../..
 
-DEPENDENCIES = coding base minizip tomcrypt succinct
+DEPENDENCIES = coding base geometry minizip tomcrypt succinct
 
 include($$ROOT_DIR/common.pri)
 
@@ -39,6 +39,7 @@ SOURCES += ../../testing/testingmain.cpp \
     simple_dense_coding_test.cpp \
     sha2_test.cpp \
     succinct_mapper_test.cpp \
+    traffic_test.cpp \
     uri_test.cpp \
     url_encode_test.cpp \
     value_opt_string_test.cpp \
diff --git a/coding/coding_tests/traffic_test.cpp b/coding/coding_tests/traffic_test.cpp
new file mode 100644
index 0000000000..ace5b7a610
--- /dev/null
+++ b/coding/coding_tests/traffic_test.cpp
@@ -0,0 +1,152 @@
+#include "testing/testing.hpp"
+
+#include "coding/traffic.hpp"
+
+#include "geometry/mercator.hpp"
+#include "geometry/point2d.hpp"
+
+#include "base/logging.hpp"
+#include "base/math.hpp"
+
+namespace coding
+{
+double CalculateLength(vector<TrafficGPSEncoder::DataPoint> const & path)
+{
+  double res = 0;
+  for (size_t i = 1; i < path.size(); ++i)
+  {
+    auto p1 = MercatorBounds::FromLatLon(path[i - 1].m_latLon.lat, path[i - 1].m_latLon.lon);
+    auto p2 = MercatorBounds::FromLatLon(path[i].m_latLon.lat, path[i].m_latLon.lon);
+    res += MercatorBounds::DistanceOnEarth(p1, p2);
+  }
+  return res;
+}
+
+void Test(vector<TrafficGPSEncoder::DataPoint> & points)
+{
+  double const kEps = 1e-5;
+
+  for (uint32_t version = 0; version <= TrafficGPSEncoder::kLatestVersion; ++version)
+  {
+    vector<uint8_t> buf;
+    MemWriter<decltype(buf)> memWriter(buf);
+    TrafficGPSEncoder::SerializeDataPoints(version, memWriter, points);
+
+    vector<TrafficGPSEncoder::DataPoint> result;
+    MemReader memReader(buf.data(), buf.size());
+    ReaderSource<MemReader> src(memReader);
+    uint32_t const header = ReadPrimitiveFromSource<uint32_t>(src);
+    uint32_t const size = header >> 3;
+    TEST_EQUAL(version, header & 7, ());
+    TEST_EQUAL(src.Size(), size, ());
+    src = ReaderSource<MemReader>(size);
+    TrafficGPSEncoder::DeserializeDataPoints(version, src, result);
+
+    TEST_EQUAL(points.size(), result.size(), ());
+    for (size_t i = 0; i < points.size(); ++i)
+    {
+      TEST_EQUAL(points[i].m_timestamp, result[i].m_timestamp,
+                 (points[i].m_timestamp, result[i].m_timestamp));
+      TEST(my::AlmostEqualAbsOrRel(points[i].m_latLon.lat, result[i].m_latLon.lat, kEps),
+           (points[i].m_latLon.lat, result[i].m_latLon.lat));
+      TEST(my::AlmostEqualAbsOrRel(points[i].m_latLon.lon, result[i].m_latLon.lon, kEps),
+           (points[i].m_latLon.lon, result[i].m_latLon.lon));
+    }
+
+    if (version == TrafficGPSEncoder::kLatestVersion)
+    {
+      LOG(LINFO, ("path length =", CalculateLength(points), "num points =", points.size(),
+                  "compressed size =", buf.size()));
+    }
+  }
+}
+
+UNIT_TEST(Traffic_Serialization_Smoke)
+{
+  vector<TrafficGPSEncoder::DataPoint> data = {
+      {0, ms::LatLon(0.0, 1.0)}, {0, ms::LatLon(0.0, 2.0)},
+  };
+  Test(data);
+}
+
+UNIT_TEST(Traffic_Serialization_EmptyPath)
+{
+  vector<TrafficGPSEncoder::DataPoint> data;
+  Test(data);
+}
+
+UNIT_TEST(Traffic_Serialization_StraightLine100m)
+{
+  vector<TrafficGPSEncoder::DataPoint> path = {
+      {0, ms::LatLon(0.0, 0.0)}, {0, ms::LatLon(0.0, 1e-3)},
+  };
+  Test(path);
+}
+
+UNIT_TEST(Traffic_Serialization_StraightLine50Km)
+{
+  vector<TrafficGPSEncoder::DataPoint> path = {
+      {0, ms::LatLon(0.0, 0.0)}, {0, ms::LatLon(0.0, 0.5)},
+  };
+  Test(path);
+}
+
+UNIT_TEST(Traffic_Serialization_Zigzag500m)
+{
+  vector<TrafficGPSEncoder::DataPoint> path;
+  for (size_t i = 0; i < 5; ++i)
+  {
+    double const x = i * 1e-3;
+    double const y = i % 2 == 0 ? 0 : 1e-3;
+    path.emplace_back(TrafficGPSEncoder::DataPoint(0, ms::LatLon(y, x)));
+  }
+  Test(path);
+}
+
+UNIT_TEST(Traffic_Serialization_Zigzag10Km)
+{
+  vector<TrafficGPSEncoder::DataPoint> path;
+  for (size_t i = 0; i < 10; ++i)
+  {
+    double const x = i * 1e-2;
+    double const y = i % 2 == 0 ? 0 : 1e-2;
+    path.emplace_back(TrafficGPSEncoder::DataPoint(0, ms::LatLon(y, x)));
+  }
+  Test(path);
+}
+
+UNIT_TEST(Traffic_Serialization_Zigzag100Km)
+{
+  vector<TrafficGPSEncoder::DataPoint> path;
+  for (size_t i = 0; i < 1000; ++i)
+  {
+    double const x = i * 1e-1;
+    double const y = i % 2 == 0 ? 0 : 1e-1;
+    path.emplace_back(TrafficGPSEncoder::DataPoint(0, ms::LatLon(y, x)));
+  }
+  Test(path);
+}
+
+UNIT_TEST(Traffic_Serialization_Circle20KmRadius)
+{
+  vector<TrafficGPSEncoder::DataPoint> path;
+  size_t const n = 100;
+  for (size_t i = 0; i < n; ++i)
+  {
+    double const alpha = 2 * math::pi * i / n;
+    double const radius = 0.25;
+    double const x = radius * cos(alpha);
+    double const y = radius * sin(alpha);
+    path.emplace_back(TrafficGPSEncoder::DataPoint(0, ms::LatLon(y, x)));
+  }
+  Test(path);
+}
+
+UNIT_TEST(Traffic_Serialization_ExtremeLatLon)
+{
+  vector<TrafficGPSEncoder::DataPoint> path = {
+      {0, ms::LatLon(-90, -180)}, {0, ms::LatLon(90, 180)},
+  };
+  Test(path);
+}
+}  // namespace coding
diff --git a/coding/traffic.cpp b/coding/traffic.cpp
new file mode 100644
index 0000000000..2883a5f1f3
--- /dev/null
+++ b/coding/traffic.cpp
@@ -0,0 +1,27 @@
+#include "coding/traffic.hpp"
+
+#include "base/math.hpp"
+
+namespace coding
+{
+// static
+uint32_t const TrafficGPSEncoder::kLatestVersion = 0;
+uint32_t const TrafficGPSEncoder::kCoordBits = 30;
+double const TrafficGPSEncoder::kMinDeltaLat = ms::LatLon::kMinLat - ms::LatLon::kMaxLat;
+double const TrafficGPSEncoder::kMaxDeltaLat = ms::LatLon::kMaxLat - ms::LatLon::kMinLat;
+double const TrafficGPSEncoder::kMinDeltaLon = ms::LatLon::kMinLon - ms::LatLon::kMaxLon;
+double const TrafficGPSEncoder::kMaxDeltaLon = ms::LatLon::kMaxLon - ms::LatLon::kMinLon;
+
+// static
+uint32_t TrafficGPSEncoder::DoubleToUint32(double x, double min, double max)
+{
+  x = my::clamp(x, min, max);
+  return static_cast<uint32_t>(0.5 + (x - min) / (max - min) * ((1 << kCoordBits) - 1));
+}
+
+// static
+double TrafficGPSEncoder::Uint32ToDouble(uint32_t x, double min, double max)
+{
+  return min + static_cast<double>(x) * (max - min) / ((1 << kCoordBits) - 1);
+}
+}  // namespace coding
diff --git a/coding/traffic.hpp b/coding/traffic.hpp
new file mode 100644
index 0000000000..06c2c4dddb
--- /dev/null
+++ b/coding/traffic.hpp
@@ -0,0 +1,133 @@
+#pragma once
+
+#include "coding/reader.hpp"
+#include "coding/varint.hpp"
+#include "coding/writer.hpp"
+
+#include "geometry/latlon.hpp"
+
+#include "std/vector.hpp"
+
+namespace coding
+{
+class TrafficGPSEncoder
+{
+public:
+  static uint32_t const kLatestVersion;
+  static uint32_t const kCoordBits;
+  static double const kMinDeltaLat;
+  static double const kMaxDeltaLat;
+  static double const kMinDeltaLon;
+  static double const kMaxDeltaLon;
+
+  struct DataPoint
+  {
+    DataPoint() = default;
+
+    DataPoint(uint64_t timestamp, ms::LatLon latLon) : m_timestamp(timestamp), m_latLon(latLon) {}
+    uint64_t m_timestamp = 0;
+    ms::LatLon m_latLon = ms::LatLon::Zero();
+  };
+
+  // Serializes |points| to |writer| by first writing
+  // a header of 4 bytes and then writing the payload
+  // encoded according to |version|.
+  // Version 0:
+  //   * header contains the size of the payload in bytes
+  //     in its top 29 (little-endian) bits and version number
+  //     in its 3 low bits.
+  //   * payload stores delta-encoded points. Coordinates
+  //     are truncated and stored as integers. All integers
+  //     are written as varints.
+  template <typename Writer>
+  static void SerializeDataPoints(uint32_t version, Writer & writer,
+                                  vector<DataPoint> const & points)
+  {
+    vector<uint8_t> buf;
+    MemWriter<decltype(buf)> bufWriter(buf);
+
+    auto const startPos = bufWriter.Pos();
+    uint32_t header = 0;
+    // We will fill the header later.
+    bufWriter.Write(&header, sizeof(header));
+    auto const payloadStartPos = bufWriter.Pos();
+
+    if (!points.empty())
+    {
+      uint64_t const firstTimestamp = points[0].m_timestamp;
+      uint32_t const firstLat =
+          DoubleToUint32(points[0].m_latLon.lat, ms::LatLon::kMinLat, ms::LatLon::kMaxLat);
+      uint32_t const firstLon =
+          DoubleToUint32(points[0].m_latLon.lon, ms::LatLon::kMinLon, ms::LatLon::kMaxLon);
+      WriteVarUint(bufWriter, firstTimestamp);
+      WriteVarUint(bufWriter, firstLat);
+      WriteVarUint(bufWriter, firstLon);
+    }
+
+    for (size_t i = 1; i < points.size(); ++i)
+    {
+      ASSERT_LESS_OR_EQUAL(points[i - 1].m_timestamp, points[i].m_timestamp, ());
+
+      uint64_t const deltaTimestamp = points[i].m_timestamp - points[i - 1].m_timestamp;
+      uint32_t deltaLat = DoubleToUint32(points[i].m_latLon.lat - points[i - 1].m_latLon.lat,
+                                         kMinDeltaLat, kMaxDeltaLat);
+      uint32_t deltaLon = DoubleToUint32(points[i].m_latLon.lon - points[i - 1].m_latLon.lon,
+                                         kMinDeltaLon, kMaxDeltaLon);
+
+      WriteVarUint(bufWriter, deltaTimestamp);
+      WriteVarUint(bufWriter, deltaLat);
+      WriteVarUint(bufWriter, deltaLon);
+    }
+
+    auto const endPos = bufWriter.Pos();
+    ASSERT_LESS(endPos - payloadStartPos, static_cast<uint32_t>(1) << 29, ("Payload too big."));
+    ASSERT_LESS(version, static_cast<uint32_t>(1) << 3, ("Version too big."));
+    uint32_t size = static_cast<uint32_t>(endPos - payloadStartPos);
+    header = (size << 3) | version;
+    bufWriter.Seek(startPos);
+    bufWriter.Write(&header, sizeof(header));
+    bufWriter.Seek(endPos);
+
+    writer.Write(buf.data(), buf.size());
+  }
+
+  // Deserializes the points from |source| and appends them to |result|.
+  // Version 0:
+  //   The source must contain the encoded payload and nothing more (i.e.,
+  //   the header must be read separately).
+  template <typename Source>
+  static void DeserializeDataPoints(uint32_t version, Source & src, vector<DataPoint> & result)
+  {
+    bool first = true;
+    uint64_t lastTimestamp = 0;
+    double lastLat = 0.0;
+    double lastLon = 0.0;
+
+    while (src.Size() > 0)
+    {
+      if (first)
+      {
+        lastTimestamp = ReadVarUint<uint64_t>(src);
+        lastLat =
+            Uint32ToDouble(ReadVarUint<uint32_t>(src), ms::LatLon::kMinLat, ms::LatLon::kMaxLat);
+        lastLon =
+            Uint32ToDouble(ReadVarUint<uint32_t>(src), ms::LatLon::kMinLon, ms::LatLon::kMaxLon);
+        result.emplace_back(lastTimestamp, ms::LatLon(lastLat, lastLon));
+        first = false;
+      }
+      else
+      {
+        lastTimestamp += ReadVarUint<uint64_t>(src);
+        lastLat += Uint32ToDouble(ReadVarUint<uint32_t>(src), kMinDeltaLat, kMaxDeltaLat);
+        lastLon += Uint32ToDouble(ReadVarUint<uint32_t>(src), kMinDeltaLon, kMaxDeltaLon);
+        result.emplace_back(lastTimestamp, ms::LatLon(lastLat, lastLon));
+      }
+    }
+  }
+
+private:
+  static uint32_t DoubleToUint32(double x, double min, double max);
+
+  static double Uint32ToDouble(uint32_t x, double min, double max);
+};
+}  // namespace coding