lok - sc: a cache-like structure for row/col positions in the document

ScPositionHelper provides the ability to insert (and remove) row-
position pairs where the position is in pixel and related to the
spreadsheet top.

In this way one can compute a new row position by starting from the
nearest row presents in this cache-like data structure.

It offers also the ability to invalidate the cache by removing all
cached data below a given row or position.

This data structure can be used for columns, too.

Change-Id: Ifd66a003680ef9a3babf46ae952221c04451be9a
Reviewed-on: https://gerrit.libreoffice.org/40447
Tested-by: Jenkins <ci@libreoffice.org>
Reviewed-by: Marco Cecchetti <mrcekets@gmail.com>

2 files changed, 197 insertions, 0 deletions

diff --git a/sc/source/ui/inc/viewdata.hxx b/sc/source/ui/inc/viewdata.hxx
index bd1288d6ba9c..dbda16afe2f2 100644
--- a/sc/source/ui/inc/viewdata.hxx
+++ b/sc/source/ui/inc/viewdata.hxx
@@ -118,6 +118,38 @@ class ScViewData;
 class ScMarkData;
 class ScGridWindow;
 
+class ScPositionHelper
+{
+public:
+    typedef SCCOLROW index_type;
+    typedef std::pair<index_type, long> value_type;
+    static_assert(std::numeric_limits<index_type>::is_signed, "ScPositionCache: index type is not signed");
+
+private:
+    static const index_type null = std::numeric_limits<index_type>::min();
+
+    class Comp
+    {
+    public:
+        bool operator() (const value_type& rValue1, const value_type& rValue2) const;
+    };
+
+    std::set<value_type, Comp> mData;
+
+public:
+    ScPositionHelper();
+
+    void insert(index_type nIndex, long nPos);
+    void removeByIndex(index_type nIndex);
+    void removeByPosition(long nPos);
+    void invalidateByIndex(index_type nIndex);
+    void invalidateByPosition(long nPos);
+    const value_type& getNearestByIndex(index_type nIndex) const;
+    const value_type& getNearestByPosition(long nPos) const;
+    long getPosition(index_type nIndex) const;
+    index_type getIndex(long nPos) const;
+};
+
 class ScViewDataTable                           // per-sheet data
 {
 friend class ScViewData;
@@ -148,6 +180,9 @@ private:
     SCROW           nCurY;
     SCCOL           nOldCurX;
     SCROW           nOldCurY;
+    ScPositionHelper aWidthHelper;
+    ScPositionHelper aHeightHelper;
+
     SCCOL           nPosX[2];                   ///< X position of the top left cell of the visible area.
     SCROW           nPosY[2];                   ///< Y position of the top left cell of the visible area.
     SCCOL           nMaxTiledCol;
@@ -302,6 +337,8 @@ public:
     SCROW           GetCurYForTab( SCTAB nTabIndex ) const;
     SCCOL           GetOldCurX() const;
     SCROW           GetOldCurY() const;
+    ScPositionHelper& GetLOKWidthHelper()                   { return pThisTab->aWidthHelper; }
+    ScPositionHelper& GetLOKHeightHelper()                  { return pThisTab->aHeightHelper; }
 
     ScSplitMode     GetHSplitMode() const                   { return pThisTab->eHSplitMode; }
     ScSplitMode     GetVSplitMode() const                   { return pThisTab->eVSplitMode; }
diff --git a/sc/source/ui/view/viewdata.cxx b/sc/source/ui/view/viewdata.cxx
index 92647acb5a5e..af65ac0af798 100644
--- a/sc/source/ui/view/viewdata.cxx
+++ b/sc/source/ui/view/viewdata.cxx
@@ -90,6 +90,166 @@ void lcl_LOKRemoveWindow(ScTabViewShell* pTabViewShell, ScSplitPos eWhich)
 
 } // anonymous namespace
 
