Switch to using multi_type_vector for cell storage.

The old style cell storage is no more.  Currently the code is buildable,
but crashes during unit test.

Change-Id: Ie688e22e95c7fb02b9e97b23df0fc1883a97945f

1 files changed, 786 insertions, 0 deletions

diff --git a/sc/inc/mtvfunctions.hxx b/sc/inc/mtvfunctions.hxx
new file mode 100644
index 000000000000..03cb55ab4548
--- /dev/null
+++ b/sc/inc/mtvfunctions.hxx
@@ -0,0 +1,786 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#ifndef SC_MTVFUNCTIONS_HXX
+#define SC_MTVFUNCTIONS_HXX
+
+#include <cstdlib>
+#include <mdds/multi_type_vector_types.hpp>
+
+namespace sc {
+
+template<typename _SizeT, typename _Ret = bool>
+struct FuncElseNoOp
+{
+    _Ret operator() (mdds::mtv::element_t, _SizeT, _SizeT) const
+    {
+        return _Ret();
+    }
+};
+
+/**
+ * Generic algorithm to parse blocks of multi_type_vector either partially
+ * or fully.
+ */
+template<typename _StoreT, typename _Func>
+typename _StoreT::const_iterator
+ParseBlock(
+    const typename _StoreT::const_iterator& itPos, const _StoreT& rStore, _Func& rFunc,
+    typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd)
+{
+    typedef std::pair<typename _StoreT::const_iterator, typename _StoreT::size_type> PositionType;
+
+    PositionType aPos = rStore.position(itPos, nStart);
+    typename _StoreT::const_iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        rFunc(*it, nOffset, nDataSize);
+
+        if (bLastBlock)
+            break;
+    }
+
+    return it;
+}
+
+/**
+ * Non-const variant of the above function. TODO: Find a way to merge these
+ * two in an elegant way.
+ */
+template<typename _StoreT, typename _Func>
+typename _StoreT::iterator
+ProcessBlock(const typename _StoreT::iterator& itPos, _StoreT& rStore, _Func& rFunc, typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd)
+{
+    typedef std::pair<typename _StoreT::iterator, typename _StoreT::size_type> PositionType;
+
+    PositionType aPos = rStore.position(itPos, nStart);
+    typename _StoreT::iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nCurRow = nStart;
+
+    for (; it != rStore.end() && nCurRow <= nEnd; ++it, nOffset = 0, nCurRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nCurRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nCurRow + 1;
+            bLastBlock = true;
+        }
+
+        rFunc(*it, nOffset, nDataSize);
+
+        if (bLastBlock)
+            break;
+    }
+
+    return it;
+}
+
+template<typename _StoreT, typename _BlkT, typename _FuncElem, typename _FuncElse>
+void ParseElements1(const _StoreT& rStore, _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typename _StoreT::size_type nTopRow = 0, nDataSize = 0;
+    typename _StoreT::const_iterator it = rStore.begin(), itEnd = rStore.end();
+    for (; it != itEnd; ++it, nTopRow += nDataSize)
+    {
+        nDataSize = it->size;
+        if (it->type != _BlkT::block_type)
+        {
+            rFuncElse(it->type, nTopRow, nDataSize);
+            continue;
+        }
+
+        typename _BlkT::const_iterator itf    = _BlkT::begin(*it->data);
+        typename _BlkT::const_iterator itfEnd = _BlkT::end(*it->data);
+        typename _StoreT::size_type nRow = nTopRow;
+        for (; itf != itfEnd; ++itf, ++nRow)
+            rFuncElem(nRow, *itf);
+    }
+}
+
+template<typename _StoreT, typename _BlkT, typename _FuncElem, typename _FuncElse>
+typename _StoreT::const_iterator
+ParseElements1(
+    const typename _StoreT::const_iterator& itPos, const _StoreT& rStore,
+    typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd,
+    _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typedef std::pair<typename _StoreT::const_iterator, typename _StoreT::size_type> PositionType;
+
+    PositionType aPos = rStore.position(itPos, nStart);
+    typename _StoreT::const_iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        if (it->type == _BlkT::block_type)
+        {
+            typename _BlkT::const_iterator itf    = _BlkT::begin(*it->data);
+            std::advance(itf, nOffset);
+            typename _BlkT::const_iterator itfEnd = itf;
+            std::advance(itfEnd, nDataSize);
+            typename _StoreT::size_type nRow = nTopRow;
+            for (; itf != itfEnd; ++itf, ++nRow)
+                rFuncElem(nRow, *itf);
+        }
+        else
+            rFuncElse(it->type, nTopRow, nDataSize);
+
+
+        if (bLastBlock)
+            break;
+    }
+
+    return it;
+};
+
+template<typename _StoreT, typename _Blk1, typename _Blk2, typename _FuncElem, typename _FuncElse>
+typename _StoreT::const_iterator
+ParseElements2(
+    const typename _StoreT::const_iterator& itPos, const _StoreT& rStore, typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd,
+    _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typedef std::pair<typename _StoreT::const_iterator, typename _StoreT::size_type> PositionType;
+
+    PositionType aPos = rStore.position(itPos, nStart);
+    typename _StoreT::const_iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::const_iterator itData = _Blk1::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk1::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk2::block_type:
+            {
+                typename _Blk2::const_iterator itData = _Blk2::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk2::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            default:
+                rFuncElse(it->type, nTopRow, nDataSize);
+        }
+
+        if (bLastBlock)
+            break;
+    }
+
+    return it;
+}
+
+template<typename _StoreT, typename _Blk1, typename _Blk2, typename _Blk3, typename _Blk4, typename _FuncElem, typename _FuncElse>
+typename _StoreT::const_iterator
+ParseElements4(
+    const typename _StoreT::const_iterator& itPos, const _StoreT& rStore, typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd,
+    _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typedef std::pair<typename _StoreT::const_iterator, typename _StoreT::size_type> PositionType;
+
+    PositionType aPos = rStore.position(itPos, nStart);
+    typename _StoreT::const_iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::const_iterator itData = _Blk1::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk1::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk2::block_type:
+            {
+                typename _Blk2::const_iterator itData = _Blk2::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk2::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk3::block_type:
+            {
+                typename _Blk3::const_iterator itData = _Blk3::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk3::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk4::block_type:
+            {
+                typename _Blk4::const_iterator itData = _Blk4::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk4::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            default:
+                rFuncElse(it->type, nTopRow, nDataSize);
+        }
+
+        if (bLastBlock)
+            break;
+    }
+
+    return it;
+}
+
+template<typename _StoreT, typename _BlkT, typename _FuncElem, typename _FuncElse>
+void ProcessElements1(_StoreT& rStore, _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typename _StoreT::size_type nTopRow = 0, nDataSize = 0;
+    typename _StoreT::iterator it = rStore.begin(), itEnd = rStore.end();
+    for (; it != itEnd; ++it, nTopRow += nDataSize)
+    {
+        nDataSize = it->size;
+        if (it->type != _BlkT::block_type)
+        {
+            rFuncElse(it->type, nTopRow, nDataSize);
+            continue;
+        }
+
+        typename _BlkT::iterator itf    = _BlkT::begin(*it->data);
+        typename _BlkT::iterator itfEnd = _BlkT::end(*it->data);
+        typename _StoreT::size_type nRow = nTopRow;
+        for (; itf != itfEnd; ++itf, ++nRow)
+            rFuncElem(nRow, *itf);
+    }
+}
+
+/**
+ * This variant specifies start and end positions.
+ */
+template<typename _StoreT, typename _BlkT, typename _FuncElem, typename _FuncElse>
+typename _StoreT::iterator
+ProcessElements1(
+    const typename _StoreT::iterator& itPos, _StoreT& rStore,
+    typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd,
+    _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typedef std::pair<typename _StoreT::iterator, typename _StoreT::size_type> PositionType;
+
+    PositionType aPos = rStore.position(itPos, nStart);
+    typename _StoreT::iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        if (it->type == _BlkT::block_type)
+        {
+            typename _BlkT::iterator itf    = _BlkT::begin(*it->data);
+            std::advance(itf, nOffset);
+            typename _BlkT::iterator itfEnd = itf;
+            std::advance(itfEnd, nDataSize);
+            typename _StoreT::size_type nRow = nTopRow;
+            for (; itf != itfEnd; ++itf, ++nRow)
+                rFuncElem(nRow, *itf);
+        }
+        else
+            rFuncElse(it->type, nTopRow, nDataSize);
+
+        if (bLastBlock)
+            break;
+    }
+
+    return it;
+};
+
+template<typename _StoreT, typename _Blk1, typename _Blk2, typename _FuncElem, typename _FuncElse>
+void ProcessElements2(_StoreT& rStore, _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typename _StoreT::size_type nTopRow = 0, nDataSize = 0;
+    typename _StoreT::iterator it = rStore.begin(), itEnd = rStore.end();
+    for (; it != itEnd; ++it, nTopRow += nDataSize)
+    {
+        nDataSize = it->size;
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::iterator itData    = _Blk1::begin(*it->data);
+                typename _Blk1::iterator itDataEnd = _Blk1::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk2::block_type:
+            {
+                typename _Blk2::iterator itData    = _Blk2::begin(*it->data);
+                typename _Blk2::iterator itDataEnd = _Blk2::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            default:
+                rFuncElse(it->type, nTopRow, nDataSize);
+        }
+    }
+}
+
+template<typename _StoreT, typename _Blk1, typename _Blk2, typename _FuncElem, typename _FuncElse>
+typename _StoreT::iterator
+ProcessElements2(
+    const typename _StoreT::iterator& itPos, _StoreT& rStore,
+    typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd,
+    _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typedef std::pair<typename _StoreT::iterator, typename _StoreT::size_type> PositionType;
+
+    PositionType aPos = rStore.position(itPos, nStart);
+    typename _StoreT::iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::iterator itData = _Blk1::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk1::iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk2::block_type:
+            {
+                typename _Blk2::iterator itData = _Blk2::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk2::iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            default:
+                rFuncElse(it->type, nTopRow, nDataSize);
+        }
+
+        if (bLastBlock)
+            break;
+    }
+
+    return it;
+}
+
+template<typename _StoreT, typename _Blk1, typename _Blk2, typename _Blk3, typename _FuncElem, typename _FuncElse>
+void ProcessElements3(_StoreT& rStore, _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typename _StoreT::size_type nTopRow = 0, nDataSize = 0;
+    typename _StoreT::iterator it = rStore.begin(), itEnd = rStore.end();
+    for (; it != itEnd; ++it, nTopRow += nDataSize)
+    {
+        nDataSize = it->size;
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::iterator itData    = _Blk1::begin(*it->data);
+                typename _Blk1::iterator itDataEnd = _Blk1::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk2::block_type:
+            {
+                typename _Blk2::iterator itData    = _Blk2::begin(*it->data);
+                typename _Blk2::iterator itDataEnd = _Blk2::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk3::block_type:
+            {
+                typename _Blk3::iterator itData    = _Blk3::begin(*it->data);
+                typename _Blk3::iterator itDataEnd = _Blk3::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            default:
+                rFuncElse(it->type, nTopRow, nDataSize);
+        }
+    }
+}
+
+template<typename _StoreT, typename _Blk1, typename _Blk2, typename _Blk3, typename _Blk4, typename _FuncElem, typename _FuncElse>
+void ProcessElements4(_StoreT& rStore, _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typename _StoreT::size_type nTopRow = 0, nDataSize = 0;
+    typename _StoreT::iterator it = rStore.begin(), itEnd = rStore.end();
+    for (; it != itEnd; ++it, nTopRow += nDataSize)
+    {
+        nDataSize = it->size;
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::iterator itData    = _Blk1::begin(*it->data);
+                typename _Blk1::iterator itDataEnd = _Blk1::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk2::block_type:
+            {
+                typename _Blk2::iterator itData    = _Blk2::begin(*it->data);
+                typename _Blk2::iterator itDataEnd = _Blk2::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk3::block_type:
+            {
+                typename _Blk3::iterator itData    = _Blk3::begin(*it->data);
+                typename _Blk3::iterator itDataEnd = _Blk3::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk4::block_type:
+            {
+                typename _Blk4::iterator itData    = _Blk4::begin(*it->data);
+                typename _Blk4::iterator itDataEnd = _Blk4::end(*it->data);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            default:
+                rFuncElse(it->type, nTopRow, nDataSize);
+        }
+    }
+}
+
+template<typename _StoreT, typename _Blk1, typename _Blk2, typename _Blk3, typename _Blk4, typename _FuncElem, typename _FuncElse>
+typename _StoreT::iterator
+ProcessElements4(
+    const typename _StoreT::iterator& itPos, _StoreT& rStore,
+    typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd,
+    _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typedef std::pair<typename _StoreT::iterator, typename _StoreT::size_type> PositionType;
+
+    PositionType aPos = rStore.position(itPos, nStart);
+    typename _StoreT::iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::iterator itData = _Blk1::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk1::iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk2::block_type:
+            {
+                typename _Blk2::iterator itData = _Blk2::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk2::iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk3::block_type:
+            {
+                typename _Blk3::iterator itData = _Blk3::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk3::iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            case _Blk4::block_type:
+            {
+                typename _Blk4::iterator itData = _Blk4::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk4::iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    rFuncElem(nRow, *itData);
+            }
+            break;
+            default:
+                rFuncElse(it->type, nTopRow, nDataSize);
+        }
+
+        if (bLastBlock)
+            break;
+    }
+
+    return it;
+}
+
+template<typename _StoreT, typename _Blk1, typename _FuncElem, typename _FuncElse>
+std::pair<typename _StoreT::const_iterator, typename _StoreT::size_type>
+FindElement1(
+    const _StoreT& rStore, typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd,
+    _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typedef std::pair<typename _StoreT::const_iterator, typename _StoreT::size_type> PositionType;
+    typedef std::pair<typename _StoreT::size_type, bool> ElseRetType;
+
+    PositionType aPos = rStore.position(nStart);
+    typename _StoreT::const_iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::const_iterator itData = _Blk1::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk1::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                {
+                    if (rFuncElem(nRow, *itData))
+                        return PositionType(it, nRow-nTopRow);
+                }
+            }
+            break;
+            default:
+            {
+                ElseRetType aRet = rFuncElse(it->type, nTopRow, nDataSize);
+                if (aRet.second)
+                    return PositionType(it, aRet.first);
+            }
+        }
+
+        if (bLastBlock)
+            break;
+    }
+
+    return PositionType(rStore.end(), 0);
+}
+
+template<typename _StoreT, typename _Blk1, typename _Blk2, typename _FuncElem, typename _FuncElse>
+std::pair<typename _StoreT::const_iterator, typename _StoreT::size_type>
+FindElement2(
+    const _StoreT& rStore, typename _StoreT::size_type nStart, typename _StoreT::size_type nEnd,
+    _FuncElem& rFuncElem, _FuncElse& rFuncElse)
+{
+    typedef std::pair<typename _StoreT::const_iterator, typename _StoreT::size_type> PositionType;
+    typedef std::pair<typename _StoreT::size_type, bool> ElseRetType;
+
+    PositionType aPos = rStore.position(nStart);
+    typename _StoreT::const_iterator it = aPos.first;
+    typename _StoreT::size_type nOffset = aPos.second;
+    typename _StoreT::size_type nDataSize = 0;
+    typename _StoreT::size_type nTopRow = nStart;
+
+    for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
+    {
+        bool bLastBlock = false;
+        nDataSize = it->size - nOffset;
+        if (nTopRow + nDataSize - 1 > nEnd)
+        {
+            // Truncate the block.
+            nDataSize = nEnd - nTopRow + 1;
+            bLastBlock = true;
+        }
+
+        switch (it->type)
+        {
+            case _Blk1::block_type:
+            {
+                typename _Blk1::const_iterator itData = _Blk1::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk1::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                {
+                    if (rFuncElem(nRow, *itData))
+                        return PositionType(it, nRow-nTopRow);
+                }
+            }
+            break;
+            case _Blk2::block_type:
+            {
+                typename _Blk2::const_iterator itData = _Blk2::begin(*it->data);
+                std::advance(itData, nOffset);
+                typename _Blk2::const_iterator itDataEnd = itData;
+                std::advance(itDataEnd, nDataSize);
+                typename _StoreT::size_type nRow = nTopRow;
+                for (; itData != itDataEnd; ++itData, ++nRow)
+                    if (rFuncElem(nRow, *itData))
+                        return PositionType(it, nRow-nTopRow);
+            }
+            break;
+            default:
+            {
+                ElseRetType aRet = rFuncElse(it->type, nTopRow, nDataSize);
+                if (aRet.second)
+                    return PositionType(it, aRet.first);
+            }
+        }
+
+        if (bLastBlock)
+            break;
+    }
+
+    return PositionType(rStore.end(), 0);
+}
+
+}
+
+#endif
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */