Refactor ScMarkData for tdf#50916

Made the container for storing multimarks dynamic.
Also let the full row marks to be stored in a dedicated
ScMarkArray object rather than in the multimarks container.

Unit tests for ScMarkData and ScMultiSel will come in a follow up
patch.

Reviewed-on: https://gerrit.libreoffice.org/22163
Tested-by: Jenkins <ci@libreoffice.org>
Reviewed-by: Markus Mohrhard <markus.mohrhard@googlemail.com>
(cherry picked from commit bc20c6d0f397c0c1aef6ef7d6f750c2f81af8db6)

Change-Id: I300ff80bebd6f4f39c284c1e8cb7deece82c1bec
Reviewed-on: https://gerrit.libreoffice.org/25282
Reviewed-by: Ashod Nakashian <ashnakash@gmail.com>
Tested-by: Ashod Nakashian <ashnakash@gmail.com>

14 files changed, 818 insertions, 125 deletions

diff --git a/sc/Library_sc.mk b/sc/Library_sc.mk
index d2fd5cd345b9..b22b2a0869ad 100644
--- a/sc/Library_sc.mk
+++ b/sc/Library_sc.mk
@@ -165,6 +165,7 @@ $(eval $(call gb_Library_add_exception_objects,sc,\
     sc/source/core/data/listenercontext \
     sc/source/core/data/markarr \
     sc/source/core/data/markdata \
+    sc/source/core/data/markmulti \
     sc/source/core/data/mtvelements \
     sc/source/core/data/olinetab \
     sc/source/core/data/pagepar \
diff --git a/sc/inc/markarr.hxx b/sc/inc/markarr.hxx
index 2988fe4b74cb..386b97adaa8a 100644
--- a/sc/inc/markarr.hxx
+++ b/sc/inc/markarr.hxx
@@ -41,6 +41,7 @@ friend class ScDocument;                // for FillInfo
 
 public:
             ScMarkArray();
+            ScMarkArray( ScMarkArray&& rArray );
             ~ScMarkArray();
     void    Reset( bool bMarked = false );
     bool    GetMark( SCROW nRow ) const;
diff --git a/sc/inc/markdata.hxx b/sc/inc/markdata.hxx
index fc7aec64c6ce..0392971f0a1c 100644
--- a/sc/inc/markdata.hxx
+++ b/sc/inc/markdata.hxx
@@ -21,9 +21,12 @@
 #define INCLUDED_SC_INC_MARKDATA_HXX
 
 #include "address.hxx"
+#include "rangelst.hxx"
+#include "markmulti.hxx"
 #include "scdllapi.h"
 
 #include <set>
+#include <vector>
 
 namespace sc {
 
@@ -48,12 +51,17 @@ private:
 
     ScRange         aMarkRange;             // area
     ScRange         aMultiRange;            // maximum area altogether
-    ScMarkArray*    pMultiSel;              // multi selection
+    ScMultiSel      aMultiSel;              // multi selection
     bool            bMarked:1;                // rectangle marked
     bool            bMultiMarked:1;
 
     bool            bMarking:1;               // area is being marked -> no MarkToMulti
     bool            bMarkIsNeg:1;             // cancel if multi selection
+    ScRangeList     aTopEnvelope;             // list of ranges in the top envelope of the multi selection
+    ScRangeList     aBottomEnvelope;          // list of ranges in the bottom envelope of the multi selection
+    ScRangeList     aLeftEnvelope;            // list of ranges in the left envelope of the multi selection
+    ScRangeList     aRightEnvelope;           // list of ranges in the right envelope of the multi selection
+
 
 public:
                 ScMarkData();
@@ -65,7 +73,8 @@ public:
     void        ResetMark();
     void        SetMarkArea( const ScRange& rRange );
 
-    void        SetMultiMarkArea( const ScRange& rRange, bool bMark = true );
+    // bSetupMulti must be set to true only for recursive calls to SetMultiMarkArea
+    void        SetMultiMarkArea( const ScRange& rRange, bool bMark = true, bool bSetupMulti = false );
 
     void        MarkToMulti();
     void        MarkToSimple();
@@ -95,7 +104,8 @@ public:
     bool        GetMarkingFlag() const          { return bMarking;    }
 
     //  for FillInfo / Document etc.
-    const ScMarkArray* GetArray() const         { return pMultiSel; }
+    const ScMultiSel& GetMultiSelData() const   { return aMultiSel;   }
+    ScMarkArray GetMarkArray( SCCOL nCol ) const;
 
     bool        IsCellMarked( SCCOL nCol, SCROW nRow, bool bNoSimple = false ) const;
     void        FillRangeListWithMarks( ScRangeList* pList, bool bClear ) const;
@@ -121,6 +131,15 @@ public:
     void        InsertTab( SCTAB nTab );
     void        DeleteTab( SCTAB nTab );
 
+    // Generate envelopes if mutimarked and fills the passed ScRange object with
+    // the smallest range that includes the marked area plus its envelopes.
+    void        GetSelectionCover( ScRange& rRange );
+    // Get top, bottom, left and right envelopes
+    const ScRangeList& GetTopEnvelope() const    { return aTopEnvelope;    }
+    const ScRangeList& GetBottomEnvelope() const { return aBottomEnvelope; }
+    const ScRangeList& GetLeftEnvelope() const   { return aLeftEnvelope;   }
+    const ScRangeList& GetRightEnvelope() const  { return aRightEnvelope;  }
+
     // iterators for table access
     typedef std::set<SCTAB>::iterator iterator;
     typedef std::set<SCTAB>::const_iterator const_iterator;
diff --git a/sc/inc/markmulti.hxx b/sc/inc/markmulti.hxx
new file mode 100644
index 000000000000..22f0ee5d1dad
--- /dev/null
+++ b/sc/inc/markmulti.hxx
@@ -0,0 +1,84 @@
+/* -*- 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/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   Licensed to the Apache Software Foundation (ASF) under one or more
+ *   contributor license agreements. See the NOTICE file distributed
+ *   with this work for additional information regarding copyright
+ *   ownership. The ASF licenses this file to you under the Apache
+ *   License, Version 2.0 (the "License"); you may not use this file
+ *   except in compliance with the License. You may obtain a copy of
+ *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#ifndef INCLUDED_SC_INC_MARKMULTI_HXX
+#define INCLUDED_SC_INC_MARKMULTI_HXX
+
+#include "address.hxx"
+#include "segmenttree.hxx"
+#include "markarr.hxx"
+
+#include <map>
+
+class ScMultiSel
+{
+
+private:
+    typedef std::map<SCCOL, ScMarkArray> MapType;
+    MapType aMultiSelContainer;
+    ScMarkArray aRowSel;
+
+friend class ScMultiSelIter;
+
+public:
+    ScMultiSel();
+    ScMultiSel( const ScMultiSel& rMultiSel );
+    ~ScMultiSel();
+
+    ScMultiSel& operator=(const ScMultiSel& rMultiSel);
+    ScMultiSel& operator=(const ScMultiSel&& rMultiSel) = delete;
+
+    SCCOL size() const
+    {
+        return static_cast<SCCOL>( aMultiSelContainer.size() );
+    }
+
+    bool HasMarks( SCCOL nCol ) const;
+    bool HasOneMark( SCCOL nCol, SCROW& rStartRow, SCROW& rEndRow ) const;
+    bool GetMark( SCCOL nCol, SCROW nRow ) const;
+    bool IsAllMarked( SCCOL nCol, SCROW nStartRow, SCROW nEndRow ) const;
+    bool HasEqualRowsMarked( SCCOL nCol1, SCCOL nCol2 ) const;
+    SCsROW GetNextMarked( SCCOL nCol, SCsROW nRow, bool bUp ) const;
+    void SetMarkArea( SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, SCROW nEndRow, bool bMark );
+    bool IsRowMarked( SCROW nRow ) const;
+    bool IsRowRangeMarked( SCROW nStartRow, SCROW nEndRow ) const;
+    bool IsEmpty() const { return ( !aMultiSelContainer.size() && !aRowSel.HasMarks() ); }
+    ScMarkArray GetMarkArray( SCCOL nCol ) const;
+    void Clear();
+    void MarkAllCols( SCROW nStartRow, SCROW nEndRow );
+    bool HasAnyMarks() const;
+};
+
+class ScMultiSelIter
+{
+
+private:
+    ScFlatBoolRowSegments aRowSegs;
+    SCROW nNextSegmentStart;
+public:
+    ScMultiSelIter( const ScMultiSel& rMultiSel, SCCOL nCol );
+    ~ScMultiSelIter();
+
+    bool Next( SCROW& rTop, SCROW& rBottom );
+    const ScFlatBoolRowSegments& GetRowSegments() const { return aRowSegs; }
+};
+
+#endif
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/segmenttree.hxx b/sc/inc/segmenttree.hxx
index 72d45b63afb6..3a2d1283b002 100644
--- a/sc/inc/segmenttree.hxx
+++ b/sc/inc/segmenttree.hxx
@@ -68,7 +68,7 @@ public:
 
     bool setTrue(SCROW nRow1, SCROW nRow2);
     bool setFalse(SCROW nRow1, SCROW nRow2);
-    bool getRangeData(SCROW nRow, RangeData& rData);
+    bool getRangeData(SCROW nRow, RangeData& rData) const;
     bool getRangeDataLeaf(SCROW nRow, RangeData& rData);
     void removeSegment(SCROW nRow1, SCROW nRow2);
     void insertSegment(SCROW nRow, SCROW nSize, bool bSkipStartBoundary);
diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx
index 3a7daf10a657..6e5d6cba5f7c 100644
--- a/sc/source/core/data/column.cxx
+++ b/sc/source/core/data/column.cxx
@@ -314,8 +314,8 @@ bool ScColumn::HasAttribSelection( const ScMarkData& rMark, sal_uInt16 nMask ) c
 
     if (rMark.IsMultiMarked())
     {
-        ScMarkArrayIter aMarkIter( rMark.GetArray()+nCol );
-        while (aMarkIter.Next( nTop, nBottom ) && !bFound)
+        ScMultiSelIter aMultiIter( rMark.GetMultiSelData(), nCol );
+        while (aMultiIter.Next( nTop, nBottom ) && !bFound)
         {
             if (pAttrArray->HasAttrib( nTop, nBottom, nMask ))
                 bFound = true;
@@ -339,11 +339,11 @@ void ScColumn::MergeSelectionPattern( ScMergePatternState& rState, const ScMarkD
 
     if ( rMark.IsMultiMarked() )
     {
-        const ScMarkArray* pArray = rMark.GetArray() + nCol;
-        if ( pArray->HasMarks() )
+        const ScMultiSel& rMultiSel = rMark.GetMultiSelData();
+        if ( rMultiSel.HasMarks( nCol ) )
         {
-            ScMarkArrayIter aMarkIter( pArray );
-            while (aMarkIter.Next( nTop, nBottom ))
+            ScMultiSelIter aMultiIter( rMultiSel, nCol );
+            while (aMultiIter.Next( nTop, nBottom ))
                 pAttrArray->MergePatternArea( nTop, nBottom, rState, bDeep );
         }
     }
@@ -430,8 +430,8 @@ SCsROW ScColumn::ApplySelectionCache( SfxItemPoolCache* pCache, const ScMarkData
 
     if ( rMark.IsMultiMarked() )
     {
-        ScMarkArrayIter aMarkIter( rMark.GetArray() + nCol );
-        while (aMarkIter.Next( nTop, nBottom ))
+        ScMultiSelIter aMultiIter( rMark.GetMultiSelData(), nCol );
+        while (aMultiIter.Next( nTop, nBottom ))
         {
             pAttrArray->ApplyCacheArea( nTop, nBottom, pCache, pDataArray );
             bFound = true;
@@ -453,8 +453,8 @@ void ScColumn::ChangeSelectionIndent( bool bIncrement, const ScMarkData& rMark )
 
     if ( pAttrArray && rMark.IsMultiMarked() )
     {
-        ScMarkArrayIter aMarkIter( rMark.GetArray() + nCol );
-        while (aMarkIter.Next( nTop, nBottom ))
+        ScMultiSelIter aMultiIter( rMark.GetMultiSelData(), nCol );
+        while (aMultiIter.Next( nTop, nBottom ))
             pAttrArray->ChangeIndent(nTop, nBottom, bIncrement);
     }
 }
@@ -466,8 +466,8 @@ void ScColumn::ClearSelectionItems( const sal_uInt16* pWhich,const ScMarkData& r
 
     if ( pAttrArray && rMark.IsMultiMarked() )
     {
-        ScMarkArrayIter aMarkIter( rMark.GetArray() + nCol );
-        while (aMarkIter.Next( nTop, nBottom ))
+        ScMultiSelIter aMultiIter( rMark.GetMultiSelData(), nCol );
+        while (aMultiIter.Next( nTop, nBottom ))
             pAttrArray->ClearItems(nTop, nBottom, pWhich);
     }
 }
@@ -479,8 +479,8 @@ void ScColumn::DeleteSelection( InsertDeleteFlags nDelFlag, const ScMarkData& rM
 
     if ( rMark.IsMultiMarked() )
     {
-        ScMarkArrayIter aMarkIter( rMark.GetArray() + nCol );
-        while (aMarkIter.Next( nTop, nBottom ))
+        ScMultiSelIter aMultiIter( rMark.GetMultiSelData(), nCol );
+        while (aMultiIter.Next( nTop, nBottom ))
             DeleteArea(nTop, nBottom, nDelFlag, bBroadcast);
     }
 }
@@ -569,8 +569,8 @@ void ScColumn::ApplySelectionStyle(const ScStyleSheet& rStyle, const ScMarkData&
 
     if ( rMark.IsMultiMarked() )
     {
-        ScMarkArrayIter aMarkIter( rMark.GetArray() + nCol );
-        while (aMarkIter.Next( nTop, nBottom ))
+        ScMultiSelIter aMultiIter( rMark.GetMultiSelData(), nCol );
+        while (aMultiIter.Next( nTop, nBottom ))
             pAttrArray->ApplyStyleArea(nTop, nBottom, const_cast<ScStyleSheet*>(&rStyle));
     }
 }
@@ -586,8 +586,8 @@ void ScColumn::ApplySelectionLineStyle( const ScMarkData& rMark,
 
     if (rMark.IsMultiMarked())
     {
-        ScMarkArrayIter aMarkIter( rMark.GetArray()+nCol );
-        while (aMarkIter.Next( nTop, nBottom ))
+        ScMultiSelIter aMultiIter( rMark.GetMultiSelData(), nCol );
+        while (aMultiIter.Next( nTop, nBottom ))
             pAttrArray->ApplyLineStyleArea(nTop, nBottom, pLine, bColorOnly );
     }
 }
@@ -611,10 +611,10 @@ const ScStyleSheet* ScColumn::GetSelectionStyle( const ScMarkData& rMark, bool&
     const ScStyleSheet* pStyle = NULL;
     const ScStyleSheet* pNewStyle;
 
-    ScMarkArrayIter aMarkIter( rMark.GetArray() + nCol );
+    ScMultiSelIter aMultiIter( rMark.GetMultiSelData(), nCol );
     SCROW nTop;
     SCROW nBottom;
-    while (bEqual && aMarkIter.Next( nTop, nBottom ))
+    while (bEqual && aMultiIter.Next( nTop, nBottom ))
     {
         ScAttrIterator aAttrIter( pAttrArray, nTop, nBottom );
         SCROW nRow;
@@ -1631,7 +1631,7 @@ void ScColumn::CopyToColumn(
         SCROW nStart, nEnd;
         if (pMarkData && pMarkData->IsMultiMarked())
         {
-            ScMarkArrayIter aIter( pMarkData->GetArray()+nCol );
+            ScMultiSelIter aIter( pMarkData->GetMultiSelData(), nCol );
 
             while ( aIter.Next( nStart, nEnd ) && nStart <= nRow2 )
             {
@@ -3423,7 +3423,10 @@ SCsROW ScColumn::SearchStyle(
     if (bInSelection)
     {
         if (rMark.IsMultiMarked())
-            return pAttrArray->SearchStyle(nRow, pSearchStyle, bUp, rMark.GetArray()+nCol);
+        {
+            ScMarkArray aArray(rMark.GetMarkArray(nCol));
+            return pAttrArray->SearchStyle(nRow, pSearchStyle, bUp, &aArray);
+        }
         else
             return -1;
     }
@@ -3438,8 +3441,11 @@ bool ScColumn::SearchStyleRange(
     if (bInSelection)
     {
         if (rMark.IsMultiMarked())
+        {
+            ScMarkArray aArray(rMark.GetMarkArray(nCol));
             return pAttrArray->SearchStyleRange(
-                rRow, rEndRow, pSearchStyle, bUp, rMark.GetArray() + nCol);
+                rRow, rEndRow, pSearchStyle, bUp, &aArray);
+        }
         else
             return false;
     }
diff --git a/sc/source/core/data/column3.cxx b/sc/source/core/data/column3.cxx
index 0c8ac2b030b9..b522fecd90e7 100644
--- a/sc/source/core/data/column3.cxx
+++ b/sc/source/core/data/column3.cxx
@@ -1117,7 +1117,7 @@ void ScColumn::MixMarked(
 
     if (rMark.IsMultiMarked())
     {
-        ScMarkArrayIter aIter( rMark.GetArray()+nCol );
+        ScMultiSelIter aIter( rMark.GetMultiSelData(), nCol );
         while (aIter.Next( nRow1, nRow2 ))
             MixData(rCxt, nRow1, nRow2, nFunction, bSkipEmpty, rSrcCol);
     }
diff --git a/sc/source/core/data/fillinfo.cxx b/sc/source/core/data/fillinfo.cxx
index b30179698d8d..4197b3f647ec 100644
--- a/sc/source/core/data/fillinfo.cxx
+++ b/sc/source/core/data/fillinfo.cxx
@@ -620,17 +620,17 @@ void ScDocument::FillInfo(
                     if (pMarkData && pMarkData->IsMultiMarked())
                     {
                         //  Block marks
-                        const ScMarkArray* pThisMarkArr = pMarkData->GetArray()+nX;
+                        ScMarkArray aThisMarkArr(pMarkData->GetMarkArray( nX ));
                         nArrRow = 1;
                         nCurRow = nRow1;                                      // single rows
                         nThisRow = nRow1;                                     // End of range
 
-                        if ( pThisMarkArr->Search( nRow1, nIndex ) )
+                        if ( aThisMarkArr.Search( nRow1, nIndex ) )
                         {
                             do
                             {
-                                nThisRow=pThisMarkArr->pData[nIndex].nRow;      // End of range
-                                const bool bThisMarked=pThisMarkArr->pData[nIndex].bMarked;
+                                nThisRow=aThisMarkArr.pData[nIndex].nRow;      // End of range
+                                const bool bThisMarked=aThisMarkArr.pData[nIndex].bMarked;
 
                                 do
                                 {
@@ -657,7 +657,7 @@ void ScDocument::FillInfo(
                                 while (nCurRow <= nThisRow && nCurRow <= nRow2);
                                 ++nIndex;
                             }
-                            while ( nIndex < pThisMarkArr->nCount && nThisRow < nRow2 );
+                            while ( nIndex < aThisMarkArr.nCount && nThisRow < nRow2 );
                         }
                     }
                 }
@@ -797,10 +797,10 @@ void ScDocument::FillInfo(
                                     && nStartY <= (SCsROW) nBlockEndY );
                     if (pMarkData && pMarkData->IsMultiMarked() && !bCellMarked)
                     {
-                        const ScMarkArray* pThisMarkArr = pMarkData->GetArray()+nStartX;
+                        ScMarkArray aThisMarkArr(pMarkData->GetMarkArray( nStartX ));
                         SCSIZE nIndex;
-                        if ( pThisMarkArr->Search( nStartY, nIndex ) )
-                            bCellMarked=pThisMarkArr->pData[nIndex].bMarked;
+                        if ( aThisMarkArr.Search( nStartY, nIndex ) )
+                            bCellMarked=aThisMarkArr.pData[nIndex].bMarked;
                     }
 
                     pInfo->bMarked = bCellMarked;
diff --git a/sc/source/core/data/markarr.cxx b/sc/source/core/data/markarr.cxx
index 6a83437216fc..50ec4ba37dda 100644
--- a/sc/source/core/data/markarr.cxx
+++ b/sc/source/core/data/markarr.cxx
@@ -33,6 +33,17 @@ ScMarkArray::ScMarkArray() :
     // special case "no marks" with pData = NULL
 }
 
+// Move constructor
+ScMarkArray::ScMarkArray( ScMarkArray&& rArray ) :
+    nCount( rArray.nCount ),
+    nLimit( rArray.nLimit ),
+    pData( rArray.pData )
+{
+    rArray.nCount = 0;
+    rArray.nLimit = 0;
+    rArray.pData = nullptr;
+}
+
 ScMarkArray::~ScMarkArray()
 {
     delete[] pData;
diff --git a/sc/source/core/data/markdata.cxx b/sc/source/core/data/markdata.cxx
index 55537b23f12c..154a6938a204 100644
--- a/sc/source/core/data/markdata.cxx
+++ b/sc/source/core/data/markdata.cxx
@@ -19,19 +19,21 @@
 
 #include "markdata.hxx"
 #include "markarr.hxx"
+#include "markmulti.hxx"
 #include "rangelst.hxx"
+#include "segmenttree.hxx"
 #include <columnspanset.hxx>
 #include <fstalgorithm.hxx>
+#include <unordered_map>
 
 #include <osl/diagnose.h>
 
 #include <mdds/flat_segment_tree.hpp>
 
-// STATIC DATA -----------------------------------------------------------
 
 ScMarkData::ScMarkData() :
     maTabMarked(),
-    pMultiSel( NULL )
+    aMultiSel()
 {
     ResetMark();
 }
@@ -40,19 +42,16 @@ ScMarkData::ScMarkData(const ScMarkData& rData) :
     maTabMarked( rData.maTabMarked ),
     aMarkRange( rData.aMarkRange ),
     aMultiRange( rData.aMultiRange ),
-    pMultiSel( NULL )
+    aMultiSel( rData.aMultiSel ),
+    aTopEnvelope( rData.aTopEnvelope ),
+    aBottomEnvelope( rData.aBottomEnvelope ),
+    aLeftEnvelope( rData.aLeftEnvelope ),
+    aRightEnvelope( rData.aRightEnvelope )
 {
     bMarked      = rData.bMarked;
     bMultiMarked = rData.bMultiMarked;
     bMarking     = rData.bMarking;
     bMarkIsNeg   = rData.bMarkIsNeg;
-
-    if (rData.pMultiSel)
-    {
-        pMultiSel = new ScMarkArray[MAXCOLCOUNT];
-        for (SCCOL j=0; j<MAXCOLCOUNT; j++)
-            rData.pMultiSel[j].CopyMarksTo( pMultiSel[j] );
-    }
 }
 
 ScMarkData& ScMarkData::operator=(const ScMarkData& rData)
@@ -60,46 +59,43 @@ ScMarkData& ScMarkData::operator=(const ScMarkData& rData)
     if ( &rData == this )
         return *this;
 
-    delete[] pMultiSel;
-    pMultiSel = NULL;
-
     aMarkRange   = rData.aMarkRange;
     aMultiRange  = rData.aMultiRange;
     bMarked      = rData.bMarked;
     bMultiMarked = rData.bMultiMarked;
     bMarking     = rData.bMarking;
     bMarkIsNeg   = rData.bMarkIsNeg;
+    aTopEnvelope = rData.aTopEnvelope;
+    aBottomEnvelope = rData.aBottomEnvelope;
+    aLeftEnvelope   = rData.aLeftEnvelope;
+    aRightEnvelope  = rData.aRightEnvelope;
 
     maTabMarked = rData.maTabMarked;
-
-    if (rData.pMultiSel)
-    {
-        pMultiSel = new ScMarkArray[MAXCOLCOUNT];
-        for (SCCOL j=0; j<MAXCOLCOUNT; j++)
-            rData.pMultiSel[j].CopyMarksTo( pMultiSel[j] );
-    }
+    aMultiSel = rData.aMultiSel;
 
     return *this;
 }
 
 ScMarkData::~ScMarkData()
 {
-    delete[] pMultiSel;
 }
 
 void ScMarkData::ResetMark()
 {
-    delete[] pMultiSel;
-    pMultiSel = NULL;
+    aMultiSel.Clear();
 
     bMarked = bMultiMarked = false;
     bMarking = bMarkIsNeg = false;
+    aTopEnvelope.RemoveAll();
+    aBottomEnvelope.RemoveAll();
+    aLeftEnvelope.RemoveAll();
+    aRightEnvelope.RemoveAll();
 }
 
 void ScMarkData::SetMarkArea( const ScRange& rRange )
 {
     aMarkRange = rRange;
-    aMarkRange.Justify();
+    aMarkRange.PutInOrder();
     if ( !bMarked )
     {
         // Upon creation of a document ScFormatShell GetTextAttrState
@@ -121,17 +117,18 @@ void ScMarkData::GetMultiMarkArea( ScRange& rRange ) const
     rRange = aMultiRange;
 }
 
-void ScMarkData::SetMultiMarkArea( const ScRange& rRange, bool bMark )
+void ScMarkData::SetMultiMarkArea( const ScRange& rRange, bool bMark, bool bSetupMulti )
 {
-    if (!pMultiSel)
+    if ( aMultiSel.IsEmpty() )
     {
-        pMultiSel = new ScMarkArray[MAXCOL+1];
-
         // if simple mark range is set, copy to multi marks
-        if ( bMarked && !bMarkIsNeg )
+        if ( bMarked && !bMarkIsNeg && !bSetupMulti )
         {
             bMarked = false;
-            SetMultiMarkArea( aMarkRange, true );
+            SCCOL nStartCol = aMarkRange.aStart.Col();
+            SCCOL nEndCol = aMarkRange.aEnd.Col();
+            PutInOrder( nStartCol, nEndCol );
+            SetMultiMarkArea( aMarkRange, true, true );
         }
     }
 
@@ -142,9 +139,7 @@ void ScMarkData::SetMultiMarkArea( const ScRange& rRange, bool bMark )
     PutInOrder( nStartRow, nEndRow );
     PutInOrder( nStartCol, nEndCol );
 
-    SCCOL nCol;
-    for (nCol=nStartCol; nCol<=nEndCol; nCol++)
-        pMultiSel[nCol].SetMarkArea( nStartRow, nEndRow, bMark );
+    aMultiSel.SetMarkArea( nStartCol, nEndCol, nStartRow, nEndRow, bMark );
 
     if ( bMultiMarked )                 // Update aMultiRange
     {
@@ -247,27 +242,25 @@ void ScMarkData::MarkToSimple()
 
     if ( bMultiMarked )
     {
-        OSL_ENSURE(pMultiSel, "bMultiMarked, but pMultiSel == 0");
-
         ScRange aNew = aMultiRange;
 
         bool bOk = false;
         SCCOL nStartCol = aNew.aStart.Col();
         SCCOL nEndCol   = aNew.aEnd.Col();
 
-        while ( nStartCol < nEndCol && !pMultiSel[nStartCol].HasMarks() )
+        while ( nStartCol < nEndCol && !aMultiSel.HasMarks( nStartCol ) )
             ++nStartCol;
-        while ( nStartCol < nEndCol && !pMultiSel[nEndCol].HasMarks() )
+        while ( nStartCol < nEndCol && !aMultiSel.HasMarks( nEndCol ) )
             --nEndCol;
 
         // Rows are only taken from MarkArray
         SCROW nStartRow, nEndRow;
-        if ( pMultiSel[nStartCol].HasOneMark( nStartRow, nEndRow ) )
+        if ( aMultiSel.HasOneMark( nStartCol, nStartRow, nEndRow ) )
         {
             bOk = true;
             SCROW nCmpStart, nCmpEnd;
             for (SCCOL nCol=nStartCol+1; nCol<=nEndCol && bOk; nCol++)
-                if ( !pMultiSel[nCol].HasOneMark( nCmpStart, nCmpEnd )
+                if ( !aMultiSel.HasOneMark( nCol, nCmpStart, nCmpEnd )
                         || nCmpStart != nStartRow || nCmpEnd != nEndRow )
                     bOk = false;
         }
@@ -298,8 +291,7 @@ bool ScMarkData::IsCellMarked( SCCOL nCol, SCROW nRow, bool bNoSimple ) const
     {
         //TODO: test here for negative Marking ?
 
-        OSL_ENSURE(pMultiSel, "bMultiMarked, but pMultiSel == 0");
-        return pMultiSel[nCol].GetMark( nRow );
+        return aMultiSel.GetMark( nCol, nRow );
     }
 
     return false;
@@ -315,7 +307,7 @@ bool ScMarkData::IsColumnMarked( SCCOL nCol ) const
                     aMarkRange.aStart.Row() == 0    && aMarkRange.aEnd.Row() == MAXROW )
         return true;
 
-    if ( bMultiMarked && pMultiSel[nCol].IsAllMarked(0,MAXROW) )
+    if ( bMultiMarked && aMultiSel.IsAllMarked( nCol, 0, MAXROW ) )
         return true;
 
     return false;
@@ -332,13 +324,7 @@ bool ScMarkData::IsRowMarked( SCROW nRow ) const
         return true;
 
     if ( bMultiMarked )
-    {
-        OSL_ENSURE(pMultiSel, "bMultiMarked, but pMultiSel == 0");
-        for (SCCOL nCol=0; nCol<=MAXCOL; nCol++)
-            if (!pMultiSel[nCol].GetMark(nRow))
-                return false;
-        return true;
-    }
+        return aMultiSel.IsRowMarked( nRow );
 
     return false;
 }
@@ -363,7 +349,7 @@ void ScMarkData::MarkFromRangeList( const ScRangeList& rList, bool bReset )
         for (size_t i=0; i < nCount; i++)
         {
             const ScRange& rRange = *rList[ i ];
-            SetMultiMarkArea( rRange, true );
+            SetMultiMarkArea( rRange );
             SelectTable( rRange.aStart.Tab(), true );
         }
     }
@@ -377,19 +363,17 @@ void ScMarkData::FillRangeListWithMarks( ScRangeList* pList, bool bClear ) const
     if (bClear)
         pList->RemoveAll();
 
-    //TODO: for muliple selected tables enter multiple ranges !!!
+    //TODO: for multiple selected tables enter multiple ranges !!!
 
     if ( bMultiMarked )
     {
-        OSL_ENSURE(pMultiSel, "bMultiMarked, but pMultiSel == 0");
-
         SCTAB nTab = aMultiRange.aStart.Tab();
 
         SCCOL nStartCol = aMultiRange.aStart.Col();
         SCCOL nEndCol = aMultiRange.aEnd.Col();
         for (SCCOL nCol=nStartCol; nCol<=nEndCol; nCol++)
         {
-            if (pMultiSel[nCol].HasMarks())
+            if (aMultiSel.HasMarks( nCol ))
             {
                 // Feeding column-wise fragments to ScRangeList::Join() is a
                 // huge bottleneck, speed this up for multiple columns
@@ -399,14 +383,14 @@ void ScMarkData::FillRangeListWithMarks( ScRangeList* pList, bool bClear ) const
                 SCCOL nToCol = nCol+1;
                 for ( ; nToCol <= nEndCol; ++nToCol)
                 {
-                    if (!pMultiSel[nCol].HasEqualRowsMarked( pMultiSel[nToCol]))
+                    if (!aMultiSel.HasEqualRowsMarked(nCol, nToCol))
                         break;
                 }
                 --nToCol;
                 ScRange aRange( nCol, 0, nTab, nToCol, 0, nTab );
                 SCROW nTop, nBottom;
-                ScMarkArrayIter aMarkIter( &pMultiSel[nCol] );
-                while ( aMarkIter.Next( nTop, nBottom ) )
+                ScMultiSelIter aMultiIter( aMultiSel, nCol );
+                while ( aMultiIter.Next( nTop, nBottom ) )
                 {
                     aRange.aStart.SetRow( nTop );
                     aRange.aEnd.SetRow( nBottom );
@@ -486,15 +470,17 @@ bool ScMarkData::IsAllMarked( const ScRange& rRange ) const
     if ( !bMultiMarked )
         return false;
 
-    OSL_ENSURE(pMultiSel, "bMultiMarked, but pMultiSel == 0");
-
     SCCOL nStartCol = rRange.aStart.Col();
     SCROW nStartRow = rRange.aStart.Row();
     SCCOL nEndCol = rRange.aEnd.Col();
     SCROW nEndRow = rRange.aEnd.Row();
     bool bOk = true;
+
+    if ( nStartCol == 0 && nEndCol == MAXCOL )
+        return aMultiSel.IsRowRangeMarked( nStartRow, nEndRow );
+
     for (SCCOL nCol=nStartCol; nCol<=nEndCol && bOk; nCol++)
-        if ( !pMultiSel[nCol].IsAllMarked( nStartRow, nEndRow ) )
+        if ( !aMultiSel.IsAllMarked( nCol, nStartRow, nEndRow ) )
             bOk = false;
 
     return bOk;
@@ -505,9 +491,7 @@ SCsROW ScMarkData::GetNextMarked( SCCOL nCol, SCsROW nRow, bool bUp ) const
     if ( !bMultiMarked )
         return nRow;
 
-    OSL_ENSURE(pMultiSel, "bMultiMarked, but pMultiSel == 0");
-
-    return pMultiSel[nCol].GetNextMarked( nRow, bUp );
+    return aMultiSel.GetNextMarked( nCol, nRow, bUp );
 }
 
 bool ScMarkData::HasMultiMarks( SCCOL nCol ) const
@@ -515,9 +499,7 @@ bool ScMarkData::HasMultiMarks( SCCOL nCol ) const
     if ( !bMultiMarked )
         return false;
 
-    OSL_ENSURE(pMultiSel, "bMultiMarked, but pMultiSel == 0");
-
-    return pMultiSel[nCol].HasMarks();
+    return aMultiSel.HasMarks( nCol );
 }
 
 bool ScMarkData::HasAnyMultiMarks() const
@@ -525,13 +507,7 @@ bool ScMarkData::HasAnyMultiMarks() const
     if ( !bMultiMarked )
         return false;
 
-    OSL_ENSURE(pMultiSel, "bMultiMarked, but pMultiSel == 0");
-
-    for (SCCOL nCol=0; nCol<=MAXCOL; nCol++)
-        if ( pMultiSel[nCol].HasMarks() )
-            return true;
-
-    return false;       // no
+    return aMultiSel.HasAnyMarks();
 }
 
 void ScMarkData::InsertTab( SCTAB nTab )
@@ -553,6 +529,261 @@ void ScMarkData::DeleteTab( SCTAB nTab )
     maTabMarked.swap(tabMarked);
 }
 
+static void lcl_AddRanges(ScRange& rRangeDest, const ScRange& rNewRange )
+{
+    SCCOL nStartCol = rNewRange.aStart.Col();
+    SCROW nStartRow = rNewRange.aStart.Row();
+    SCCOL nEndCol = rNewRange.aEnd.Col();
+    SCROW nEndRow = rNewRange.aEnd.Row();
+    PutInOrder( nStartRow, nEndRow );
+    PutInOrder( nStartCol, nEndCol );
+    if ( nStartCol < rRangeDest.aStart.Col() )
+        rRangeDest.aStart.SetCol( nStartCol );
+    if ( nStartRow < rRangeDest.aStart.Row() )
+        rRangeDest.aStart.SetRow( nStartRow );
+    if ( nEndCol > rRangeDest.aEnd.Col() )
+        rRangeDest.aEnd.SetCol( nEndCol );
+    if ( nEndRow > rRangeDest.aEnd.Row() )
+        rRangeDest.aEnd.SetRow( nEndRow );
+}
+
+void ScMarkData::GetSelectionCover( ScRange& rRange )
+{
+    if( bMultiMarked )
+    {
+        rRange = aMultiRange;
+        SCCOL nStartCol = aMultiRange.aStart.Col(), nEndCol = aMultiRange.aEnd.Col();
+        PutInOrder( nStartCol, nEndCol );
+        nStartCol = ( nStartCol == 0 ) ? nStartCol : nStartCol - 1;
+        nEndCol = ( nEndCol == MAXCOL ) ? nEndCol : nEndCol + 1;
+        std::unique_ptr<ScFlatBoolRowSegments> pPrevColMarkedRows;
+        std::unique_ptr<ScFlatBoolRowSegments> pCurColMarkedRows;
+        std::unordered_map<SCROW,ScFlatBoolColSegments> aRowToColSegmentsInTopEnvelope;
+        std::unordered_map<SCROW,ScFlatBoolColSegments> aRowToColSegmentsInBottomEnvelope;
+        ScFlatBoolRowSegments aNoRowsMarked;
+        aNoRowsMarked.setFalse( 0, MAXROW );
+
+        bool bPrevColUnMarked = false;
+
+        for ( SCCOL nCol=nStartCol; nCol <= nEndCol; nCol++ )
+        {
+            SCROW nTop, nBottom;
+            bool bCurColUnMarked = !aMultiSel.HasMarks( nCol );
+            if ( !bCurColUnMarked )
+            {
+                pCurColMarkedRows.reset( new ScFlatBoolRowSegments() );
+                pCurColMarkedRows->setFalse( 0, MAXROW );
+                ScMultiSelIter aMultiIter( aMultiSel, nCol );
+                ScFlatBoolRowSegments::ForwardIterator aPrevItr ( pPrevColMarkedRows.get() ? *pPrevColMarkedRows : aNoRowsMarked ); // For finding left envelope
+                ScFlatBoolRowSegments::ForwardIterator aPrevItr1( pPrevColMarkedRows.get() ? *pPrevColMarkedRows : aNoRowsMarked ); // For finding right envelope
+                SCROW nTopPrev = 0, nBottomPrev = 0; // For right envelope
+                while ( aMultiIter.Next( nTop, nBottom ) )
+                {
+                    pCurColMarkedRows->setTrue( nTop, nBottom );
+                    if( bPrevColUnMarked && ( nCol > nStartCol ))
+                    {
+                        ScRange aAddRange(nCol - 1, nTop, aMultiRange.aStart.Tab(),
+                                          nCol - 1, nBottom, aMultiRange.aStart.Tab());
+                        lcl_AddRanges( rRange, aAddRange ); // Left envelope
+                        aLeftEnvelope.Append( aAddRange );
+                    }
+                    else if( nCol > nStartCol )
+                    {
+                        SCROW nTop1 = nTop, nBottom1 = nTop;
+                        while( nTop1 <= nBottom && nBottom1 <= nBottom )
+                        {
+                            bool bRangeMarked = false;
+                            aPrevItr.getValue( nTop1, bRangeMarked );
+                            if( bRangeMarked )
+                            {
+                                nTop1 = aPrevItr.getLastPos() + 1;
+                                nBottom1 = nTop1;
+                            }
+                            else
+                            {
+                                nBottom1 = aPrevItr.getLastPos();
+                                if( nBottom1 > nBottom )
+                                    nBottom1 = nBottom;
+                                ScRange aAddRange( nCol - 1, nTop1, aMultiRange.aStart.Tab(),
+                                                   nCol - 1, nBottom1, aMultiRange.aStart.Tab() );
+                                lcl_AddRanges( rRange, aAddRange ); // Left envelope
+                                aLeftEnvelope.Append( aAddRange );
+                                nTop1 = ++nBottom1;
+                            }
+                        }
+                        while( nTopPrev <= nBottom && nBottomPrev <= nBottom )
+                        {
+                            bool bRangeMarked;
+                            aPrevItr1.getValue( nTopPrev, bRangeMarked );
+                            if( bRangeMarked )
+                            {
+                                nBottomPrev = aPrevItr1.getLastPos();
+                                if( nTopPrev < nTop )
+                                {
+                                    if( nBottomPrev >= nTop )
+                                    {
+                                        nBottomPrev = nTop - 1;
+                                        ScRange aAddRange( nCol, nTopPrev, aMultiRange.aStart.Tab(),
+                                                           nCol, nBottomPrev, aMultiRange.aStart.Tab());
+                                        lcl_AddRanges( rRange, aAddRange ); // Right envelope
+                                        aRightEnvelope.Append( aAddRange );
+                                        nTopPrev = nBottomPrev = (nBottom + 1);
+                                    }
+                                    else
+                                    {
+                                        ScRange aAddRange( nCol, nTopPrev, aMultiRange.aStart.Tab(),
+                                                           nCol, nBottomPrev, aMultiRange.aStart.Tab());
+                                        lcl_AddRanges( rRange, aAddRange ); // Right envelope
+                                        aRightEnvelope.Append( aAddRange );
+                                        nTopPrev = ++nBottomPrev;
+                                    }
+                                }
+                                else
+                                    nTopPrev = nBottomPrev = ( nBottom + 1 );
+                            }
+                            else
+                            {
+                                nBottomPrev = aPrevItr1.getLastPos();
+                                nTopPrev = ++nBottomPrev;
+                            }
+                        }
+                    }
+                    if( nTop )
+                    {
+                        ScRange aAddRange( nCol, nTop - 1, aMultiRange.aStart.Tab(),
+                                           nCol, nTop - 1, aMultiRange.aStart.Tab());
+                        lcl_AddRanges( rRange, aAddRange ); // Top envelope
+                        aRowToColSegmentsInTopEnvelope[nTop - 1].setTrue( nCol, nCol );
+                    }
+                    if( nBottom < MAXROW )
+                    {
+                        ScRange aAddRange(nCol, nBottom + 1, aMultiRange.aStart.Tab(),
+                                          nCol, nBottom + 1, aMultiRange.aStart.Tab());
+                        lcl_AddRanges( rRange, aAddRange ); // Bottom envelope
+                        aRowToColSegmentsInBottomEnvelope[nBottom + 1].setTrue( nCol, nCol );
+                    }
+                }
+
+                while( nTopPrev <= MAXROW && nBottomPrev <= MAXROW && ( nCol > nStartCol ) )
+                {
+                    bool bRangeMarked;
+                    aPrevItr1.getValue( nTopPrev, bRangeMarked );
+                    if( bRangeMarked )
+                    {
+                        nBottomPrev = aPrevItr1.getLastPos();
+                        ScRange aAddRange(nCol, nTopPrev, aMultiRange.aStart.Tab(),
+                                          nCol, nBottomPrev, aMultiRange.aStart.Tab());
+                        lcl_AddRanges( rRange, aAddRange ); // Right envelope
+                        aRightEnvelope.Append( aAddRange );
+                        nTopPrev = ++nBottomPrev;
+                    }
+                    else
+                    {
+                        nBottomPrev = aPrevItr1.getLastPos();
+                        nTopPrev = ++nBottomPrev;
+                    }
+                }
+            }
+            else if( nCol > nStartCol )
+            {
+                bPrevColUnMarked = true;
+                SCROW nTopPrev = 0, nBottomPrev = 0;
+                bool bRangeMarked = false;
+                ScFlatBoolRowSegments::ForwardIterator aPrevItr( pPrevColMarkedRows.get() ? *pPrevColMarkedRows : aNoRowsMarked );
+                while( nTopPrev <= MAXROW && nBottomPrev <= MAXROW )
+                {
+                    aPrevItr.getValue(nTopPrev, bRangeMarked);
+                    if( bRangeMarked )
+                    {
+                        nBottomPrev = aPrevItr.getLastPos();
+                        ScRange aAddRange(nCol, nTopPrev, aMultiRange.aStart.Tab(),
+                                          nCol, nBottomPrev, aMultiRange.aStart.Tab());
+                        lcl_AddRanges( rRange, aAddRange ); // Right envelope
+                        aRightEnvelope.Append( aAddRange );
+                        nTopPrev = ++nBottomPrev;
+                    }
+                    else
+                    {
+                        nBottomPrev = aPrevItr.getLastPos();
+                        nTopPrev = ++nBottomPrev;
+                    }
+                }
+            }
+            if ( bCurColUnMarked )
+                pPrevColMarkedRows.reset( nullptr );
+            else
+                pPrevColMarkedRows.reset( pCurColMarkedRows.release() );
+        }
+        for( auto& rKV : aRowToColSegmentsInTopEnvelope )
+        {
+            SCCOL nStart = nStartCol;
+            ScFlatBoolColSegments::RangeData aRange;
+            while( nStart <= nEndCol )
+            {
+                if( !rKV.second.getRangeData( nStart, aRange ) )
+                    break;
+                if( aRange.mbValue ) // is marked
+                    aTopEnvelope.Append( ScRange( aRange.mnCol1, rKV.first, aMultiRange.aStart.Tab(),
+                                                  aRange.mnCol2, rKV.first, aMultiRange.aStart.Tab() ) );
+                nStart = aRange.mnCol2 + 1;
+            }
+        }
+        for( auto& rKV : aRowToColSegmentsInBottomEnvelope )
+        {
+            SCCOL nStart = nStartCol;
+            ScFlatBoolColSegments::RangeData aRange;
+            while( nStart <= nEndCol )
+            {
+                if( !rKV.second.getRangeData( nStart, aRange ) )
+                    break;
+                if( aRange.mbValue ) // is marked
+                    aBottomEnvelope.Append( ScRange( aRange.mnCol1, rKV.first, aMultiRange.aStart.Tab(),
+                                                     aRange.mnCol2, rKV.first, aMultiRange.aStart.Tab() ) );
+                nStart = aRange.mnCol2 + 1;
+            }
+        }
+    }
+    else if( bMarked )
+    {
+        aMarkRange.PutInOrder();
+        SCROW nRow1, nRow2, nRow1New, nRow2New;
+        SCCOL nCol1, nCol2, nCol1New, nCol2New;
+        SCTAB nTab1, nTab2;
+        aMarkRange.GetVars( nCol1, nRow1, nTab1, nCol2, nRow2, nTab2 );
+        nCol1New = nCol1;
+        nCol2New = nCol2;
+        nRow1New = nRow1;
+        nRow2New = nRow2;
+        // Each envelope will have zero or more ranges for single rectangle selection.
+        if( nCol1 > 0 )
+        {
+            aLeftEnvelope.Append( ScRange( nCol1 - 1, nRow1, nTab1, nCol1 - 1, nRow2, nTab2 ) );
+            --nCol1New;
+        }
+        if( nRow1 > 0 )
+        {
+            aTopEnvelope.Append( ScRange( nCol1, nRow1 - 1, nTab1, nCol2, nRow1 - 1, nTab2 ) );
+            --nRow1New;
+        }
+        if( nCol2 < MAXCOL )
+        {
+            aRightEnvelope.Append( ScRange( nCol2 + 1, nRow1, nTab1, nCol2 + 1, nRow2, nTab2 ) );
+            ++nCol2New;
+        }
+        if( nRow2 < MAXROW )
+        {
+            aBottomEnvelope.Append( ScRange( nCol1, nRow2 + 1, nTab1, nCol2, nRow2 + 1, nTab2 ) );
+            ++nRow2New;
+        }
+        rRange = ScRange( nCol1New, nRow1New, nTab1, nCol2New, nRow2New, nTab2 );
+    }
+}
+
+ScMarkArray ScMarkData::GetMarkArray( SCCOL nCol ) const
+{
+    return aMultiSel.GetMarkArray( nCol );
+}
+
 //iterators
 ScMarkData::iterator ScMarkData::begin()
 {
diff --git a/sc/source/core/data/markmulti.cxx b/sc/source/core/data/markmulti.cxx
new file mode 100644
index 000000000000..07502c12dccc
--- /dev/null
+++ b/sc/source/core/data/markmulti.cxx
@@ -0,0 +1,348 @@
+/* -*- 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/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   Licensed to the Apache Software Foundation (ASF) under one or more
+ *   contributor license agreements. See the NOTICE file distributed
+ *   with this work for additional information regarding copyright
+ *   ownership. The ASF licenses this file to you under the Apache
+ *   License, Version 2.0 (the "License"); you may not use this file
+ *   except in compliance with the License. You may obtain a copy of
+ *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#include "markmulti.hxx"
+#include "markarr.hxx"
+#include "segmenttree.hxx"
+
+#include <algorithm>
+
+ScMultiSel::ScMultiSel():
+    aMultiSelContainer(),
+    aRowSel()
+{
+}
+
+ScMultiSel::ScMultiSel( const ScMultiSel& rMultiSel )
+{
+    MapType::iterator aDestEnd = aMultiSelContainer.end();
+    MapType::iterator aDestIter = aDestEnd;
+    for ( const auto& aSourcePair : rMultiSel.aMultiSelContainer )
+    {
+        // correct hint is always aDestEnd as keys come in ascending order
+        // Amortized constant time operation as we always give the correct hint
+        aDestIter = aMultiSelContainer.emplace_hint( aDestEnd, aSourcePair.first, ScMarkArray() );
+        aSourcePair.second.CopyMarksTo( aDestIter->second );
+    }
+    rMultiSel.aRowSel.CopyMarksTo( aRowSel );
+}
+
+ScMultiSel::~ScMultiSel()
+{
+}
+
+ScMultiSel& ScMultiSel::operator=(const ScMultiSel& rMultiSel)
+{
+    Clear();
+    MapType::iterator aDestEnd = aMultiSelContainer.end();
+    MapType::iterator aDestIter = aDestEnd;
+    for ( const auto& aSourcePair : rMultiSel.aMultiSelContainer )
+    {
+        // correct hint is always aDestEnd as keys come in ascending order
+        // Amortized constant time operation as we always give the correct hint
+        aDestIter = aMultiSelContainer.emplace_hint( aDestEnd, aSourcePair.first, ScMarkArray() );
+        aSourcePair.second.CopyMarksTo( aDestIter->second );
+    }
+    rMultiSel.aRowSel.CopyMarksTo( aRowSel );
+    return *this;
+}
+
+void ScMultiSel::Clear()
+{
+    aMultiSelContainer.clear();
+    aRowSel.Reset();
+}
+
+bool ScMultiSel::HasMarks( SCCOL nCol ) const
+{
+    if ( aRowSel.HasMarks() )
+        return true;
+    MapType::const_iterator aIter = aMultiSelContainer.find( nCol );
+    if ( aIter == aMultiSelContainer.end() )
+        return false;
+    return aIter->second.HasMarks();
+}
+
+bool ScMultiSel::HasOneMark( SCCOL nCol, SCROW& rStartRow, SCROW& rEndRow ) const
+{
+    bool aResult1 = false, aResult2 = false;
+    SCROW nRow1 = -1, nRow2 = -1, nRow3 = -1, nRow4 = -1;
+    aResult1 = aRowSel.HasOneMark( nRow1, nRow2 );
+    MapType::const_iterator aIter = aMultiSelContainer.find( nCol );
+    if ( aIter != aMultiSelContainer.end() )
+        aResult2 = aIter->second.HasOneMark( nRow3, nRow4 );
+
+    if ( aResult1 || aResult2 )
+    {
+        if ( aResult1 && aResult2 )
+        {
+            if ( ( nRow2 + 1 ) < nRow3 )
+                return false;
+            if ( ( nRow4 + 1 ) < nRow1 )
+                return false;
+
+            auto aRows = std::minmax( { nRow1, nRow2, nRow3, nRow4 } );
+            rStartRow = aRows.first;
+            rEndRow = aRows.second;
+            return true;
+        }
+        if ( aResult1 )
+        {
+            rStartRow = nRow1;
+            rEndRow = nRow2;
+            return true;
+        }
+
+        rStartRow = nRow3;
+        rEndRow = nRow4;
+        return true;
+    }
+
+    return false;
+}
+
+bool ScMultiSel::GetMark( SCCOL nCol, SCROW nRow ) const
+{
+    if ( aRowSel.GetMark( nRow ) )
+        return true;
+    MapType::const_iterator aIter = aMultiSelContainer.find( nCol );
+    if ( aIter != aMultiSelContainer.end() )
+        return aIter->second.GetMark( nRow );
+    return false;
+}
+
+bool ScMultiSel::IsAllMarked( SCCOL nCol, SCROW nStartRow, SCROW nEndRow ) const
+{
+    bool bHasMarks1 = aRowSel.HasMarks();
+    MapType::const_iterator aIter = aMultiSelContainer.find( nCol );
+    bool bHasMarks2 = ( aIter != aMultiSelContainer.end() && aIter->second.HasMarks() );
+
+    if ( !bHasMarks1 && !bHasMarks2 )
+        return false;
+
+    if ( bHasMarks1 && bHasMarks2 )
+    {
+        if ( aRowSel.IsAllMarked( nStartRow, nEndRow ) ||
+             aIter->second.IsAllMarked( nStartRow, nEndRow ) )
+            return true;
+        ScMultiSelIter aMultiIter( *this, nCol );
+        ScFlatBoolRowSegments::RangeData aRowRange;
+        aMultiIter.GetRowSegments().getRangeData( nStartRow, aRowRange );
+        return ( aRowRange.mbValue && aRowRange.mnRow2 >= nEndRow );
+    }
+
+    if ( bHasMarks1 )
+        return aRowSel.IsAllMarked( nStartRow, nEndRow );
+
+    return aIter->second.IsAllMarked( nStartRow, nEndRow );
+}
+
+bool ScMultiSel::HasEqualRowsMarked( SCCOL nCol1, SCCOL nCol2 ) const
+{
+    MapType::const_iterator aIter1 = aMultiSelContainer.find( nCol1 );
+    MapType::const_iterator aIter2 = aMultiSelContainer.find( nCol2 );
+    MapType::const_iterator aEnd = aMultiSelContainer.end();
+    bool bCol1Exists = ( aIter1 != aEnd );
+    bool bCol2Exists = ( aIter2 != aEnd );
+    if ( bCol1Exists || bCol2Exists )
+    {
+        if ( bCol1Exists && bCol2Exists )
+            return aIter1->second.HasEqualRowsMarked( aIter2->second );
+        else if ( bCol1Exists )
+            return !aIter1->second.HasMarks();
+        else
+            return !aIter2->second.HasMarks();
+    }
+
+    return true;
+}
+
+SCsROW ScMultiSel::GetNextMarked( SCCOL nCol, SCsROW nRow, bool bUp ) const
+{
+    MapType::const_iterator aIter = aMultiSelContainer.find( nCol );
+    if ( aIter == aMultiSelContainer.end() )
+        return aRowSel.GetNextMarked( nRow, bUp );
+
+    SCsROW nRow1, nRow2;
+    nRow1 = aRowSel.GetNextMarked( nRow, bUp );
+    nRow2 = aIter->second.GetNextMarked( nRow, bUp );
+    if ( nRow1 == nRow2 )
+        return nRow1;
+    if ( nRow1 == -1 )
+        return nRow2;
+    if ( nRow2 == -1 )
+        return nRow1;
+
+    PutInOrder( nRow1, nRow2 );
+    return ( bUp ? nRow2 : nRow1 );
+}
+
+void ScMultiSel::MarkAllCols( SCROW nStartRow, SCROW nEndRow )
+{
+    MapType::iterator aIter = aMultiSelContainer.end();
+    for ( SCCOL nCol = MAXCOL; nCol >= 0; --nCol )
+    {
+        aIter = aMultiSelContainer.emplace_hint( aIter, nCol, ScMarkArray() );
+        aIter->second.SetMarkArea( nStartRow, nEndRow, true );
+    }
+}
+
+void ScMultiSel::SetMarkArea( SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, SCROW nEndRow, bool bMark )
+{
+    if ( nStartCol == 0 && nEndCol == MAXCOL )
+    {
+        aRowSel.SetMarkArea( nStartRow, nEndRow, bMark );
+        if ( !bMark )
+        {
+            // Remove any per column marks for the row range.
+            for ( auto& aIter : aMultiSelContainer )
+                if ( aIter.second.HasMarks() )
+                    aIter.second.SetMarkArea( nStartRow, nEndRow, false );
+        }
+        return;
+    }
+
+    // Bad case - we need to extend aMultiSelContainer size to MAXCOL
+    // and move row marks from aRowSel to aMultiSelContainer
+    if ( !bMark && aRowSel.HasMarks() )
+    {
+        SCROW nBeg, nLast = nEndRow + 1;
+        if ( aRowSel.GetMark( nStartRow ) )
+        {
+            nBeg = nStartRow;
+            nLast = aRowSel.GetMarkEnd( nStartRow, false );
+        }
+        else
+        {
+            nBeg = aRowSel.GetNextMarked( nStartRow, false );
+            if ( nBeg != MAXROWCOUNT )
+                nLast = aRowSel.GetMarkEnd( nBeg, false );
+        }
+
+        if ( nBeg != MAXROWCOUNT && nLast >= nEndRow )
+            MarkAllCols( nBeg, nEndRow );
+        else
+        {
+            while ( nBeg != MAXROWCOUNT && nLast < nEndRow )
+            {
+                MarkAllCols( nBeg, nLast );
+                nBeg = aRowSel.GetNextMarked( nLast + 1, false );
+                if ( nBeg != MAXROWCOUNT )
+                    nLast = aRowSel.GetMarkEnd( nBeg, false );
+            }
+            if ( nBeg != MAXROWCOUNT && nLast >= nEndRow )
+                MarkAllCols( nBeg, nEndRow );
+        }
+
+        aRowSel.SetMarkArea( nStartRow, nEndRow, false );
+    }
+
+    MapType::iterator aIter = aMultiSelContainer.end();
+    for ( SCCOL nColIter = nEndCol; nColIter >= nStartCol; --nColIter )
+    {
+        // First hint is usually off, so the first emplace operation will take upto
+        // logarithmic in map size, all other iterations will take only constant time.
+        aIter = aMultiSelContainer.emplace_hint( aIter, nColIter, ScMarkArray() );
+        aIter->second.SetMarkArea( nStartRow, nEndRow, bMark );
+    }
+}
+
+bool ScMultiSel::IsRowMarked( SCROW nRow ) const
+{
+    return aRowSel.GetMark( nRow );
+}
+
+bool ScMultiSel::IsRowRangeMarked( SCROW nStartRow, SCROW nEndRow ) const
+{
+    if ( !aRowSel.GetMark( nStartRow ) )
+        return false;
+    SCROW nLast = aRowSel.GetMarkEnd( nStartRow, false );
+    return ( nLast >= nEndRow );
+}
+
+ScMarkArray ScMultiSel::GetMarkArray( SCCOL nCol ) const
+{
+    ScMultiSelIter aMultiIter( *this, nCol );
+    ScMarkArray aMarkArray;
+    SCROW nTop, nBottom;
+    while( aMultiIter.Next( nTop, nBottom ) )
+        aMarkArray.SetMarkArea( nTop, nBottom, true );
+    return aMarkArray;
+}
+
+bool ScMultiSel::HasAnyMarks() const
+{
+    if ( aRowSel.HasMarks() )
+        return true;
+    for ( const auto& aPair : aMultiSelContainer )
+        if ( aPair.second.HasMarks() )
+            return true;
+    return false;
+}
+
+ScMultiSelIter::ScMultiSelIter( const ScMultiSel& rMultiSel, SCCOL nCol ) :
+    aRowSegs(),
+    nNextSegmentStart(0)
+{
+    aRowSegs.setFalse( 0, MAXROW );
+    bool bHasMarks1 = rMultiSel.aRowSel.HasMarks();
+    ScMultiSel::MapType::const_iterator aIter = rMultiSel.aMultiSelContainer.find( nCol );
+    bool bHasMarks2 = ( ( aIter != rMultiSel.aMultiSelContainer.end() ) && aIter->second.HasMarks() );
+
+    if ( bHasMarks1 )
+    {
+        ScMarkArrayIter aMarkIter( &rMultiSel.aRowSel );
+        SCROW nTop, nBottom;
+        while ( aMarkIter.Next( nTop, nBottom ) )
+            aRowSegs.setTrue( nTop, nBottom );
+    }
+
+    if ( bHasMarks2 )
+    {
+        ScMarkArrayIter aMarkIter( &aIter->second );
+        SCROW nTop, nBottom;
+        while ( aMarkIter.Next( nTop, nBottom ) )
+            aRowSegs.setTrue( nTop, nBottom );
+    }
+
+}
+
+ScMultiSelIter::~ScMultiSelIter()
+{
+}
+
+bool ScMultiSelIter::Next( SCROW& rTop, SCROW& rBottom )
+{
+    ScFlatBoolRowSegments::RangeData aRowRange;
+    bool bRet = aRowSegs.getRangeData( nNextSegmentStart, aRowRange );
+    if ( bRet && !aRowRange.mbValue )
+    {
+        nNextSegmentStart = aRowRange.mnRow2 + 1;
+        bRet = aRowSegs.getRangeData( nNextSegmentStart, aRowRange );
+    }
+    if ( bRet )
+    {
+        rTop = aRowRange.mnRow1;
+        rBottom = aRowRange.mnRow2;
+        nNextSegmentStart = rBottom + 1;
+    }
+    return bRet;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/segmenttree.cxx b/sc/source/core/data/segmenttree.cxx
index 1ed168037c77..344464cd1bf1 100644
--- a/sc/source/core/data/segmenttree.cxx
+++ b/sc/source/core/data/segmenttree.cxx
@@ -344,7 +344,7 @@ bool ScFlatBoolRowSegments::setFalse(SCROW nRow1, SCROW nRow2)
     return mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 }
 
-bool ScFlatBoolRowSegments::getRangeData(SCROW nRow, RangeData& rData)
+bool ScFlatBoolRowSegments::getRangeData(SCROW nRow, RangeData& rData) const
 {
     ScFlatBoolSegmentsImpl::RangeData aData;
     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index be738f9c5a6e..e1bcfb0bee51 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -1395,22 +1395,17 @@ void ScTable::GetNextPos( SCCOL& rCol, SCROW& rRow, SCsCOL nMovX, SCsROW nMovY,
 
 bool ScTable::GetNextMarkedCell( SCCOL& rCol, SCROW& rRow, const ScMarkData& rMark ) const
 {
-    const ScMarkArray* pMarkArray = rMark.GetArray();
-    OSL_ENSURE(pMarkArray,"GetNextMarkedCell without MarkArray");
-    if ( !pMarkArray )
-        return false;
-
     ++rRow;                 // next row
 
     while ( rCol <= MAXCOL )
     {
-        const ScMarkArray& rArray = pMarkArray[rCol];
+        ScMarkArray aArray( rMark.GetMarkArray( rCol ) );
         while ( rRow <= MAXROW )
         {
-            SCROW nStart = (SCROW) rArray.GetNextMarked( (SCsROW) rRow, false );
+            SCROW nStart = (SCROW) aArray.GetNextMarked( (SCsROW) rRow, false );
             if ( nStart <= MAXROW )
             {
-                SCROW nEnd = rArray.GetMarkEnd( nStart, false );
+                SCROW nEnd = aArray.GetMarkEnd( nStart, false );
 
                 const sc::CellStoreType& rCells = aCol[rCol].maCells;
                 std::pair<sc::CellStoreType::const_iterator,size_t> aPos = rCells.position(nStart);
diff --git a/sc/source/ui/view/formatsh.cxx b/sc/source/ui/view/formatsh.cxx
index 586a2364b4ee..9d5e8045b498 100644
--- a/sc/source/ui/view/formatsh.cxx
+++ b/sc/source/ui/view/formatsh.cxx
@@ -2721,21 +2721,18 @@ short ScFormatShell::GetCurrentNumberFormatType()
         ScRange aRange;
         aMark.GetMultiMarkArea(aRange);
 
-        const ScMarkArray* pArray = aMark.GetArray();
-        if (!pArray)
-            return nType;
+        const ScMultiSel& rMultiSel = aMark.GetMultiSelData();
 
         short nComboType = css::util::NumberFormat::ALL;
         bool bFirstItem = true;
         for (SCCOL nCol = aRange.aStart.Col(); nCol <= aRange.aEnd.Col(); ++nCol)
         {
-            const ScMarkArray& rColArray = pArray[nCol];
-            if (!rColArray.HasMarks())
+            if (!rMultiSel.HasMarks(nCol))
                 continue;
 
             SCROW nRow1, nRow2;
-            ScMarkArrayIter aMarkIter(&rColArray);
-            while (aMarkIter.Next(nRow1, nRow2))
+            ScMultiSelIter aMultiIter(rMultiSel, nCol);
+            while (aMultiIter.Next(nRow1, nRow2))
             {
                 ScRange aColRange(nCol, nRow1, aRange.aStart.Tab());
                 aColRange.aEnd.SetRow(nRow2);