diff options
Diffstat (limited to 'sc/source/core/data/markarr.cxx')
| -rw-r--r-- | sc/source/core/data/markarr.cxx | 462 |
1 files changed, 462 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..9b93c32f2 --- /dev/null +++ b/sc/source/core/data/markarr.cxx @@ -0,0 +1,462 @@ +/* -*- 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 <sheetlimits.hxx> +#include <vector> + +ScMarkArray::ScMarkArray(const ScSheetLimits& rLimits) : + mrSheetLimits(rLimits) +{ + Reset(false); +} + +// Move constructor +ScMarkArray::ScMarkArray( ScMarkArray&& rOther ) noexcept + : mrSheetLimits(rOther.mrSheetLimits) +{ + operator=(std::move(rOther)); +} + +// Copy constructor +ScMarkArray::ScMarkArray( const ScMarkArray & rOther ) + : mrSheetLimits(rOther.mrSheetLimits) +{ + operator=(rOther); +} + +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 = mrSheetLimits.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 (!(mrSheetLimits.ValidRow(nStartRow) && mrSheetLimits.ValidRow(nEndRow))) + return; + + if ((nStartRow == 0) && (nEndRow == mrSheetLimits.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 = mrSheetLimits.GetMaxRowCount(); + 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 = mrSheetLimits.GetMaxRowCount(); + 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 = mrSheetLimits.GetMaxRowCount(); + 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 = mrSheetLimits.GetMaxRowCount(); + } + if ( ni < nj ) + { // remove entries + mvData.erase(mvData.begin() + ni, mvData.begin() + nj); + } + } + + if ( nInsert < sal::static_int_cast<SCSIZE>(mrSheetLimits.GetMaxRowCount()) ) + { // 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( std::vector<ScMarkEntry> && rMarkEntries ) +{ + mvData = std::move(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 = mrSheetLimits.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 = mrSheetLimits.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; + return *this; +} + +ScMarkArray& ScMarkArray::operator=(ScMarkArray&& rOther) noexcept +{ + mvData = std::move(rOther.mvData); + return *this; +} + +SCROW ScMarkArray::GetNextMarked( SCROW nRow, bool bUp ) const +{ + SCROW nRet = nRow; + if (mrSheetLimits.ValidRow(nRow)) + { + 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, tools::Long nOffset) +{ + if (nOffset == 0 || nStartRow > mrSheetLimits.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 > mrSheetLimits.mnMaxRow) + { + rEntry.nRow = mrSheetLimits.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 ) +{ +} + +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: */ |