[traffic] Separate keys and values when serializing traffic.

13 files changed, 489 insertions, 84 deletions

diff --git a/defines.hpp b/defines.hpp
index e79978cb1b..b92d37b79c 100644
--- a/defines.hpp
+++ b/defines.hpp
@@ -34,6 +34,7 @@
 #define REGION_INFO_FILE_TAG "rgninfo"
 // Temporary addresses section that is used in search index generation.
 #define SEARCH_TOKENS_FILE_TAG "addrtags"
+#define TRAFFIC_KEYS_FILE_TAG "traffic"
 
 #define ROUTING_MATRIX_FILE_TAG "mercedes"
 #define ROUTING_EDGEDATA_FILE_TAG "daewoo"
diff --git a/generator/generator.pro b/generator/generator.pro
index eab138f66a..5b7f5a7acb 100644
--- a/generator/generator.pro
+++ b/generator/generator.pro
@@ -47,6 +47,7 @@ SOURCES += \
     statistics.cpp \
     tesselator.cpp \
     towns_dumper.cpp \
+    traffic_generator.cpp \
     unpack_mwm.cpp \
 
 HEADERS += \
@@ -91,6 +92,7 @@ HEADERS += \
     tag_admixer.hpp \
     tesselator.hpp \
     towns_dumper.hpp \
+    traffic_generator.hpp \
     unpack_mwm.hpp \
     ways_merger.hpp \
     world_map_generator.hpp \
diff --git a/generator/generator_tool/generator_tool.cpp b/generator/generator_tool/generator_tool.cpp
index aef0ff54f1..151b9d5655 100644
--- a/generator/generator_tool/generator_tool.cpp
+++ b/generator/generator_tool/generator_tool.cpp
@@ -13,6 +13,7 @@
 #include "generator/routing_index_generator.hpp"
 #include "generator/search_index_builder.hpp"
 #include "generator/statistics.hpp"
+#include "generator/traffic_generator.hpp"
 #include "generator/unpack_mwm.hpp"
 
 #include "indexer/classificator.hpp"
@@ -96,6 +97,8 @@ DEFINE_bool(unpack_mwm, false, "Unpack each section of mwm into a separate file
 DEFINE_bool(check_mwm, false, "Check map file to be correct.");
 DEFINE_string(delete_section, "", "Delete specified section (defines.hpp) from container.");
 DEFINE_bool(generate_addresses_file, false, "Generate .addr file (for '--output' option) with full addresses list.");
+DEFINE_bool(generate_traffic_keys, false,
+            "Generate keys for the traffic map (road segment -> speed group).");
 
 int main(int argc, char ** argv)
 {
@@ -158,7 +161,7 @@ int main(int argc, char ** argv)
       FLAGS_generate_index || FLAGS_generate_search_index || FLAGS_calc_statistics ||
       FLAGS_type_statistics || FLAGS_dump_types || FLAGS_dump_prefixes ||
       FLAGS_dump_feature_names != "" || FLAGS_check_mwm || FLAGS_srtm_path != "" ||
-      FLAGS_make_routing_index)
+      FLAGS_make_routing_index || FLAGS_generate_traffic_keys)
   {
     classificator::Load();
     classif().SortClassificator();
@@ -252,6 +255,12 @@ int main(int argc, char ** argv)
 
       routing::BuildRoutingIndex(datFile, country);
     }
+
+    if (FLAGS_generate_traffic_keys)
+    {
+      if (!traffic::GenerateTrafficKeysFromDataFile(datFile))
+        LOG(LCRITICAL, ("Error generating traffic keys."));
+    }
   }
 
   string const datFile = my::JoinFoldersToPath(path, FLAGS_output + DATA_FILE_EXTENSION);
diff --git a/generator/generator_tool/generator_tool.pro b/generator/generator_tool/generator_tool.pro
index cdd4138aa1..0e5e58b7d2 100644
--- a/generator/generator_tool/generator_tool.pro
+++ b/generator/generator_tool/generator_tool.pro
@@ -2,7 +2,7 @@
 
 ROOT_DIR = ../..
 
-DEPENDENCIES = generator routing search storage indexer editor platform geometry \
+DEPENDENCIES = generator routing traffic search storage indexer editor platform geometry \
                coding base freetype expat fribidi jansson protobuf osrm stats_client \
                minizip succinct pugixml tess2 gflags oauthcpp 
 include($$ROOT_DIR/common.pri)
