Added city rank table

7 files changed, 528 insertions, 1 deletions

diff --git a/indexer/drawing_rules.cpp b/indexer/drawing_rules.cpp
index 3dd98076af..a825971743 100644
--- a/indexer/drawing_rules.cpp
+++ b/indexer/drawing_rules.cpp
@@ -91,6 +91,7 @@ ShieldRuleProto const * BaseRule::GetShield() const
 
 RulesHolder::RulesHolder()
   : m_bgColors(scales::UPPER_STYLE_SCALE+1, DEFAULT_BG_COLOR)
+  , m_cityRankTable(GetConstRankCityRankTable())
 {}
 
 RulesHolder::~RulesHolder()
@@ -148,6 +149,14 @@ uint32_t RulesHolder::GetBgColor(int scale) const
   return m_bgColors[scale];
 }
 
+double RulesHolder::GetCityRank(int scale, uint32_t population) const
+{
+  double rank;
+  if (!m_cityRankTable->GetCityRank(scale, population, rank))
+    return -1.0; // do not draw
+  return rank;
+}
+
 void RulesHolder::ClearCaches()
 {
   ForEachRule(bind(static_cast<void (BaseRule::*)()>(&BaseRule::MakeEmptyID), _4));
@@ -441,12 +450,45 @@ void RulesHolder::LoadFromBinaryProto(string const & s)
   InitBackgroundColors(doSet.m_cont);
 }
 
+void RulesHolder::LoadCityRankTableFromString(string & s)
+{
+  unique_ptr<ICityRankTable> table;
+
+  if (!s.empty())
+  {
+    table = GetCityRankTableFromString(s);
+
+    if (nullptr == table)
+      LOG(LINFO, ("Invalid city-rank-table file"));
+  }
+
+  if (nullptr == table)
+    table = GetConstRankCityRankTable();
+
+  m_cityRankTable = move(table);
+}
+
 void LoadRules()
 {
   string buffer;
-  GetStyleReader().GetDrawingRulesReader().ReadAsString(buffer);
 
+  // Load drules_proto
+  GetStyleReader().GetDrawingRulesReader().ReadAsString(buffer);
   rules().LoadFromBinaryProto(buffer);
+
+  // Load city_rank
+  buffer.clear();
+  try
+  {
+    ReaderPtr<Reader> cityRankFileReader = GetPlatform().GetReader("city_rank.txt");
+    cityRankFileReader.ReadAsString(buffer);
+  }
+  catch (FileAbsentException & e)
+  {
+    // city-rank.txt file is optional, if it does not exist, then default city-rank-table is used
+    LOG(LINFO, ("File city-rank-table does not exist", e.Msg()));
+  }
+  rules().LoadCityRankTableFromString(buffer);
 }
 
 }
diff --git a/indexer/drawing_rules.hpp b/indexer/drawing_rules.hpp
index 1624ed3f3a..8292836fea 100644
--- a/indexer/drawing_rules.hpp
+++ b/indexer/drawing_rules.hpp
@@ -1,5 +1,7 @@
 #pragma once
+
 #include "indexer/drawing_rule_def.hpp"
+#include "indexer/drules_city_rank_table.hpp"
 
 #include "base/base.hpp"
 #include "base/buffer_vector.hpp"
@@ -66,6 +68,8 @@ namespace drule
     /// background color for scales in range [0...scales::UPPER_STYLE_SCALE]
     vector<uint32_t> m_bgColors;
 
+    unique_ptr<ICityRankTable> m_cityRankTable;
+
   public:
     RulesHolder();
     ~RulesHolder();
@@ -81,12 +85,15 @@ namespace drule
 
     uint32_t GetBgColor(int scale) const;
 
+    double GetCityRank(int scale, uint32_t population) const;
+
 #ifdef OMIM_OS_DESKTOP
     void LoadFromTextProto(string const & buffer);
     static void SaveToBinaryProto(string const & buffer, ostream & s);
 #endif
 
     void LoadFromBinaryProto(string const & s);
+    void LoadCityRankTableFromString(string & s);
 
     template <class ToDo> void ForEachRule(ToDo toDo)
     {
diff --git a/indexer/drules_city_rank_table.cpp b/indexer/drules_city_rank_table.cpp
new file mode 100644
index 0000000000..59cab838b9
--- /dev/null
+++ b/indexer/drules_city_rank_table.cpp
@@ -0,0 +1,292 @@
+#include "indexer/drules_city_rank_table.hpp"
+#include "indexer/scales.hpp"
+
+#include "std/algorithm.hpp"
+#include "std/bind.hpp"
+#include "std/exception.hpp"
+#include "std/function.hpp"
+#include "std/unordered_map.hpp"
+#include "std/utility.hpp"
+#include "std/vector.hpp"
+
+#include "base/assert.hpp"
+
+namespace drule
+{
+
+namespace
+{
+
+using TZoomRange = pair<uint32_t, uint32_t>;
+using TPopulationRange = pair<uint32_t, uint32_t>;
+using TRankForPopulationRange = pair<double, TPopulationRange>;
+using TCityRankVector = vector<TRankForPopulationRange>;
+using TCityRankTable = unordered_map<uint32_t, TCityRankVector>;
+
+class ConstCityRankTable : public ICityRankTable
+{
+public:
+  explicit ConstCityRankTable(double rank)
+    : m_rank(rank)
+  {
+  }
+
+  bool GetCityRank(uint32_t /*zoomLevel*/, uint32_t /*population*/, double & rank) const override
+  {
+    rank = m_rank;
+    return true;
+  }
+
+private:
+  double const m_rank;
+};
+
+class CityRankTable : public ICityRankTable
+{
+public:
+  explicit CityRankTable(TCityRankTable && table)
+    : m_table(move(table))
+  {
+  }
+
+  bool GetCityRank(uint32_t zoomLevel, uint32_t population, double & rank) const override
+  {
+    auto const itr = m_table.find(zoomLevel);
+    if (itr == m_table.cend())
+      return false;
+
+    for (auto const & rp : itr->second)
+    {
+      if (population >= rp.second.first && population <= rp.second.second)
+      {
+        rank = rp.first;
+        return true;
+      }
+    }
+
+    return false;
+  }
+
+private:
+  TCityRankTable const m_table;
+};
+
+void RemoveSpaces(string & s)
+{    
+  s.erase(remove_if(s.begin(), s.end(), &isspace), s.end());
+}
+
+bool ParseZoom(string const & s, size_t start, size_t end,
+               uint32_t & zFrom, uint32_t & zTo)
+{
+  ASSERT_LESS(start, end, ());
+  ASSERT_LESS(end, s.length(), ());
+
+  // Parse Zoom
+  // z[zoomFrom]-[zoomTo]
+  // z[zoom]
+
+  // length of Zoom must be more than 1 because it starts with z
+  if ((end - start) <= 1)
+    return false;
+
+  if (s[start] != 'z')
+    return false;
+
+  string zFromStr, zToStr;
+
+  size_t const d = s.find('-', start + 1);
+  if (d == string::npos || d >= end)
+  {
+    zFromStr.assign(s.begin() + start + 1, s.begin() + end);
+    zToStr = zFromStr;
+  }
+  else
+  {
+    zFromStr.assign(s.begin() + start + 1, s.begin() + d);
+    zToStr.assign(s.begin() + d + 1, s.begin() + end);
+  }
+
+  try
+  {
+    zFrom = zFromStr.empty() ? 0 : stoi(zFromStr);
+    zTo = zToStr.empty() ? scales::UPPER_STYLE_SCALE : stoi(zToStr);
+  }
+  catch (exception &)
+  {
+    // stoi has not parsed a number
+    return false;
+  }
+
+  if (zFrom > zTo)
+    return false;
+
+  return true;
+}
+
+bool ParsePopulationRank(string const & s, size_t start, size_t end,
+                         uint32_t & popFrom, uint32_t & popTo, double & rank)
+{
+  ASSERT_LESS(start, end, ());
+  ASSERT_LESS(end, s.length(), ());
+
+  // Parse PopulationRank
+  // [populationFrom]-[populationTo]:rank
+
+  size_t const d1 = s.find('-', start);
+  if (d1 == string::npos || d1 >= end)
+    return false;
+
+  size_t const d2 = s.find(':', d1 + 1);
+  if (d2 == string::npos || d2 >= end)
+    return false;
+
+  string popFromStr(s.begin() + start, s.begin() + d1);
+  string popToStr(s.begin() + d1 + 1, s.begin() + d2);
+  string rankStr(s.begin() + d2 + 1, s.begin() + end);
+
+  try
+  {
+    popFrom = popFromStr.empty() ? 0 : stoi(popFromStr);
+    popTo = popToStr.empty() ? numeric_limits<uint32_t>::max() : stoi(popToStr);
+    rank = stod(rankStr);
+  }
+  catch (exception &)
+  {
+    // stoi, stod has not parsed a number
+    return false;
+  }
+
+  if (popFrom > popTo)
+    return false;
+
+  return true;
+}
+
+bool ParsePopulationRanks(string const & s, size_t start, size_t end,
+                          function<void(uint32_t, uint32_t, double)> const & onPopRank)
+{
+  ASSERT_LESS(start, end, ());
+  ASSERT_LESS(end, s.length(), ());
+
+  // Parse 0...n of PopulationRank, delimited by ;
+
+  while (start < end)
+  {
+    size_t const i = s.find(';', start);
+    if (i == string::npos || i >= end)
+      return false;
+
+    if (i > start)
+    {
+      uint32_t popFrom, popTo;
+      double rank;
+      if (!ParsePopulationRank(s, start, i, popFrom, popTo, rank))
+        return false;
+
+      onPopRank(popFrom, popTo, rank);
+    }
+
+    start = i + 1;
+  }
+
+  return true;
+}
+
+bool ParseCityRankTable(string const & s,
+                        function<void(uint32_t, uint32_t)> const & onZoom,
+                        function<void(uint32_t, uint32_t, double)> const & onPopRank)
+{
+  // CityRankTable string format is
+  // z[zoomFrom]-[zoomTo] { [populationFrom]-[populationTo]:rank;[populationFrom]-[populationTo]:rank; }
+
+  size_t const end = s.length();
+  size_t start = 0;
+
+  while (start < end)
+  {
+    size_t const i = s.find('{', start);
+    if (i == string::npos)
+      return false;
+
+    size_t const j = s.find('}', i + 1);
+    if (j == string::npos)
+      return false;
+
+    uint32_t zFrom, zTo;
+    if (!ParseZoom(s, start, i, zFrom, zTo))
+      return false;
+
+    if (j > (i + 1))
+    {
+      onZoom(zFrom, zTo);
+
+      if (!ParsePopulationRanks(s, i + 1, j, onPopRank))
+        return false;
+    }
+
+    start = j + 1;
+  }
+
+  return true;
+}
+
+class CityRankTableBuilder
+{
+public:
+  unique_ptr<ICityRankTable> Parse(string & str)
+  {
+    RemoveSpaces(str);
+
+    auto onZoom = bind(&CityRankTableBuilder::OnZoom, this, _1, _2);
+    auto onPopRank = bind(&CityRankTableBuilder::OnPopulationRank, this, _1, _2, _3);
+    if (!ParseCityRankTable(str, onZoom, onPopRank))
+      return unique_ptr<ICityRankTable>();
+
+    Flush();
+
+    return make_unique<CityRankTable>(move(m_cityRanksTable));
+  }
+
+private:
+  void OnPopulationRank(uint32_t popFrom, uint32_t popTo, double rank)
+  {
+    m_cityRanksForZoomRange.emplace_back(make_pair(rank, make_pair(popFrom, popTo)));
+  }
+  void OnZoom(uint32_t zoomFrom, uint32_t zoomTo)
+  {
+    Flush();
+
+    m_zoomRange = make_pair(zoomFrom, zoomTo);
+  }
+  void Flush()
+  {
+    if (!m_cityRanksForZoomRange.empty())
+    {
+      for (uint32_t z = m_zoomRange.first; z <= m_zoomRange.second; ++z)
+      {
+        TCityRankVector & dst = m_cityRanksTable[z];
+        dst.insert(dst.end(), m_cityRanksForZoomRange.begin(), m_cityRanksForZoomRange.end());
+      }
+      m_cityRanksForZoomRange.clear();
+    }
+  }
+
+  TZoomRange m_zoomRange;
+  TCityRankVector m_cityRanksForZoomRange;
+  TCityRankTable m_cityRanksTable;
+};
+
+}  // namespace
+
+unique_ptr<ICityRankTable> GetCityRankTableFromString(string & str)
+{
+  return CityRankTableBuilder().Parse(str);
+}
+
+unique_ptr<ICityRankTable> GetConstRankCityRankTable(double rank)
+{
+  return unique_ptr<ICityRankTable>(new ConstCityRankTable(rank));
+}
+
+}  // namespace drule
diff --git a/indexer/drules_city_rank_table.hpp b/indexer/drules_city_rank_table.hpp
new file mode 100644
index 0000000000..b43d7cb3f3
--- /dev/null
+++ b/indexer/drules_city_rank_table.hpp
@@ -0,0 +1,51 @@
+#pragma once
+
+#include "std/string.hpp"
+#include "std/unique_ptr.hpp"
+
+namespace drule
+{
+
+class ICityRankTable
+{
+public:
+  virtual ~ICityRankTable() = default;
+  virtual bool GetCityRank(uint32_t zoomLevel, uint32_t population, double & rank) const = 0;
+};
+
+// Parses string and returns city-rank table which corresponds to string
+// String format similar to mapcss format:
+// z[ZOOMLEVEL_FROM]-[ZOOMLEVEL_TP]
+// {
+//    [POPULATION_FROMn]-[POPULATION_TOn]:RANKn;
+// }
+//
+// z[ZOOMLEVEL_FROM]-[ZOOMLEVEL_TO] - specifies zoom range for which population rula is applicable.
+// ZOOMLEVEL_FROM and ZOOMLEVEL_TO are non negative integers, ZOOMLEVEL_TO must be not less than
+// ZOOMLEVEL_FROM.
+// ZOOMLEVEL_FROM may be omitted, then ZOOMLEVEL_FROM is 0
+// ZOOMLEVEL_TO may be omitted, then ZOOMLEVEL_TO is UPPER_SCALE
+// if ZOOMLEVEL_FROM equals to ZOOMLEVEL_TO then z can be rewritten as z[ZOOMLEVEL]
+//
+// [POPULATION_FROMn]-[POPULATION_TOn]:RANKn; - specifies population range and city rank.
+// POPULATION_FROMn and POPULATION_TOn are non negative integers, POPULATION_TOn must be not less than
+// POPULATION_FROMn.
+// Similarly, POPULATION_FROMn can be ommited then, POPULATION_FROMn is 0
+// POPULATION_TOn also can be ommited then POPULATION_FROMn is MAX_UINT
+// RANKn is float value. if RANKn is less than 0 then population scope is not drawn,
+// if RANKn is 0 then city will be drawn as it specified in mapcss
+// if RANKn is more than 0 then font size will be (1.0 + RANKn) * fontSizeInMapcss
+//
+// Example is:
+// z-3 { -10000:-1; 10000-:0; }
+// z4 { -10000:0; 10000-:0.5; }
+// z5-9 { -10000:0; 10000-100000:0.5;100000-:0.75; }
+// z10- { -10000:0.5; 10000-100000:0.75;100000-:1; }
+
+// Returns city-rank-table if str matches to format, otherwise returns nullptr
+unique_ptr<ICityRankTable> GetCityRankTableFromString(string & str);
+
+// Returns city-rank-table which returns constant rank for any zoom and population.
+unique_ptr<ICityRankTable> GetConstRankCityRankTable(double rank = 0.0);
+
+}  // namespace drule
diff --git a/indexer/indexer.pro b/indexer/indexer.pro
index 88556f1f54..01e22175af 100644
--- a/indexer/indexer.pro
+++ b/indexer/indexer.pro
@@ -18,6 +18,7 @@ SOURCES += \
     data_header.cpp \
     drawing_rule_def.cpp \
     drawing_rules.cpp \
+    drules_city_rank_table.cpp \
     feature.cpp \
     feature_algo.cpp \
     feature_covering.cpp \
@@ -57,6 +58,7 @@ HEADERS += \
     data_header.hpp \
     drawing_rule_def.hpp \
     drawing_rules.hpp \
+    drules_city_rank_table.hpp \
     drules_include.hpp \
     feature.hpp \
     feature_algo.hpp \
diff --git a/indexer/indexer_tests/city_rank_table_test.cpp b/indexer/indexer_tests/city_rank_table_test.cpp
new file mode 100644
index 0000000000..7ad40e17f0
--- /dev/null
+++ b/indexer/indexer_tests/city_rank_table_test.cpp
@@ -0,0 +1,132 @@
+#include "testing/testing.hpp"
+
+#include "indexer/drules_city_rank_table.hpp"
+
+UNIT_TEST(TestCityRankTableParser)
+{
+  string s =
+    "z-4{\n"
+    "-10000:0.25;\n"
+    "10000-1000000:0.5;\n}\n"
+    " z5 { 1000-10000 : -1; } "
+    "z6-15{\n"
+    "-10000:0.25;\n"
+    "10000-:0.5;\n}\n"
+    "z16-{\n"
+    "-10000:0.25;\n"
+    "10000-10000000:0.5;\n}\n";
+
+  unique_ptr<drule::ICityRankTable> table = drule::GetCityRankTableFromString(s);
+  TEST(nullptr != table.get(), ());
+
+  double rank = 0.0;
+
+  // test zoom > 19
+
+  // test there is no rank for zoom > 19
+  TEST_EQUAL(false, table->GetCityRank(20, 100000, rank), ());
+
+  // test zoom 0-4
+
+  // test there is 0.25 rank for city with population = 5K and zoom = 3
+  TEST_EQUAL(true, table->GetCityRank(3, 5000, rank), ());
+  TEST_EQUAL(0.25, rank, ());
+
+  // test there is 0.5 rank for city with population = 50K and zoom = 3
+  TEST_EQUAL(true, table->GetCityRank(3, 50000, rank), ());
+  TEST_EQUAL(0.5, rank, ());
+
+  // test there is no rank for city with population = 5M and zoom = 3
+  TEST_EQUAL(false, table->GetCityRank(3, 50000000, rank), ());
+
+  // test zoom 5
+
+  // test there is no rank for city with population = 500 and zoom = 5
+  TEST_EQUAL(false, table->GetCityRank(5, 500, rank), ());
+
+  // test there is -1 rank for city with population = 5K and zoom = 5
+  TEST_EQUAL(true, table->GetCityRank(5, 5000, rank), ());
+  TEST_EQUAL(-1.0, rank, ());
+
+  // test there is no rank for city with population = 50K and zoom = 5
+  TEST_EQUAL(false, table->GetCityRank(5, 50000, rank), ());
+
+  // test zoom 6-15
+
+  // test there is 0.25 rank for city with population = 5K and zoom = 9
+  TEST_EQUAL(true, table->GetCityRank(9, 5000, rank), ());
+  TEST_EQUAL(0.25, rank, ());
+
+  // test there is 0.5 rank for city with population = 50K and zoom = 9
+  TEST_EQUAL(true, table->GetCityRank(9, 50000, rank), ());
+  TEST_EQUAL(0.5, rank, ());
+
+  // test zoom 16-19
+
+  // test there is 0.25 rank for city with population = 5K and zoom = 17
+  TEST_EQUAL(true, table->GetCityRank(17, 5000, rank), ());
+  TEST_EQUAL(0.25, rank, ());
+
+  // test there is 0.5 rank for city with population = 50K and zoom = 17
+  TEST_EQUAL(true, table->GetCityRank(17, 50000, rank), ());
+  TEST_EQUAL(0.5, rank, ());
+
+  // test there is no rank for city with population = 50M and zoom = 17
+  TEST_EQUAL(false, table->GetCityRank(17, 50000000, rank), ());
+}
+
+UNIT_TEST(TestCityRankTableParserInvalidString1)
+{
+  string s = "z-5{bad_format;}";
+
+  unique_ptr<drule::ICityRankTable> table = drule::GetCityRankTableFromString(s);
+  TEST(nullptr == table.get(), ());
+}
+
+UNIT_TEST(TestCityRankTableParserInvalidString2)
+{
+  string s = "z-5{0-1000:0.25;} zBadFormat{}";
+
+  unique_ptr<drule::ICityRankTable> table = drule::GetCityRankTableFromString(s);
+  TEST(nullptr == table.get(), ());
+}
+
+UNIT_TEST(TestCityRankTableWithEmptyPopulation1)
+{
+  string s = "z-5  {} z6-9 {;;;1000-10000:0.25;;;}\n"
+             "z10-{ -:3.5;;; }";
+
+  unique_ptr<drule::ICityRankTable> table = drule::GetCityRankTableFromString(s);
+  TEST(nullptr != table.get(), ());
+
+  double rank = 0.0;
+
+  // there is no rank for zoom 0-5
+  TEST_EQUAL(false, table->GetCityRank(3, 100000, rank), ());
+
+  // there is no rank for zoom 6-9 and population 100
+  TEST_EQUAL(false, table->GetCityRank(7, 100, rank), ());
+
+  // there is 0.25 rank for zoom 6-9 and population 5000
+  TEST_EQUAL(true, table->GetCityRank(7, 5000, rank), ());
+  TEST_EQUAL(0.25, rank, ());
+
+  // there is no rank for zoom 6-9 and population 15000
+  TEST_EQUAL(false, table->GetCityRank(7, 15000, rank), ());
+
+  // there is 3.5 rank for zoom 10+ and any population
+  TEST_EQUAL(true, table->GetCityRank(17, 1, rank), ());
+  TEST_EQUAL(3.5, rank, ());
+}
+
+UNIT_TEST(TestCityRankTableWithEmptyPopulation2)
+{
+  string s = "z0-20  {}";
+
+  unique_ptr<drule::ICityRankTable> table = drule::GetCityRankTableFromString(s);
+  TEST(nullptr != table.get(), ());
+
+  // there is no any rank
+  double rank = 0.0;
+  TEST_EQUAL(false, table->GetCityRank(3, 100000, rank), ());
+}
diff --git a/indexer/indexer_tests/indexer_tests.pro b/indexer/indexer_tests/indexer_tests.pro
index 667321487b..030f44f458 100644
--- a/indexer/indexer_tests/indexer_tests.pro
+++ b/indexer/indexer_tests/indexer_tests.pro
@@ -27,6 +27,7 @@ SOURCES += \
     cell_coverer_test.cpp \
     cell_id_test.cpp \
     checker_test.cpp \
+    city_rank_table_test.cpp \
     features_offsets_table_test.cpp \
     geometry_coding_test.cpp \
     geometry_serialization_test.cpp \