Implementation index for altitude data with the help of succinct strutures.

4 files changed, 135 insertions, 59 deletions

diff --git a/indexer/altitude_loader.cpp b/indexer/altitude_loader.cpp
index 66fa124bf8..21c25ac9b0 100644
--- a/indexer/altitude_loader.cpp
+++ b/indexer/altitude_loader.cpp
@@ -1,49 +1,110 @@
 #include "indexer/altitude_loader.hpp"
 
+#include "coding/reader.hpp"
+
 #include "base/logging.hpp"
 #include "base/stl_helpers.hpp"
+#include "base/thread.hpp"
 
 #include "defines.hpp"
 
+#include "3party/succinct/mapper.hpp"
+
+namespace
+{
+void ReadBuffer(ReaderSource<FilesContainerR::TReader> & rs, vector<char> & buf)
+{
+  uint32_t bufSz = 0;
+  rs.Read(&bufSz, sizeof(bufSz));
+  if (bufSz > rs.Size() + rs.Pos())
+  {
+    ASSERT(false, ());
+    return;
+  }
+  buf.clear();
+  buf.resize(bufSz);
+  rs.Read(buf.data(), bufSz);
+}
+} // namespace
+
 namespace feature
 {
 AltitudeLoader::AltitudeLoader(MwmValue const * mwmValue)
+  : reader(mwmValue->m_cont.GetReader(ALTITUDE_FILE_TAG)), m_altitudeInfoOffset(0), m_minAltitude(kInvalidAltitude)
 {
   if (!mwmValue || mwmValue->GetHeader().GetFormat() < version::Format::v8 )
     return;
 
   try
   {
-    m_idx = make_unique<DDVector<TAltitudeIndexEntry, FilesContainerR::TReader>>
-        (mwmValue->m_cont.GetReader(ALTITUDE_FILE_TAG));
+    ReaderSource<FilesContainerR::TReader> rs(reader);
+    DeserializeHeader(rs);
+
+    // Reading rs_bit_vector with altitude availability information.
+    ReadBuffer(rs, m_altitudeAvailabilitBuf);
+    m_altitudeAvailability = make_unique<succinct::rs_bit_vector>();
+    succinct::mapper::map(*m_altitudeAvailability, m_altitudeAvailabilitBuf.data());
+
+    // Reading table with altitude ofsets for features.
+    ReadBuffer(rs, m_featureTableBuf);
+    m_featureTable = make_unique<succinct::elias_fano>();
+    succinct::mapper::map(*m_featureTable, m_featureTableBuf.data());
   }
-  catch (Reader::OpenException const &)
+  catch (Reader::OpenException const & e)
   {
-    LOG(LINFO, ("MWM does not contain", ALTITUDE_FILE_TAG, "section."));
+    m_altitudeInfoOffset = 0;
+    m_minAltitude = kInvalidAltitude;
+    LOG(LINFO, ("MWM does not contain", ALTITUDE_FILE_TAG, "section.", e.Msg()));
   }
 }
 
-Altitudes AltitudeLoader::GetAltitudes(uint32_t featureId) const
+void AltitudeLoader::DeserializeHeader(ReaderSource<FilesContainerR::TReader> & rs)
 {
-  if (!m_idx || m_idx->size() == 0)
-    return Altitudes();
-
-  auto it = lower_bound(m_idx->begin(), m_idx->end(),
-                        TAltitudeIndexEntry{static_cast<uint32_t>(featureId), 0, 0},
-                        my::LessBy(&TAltitudeIndexEntry::featureId));
+  TAltitudeSectionVersion version;
+  rs.Read(&version, sizeof(version));
+  LOG(LINFO, ("Reading version =", version));
+  rs.Read(&m_minAltitude, sizeof(m_minAltitude));
+  LOG(LINFO, ("Reading m_minAltitude =", m_minAltitude));
+  rs.Read(&m_altitudeInfoOffset, sizeof(m_altitudeInfoOffset));
+  LOG(LINFO, ("Reading m_altitudeInfoOffset =", m_altitudeInfoOffset));
+}
 
-  if (it == m_idx->end())
-    return Altitudes();
+TAltitudes AltitudeLoader::GetAltitude(uint32_t featureId, size_t pointCount) const
+{
+  if (m_altitudeInfoOffset == 0)
+  {
+    // The version of mwm is less then version::Format::v8 or there's no altitude section in mwm.
+    return TAltitudes();
+  }
 
-  if (featureId != it->featureId)
+  if (!(*m_altitudeAvailability)[featureId])
   {
-    ASSERT(false, ());
-    return Altitudes();
+    LOG(LINFO, ("Feature featureId =", featureId, "does not contain any altitude information."));
+    return TAltitudes();
   }
 
-  if (it->beginAlt == kInvalidAltitude || it->endAlt == kInvalidAltitude)
-    return Altitudes();
+  uint64_t const r = m_altitudeAvailability->rank(featureId);
+  CHECK_LESS(r, m_altitudeAvailability->size(), (featureId));
+  uint64_t const offset = m_featureTable->select(r);
+  CHECK_LESS(offset, m_featureTable->size(), (featureId));
+
+  uint64_t const m_altitudeInfoOffsetInSection = m_altitudeInfoOffset + offset;
+  CHECK_LESS(m_altitudeInfoOffsetInSection, reader.Size(), ());
 
-  return Altitudes(it->beginAlt, it->endAlt);
+  try
+  {
+    Altitude a;
+    ReaderSource<FilesContainerR::TReader> rs(reader);
+    rs.Skip(m_altitudeInfoOffsetInSection);
+    a.Deserialize(m_minAltitude, pointCount, rs);
+
+    // @TODO(bykoianko) Considers using move semantic for returned value here.
+    return a.GetAltitudes();
+  }
+  catch (Reader::OpenException const & e)
+  {
+    LOG(LERROR, ("Error while getting mwm data", e.Msg()));
+    return TAltitudes();
+  }
 }
 } // namespace feature
