diff options
author | Maxim Pimenov <m@maps.me> | 2016-11-18 17:42:44 +0300 |
---|---|---|
committer | Maxim Pimenov <m@maps.me> | 2016-12-08 15:31:29 +0300 |
commit | 554f0f855f3980f9be87ad7e058a8f7a8b06363f (patch) | |
tree | b3bd675773fc15547ccff1422326c606ab290552 /traffic | |
parent | 3de499bb3402f31003a1285d5a4c52c2d4ca4297 (diff) |
[traffic] Separate keys and values when serializing traffic.
Diffstat (limited to 'traffic')
-rw-r--r-- | traffic/speed_groups.cpp | 17 | ||||
-rw-r--r-- | traffic/speed_groups.hpp | 2 | ||||
-rw-r--r-- | traffic/traffic_info.cpp | 386 | ||||
-rw-r--r-- | traffic/traffic_info.hpp | 50 | ||||
-rw-r--r-- | traffic/traffic_tests/traffic_info_test.cpp | 50 | ||||
-rw-r--r-- | traffic/traffic_tests/traffic_tests.pro | 2 |
6 files changed, 426 insertions, 81 deletions
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) |