diff options
| -rw-r--r-- | defines.hpp | 2 | ||||
| -rw-r--r-- | generator/generator.pro | 4 | ||||
| -rw-r--r-- | generator/generator_tests/generator_tests.pro | 4 | ||||
| -rw-r--r-- | generator/generator_tests/restriction_collector_test.cpp (renamed from generator/generator_tests/restrictions_tests.cpp) | 58 | ||||
| -rw-r--r-- | generator/generator_tests/restriction_test.cpp | 136 | ||||
| -rw-r--r-- | generator/restriction_collector.cpp (renamed from generator/restrictions.cpp) | 59 | ||||
| -rw-r--r-- | generator/restriction_collector.hpp (renamed from generator/restrictions.hpp) | 56 | ||||
| -rw-r--r-- | generator/restriction_dumper.cpp | 13 | ||||
| -rw-r--r-- | generator/restriction_generator.cpp | 55 | ||||
| -rw-r--r-- | generator/restriction_generator.hpp | 18 | ||||
| -rw-r--r-- | indexer/indexer.pro | 4 | ||||
| -rw-r--r-- | indexer/restriction_loader.cpp | 47 | ||||
| -rw-r--r-- | indexer/restriction_loader.hpp | 28 | ||||
| -rw-r--r-- | indexer/routing.cpp | 43 | ||||
| -rw-r--r-- | indexer/routing.hpp | 142 | ||||
| -rwxr-xr-x | tools/unix/generate_mwm.sh | 2 |
16 files changed, 545 insertions, 126 deletions
diff --git a/defines.hpp b/defines.hpp index 9eb0cd88de..75a0189fc3 100644 --- a/defines.hpp +++ b/defines.hpp @@ -40,6 +40,8 @@ #define ROUTING_SHORTCUTS_FILE_TAG "skoda" #define ROUTING_CROSS_CONTEXT_TAG "chrysler" +#define ROUTING_FILE_TAG "routing" + #define ROUTING_FTSEG_FILE_TAG "ftseg" #define ROUTING_NODEIND_TO_FTSEGIND_FILE_TAG "node2ftseg" diff --git a/generator/generator.pro b/generator/generator.pro index 40fa8a0675..917696bed2 100644 --- a/generator/generator.pro +++ b/generator/generator.pro @@ -36,9 +36,9 @@ SOURCES += \ osm_id.cpp \ osm_source.cpp \ region_meta.cpp \ + restriction_collector.cpp \ restriction_dumper.cpp \ restriction_generator.cpp \ - restrictions.cpp \ routing_generator.cpp \ search_index_builder.cpp \ sponsored_scoring.cpp \ @@ -76,9 +76,9 @@ HEADERS += \ osm_xml_source.hpp \ polygonizer.hpp \ region_meta.hpp \ + restriction_collector.hpp \ restriction_dumper.hpp \ restriction_generator.hpp \ - restrictions.hpp \ routing_generator.hpp \ search_index_builder.hpp \ sponsored_dataset.hpp \ diff --git a/generator/generator_tests/generator_tests.pro b/generator/generator_tests/generator_tests.pro index 18ac6fcaca..0224bfef04 100644 --- a/generator/generator_tests/generator_tests.pro +++ b/generator/generator_tests/generator_tests.pro @@ -30,10 +30,12 @@ SOURCES += \ osm_id_test.cpp \ osm_o5m_source_test.cpp \ osm_type_test.cpp \ - restrictions_tests.cpp \ + restriction_collector_test.cpp \ + restriction_test.cpp \ source_data.cpp \ source_to_element_test.cpp \ srtm_parser_test.cpp \ tag_admixer_test.cpp \ tesselator_test.cpp \ triangles_tree_coding_test.cpp \ + diff --git a/generator/generator_tests/restrictions_tests.cpp b/generator/generator_tests/restriction_collector_test.cpp index c9708fe35a..b18f00d3aa 100644 --- a/generator/generator_tests/restrictions_tests.cpp +++ b/generator/generator_tests/restriction_collector_test.cpp @@ -1,7 +1,9 @@ #include "testing/testing.hpp" #include "generator/osm_id.hpp" -#include "generator/restrictions.hpp" +#include "generator/restriction_collector.hpp" + +#include "indexer/routing.hpp" #include "coding/file_name_utils.hpp" @@ -11,6 +13,7 @@ #include "platform/platform.hpp" #include "std/string.hpp" +#include "std/utility.hpp" #include "std/vector.hpp" using namespace platform; @@ -24,12 +27,12 @@ UNIT_TEST(RestrictionTest_ValidCase) { RestrictionCollector restrictionCollector("", ""); // Adding restrictions and feature ids to restrictionCollector in mixed order. - restrictionCollector.AddRestriction(RestrictionCollector::Type::No, {1, 2} /* osmIds */); + restrictionCollector.AddRestriction(Restriction::Type::No, {1, 2} /* osmIds */); restrictionCollector.AddFeatureId(30 /* featureId */, {3} /* osmIds */); - restrictionCollector.AddRestriction(RestrictionCollector::Type::No, {2, 3} /* osmIds */); + restrictionCollector.AddRestriction(Restriction::Type::No, {2, 3} /* osmIds */); restrictionCollector.AddFeatureId(10 /* featureId */, {1} /* osmIds */); restrictionCollector.AddFeatureId(50 /* featureId */, {5} /* osmIds */); - restrictionCollector.AddRestriction(RestrictionCollector::Type::Only, {5, 7} /* osmIds */); + restrictionCollector.AddRestriction(Restriction::Type::Only, {5, 7} /* osmIds */); restrictionCollector.AddFeatureId(70 /* featureId */, {7} /* osmIds */); restrictionCollector.AddFeatureId(20 /* featureId */, {2} /* osmIds */); @@ -40,10 +43,10 @@ UNIT_TEST(RestrictionTest_ValidCase) // Checking the result. TEST(restrictionCollector.IsValid(), ()); - vector<RestrictionCollector::Restriction> const expectedRestrictions = - {{RestrictionCollector::Type::No, {10, 20}}, - {RestrictionCollector::Type::No, {20, 30}}, - {RestrictionCollector::Type::Only, {50, 70}}}; + RestrictionVec const expectedRestrictions = + {{Restriction::Type::No, {10, 20}}, + {Restriction::Type::No, {20, 30}}, + {Restriction::Type::Only, {50, 70}}}; TEST_EQUAL(restrictionCollector.m_restrictions, expectedRestrictions, ()); } @@ -51,15 +54,15 @@ UNIT_TEST(RestrictionTest_InvalidCase) { RestrictionCollector restrictionCollector("", ""); restrictionCollector.AddFeatureId(0 /* featureId */, {0} /* osmIds */); - restrictionCollector.AddRestriction(RestrictionCollector::Type::No, {0, 1} /* osmIds */); + restrictionCollector.AddRestriction(Restriction::Type::No, {0, 1} /* osmIds */); restrictionCollector.AddFeatureId(20 /* featureId */, {2} /* osmIds */); restrictionCollector.ComposeRestrictions(); TEST(!restrictionCollector.IsValid(), ()); - vector<RestrictionCollector::Restriction> const expectedRestrictions = - {{RestrictionCollector::Type::No, {0, RestrictionCollector::kInvalidFeatureId}}}; + RestrictionVec const expectedRestrictions = + {{Restriction::Type::No, {0, Restriction::kInvalidFeatureId}}}; TEST_EQUAL(restrictionCollector.m_restrictions, expectedRestrictions, ()); restrictionCollector.RemoveInvalidRestrictions(); @@ -86,12 +89,12 @@ UNIT_TEST(RestrictionTest_ParseRestrictions) TEST(restrictionCollector.ParseRestrictions(my::JoinFoldersToPath(platform.WritableDir(), kRestrictionPath)), ()); - vector<RestrictionCollector::Restriction> expectedRestrictions = - {{RestrictionCollector::Type::No, 2}, - {RestrictionCollector::Type::Only, 2}, - {RestrictionCollector::Type::Only, 2}, - {RestrictionCollector::Type::No, 2}, - {RestrictionCollector::Type::No, 2}}; + RestrictionVec expectedRestrictions = + {{Restriction::Type::No, 2}, + {Restriction::Type::Only, 2}, + {Restriction::Type::Only, 2}, + {Restriction::Type::No, 2}, + {Restriction::Type::No, 2}}; TEST_EQUAL(restrictionCollector.m_restrictions, expectedRestrictions, ()); vector<pair<uint64_t, RestrictionCollector::Index>> const expectedRestrictionIndex = @@ -121,10 +124,10 @@ UNIT_TEST(RestrictionTest_ParseFeatureId2OsmIdsMapping) restrictionCollector.ParseFeatureId2OsmIdsMapping(my::JoinFoldersToPath(platform.WritableDir(), kFeatureIdToOsmIdsPath)); - vector<pair<uint64_t, RestrictionCollector::FeatureId>> const expectedOsmIds2FeatureId = - {{10, 1}, {20, 2}, {5423239545, 779703}, {30, 3}}; - vector<pair<uint64_t, RestrictionCollector::FeatureId>> const osmIds2FeatureId( - restrictionCollector.m_osmIds2FeatureId.cbegin(), restrictionCollector.m_osmIds2FeatureId.cend()); + vector<pair<uint64_t, Restriction::FeatureId>> const expectedOsmIds2FeatureId = + {{10, 1}, {20, 2}, {5423239545, 779703}, {30, 3}}; + vector<pair<uint64_t, Restriction::FeatureId>> const osmIds2FeatureId( + restrictionCollector.m_osmIds2FeatureId.cbegin(), restrictionCollector.m_osmIds2FeatureId.cend()); TEST_EQUAL(osmIds2FeatureId, expectedOsmIds2FeatureId, ()); } @@ -152,10 +155,13 @@ UNIT_TEST(RestrictionTest_RestrictionCollectorWholeClassTest) my::JoinFoldersToPath(platform.WritableDir(), kFeatureIdToOsmIdsPath)); TEST(restrictionCollector.IsValid(), ()); - vector<RestrictionCollector::Restriction> const expectedRestrictions = - {{RestrictionCollector::Type::No, {1, 1}}, - {RestrictionCollector::Type::Only, {1, 2}}, - {RestrictionCollector::Type::Only, {3, 4}}}; - TEST_EQUAL(restrictionCollector.GetRestriction(), expectedRestrictions, ()); + RestrictionVec const & restrictions = restrictionCollector.GetRestrictions(); + TEST(is_sorted(restrictions.cbegin(), restrictions.cend()), ()); + + RestrictionVec const expectedRestrictions = + {{Restriction::Type::No, {1, 1}}, + {Restriction::Type::Only, {1, 2}}, + {Restriction::Type::Only, {3, 4}}}; + TEST_EQUAL(restrictions, expectedRestrictions, ()); } } // namespace routing diff --git a/generator/generator_tests/restriction_test.cpp b/generator/generator_tests/restriction_test.cpp new file mode 100644 index 0000000000..bc64079940 --- /dev/null +++ b/generator/generator_tests/restriction_test.cpp @@ -0,0 +1,136 @@ +#include "testing/testing.hpp" + +#include "generator/generator_tests_support/test_feature.hpp" +#include "generator/generator_tests_support/test_mwm_builder.hpp" + +#include "generator/restriction_collector.hpp" +#include "generator/restriction_generator.hpp" + +#include "indexer/index.hpp" +#include "indexer/mwm_set.hpp" +#include "indexer/restriction_loader.hpp" + +#include "coding/file_name_utils.hpp" + +#include "platform/platform_tests_support/scoped_dir.hpp" +#include "platform/platform_tests_support/scoped_file.hpp" + +#include "platform/platform.hpp" +#include "platform/country_file.hpp" + +#include "base/logging.hpp" +#include "base/scope_guard.hpp" + +#include "std/string.hpp" + +using namespace feature; +using namespace generator; +using namespace platform; +using namespace routing; +using namespace platform::tests_support; + +namespace +{ +// Directory name for creating test mwm and temporary files. +string const kTestDir = "restriction_generation_test"; +// Temporary mwm name for testing. +string const kTestMwm = "test"; +string const kRestrictionFileName = "restrictions_in_osm_ids.csv"; +string const featureId2OsmIdsName = "feature_id_to_osm_ids.csv"; + +void BuildEmptyMwm(LocalCountryFile & country) +{ + generator::tests_support::TestMwmBuilder builder(country, feature::DataHeader::country); +} + +/// \brief Generates a restriction section, adds it to an empty mwm, +/// loads the restriction section and test loaded restrictions. +/// \param restrictionContent comma separated text with restrictions in osm id terms. +/// \param mappingContent comma separated text with with mapping from feature id to osm ids. +void TestRestrictionBuilding(string const & restrictionContent, string const & mappingContent) +{ + Platform & platform = GetPlatform(); + string const writeableDir = platform.WritableDir(); + + // Building empty mwm. + LocalCountryFile country(my::JoinFoldersToPath(writeableDir, kTestDir), CountryFile(kTestMwm), 1); + ScopedDir const scopedDir(kTestDir); + string const mwmRelativePath = my::JoinFoldersToPath(kTestDir, kTestMwm + DATA_FILE_EXTENSION); + ScopedFile const scopedMwm(mwmRelativePath); + BuildEmptyMwm(country); + + // Creating files with restrictions. + string const restrictionRelativePath = my::JoinFoldersToPath(kTestDir, kRestrictionFileName); + ScopedFile const restrictionScopedFile(restrictionRelativePath, restrictionContent); + + string const mappingRelativePath = my::JoinFoldersToPath(kTestDir, featureId2OsmIdsName); + ScopedFile const mappingScopedFile(mappingRelativePath, mappingContent); + + // Adding restriction section to mwm. + string const restrictionFullPath = my::JoinFoldersToPath(writeableDir, restrictionRelativePath); + string const mappingFullPath = my::JoinFoldersToPath(writeableDir, mappingRelativePath); + string const mwmFullPath = my::JoinFoldersToPath(writeableDir, mwmRelativePath); + BuildRoadRestrictions(mwmFullPath, restrictionFullPath, mappingFullPath); + + // Reading from mwm section and testing restrictions. + Index index; + auto const regResult = index.RegisterMap(country); + TEST_EQUAL(regResult.second, MwmSet::RegResult::Success, ()); + + MwmSet::MwmHandle mwmHandle = index.GetMwmHandleById(regResult.first); + TEST(mwmHandle.IsAlive(), ()); + RestrictionLoader const restrictionLoader(*mwmHandle.GetValue<MwmValue>()); + RestrictionCollector const restrictionCollector(restrictionFullPath, mappingFullPath); + + TEST_EQUAL(restrictionLoader.GetRestrictions(), restrictionCollector.GetRestrictions(), ()); +} + +UNIT_TEST(RestrictionGenerationTest_NoRestriction) +{ + string const restrictionContent = ""; + string const featureIdToOsmIdsContent = ""; + TestRestrictionBuilding(restrictionContent, featureIdToOsmIdsContent); +} + +UNIT_TEST(RestrictionGenerationTest_ZeroId) +{ + string const restrictionContent = R"(Only, 0, 0,)"; + string const featureIdToOsmIdsContent = R"(0, 0,)"; + TestRestrictionBuilding(restrictionContent, featureIdToOsmIdsContent); +} + +UNIT_TEST(RestrictionGenerationTest_OneRestriction) +{ + string const restrictionContent = R"(No, 10, 10,)"; + string const featureIdToOsmIdsContent = R"(1, 10,)"; + TestRestrictionBuilding(restrictionContent, featureIdToOsmIdsContent); +} + +UNIT_TEST(RestrictionGenerationTest_ThreeRestriction) +{ + string const restrictionContent = R"(No, 10, 10, + Only, 10, 20, + Only, 30, 40)"; + string const featureIdToOsmIdsContent = R"(1, 10, + 2, 20, + 3, 30, + 4, 40)"; + TestRestrictionBuilding(restrictionContent, featureIdToOsmIdsContent); +} + +UNIT_TEST(RestrictionGenerationTest_SevenRestriction) +{ + string const restrictionContent = R"(No, 10, 10, + No, 20, 20, + Only, 10, 20, + Only, 20, 30, + No, 30, 30, + No, 40, 40, + Only, 30, 40,)"; + string const featureIdToOsmIdsContent = R"(1, 10, + 2, 20, + 3, 30, + 4, 40)"; + TestRestrictionBuilding(restrictionContent, featureIdToOsmIdsContent); +} +} // namespace diff --git a/generator/restrictions.cpp b/generator/restriction_collector.cpp index c7e14ff517..c4c1a6df0c 100644 --- a/generator/restrictions.cpp +++ b/generator/restriction_collector.cpp @@ -1,4 +1,4 @@ -#include "generator/restrictions.hpp" +#include "generator/restriction_collector.hpp" #include "base/assert.hpp" #include "base/logging.hpp" @@ -37,37 +37,6 @@ bool ParseLineOfNumbers(istringstream & stream, vector<uint64_t> & numbers) namespace routing { -RestrictionCollector::FeatureId const RestrictionCollector::kInvalidFeatureId = - numeric_limits<RestrictionCollector::FeatureId>::max(); - -RestrictionCollector::Restriction::Restriction(Type type, size_t linkNumber) : m_type(type) -{ - m_links.resize(linkNumber, kInvalidFeatureId); -} - -RestrictionCollector::Restriction::Restriction(Type type, vector<FeatureId> const & links) - : m_links(links), m_type(type) -{ -} - -bool RestrictionCollector::Restriction::IsValid() const -{ - return find(begin(m_links), end(m_links), kInvalidFeatureId) == end(m_links); -} - -bool RestrictionCollector::Restriction::operator==(Restriction const & restriction) const -{ - return m_links == restriction.m_links && m_type == restriction.m_type; -} - -bool RestrictionCollector::Restriction::operator<(Restriction const & restriction) const -{ - if (m_type != restriction.m_type) - return m_type < restriction.m_type; - - return m_links < restriction.m_links; -} - RestrictionCollector::RestrictionCollector(string const & restrictionPath, string const & featureId2OsmIdsPath) { @@ -111,7 +80,7 @@ bool RestrictionCollector::ParseFeatureId2OsmIdsMapping(string const & featureId if (ids.size() <= 1) return false; // Every line should contain at least feature id and osm id. - FeatureId const featureId = static_cast<FeatureId>(ids.front()); + Restriction::FeatureId const featureId = static_cast<Restriction::FeatureId>(ids.front()); ids.erase(ids.begin()); AddFeatureId(featureId, ids); } @@ -132,7 +101,7 @@ bool RestrictionCollector::ParseRestrictions(string const & restrictionPath) istringstream lineStream(line); string typeStr; getline(lineStream, typeStr, ',' ); - Type type; + Restriction::Type type; if (!FromString(typeStr, type)) return false; @@ -169,7 +138,7 @@ void RestrictionCollector::ComposeRestrictions() if (distance(rangeId.first, rangeId.second) != 1) continue; // |osmId| mentioned in restrictions was included in more than one feature. - FeatureId const & featureId = rangeId.first->second; + Restriction::FeatureId const & featureId = rangeId.first->second; // Adding feature id to restriction coresponded to the osm id. restriction.m_links[index.m_linkNumber] = featureId; } @@ -186,7 +155,7 @@ void RestrictionCollector::RemoveInvalidRestrictions() m_restrictions.end()); } -void RestrictionCollector::AddRestriction(Type type, vector<uint64_t> const & osmIds) +void RestrictionCollector::AddRestriction(Restriction::Type type, vector<uint64_t> const & osmIds) { m_restrictions.emplace_back(type, osmIds.size()); size_t const restrictionCount = m_restrictions.size() - 1; @@ -194,7 +163,7 @@ void RestrictionCollector::AddRestriction(Type type, vector<uint64_t> const & os m_restrictionIndex.emplace_back(osmIds[i], Index({restrictionCount, i})); } -void RestrictionCollector::AddFeatureId(FeatureId featureId, vector<uint64_t> const & osmIds) +void RestrictionCollector::AddFeatureId(Restriction::FeatureId featureId, vector<uint64_t> const & osmIds) { // Note. One |featureId| could correspond to several osm ids. // but for road feature |featureId| corresponds exactly one osm id. @@ -202,36 +171,36 @@ void RestrictionCollector::AddFeatureId(FeatureId featureId, vector<uint64_t> co m_osmIds2FeatureId.insert(make_pair(osmId, featureId)); } -string ToString(RestrictionCollector::Type const & type) +string ToString(Restriction::Type const & type) { switch (type) { - case RestrictionCollector::Type::No: + case Restriction::Type::No: return kNoStr; - case RestrictionCollector::Type::Only: + case Restriction::Type::Only: return kOnlyStr; } return "Unknown"; } -bool FromString(string str, RestrictionCollector::Type & type) +bool FromString(string str, Restriction::Type & type) { str.erase(remove_if(str.begin(), str.end(), isspace), str.end()); if (str == kNoStr) { - type = RestrictionCollector::Type::No; + type = Restriction::Type::No; return true; } if (str == kOnlyStr) { - type = RestrictionCollector::Type::Only; + type = Restriction::Type::Only; return true; } return false; } -string DebugPrint(RestrictionCollector::Type const & type) +string DebugPrint(Restriction::Type const & type) { return ToString(type); } @@ -244,7 +213,7 @@ string DebugPrint(RestrictionCollector::Index const & index) return out.str(); } -string DebugPrint(RestrictionCollector::Restriction const & restriction) +string DebugPrint(Restriction const & restriction) { ostringstream out; out << "m_links:[" << ::DebugPrint(restriction.m_links) << "] m_type:" diff --git a/generator/restrictions.hpp b/generator/restriction_collector.hpp index 4c3aaa0bdf..432bcf8dc0 100644 --- a/generator/restrictions.hpp +++ b/generator/restriction_collector.hpp @@ -1,5 +1,7 @@ #pragma once +#include "indexer/routing.hpp" + #include "std/functional.hpp" #include "std/limits.hpp" #include "std/string.hpp" @@ -7,8 +9,6 @@ #include "std/utility.hpp" #include "std/vector.hpp" -class RelationElement; - namespace routing { /// This class collects all relations with type restriction and save feature ids of @@ -19,39 +19,8 @@ class RestrictionCollector friend void UnitTest_RestrictionTest_InvalidCase(); friend void UnitTest_RestrictionTest_ParseRestrictions(); friend void UnitTest_RestrictionTest_ParseFeatureId2OsmIdsMapping(); -public: - using FeatureId = uint32_t; - static FeatureId const kInvalidFeatureId; - - /// \brief Types of road graph restrictions. - /// \note Despite the fact more that 10 restriction tags are present in osm all of them - /// could be split into two categories. - /// * no_left_turn, no_right_turn, no_u_turn and so on go to "No" category. - /// * only_left_turn, only_right_turn and so on go to "Only" category. - /// That's enough to rememeber if - /// * there's only way to pass the junction is driving along the restriction (Only) - /// * driving along the restriction is prohibited (No) - enum class Type - { - No, // Going according such restriction is prohibited. - Only, // Only going according such restriction is permitted - }; - - /// \brief Restriction to modify road graph. - struct Restriction - { - Restriction(Type type, size_t linkNumber); - // Constructor for testing. - Restriction(Type type, vector<FeatureId> const & links); - - bool IsValid() const; - bool operator==(Restriction const & restriction) const; - bool operator<(Restriction const & restriction) const; - - vector<FeatureId> m_links; - Type m_type; - }; +public: /// \brief Addresses a link in vector<Restriction>. struct Index { @@ -75,7 +44,8 @@ public: /// \note Complexity of the method is up to linear in the size of |m_restrictions|. bool IsValid() const; - vector<Restriction> const & GetRestriction() { return m_restrictions; } + /// \returns Sorted vector of restrictions. + RestrictionVec const & GetRestrictions() const { return m_restrictions; } private: /// \brief Parses comma separated text file with line in following format: @@ -107,24 +77,24 @@ private: /// \brief Adds feature id and corresponding vector of |osmIds| to |m_osmId2FeatureId|. /// \note One feature id (|featureId|) may correspond to several osm ids (|osmIds|). - void AddFeatureId(FeatureId featureId, vector<uint64_t> const & osmIds); + void AddFeatureId(Restriction::FeatureId featureId, vector<uint64_t> const & osmIds); /// \brief Adds a restriction (vector of osm id). /// \param type is a type of restriction /// \param osmIds is osm ids of restriction links /// \note This method should be called to add a restriction when feature ids of the restriction /// are unknown. The feature ids should be set later with a call of |SetFeatureId(...)| method. - void AddRestriction(Type type, vector<uint64_t> const & osmIds); + void AddRestriction(Restriction::Type type, vector<uint64_t> const & osmIds); - vector<Restriction> m_restrictions; + RestrictionVec m_restrictions; vector<pair<uint64_t, Index>> m_restrictionIndex; - unordered_multimap<uint64_t, FeatureId> m_osmIds2FeatureId; + unordered_multimap<uint64_t, Restriction::FeatureId> m_osmIds2FeatureId; }; -string ToString(RestrictionCollector::Type const & type); -bool FromString(string str, RestrictionCollector::Type & type); -string DebugPrint(RestrictionCollector::Type const & type); +string ToString(Restriction::Type const & type); +bool FromString(string str, Restriction::Type & type); +string DebugPrint(Restriction::Type const & type); string DebugPrint(RestrictionCollector::Index const & index); -string DebugPrint(RestrictionCollector::Restriction const & restriction); +string DebugPrint(Restriction const & restriction); } // namespace routing diff --git a/generator/restriction_dumper.cpp b/generator/restriction_dumper.cpp index a7b266154b..da0f09e1b9 100644 --- a/generator/restriction_dumper.cpp +++ b/generator/restriction_dumper.cpp @@ -1,13 +1,16 @@ #include "generator/intermediate_elements.hpp" #include "generator/osm_id.hpp" #include "generator/restriction_dumper.hpp" -#include "generator/restrictions.hpp" +#include "generator/restriction_collector.hpp" + +#include "indexer/routing.hpp" #include "base/logging.hpp" #include "std/algorithm.hpp" #include "std/fstream.hpp" #include "std/string.hpp" +#include "std/utility.hpp" #include "std/vector.hpp" namespace @@ -21,16 +24,16 @@ vector<string> const kRestrictionTypesOnly = {"only_right_turn", "only_left_turn /// \brief Converts restriction type form string to RestrictionCollector::Type. /// \returns Fisrt item is a result of conversion. Second item is true /// if convertion was successful and false otherwise. -pair<RestrictionCollector::Type, bool> TagToType(string const & type) +pair<Restriction::Type, bool> TagToType(string const & type) { if (find(kRestrictionTypesNo.cbegin(), kRestrictionTypesNo.cend(), type) != kRestrictionTypesNo.cend()) - return make_pair(RestrictionCollector::Type::No, true); + return make_pair(Restriction::Type::No, true); if (find(kRestrictionTypesOnly.cbegin(), kRestrictionTypesOnly.cend(), type) != kRestrictionTypesOnly.cend()) - return make_pair(RestrictionCollector::Type::Only, true); + return make_pair(Restriction::Type::Only, true); // Unsupported restriction type. - return make_pair(RestrictionCollector::Type::No, false); + return make_pair(Restriction::Type::No, false); } } // namespace diff --git a/generator/restriction_generator.cpp b/generator/restriction_generator.cpp index bad3cef9e8..ac35ba141b 100644 --- a/generator/restriction_generator.cpp +++ b/generator/restriction_generator.cpp @@ -1,7 +1,44 @@ #include "generator/restriction_generator.hpp" -#include "generator/restrictions.hpp" +#include "generator/restriction_collector.hpp" + +#include "coding/file_container.hpp" +#include "coding/file_writer.hpp" #include "base/logging.hpp" +#include "base/stl_helpers.hpp" + +#include "defines.hpp" + +#include "std/algorithm.hpp" + +using namespace feature; +using namespace routing; + +namespace +{ +/// \brief Serializes a range of restrictions form |begin| to |end| to |sink|. +/// \param begin is an iterator to the first item to serialize. +/// \param end is an iterator to the element after the last element to serialize. +/// \note All restrictions should have the same type. +void SerializeRestrictions(RestrictionVec::const_iterator begin, RestrictionVec::const_iterator end, + FileWriter & sink) +{ + if (begin == end) + return; + + Restriction::Type const type = begin->m_type; + + Restriction prevRestriction(type, 0); + prevRestriction.m_links.resize(feature::RestrictionSerializer::kSupportedLinkNumber, 0); + for (auto it = begin; it != end; ++it) + { + CHECK_EQUAL(type, it->m_type, ()); + RestrictionSerializer serializer(*it); + serializer.Serialize(prevRestriction, sink); + prevRestriction = serializer.GetRestriction(); + } +} +} // namespace namespace routing { @@ -17,6 +54,22 @@ bool BuildRoadRestrictions(string const & mwmPath, string const & restrictionPat return false; } + RestrictionVec const & restrictions = restrictionCollector.GetRestrictions(); + + auto const firstOnlyIt = upper_bound(restrictions.cbegin(), restrictions.cend(), + Restriction(Restriction::Type::No, 0), my::LessBy(&Restriction::m_type)); + RoutingHeader header; + header.m_noRestrictionCount = distance(restrictions.cbegin(), firstOnlyIt); + header.m_onlyRestrictionCount = restrictions.size() - header.m_noRestrictionCount; + LOG(LINFO, ("Header info. There are", header.m_noRestrictionCount, "and", header.m_onlyRestrictionCount, + "only restrictions")); + + FilesContainerW cont(mwmPath, FileWriter::OP_WRITE_EXISTING); + FileWriter w = cont.GetWriter(ROUTING_FILE_TAG); + header.Serialize(w); + SerializeRestrictions(restrictions.cbegin(), firstOnlyIt, w); + SerializeRestrictions(firstOnlyIt, restrictions.end(), w); + return true; } } // namespace routing diff --git a/generator/restriction_generator.hpp b/generator/restriction_generator.hpp index a170a0b8ad..ce7eca560a 100644 --- a/generator/restriction_generator.hpp +++ b/generator/restriction_generator.hpp @@ -4,6 +4,20 @@ namespace routing { - bool BuildRoadRestrictions(string const & mwmPath, string const & restrictionPath, - string const & featureId2OsmIdsPath); +/// \brief Builds section with road restrictions. +/// \param mwmPath path to mwm which will be added with road restriction section. +/// \param restrictionPath comma separated (csv like) file with road restrictions in osm ids terms +/// in the following format: +/// <type of restrictions>, <osm id 1 of the restriction>, <osm id 2>, and so on +/// For example: +/// Only, 335049632, 49356687, +/// No, 157616940, 157616940, +/// \param featureId2OsmIdsPath comma separated (csv like) file with mapping from feature id to osm ids +/// in following format: +/// <feature id>, <osm id 1 corresponding feature id>, <osm id 2 corresponding feature id>, and so on +/// For example: +/// 137999, 5170186, +/// 138000, 5170209, +bool BuildRoadRestrictions(string const & mwmPath, string const & restrictionPath, + string const & featureId2OsmIdsPath); } // namespace routing diff --git a/indexer/indexer.pro b/indexer/indexer.pro index 69a8396265..38f5a0d9a3 100644 --- a/indexer/indexer.pro +++ b/indexer/indexer.pro @@ -56,6 +56,8 @@ SOURCES += \ point_to_int64.cpp \ postcodes_matcher.cpp \ # it's in indexer due to editor wich is in indexer and depends on postcodes_marcher rank_table.cpp \ + restriction_loader.cpp \ + routing.cpp \ scales.cpp \ search_delimiters.cpp \ # it's in indexer because of CategoriesHolder dependency. search_string_utils.cpp \ # it's in indexer because of CategoriesHolder dependency. @@ -117,6 +119,8 @@ HEADERS += \ point_to_int64.hpp \ postcodes_matcher.hpp \ # it's in indexer due to editor wich is in indexer and depends on postcodes_marcher rank_table.hpp \ + restriction_loader.hpp \ + routing.hpp \ scale_index.hpp \ scale_index_builder.hpp \ scales.hpp \ diff --git a/indexer/restriction_loader.cpp b/indexer/restriction_loader.cpp new file mode 100644 index 0000000000..9be2c309ad --- /dev/null +++ b/indexer/restriction_loader.cpp @@ -0,0 +1,47 @@ +#include "indexer/restriction_loader.hpp" + +#include "coding/reader.hpp" + +using namespace routing; + +namespace +{ +template <class TSource> +void DeserializeRestrictions(Restriction::Type type, uint32_t count, TSource & src, RestrictionVec & restrictions) +{ + feature::RestrictionSerializer serializer(Restriction(type, 0)); + Restriction prevRestriction(type, 0); + prevRestriction.m_links.resize(feature::RestrictionSerializer::kSupportedLinkNumber, 0); + for (size_t i = 0; i < count; ++i) + { + serializer.Deserialize(prevRestriction, src); + restrictions.push_back(serializer.GetRestriction()); + prevRestriction = serializer.GetRestriction(); + } +} +} // namespace + +namespace feature +{ +RestrictionLoader::RestrictionLoader(MwmValue const & mwmValue) +{ + m_countryFileName = mwmValue.GetCountryFileName(); + if (!mwmValue.m_cont.IsExist(ROUTING_FILE_TAG)) + return; + + try + { + m_reader = make_unique<FilesContainerR::TReader>(mwmValue.m_cont.GetReader(ROUTING_FILE_TAG)); + ReaderSource<FilesContainerR::TReader> src(*m_reader); + m_header.Deserialize(src); + + DeserializeRestrictions(Restriction::Type::No, m_header.m_noRestrictionCount, src, m_restrictions); + DeserializeRestrictions(Restriction::Type::Only, m_header.m_onlyRestrictionCount, src, m_restrictions); + } + catch (Reader::OpenException const & e) + { + m_header.Reset(); + LOG(LERROR, ("File", m_countryFileName, "Error while reading", ROUTING_FILE_TAG, "section.", e.Msg())); + } +} +} // namespace feature diff --git a/indexer/restriction_loader.hpp b/indexer/restriction_loader.hpp new file mode 100644 index 0000000000..3083632173 --- /dev/null +++ b/indexer/restriction_loader.hpp @@ -0,0 +1,28 @@ +#pragma once + +#include "indexer/index.hpp" +#include "indexer/routing.hpp" + +#include "coding/file_container.hpp" + +#include "std/string.hpp" +#include "std/unique_ptr.hpp" + +namespace feature +{ +class RestrictionLoader +{ +public: + explicit RestrictionLoader(MwmValue const & mwmValue); + + bool HasRestrictions() const { return !m_restrictions.empty(); } + + routing::RestrictionVec const & GetRestrictions() const { return m_restrictions; } + +private: + unique_ptr<FilesContainerR::TReader> m_reader; + RoutingHeader m_header; + routing::RestrictionVec m_restrictions; + string m_countryFileName; +}; +} // namespace feature diff --git a/indexer/routing.cpp b/indexer/routing.cpp new file mode 100644 index 0000000000..e2e1ec186b --- /dev/null +++ b/indexer/routing.cpp @@ -0,0 +1,43 @@ +#include "indexer/routing.hpp" + +namespace routing +{ +Restriction::FeatureId const Restriction::kInvalidFeatureId = + numeric_limits<Restriction::FeatureId>::max(); + +Restriction::Restriction(Type type, size_t linkNumber) : m_type(type) +{ + m_links.resize(linkNumber, kInvalidFeatureId); +} + +Restriction::Restriction(Type type, vector<FeatureId> const & links) + : m_links(links), m_type(type) +{ +} + +bool Restriction::IsValid() const +{ + return !m_links.empty() && find(begin(m_links), end(m_links), kInvalidFeatureId) == end(m_links); +} + +bool Restriction::operator==(Restriction const & restriction) const +{ + return m_links == restriction.m_links && m_type == restriction.m_type; +} + +bool Restriction::operator<(Restriction const & restriction) const +{ + if (m_type != restriction.m_type) + return m_type < restriction.m_type; + + return m_links < restriction.m_links; +} +} // namespace routing + +namespace feature +{ +// For the time being only one kind of restrictions is support. It's line-point-line +// restrictions in osm ids term. Such restrictions reflects to two feature ids +// restrictions in feature id terms. Because of it supported number of links is two. +size_t const RestrictionSerializer::kSupportedLinkNumber = 2; +} diff --git a/indexer/routing.hpp b/indexer/routing.hpp new file mode 100644 index 0000000000..c87baf5a82 --- /dev/null +++ b/indexer/routing.hpp @@ -0,0 +1,142 @@ +#pragma once + +#include "coding/bit_streams.hpp" +#include "coding/elias_coder.hpp" +#include "coding/reader.hpp" +#include "coding/varint.hpp" +#include "coding/write_to_sink.hpp" + +#include "base/assert.hpp" +#include "base/bits.hpp" + +#include "std/vector.hpp" + +namespace routing +{ +/// \brief Restriction to modify road graph. +struct Restriction +{ + using FeatureId = uint32_t; + static FeatureId const kInvalidFeatureId; + + /// \brief Types of road graph restrictions. + /// \note Despite the fact more that 10 restriction tags are present in osm all of them + /// could be split into two categories. + /// * no_left_turn, no_right_turn, no_u_turn and so on go to "No" category. + /// * only_left_turn, only_right_turn and so on go to "Only" category. + /// That's enough to rememeber if + /// * there's only way to pass the junction is driving along the restriction (Only) + /// * driving along the restriction is prohibited (No) + enum class Type + { + No, // Going according such restriction is prohibited. + Only, // Only going according such restriction is permitted + }; + + Restriction(Type type, size_t linkNumber); + Restriction(Type type, vector<FeatureId> const & links); + + bool IsValid() const; + bool operator==(Restriction const & restriction) const; + bool operator<(Restriction const & restriction) const; + + vector<FeatureId> m_links; + Type m_type; +}; + +using RestrictionVec = vector<Restriction>; +} // namespace routing + +namespace feature +{ +struct RoutingHeader +{ + RoutingHeader() { Reset(); } + + template <class TSink> + void Serialize(TSink & sink) const + { + WriteToSink(sink, m_version); + WriteToSink(sink, m_reserved); + WriteToSink(sink, m_noRestrictionCount); + WriteToSink(sink, m_onlyRestrictionCount); + } + + template <class TSource> + void Deserialize(TSource & src) + { + m_version = ReadPrimitiveFromSource<uint16_t>(src); + m_reserved = ReadPrimitiveFromSource<uint16_t>(src); + m_noRestrictionCount = ReadPrimitiveFromSource<uint32_t>(src); + m_onlyRestrictionCount = ReadPrimitiveFromSource<uint32_t>(src); + } + + void Reset() + { + m_version = 0; + m_reserved = 0; + m_noRestrictionCount = 0; + m_onlyRestrictionCount = 0; + } + + uint16_t m_version; + uint16_t m_reserved; + uint32_t m_noRestrictionCount; + uint32_t m_onlyRestrictionCount; +}; + +static_assert(sizeof(RoutingHeader) == 12, "Wrong header size of routing section."); + +class RestrictionSerializer +{ +public: + RestrictionSerializer() : m_restriction(routing::Restriction::Type::No, 0) {} + explicit RestrictionSerializer(routing::Restriction const & restriction) : m_restriction(restriction) {} + + template <class TSink> + void Serialize(routing::Restriction const & prevRestriction, TSink & sink) const + { + CHECK(m_restriction.IsValid(), ()); + CHECK_EQUAL(m_restriction.m_links.size(), kSupportedLinkNumber, + ("Only", kSupportedLinkNumber, "links restriction are supported.")); + CHECK_EQUAL(m_restriction.m_links.size(), prevRestriction.m_links.size(), ()); + + BitWriter<TSink> bits(sink); + for (size_t i = 0; i < kSupportedLinkNumber; ++i) + { + uint32_t const delta = bits::ZigZagEncode(static_cast<int32_t>(m_restriction.m_links[i]) - + static_cast<int32_t>(prevRestriction.m_links[i])); + coding::DeltaCoder::Encode(bits, delta + 1 /* making it greater than zero */); + } + } + + template <class TSource> + bool Deserialize(routing::Restriction const & prevRestriction, TSource & src) + { + BitReader<TSource> bits(src); + m_restriction.m_links.resize(kSupportedLinkNumber); + for (size_t i = 0; i < kSupportedLinkNumber; ++i) + { + uint32_t const biasedDelta = coding::DeltaCoder::Decode(bits); + if (biasedDelta == 0) + { + LOG(LERROR, ("Decoded link restriction feature id delta is zero.")); + m_restriction.m_links.clear(); + return false; + } + uint32_t const delta = biasedDelta - 1; + m_restriction.m_links[i] = + static_cast<routing::Restriction::FeatureId>(bits::ZigZagDecode(delta) + + prevRestriction.m_links[i]); + } + return true; + } + + routing::Restriction const & GetRestriction() const { return m_restriction; } + + static size_t const kSupportedLinkNumber; + +private: + routing::Restriction m_restriction; +}; +} // namespace feature diff --git a/tools/unix/generate_mwm.sh b/tools/unix/generate_mwm.sh index 13c47bff28..56dcf059c2 100755 --- a/tools/unix/generate_mwm.sh +++ b/tools/unix/generate_mwm.sh @@ -104,7 +104,7 @@ if [ "$SOURCE_TYPE" == "pbf" -o "$SOURCE_TYPE" == "bz2" -o "$SOURCE_TYPE" == "os fi if [ "$SOURCE_TYPE" == "o5m" ]; then $GENERATOR_TOOL $INTDIR_FLAG --osm_file_type=o5m --osm_file_name="$SOURCE_FILE" --preprocess=true || fail "Preprocessing failed" - $GENERATOR_TOOL $INTDIR_FLAG --osm_file_type=o5m --osm_file_name="$SOURCE_FILE" --data_path="$TARGET" --user_resource_path="$DATA_PATH" $GENERATE_EVERYTHING --output="$BASE_NAME" + $GENERATOR_TOOL $INTDIR_FLAG --osm_file_type=o5m --osm_file_name="$SOURCE_FILE" --restriction_name="restrictions.csv" --feature_id_to_osm_ids_name="feature_id_to_osm_ids.csv" --generate_outgoing_edge_index --data_path="$TARGET" --user_resource_path="$DATA_PATH" $GENERATE_EVERYTHING --output="$BASE_NAME" else fail "Unsupported source type: $SOURCE_TYPE" fi |