/* -*- 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;
}
}
}
// -------------- 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: */
↑ V560 A part of conditional expression is always true: ni > 0.