Support old format 1.01 (April 2011).

12 files changed, 645 insertions, 22 deletions

diff --git a/indexer/data_factory.cpp b/indexer/data_factory.cpp
index 1358c82f8d..73509ff2f1 100644
--- a/indexer/data_factory.cpp
+++ b/indexer/data_factory.cpp
@@ -2,6 +2,7 @@
 
 #include "data_factory.hpp"
 #include "interval_index.hpp"
+#include "old/interval_index_101.hpp"
 
 #include "../defines.hpp"
 
@@ -11,12 +12,47 @@
 #include "../base/start_mem_debug.hpp"
 
 
+namespace
+{
+  void LoadHeader(FilesContainerR const & cont, feature::DataHeader & header)
+  {
+    ModelReaderPtr r = cont.GetReader(HEADER_FILE_TAG);
+
+    if (cont.IsReaderExist(VERSION_FILE_TAG))
+      header.Load(r);
+    else
+      header.LoadVer1(r);
+  }
+}
+
 void IndexFactory::Load(FilesContainerR const & cont)
 {
-  m_header.Load(cont.GetReader(HEADER_FILE_TAG));
+  LoadHeader(cont, m_header);
 }
 
 IntervalIndexIFace * IndexFactory::CreateIndex(ModelReaderPtr reader)
 {
-  return new IntervalIndex<ModelReaderPtr>(reader);
+  using namespace feature;
+
+  IntervalIndexIFace * p;
+
+  switch (m_header.GetVersion())
+  {
+  case DataHeader::v1:
+    p = new old_101::IntervalIndex<uint32_t, ModelReaderPtr>(reader);
+    break;
+
+  default:
+    p = new IntervalIndex<ModelReaderPtr>(reader);;
+    break;
+  }
+
+  return p;
+}
+
+m2::RectD GetMapBounds(FilesContainerR const & cont)
+{
+  feature::DataHeader header;
+  LoadHeader(cont, header);
+  return header.GetBounds();
 }
diff --git a/indexer/data_factory.hpp b/indexer/data_factory.hpp
index 79e83229bf..ac171ec673 100644
--- a/indexer/data_factory.hpp
+++ b/indexer/data_factory.hpp
@@ -18,3 +18,5 @@ public:
 
   IntervalIndexIFace * CreateIndex(ModelReaderPtr reader);
 };
+
+m2::RectD GetMapBounds(FilesContainerR const & cont);
diff --git a/indexer/data_header.cpp b/indexer/data_header.cpp
index c461fa1fb3..0c193981d2 100644
--- a/indexer/data_header.cpp
+++ b/indexer/data_header.cpp
@@ -33,16 +33,13 @@ namespace feature
 
   pair<int, int> DataHeader::GetScaleRange() const
   {
-    pair<int, int> ret(0, scales::GetUpperScale());
+    int const worldB = scales::GetUpperWorldScale();
+    int const countryB = scales::GetUpperScale();
 
-    int const bound = scales::GetUpperWorldScale();
-
-    if (m_scales.front() > bound)
-      ret.first = bound+1;
-    if (m_scales.back() <= bound)
-      ret.second = bound;
-
-    return ret;
+    if (m_scales.back() == countryB)
+      return make_pair(worldB + 1, countryB);
+    else
+      return make_pair(0, worldB);
   }
 
   void DataHeader::Save(FileWriter & w) const
@@ -70,5 +67,21 @@ namespace feature
     m_bounds.second = ReadPrimitiveFromSource<int64_t>(src);
 
     src.Read(m_scales.data(), m_scales.size());
+
+    m_ver = v2;
+  }
+
+  void DataHeader::LoadVer1(ModelReaderPtr const & r)
+  {
+    ReaderSource<ModelReaderPtr> src(r);
+    int64_t const base = ReadPrimitiveFromSource<int64_t>(src);
+    m_codingParams = serial::CodingParams(POINT_COORD_BITS, base);
+
+    m_bounds.first = ReadVarInt<int64_t>(src) + base;
+    m_bounds.second = ReadVarInt<int64_t>(src) + base;
+
+    src.Read(m_scales.data(), m_scales.size());
+
+    m_ver = v1;
   }
 }
