summaryrefslogtreecommitdiffstats
path: root/sc/source/core/data/markarr.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'sc/source/core/data/markarr.cxx')
-rw-r--r--sc/source/core/data/markarr.cxx472
1 files changed, 472 insertions, 0 deletions
diff --git a/sc/source/core/data/markarr.cxx b/sc/source/core/data/markarr.cxx
new file mode 100644
index 000000000..81481f211
--- /dev/null
+++ b/sc/source/core/data/markarr.cxx
@@ -0,0 +1,472 @@
+/* -*- 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 <markarr.hxx>
+#include <address.hxx>
+#include <rangelst.hxx>
+#include <vector>
+
+#include <osl/diagnose.h>
+
+ScMarkArray::ScMarkArray(SCROW nMaxRow) :
+ mnMaxRow( nMaxRow )
+{
+ Reset(false);
+}
+
+// Move constructor
+ScMarkArray::ScMarkArray( ScMarkArray&& rOther ) noexcept
+{
+ operator=(std::move(rOther));
+}
+
+// Copy constructor
+ScMarkArray::ScMarkArray( const ScMarkArray & rOther )
+{
+ operator=(rOther);
+}
+
+ScMarkArray::~ScMarkArray()
+{
+}
+
+void ScMarkArray::Reset( bool bMarked, SCSIZE nNeeded )
+{
+ // always create pData here
+ // (or have separate method to ensure pData)
+
+ assert(nNeeded);
+ mvData.resize(1);
+ mvData.reserve(nNeeded);
+ mvData[0].nRow = mnMaxRow;
+ mvData[0].bMarked = bMarked;
+}
+
+// Iterative implementation of Binary Search
+bool ScMarkArray::Search( SCROW nRow, SCSIZE& nIndex ) const
+{
+ assert(mvData.size() > 0);
+ SCSIZE nHi = mvData.size() - 1;
+ SCSIZE nLo = 0;
+
+ while ( nLo <= nHi )
+ {
+ SCSIZE i = (nLo + nHi) / 2;
+
+ if (mvData[i].nRow < nRow)
+ {
+ // If [nRow] greater, ignore left half
+ nLo = i + 1;
+ }
+ else if ((i > 0) && (mvData[i - 1].nRow >= nRow))
+ {
+ // If [nRow] is smaller, ignore right half
+ nHi = i - 1;
+ }
+ else
+ {
+ // found
+ nIndex=i;
+ return true;
+ }
+ }
+
+ // not found
+ nIndex=0;
+ return false;
+}
+
+bool ScMarkArray::GetMark( SCROW nRow ) const
+{
+ SCSIZE i;
+ if (Search( nRow, i ))
+ return mvData[i].bMarked;
+ else
+ return false;
+
+}
+
+void ScMarkArray::SetMarkArea( SCROW nStartRow, SCROW nEndRow, bool bMarked )
+{
+ if (ValidRow(nStartRow, mnMaxRow) && ValidRow(nEndRow, mnMaxRow))
+ {
+ if ((nStartRow == 0) && (nEndRow == mnMaxRow))
+ {
+ Reset(bMarked);
+ }
+ else
+ {
+ SCSIZE ni; // number of entries in beginning
+ SCSIZE nInsert; // insert position (mnMaxRow+1 := no insert)
+ bool bCombined = false;
+ bool bSplit = false;
+ if ( nStartRow > 0 )
+ {
+ // skip beginning
+ SCSIZE nIndex;
+ Search( nStartRow, nIndex );
+ ni = nIndex;
+
+ nInsert = MAXROWCOUNT;
+ if ( mvData[ni].bMarked != bMarked )
+ {
+ if ( ni == 0 || (mvData[ni-1].nRow < nStartRow - 1) )
+ { // may be a split or a simple insert or just a shrink,
+ // row adjustment is done further down
+ if ( mvData[ni].nRow > nEndRow )
+ bSplit = true;
+ ni++;
+ nInsert = ni;
+ }
+ else if ( ni > 0 && mvData[ni-1].nRow == nStartRow - 1 )
+ nInsert = ni;
+ }
+ if ( ni > 0 && mvData[ni-1].bMarked == bMarked )
+ { // combine
+ mvData[ni-1].nRow = nEndRow;
+ nInsert = MAXROWCOUNT;
+ bCombined = true;
+ }
+ }
+ else
+ {
+ nInsert = 0;
+ ni = 0;
+ }
+
+ SCSIZE nj = ni; // stop position of range to replace
+ while ( nj < mvData.size() && mvData[nj].nRow <= nEndRow )
+ nj++;
+ if ( !bSplit )
+ {
+ if ( nj < mvData.size() && mvData[nj].bMarked == bMarked )
+ { // combine
+ if ( ni > 0 )
+ {
+ if ( mvData[ni-1].bMarked == bMarked )
+ { // adjacent entries
+ mvData[ni-1].nRow = mvData[nj].nRow;
+ nj++;
+ }
+ else if ( ni == nInsert )
+ mvData[ni-1].nRow = nStartRow - 1; // shrink
+ }
+ nInsert = MAXROWCOUNT;
+ bCombined = true;
+ }
+ else if ( ni > 0 && ni == nInsert )
+ mvData[ni-1].nRow = nStartRow - 1; // shrink
+ }
+ if ( ni < nj )
+ { // remove middle entries
+ if ( !bCombined )
+ { // replace one entry
+ mvData[ni].nRow = nEndRow;
+ mvData[ni].bMarked = bMarked;
+ ni++;
+ nInsert = MAXROWCOUNT;
+ }
+ if ( ni < nj )
+ { // remove entries
+ mvData.erase(mvData.begin() + ni, mvData.begin() + nj);
+ }
+ }
+
+ if ( nInsert < sal::static_int_cast<SCSIZE>(MAXROWCOUNT) )
+ { // insert or append new entry
+ if ( nInsert <= mvData.size() )
+ {
+ if ( !bSplit )
+ mvData.insert(mvData.begin() + nInsert, { nEndRow, bMarked });
+ else
+ {
+ mvData.insert(mvData.begin() + nInsert, 2, { nEndRow, bMarked });
+ mvData[nInsert+1] = mvData[nInsert-1];
+ }
+ }
+ else
+ mvData.push_back(ScMarkEntry{ nEndRow, bMarked });
+ if ( nInsert )
+ mvData[nInsert-1].nRow = nStartRow - 1;
+ }
+ }
+ }
+}
+
+/**
+ optimised init-from-range-list. Specifically this is optimised for cases
+ where we have very large data columns with lots and lots of ranges.
+*/
+void ScMarkArray::Set( const std::vector<ScMarkEntry> & rMarkEntries )
+{
+ mvData = rMarkEntries;
+}
+
+bool ScMarkArray::IsAllMarked( SCROW nStartRow, SCROW nEndRow ) const
+{
+ SCSIZE nStartIndex;
+ SCSIZE nEndIndex;
+
+ if (Search( nStartRow, nStartIndex ))
+ if (mvData[nStartIndex].bMarked)
+ if (Search( nEndRow, nEndIndex ))
+ if (nEndIndex==nStartIndex)
+ return true;
+
+ return false;
+}
+
+bool ScMarkArray::HasOneMark( SCROW& rStartRow, SCROW& rEndRow ) const
+{
+ bool bRet = false;
+ if ( mvData.size() == 1 )
+ {
+ if ( mvData[0].bMarked )
+ {
+ rStartRow = 0;
+ rEndRow = mnMaxRow;
+ bRet = true;
+ }
+ }
+ else if ( mvData.size() == 2 )
+ {
+ if ( mvData[0].bMarked )
+ {
+ rStartRow = 0;
+ rEndRow = mvData[0].nRow;
+ }
+ else
+ {
+ rStartRow = mvData[0].nRow + 1;
+ rEndRow = mnMaxRow;
+ }
+ bRet = true;
+ }
+ else if ( mvData.size() == 3 )
+ {
+ if ( mvData[1].bMarked )
+ {
+ rStartRow = mvData[0].nRow + 1;
+ rEndRow = mvData[1].nRow;
+ bRet = true;
+ }
+ }
+ return bRet;
+}
+
+bool ScMarkArray::operator==( const ScMarkArray& rOther ) const
+{
+ return mvData == rOther.mvData;
+}
+
+ScMarkArray& ScMarkArray::operator=( const ScMarkArray& rOther )
+{
+ mvData = rOther.mvData;
+ mnMaxRow = rOther.mnMaxRow;
+ return *this;
+}
+
+ScMarkArray& ScMarkArray::operator=(ScMarkArray&& rOther) noexcept
+{
+ mvData = std::move(rOther.mvData);
+ mnMaxRow = rOther.mnMaxRow;
+ return *this;
+}
+
+SCROW ScMarkArray::GetNextMarked( SCROW nRow, bool bUp ) const
+{
+ SCROW nRet = nRow;
+ if (ValidRow(nRow, mnMaxRow))
+ {
+ SCSIZE nIndex;
+ Search(nRow, nIndex);
+ if (!mvData[nIndex].bMarked)
+ {
+ if (bUp)
+ {
+ if (nIndex>0)
+ nRet = mvData[nIndex-1].nRow;
+ else
+ nRet = -1;
+ }
+ else
+ nRet = mvData[nIndex].nRow + 1;
+ }
+ }
+ return nRet;
+}
+
+SCROW ScMarkArray::GetMarkEnd( SCROW nRow, bool bUp ) const
+{
+ SCROW nRet;
+ SCSIZE nIndex;
+ Search(nRow, nIndex);
+ assert( mvData[nIndex].bMarked && "GetMarkEnd without bMarked" );
+ if (bUp)
+ {
+ if (nIndex>0)
+ nRet = mvData[nIndex-1].nRow + 1;
+ else
+ nRet = 0;
+ }
+ else
+ nRet = mvData[nIndex].nRow;
+
+ return nRet;
+}
+
+void ScMarkArray::Shift(SCROW nStartRow, long nOffset)
+{
+ if (nOffset == 0 || nStartRow > mnMaxRow)
+ return;
+
+ for (size_t i=0; i < mvData.size(); ++i)
+ {
+ auto& rEntry = mvData[i];
+
+ if (rEntry.nRow < nStartRow)
+ continue;
+ rEntry.nRow += nOffset;
+ if (rEntry.nRow < 0)
+ {
+ rEntry.nRow = 0;
+ }
+ else if (rEntry.nRow > mnMaxRow)
+ {
+ rEntry.nRow = mnMaxRow;
+ }
+ }
+}
+
+void ScMarkArray::Intersect(const ScMarkArray& rOther)
+{
+ size_t i = 0;
+ size_t j = 0;
+
+ std::vector<ScMarkEntry> aEntryArray;
+ aEntryArray.reserve(std::max(mvData.size(), rOther.mvData.size()));
+
+ while (i < mvData.size() && j < rOther.mvData.size())
+ {
+ const auto& rEntry = mvData[i];
+ const auto& rOtherEntry = rOther.mvData[j];
+
+ if (rEntry.bMarked != rOtherEntry.bMarked)
+ {
+ if (!rOtherEntry.bMarked)
+ {
+ aEntryArray.push_back(rOther.mvData[j++]);
+ while (i < mvData.size() && mvData[i].nRow <= rOtherEntry.nRow)
+ ++i;
+ }
+ else // rEntry not marked
+ {
+ aEntryArray.push_back(mvData[i++]);
+ while (j < rOther.mvData.size() && rOther.mvData[j].nRow <= rEntry.nRow)
+ ++j;
+ }
+ }
+ else // rEntry.bMarked == rOtherEntry.bMarked
+ {
+ if (rEntry.bMarked) // both marked
+ {
+ if (rEntry.nRow <= rOtherEntry.nRow)
+ {
+ aEntryArray.push_back(mvData[i++]); // upper row
+ if (rEntry.nRow == rOtherEntry.nRow)
+ ++j;
+ }
+ else
+ {
+ aEntryArray.push_back(rOther.mvData[j++]); // upper row
+ }
+ }
+ else // both not marked
+ {
+ if (rEntry.nRow <= rOtherEntry.nRow)
+ {
+ aEntryArray.push_back(rOther.mvData[j++]); // lower row
+ while (i < mvData.size() && mvData[i].nRow <= rOtherEntry.nRow)
+ ++i;
+ }
+ else
+ {
+ aEntryArray.push_back(mvData[i++]); // lower row
+ while (j < rOther.mvData.size() && rOther.mvData[j].nRow <= rEntry.nRow)
+ ++j;
+ }
+ }
+ }
+ }
+
+ assert((i == mvData.size() || j == rOther.mvData.size()) && "Unexpected case.");
+
+ if (i == mvData.size())
+ {
+ aEntryArray.insert(aEntryArray.end(), rOther.mvData.begin() + j, rOther.mvData.end());
+ }
+ else // j == rOther.nCount
+ {
+ aEntryArray.insert(aEntryArray.end(), mvData.begin() + i, mvData.end());
+ }
+
+ mvData = std::move(aEntryArray);
+}
+
+
+// -------------- Iterator ----------------------------------------------
+
+ScMarkArrayIter::ScMarkArrayIter( const ScMarkArray* pNewArray ) :
+ pArray( pNewArray ),
+ nPos( 0 )
+{
+}
+
+ScMarkArrayIter::~ScMarkArrayIter()
+{
+}
+
+void ScMarkArrayIter::reset( const ScMarkArray* pNewArray )
+{
+ pArray = pNewArray;
+ nPos = 0;
+}
+
+bool ScMarkArrayIter::Next( SCROW& rTop, SCROW& rBottom )
+{
+ if (!pArray)
+ return false;
+ if ( nPos >= pArray->mvData.size() )
+ return false;
+ while (!pArray->mvData[nPos].bMarked)
+ {
+ ++nPos;
+ if ( nPos >= pArray->mvData.size() )
+ return false;
+ }
+ rBottom = pArray->mvData[nPos].nRow;
+ if (nPos==0)
+ rTop = 0;
+ else
+ rTop = pArray->mvData[nPos-1].nRow + 1;
+ ++nPos;
+ return true;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-14 20:49:34 +0000