diff --git a/generator/traffic_generator.cpp b/generator/traffic_generator.cpp
new file mode 100644
index 0000000000..8e52ca4c5c
--- /dev/null
+++ b/generator/traffic_generator.cpp
@@ -0,0 +1,40 @@
+#include "generator/traffic_generator.hpp"
+
+#include "routing/car_model.hpp"
+#include "routing/routing_helpers.hpp"
+
+#include "traffic/traffic_info.hpp"
+
+#include "platform/mwm_traits.hpp"
+
+#include "indexer/feature_algo.hpp"
+#include "indexer/feature_processor.hpp"
+#include "indexer/features_offsets_table.hpp"
+
+#include "coding/file_container.hpp"
+
+namespace traffic
+{
+bool GenerateTrafficKeysFromDataFile(string const & mwmPath)
+{
+  try
+  {
+    vector<TrafficInfo::RoadSegmentId> keys;
+    TrafficInfo::ExtractTrafficKeys(mwmPath, keys);
+
+    vector<uint8_t> buf;
+    TrafficInfo::SerializeTrafficKeys(keys, buf);
+
+    FilesContainerW writeContainer(mwmPath, FileWriter::OP_WRITE_EXISTING);
+    FileWriter writer = writeContainer.GetWriter(TRAFFIC_KEYS_FILE_TAG);
+    writer.Write(buf.data(), buf.size());
+  }
+  catch (RootException const & e)
+  {
+    LOG(LERROR, ("Failed to build traffic keys:", e.Msg()));
+    return false;
+  }
+
+  return true;
+}
+}  // namespace traffic
diff --git a/generator/traffic_generator.hpp b/generator/traffic_generator.hpp
new file mode 100644
index 0000000000..e0e0c0ef77
--- /dev/null
+++ b/generator/traffic_generator.hpp
@@ -0,0 +1,8 @@
+#pragma once
+
+#include "std/string.hpp"
+
+namespace traffic
+{
+bool GenerateTrafficKeysFromDataFile(string const & mwmPath);
+}  // namespace traffic
diff --git a/omim.pro b/omim.pro
index 3a80d1e8d9..e53e29a481 100644
--- a/omim.pro
+++ b/omim.pro
@@ -115,7 +115,7 @@ SUBDIRS = 3party base coding geometry editor indexer routing search
     feature_list.subdir = feature_list
     feature_list.depends = $$SUBDIRS
 