+const ScPositionHelper::index_type ScPositionHelper::null; // definition
+
+bool ScPositionHelper::Comp::operator() (const value_type& rValue1, const value_type& rValue2) const
+{
+    if (rValue1.first == null || rValue2.first == null)
+    {
+        return rValue1.second < rValue2.second;
+    }
+    else
+    {
+        return rValue1.first < rValue2.first;
+    }
+}
+
+ScPositionHelper::ScPositionHelper()
+{
+    mData.insert(std::make_pair(-1, 0));
+}
+
+void ScPositionHelper::insert(index_type nIndex, long nPos)
+{
+    if (nIndex < 0) return;
+    SAL_INFO("sc.lok.poshelper", "ScPositionHelper::insert: nIndex: "
+            << nIndex << ", nPos: " << nPos << ", size: " << mData.size());
+    value_type aValue = std::make_pair(nIndex, nPos);
+    mData.erase(aValue);
+    mData.insert(aValue);
+    SAL_INFO("sc.lok.poshelper",
+            "ScPositionHelper::insert: after insert: size: " << mData.size());
+}
+
+void ScPositionHelper::removeByIndex(index_type nIndex)
+{
+    if (nIndex < 0)
+        return;
+    SAL_INFO("sc.lok.poshelper", "ScPositionHelper::remove: nIndex: " << nIndex
+            << ", size: " << mData.size());
+    auto it = mData.find(std::make_pair(nIndex, 0));
+    if (it == mData.end()) return;
+    mData.erase(it);
+    SAL_INFO("sc.lok.poshelper",
+            "ScPositionHelper::remove: after erase: size: " << mData.size());
+}
+
+void ScPositionHelper::removeByPosition(long nPos)
+{
+    SAL_INFO("sc.lok.poshelper", "ScPositionHelper::remove: nPos: " << nPos
+            << ", size: " << mData.size());
+    auto it = mData.find(std::make_pair(null, nPos));
+    if (it == mData.end() || it->first <= 0)
+        return;
+    mData.erase(it);
+    SAL_INFO("sc.lok.poshelper",
+            "ScPositionHelper::remove: after erase: size: " << mData.size());
+}
+
+void ScPositionHelper::invalidateByIndex(index_type nIndex)
+{
+    SAL_INFO("sc.lok.poshelper", "ScPositionHelper::invalidate: nIndex: " << nIndex);
+    if (nIndex < 0)
+    {
+        mData.clear();
+        mData.insert(std::make_pair(-1, 0));
+    }
+    else
+    {
+        auto it = mData.lower_bound(std::make_pair(nIndex, 0));
+        mData.erase(it, mData.end());
+    }
+}
+
+void ScPositionHelper::invalidateByPosition(long nPos)
+{
+    SAL_INFO("sc.lok.poshelper", "ScPositionHelper::invalidate: nPos: " << nPos);
+    if (nPos <= 0)
+    {
+        mData.clear();
+        mData.insert(std::make_pair(-1, 0));
+    }
+    else
+    {
+        auto it = mData.lower_bound(std::make_pair(null, nPos));
+        mData.erase(it, mData.end());
+    }
+}
+
+const ScPositionHelper::value_type&
+ScPositionHelper::getNearestByIndex(index_type nIndex) const
+{
+    SAL_INFO("sc.lok.poshelper",
+            "ScPositionHelper::getNearest: nIndex: " << nIndex << ", size: " << mData.size());
+    auto posUB = mData.upper_bound(std::make_pair(nIndex, 0));
+    if (posUB == mData.begin())
+    {
+        return *posUB;
+    }
+
+    auto posLB = std::prev(posUB);
+    if (posUB == mData.end())
+    {
+        return *posLB;
+    }
+
+    long nDiffUB = posUB->first - nIndex;
+    long nDiffLB = posLB->first - nIndex;
+    if (nDiffUB < -nDiffLB)
+    {
+        return *posUB;
+    }
+    else
+    {
+        return *posLB;
+    }
+}
+
+const ScPositionHelper::value_type&
+ScPositionHelper::getNearestByPosition(long nPos) const
+{
+    SAL_INFO("sc.lok.poshelper",
+            "ScPositionHelper::getNearest: nPos: " << nPos << ", size: " << mData.size());
+    auto posUB = mData.upper_bound(std::make_pair(null, nPos));
+
+    if (posUB == mData.begin())
+    {
+        return *posUB;
+    }
+
+    auto posLB = std::prev(posUB);
+    if (posUB == mData.end())
+    {
+        return *posLB;
+    }
+
+    long nDiffUB = posUB->second - nPos;
+    long nDiffLB = posLB->second - nPos;
+
+    if (nDiffUB < -nDiffLB)
+    {
+        return *posUB;
+    }
+    else
+    {
+        return *posLB;
+    }
+}
+
+long ScPositionHelper::getPosition(index_type nIndex) const
+{
+    auto it = mData.find(std::make_pair(nIndex, 0));
+    if (it == mData.end()) return -1;
+    return it->second;
+}
+
+ScPositionHelper::index_type ScPositionHelper::getIndex(long nPos) const
+{
+    auto it = mData.find(std::make_pair(null, nPos));
+    if (it == mData.end()) return null;
+    return it->first;
+}
+
 ScViewDataTable::ScViewDataTable() :
                 eZoomType( SvxZoomType::PERCENT ),
                 aZoomX( 1,1 ),