6 files changed, 57 insertions, 10 deletions

diff --git a/search/category_info.hpp b/search/category_info.hpp
new file mode 100644
index 0000000000..2b98ce2c66
--- /dev/null
+++ b/search/category_info.hpp
@@ -0,0 +1,19 @@
+#pragma once
+
+#include "../base/base.hpp"
+#include "../std/vector.hpp"
+
+namespace search
+{
+
+struct CategoryInfo
+{
+  static uint32_t const DO_NOT_SUGGEST = 255;
+
+  CategoryInfo() : m_prefixLengthToSuggest(DO_NOT_SUGGEST) {}
+
+  vector<uint32_t> m_types;
+  uint8_t m_prefixLengthToSuggest;
+};
+
+}  // namespace search
diff --git a/search/search.pro b/search/search.pro
index 5f78fe3bd9..c769bf6306 100644
--- a/search/search.pro
+++ b/search/search.pro
@@ -21,6 +21,7 @@ HEADERS += \
     search_trie_matching.hpp \
     approximate_string_match.hpp \
     feature_offset_match.hpp \
+    category_info.hpp \
 
 SOURCES += \
     search_engine.cpp \
diff --git a/search/search_engine.cpp b/search/search_engine.cpp
index d7329b52e9..45d56b9480 100644
--- a/search/search_engine.cpp
+++ b/search/search_engine.cpp
@@ -1,4 +1,5 @@
 #include "search_engine.hpp"
+#include "category_info.hpp"
 #include "result.hpp"
 #include "search_query.hpp"
 
@@ -7,6 +8,7 @@
 
 #include "../base/logging.hpp"
 
+#include "../std/algorithm.hpp"
 #include "../std/function.hpp"
 #include "../std/string.hpp"
 #include "../std/vector.hpp"
@@ -16,20 +18,21 @@ namespace search
 {
 
 Engine::Engine(IndexType const * pIndex, CategoriesHolder * pCategories)
-  : m_pIndex(pIndex)
+  : m_pIndex(pIndex), m_pCategories(new map<strings::UniString, CategoryInfo>())
 {
   for (CategoriesHolder::const_iterator it = pCategories->begin(); it != pCategories->end(); ++it)
   {
     for (size_t i = 0; i < it->m_synonyms.size(); ++i)
     {
-      vector<uint32_t> & types = m_categories[NormalizeAndSimplifyString(it->m_synonyms[i].m_name)];
-      types.insert(types.end(), it->m_types.begin(), it->m_types.end());
+      CategoryInfo & info = (*m_pCategories)[NormalizeAndSimplifyString(it->m_synonyms[i].m_name)];
+      info.m_types.insert(info.m_types.end(), it->m_types.begin(), it->m_types.end());
+      info.m_prefixLengthToSuggest = min(info.m_prefixLengthToSuggest,
+                                         it->m_synonyms[i].m_prefixLengthToSuggest);
     }
   }
-
   delete pCategories;
 
-  m_pQuery.reset(new Query(pIndex, &m_categories));
+  m_pQuery.reset(new Query(pIndex, m_pCategories.get()));
 }
 
 Engine::~Engine()
diff --git a/search/search_engine.hpp b/search/search_engine.hpp
index 3c5669ce66..6094868c06 100644
--- a/search/search_engine.hpp
+++ b/search/search_engine.hpp
@@ -19,6 +19,7 @@ class Index;
 namespace search
 {
 
+class CategoryInfo;
 class Query;
 class Result;
 
@@ -36,7 +37,7 @@ public:
 
 private:
   Index const * m_pIndex;
-  map<strings::UniString, vector<uint32_t> > m_categories;
+  scoped_ptr<map<strings::UniString, CategoryInfo> > m_pCategories;
   scoped_ptr<search::Query> m_pQuery;
 };
 
diff --git a/search/search_query.cpp b/search/search_query.cpp
index f01c20a2cd..6cd6de0e6b 100644
--- a/search/search_query.cpp
+++ b/search/search_query.cpp
@@ -1,9 +1,10 @@
 #include "search_query.hpp"
+#include "category_info.hpp"
 #include "feature_offset_match.hpp"
 #include "keyword_matcher.hpp"
 #include "latlon_match.hpp"
 #include "result.hpp"
-#include "../indexer/categories_holder.hpp"
+#include "search_common.hpp"
 #include "../indexer/feature_covering.hpp"
 #include "../indexer/features_vector.hpp"
 #include "../indexer/index.hpp"
@@ -137,6 +138,8 @@ void Query::Search(string const & query,
     }
   }
 
+  SuggestCategories();
+
   SearchFeatures();
 
   FlushResults(f);
@@ -264,8 +267,8 @@ void Query::SearchFeatures()
                 CategoriesMapT::const_iterator it = m_pCategories->find(m_tokens[i]);
                 if (it != m_pCategories->end())
                 {
-                  for (size_t j = 0; j < it->second.size(); ++j)
-                    tokens[i].push_back(FeatureTypeToString(it->second[j]));
+                  for (size_t j = 0; j < it->second.m_types.size(); ++j)
+                    tokens[i].push_back(FeatureTypeToString(it->second.m_types[j]));
                 }
               }
             }
@@ -281,4 +284,22 @@ void Query::SearchFeatures()
   }
 }
 
+void Query::SuggestCategories()
+{
+  // Category matching.
+  if (m_pCategories && !m_prefix.empty())
+  {
+    for (CategoriesMapT::const_iterator it = m_pCategories->begin();
+         it != m_pCategories->end(); ++it)
+    {
+      if (it->second.m_prefixLengthToSuggest <= m_prefix.size() &&
+          StartsWith(it->first.begin(), it->first.end(), m_prefix.begin(), m_prefix.end()))
+      {
+        string name = strings::ToUtf8(it->first);
+        AddResult(impl::IntermediateResult(name, name + " ", it->second.m_prefixLengthToSuggest));
+      }
+    }
+  }
+}
+
 }  // namespace search
diff --git a/search/search_query.hpp b/search/search_query.hpp
index 0ac8feb3c4..dadbb83e7b 100644
--- a/search/search_query.hpp
+++ b/search/search_query.hpp
@@ -17,13 +17,14 @@ class Index;
 namespace search
 {
 
+class CategoryInfo;
 class KeywordMatcher;
 namespace impl { class IntermediateResult; struct FeatureLoader; class BestNameFinder; }
 
 class Query
 {
 public:
-  typedef map<strings::UniString, vector<uint32_t> > CategoriesMapT;
+  typedef map<strings::UniString, CategoryInfo > CategoriesMapT;
 
   Query(Index const * pIndex, CategoriesMapT const * pCategories);
   ~Query();
@@ -45,6 +46,7 @@ private:
   void FlushResults(function<void (Result const &)> const & f);
   void UpdateViewportOffsets();
   void SearchFeatures();
+  void SuggestCategories();
   void GetBestMatchName(FeatureType const & feature, uint32_t & penalty, string & name);
 
   Index const * m_pIndex;