diff --git a/indexer/altitude_loader.hpp b/indexer/altitude_loader.hpp
index d792b28467..d7a27785de 100644
--- a/indexer/altitude_loader.hpp
+++ b/indexer/altitude_loader.hpp
@@ -2,24 +2,32 @@
 #include "indexer/feature_altitude.hpp"
 #include "indexer/index.hpp"
 
-#include "coding/dd_vector.hpp"
+#include "3party/succinct/rs_bit_vector.hpp"
+
+#include "std/unique_ptr.hpp"
+#include "std/vector.hpp"
 
 namespace feature
 {
+using TAltitudeSectionVersion = uint16_t;
+using TAltitudeSectionOffset = uint32_t;
+
 class AltitudeLoader
 {
 public:
   AltitudeLoader(MwmValue const * mwmValue);
-  Altitudes GetAltitudes(uint32_t featureId) const;
+
+  TAltitudes GetAltitude(uint32_t featureId, size_t pointCount) const;
 
 private:
-  struct TAltitudeIndexEntry
-  {
-    uint32_t featureId;
-    feature::TAltitude beginAlt;
-    feature::TAltitude endAlt;
-  };
+  void DeserializeHeader(ReaderSource<FilesContainerR::TReader> & rs);
 
-  unique_ptr<DDVector<TAltitudeIndexEntry, FilesContainerR::TReader>> m_idx;
+  vector<char> m_altitudeAvailabilitBuf;
+  vector<char> m_featureTableBuf;
+  unique_ptr<succinct::rs_bit_vector> m_altitudeAvailability;
+  unique_ptr<succinct::elias_fano> m_featureTable;
+  FilesContainerR::TReader reader;
+  TAltitudeSectionOffset m_altitudeInfoOffset;
+  TAltitude m_minAltitude;
 };
 } // namespace feature
diff --git a/indexer/feature.hpp b/indexer/feature.hpp
index fe5f30c206..4ecbb79357 100644
--- a/indexer/feature.hpp
+++ b/indexer/feature.hpp
@@ -362,10 +362,6 @@ private:
   mutable points_t m_points, m_triangles;
   mutable feature::Metadata m_metadata;
 
