LibreOffice Module sc (master) 1
markarr.cxx
Go to the documentation of this file.
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2/*
3 * This file is part of the LibreOffice project.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 *
9 * This file incorporates work covered by the following license notice:
10 *
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 */
19
20#include <markarr.hxx>
21#include <address.hxx>
22#include <sheetlimits.hxx>
23#include <vector>
24
26 mrSheetLimits(rLimits)
27{
28 Reset(false);
29}
30
31// Move constructor
33 : mrSheetLimits(rOther.mrSheetLimits)
34{
35 operator=(std::move(rOther));
36}
37
38// Copy constructor
40 : mrSheetLimits(rOther.mrSheetLimits)
41{
42 operator=(rOther);
43}
44
45void ScMarkArray::Reset( bool bMarked, SCSIZE nNeeded )
46{
47 // always create pData here
48 // (or have separate method to ensure pData)
49
50 assert(nNeeded);
51 mvData.resize(1);
52 mvData.reserve(nNeeded);
54 mvData[0].bMarked = bMarked;
55}
56
57// Iterative implementation of Binary Search
58bool ScMarkArray::Search( SCROW nRow, SCSIZE& nIndex ) const
59{
60 assert(mvData.size() > 0);
61 SCSIZE nHi = mvData.size() - 1;
62 SCSIZE nLo = 0;
63
64 while ( nLo <= nHi )
65 {
66 SCSIZE i = (nLo + nHi) / 2;
67
68 if (mvData[i].nRow < nRow)
69 {
70 // If [nRow] greater, ignore left half
71 nLo = i + 1;
72 }
73 else if ((i > 0) && (mvData[i - 1].nRow >= nRow))
74 {
75 // If [nRow] is smaller, ignore right half
76 nHi = i - 1;
77 }
78 else
79 {
80 // found
81 nIndex=i;
82 return true;
83 }
84 }
85
86 // not found
87 nIndex=0;
88 return false;
89}
90
91bool ScMarkArray::GetMark( SCROW nRow ) const
92{
93 SCSIZE i;
94 if (Search( nRow, i ))
95 return mvData[i].bMarked;
96 else
97 return false;
98
99}
100
101void ScMarkArray::SetMarkArea( SCROW nStartRow, SCROW nEndRow, bool bMarked )
102{
103 if (!(mrSheetLimits.ValidRow(nStartRow) && mrSheetLimits.ValidRow(nEndRow)))
104 return;
105
106 if ((nStartRow == 0) && (nEndRow == mrSheetLimits.mnMaxRow))
107 {
108 Reset(bMarked);
109 }
110 else
111 {
112 SCSIZE ni; // number of entries in beginning
113 SCSIZE nInsert; // insert position (mnMaxRow+1 := no insert)
114 bool bCombined = false;
115 bool bSplit = false;
116 if ( nStartRow > 0 )
117 {
118 // skip beginning
120 Search( nStartRow, nIndex );
121 ni = nIndex;
122
123 nInsert = mrSheetLimits.GetMaxRowCount();
124 if ( mvData[ni].bMarked != bMarked )
125 {
126 if ( ni == 0 || (mvData[ni-1].nRow < nStartRow - 1) )
127 { // may be a split or a simple insert or just a shrink,
128 // row adjustment is done further down
129 if ( mvData[ni].nRow > nEndRow )
130 bSplit = true;
131 ni++;
132 nInsert = ni;
133 }
134 else if ( ni > 0 && mvData[ni-1].nRow == nStartRow - 1 )
135 nInsert = ni;
136 }
137 if ( ni > 0 && mvData[ni-1].bMarked == bMarked )
138 { // combine
139 mvData[ni-1].nRow = nEndRow;
140 nInsert = mrSheetLimits.GetMaxRowCount();
141 bCombined = true;
142 }
143 }
144 else
145 {
146 nInsert = 0;
147 ni = 0;
148 }
149
150 SCSIZE nj = ni; // stop position of range to replace
151 while ( nj < mvData.size() && mvData[nj].nRow <= nEndRow )
152 nj++;
153 if ( !bSplit )
154 {
155 if ( nj < mvData.size() && mvData[nj].bMarked == bMarked )
156 { // combine
157 if ( ni > 0 )
158 {
159 if ( mvData[ni-1].bMarked == bMarked )
160 { // adjacent entries
161 mvData[ni-1].nRow = mvData[nj].nRow;
162 nj++;
163 }
164 else if ( ni == nInsert )
165 mvData[ni-1].nRow = nStartRow - 1; // shrink
166 }
167 nInsert = mrSheetLimits.GetMaxRowCount();
168 bCombined = true;
169 }
170 else if ( ni > 0 && ni == nInsert )
171 mvData[ni-1].nRow = nStartRow - 1; // shrink
172 }
173 if ( ni < nj )
174 { // remove middle entries
175 if ( !bCombined )
176 { // replace one entry
177 mvData[ni].nRow = nEndRow;
178 mvData[ni].bMarked = bMarked;
179 ni++;
180 nInsert = mrSheetLimits.GetMaxRowCount();
181 }
182 if ( ni < nj )
183 { // remove entries
184 mvData.erase(mvData.begin() + ni, mvData.begin() + nj);
185 }
186 }
187
188 if ( nInsert < sal::static_int_cast<SCSIZE>(mrSheetLimits.GetMaxRowCount()) )
189 { // insert or append new entry
190 if ( nInsert <= mvData.size() )
191 {
192 if ( !bSplit )
193 mvData.insert(mvData.begin() + nInsert, { nEndRow, bMarked });
194 else
195 {
196 mvData.insert(mvData.begin() + nInsert, 2, { nEndRow, bMarked });
197 mvData[nInsert+1] = mvData[nInsert-1];
198 }
199 }
200 else
201 mvData.push_back(ScMarkEntry{ nEndRow, bMarked });
202 if ( nInsert )
203 mvData[nInsert-1].nRow = nStartRow - 1;
204 }
205 }
206}
207
212void ScMarkArray::Set( std::vector<ScMarkEntry> && rMarkEntries )
213{
214 mvData = std::move(rMarkEntries);
215}
216
217bool ScMarkArray::IsAllMarked( SCROW nStartRow, SCROW nEndRow ) const
218{
219 SCSIZE nStartIndex;
220 SCSIZE nEndIndex;
221
222 if (Search( nStartRow, nStartIndex ))
223 if (mvData[nStartIndex].bMarked)
224 if (Search( nEndRow, nEndIndex ))
225 if (nEndIndex==nStartIndex)
226 return true;
227
228 return false;
229}
230
231bool ScMarkArray::HasOneMark( SCROW& rStartRow, SCROW& rEndRow ) const
232{
233 bool bRet = false;
234 if ( mvData.size() == 1 )
235 {
236 if ( mvData[0].bMarked )
237 {
238 rStartRow = 0;
239 rEndRow = mrSheetLimits.mnMaxRow;
240 bRet = true;
241 }
242 }
243 else if ( mvData.size() == 2 )
244 {
245 if ( mvData[0].bMarked )
246 {
247 rStartRow = 0;
248 rEndRow = mvData[0].nRow;
249 }
250 else
251 {
252 rStartRow = mvData[0].nRow + 1;
253 rEndRow = mrSheetLimits.mnMaxRow;
254 }
255 bRet = true;
256 }
257 else if ( mvData.size() == 3 )
258 {
259 if ( mvData[1].bMarked )
260 {
261 rStartRow = mvData[0].nRow + 1;
262 rEndRow = mvData[1].nRow;
263 bRet = true;
264 }
265 }
266 return bRet;
267}
268
269bool ScMarkArray::operator==( const ScMarkArray& rOther ) const
270{
271 return mvData == rOther.mvData;
272}
273
275{
276 mvData = rOther.mvData;
277 return *this;
278}
279
281{
282 mvData = std::move(rOther.mvData);
283 return *this;
284}
285
287{
288 SCROW nRet = nRow;
289 if (mrSheetLimits.ValidRow(nRow))
290 {
292 Search(nRow, nIndex);
293 if (!mvData[nIndex].bMarked)
294 {
295 if (bUp)
296 {
297 if (nIndex>0)
298 nRet = mvData[nIndex-1].nRow;
299 else
300 nRet = -1;
301 }
302 else
303 nRet = mvData[nIndex].nRow + 1;
304 }
305 }
306 return nRet;
307}
308
309SCROW ScMarkArray::GetMarkEnd( SCROW nRow, bool bUp ) const
310{
311 SCROW nRet;
313 Search(nRow, nIndex);
314 assert( mvData[nIndex].bMarked && "GetMarkEnd without bMarked" );
315 if (bUp)
316 {
317 if (nIndex>0)
318 nRet = mvData[nIndex-1].nRow + 1;
319 else
320 nRet = 0;
321 }
322 else
323 nRet = mvData[nIndex].nRow;
324
325 return nRet;
326}
327
328void ScMarkArray::Shift(SCROW nStartRow, tools::Long nOffset)
329{
330 if (nOffset == 0 || nStartRow > mrSheetLimits.mnMaxRow)
331 return;
332
333 for (size_t i=0; i < mvData.size(); ++i)
334 {
335 auto& rEntry = mvData[i];
336
337 if (rEntry.nRow < nStartRow)
338 continue;
339 rEntry.nRow += nOffset;
340 if (rEntry.nRow < 0)
341 {
342 rEntry.nRow = 0;
343 }
344 else if (rEntry.nRow > mrSheetLimits.mnMaxRow)
345 {
346 rEntry.nRow = mrSheetLimits.mnMaxRow;
347 }
348 }
349}
350
352{
353 size_t i = 0;
354 size_t j = 0;
355
356 std::vector<ScMarkEntry> aEntryArray;
357 aEntryArray.reserve(std::max(mvData.size(), rOther.mvData.size()));
358
359 while (i < mvData.size() && j < rOther.mvData.size())
360 {
361 const auto& rEntry = mvData[i];
362 const auto& rOtherEntry = rOther.mvData[j];
363
364 if (rEntry.bMarked != rOtherEntry.bMarked)
365 {
366 if (!rOtherEntry.bMarked)
367 {
368 aEntryArray.push_back(rOther.mvData[j++]);
369 while (i < mvData.size() && mvData[i].nRow <= rOtherEntry.nRow)
370 ++i;
371 }
372 else // rEntry not marked
373 {
374 aEntryArray.push_back(mvData[i++]);
375 while (j < rOther.mvData.size() && rOther.mvData[j].nRow <= rEntry.nRow)
376 ++j;
377 }
378 }
379 else // rEntry.bMarked == rOtherEntry.bMarked
380 {
381 if (rEntry.bMarked) // both marked
382 {
383 if (rEntry.nRow <= rOtherEntry.nRow)
384 {
385 aEntryArray.push_back(mvData[i++]); // upper row
386 if (rEntry.nRow == rOtherEntry.nRow)
387 ++j;
388 }
389 else
390 {
391 aEntryArray.push_back(rOther.mvData[j++]); // upper row
392 }
393 }
394 else // both not marked
395 {
396 if (rEntry.nRow <= rOtherEntry.nRow)
397 {
398 aEntryArray.push_back(rOther.mvData[j++]); // lower row
399 while (i < mvData.size() && mvData[i].nRow <= rOtherEntry.nRow)
400 ++i;
401 }
402 else
403 {
404 aEntryArray.push_back(mvData[i++]); // lower row
405 while (j < rOther.mvData.size() && rOther.mvData[j].nRow <= rEntry.nRow)
406 ++j;
407 }
408 }
409 }
410 }
411
412 assert((i == mvData.size() || j == rOther.mvData.size()) && "Unexpected case.");
413
414 if (i == mvData.size())
415 {
416 aEntryArray.insert(aEntryArray.end(), rOther.mvData.begin() + j, rOther.mvData.end());
417 }
418 else // j == rOther.nCount
419 {
420 aEntryArray.insert(aEntryArray.end(), mvData.begin() + i, mvData.end());
421 }
422
423 mvData = std::move(aEntryArray);
424}
425
426
427// -------------- Iterator ----------------------------------------------
428
430 pArray( pNewArray ),
431 nPos( 0 )
432{
433}
434
435void ScMarkArrayIter::reset( const ScMarkArray* pNewArray )
436{
437 pArray = pNewArray;
438 nPos = 0;
439}
440
441bool ScMarkArrayIter::Next( SCROW& rTop, SCROW& rBottom )
442{
443 if (!pArray)
444 return false;
445 if ( nPos >= pArray->mvData.size() )
446 return false;
447 while (!pArray->mvData[nPos].bMarked)
448 {
449 ++nPos;
450 if ( nPos >= pArray->mvData.size() )
451 return false;
452 }
453 rBottom = pArray->mvData[nPos].nRow;
454 if (nPos==0)
455 rTop = 0;
456 else
457 rTop = pArray->mvData[nPos-1].nRow + 1;
458 ++nPos;
459 return true;
460}
461
462/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
size_t SCSIZE
size_t typedef to be able to find places where code was changed from USHORT to size_t and is used to ...
Definition: address.hxx:44
bool Next(SCROW &rTop, SCROW &rBottom)
Definition: markarr.cxx:441
ScMarkArrayIter(const ScMarkArray *pNewArray)
Definition: markarr.cxx:429
void reset(const ScMarkArray *pNewArray)
Definition: markarr.cxx:435
const ScMarkArray * pArray
Definition: markarr.hxx:80
This is a rather odd datastructure.
Definition: markarr.hxx:44
SCROW GetNextMarked(SCROW nRow, bool bUp) const
Including current row, may return -1 if bUp and not found.
Definition: markarr.cxx:286
bool IsAllMarked(SCROW nStartRow, SCROW nEndRow) const
Definition: markarr.cxx:217
void Shift(SCROW nStartRow, tools::Long nOffset)
Definition: markarr.cxx:328
ScMarkArray(const ScSheetLimits &rLimits)
Definition: markarr.cxx:25
SCROW GetMarkEnd(SCROW nRow, bool bUp) const
Definition: markarr.cxx:309
const ScSheetLimits & mrSheetLimits
Definition: markarr.hxx:45
void Intersect(const ScMarkArray &rOther)
Definition: markarr.cxx:351
void Reset(bool bMarked=false, SCSIZE nNeeded=1)
Definition: markarr.cxx:45
ScMarkArray & operator=(ScMarkArray const &rSource)
Definition: markarr.cxx:274
void SetMarkArea(SCROW nStartRow, SCROW nEndRow, bool bMarked)
Definition: markarr.cxx:101
bool GetMark(SCROW nRow) const
Definition: markarr.cxx:91
bool HasOneMark(SCROW &rStartRow, SCROW &rEndRow) const
Definition: markarr.cxx:231
bool operator==(ScMarkArray const &rOther) const
Definition: markarr.cxx:269
std::vector< ScMarkEntry > mvData
Definition: markarr.hxx:46
bool Search(SCROW nRow, SCSIZE &nIndex) const
Definition: markarr.cxx:58
void Set(std::vector< ScMarkEntry > &&)
optimised init-from-range-list.
Definition: markarr.cxx:212
sal_Int32 nIndex
std::vector< std::unique_ptr< SvLinkSource_Entry_Impl > > mvData
sal_uInt16 nPos
int i
long Long
SCROW GetMaxRowCount() const
Definition: sheetlimits.hxx:66
bool ValidRow(SCROW nRow) const
Definition: sheetlimits.hxx:41
const SCROW mnMaxRow
Maximum addressable column.
Definition: sheetlimits.hxx:30
sal_Int32 SCROW
Definition: types.hxx:17