diff --git a/indexer/data_header.hpp b/indexer/data_header.hpp
index 434747a1ef..20680864f2 100644
--- a/indexer/data_header.hpp
+++ b/indexer/data_header.hpp
@@ -40,6 +40,17 @@ namespace feature
     //@{
     void Save(FileWriter & w) const;
     void Load(ModelReaderPtr const & r);
+
+    void LoadVer1(ModelReaderPtr const & r);
     //@}
+
+    enum Version {
+      v1,     // April 2011
+      v2      // September 2011
+    };
+    inline Version GetVersion() const { return m_ver; }
+
+  private:
+    Version m_ver;
   };
 }
diff --git a/indexer/feature.hpp b/indexer/feature.hpp
index ff34c711d6..7095f2f214 100644
--- a/indexer/feature.hpp
+++ b/indexer/feature.hpp
@@ -17,6 +17,12 @@ namespace feature
   class LoaderCurrent;
 }
 
+namespace old_101 { namespace feature
+{
+  class LoaderImpl;
+}}
+
+
 /// Base feature class for storing common data (without geometry).
 class FeatureBase
 {
@@ -138,6 +144,7 @@ protected:
   mutable bool m_bTypesParsed, m_bCommonParsed;
 
   friend class feature::LoaderCurrent;
+  friend class old_101::feature::LoaderImpl;
 };
 
 /// Working feature class with geometry.
@@ -269,4 +276,15 @@ private:
   mutable inner_geom_stat_t m_InnerStats;
 
   friend class feature::LoaderCurrent;
+  friend class old_101::feature::LoaderImpl;
 };
+
+namespace feature
+{
+  template <class TCont>
+  void CalcRect(TCont const & points, m2::RectD & rect)
+  {
+    for (size_t i = 0; i < points.size(); ++i)
+      rect.Add(points[i]);
+  }
+}
diff --git a/indexer/feature_impl.hpp b/indexer/feature_impl.hpp
index ff5d781c7a..75c41bf034 100644
--- a/indexer/feature_impl.hpp
+++ b/indexer/feature_impl.hpp
@@ -39,11 +39,4 @@ namespace feature
     str += arrChar[ind];
     return str;
   }
-
-  template <class TCont>
-  void CalcRect(TCont const & points, m2::RectD & rect)
-  {
-    for (size_t i = 0; i < points.size(); ++i)
-      rect.Add(points[i]);
-  }
 }
diff --git a/indexer/feature_loader.cpp b/indexer/feature_loader.cpp
index 17c9357bf8..88dd5262cb 100644
--- a/indexer/feature_loader.cpp
+++ b/indexer/feature_loader.cpp
@@ -2,13 +2,10 @@
 
 #include "feature_loader.hpp"
 #include "feature.hpp"
-#include "feature_impl.hpp"
 #include "scales.hpp"
 #include "geometry_serialization.hpp"
 #include "classificator.hpp"
 
-#include "../defines.hpp" // just for file extensions
-
 #include "../geometry/pointu_to_uint64.hpp"
 
 #include "../coding/byte_stream.hpp"
diff --git a/indexer/feature_loader_base.cpp b/indexer/feature_loader_base.cpp
index ce289297f3..63e66522d6 100644
--- a/indexer/feature_loader_base.cpp
+++ b/indexer/feature_loader_base.cpp
@@ -4,6 +4,8 @@
 #include "feature_loader.hpp"
 #include "feature_impl.hpp"
 
+#include "old/feature_loader_101.hpp"
+
 #include "../defines.hpp"
 
 #include "../coding/byte_stream.hpp"
@@ -40,7 +42,20 @@ SharedLoadInfo::ReaderT SharedLoadInfo::GetTrianglesReader(int ind) const
 
 LoaderBase * SharedLoadInfo::CreateLoader() const
 {
-  return new LoaderCurrent(*this);
+  LoaderBase * p;
+
+  switch (m_header.GetVersion())
+  {
+  case DataHeader::v1:
+    p = new old_101::feature::LoaderImpl(*this);
+    break;
+
+  default:
+    p = new LoaderCurrent(*this);
+    break;
+  }
+
+  return p;
 }
 
 
diff --git a/indexer/indexer.pro b/indexer/indexer.pro
index ec1dd9ab10..8b3449f57a 100644
--- a/indexer/indexer.pro
+++ b/indexer/indexer.pro
@@ -33,6 +33,7 @@ SOURCES += \
     types_mapping.cpp \
     search_index_builder.cpp \
     data_factory.cpp \
+    old/feature_loader_101.cpp \
     coding_params.cpp \
     feature_loader_base.cpp \
     feature_loader.cpp \
@@ -74,6 +75,8 @@ HEADERS += \
     search_index_builder.hpp \
     interval_index_iface.hpp \
     data_factory.hpp \
+    old/interval_index_101.hpp \
+    old/feature_loader_101.hpp \
     coding_params.hpp \
     feature_loader_base.hpp \
     feature_loader.hpp \
diff --git a/indexer/old/feature_loader_101.cpp b/indexer/old/feature_loader_101.cpp
new file mode 100644
index 0000000000..c886c40684
--- /dev/null
+++ b/indexer/old/feature_loader_101.cpp
@@ -0,0 +1,332 @@
+#include "../../base/SRC_FIRST.hpp"
+
+#include "feature_loader_101.hpp"
+
+#include "../feature.hpp"
+#include "../scales.hpp"
+#include "../geometry_serialization.hpp"
+#include "../coding_params.hpp"
+
+#include "../../coding/byte_stream.hpp"
+
+#include "../../base/start_mem_debug.hpp"
+
+
+namespace old_101 { namespace feature {
+
+
+uint8_t LoaderImpl::GetHeader()
+{
+  uint8_t const h = Header();
+
+  uint8_t header = static_cast<uint8_t>((h & 7) - 1);
+
+  if (h & HEADER_HAS_NAME)
+    header |= ::feature::HEADER_HAS_NAME;
+
+  if (h & HEADER_HAS_LAYER)
+    header |= ::feature::HEADER_HAS_LAYER;
+
+  if (h & HEADER_IS_LINE)
+    header |= ::feature::HEADER_GEOM_LINE;
+
+  if (h & HEADER_IS_AREA)
+    header |= ::feature::HEADER_GEOM_AREA;
+
+  return header;
+}
+
+void LoaderImpl::ParseTypes()
+{
+  ArrayByteSource source(DataPtr() + m_TypesOffset);
+
+  size_t const count = m_pF->GetTypesCount();
+  for (size_t i = 0; i < count; ++i)
+    m_pF->m_Types[i] = ReadVarUint<uint32_t>(source);
+
+  m_CommonOffset = CalcOffset(source);
+}
+
+void LoaderImpl::ParseCommon()
+{
+  ArrayByteSource source(DataPtr() + m_CommonOffset);
+
+  uint8_t const h = Header();
+
+  if (h & HEADER_HAS_LAYER)
+    m_pF->m_Params.layer = ReadVarInt<int32_t>(source);
+
+  if (h & HEADER_HAS_NAME)
+  {
+    string name;
+    name.resize(ReadVarUint<uint32_t>(source) + 1);
+    source.Read(&name[0], name.size());
+    m_pF->m_Params.name.AddString(0, name);
+  }
+
+  if (h & HEADER_HAS_POINT)
+  {
+    CoordPointT const center = Int64ToPoint(
+          ReadVarInt<int64_t>(source) + m_Info.GetCodingParams().GetBasePointInt64(), POINT_COORD_BITS);
+
+    m_pF->m_Center = m2::PointD(center.first, center.second);
+    m_pF->m_LimitRect.Add(m_pF->m_Center);
+  }
+
+  m_Header2Offset = CalcOffset(source);
+}
+
+namespace
+{
+    uint32_t const kInvalidOffset = uint32_t(-1);
+}
+
+int LoaderImpl::GetScaleIndex(int scale) const
+{
+  int const count = m_Info.GetScalesCount();
+  if (scale == -1) return count-1;
+
+  for (int i = 0; i < count; ++i)
+    if (scale <= m_Info.GetScale(i))
+      return i;
+  return -1;
+}
+
+int LoaderImpl::GetScaleIndex(int scale, offsets_t const & offsets) const
+{
+  if (scale == -1)
+  {
+    // Choose the best geometry for the last visible scale.
+    int i = offsets.size()-1;
+    while (i >= 0 && offsets[i] == kInvalidOffset) --i;
+    if (i >= 0)
+      return i;
+    else
+      CHECK ( false, ("Feature should have any geometry ...") );
+  }
+  else
+  {
+    for (size_t i = 0; i < m_Info.GetScalesCount(); ++i)
+      if (scale <= m_Info.GetScale(i))
+      {
+        if (offsets[i] != kInvalidOffset)
+          return i;
+        else
+          break;
+      }
+  }
+
+  return -1;
+}
+
+namespace
+{
+  class BitSource
+  {
+    char const * m_ptr;
+    uint8_t m_pos;
+
+  public:
+    BitSource(char const * p) : m_ptr(p), m_pos(0) {}
+
+    uint8_t Read(uint8_t count)
+    {
+      ASSERT_LESS ( count, 9, () );
+
+      uint8_t v = *m_ptr;
+      v >>= m_pos;
+      v &= ((1 << count) - 1);
+
+      m_pos += count;
+      if (m_pos >= 8)
+      {
+        ASSERT_EQUAL ( m_pos, 8, () );
+        ++m_ptr;
+        m_pos = 0;
+      }
+
+      return v;
+    }
+
+    char const * RoundPtr()
+    {
+      if (m_pos > 0)
+      {
+        ++m_ptr;
+        m_pos = 0;
+      }
+      return m_ptr;
+    }
+  };
+
+  template <class TSource> uint8_t ReadByte(TSource & src)
+  {
+    return ReadPrimitiveFromSource<uint8_t>(src);
+  }
+}
+
+void LoaderImpl::ParseHeader2()
+{
+  uint8_t ptsCount, ptsMask, trgCount, trgMask;
+
+  uint8_t const commonH = Header();
+  BitSource bitSource(DataPtr() + m_Header2Offset);
+
+  if (commonH & HEADER_IS_LINE)
+  {
+    ptsCount = bitSource.Read(4);
+    if (ptsCount == 0)
+      ptsMask = bitSource.Read(4);
+    else
+    {
+      ASSERT_GREATER ( ptsCount, 1, () );
+    }
+  }
+
+  if (commonH & HEADER_IS_AREA)
+  {
+    trgCount = bitSource.Read(4);
+    if (trgCount == 0)
+      trgMask = bitSource.Read(4);
+  }
+
+  ArrayByteSource src(bitSource.RoundPtr());
+
+  if (commonH & HEADER_IS_LINE)
+  {
+    if (ptsCount > 0)
+    {
+      int const count = (ptsCount - 2 + 3) / 4;
+      ASSERT_LESS ( count, 4, () );
+
+      for (int i = 0; i < count; ++i)
+      {
+        uint32_t mask = ReadByte(src);
+        m_ptsSimpMask += (mask << (i << 3));
+      }
+
+      char const * start = static_cast<char const *>(src.Ptr());
+
+      src = ArrayByteSource(serial::LoadInnerPath(
+                              src.Ptr(), ptsCount, m_Info.GetCodingParams(), m_pF->m_Points));
+
+      m_pF->m_InnerStats.m_Points = static_cast<char const *>(src.Ptr()) - start;
+    }
+    else
+      ReadOffsets(src, ptsMask, m_ptsOffsets);
+  }
+
+  if (commonH & HEADER_IS_AREA)
+  {
+    if (trgCount > 0)
+    {
+      trgCount += 2;
+
+      char const * start = static_cast<char const *>(src.Ptr());
+
+      FeatureType::points_t points;
+      src = ArrayByteSource(serial::LoadInnerTriangles(
+                              src.Ptr(), trgCount, m_Info.GetCodingParams(), points));
+
+      m_pF->m_InnerStats.m_Strips = static_cast<char const *>(src.Ptr()) - start;
+
+      for (uint8_t i = 2; i < trgCount; ++i)
+      {
+        m_pF->m_Triangles.push_back(points[i-2]);
+        m_pF->m_Triangles.push_back(points[i-1]);
+        m_pF->m_Triangles.push_back(points[i]);
+      }
+    }
+    else
+      ReadOffsets(src, trgMask, m_trgOffsets);
+  }
+
+  m_pF->m_InnerStats.m_Size = static_cast<char const *>(src.Ptr()) - DataPtr();
+}
+
+uint32_t LoaderImpl::ParseGeometry(int scale)
+{
+  uint32_t sz = 0;
+  if (Header() & HEADER_IS_LINE)
+  {
+    if (m_pF->m_Points.empty())
+    {
+      // outer geometry
+      int const ind = GetScaleIndex(scale, m_ptsOffsets);
+      if (ind != -1)
+      {
+        ReaderSource<FilesContainerR::ReaderT> src(m_Info.GetGeometryReader(ind));
+        src.Skip(m_ptsOffsets[ind]);
+        serial::LoadOuterPath(src, m_Info.GetCodingParams(), m_pF->m_Points);
+
+        sz = static_cast<uint32_t>(src.Pos() - m_ptsOffsets[ind]);
+      }
+    }
+    else
+    {
+      // filter inner geometry
+
+      size_t const count = m_pF->m_Points.size();
+      FeatureType::points_t points;
+      points.reserve(count);
+
+      int const scaleIndex = GetScaleIndex(scale);
+      ASSERT_LESS ( scaleIndex, m_Info.GetScalesCount(), () );
+
+      points.push_back(m_pF->m_Points.front());
+      for (size_t i = 1; i < count-1; ++i)
+      {
+        // check for point visibility in needed scaleIndex
+        if (((m_ptsSimpMask >> (2*(i-1))) & 0x3) <= scaleIndex)
+          points.push_back(m_pF->m_Points[i]);
+      }
+      points.push_back(m_pF->m_Points.back());
+
+      m_pF->m_Points.swap(points);
+    }
+
+    ::feature::CalcRect(m_pF->m_Points, m_pF->m_LimitRect);
+  }
+
+  return sz;
+}
+
+uint32_t LoaderImpl::ParseTriangles(int scale)
+{
+  uint32_t sz = 0;
+  if (Header() & HEADER_IS_AREA)
+  {
+    if (m_pF->m_Triangles.empty())
+    {
+      uint32_t const ind = GetScaleIndex(scale, m_trgOffsets);
+      if (ind != -1)
+      {
+        ReaderSource<FilesContainerR::ReaderT> src(m_Info.GetTrianglesReader(ind));
+        src.Skip(m_trgOffsets[ind]);
+        serial::LoadOuterTriangles(src, m_Info.GetCodingParams(), m_pF->m_Triangles);
+
+        sz = static_cast<uint32_t>(src.Pos() - m_trgOffsets[ind]);
+      }
+    }
+
+    ::feature::CalcRect(m_pF->m_Triangles, m_pF->m_LimitRect);
+  }
+
+  return sz;
+}
+
+void LoaderImpl::ReadOffsets(ArrayByteSource & src, uint8_t mask, offsets_t & offsets) const
+{
+  ASSERT_GREATER ( mask, 0, () );
+
+  int index = 0;
+  while (mask > 0)
+  {
+    ASSERT_LESS ( index, m_Info.GetScalesCount(), () );
+    offsets[index++] = (mask & 0x01) ? ReadVarUint<uint32_t>(src) : kInvalidOffset;
+    mask = mask >> 1;
+  }
+}
+
+}
+}
diff --git a/indexer/old/feature_loader_101.hpp b/indexer/old/feature_loader_101.hpp
new file mode 100644
index 0000000000..d7fe928c10
--- /dev/null
+++ b/indexer/old/feature_loader_101.hpp
@@ -0,0 +1,44 @@
+#pragma once
+#include "../feature_loader_base.hpp"
+
+
+namespace old_101 { namespace feature
+{
+  class LoaderImpl : public ::feature::LoaderBase
+  {
+    typedef ::feature::LoaderBase BaseT;
+
+    void ReadOffsets(ArrayByteSource & src, uint8_t mask, offsets_t & offsets) const;
+
+    /// Get the index for geometry serialization.
+    /// @param[in]  scale:
+    /// -1 : index for the best geometry
+    /// default : needed geometry
+    //@{
+    int GetScaleIndex(int scale) const;
+    int GetScaleIndex(int scale, offsets_t const & offsets) const;
+    //@}
+
+    enum
+    {
+      HEADER_HAS_LAYER = 1U << 7,
+      HEADER_HAS_NAME = 1U << 6,
+      HEADER_IS_AREA = 1U << 5,
+      HEADER_IS_LINE = 1U << 4,
+      HEADER_HAS_POINT = 1U << 3
+    };
+
+  public:
+    LoaderImpl(::feature::SharedLoadInfo const & info) : BaseT(info) {}
+
+    virtual uint8_t GetHeader();
+
+    virtual void ParseTypes();
+    virtual void ParseCommon();
+    virtual void ParseHeader2();
+    virtual uint32_t ParseGeometry(int scale);
+    virtual uint32_t ParseTriangles(int scale);
+  };
+
+}
+}
diff --git a/indexer/old/interval_index_101.hpp b/indexer/old/interval_index_101.hpp
new file mode 100644
index 0000000000..2a72c841fe
--- /dev/null
+++ b/indexer/old/interval_index_101.hpp
@@ -0,0 +1,159 @@
+#pragma once
+#include "../interval_index_iface.hpp"
+
+#include "../../coding/endianness.hpp"
+
+#include "../../base/assert.hpp"
+#include "../../base/base.hpp"
+#include "../../base/macros.hpp"
+
+#include "../../std/memcpy.hpp"
+
+
+namespace old_101 {
+
+class IntervalIndexBase : public IntervalIndexIFace
+{
+public:
+#pragma pack(push, 1)
+  struct Header
+  {
+    uint8_t m_CellIdLeafBytes;
+  };
+#pragma pack(pop)
+
+  class Index
+  {
+  public:
+    uint32_t GetBaseOffset() const { return UINT32_FROM_UINT16(m_BaseOffsetHi, m_BaseOffsetLo); }
+    void SetBaseOffset(uint32_t baseOffset)
+    {
+      m_BaseOffsetLo = UINT32_LO(baseOffset);
+      m_BaseOffsetHi = UINT32_HI(baseOffset);
+    }
+
+  private:
+    uint16_t m_BaseOffsetLo;
+    uint16_t m_BaseOffsetHi;
+  public:
+    uint16_t m_Count[256];
+  };
+  STATIC_ASSERT(sizeof(Index) == 2 * 258);
+};
+
+// TODO: IntervalIndex shouldn't do SwapIfBigEndian for ValueT.
+template <typename ValueT, class ReaderT>
+class IntervalIndex : public IntervalIndexBase
+{
+  typedef IntervalIndexBase base_t;
+
+public:
+
+  class Query : public base_t::QueryIFace
+  {
+  public:
+    void Clear() {}
+
+  private:
+    friend class IntervalIndex;
+    vector<char> m_IntervalIndexCache;
+  };
+
+  IntervalIndex(ReaderT const & reader, int cellIdBytes = 5)
+    : m_Reader(reader), m_CellIdBytes(cellIdBytes)
+  {
+    m_Reader.Read(0, &m_Header, sizeof(m_Header));
+    ReadIndex(sizeof(m_Header), m_Level0Index);
+  }
+
+  template <typename F>
+  void ForEach(F const & f, uint64_t beg, uint64_t end, Query & query) const
+  {
+    ASSERT_LESS(beg, 1ULL << 8 * m_CellIdBytes, (beg, end));
+    ASSERT_LESS_OR_EQUAL(end, 1ULL << 8 * m_CellIdBytes, (beg, end));
+    // end is inclusive in ForEachImpl().
+    --end;
+    ForEachImpl(f, beg, end, m_Level0Index, m_CellIdBytes - 1, query);
+  }
+
+  template <typename F>
+  void ForEach(F const & f, uint64_t beg, uint64_t end) const
+  {
+    Query query;
+    ForEach(f, beg, end, query);
+  }
+
+  virtual void DoForEach(FunctionT const & f, uint64_t beg, uint64_t end, QueryIFace & /*query*/)
+  {
+    ForEach(f, beg, end);
+  }
+
+private:
+  template <typename F>
+  void ForEachImpl(F const & f, uint64_t beg, uint64_t end, Index const & index, int level,
+                   Query & query) const
+  {
+    uint32_t const beg0 = static_cast<uint32_t>(beg >> (8 * level));
+    uint32_t const end0 = static_cast<uint32_t>(end >> (8 * level));
+    uint32_t cumCount = 0;
+    for (uint32_t i = 0; i < beg0; ++i)
+      cumCount += index.m_Count[i];
+    for (uint32_t i = beg0; i <= end0; ++i)
+    {
+      ASSERT_LESS(i, 256, ());
+      if (index.m_Count[i] != 0)
+      {
+        uint64_t const levelBytesFF = (1ULL << 8 * level) - 1;
+        uint64_t const b1 = (i == beg0) ? (beg & levelBytesFF) : 0;
+        uint64_t const e1 = (i == end0) ? (end & levelBytesFF) : levelBytesFF;
+        if (level > m_Header.m_CellIdLeafBytes)
+        {
+          Index index1;
+          ReadIndex(index.GetBaseOffset() + (cumCount * sizeof(Index)), index1);
+          ForEachImpl(f, b1, e1, index1, level - 1, query);
+        }
+        else
+        {
+          // TODO: Use binary search here if count is very large.
+          uint32_t const step = sizeof(ValueT) + m_Header.m_CellIdLeafBytes;
+          uint32_t const count = index.m_Count[i];
+          uint32_t pos = index.GetBaseOffset() + (cumCount * step);
+          size_t const readSize = step * count;
+          query.m_IntervalIndexCache.assign(readSize, 0);
+          char * pData = &query.m_IntervalIndexCache[0];
+          m_Reader.Read(pos, pData, readSize);
+          for (uint32_t j = 0; j < count; ++j, pData += step)
+          // for (uint32_t j = 0; j < count; ++j, pos += step)
+          {
+            ValueT value;
+            uint32_t cellIdOnDisk = 0;
+            memcpy(&value, pData, sizeof(ValueT));
+            memcpy(&cellIdOnDisk, pData + sizeof(ValueT), m_Header.m_CellIdLeafBytes);
+            // m_Reader.Read(pos, &value, step);
+            uint32_t const cellId = SwapIfBigEndian(cellIdOnDisk);
+            if (b1 <= cellId && cellId <= e1)
+              f(SwapIfBigEndian(value));
+          }
+        }
+        cumCount += index.m_Count[i];
+      }
+    }
+  }
+
+  void ReadIndex(uint64_t pos, Index & index) const
+  {
+    m_Reader.Read(pos, &index, sizeof(Index));
+    if (IsBigEndian())
+    {
+      for (uint32_t i = 0; i < 256; ++i)
+        index.m_Count[i] = SwapIfBigEndian(index.m_Count[i]);
+    }
+  }
+
+  ReaderT m_Reader;
+  Header m_Header;
+  Index m_Level0Index;
+  int m_CellIdBytes;
+};
+
+}