-    SUBDIRS *= search_quality_tool features_collector_tool feature_list
+    SUBDIRS *= feature_list features_collector_tool search_quality_tool
   }
 
   CONFIG(desktop):!CONFIG(no-tests) {
diff --git a/traffic/speed_groups.cpp b/traffic/speed_groups.cpp
index dd1d22f964..d32abde9c2 100644
--- a/traffic/speed_groups.cpp
+++ b/traffic/speed_groups.cpp
@@ -1,9 +1,26 @@
 #include "traffic/speed_groups.hpp"
 
+#include "base/math.hpp"
+
+#include "std/algorithm.hpp"
+
 namespace traffic
 {
 uint32_t const kSpeedGroupThresholdPercentage[] = {8, 16, 33, 58, 83, 100, 100, 100};
 
+SpeedGroup GetSpeedGroupByPercentage(double p)
+{
+  p = my::clamp(p, 0.0, 100.0);
+  uint32_t const pu = static_cast<uint32_t>(p);
+  SpeedGroup res = SpeedGroup::Unknown;
+  for (int i = static_cast<int>(SpeedGroup::Count) - 1; i >= 0; --i)
+  {
+    if (pu <= kSpeedGroupThresholdPercentage[i])
+      res = static_cast<SpeedGroup>(i);
+  }
+  return res;
+}
+
 string DebugPrint(SpeedGroup const & group)
 {
   switch (group)
diff --git a/traffic/speed_groups.hpp b/traffic/speed_groups.hpp
index be18ea0634..91f81786d4 100644
--- a/traffic/speed_groups.hpp
+++ b/traffic/speed_groups.hpp
@@ -37,5 +37,7 @@ static_assert(static_cast<uint8_t>(SpeedGroup::Count) <= 8, "");
 // special groups where V is unknown or not defined.
 extern uint32_t const kSpeedGroupThresholdPercentage[static_cast<size_t>(SpeedGroup::Count)];
 
+SpeedGroup GetSpeedGroupByPercentage(double p);
+
 string DebugPrint(SpeedGroup const & group);
 }  // namespace traffic
diff --git a/traffic/traffic_info.cpp b/traffic/traffic_info.cpp
index 879fe7a9cf..8383c74858 100644
--- a/traffic/traffic_info.cpp
+++ b/traffic/traffic_info.cpp
@@ -2,18 +2,30 @@
 
 #include "platform/http_client.hpp"
 
+#include "routing/car_model.hpp"
+#include "routing/routing_helpers.hpp"
+
+#include "indexer/feature_algo.hpp"
+#include "indexer/feature_processor.hpp"
+
 #include "coding/bit_streams.hpp"
+#include "coding/elias_coder.hpp"
+#include "coding/file_container.hpp"
 #include "coding/reader.hpp"
 #include "coding/url_encode.hpp"
 #include "coding/varint.hpp"
 #include "coding/write_to_sink.hpp"
 #include "coding/writer.hpp"
+#include "coding/zlib.hpp"
 
 #include "base/assert.hpp"
+#include "base/bits.hpp"
 #include "base/logging.hpp"
 #include "base/string_utils.hpp"
 
 #include "std/algorithm.hpp"
+#include "std/limits.hpp"
+#include "std/sstream.hpp"
 #include "std/string.hpp"
 
 #include "defines.hpp"
@@ -72,10 +84,38 @@ TrafficInfo::RoadSegmentId::RoadSegmentId(uint32_t fid, uint16_t idx, uint8_t di
 }
 
 // TrafficInfo --------------------------------------------------------------------------------
+
+// static
+uint8_t const TrafficInfo::kLatestKeysVersion = 0;
+uint8_t const TrafficInfo::kLatestValuesVersion = 0;
+
 TrafficInfo::TrafficInfo(MwmSet::MwmId const & mwmId, int64_t currentDataVersion)
   : m_mwmId(mwmId)
   , m_currentDataVersion(currentDataVersion)
-{}
+{
+  string const mwmPath = mwmId.GetInfo()->GetLocalFile().GetPath(MapOptions::Map);
+  try
+  {
+    FilesContainerR rcont(mwmPath);
+    if (rcont.IsExist(TRAFFIC_KEYS_FILE_TAG))
+    {
+      auto reader = rcont.GetReader(TRAFFIC_KEYS_FILE_TAG);
+      vector<uint8_t> buf(reader.Size());
+      reader.Read(0, buf.data(), buf.size());
+      LOG(LINFO, ("Reading keys for", mwmId, "from section"));
+      DeserializeTrafficKeys(buf, m_keys);
+    }
+    else
+    {
+      LOG(LINFO, ("Reading traffic keys for", mwmId, "from the web"));
+      ReceiveTrafficKeys();
+    }
+  }
+  catch (RootException const & e)
+  {
+    LOG(LWARNING, ("Could not initialize traffic keys"));
+  }
+}
 
 // static
 TrafficInfo TrafficInfo::BuildForTesting(Coloring && coloring)
@@ -87,6 +127,278 @@ TrafficInfo TrafficInfo::BuildForTesting(Coloring && coloring)
 
 bool TrafficInfo::ReceiveTrafficData()
 {
+  vector<SpeedGroup> values;
+  if (!ReceiveTrafficValues(values))
+    return false;
+
+  if (m_keys.size() != values.size())
+  {
+    LOG(LWARNING,
+        ("The number of received traffic values does not correspond to the number of keys:",
+         m_keys.size(), "keys", values.size(), "values."));
+    m_availability = Availability::NoData;
+    m_coloring.clear();
+    return false;
+  }
+
+  for (size_t i = 0; i < m_keys.size(); ++i)
+    m_coloring.emplace(m_keys[i], values[i]);
+
+  return true;
+}
+
+SpeedGroup TrafficInfo::GetSpeedGroup(RoadSegmentId const & id) const
+{
+  auto const it = m_coloring.find(id);
+  if (it == m_coloring.cend())
+    return SpeedGroup::Unknown;
+  return it->second;
+}
+
+// static
+void TrafficInfo::ExtractTrafficKeys(string const & mwmPath, vector<RoadSegmentId> & result)
+{
+  result.clear();
+  feature::ForEachFromDat(mwmPath, [&](FeatureType const & ft, uint32_t const fid) {
+    if (!routing::CarModel::AllLimitsInstance().IsRoad(ft))
+      return;
+
+    ft.ParseGeometry(FeatureType::BEST_GEOMETRY);
+    auto const numPoints = static_cast<uint16_t>(ft.GetPointsCount());
+    uint8_t const numDirs = routing::CarModel::AllLimitsInstance().IsOneWay(ft) ? 1 : 2;
+    for (uint16_t i = 0; i + 1 < numPoints; ++i)
+    {
+      for (uint8_t dir = 0; dir < numDirs; ++dir)
+        result.emplace_back(fid, i, dir);
+    }
+  });
+
+  ASSERT(is_sorted(result.begin(), result.end()), ());
+}
+
+// static
+void CombineColorings(vector<TrafficInfo::RoadSegmentId> const & keys,
+                      TrafficInfo::Coloring const & knownColors, TrafficInfo::Coloring & result)
+{
+  result.clear();
+  size_t numKnown = 0;
+  size_t numUnknown = 0;
+  size_t numUnexpectedKeys = knownColors.size();
+  for (auto const & key : keys)
+  {
+    auto it = knownColors.find(key);
+    if (it == knownColors.end())
+    {
+      result[key] = SpeedGroup::Unknown;
+      ++numUnknown;
+    }
+    else
+    {
+      result[key] = it->second;
+      --numUnexpectedKeys;
+      ++numKnown;
+    }
+  }
+
+  LOG(LINFO, ("Road segments: known/unknown/total =", numKnown, numUnknown, numKnown + numUnknown));
+  ASSERT_EQUAL(numUnexpectedKeys, 0, ());
+}
+
+// static
+void TrafficInfo::SerializeTrafficKeys(vector<RoadSegmentId> const & keys, vector<uint8_t> & result)
+{
+  vector<uint32_t> fids;
+  vector<size_t> numSegs;
+  vector<bool> oneWay;
+  for (size_t i = 0; i < keys.size();)
+  {
+    size_t j = i;
+    while (j < keys.size() && keys[i].m_fid == keys[j].m_fid)
+      ++j;
+
+    bool ow = true;
+    for (size_t k = i; k < j; ++k)
+    {
+      if (keys[k].m_dir == RoadSegmentId::kReverseDirection)
+      {
+        ow = false;
+        break;
+      }
+    }
+
+    auto const numDirs = ow ? 1 : 2;
+    size_t numSegsForThisFid = j - i;
+    CHECK_GREATER(numDirs, 0, ());
+    CHECK_EQUAL(numSegsForThisFid % numDirs, 0, ());
+    numSegsForThisFid /= numDirs;
+
+    fids.push_back(keys[i].m_fid);
+    numSegs.push_back(numSegsForThisFid);
+    oneWay.push_back(ow);
+
+    i = j;
+  }
+
+  MemWriter<vector<uint8_t>> memWriter(result);
+  WriteToSink(memWriter, kLatestKeysVersion);
+  WriteVarUint(memWriter, fids.size());
+
+  {
+    BitWriter<decltype(memWriter)> bitWriter(memWriter);
+
+    uint32_t prevFid = 0;
+    for (auto const & fid : fids)
+    {
+      uint32_t const fidDiff = fid - prevFid;
+      bool ok = coding::GammaCoder::Encode(bitWriter, fidDiff + 1);
+      ASSERT(ok, ());
+      prevFid = fid;
+    }
+
+    for (auto const & s : numSegs)
+    {
+      bool ok = coding::GammaCoder::Encode(bitWriter, s + 1);
+      ASSERT(ok, ());
+    }
+
+    for (auto const & val : oneWay)
+      bitWriter.Write(val ? 1 : 0, 1);
+  }
+}
+
+// static
+void TrafficInfo::DeserializeTrafficKeys(vector<uint8_t> const & data,
+                                         vector<TrafficInfo::RoadSegmentId> & result)
+{
+  MemReader memReader(data.data(), data.size());
+  ReaderSource<decltype(memReader)> src(memReader);
+  auto const version = ReadPrimitiveFromSource<uint8_t>(src);
+  CHECK_EQUAL(version, kLatestKeysVersion, ("Unsupported version of traffic values."));
+  auto const n = static_cast<size_t>(ReadVarUint<uint64_t>(src));
+
+  vector<uint32_t> fids(n);
+  vector<size_t> numSegs(n);
+  vector<bool> oneWay(n);
+
+  {
+    BitReader<decltype(src)> bitReader(src);
+    uint32_t prevFid = 0;
+    for (size_t i = 0; i < n; ++i)
+    {
+      prevFid += coding::GammaCoder::Decode(bitReader) - 1;
+      fids[i] = prevFid;
+    }
+
+    for (size_t i = 0; i < n; ++i)
+      numSegs[i] = coding::GammaCoder::Decode(bitReader) - 1;
+
+    for (size_t i = 0; i < n; ++i)
+      oneWay[i] = bitReader.Read(1) > 0;
+  }
+
+  ASSERT_EQUAL(src.Size(), 0, ());
+
+  result.clear();
+  for (size_t i = 0; i < n; ++i)
+  {
+    auto const fid = fids[i];
+    uint8_t numDirs = oneWay[i] ? 1 : 2;
+    for (size_t j = 0; j < numSegs[i]; ++j)
+    {
+      for (uint8_t dir = 0; dir < numDirs; ++dir)
+      {
+        RoadSegmentId key(fid, j, dir);
+        result.push_back(key);
+      }
+    }
+  }
+}
+
+// static
+void TrafficInfo::SerializeTrafficValues(vector<SpeedGroup> const & values,
+                                         vector<uint8_t> & result)
+{
+  vector<uint8_t> buf;
+  MemWriter<vector<uint8_t>> memWriter(buf);
+  WriteToSink(memWriter, kLatestValuesVersion);
+  WriteVarUint(memWriter, values.size());
+  {
+    BitWriter<decltype(memWriter)> bitWriter(memWriter);
+    for (auto const & v : values)
+    {
+      // SpeedGroup's values fit into 3 bits.
+      bitWriter.Write(static_cast<uint8_t>(v), 3);
+    }
+  }
+
+  coding::ZLib::Deflate(buf.data(), buf.size(), coding::ZLib::Level::BestCompression,
+                        back_inserter(result));
+}
+
+// static
+void TrafficInfo::DeserializeTrafficValues(vector<uint8_t> const & data,
+                                           vector<SpeedGroup> & result)
+{
+  vector<uint8_t> decompressedData;
+  coding::ZLib::Inflate(data.data(), data.size(), back_inserter(decompressedData));
+
+  MemReader memReader(decompressedData.data(), decompressedData.size());
+  ReaderSource<decltype(memReader)> src(memReader);
+
+  auto const version = ReadPrimitiveFromSource<uint8_t>(src);
+  CHECK_EQUAL(version, kLatestValuesVersion, ("Unsupported version of traffic keys."));
+
+  auto const n = ReadVarUint<uint32_t>(src);
+  result.resize(n);
+  BitReader<decltype(src)> bitReader(src);
+  for (size_t i = 0; i < static_cast<size_t>(n); ++i)
+  {
+    // SpeedGroup's values fit into 3 bits.
+    result[i] = static_cast<SpeedGroup>(bitReader.Read(3));
+  }
+
+  ASSERT_EQUAL(src.Size(), 0, ());
+}
+
+// todo(@m) This is a temporary method. Do not refactor it.
+bool TrafficInfo::ReceiveTrafficKeys()
+{
+  auto const & info = m_mwmId.GetInfo();
+  if (!info)
+    return false;
+
+  string const url = MakeRemoteURL(info->GetCountryName(), info->GetVersion());
+
+  if (url.empty())
+    return false;
+
+  vector<uint8_t> contents;
+  int errorCode;
+  if (!ReadRemoteFile(url + ".keys", contents, errorCode))
+    return false;
+  if (errorCode != 200)
+  {
+    LOG(LWARNING, ("Network error when reading keys"));
+    return false;
+  }
+
+  vector<RoadSegmentId> keys;
+  try
+  {
+    DeserializeTrafficKeys(contents, keys);
+  }
+  catch (Reader::Exception const & e)
+  {
+    LOG(LINFO, ("Could not read traffic keys received from server. MWM:", info->GetCountryName(),
+                "Version:", info->GetVersion()));
+    return false;
+  }
+  m_keys.swap(keys);
+  return true;
+}
+
+bool TrafficInfo::ReceiveTrafficValues(vector<SpeedGroup> & values)
+{
   auto const & info = m_mwmId.GetInfo();
   if (!info)
     return false;
@@ -121,80 +433,28 @@ bool TrafficInfo::ReceiveTrafficData()
     return false;
   }
 
-  Coloring coloring;
   try
   {
-    DeserializeTrafficData(contents, coloring);
+    DeserializeTrafficValues(contents, values);
   }
   catch (Reader::Exception const & e)
   {
     m_availability = Availability::NoData;
-    LOG(LWARNING, ("Could not read traffic data received from server. MWM:", info->GetCountryName(),
-                   "Version:", info->GetVersion()));
+    LOG(LWARNING, ("Could not read traffic values received from server. MWM:",
+                   info->GetCountryName(), "Version:", info->GetVersion()));
     return false;
   }
-  m_coloring.swap(coloring);
   m_availability = Availability::IsAvailable;
   return true;
 }
 
-SpeedGroup TrafficInfo::GetSpeedGroup(RoadSegmentId const & id) const
-{
-  auto const it = m_coloring.find(id);
-  if (it == m_coloring.cend())
-    return SpeedGroup::Unknown;
-  return it->second;
-}
-
-// static
-void TrafficInfo::SerializeTrafficData(Coloring const & coloring, vector<uint8_t> & result)
-{
-  MemWriter<vector<uint8_t>> memWriter(result);
-  WriteToSink(memWriter, static_cast<uint32_t>(coloring.size()));
-  for (auto const & p : coloring)
-  {
-    WriteVarUint(memWriter, p.first.m_fid);
-    uint16_t const x = (p.first.m_idx << 1) | p.first.m_dir;
-    WriteVarUint(memWriter, x);
-  }
-  {
-    BitWriter<decltype(memWriter)> bitWriter(memWriter);
-    for (auto const & p : coloring)
-    {
-      // SpeedGroup's values fit into 3 bits.
-      bitWriter.Write(static_cast<uint8_t>(p.second), 3);
-    }
-  }
-}
-
-// static
-void TrafficInfo::DeserializeTrafficData(vector<uint8_t> const & data, Coloring & coloring)
+string DebugPrint(TrafficInfo::RoadSegmentId const & id)
 {
-  MemReader memReader(data.data(), data.size());
-  ReaderSource<decltype(memReader)> src(memReader);
-  auto const n = ReadPrimitiveFromSource<uint32_t>(src);
-
-  vector<RoadSegmentId> keys(n);
-  for (size_t i = 0; i < static_cast<size_t>(n); ++i)
-  {
-    keys[i].m_fid = ReadVarUint<uint32_t>(src);
-    auto const x = ReadVarUint<uint32_t>(src);
-    keys[i].m_idx = static_cast<uint16_t>(x >> 1);
-    keys[i].m_dir = static_cast<uint8_t>(x & 1);
-  }
-
-  vector<SpeedGroup> values(n);
-  BitReader<decltype(src)> bitReader(src);
-  for (size_t i = 0; i < static_cast<size_t>(n); ++i)
-  {
-    // SpeedGroup's values fit into 3 bits.
-    values[i] = static_cast<SpeedGroup>(bitReader.Read(3));
-  }
-
-  coloring.clear();
-  for (size_t i = 0; i < static_cast<size_t>(n); ++i)
-    coloring[keys[i]] = values[i];
-
-  ASSERT_EQUAL(src.Size(), 0, ());
+  string const dir =
+      id.m_dir == TrafficInfo::RoadSegmentId::kForwardDirection ? "Forward" : "Backward";
+  ostringstream oss;
+  oss << "RoadSegmentId ["
+      << " fid = " << id.m_fid << " idx = " << id.m_idx << " dir = " << dir << " ]";
+  return oss.str();
 }
 }  // namespace traffic
