text: #include "reverse_geocoder.hpp"
  
  #include "search/mwm_context.hpp"
  
  #include "indexer/data_source.hpp"
  
  #include "indexer/fake_feature_ids.hpp"
  #include "indexer/feature.hpp"
  #include "indexer/feature_algo.hpp"
  #include "indexer/ftypes_matcher.hpp"
  #include "indexer/scales.hpp"
  #include "indexer/search_string_utils.hpp"
  
  #include "base/stl_helpers.hpp"
  
  #include <algorithm>
  #include <cstddef>
  #include <functional>
  #include <limits>
  
  using namespace std;
  
  namespace search
  {
  namespace
  {
  size_t constexpr kSimilarityThresholdPercent = 10;
  int constexpr kQueryScale = scales::GetUpperScale();
  /// Max number of tries (nearest houses with housenumber) to check when getting point address.
  size_t constexpr kMaxNumTriesToApproxAddress = 10;
  
  using AppendStreet = function<void(FeatureType & ft)>;
  using FillStreets =
      function<void(MwmSet::MwmHandle && handle, m2::RectD const & rect, AppendStreet && addStreet)>;
  
  m2::RectD GetLookupRect(m2::PointD const & center, double radiusM)
  {
    return MercatorBounds::RectByCenterXYAndSizeInMeters(center, radiusM);
  }
  
  void AddStreet(FeatureType & ft, m2::PointD const & center, bool includeSquaresAndSuburbs,
                 vector<ReverseGeocoder::Street> & streets)
  {
    bool const addAsStreet =
        ft.GetFeatureType() == feature::GEOM_LINE && ftypes::IsWayChecker::Instance()(ft);
    bool const isSquareOrSuburb =
        ftypes::IsSquareChecker::Instance()(ft) || ftypes::IsSuburbChecker::Instance()(ft);
    bool const addAsSquareOrSuburb = includeSquaresAndSuburbs && isSquareOrSuburb;
  
    if (!addAsStreet && !addAsSquareOrSuburb)
      return;
  
    string name;
    ft.GetReadableName(name);
    if (name.empty())
      return;
  
    streets.emplace_back(ft.GetID(), feature::GetMinDistanceMeters(ft, center), name);
  }
  
  // Following methods join only non-empty arguments in order with
  // commas.
  string Join(string const & s)
  {
    return s;
  }
  
  template <typename... Args>
  string Join(string const & s, Args &&... args)
  {
    auto const tail = Join(forward<Args>(args)...);
    if (s.empty())
      return tail;
    if (tail.empty())
      return s;
    return s + ", " + tail;
  }
  }  // namespace
  
  ReverseGeocoder::ReverseGeocoder(DataSource const & dataSource) : m_dataSource(dataSource) {}
  
  // static
  boost::optional<uint32_t> ReverseGeocoder::GetMatchedStreetIndex(std::string const & keyName,
                                                                   vector<Street> const & streets)
  {
    auto matchStreet = [&](bool ignoreStreetSynonyms) -> boost::optional<uint32_t> {
      // Find the exact match or the best match in kSimilarityTresholdPercent limit.
      uint32_t result;
      size_t minPercent = kSimilarityThresholdPercent + 1;
  
      auto const key = GetStreetNameAsKey(keyName, ignoreStreetSynonyms);
      for (auto const & street : streets)
      {
        strings::UniString const actual = GetStreetNameAsKey(street.m_name, ignoreStreetSynonyms);
  
        size_t const editDistance =
          strings::EditDistance(key.begin(), key.end(), actual.begin(), actual.end());
  
        if (editDistance == 0)
          return street.m_id.m_index;
  
        if (actual.empty())
          continue;
  
        size_t const percent = editDistance * 100 / actual.size();
        if (percent < minPercent)
        {
          result = street.m_id.m_index;
          minPercent = percent;
        }
      }
  
      if (minPercent <= kSimilarityThresholdPercent)
        return result;
      return {};
    };
  
    auto result = matchStreet(false /* ignoreStreetSynonyms */);
    if (result)
      return result;
    return matchStreet(true /* ignoreStreetSynonyms */);
  }
  
  // static
  void ReverseGeocoder::GetNearbyStreets(search::MwmContext & context, m2::PointD const & center,
                                         bool includeSquaresAndSuburbs, vector<Street> & streets)
  {
    m2::RectD const rect = GetLookupRect(center, kLookupRadiusM);
  
    auto const addStreet = [&](FeatureType & ft) {
      AddStreet(ft, center, includeSquaresAndSuburbs, streets);
    };
  
    context.ForEachFeature(rect, addStreet);
    sort(streets.begin(), streets.end(), base::LessBy(&Street::m_distanceMeters));
  }
  
  void ReverseGeocoder::GetNearbyStreets(MwmSet::MwmId const & id, m2::PointD const & center,
                                         vector<Street> & streets) const
  {
    MwmSet::MwmHandle mwmHandle = m_dataSource.GetMwmHandleById(id);
    if (mwmHandle.IsAlive())
    {
      search::MwmContext context(move(mwmHandle));
      GetNearbyStreets(context, center, true /* includeSquaresAndSuburbs */, streets);
    }
  }
  
  void ReverseGeocoder::GetNearbyStreets(FeatureType & ft, vector<Street> & streets) const
  {
    ASSERT(ft.GetID().IsValid(), ());
    GetNearbyStreets(ft.GetID().m_mwmId, feature::GetCenter(ft), streets);
  }
  
  void ReverseGeocoder::GetNearbyStreetsWaysOnly(MwmSet::MwmId const & id, m2::PointD const & center,
                                                 vector<Street> & streets) const
  {
    MwmSet::MwmHandle mwmHandle = m_dataSource.GetMwmHandleById(id);
    if (mwmHandle.IsAlive())
    {
      search::MwmContext context(move(mwmHandle));
      GetNearbyStreets(context, center, false /* includeSquaresAndSuburbs */, streets);
    }
  }
  
  string ReverseGeocoder::GetFeatureStreetName(FeatureType & ft) const
  {
    Address addr;
    HouseTable table(m_dataSource);
    GetNearbyAddress(table, FromFeature(ft, 0.0 /* distMeters */), false /* ignoreEdits */, addr);
    return addr.m_street.m_name;
  }
  
  string ReverseGeocoder::GetOriginalFeatureStreetName(FeatureID const & fid) const
  {
    Address addr;
    HouseTable table(m_dataSource);
    Building bld;
  
    m_dataSource.ReadFeature([&](FeatureType & ft) { bld = FromFeature(ft, 0.0 /* distMeters */); },
                             fid);
    GetNearbyAddress(table, bld, true /* ignoreEdits */, addr);
    return addr.m_street.m_name;
  }
  
  bool ReverseGeocoder::GetStreetByHouse(FeatureType & house, FeatureID & streetId) const
  {
    Address addr;
    HouseTable table(m_dataSource);
    if (GetNearbyAddress(table, FromFeature(house, 0.0 /* distMeters */), false /* ignoreEdits */, addr))
    {
      streetId = addr.m_street.m_id;
      return true;
    }
  
    return false;
  }
  
  void ReverseGeocoder::GetNearbyAddress(m2::PointD const & center, Address & addr) const
  {
    return GetNearbyAddress(center, kLookupRadiusM, addr);
  }
  
  void ReverseGeocoder::GetNearbyAddress(m2::PointD const & center, double maxDistanceM,
                                         Address & addr) const
  {
    vector<Building> buildings;
    GetNearbyBuildings(center, maxDistanceM, buildings);
  
    HouseTable table(m_dataSource);
    size_t triesCount = 0;
  
    for (auto const & b : buildings)
    {
      // It's quite enough to analize nearest kMaxNumTriesToApproxAddress houses for the exact nearby address.
      // When we can't guarantee suitable address for the point with distant houses.
      if (GetNearbyAddress(table, b, false /* ignoreEdits */, addr) ||
          (++triesCount == kMaxNumTriesToApproxAddress))
        break;
    }
  }
  
  bool ReverseGeocoder::GetExactAddress(FeatureType & ft, Address & addr) const
  {
    if (ft.GetHouseNumber().empty())
      return false;
    HouseTable table(m_dataSource);
    return GetNearbyAddress(table, FromFeature(ft, 0.0 /* distMeters */), false /* ignoreEdits */,
                            addr);
  }
  
  bool ReverseGeocoder::GetNearbyAddress(HouseTable & table, Building const & bld, bool ignoreEdits,
                                         Address & addr) const
  {
    string street;
    if (!ignoreEdits && osm::Editor::Instance().GetEditedFeatureStreet(bld.m_id, street))
    {
      addr.m_building = bld;
      addr.m_street.m_name = street;
      return true;
    }
  
    uint32_t streetId;
    HouseToStreetTable::StreetIdType type;
    if (!table.Get(bld.m_id, type, streetId))
      return false;
  
    switch (type)
    {
    case HouseToStreetTable::StreetIdType::Index:
    {
      vector<Street> streets;
      // Get streets without squares and suburbs for backward compatibility with data.
      GetNearbyStreetsWaysOnly(bld.m_id.m_mwmId, bld.m_center, streets);
      if (streetId < streets.size())
      {
        addr.m_building = bld;
        addr.m_street = streets[streetId];
        return true;
      }
      LOG(LWARNING, ("Out of bound street index", streetId, "for", bld.m_id));
      return false;
    }
    case HouseToStreetTable::StreetIdType::FeatureId:
    {
      FeatureID streetFeature(bld.m_id.m_mwmId, streetId);
      string streetName;
      double distance;
      m_dataSource.ReadFeature(
          [&](FeatureType & ft) {
            ft.GetReadableName(streetName);
            distance = feature::GetMinDistanceMeters(ft, bld.m_center);
          },
          streetFeature);
      CHECK(!streetName.empty(), ());
      addr.m_building = bld;
      addr.m_street = Street(streetFeature, distance, streetName);
      return true;
    }
    case HouseToStreetTable::StreetIdType::None:
    {
      // Prior call of table.Get() is expected to fail.
      UNREACHABLE();
    }
    }
    UNREACHABLE();
  }
  
  void ReverseGeocoder::GetNearbyBuildings(m2::PointD const & center, double radius,
                                           vector<Building> & buildings) const
  {
    auto const addBuilding = [&](FeatureType & ft) {
      auto const distance = feature::GetMinDistanceMeters(ft, center);
      if (!ft.GetHouseNumber().empty() && distance <= radius)
        buildings.push_back(FromFeature(ft, distance));
    };
  
    auto const stop = [&]() { return buildings.size() >= kMaxNumTriesToApproxAddress; };
  
    m_dataSource.ForClosestToPoint(addBuilding, stop, center, radius, kQueryScale);
    sort(buildings.begin(), buildings.end(), base::LessBy(&Building::m_distanceMeters));
  }
  
  // static
  ReverseGeocoder::Building ReverseGeocoder::FromFeature(FeatureType & ft, double distMeters)
  {
    return { ft.GetID(), distMeters, ft.GetHouseNumber(), feature::GetCenter(ft) };
  }
  
  bool ReverseGeocoder::HouseTable::Get(FeatureID const & fid,
                                        HouseToStreetTable::StreetIdType & type,
                                        uint32_t & streetIndex)
  {
    if (feature::FakeFeatureIds::IsEditorCreatedFeature(fid.m_index))
      return false;
  
    if (!m_table || m_handle.GetId() != fid.m_mwmId)
    {
      m_handle = m_dataSource.GetMwmHandleById(fid.m_mwmId);
      if (!m_handle.IsAlive())
      {
        LOG(LWARNING, ("MWM", fid, "is dead"));
        return false;
      }
      m_table = search::HouseToStreetTable::Load(*m_handle.GetValue<MwmValue>());
    }
  
    type = m_table->GetStreetIdType();
    return m_table->Get(fid.m_index, streetIndex);
  }
  
  string ReverseGeocoder::Address::FormatAddress() const
  {
    // Check whether we can format address according to the query type
    // and actual address distance.
  
    // TODO (@m, @y): we can add "Near" prefix here in future according
    // to the distance.
    if (m_building.m_distanceMeters > 200.0)
      return {};
  
    return Join(m_street.m_name, m_building.m_name);
  }
  
  string DebugPrint(ReverseGeocoder::Object const & obj)
  {
    return obj.m_name;
  }
  
  string DebugPrint(ReverseGeocoder::Address const & addr)
  {
    return "{ " + DebugPrint(addr.m_building) + ", " + DebugPrint(addr.m_street) + " }";
  }
  
  } // namespace search
  