-  // @TODO |m_altitudes| should be exchanged with vector<TAltitude>.
-  // If the vector is empty no altitude information is available for this feature.
-  feature::Altitudes m_altitudes;
-
   mutable bool m_header2Parsed = false;
   mutable bool m_pointsParsed = false;
   mutable bool m_trianglesParsed = false;
diff --git a/indexer/feature_altitude.hpp b/indexer/feature_altitude.hpp
index 4d59135342..84582fac7c 100644
--- a/indexer/feature_altitude.hpp
+++ b/indexer/feature_altitude.hpp
@@ -11,44 +11,55 @@ using TAltitude = int16_t;
 using TAltitudes = vector<feature::TAltitude>;
 TAltitude constexpr kInvalidAltitude = numeric_limits<TAltitude>::min();
 
-struct Altitudes
-{
-  Altitudes() = default;
-  Altitudes(TAltitude b, TAltitude e) : begin(b), end(e) {}
-
-  TAltitude begin = kInvalidAltitude;
-  TAltitude end = kInvalidAltitude;
-};
-
 class Altitude
 {
 public:
   Altitude() = default;
-  Altitude(uint32_t featureId, Altitudes const & altitudes)
-    : m_featureId(featureId), m_altitudes(altitudes)
-  {
-  }
+  Altitude(TAltitudes const & altitudes) : m_pointAlt(altitudes) {}
 
   template <class TSink>
-  void Serialize(TSink & sink) const
+  void Serialize(TAltitude minAltitude, TSink & sink) const
   {
-    sink.Write(&m_featureId, sizeof(uint32_t));
-    sink.Write(&m_altitudes.begin, sizeof(TAltitude));
-    sink.Write(&m_altitudes.end, sizeof(TAltitude));
+    CHECK(!m_pointAlt.empty(), ());
+
+    TAltitude prevPntAltitude = minAltitude;
+    for (size_t i = 0; i < m_pointAlt.size(); ++i)
+    {
+      WriteVarInt(sink, static_cast<int32_t>(static_cast<int32_t>(m_pointAlt[i] - prevPntAltitude)));
+      prevPntAltitude = m_pointAlt[i];
+    }
   }
 
-  /// @TODO template <class TSource> void Deserialize(TSource & src) should be implement here.
-  /// But now for test purposes deserialization is done with DDVector construction.
+  template <class TSource>
+  void Deserialize(TAltitude minAltitude, size_t pointCount, TSource & src)
+  {
+    m_pointAlt.clear();
+    if (pointCount == 0)
+    {
+      ASSERT(false, ());
+      return;
+    }
+
+    m_pointAlt.resize(pointCount);
+    TAltitude prevPntAltitude = minAltitude;
+    for (size_t i = 0; i < pointCount; ++i)
+    {
+      m_pointAlt[i] = static_cast<TAltitude>(ReadVarInt<int32_t>(src) + prevPntAltitude);
+      prevPntAltitude = m_pointAlt[i];
+    }
+  }
 
-  uint32_t GetFeatureId() const { return m_featureId; }
-  Altitudes const & GetAltitudes() const { return m_altitudes; }
+  TAltitudes GetAltitudes() const
+  {
+    return m_pointAlt;
+  }
 
 private:
-  /// @TODO Note. Feature id is located here because there's no index for altitudes.
-  /// There's only pairs sorted by feature id. Before merging to master some index has to be
-  /// implemented.
-  /// Don't forget to remove |m_featureId|.
-  uint32_t m_featureId = 0;
-  Altitudes m_altitudes;
+  /// \note |m_pointAlt| is a vector of feature point altitudes. There's two posibilities:
+  /// * |m_pointAlt| is empty. It means no altitude information defines.
+  /// * size of |m_pointAlt| is equal to feature point number. In that case every item of
+  /// |m_pointAlt| defines altitude in meters for every feature point. If altitude is not defined
+  ///  for some feature point corresponding vector items are equel to |kInvalidAltitude|
+  TAltitudes m_pointAlt;
 };
 }  // namespace feature