diff --git a/traffic/traffic_info.hpp b/traffic/traffic_info.hpp
index bafa0a4fa5..b4bab86a5b 100644
--- a/traffic/traffic_info.hpp
+++ b/traffic/traffic_info.hpp
@@ -17,6 +17,9 @@ namespace traffic
 class TrafficInfo
 {
 public:
+  static uint8_t const kLatestKeysVersion;
+  static uint8_t const kLatestValuesVersion;
+
   enum class Availability
   {
     IsAvailable,
@@ -29,8 +32,8 @@ public:
   struct RoadSegmentId
   {
     // m_dir can be kForwardDirection or kReverseDirection.
-    static int constexpr kForwardDirection = 0;
-    static int constexpr kReverseDirection = 1;
+    static uint8_t constexpr kForwardDirection = 0;
+    static uint8_t constexpr kReverseDirection = 1;
 
     RoadSegmentId();
 
@@ -75,20 +78,55 @@ public:
   // *NOTE* This method must not be called on the UI thread.
   bool ReceiveTrafficData();
 
-  // Returns the latest known speed group by a feature segment's id.
+  // Returns the latest known speed group by a feature segment's id
+  // or SpeedGroup::Unknown if there is no information about the segment.
   SpeedGroup GetSpeedGroup(RoadSegmentId const & id) const;
 
   MwmSet::MwmId const & GetMwmId() const { return m_mwmId; }
   Coloring const & GetColoring() const { return m_coloring; }
   Availability GetAvailability() const { return m_availability; }
 
-  static void SerializeTrafficData(Coloring const & coloring, vector<uint8_t> & result);
+  // Extracts RoadSegmentIds from mwm and stores them in a sorted order.
+  static void ExtractTrafficKeys(string const & mwmPath, vector<RoadSegmentId> & result);
+
+  // Adds the unknown values to the partially known coloring map |knownColors|
+  // so that the keys of the resulting map are exactly |keys|.
+  static void CombineColorings(vector<TrafficInfo::RoadSegmentId> const & keys,
+                               TrafficInfo::Coloring const & knownColors,
+                               TrafficInfo::Coloring & result);
+
+  // Serializes the keys of the coloring map to |result|.
+  // The keys are road segments ids which do not change during
+  // an mwm's lifetime so there's no point in downloading them every time.
+  // todo(@m) Document the format.
+  static void SerializeTrafficKeys(vector<RoadSegmentId> const & keys, vector<uint8_t> & result);
+
+  static void DeserializeTrafficKeys(vector<uint8_t> const & data, vector<RoadSegmentId> & result);
+
+  static void SerializeTrafficValues(vector<SpeedGroup> const & values, vector<uint8_t> & result);
 
-  static void DeserializeTrafficData(vector<uint8_t> const & data, Coloring & coloring);
+  static void DeserializeTrafficValues(vector<uint8_t> const & data, vector<SpeedGroup> & result);
 
 private:
+  // todo(@m) A temporary method. Remove it once the keys are added
+  // to the generator and the data is regenerated.
+  bool ReceiveTrafficKeys();
+
+  // Tries to read the values of the Coloring map from server.
+  // Returns true and updates m_coloring if the values are read successfully and
+  // their number is equal to the number of keys.
+  // Otherwise, returns false and does not change m_coloring.
+  bool ReceiveTrafficValues(vector<SpeedGroup> & values);
+
   // The mapping from feature segments to speed groups (see speed_groups.hpp).
   Coloring m_coloring;
+
+  // The keys of the coloring map. The values are downloaded periodically
+  // and combined with the keys to form m_coloring.
+  // *NOTE* The values must be received in the exact same order that the
+  // keys are saved in.
+  vector<RoadSegmentId> m_keys;
+
   MwmSet::MwmId m_mwmId;
   Availability m_availability = Availability::Unknown;
   int64_t m_currentDataVersion = 0;
@@ -103,4 +141,6 @@ public:
   virtual void OnTrafficInfoAdded(traffic::TrafficInfo && info) = 0;
   virtual void OnTrafficInfoRemoved(MwmSet::MwmId const & mwmId) = 0;
 };
+
+string DebugPrint(TrafficInfo::RoadSegmentId const & id);
 }  // namespace traffic
diff --git a/traffic/traffic_tests/traffic_info_test.cpp b/traffic/traffic_tests/traffic_info_test.cpp
index 5b19f599ec..0d96bf9db1 100644
--- a/traffic/traffic_tests/traffic_info_test.cpp
+++ b/traffic/traffic_tests/traffic_info_test.cpp
@@ -6,9 +6,14 @@
 #include "platform/local_country_file.hpp"
 #include "platform/platform_tests_support/writable_dir_changer.hpp"
 
+#include "indexer/classificator_loader.hpp"
 #include "indexer/mwm_set.hpp"
 
+#include "geometry/mercator.hpp"
+#include "geometry/rect2d.hpp"
+
 #include "std/algorithm.hpp"
+#include "std/random.hpp"
 
 namespace traffic
 {
@@ -73,24 +78,45 @@ UNIT_TEST(TrafficInfo_Serialization)
 {
   TrafficInfo::Coloring coloring = {
       {TrafficInfo::RoadSegmentId(0, 0, 0), SpeedGroup::G0},
-      {TrafficInfo::RoadSegmentId(1000, 1, 1), SpeedGroup::G1},
-      {TrafficInfo::RoadSegmentId(1000000, 0, 0), SpeedGroup::G5},
-      {TrafficInfo::RoadSegmentId(4294967295, 32767, 1), SpeedGroup::TempBlock},
+
+      {TrafficInfo::RoadSegmentId(1, 0, 0), SpeedGroup::G1},
+      {TrafficInfo::RoadSegmentId(1, 0, 1), SpeedGroup::G3},
+
+      {TrafficInfo::RoadSegmentId(5, 0, 0), SpeedGroup::G2},
+      {TrafficInfo::RoadSegmentId(5, 0, 1), SpeedGroup::G2},
+      {TrafficInfo::RoadSegmentId(5, 1, 0), SpeedGroup::G2},
+      {TrafficInfo::RoadSegmentId(5, 1, 1), SpeedGroup::G5},
+
+      {TrafficInfo::RoadSegmentId(4294967295, 0, 0), SpeedGroup::TempBlock},
   };
 
-  vector<uint8_t> buf;
-  TrafficInfo::SerializeTrafficData(coloring, buf);
+  vector<TrafficInfo::RoadSegmentId> keys;
+  vector<SpeedGroup> values;
+  for (auto const & kv : coloring)
+  {
+    keys.push_back(kv.first);
+    values.push_back(kv.second);
+  }
+
+  {
+    vector<uint8_t> buf;
+    TrafficInfo::SerializeTrafficKeys(keys, buf);
 
-  TrafficInfo::Coloring deserializedColoring;
-  TrafficInfo::DeserializeTrafficData(buf, deserializedColoring);
+    vector<TrafficInfo::RoadSegmentId> deserializedKeys;
+    TrafficInfo::DeserializeTrafficKeys(buf, deserializedKeys);
 
-  TEST_EQUAL(coloring.size(), deserializedColoring.size(), ());
+    ASSERT(is_sorted(keys.begin(), keys.end()), ());
+    ASSERT(is_sorted(deserializedKeys.begin(), deserializedKeys.end()), ());
+    TEST_EQUAL(keys, deserializedKeys, ());
+  }
 
-  for (auto const & p : coloring)
   {
-    auto const g1 = p.second;
-    auto const g2 = GetSpeedGroup(deserializedColoring, p.first);
-    TEST_EQUAL(g1, g2, ());
+    vector<uint8_t> buf;
+    TrafficInfo::SerializeTrafficValues(values, buf);
+
+    vector<SpeedGroup> deserializedValues;
+    TrafficInfo::DeserializeTrafficValues(buf, deserializedValues);
+    TEST_EQUAL(values, deserializedValues, ());
   }
 }
 }  // namespace traffic
diff --git a/traffic/traffic_tests/traffic_tests.pro b/traffic/traffic_tests/traffic_tests.pro
index e698084a64..0402ae4742 100644
--- a/traffic/traffic_tests/traffic_tests.pro
+++ b/traffic/traffic_tests/traffic_tests.pro
@@ -7,7 +7,7 @@ ROOT_DIR = ../..
 
 INCLUDEPATH *= $$ROOT_DIR/3party/jansson/src
 
-DEPENDENCIES = routing traffic indexer platform_tests_support platform coding geometry base stats_client
+DEPENDENCIES = routing traffic indexer platform_tests_support platform coding geometry base stats_client protobuf
 
 include($$ROOT_DIR/common.pri)