Bug Summary

File:home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx
Warning:line 2852, column 5
Assigned value is garbage or undefined

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name table3.cxx -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -mframe-pointer=all -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib64/clang/11.0.0 -isystem /usr/include/libxml2 -D BOOST_ERROR_CODE_HEADER_ONLY -D BOOST_SYSTEM_NO_DEPRECATED -D CPPU_ENV=gcc3 -D LINUX -D OSL_DEBUG_LEVEL=1 -D SAL_LOG_INFO -D SAL_LOG_WARN -D UNIX -D UNX -D X86_64 -D _PTHREADS -D _REENTRANT -D SC_DLLIMPLEMENTATION -D SC_INFO_OSVERSION="LINUX" -D SYSTEM_LIBXML -D EXCEPTIONS_ON -D LIBO_INTERNAL_ONLY -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/liborcus/include -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/mdds/include -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source/i18n -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source/common -I /home/maarten/src/libreoffice/core/external/clew/source/include -I /home/maarten/src/libreoffice/core/external/boost/include -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/boost -I /home/maarten/src/libreoffice/core/sc/source/core/inc -I /home/maarten/src/libreoffice/core/sc/source/filter/inc -I /home/maarten/src/libreoffice/core/sc/source/ui/inc -I /home/maarten/src/libreoffice/core/sc/inc -I /home/maarten/src/libreoffice/core/workdir/SdiTarget/sc/sdi -I /home/maarten/src/libreoffice/core/include -I /usr/lib/jvm/java-11-openjdk-11.0.9.10-0.0.ea.fc33.x86_64/include -I /usr/lib/jvm/java-11-openjdk-11.0.9.10-0.0.ea.fc33.x86_64/include/linux -I /home/maarten/src/libreoffice/core/config_host -I /home/maarten/src/libreoffice/core/workdir/CustomTarget/officecfg/registry -I /home/maarten/src/libreoffice/core/workdir/UnoApiHeadersTarget/udkapi/normal -I /home/maarten/src/libreoffice/core/workdir/UnoApiHeadersTarget/offapi/normal -I /home/maarten/src/libreoffice/core/workdir/UnoApiHeadersTarget/oovbaapi/normal -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10 -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/x86_64-redhat-linux -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib64/clang/11.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O0 -Wno-missing-braces -std=c++17 -fdeprecated-macro -fdebug-compilation-dir /home/maarten/src/libreoffice/core -ferror-limit 19 -fvisibility hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcxx-exceptions -fexceptions -debug-info-kind=constructor -analyzer-output=html -faddrsig -o /home/maarten/tmp/wis/scan-build-libreoffice/output/report/2020-10-07-141433-9725-1 -x c++ /home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx

/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx

→
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 <comphelper/processfactory.hxx>
21#include <comphelper/random.hxx>
22#include <unotools/textsearch.hxx>
23#include <svl/zforlist.hxx>
24#include <svl/zformat.hxx>
25#include <unotools/charclass.hxx>
26#include <unotools/collatorwrapper.hxx>
27#include <stdlib.h>
28#include <unotools/transliterationwrapper.hxx>
29#include <com/sun/star/i18n/KParseTokens.hpp>
30#include <com/sun/star/i18n/KParseType.hpp>
31#include <sal/log.hxx>
32
33#include <refdata.hxx>
34#include <table.hxx>
35#include <scitems.hxx>
36#include <formulacell.hxx>
37#include <document.hxx>
38#include <globstr.hrc>
39#include <scresid.hxx>
40#include <global.hxx>
41#include <stlpool.hxx>
42#include <patattr.hxx>
43#include <subtotal.hxx>
44#include <docoptio.hxx>
45#include <markdata.hxx>
46#include <rangelst.hxx>
47#include <userlist.hxx>
48#include <progress.hxx>
49#include <cellform.hxx>
50#include <queryparam.hxx>
51#include <queryentry.hxx>
52#include <subtotalparam.hxx>
53#include <docpool.hxx>
54#include <cellvalue.hxx>
55#include <tokenarray.hxx>
56#include <mtvcellfunc.hxx>
57#include <columnspanset.hxx>
58#include <fstalgorithm.hxx>
59#include <listenercontext.hxx>
60#include <sharedformula.hxx>
61#include <stlsheet.hxx>
62#include <refhint.hxx>
63#include <listenerquery.hxx>
64#include <bcaslot.hxx>
65#include <reordermap.hxx>
66#include <drwlayer.hxx>
67
68#include <svl/sharedstringpool.hxx>
69
70#include <memory>
71#include <set>
72#include <unordered_set>
73#include <vector>
74#include <mdds/flat_segment_tree.hpp>
75
76using namespace ::com::sun::star;
77
78namespace naturalsort {
79
80using namespace ::com::sun::star::i18n;
81
82/** Splits a given string into three parts: the prefix, number string, and
83 the suffix.
84
85 @param sWhole
86 Original string to be split into pieces
87
88 @param sPrefix
89 Prefix string that consists of the part before the first number token.
90 If no number was found, sPrefix is unchanged.
91
92 @param sSuffix
93 String after the last number token. This may still contain number strings.
94 If no number was found, sSuffix is unchanged.
95
96 @param fNum
97 Number converted from the middle number string
98 If no number was found, fNum is unchanged.
99
100 @return Returns TRUE if a numeral element is found in a given string, or
101 FALSE if no numeral element is found.
102*/
103static bool SplitString( const OUString &sWhole,
104 OUString &sPrefix, OUString &sSuffix, double &fNum )
105{
106 // Get prefix element, search for any digit and stop.
107 sal_Int32 nPos = 0;
108 while (nPos < sWhole.getLength())
109 {
110 const sal_uInt16 nType = ScGlobal::getCharClassPtr()->getCharacterType( sWhole, nPos);
111 if (nType & KCharacterType::DIGIT)
112 break;
113 sWhole.iterateCodePoints( &nPos );
114 }
115
116 // Return FALSE if no numeral element is found
117 if ( nPos == sWhole.getLength() )
118 return false;
119
120 // Get numeral element
121 const OUString& sUser = ScGlobal::getLocaleDataPtr()->getNumDecimalSep();
122 ParseResult aPRNum = ScGlobal::getCharClassPtr()->parsePredefinedToken(
123 KParseType::ANY_NUMBER, sWhole, nPos,
124 KParseTokens::ANY_NUMBER, "", KParseTokens::ANY_NUMBER, sUser );
125
126 if ( aPRNum.EndPos == nPos )
127 {
128 SAL_WARN("sc.core","naturalsort::SplitString - digit found but no number parsed, pos " <<do { if (true) { switch (sal_detail_log_report(::SAL_DETAIL_LOG_LEVEL_WARN
, "sc.core")) { case SAL_DETAIL_LOG_ACTION_IGNORE: break; case
SAL_DETAIL_LOG_ACTION_LOG: if (sizeof ::sal::detail::getResult
( ::sal::detail::StreamStart() << "naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole) == 1) { ::sal_detail_log
( (::SAL_DETAIL_LOG_LEVEL_WARN), ("sc.core"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "129" ": "), ::sal::detail::unwrapStream( ::sal::detail::
StreamStart() << "naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole), 0); } else { ::
std::ostringstream sal_detail_stream; sal_detail_stream <<
"naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole; ::sal::detail::
log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("sc.core"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "129" ": "), sal_detail_stream, 0); }; break; case SAL_DETAIL_LOG_ACTION_FATAL
: if (sizeof ::sal::detail::getResult( ::sal::detail::StreamStart
() << "naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole) == 1) { ::sal_detail_log
( (::SAL_DETAIL_LOG_LEVEL_WARN), ("sc.core"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "129" ": "), ::sal::detail::unwrapStream( ::sal::detail::
StreamStart() << "naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole), 0); } else { ::
std::ostringstream sal_detail_stream; sal_detail_stream <<
"naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole; ::sal::detail::
log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("sc.core"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "129" ": "), sal_detail_stream, 0); }; std::abort(); break
; } } } while (false)
129 nPos << " : " << sWhole)do { if (true) { switch (sal_detail_log_report(::SAL_DETAIL_LOG_LEVEL_WARN
, "sc.core")) { case SAL_DETAIL_LOG_ACTION_IGNORE: break; case
SAL_DETAIL_LOG_ACTION_LOG: if (sizeof ::sal::detail::getResult
( ::sal::detail::StreamStart() << "naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole) == 1) { ::sal_detail_log
( (::SAL_DETAIL_LOG_LEVEL_WARN), ("sc.core"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "129" ": "), ::sal::detail::unwrapStream( ::sal::detail::
StreamStart() << "naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole), 0); } else { ::
std::ostringstream sal_detail_stream; sal_detail_stream <<
"naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole; ::sal::detail::
log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("sc.core"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "129" ": "), sal_detail_stream, 0); }; break; case SAL_DETAIL_LOG_ACTION_FATAL
: if (sizeof ::sal::detail::getResult( ::sal::detail::StreamStart
() << "naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole) == 1) { ::sal_detail_log
( (::SAL_DETAIL_LOG_LEVEL_WARN), ("sc.core"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "129" ": "), ::sal::detail::unwrapStream( ::sal::detail::
StreamStart() << "naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole), 0); } else { ::
std::ostringstream sal_detail_stream; sal_detail_stream <<
"naturalsort::SplitString - digit found but no number parsed, pos "
<< nPos << " : " << sWhole; ::sal::detail::
log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("sc.core"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "129" ": "), sal_detail_stream, 0); }; std::abort(); break
; } } } while (false);
130 return false;
131 }
132
133 sPrefix = sWhole.copy( 0, nPos );
134 fNum = aPRNum.Value;
135 sSuffix = sWhole.copy( aPRNum.EndPos );
136
137 return true;
138}
139
140/** Naturally compares two given strings.
141
142 This is the main function that should be called externally. It returns
143 either 1, 0, or -1 depending on the comparison result of given two strings.
144
145 @param sInput1
146 Input string 1
147
148 @param sInput2
149 Input string 2
150
151 @param bCaseSens
152 Boolean value for case sensitivity
153
154 @param pData
155 Pointer to user defined sort list
156
157 @param pCW
158 Pointer to collator wrapper for normal string comparison
159
160 @return Returns 1 if sInput1 is greater, 0 if sInput1 == sInput2, and -1 if
161 sInput2 is greater.
162*/
163static short Compare( const OUString &sInput1, const OUString &sInput2,
164 const bool bCaseSens, const ScUserListData* pData, const CollatorWrapper *pCW )
165{
166 OUString sStr1( sInput1 ), sStr2( sInput2 ), sPre1, sSuf1, sPre2, sSuf2;
167
168 do
169 {
170 double nNum1, nNum2;
171 bool bNumFound1 = SplitString( sStr1, sPre1, sSuf1, nNum1 );
172 bool bNumFound2 = SplitString( sStr2, sPre2, sSuf2, nNum2 );
173
174 short nPreRes; // Prefix comparison result
175 if ( pData )
176 {
177 if ( bCaseSens )
178 {
179 if ( !bNumFound1 || !bNumFound2 )
180 return static_cast<short>(pData->Compare( sStr1, sStr2 ));
181 else
182 nPreRes = pData->Compare( sPre1, sPre2 );
183 }
184 else
185 {
186 if ( !bNumFound1 || !bNumFound2 )
187 return static_cast<short>(pData->ICompare( sStr1, sStr2 ));
188 else
189 nPreRes = pData->ICompare( sPre1, sPre2 );
190 }
191 }
192 else
193 {
194 if ( !bNumFound1 || !bNumFound2 )
195 return static_cast<short>(pCW->compareString( sStr1, sStr2 ));
196 else
197 nPreRes = static_cast<short>(pCW->compareString( sPre1, sPre2 ));
198 }
199
200 // Prefix strings differ. Return immediately.
201 if ( nPreRes != 0 ) return nPreRes;
202
203 if ( nNum1 != nNum2 )
204 {
205 if ( nNum1 < nNum2 ) return -1;
206 return (nNum1 > nNum2) ? 1 : 0;
207 }
208
209 // The prefix and the first numerical elements are equal, but the suffix
210 // strings may still differ. Stay in the loop.
211
212 sStr1 = sSuf1;
213 sStr2 = sSuf2;
214
215 } while (true);
216
217 return 0;
218}
219
220}
221
222namespace {
223
224struct ScSortInfo final
225{
226 ScRefCellValue maCell;
227 SCCOLROW nOrg;
228};
229
230}
231
232class ScSortInfoArray
233{
234public:
235
236 struct Cell
237 {
238 ScRefCellValue maCell;
239 const sc::CellTextAttr* mpAttr;
240 const ScPostIt* mpNote;
241 std::vector<SdrObject*> maDrawObjects;
242 const ScPatternAttr* mpPattern;
243
244 Cell() : mpAttr(nullptr), mpNote(nullptr), maDrawObjects(), mpPattern(nullptr) {}
245 };
246
247 struct Row
248 {
249 std::vector<Cell> maCells;
250
251 bool mbHidden:1;
252 bool mbFiltered:1;
253
254 explicit Row( size_t nColSize ) : maCells(nColSize, Cell()), mbHidden(false), mbFiltered(false) {}
255 };
256
257 typedef std::vector<Row> RowsType;
258
259private:
260 std::unique_ptr<RowsType> mpRows; /// row-wise data table for sort by row operation.
261
262 std::vector<std::unique_ptr<ScSortInfo[]>> mvppInfo;
263 SCCOLROW nStart;
264 SCCOLROW mnLastIndex; /// index of last non-empty cell position.
265
266 std::vector<SCCOLROW> maOrderIndices;
267 bool mbKeepQuery;
268 bool mbUpdateRefs;
269
270public:
271 ScSortInfoArray(const ScSortInfoArray&) = delete;
272 const ScSortInfoArray& operator=(const ScSortInfoArray&) = delete;
273
274 ScSortInfoArray( sal_uInt16 nSorts, SCCOLROW nInd1, SCCOLROW nInd2 ) :
275 mvppInfo(nSorts),
276 nStart( nInd1 ),
277 mnLastIndex(nInd2),
278 mbKeepQuery(false),
279 mbUpdateRefs(false)
280 {
281 SCSIZE nCount( nInd2 - nInd1 + 1 );
282 if (nSorts)
283 {
284 for ( sal_uInt16 nSort = 0; nSort < nSorts; nSort++ )
285 {
286 mvppInfo[nSort].reset(new ScSortInfo[nCount]);
287 }
288 }
289
290 for (size_t i = 0; i < nCount; ++i)
291 maOrderIndices.push_back(i+nStart);
292 }
293
294 void SetKeepQuery( bool b ) { mbKeepQuery = b; }
295
296 bool IsKeepQuery() const { return mbKeepQuery; }
297
298 void SetUpdateRefs( bool b ) { mbUpdateRefs = b; }
299
300 bool IsUpdateRefs() const { return mbUpdateRefs; }
301
302 /**
303 * Call this only during normal sorting, not from reordering.
304 */
305 std::unique_ptr<ScSortInfo[]> const & GetFirstArray() const
306 {
307 return mvppInfo[0];
308 }
309
310 /**
311 * Call this only during normal sorting, not from reordering.
312 */
313 ScSortInfo & Get( sal_uInt16 nSort, SCCOLROW nInd )
314 {
315 return mvppInfo[nSort][ nInd - nStart ];
316 }
317
318 /**
319 * Call this only during normal sorting, not from reordering.
320 */
321 void Swap( SCCOLROW nInd1, SCCOLROW nInd2 )
322 {
323 if (nInd1 == nInd2) // avoid self-move-assign
324 return;
325 SCSIZE n1 = static_cast<SCSIZE>(nInd1 - nStart);
326 SCSIZE n2 = static_cast<SCSIZE>(nInd2 - nStart);
327 for ( sal_uInt16 nSort = 0; nSort < static_cast<sal_uInt16>(mvppInfo.size()); nSort++ )
328 {
329 auto & ppInfo = mvppInfo[nSort];
330 std::swap(ppInfo[n1], ppInfo[n2]);
331 }
332
333 std::swap(maOrderIndices[n1], maOrderIndices[n2]);
334
335 if (mpRows)
336 {
337 // Swap rows in data table.
338 RowsType& rRows = *mpRows;
339 std::swap(rRows[n1], rRows[n2]);
340 }
341 }
342
343 void SetOrderIndices( const std::vector<SCCOLROW>& rIndices )
344 {
345 maOrderIndices = rIndices;
346 }
347
348 /**
349 * @param rIndices indices are actual row positions on the sheet, not an
350 * offset from the top row.
351 */
352 void ReorderByRow( const std::vector<SCCOLROW>& rIndices )
353 {
354 if (!mpRows)
355 return;
356
357 RowsType& rRows = *mpRows;
358
359 std::vector<SCCOLROW> aOrderIndices2;
360 aOrderIndices2.reserve(rIndices.size());
361
362 RowsType aRows2;
363 aRows2.reserve(rRows.size());
364
365 for (const auto& rIndex : rIndices)
366 {
367 size_t nPos = rIndex - nStart; // switch to an offset to top row.
368 aRows2.push_back(rRows[nPos]);
369 aOrderIndices2.push_back(maOrderIndices[nPos]);
370 }
371
372 rRows.swap(aRows2);
373 maOrderIndices.swap(aOrderIndices2);
374 }
375
376 sal_uInt16 GetUsedSorts() const { return mvppInfo.size(); }
377
378 SCCOLROW GetStart() const { return nStart; }
379 SCCOLROW GetLast() const { return mnLastIndex; }
380
381 const std::vector<SCCOLROW>& GetOrderIndices() const { return maOrderIndices; }
382
383 RowsType& InitDataRows( size_t nRowSize, size_t nColSize )
384 {
385 mpRows.reset(new RowsType);
386 mpRows->resize(nRowSize, Row(nColSize));
387 return *mpRows;
388 }
389
390 RowsType* GetDataRows()
391 {
392 return mpRows.get();
393 }
394};
395
396namespace {
397
398void initDataRows(
399 ScSortInfoArray& rArray, ScTable& rTab, ScColContainer& rCols,
400 SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
401 bool bPattern, bool bHiddenFiltered )
402{
403 // Fill row-wise data table.
404 ScSortInfoArray::RowsType& rRows = rArray.InitDataRows(nRow2-nRow1+1, nCol2-nCol1+1);
405
406 for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
407 {
408 ScColumn& rCol = rCols[nCol];
409
410 // Skip reordering of cell formats if the whole span is on the same pattern entry.
411 bool bUniformPattern = rCol.GetPatternCount(nRow1, nRow2) < 2u;
412
413 sc::ColumnBlockConstPosition aBlockPos;
414 rCol.InitBlockPosition(aBlockPos);
415 std::map<SCROW, std::vector<SdrObject*>> aRowDrawObjects;
416 ScDrawLayer* pDrawLayer = rTab.GetDoc().GetDrawLayer();
417 if (pDrawLayer)
418 aRowDrawObjects = pDrawLayer->GetObjectsAnchoredToRange(rTab.GetTab(), nCol, nRow1, nRow2);
419
420 for (SCROW nRow = nRow1; nRow <= nRow2; ++nRow)
421 {
422 ScSortInfoArray::Row& rRow = rRows[nRow-nRow1];
423 ScSortInfoArray::Cell& rCell = rRow.maCells[nCol-nCol1];
424 rCell.maCell = rCol.GetCellValue(aBlockPos, nRow);
425 rCell.mpAttr = rCol.GetCellTextAttr(aBlockPos, nRow);
426 rCell.mpNote = rCol.GetCellNote(aBlockPos, nRow);
427 if (pDrawLayer)
428 rCell.maDrawObjects = aRowDrawObjects[nRow];
429
430 if (!bUniformPattern && bPattern)
431 rCell.mpPattern = rCol.GetPattern(nRow);
432 }
433 }
434
435 if (bHiddenFiltered)
436 {
437 for (SCROW nRow = nRow1; nRow <= nRow2; ++nRow)
438 {
439 ScSortInfoArray::Row& rRow = rRows[nRow-nRow1];
440 rRow.mbHidden = rTab.RowHidden(nRow);
441 rRow.mbFiltered = rTab.RowFiltered(nRow);
442 }
443 }
444}
445
446}
447
448std::unique_ptr<ScSortInfoArray> ScTable::CreateSortInfoArray( const sc::ReorderParam& rParam )
449{
450 std::unique_ptr<ScSortInfoArray> pArray;
451
452 if (rParam.mbByRow)
453 {
454 // Create a sort info array with just the data table.
455 SCROW nRow1 = rParam.maSortRange.aStart.Row();
456 SCROW nRow2 = rParam.maSortRange.aEnd.Row();
457 SCCOL nCol1 = rParam.maSortRange.aStart.Col();
458 SCCOL nCol2 = rParam.maSortRange.aEnd.Col();
459
460 pArray.reset(new ScSortInfoArray(0, nRow1, nRow2));
461 pArray->SetKeepQuery(rParam.mbHiddenFiltered);
462 pArray->SetUpdateRefs(rParam.mbUpdateRefs);
463
464 initDataRows(
465 *pArray, *this, aCol, nCol1, nRow1, nCol2, nRow2,
466 rParam.mbPattern, rParam.mbHiddenFiltered);
467 }
468 else
469 {
470 SCCOLROW nCol1 = rParam.maSortRange.aStart.Col();
471 SCCOLROW nCol2 = rParam.maSortRange.aEnd.Col();
472
473 pArray.reset(new ScSortInfoArray(0, nCol1, nCol2));
474 pArray->SetKeepQuery(rParam.mbHiddenFiltered);
475 pArray->SetUpdateRefs(rParam.mbUpdateRefs);
476 }
477
478 return pArray;
479}
480
481std::unique_ptr<ScSortInfoArray> ScTable::CreateSortInfoArray(
482 const ScSortParam& rSortParam, SCCOLROW nInd1, SCCOLROW nInd2,
483 bool bKeepQuery, bool bUpdateRefs )
484{
485 sal_uInt16 nUsedSorts = 1;
486 while ( nUsedSorts < rSortParam.GetSortKeyCount() && rSortParam.maKeyState[nUsedSorts].bDoSort )
487 nUsedSorts++;
488 std::unique_ptr<ScSortInfoArray> pArray(new ScSortInfoArray( nUsedSorts, nInd1, nInd2 ));
489 pArray->SetKeepQuery(bKeepQuery);
490 pArray->SetUpdateRefs(bUpdateRefs);
491
492 if ( rSortParam.bByRow )
493 {
494 for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
495 {
496 SCCOL nCol = static_cast<SCCOL>(rSortParam.maKeyState[nSort].nField);
497 ScColumn* pCol = &aCol[nCol];
498 sc::ColumnBlockConstPosition aBlockPos;
499 pCol->InitBlockPosition(aBlockPos);
500 for ( SCROW nRow = nInd1; nRow <= nInd2; nRow++ )
501 {
502 ScSortInfo & rInfo = pArray->Get( nSort, nRow );
503 rInfo.maCell = pCol->GetCellValue(aBlockPos, nRow);
504 rInfo.nOrg = nRow;
505 }
506 }
507
508 initDataRows(
509 *pArray, *this, aCol, rSortParam.nCol1, nInd1, rSortParam.nCol2, nInd2,
510 rSortParam.bIncludePattern, bKeepQuery);
511 }
512 else
513 {
514 for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
515 {
516 SCROW nRow = rSortParam.maKeyState[nSort].nField;
517 for ( SCCOL nCol = static_cast<SCCOL>(nInd1);
518 nCol <= static_cast<SCCOL>(nInd2); nCol++ )
519 {
520 ScSortInfo & rInfo = pArray->Get( nSort, nCol );
521 rInfo.maCell = GetCellValue(nCol, nRow);
522 rInfo.nOrg = nCol;
523 }
524 }
525 }
526 return pArray;
527}
528
529namespace {
530
531struct SortedColumn
532{
533 typedef mdds::flat_segment_tree<SCROW, const ScPatternAttr*> PatRangeType;
534
535 sc::CellStoreType maCells;
536 sc::CellTextAttrStoreType maCellTextAttrs;
537 sc::BroadcasterStoreType maBroadcasters;
538 sc::CellNoteStoreType maCellNotes;
539 std::vector<std::vector<SdrObject*>> maCellDrawObjects;
540
541 PatRangeType maPatterns;
542 PatRangeType::const_iterator miPatternPos;
543
544 SortedColumn(const SortedColumn&) = delete;
545 const SortedColumn operator=(const SortedColumn&) = delete;
546
547 explicit SortedColumn( size_t nTopEmptyRows, const ScSheetLimits& rSheetLimits ) :
548 maCells(nTopEmptyRows),
549 maCellTextAttrs(nTopEmptyRows),
550 maBroadcasters(nTopEmptyRows),
551 maCellNotes(nTopEmptyRows),
552 maCellDrawObjects(),
553 maPatterns(0, rSheetLimits.GetMaxRowCount(), nullptr),
554 miPatternPos(maPatterns.begin()) {}
555
556 void setPattern( SCROW nRow, const ScPatternAttr* pPat )
557 {
558 miPatternPos = maPatterns.insert(miPatternPos, nRow, nRow+1, pPat).first;
559 }
560};
561
562struct SortedRowFlags
563{
564 typedef mdds::flat_segment_tree<SCROW,bool> FlagsType;
565
566 FlagsType maRowsHidden;
567 FlagsType maRowsFiltered;
568 FlagsType::const_iterator miPosHidden;
569 FlagsType::const_iterator miPosFiltered;
570
571 SortedRowFlags(const ScSheetLimits& rSheetLimits) :
572 maRowsHidden(0, rSheetLimits.GetMaxRowCount(), false),
573 maRowsFiltered(0, rSheetLimits.GetMaxRowCount(), false),
574 miPosHidden(maRowsHidden.begin()),
575 miPosFiltered(maRowsFiltered.begin()) {}
576
577 void setRowHidden( SCROW nRow, bool b )
578 {
579 miPosHidden = maRowsHidden.insert(miPosHidden, nRow, nRow+1, b).first;
580 }
581
582 void setRowFiltered( SCROW nRow, bool b )
583 {
584 miPosFiltered = maRowsFiltered.insert(miPosFiltered, nRow, nRow+1, b).first;
585 }
586
587 void swap( SortedRowFlags& r )
588 {
589 maRowsHidden.swap(r.maRowsHidden);
590 maRowsFiltered.swap(r.maRowsFiltered);
591
592 // Just reset the position hints.
593 miPosHidden = maRowsHidden.begin();
594 miPosFiltered = maRowsFiltered.begin();
595 }
596};
597
598struct PatternSpan
599{
600 SCROW mnRow1;
601 SCROW mnRow2;
602 const ScPatternAttr* mpPattern;
603
604 PatternSpan( SCROW nRow1, SCROW nRow2, const ScPatternAttr* pPat ) :
605 mnRow1(nRow1), mnRow2(nRow2), mpPattern(pPat) {}
606};
607
608}
609
610bool ScTable::IsSortCollatorGlobal() const
611{
612 return pSortCollator == ScGlobal::GetCollator() ||
613 pSortCollator == ScGlobal::GetCaseCollator();
614}
615
616void ScTable::InitSortCollator( const ScSortParam& rPar )
617{
618 if ( !rPar.aCollatorLocale.Language.isEmpty() )
619 {
620 if ( !pSortCollator || IsSortCollatorGlobal() )
621 pSortCollator = new CollatorWrapper( comphelper::getProcessComponentContext() );
622 pSortCollator->loadCollatorAlgorithm( rPar.aCollatorAlgorithm,
623 rPar.aCollatorLocale, (rPar.bCaseSens ? 0 : SC_COLLATOR_IGNOREScss::i18n::CollatorOptions::CollatorOptions_IGNORE_CASE) );
624 }
625 else
626 { // SYSTEM
627 DestroySortCollator();
628 pSortCollator = (rPar.bCaseSens ? ScGlobal::GetCaseCollator() :
629 ScGlobal::GetCollator());
630 }
631}
632
633void ScTable::DestroySortCollator()
634{
635 if ( pSortCollator )
636 {
637 if ( !IsSortCollatorGlobal() )
638 delete pSortCollator;
639 pSortCollator = nullptr;
640 }
641}
642
643namespace {
644
645template<typename Hint, typename ReorderMap, typename Index>
646class ReorderNotifier
647{
648 Hint maHint;
649public:
650 ReorderNotifier( const ReorderMap& rMap, SCTAB nTab, Index nPos1, Index nPos2 ) :
651 maHint(rMap, nTab, nPos1, nPos2) {}
652
653 void operator() ( SvtListener* p )
654 {
655 p->Notify(maHint);
656 }
657};
658
659class FormulaGroupPosCollector
660{
661 sc::RefQueryFormulaGroup& mrQuery;
662
663public:
664 explicit FormulaGroupPosCollector( sc::RefQueryFormulaGroup& rQuery ) : mrQuery(rQuery) {}
665
666 void operator() ( const SvtListener* p )
667 {
668 p->Query(mrQuery);
669 }
670};
671
672void fillSortedColumnArray(
673 std::vector<std::unique_ptr<SortedColumn>>& rSortedCols,
674 SortedRowFlags& rRowFlags,
675 std::vector<SvtListener*>& rCellListeners,
676 ScSortInfoArray* pArray, SCTAB nTab, SCCOL nCol1, SCCOL nCol2, ScProgress* pProgress, const ScTable* pTable )
677{
678 SCROW nRow1 = pArray->GetStart();
679 ScSortInfoArray::RowsType* pRows = pArray->GetDataRows();
680 std::vector<SCCOLROW> aOrderIndices = pArray->GetOrderIndices();
681
682 size_t nColCount = nCol2 - nCol1 + 1;
683 std::vector<std::unique_ptr<SortedColumn>> aSortedCols; // storage for copied cells.
684 SortedRowFlags aRowFlags(pTable->GetDoc().GetSheetLimits());
685 aSortedCols.reserve(nColCount);
686 for (size_t i = 0; i < nColCount; ++i)
687 {
688 // In the sorted column container, element positions and row
689 // positions must match, else formula cells may mis-behave during
690 // grouping.
691 aSortedCols.push_back(std::make_unique<SortedColumn>(nRow1, pTable->GetDoc().GetSheetLimits()));
692 }
693
694 for (size_t i = 0; i < pRows->size(); ++i)
695 {
696 ScSortInfoArray::Row& rRow = (*pRows)[i];
697 for (size_t j = 0; j < rRow.maCells.size(); ++j)
698 {
699 ScAddress aCellPos(nCol1 + j, nRow1 + i, nTab);
700
701 ScSortInfoArray::Cell& rCell = rRow.maCells[j];
702
703 sc::CellStoreType& rCellStore = aSortedCols.at(j)->maCells;
704 switch (rCell.maCell.meType)
705 {
706 case CELLTYPE_STRING:
707 assert(rCell.mpAttr)(static_cast <bool> (rCell.mpAttr) ? void (0) : __assert_fail
("rCell.mpAttr", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 707, __extension__ __PRETTY_FUNCTION__));
708 rCellStore.push_back(*rCell.maCell.mpString);
709 break;
710 case CELLTYPE_VALUE:
711 assert(rCell.mpAttr)(static_cast <bool> (rCell.mpAttr) ? void (0) : __assert_fail
("rCell.mpAttr", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 711, __extension__ __PRETTY_FUNCTION__));
712 rCellStore.push_back(rCell.maCell.mfValue);
713 break;
714 case CELLTYPE_EDIT:
715 assert(rCell.mpAttr)(static_cast <bool> (rCell.mpAttr) ? void (0) : __assert_fail
("rCell.mpAttr", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 715, __extension__ __PRETTY_FUNCTION__));
716 rCellStore.push_back(rCell.maCell.mpEditText->Clone().release());
717 break;
718 case CELLTYPE_FORMULA:
719 {
720 assert(rCell.mpAttr)(static_cast <bool> (rCell.mpAttr) ? void (0) : __assert_fail
("rCell.mpAttr", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 720, __extension__ __PRETTY_FUNCTION__));
721 ScAddress aOldPos = rCell.maCell.mpFormula->aPos;
722
723 ScFormulaCell* pNew = rCell.maCell.mpFormula->Clone( aCellPos );
724 if (pArray->IsUpdateRefs())
725 {
726 pNew->CopyAllBroadcasters(*rCell.maCell.mpFormula);
727 pNew->GetCode()->AdjustReferenceOnMovedOrigin(aOldPos, aCellPos);
728 }
729 else
730 {
731 pNew->GetCode()->AdjustReferenceOnMovedOriginIfOtherSheet(aOldPos, aCellPos);
732 }
733
734 if (!rCellListeners.empty())
735 {
736 // Original source cells will be deleted during
737 // sc::CellStoreType::transfer(), SvtListener is a base
738 // class, so we need to replace it.
739 auto it( ::std::find( rCellListeners.begin(), rCellListeners.end(), rCell.maCell.mpFormula));
740 if (it != rCellListeners.end())
741 *it = pNew;
742 }
743
744 rCellStore.push_back(pNew);
745 }
746 break;
747 default:
748 //assert(!rCell.mpAttr);
749 // This assert doesn't hold, for example
750 // CopyCellsFromClipHandler may omit copying cells during
751 // PasteSpecial for which CopyTextAttrsFromClipHandler
752 // still copies a CellTextAttr. So if that really is not
753 // expected then fix it there.
754 rCellStore.push_back_empty();
755 }
756
757 sc::CellTextAttrStoreType& rAttrStore = aSortedCols.at(j)->maCellTextAttrs;
758 if (rCell.mpAttr)
759 rAttrStore.push_back(*rCell.mpAttr);
760 else
761 rAttrStore.push_back_empty();
762
763 if (pArray->IsUpdateRefs())
764 {
765 // At this point each broadcaster instance is managed by 2
766 // containers. We will release those in the original storage
767 // below before transferring them to the document.
768 const SvtBroadcaster* pBroadcaster = pTable->GetBroadcaster( nCol1 + j, aOrderIndices[i]);
769 sc::BroadcasterStoreType& rBCStore = aSortedCols.at(j)->maBroadcasters;
770 if (pBroadcaster)
771 // A const pointer would be implicitly converted to a bool type.
772 rBCStore.push_back(const_cast<SvtBroadcaster*>(pBroadcaster));
773 else
774 rBCStore.push_back_empty();
775 }
776
777 // The same with cell note instances ...
778 sc::CellNoteStoreType& rNoteStore = aSortedCols.at(j)->maCellNotes;
779 if (rCell.mpNote)
780 rNoteStore.push_back(const_cast<ScPostIt*>(rCell.mpNote));
781 else
782 rNoteStore.push_back_empty();
783
784 // Add cell anchored images
785 aSortedCols.at(j)->maCellDrawObjects.push_back(rCell.maDrawObjects);
786
787 if (rCell.mpPattern)
788 aSortedCols.at(j)->setPattern(aCellPos.Row(), rCell.mpPattern);
789 }
790
791 if (pArray->IsKeepQuery())
792 {
793 // Hidden and filtered flags are first converted to segments.
794 SCROW nRow = nRow1 + i;
795 aRowFlags.setRowHidden(nRow, rRow.mbHidden);
796 aRowFlags.setRowFiltered(nRow, rRow.mbFiltered);
797 }
798
799 if (pProgress)
800 pProgress->SetStateOnPercent(i);
801 }
802
803 rSortedCols.swap(aSortedCols);
804 rRowFlags.swap(aRowFlags);
805}
806
807void expandRowRange( ScRange& rRange, SCROW nTop, SCROW nBottom )
808{
809 if (nTop < rRange.aStart.Row())
810 rRange.aStart.SetRow(nTop);
811
812 if (rRange.aEnd.Row() < nBottom)
813 rRange.aEnd.SetRow(nBottom);
814}
815
816class FormulaCellCollectAction : public sc::ColumnSpanSet::ColumnAction
817{
818 std::vector<ScFormulaCell*>& mrCells;
819 ScColumn* mpCol;
820
821public:
822 explicit FormulaCellCollectAction( std::vector<ScFormulaCell*>& rCells ) :
823 mrCells(rCells), mpCol(nullptr) {}
824
825 virtual void startColumn( ScColumn* pCol ) override
826 {
827 mpCol = pCol;
828 }
829
830 virtual void execute( SCROW nRow1, SCROW nRow2, bool bVal ) override
831 {
832 assert(mpCol)(static_cast <bool> (mpCol) ? void (0) : __assert_fail (
"mpCol", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 832, __extension__ __PRETTY_FUNCTION__));
833
834 if (!bVal)
835 return;
836
837 mpCol->CollectFormulaCells(mrCells, nRow1, nRow2);
838 }
839};
840
841class ListenerStartAction : public sc::ColumnSpanSet::ColumnAction
842{
843 ScColumn* mpCol;
844
845 std::shared_ptr<sc::ColumnBlockPositionSet> mpPosSet;
846 sc::StartListeningContext maStartCxt;
847 sc::EndListeningContext maEndCxt;
848
849public:
850 explicit ListenerStartAction( ScDocument& rDoc ) :
851 mpCol(nullptr),
852 mpPosSet(std::make_shared<sc::ColumnBlockPositionSet>(rDoc)),
853 maStartCxt(rDoc, mpPosSet),
854 maEndCxt(rDoc, mpPosSet) {}
855
856 virtual void startColumn( ScColumn* pCol ) override
857 {
858 mpCol = pCol;
859 }
860
861 virtual void execute( SCROW nRow1, SCROW nRow2, bool bVal ) override
862 {
863 assert(mpCol)(static_cast <bool> (mpCol) ? void (0) : __assert_fail (
"mpCol", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 863, __extension__ __PRETTY_FUNCTION__));
864
865 if (!bVal)
866 return;
867
868 mpCol->StartListeningFormulaCells(maStartCxt, maEndCxt, nRow1, nRow2);
869 }
870};
871
872}
873
874void ScTable::SortReorderByColumn(
875 const ScSortInfoArray* pArray, SCROW nRow1, SCROW nRow2, bool bPattern, ScProgress* pProgress )
876{
877 SCCOLROW nStart = pArray->GetStart();
878 SCCOLROW nLast = pArray->GetLast();
879
880 std::vector<SCCOLROW> aIndices = pArray->GetOrderIndices();
881 size_t nCount = aIndices.size();
882
883 // Cut formula grouping at row and reference boundaries before the reordering.
884 ScRange aSortRange(nStart, nRow1, nTab, nLast, nRow2, nTab);
885 for (SCCOL nCol = nStart; nCol <= static_cast<SCCOL>(nLast); ++nCol)
886 aCol[nCol].SplitFormulaGroupByRelativeRef(aSortRange);
887
888 // Collect all listeners of cell broadcasters of sorted range.
889 std::vector<SvtListener*> aCellListeners;
890
891 if (!pArray->IsUpdateRefs())
892 {
893 // Collect listeners of cell broadcasters.
894 for (SCCOL nCol = nStart; nCol <= static_cast<SCCOL>(nLast); ++nCol)
895 aCol[nCol].CollectListeners(aCellListeners, nRow1, nRow2);
896
897 // Remove any duplicate listener entries. We must ensure that we
898 // notify each unique listener only once.
899 std::sort(aCellListeners.begin(), aCellListeners.end());
900 aCellListeners.erase(std::unique(aCellListeners.begin(), aCellListeners.end()), aCellListeners.end());
901
902 // Notify the cells' listeners to stop listening.
903 /* TODO: for performance this could be enhanced to stop and later
904 * restart only listening to within the reordered range and keep
905 * listening to everything outside untouched. */
906 sc::RefStopListeningHint aHint;
907 for (auto const & l : aCellListeners)
908 l->Notify(aHint);
909 }
910
911 // table to keep track of column index to position in the index table.
912 std::vector<SCCOLROW> aPosTable(nCount);
913 for (size_t i = 0; i < nCount; ++i)
914 aPosTable[aIndices[i]-nStart] = i;
915
916 SCCOLROW nDest = nStart;
917 for (size_t i = 0; i < nCount; ++i, ++nDest)
918 {
919 SCCOLROW nSrc = aIndices[i];
920 if (nDest != nSrc)
921 {
922 aCol[nDest].Swap(aCol[nSrc], nRow1, nRow2, bPattern);
923
924 // Update the position of the index that was originally equal to nDest.
925 size_t nPos = aPosTable[nDest-nStart];
926 aIndices[nPos] = nSrc;
927 aPosTable[nSrc-nStart] = nPos;
928 }
929
930 if (pProgress)
931 pProgress->SetStateOnPercent(i);
932 }
933
934 // Reset formula cell positions which became out-of-sync after column reordering.
935 bool bUpdateRefs = pArray->IsUpdateRefs();
936 for (SCCOL nCol = nStart; nCol <= static_cast<SCCOL>(nLast); ++nCol)
937 aCol[nCol].ResetFormulaCellPositions(nRow1, nRow2, bUpdateRefs);
938
939 if (pArray->IsUpdateRefs())
940 {
941 // Set up column reorder map (for later broadcasting of reference updates).
942 sc::ColRowReorderMapType aColMap;
943 const std::vector<SCCOLROW>& rOldIndices = pArray->GetOrderIndices();
944 for (size_t i = 0, n = rOldIndices.size(); i < n; ++i)
945 {
946 SCCOL nNew = i + nStart;
947 SCCOL nOld = rOldIndices[i];
948 aColMap.emplace(nOld, nNew);
949 }
950
951 // Collect all listeners within sorted range ahead of time.
952 std::vector<SvtListener*> aListeners;
953
954 for (SCCOL nCol = nStart; nCol <= static_cast<SCCOL>(nLast); ++nCol)
955 aCol[nCol].CollectListeners(aListeners, nRow1, nRow2);
956
957 // Get all area listeners that listen on one column within the range
958 // and end their listening.
959 ScRange aMoveRange( nStart, nRow1, nTab, nLast, nRow2, nTab);
960 std::vector<sc::AreaListener> aAreaListeners = rDocument.GetBASM()->GetAllListeners(
961 aMoveRange, sc::AreaOverlapType::OneColumnInside);
962 {
963 for (auto& rAreaListener : aAreaListeners)
964 {
965 rDocument.EndListeningArea(rAreaListener.maArea, rAreaListener.mbGroupListening, rAreaListener.mpListener);
966 aListeners.push_back( rAreaListener.mpListener);
967 }
968 }
969
970 // Remove any duplicate listener entries and notify all listeners
971 // afterward. We must ensure that we notify each unique listener only
972 // once.
973 std::sort(aListeners.begin(), aListeners.end());
974 aListeners.erase(std::unique(aListeners.begin(), aListeners.end()), aListeners.end());
975 ReorderNotifier<sc::RefColReorderHint, sc::ColRowReorderMapType, SCCOL> aFunc(aColMap, nTab, nRow1, nRow2);
976 std::for_each(aListeners.begin(), aListeners.end(), aFunc);
977
978 // Re-start area listeners on the reordered columns.
979 {
980 for (auto& rAreaListener : aAreaListeners)
981 {
982 ScRange aNewRange = rAreaListener.maArea;
983 sc::ColRowReorderMapType::const_iterator itCol = aColMap.find( aNewRange.aStart.Col());
984 if (itCol != aColMap.end())
985 {
986 aNewRange.aStart.SetCol( itCol->second);
987 aNewRange.aEnd.SetCol( itCol->second);
988 }
989 rDocument.StartListeningArea(aNewRange, rAreaListener.mbGroupListening, rAreaListener.mpListener);
990 }
991 }
992 }
993 else // !(pArray->IsUpdateRefs())
994 {
995 // Notify the cells' listeners to (re-)start listening.
996 sc::RefStartListeningHint aHint;
997 for (auto const & l : aCellListeners)
998 l->Notify(aHint);
999 }
1000
1001 // Re-join formulas at row boundaries now that all the references have
1002 // been adjusted for column reordering.
1003 for (SCCOL nCol = nStart; nCol <= static_cast<SCCOL>(nLast); ++nCol)
1004 {
1005 sc::CellStoreType& rCells = aCol[nCol].maCells;
1006 sc::CellStoreType::position_type aPos = rCells.position(nRow1);
1007 sc::SharedFormulaUtil::joinFormulaCellAbove(aPos);
1008 if (nRow2 < rDocument.MaxRow())
1009 {
1010 aPos = rCells.position(aPos.first, nRow2+1);
1011 sc::SharedFormulaUtil::joinFormulaCellAbove(aPos);
1012 }
1013 }
1014}
1015
1016void ScTable::SortReorderByRow(
1017 ScSortInfoArray* pArray, SCCOL nCol1, SCCOL nCol2, ScProgress* pProgress )
1018{
1019 assert(!pArray->IsUpdateRefs())(static_cast <bool> (!pArray->IsUpdateRefs()) ? void
(0) : __assert_fail ("!pArray->IsUpdateRefs()", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 1019, __extension__ __PRETTY_FUNCTION__));
1020
1021 if (nCol2 < nCol1)
1022 return;
1023
1024 SCROW nRow1 = pArray->GetStart();
1025 SCROW nRow2 = pArray->GetLast();
1026
1027 // Collect all listeners of cell broadcasters of sorted range.
1028 std::vector<SvtListener*> aCellListeners;
1029
1030 // When the update ref mode is disabled, we need to detach all formula
1031 // cells in the sorted range before reordering, and re-start them
1032 // afterward.
1033 {
1034 sc::EndListeningContext aCxt(rDocument);
1035 DetachFormulaCells(aCxt, nCol1, nRow1, nCol2, nRow2);
1036 }
1037
1038 // Collect listeners of cell broadcasters.
1039 for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
1040 aCol[nCol].CollectListeners(aCellListeners, nRow1, nRow2);
1041
1042 // Remove any duplicate listener entries. We must ensure that we notify
1043 // each unique listener only once.
1044 std::sort(aCellListeners.begin(), aCellListeners.end());
1045 aCellListeners.erase(std::unique(aCellListeners.begin(), aCellListeners.end()), aCellListeners.end());
1046
1047 // Notify the cells' listeners to stop listening.
1048 /* TODO: for performance this could be enhanced to stop and later
1049 * restart only listening to within the reordered range and keep
1050 * listening to everything outside untouched. */
1051 {
1052 sc::RefStopListeningHint aHint;
1053 for (auto const & l : aCellListeners)
1054 l->Notify(aHint);
1055 }
1056
1057 // Split formula groups at the sort range boundaries (if applicable).
1058 std::vector<SCROW> aRowBounds;
1059 aRowBounds.reserve(2);
1060 aRowBounds.push_back(nRow1);
1061 aRowBounds.push_back(nRow2+1);
1062 for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
1063 SplitFormulaGroups(nCol, aRowBounds);
1064
1065 // Cells in the data rows only reference values in the document. Make
1066 // a copy before updating the document.
1067 std::vector<std::unique_ptr<SortedColumn>> aSortedCols; // storage for copied cells.
1068 SortedRowFlags aRowFlags(GetDoc().GetSheetLimits());
1069 fillSortedColumnArray(aSortedCols, aRowFlags, aCellListeners, pArray, nTab, nCol1, nCol2, pProgress, this);
1070
1071 for (size_t i = 0, n = aSortedCols.size(); i < n; ++i)
1072 {
1073 SCCOL nThisCol = i + nCol1;
1074
1075 {
1076 sc::CellStoreType& rDest = aCol[nThisCol].maCells;
1077 sc::CellStoreType& rSrc = aSortedCols[i]->maCells;
1078 rSrc.transfer(nRow1, nRow2, rDest, nRow1);
1079 }
1080
1081 {
1082 sc::CellTextAttrStoreType& rDest = aCol[nThisCol].maCellTextAttrs;
1083 sc::CellTextAttrStoreType& rSrc = aSortedCols[i]->maCellTextAttrs;
1084 rSrc.transfer(nRow1, nRow2, rDest, nRow1);
1085 }
1086
1087 {
1088 sc::CellNoteStoreType& rSrc = aSortedCols[i]->maCellNotes;
1089 sc::CellNoteStoreType& rDest = aCol[nThisCol].maCellNotes;
1090
1091 // Do the same as broadcaster storage transfer (to prevent double deletion).
1092 rDest.release_range(nRow1, nRow2);
1093 rSrc.transfer(nRow1, nRow2, rDest, nRow1);
1094 aCol[nThisCol].UpdateNoteCaptions(nRow1, nRow2);
1095 }
1096
1097 // Update draw object positions
1098 aCol[nThisCol].UpdateDrawObjects(aSortedCols[i]->maCellDrawObjects, nRow1, nRow2);
1099
1100 {
1101 // Get all row spans where the pattern is not NULL.
1102 std::vector<PatternSpan> aSpans =
1103 sc::toSpanArrayWithValue<SCROW,const ScPatternAttr*,PatternSpan>(
1104 aSortedCols[i]->maPatterns);
1105
1106 for (const auto& rSpan : aSpans)
1107 {
1108 assert(rSpan.mpPattern)(static_cast <bool> (rSpan.mpPattern) ? void (0) : __assert_fail
("rSpan.mpPattern", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 1108, __extension__ __PRETTY_FUNCTION__)); // should never be NULL.
1109 rDocument.GetPool()->Put(*rSpan.mpPattern);
1110 }
1111
1112 for (const auto& rSpan : aSpans)
1113 {
1114 aCol[nThisCol].SetPatternArea(rSpan.mnRow1, rSpan.mnRow2, *rSpan.mpPattern);
1115 rDocument.GetPool()->Remove(*rSpan.mpPattern);
1116 }
1117 }
1118
1119 aCol[nThisCol].CellStorageModified();
1120 }
1121
1122 if (pArray->IsKeepQuery())
1123 {
1124 aRowFlags.maRowsHidden.build_tree();
1125 aRowFlags.maRowsFiltered.build_tree();
1126
1127 // Remove all flags in the range first.
1128 SetRowHidden(nRow1, nRow2, false);
1129 SetRowFiltered(nRow1, nRow2, false);
1130
1131 std::vector<sc::RowSpan> aSpans =
1132 sc::toSpanArray<SCROW,sc::RowSpan>(aRowFlags.maRowsHidden, nRow1);
1133
1134 for (const auto& rSpan : aSpans)
1135 SetRowHidden(rSpan.mnRow1, rSpan.mnRow2, true);
1136
1137 aSpans = sc::toSpanArray<SCROW,sc::RowSpan>(aRowFlags.maRowsFiltered, nRow1);
1138
1139 for (const auto& rSpan : aSpans)
1140 SetRowFiltered(rSpan.mnRow1, rSpan.mnRow2, true);
1141 }
1142
1143 // Notify the cells' listeners to (re-)start listening.
1144 {
1145 sc::RefStartListeningHint aHint;
1146 for (auto const & l : aCellListeners)
1147 l->Notify(aHint);
1148 }
1149
1150 // Re-group columns in the sorted range too.
1151 for (SCCOL i = nCol1; i <= nCol2; ++i)
1152 aCol[i].RegroupFormulaCells();
1153
1154 {
1155 sc::StartListeningContext aCxt(rDocument);
1156 AttachFormulaCells(aCxt, nCol1, nRow1, nCol2, nRow2);
1157 }
1158}
1159
1160void ScTable::SortReorderByRowRefUpdate(
1161 ScSortInfoArray* pArray, SCCOL nCol1, SCCOL nCol2, ScProgress* pProgress )
1162{
1163 assert(pArray->IsUpdateRefs())(static_cast <bool> (pArray->IsUpdateRefs()) ? void (
0) : __assert_fail ("pArray->IsUpdateRefs()", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 1163, __extension__ __PRETTY_FUNCTION__));
1164
1165 if (nCol2 < nCol1)
1166 return;
1167
1168 SCROW nRow1 = pArray->GetStart();
1169 SCROW nRow2 = pArray->GetLast();
1170
1171 ScRange aMoveRange( nCol1, nRow1, nTab, nCol2, nRow2, nTab);
1172 sc::ColumnSpanSet aGrpListenerRanges;
1173
1174 {
1175 // Get the range of formula group listeners within sorted range (if any).
1176 sc::QueryRange aQuery;
1177
1178 ScBroadcastAreaSlotMachine* pBASM = rDocument.GetBASM();
1179 std::vector<sc::AreaListener> aGrpListeners =
1180 pBASM->GetAllListeners(
1181 aMoveRange, sc::AreaOverlapType::InsideOrOverlap, sc::ListenerGroupType::Group);
1182
1183 {
1184 for (const auto& rGrpListener : aGrpListeners)
1185 {
1186 assert(rGrpListener.mbGroupListening)(static_cast <bool> (rGrpListener.mbGroupListening) ? void
(0) : __assert_fail ("rGrpListener.mbGroupListening", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 1186, __extension__ __PRETTY_FUNCTION__));
1187 SvtListener* pGrpLis = rGrpListener.mpListener;
1188 pGrpLis->Query(aQuery);
1189 rDocument.EndListeningArea(rGrpListener.maArea, rGrpListener.mbGroupListening, pGrpLis);
1190 }
1191 }
1192
1193 ScRangeList aTmp;
1194 aQuery.swapRanges(aTmp);
1195
1196 // If the range is within the sorted range, we need to expand its rows
1197 // to the top and bottom of the sorted range, since the formula cells
1198 // could be anywhere in the sorted range after reordering.
1199 for (size_t i = 0, n = aTmp.size(); i < n; ++i)
1200 {
1201 ScRange aRange = aTmp[i];
1202 if (!aMoveRange.Intersects(aRange))
1203 {
1204 // Doesn't overlap with the sorted range at all.
1205 aGrpListenerRanges.set(GetDoc(), aRange, true);
1206 continue;
1207 }
1208
1209 if (aMoveRange.aStart.Col() <= aRange.aStart.Col() && aRange.aEnd.Col() <= aMoveRange.aEnd.Col())
1210 {
1211 // Its column range is within the column range of the sorted range.
1212 expandRowRange(aRange, aMoveRange.aStart.Row(), aMoveRange.aEnd.Row());
1213 aGrpListenerRanges.set(GetDoc(), aRange, true);
1214 continue;
1215 }
1216
1217 // It intersects with the sorted range, but its column range is
1218 // not within the column range of the sorted range. Split it into
1219 // 2 ranges.
1220 ScRange aR1 = aRange;
1221 ScRange aR2 = aRange;
1222 if (aRange.aStart.Col() < aMoveRange.aStart.Col())
1223 {
1224 // Left half is outside the sorted range while the right half is inside.
1225 aR1.aEnd.SetCol(aMoveRange.aStart.Col()-1);
1226 aR2.aStart.SetCol(aMoveRange.aStart.Col());
1227 expandRowRange(aR2, aMoveRange.aStart.Row(), aMoveRange.aEnd.Row());
1228 }
1229 else
1230 {
1231 // Left half is inside the sorted range while the right half is outside.
1232 aR1.aEnd.SetCol(aMoveRange.aEnd.Col()-1);
1233 aR2.aStart.SetCol(aMoveRange.aEnd.Col());
1234 expandRowRange(aR1, aMoveRange.aStart.Row(), aMoveRange.aEnd.Row());
1235 }
1236
1237 aGrpListenerRanges.set(GetDoc(), aR1, true);
1238 aGrpListenerRanges.set(GetDoc(), aR2, true);
1239 }
1240 }
1241
1242 // Split formula groups at the sort range boundaries (if applicable).
1243 std::vector<SCROW> aRowBounds;
1244 aRowBounds.reserve(2);
1245 aRowBounds.push_back(nRow1);
1246 aRowBounds.push_back(nRow2+1);
1247 for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
1248 SplitFormulaGroups(nCol, aRowBounds);
1249
1250 // Cells in the data rows only reference values in the document. Make
1251 // a copy before updating the document.
1252 std::vector<std::unique_ptr<SortedColumn>> aSortedCols; // storage for copied cells.
1253 SortedRowFlags aRowFlags(GetDoc().GetSheetLimits());
1254 std::vector<SvtListener*> aListenersDummy;
1255 fillSortedColumnArray(aSortedCols, aRowFlags, aListenersDummy, pArray, nTab, nCol1, nCol2, pProgress, this);
1256
1257 for (size_t i = 0, n = aSortedCols.size(); i < n; ++i)
1258 {
1259 SCCOL nThisCol = i + nCol1;
1260
1261 {
1262 sc::CellStoreType& rDest = aCol[nThisCol].maCells;
1263 sc::CellStoreType& rSrc = aSortedCols[i]->maCells;
1264 rSrc.transfer(nRow1, nRow2, rDest, nRow1);
1265 }
1266
1267 {
1268 sc::CellTextAttrStoreType& rDest = aCol[nThisCol].maCellTextAttrs;
1269 sc::CellTextAttrStoreType& rSrc = aSortedCols[i]->maCellTextAttrs;
1270 rSrc.transfer(nRow1, nRow2, rDest, nRow1);
1271 }
1272
1273 {
1274 sc::BroadcasterStoreType& rSrc = aSortedCols[i]->maBroadcasters;
1275 sc::BroadcasterStoreType& rDest = aCol[nThisCol].maBroadcasters;
1276
1277 // Release current broadcasters first, to prevent them from getting deleted.
1278 rDest.release_range(nRow1, nRow2);
1279
1280 // Transfer sorted broadcaster segment to the document.
1281 rSrc.transfer(nRow1, nRow2, rDest, nRow1);
1282 }
1283
1284 {
1285 sc::CellNoteStoreType& rSrc = aSortedCols[i]->maCellNotes;
1286 sc::CellNoteStoreType& rDest = aCol[nThisCol].maCellNotes;
1287
1288 // Do the same as broadcaster storage transfer (to prevent double deletion).
1289 rDest.release_range(nRow1, nRow2);
1290 rSrc.transfer(nRow1, nRow2, rDest, nRow1);
1291 aCol[nThisCol].UpdateNoteCaptions(nRow1, nRow2);
1292 }
1293
1294 // Update draw object positions
1295 aCol[nThisCol].UpdateDrawObjects(aSortedCols[i]->maCellDrawObjects, nRow1, nRow2);
1296
1297 {
1298 // Get all row spans where the pattern is not NULL.
1299 std::vector<PatternSpan> aSpans =
1300 sc::toSpanArrayWithValue<SCROW,const ScPatternAttr*,PatternSpan>(
1301 aSortedCols[i]->maPatterns);
1302
1303 for (const auto& rSpan : aSpans)
1304 {
1305 assert(rSpan.mpPattern)(static_cast <bool> (rSpan.mpPattern) ? void (0) : __assert_fail
("rSpan.mpPattern", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 1305, __extension__ __PRETTY_FUNCTION__)); // should never be NULL.
1306 rDocument.GetPool()->Put(*rSpan.mpPattern);
1307 }
1308
1309 for (const auto& rSpan : aSpans)
1310 {
1311 aCol[nThisCol].SetPatternArea(rSpan.mnRow1, rSpan.mnRow2, *rSpan.mpPattern);
1312 rDocument.GetPool()->Remove(*rSpan.mpPattern);
1313 }
1314 }
1315
1316 aCol[nThisCol].CellStorageModified();
1317 }
1318
1319 if (pArray->IsKeepQuery())
1320 {
1321 aRowFlags.maRowsHidden.build_tree();
1322 aRowFlags.maRowsFiltered.build_tree();
1323
1324 // Remove all flags in the range first.
1325 SetRowHidden(nRow1, nRow2, false);
1326 SetRowFiltered(nRow1, nRow2, false);
1327
1328 std::vector<sc::RowSpan> aSpans =
1329 sc::toSpanArray<SCROW,sc::RowSpan>(aRowFlags.maRowsHidden, nRow1);
1330
1331 for (const auto& rSpan : aSpans)
1332 SetRowHidden(rSpan.mnRow1, rSpan.mnRow2, true);
1333
1334 aSpans = sc::toSpanArray<SCROW,sc::RowSpan>(aRowFlags.maRowsFiltered, nRow1);
1335
1336 for (const auto& rSpan : aSpans)
1337 SetRowFiltered(rSpan.mnRow1, rSpan.mnRow2, true);
1338 }
1339
1340 // Set up row reorder map (for later broadcasting of reference updates).
1341 sc::ColRowReorderMapType aRowMap;
1342 const std::vector<SCCOLROW>& rOldIndices = pArray->GetOrderIndices();
1343 for (size_t i = 0, n = rOldIndices.size(); i < n; ++i)
1344 {
1345 SCROW nNew = i + nRow1;
1346 SCROW nOld = rOldIndices[i];
1347 aRowMap.emplace(nOld, nNew);
1348 }
1349
1350 // Collect all listeners within sorted range ahead of time.
1351 std::vector<SvtListener*> aListeners;
1352
1353 // Collect listeners of cell broadcasters.
1354 for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
1355 aCol[nCol].CollectListeners(aListeners, nRow1, nRow2);
1356
1357 // Get all area listeners that listen on one row within the range and end
1358 // their listening.
1359 std::vector<sc::AreaListener> aAreaListeners = rDocument.GetBASM()->GetAllListeners(
1360 aMoveRange, sc::AreaOverlapType::OneRowInside);
1361 {
1362 for (auto& rAreaListener : aAreaListeners)
1363 {
1364 rDocument.EndListeningArea(rAreaListener.maArea, rAreaListener.mbGroupListening, rAreaListener.mpListener);
1365 aListeners.push_back( rAreaListener.mpListener);
1366 }
1367 }
1368
1369 {
1370 // Get all formula cells from the former group area listener ranges.
1371
1372 std::vector<ScFormulaCell*> aFCells;
1373 FormulaCellCollectAction aAction(aFCells);
1374 aGrpListenerRanges.executeColumnAction(rDocument, aAction);
1375
1376 aListeners.insert( aListeners.end(), aFCells.begin(), aFCells.end() );
1377 }
1378
1379 // Remove any duplicate listener entries. We must ensure that we notify
1380 // each unique listener only once.
1381 std::sort(aListeners.begin(), aListeners.end());
1382 aListeners.erase(std::unique(aListeners.begin(), aListeners.end()), aListeners.end());
1383
1384 // Collect positions of all shared formula cells outside the sorted range,
1385 // and make them unshared before notifying them.
1386 sc::RefQueryFormulaGroup aFormulaGroupPos;
1387 aFormulaGroupPos.setSkipRange(ScRange(nCol1, nRow1, nTab, nCol2, nRow2, nTab));
1388
1389 std::for_each(aListeners.begin(), aListeners.end(), FormulaGroupPosCollector(aFormulaGroupPos));
1390 const sc::RefQueryFormulaGroup::TabsType& rGroupTabs = aFormulaGroupPos.getAllPositions();
1391 for (const auto& [rTab, rCols] : rGroupTabs)
1392 {
1393 for (const auto& [nCol, rCol] : rCols)
1394 {
1395 std::vector<SCROW> aBounds(rCol);
1396 rDocument.UnshareFormulaCells(rTab, nCol, aBounds);
1397 }
1398 }
1399
1400 // Notify the listeners to update their references.
1401 ReorderNotifier<sc::RefRowReorderHint, sc::ColRowReorderMapType, SCROW> aFunc(aRowMap, nTab, nCol1, nCol2);
1402 std::for_each(aListeners.begin(), aListeners.end(), aFunc);
1403
1404 // Re-group formulas in affected columns.
1405 for (const auto& [rTab, rCols] : rGroupTabs)
1406 {
1407 for (const auto& rEntry : rCols)
1408 rDocument.RegroupFormulaCells(rTab, rEntry.first);
1409 }
1410
1411 // Re-start area listeners on the reordered rows.
1412 for (const auto& rAreaListener : aAreaListeners)
1413 {
1414 ScRange aNewRange = rAreaListener.maArea;
1415 sc::ColRowReorderMapType::const_iterator itRow = aRowMap.find( aNewRange.aStart.Row());
1416 if (itRow != aRowMap.end())
1417 {
1418 aNewRange.aStart.SetRow( itRow->second);
1419 aNewRange.aEnd.SetRow( itRow->second);
1420 }
1421 rDocument.StartListeningArea(aNewRange, rAreaListener.mbGroupListening, rAreaListener.mpListener);
1422 }
1423
1424 // Re-group columns in the sorted range too.
1425 for (SCCOL i = nCol1; i <= nCol2; ++i)
1426 aCol[i].RegroupFormulaCells();
1427
1428 {
1429 // Re-start area listeners on the old group listener ranges.
1430 ListenerStartAction aAction(rDocument);
1431 aGrpListenerRanges.executeColumnAction(rDocument, aAction);
1432 }
1433}
1434
1435short ScTable::CompareCell(
1436 sal_uInt16 nSort,
1437 ScRefCellValue& rCell1, SCCOL nCell1Col, SCROW nCell1Row,
1438 ScRefCellValue& rCell2, SCCOL nCell2Col, SCROW nCell2Row ) const
1439{
1440 short nRes = 0;
1441
1442 CellType eType1 = rCell1.meType, eType2 = rCell2.meType;
1443
1444 if (!rCell1.isEmpty())
1445 {
1446 if (!rCell2.isEmpty())
1447 {
1448 bool bErr1 = false;
1449 bool bStr1 = ( eType1 != CELLTYPE_VALUE );
1450 if (eType1 == CELLTYPE_FORMULA)
1451 {
1452 if (rCell1.mpFormula->GetErrCode() != FormulaError::NONE)
1453 {
1454 bErr1 = true;
1455 bStr1 = false;
1456 }
1457 else if (rCell1.mpFormula->IsValue())
1458 {
1459 bStr1 = false;
1460 }
1461 }
1462
1463 bool bErr2 = false;
1464 bool bStr2 = ( eType2 != CELLTYPE_VALUE );
1465 if (eType2 == CELLTYPE_FORMULA)
1466 {
1467 if (rCell2.mpFormula->GetErrCode() != FormulaError::NONE)
1468 {
1469 bErr2 = true;
1470 bStr2 = false;
1471 }
1472 else if (rCell2.mpFormula->IsValue())
1473 {
1474 bStr2 = false;
1475 }
1476 }
1477
1478 if ( bStr1 && bStr2 ) // only compare strings as strings!
1479 {
1480 OUString aStr1;
1481 OUString aStr2;
1482 if (eType1 == CELLTYPE_STRING)
1483 aStr1 = rCell1.mpString->getString();
1484 else
1485 GetString(nCell1Col, nCell1Row, aStr1);
1486 if (eType2 == CELLTYPE_STRING)
1487 aStr2 = rCell2.mpString->getString();
1488 else
1489 GetString(nCell2Col, nCell2Row, aStr2);
1490
1491 bool bUserDef = aSortParam.bUserDef; // custom sort order
1492 bool bNaturalSort = aSortParam.bNaturalSort; // natural sort
1493 bool bCaseSens = aSortParam.bCaseSens; // case sensitivity
1494
1495 ScUserList* pList = ScGlobal::GetUserList();
1496 if (bUserDef && pList && pList->size() > aSortParam.nUserIndex )
1497 {
1498 const ScUserListData& rData = (*pList)[aSortParam.nUserIndex];
1499
1500 if ( bNaturalSort )
1501 nRes = naturalsort::Compare( aStr1, aStr2, bCaseSens, &rData, pSortCollator );
1502 else
1503 {
1504 if ( bCaseSens )
1505 nRes = sal::static_int_cast<short>( rData.Compare(aStr1, aStr2) );
1506 else
1507 nRes = sal::static_int_cast<short>( rData.ICompare(aStr1, aStr2) );
1508 }
1509
1510 }
1511 if (!bUserDef)
1512 {
1513 if ( bNaturalSort )
1514 nRes = naturalsort::Compare( aStr1, aStr2, bCaseSens, nullptr, pSortCollator );
1515 else
1516 nRes = static_cast<short>( pSortCollator->compareString( aStr1, aStr2 ) );
1517 }
1518 }
1519 else if ( bStr1 ) // String <-> Number or Error
1520 {
1521 if (bErr2)
1522 nRes = -1; // String in front of Error
1523 else
1524 nRes = 1; // Number in front of String
1525 }
1526 else if ( bStr2 ) // Number or Error <-> String
1527 {
1528 if (bErr1)
1529 nRes = 1; // String in front of Error
1530 else
1531 nRes = -1; // Number in front of String
1532 }
1533 else if (bErr1 && bErr2)
1534 {
1535 // nothing, two Errors are equal
1536 }
1537 else if (bErr1) // Error <-> Number
1538 {
1539 nRes = 1; // Number in front of Error
1540 }
1541 else if (bErr2) // Number <-> Error
1542 {
1543 nRes = -1; // Number in front of Error
1544 }
1545 else // Mixed numbers
1546 {
1547 double nVal1 = rCell1.getValue();
1548 double nVal2 = rCell2.getValue();
1549 if (nVal1 < nVal2)
1550 nRes = -1;
1551 else if (nVal1 > nVal2)
1552 nRes = 1;
1553 }
1554 if ( !aSortParam.maKeyState[nSort].bAscending )
1555 nRes = -nRes;
1556 }
1557 else
1558 nRes = -1;
1559 }
1560 else
1561 {
1562 if (!rCell2.isEmpty())
1563 nRes = 1;
1564 else
1565 nRes = 0; // both empty
1566 }
1567 return nRes;
1568}
1569
1570short ScTable::Compare( ScSortInfoArray* pArray, SCCOLROW nIndex1, SCCOLROW nIndex2 ) const
1571{
1572 short nRes;
1573 sal_uInt16 nSort = 0;
1574 do
1575 {
1576 ScSortInfo& rInfo1 = pArray->Get( nSort, nIndex1 );
1577 ScSortInfo& rInfo2 = pArray->Get( nSort, nIndex2 );
1578 if ( aSortParam.bByRow )
1579 nRes = CompareCell( nSort,
1580 rInfo1.maCell, static_cast<SCCOL>(aSortParam.maKeyState[nSort].nField), rInfo1.nOrg,
1581 rInfo2.maCell, static_cast<SCCOL>(aSortParam.maKeyState[nSort].nField), rInfo2.nOrg );
1582 else
1583 nRes = CompareCell( nSort,
1584 rInfo1.maCell, static_cast<SCCOL>(rInfo1.nOrg), aSortParam.maKeyState[nSort].nField,
1585 rInfo2.maCell, static_cast<SCCOL>(rInfo2.nOrg), aSortParam.maKeyState[nSort].nField );
1586 } while ( nRes == 0 && ++nSort < pArray->GetUsedSorts() );
1587 if( nRes == 0 )
1588 {
1589 ScSortInfo& rInfo1 = pArray->Get( 0, nIndex1 );
1590 ScSortInfo& rInfo2 = pArray->Get( 0, nIndex2 );
1591 if( rInfo1.nOrg < rInfo2.nOrg )
1592 nRes = -1;
1593 else if( rInfo1.nOrg > rInfo2.nOrg )
1594 nRes = 1;
1595 }
1596 return nRes;
1597}
1598
1599void ScTable::QuickSort( ScSortInfoArray* pArray, SCCOLROW nLo, SCCOLROW nHi )
1600{
1601 if ((nHi - nLo) == 1)
1602 {
1603 if (Compare(pArray, nLo, nHi) > 0)
1604 pArray->Swap( nLo, nHi );
1605 }
1606 else
1607 {
1608 SCCOLROW ni = nLo;
1609 SCCOLROW nj = nHi;
1610 do
1611 {
1612 while ((ni <= nHi) && (Compare(pArray, ni, nLo)) < 0)
1613 ni++;
1614 while ((nj >= nLo) && (Compare(pArray, nLo, nj)) < 0)
1615 nj--;
1616 if (ni <= nj)
1617 {
1618 if (ni != nj)
1619 pArray->Swap( ni, nj );
1620 ni++;
1621 nj--;
1622 }
1623 } while (ni < nj);
1624 if ((nj - nLo) < (nHi - ni))
1625 {
1626 if (nLo < nj)
1627 QuickSort(pArray, nLo, nj);
1628 if (ni < nHi)
1629 QuickSort(pArray, ni, nHi);
1630 }
1631 else
1632 {
1633 if (ni < nHi)
1634 QuickSort(pArray, ni, nHi);
1635 if (nLo < nj)
1636 QuickSort(pArray, nLo, nj);
1637 }
1638 }
1639}
1640
1641short ScTable::Compare(SCCOLROW nIndex1, SCCOLROW nIndex2) const
1642{
1643 short nRes;
1644 sal_uInt16 nSort = 0;
1645 const sal_uInt32 nMaxSorts = aSortParam.GetSortKeyCount();
1646 if (aSortParam.bByRow)
1647 {
1648 do
1649 {
1650 SCCOL nCol = static_cast<SCCOL>(aSortParam.maKeyState[nSort].nField);
1651 ScRefCellValue aCell1 = aCol[nCol].GetCellValue(nIndex1);
1652 ScRefCellValue aCell2 = aCol[nCol].GetCellValue(nIndex2);
1653 nRes = CompareCell(nSort, aCell1, nCol, nIndex1, aCell2, nCol, nIndex2);
1654 } while ( nRes == 0 && ++nSort < nMaxSorts && aSortParam.maKeyState[nSort].bDoSort );
1655 }
1656 else
1657 {
1658 do
1659 {
1660 SCROW nRow = aSortParam.maKeyState[nSort].nField;
1661 ScRefCellValue aCell1 = aCol[nIndex1].GetCellValue(nRow);
1662 ScRefCellValue aCell2 = aCol[nIndex2].GetCellValue(nRow);
1663 nRes = CompareCell( nSort, aCell1, static_cast<SCCOL>(nIndex1),
1664 nRow, aCell2, static_cast<SCCOL>(nIndex2), nRow );
1665 } while ( nRes == 0 && ++nSort < nMaxSorts && aSortParam.maKeyState[nSort].bDoSort );
1666 }
1667 return nRes;
1668}
1669
1670bool ScTable::IsSorted( SCCOLROW nStart, SCCOLROW nEnd ) const // over aSortParam
1671{
1672 for (SCCOLROW i=nStart; i<nEnd; i++)
1673 {
1674 if (Compare( i, i+1 ) > 0)
1675 return false;
1676 }
1677 return true;
1678}
1679
1680void ScTable::DecoladeRow( ScSortInfoArray* pArray, SCROW nRow1, SCROW nRow2 )
1681{
1682 SCROW nRow;
1683 int nMax = nRow2 - nRow1;
1684 for (SCROW i = nRow1; (i + 4) <= nRow2; i += 4)
1685 {
1686 nRow = comphelper::rng::uniform_int_distribution(0, nMax-1);
1687 pArray->Swap(i, nRow1 + nRow);
1688 }
1689}
1690
1691void ScTable::Sort(
1692 const ScSortParam& rSortParam, bool bKeepQuery, bool bUpdateRefs,
1693 ScProgress* pProgress, sc::ReorderParam* pUndo )
1694{
1695 InitSortCollator( rSortParam );
1696 bGlobalKeepQuery = bKeepQuery;
1697
1698 if (pUndo)
1699 {
1700 // Copy over the basic sort parameters.
1701 pUndo->mbByRow = rSortParam.bByRow;
1702 pUndo->mbPattern = rSortParam.bIncludePattern;
1703 pUndo->mbHiddenFiltered = bKeepQuery;
1704 pUndo->mbUpdateRefs = bUpdateRefs;
1705 pUndo->mbHasHeaders = rSortParam.bHasHeader;
1706 }
1707
1708 // It is assumed that the data area has already been trimmed as necessary.
1709
1710 aSortParam = rSortParam; // must be assigned before calling IsSorted()
1711 if (rSortParam.bByRow)
1712 {
1713 SCROW nLastRow = rSortParam.nRow2;
1714 SCROW nRow1 = (rSortParam.bHasHeader ? rSortParam.nRow1 + 1 : rSortParam.nRow1);
1715 if (nRow1 < nLastRow && !IsSorted(nRow1, nLastRow))
1716 {
1717 if(pProgress)
1718 pProgress->SetState( 0, nLastRow-nRow1 );
1719
1720 std::unique_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(aSortParam, nRow1, nLastRow, bKeepQuery, bUpdateRefs));
1721
1722 if ( nLastRow - nRow1 > 255 )
1723 DecoladeRow(pArray.get(), nRow1, nLastRow);
1724
1725 QuickSort(pArray.get(), nRow1, nLastRow);
1726 if (pArray->IsUpdateRefs())
1727 SortReorderByRowRefUpdate(pArray.get(), aSortParam.nCol1, aSortParam.nCol2, pProgress);
1728 else
1729 SortReorderByRow(pArray.get(), aSortParam.nCol1, aSortParam.nCol2, pProgress);
1730
1731 if (pUndo)
1732 {
1733 pUndo->maSortRange = ScRange(rSortParam.nCol1, nRow1, nTab, rSortParam.nCol2, nLastRow, nTab);
1734 pUndo->maOrderIndices = pArray->GetOrderIndices();
1735 }
1736 }
1737 }
1738 else
1739 {
1740 SCCOL nLastCol = rSortParam.nCol2;
1741 SCCOL nCol1 = (rSortParam.bHasHeader ? rSortParam.nCol1 + 1 : rSortParam.nCol1);
1742 if (nCol1 < nLastCol && !IsSorted(nCol1, nLastCol))
1743 {
1744 if(pProgress)
1745 pProgress->SetState( 0, nLastCol-nCol1 );
1746
1747 std::unique_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(aSortParam, nCol1, nLastCol, bKeepQuery, bUpdateRefs));
1748
1749 QuickSort(pArray.get(), nCol1, nLastCol);
1750 SortReorderByColumn(pArray.get(), aSortParam.nRow1, aSortParam.nRow2, aSortParam.bIncludePattern, pProgress);
1751
1752 if (pUndo)
1753 {
1754 pUndo->maSortRange = ScRange(nCol1, aSortParam.nRow1, nTab, nLastCol, aSortParam.nRow2, nTab);
1755 pUndo->maOrderIndices = pArray->GetOrderIndices();
1756 }
1757 }
1758 }
1759 DestroySortCollator();
1760}
1761
1762void ScTable::Reorder( const sc::ReorderParam& rParam )
1763{
1764 if (rParam.maOrderIndices.empty())
1765 return;
1766
1767 std::unique_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(rParam));
1768 if (!pArray)
1769 return;
1770
1771 if (rParam.mbByRow)
1772 {
1773 // Re-play sorting from the known sort indices.
1774 pArray->ReorderByRow(rParam.maOrderIndices);
1775 if (pArray->IsUpdateRefs())
1776 SortReorderByRowRefUpdate(
1777 pArray.get(), rParam.maSortRange.aStart.Col(), rParam.maSortRange.aEnd.Col(), nullptr);
1778 else
1779 SortReorderByRow(
1780 pArray.get(), rParam.maSortRange.aStart.Col(), rParam.maSortRange.aEnd.Col(), nullptr);
1781 }
1782 else
1783 {
1784 // Ordering by column is much simpler. Just set the order indices and we are done.
1785 pArray->SetOrderIndices(rParam.maOrderIndices);
1786 SortReorderByColumn(
1787 pArray.get(), rParam.maSortRange.aStart.Row(), rParam.maSortRange.aEnd.Row(),
1788 rParam.mbPattern, nullptr);
1789 }
1790}
1791
1792namespace {
1793
1794class SubTotalRowFinder
1795{
1796 const ScTable& mrTab;
1797 const ScSubTotalParam& mrParam;
1798
1799public:
1800 SubTotalRowFinder(const ScTable& rTab, const ScSubTotalParam& rParam) :
1801 mrTab(rTab), mrParam(rParam) {}
1802
1803 bool operator() (size_t nRow, const ScFormulaCell* pCell)
1804 {
1805 if (!pCell->IsSubTotal())
1806 return false;
1807
1808 SCCOL nStartCol = mrParam.nCol1;
1809 SCCOL nEndCol = mrParam.nCol2;
1810
1811 for (SCCOL nCol : mrTab.GetColumnsRange(0, nStartCol - 1))
1812 {
1813 if (mrTab.HasData(nCol, nRow))
1814 return true;
1815 }
1816 for (SCCOL nCol : mrTab.GetColumnsRange(nEndCol + 1, mrTab.GetDoc().MaxCol()))
1817 {
1818 if (mrTab.HasData(nCol, nRow))
1819 return true;
1820 }
1821 return false;
1822 }
1823};
1824
1825}
1826
1827bool ScTable::TestRemoveSubTotals( const ScSubTotalParam& rParam )
1828{
1829 SCCOL nStartCol = rParam.nCol1;
1830 SCROW nStartRow = rParam.nRow1 + 1; // Header
1831 SCCOL nEndCol = ClampToAllocatedColumns(rParam.nCol2);
1832 SCROW nEndRow = rParam.nRow2;
1833
1834 for (SCCOL nCol = nStartCol; nCol <= nEndCol; ++nCol)
1835 {
1836 const sc::CellStoreType& rCells = aCol[nCol].maCells;
1837 SubTotalRowFinder aFunc(*this, rParam);
1838 std::pair<sc::CellStoreType::const_iterator,size_t> aPos =
1839 sc::FindFormula(rCells, nStartRow, nEndRow, aFunc);
1840 if (aPos.first != rCells.end())
1841 return true;
1842 }
1843 return false;
1844}
1845
1846namespace {
1847
1848struct RemoveSubTotalsHandler
1849{
1850 std::set<SCROW> aRemoved;
1851
1852 void operator() (size_t nRow, const ScFormulaCell* p)
1853 {
1854 if (p->IsSubTotal())
1855 aRemoved.insert(nRow);
1856 }
1857};
1858
1859}
1860
1861void ScTable::RemoveSubTotals( ScSubTotalParam& rParam )
1862{
1863 SCCOL nStartCol = rParam.nCol1;
1864 SCROW nStartRow = rParam.nRow1 + 1; // Header
1865 SCCOL nEndCol = ClampToAllocatedColumns(rParam.nCol2);
1866 SCROW nEndRow = rParam.nRow2; // will change
1867
1868 RemoveSubTotalsHandler aFunc;
1869 for (SCCOL nCol = nStartCol; nCol <= nEndCol; ++nCol)
1870 {
1871 const sc::CellStoreType& rCells = aCol[nCol].maCells;
1872 sc::ParseFormula(rCells.begin(), rCells, nStartRow, nEndRow, aFunc);
1873 }
1874
1875 auto& aRows = aFunc.aRemoved;
1876
1877 std::for_each(aRows.rbegin(), aRows.rend(), [this](const SCROW nRow) {
1878 RemoveRowBreak(nRow+1, false, true);
1879 rDocument.DeleteRow(0, nTab, rDocument.MaxCol(), nTab, nRow, 1);
1880 });
1881
1882 rParam.nRow2 -= aRows.size();
1883}
1884
1885// Delete hard number formats (for result formulas)
1886
1887static void lcl_RemoveNumberFormat( ScTable* pTab, SCCOL nCol, SCROW nRow )
1888{
1889 const ScPatternAttr* pPattern = pTab->GetPattern( nCol, nRow );
1890 if ( pPattern->GetItemSet().GetItemState( ATTR_VALUE_FORMAT, false )
1891 == SfxItemState::SET )
1892 {
1893 auto pNewPattern = std::make_unique<ScPatternAttr>( *pPattern );
1894 SfxItemSet& rSet = pNewPattern->GetItemSet();
1895 rSet.ClearItem( ATTR_VALUE_FORMAT );
1896 rSet.ClearItem( ATTR_LANGUAGE_FORMAT );
1897 pTab->SetPattern( nCol, nRow, std::move(pNewPattern) );
1898 }
1899}
1900
1901namespace {
1902
1903struct RowEntry
1904{
1905 sal_uInt16 nGroupNo;
1906 SCROW nSubStartRow;
1907 SCROW nDestRow;
1908 SCROW nFuncStart;
1909 SCROW nFuncEnd;
1910};
1911
1912}
1913
1914static const char* lcl_GetSubTotalStrId(int id)
1915{
1916 switch ( id )
1917 {
1918 case SUBTOTAL_FUNC_AVE: return STR_FUN_TEXT_AVGreinterpret_cast<char const *>("STR_FUN_TEXT_AVG" "\004"
u8"Average");
1919 case SUBTOTAL_FUNC_CNT:
1920 case SUBTOTAL_FUNC_CNT2: return STR_FUN_TEXT_COUNTreinterpret_cast<char const *>("STR_FUN_TEXT_COUNT" "\004"
u8"Count");
1921 case SUBTOTAL_FUNC_MAX: return STR_FUN_TEXT_MAXreinterpret_cast<char const *>("STR_FUN_TEXT_MAX" "\004"
u8"Max");
1922 case SUBTOTAL_FUNC_MIN: return STR_FUN_TEXT_MINreinterpret_cast<char const *>("STR_FUN_TEXT_MIN" "\004"
u8"Min");
1923 case SUBTOTAL_FUNC_PROD: return STR_FUN_TEXT_PRODUCTreinterpret_cast<char const *>("STR_FUN_TEXT_PRODUCT" "\004"
u8"Product");
1924 case SUBTOTAL_FUNC_STD:
1925 case SUBTOTAL_FUNC_STDP: return STR_FUN_TEXT_STDDEVreinterpret_cast<char const *>("STR_FUN_TEXT_STDDEV" "\004"
u8"StDev");
1926 case SUBTOTAL_FUNC_SUM: return STR_FUN_TEXT_SUMreinterpret_cast<char const *>("STR_FUN_TEXT_SUM" "\004"
u8"Sum");
1927 case SUBTOTAL_FUNC_VAR:
1928 case SUBTOTAL_FUNC_VARP: return STR_FUN_TEXT_VARreinterpret_cast<char const *>("STR_FUN_TEXT_VAR" "\004"
u8"Var");
1929 default:
1930 {
1931 return STR_EMPTYDATAreinterpret_cast<char const *>("STR_EMPTYDATA" "\004" u8"(empty)"
);
1932 // added to avoid warnings
1933 }
1934 }
1935}
1936
1937// new intermediate results
1938// rParam.nRow2 is changed!
1939
1940bool ScTable::DoSubTotals( ScSubTotalParam& rParam )
1941{
1942 SCCOL nStartCol = rParam.nCol1;
1943 SCROW nStartRow = rParam.nRow1 + 1; // Header
1944 SCCOL nEndCol = rParam.nCol2;
1945 SCROW nEndRow = rParam.nRow2; // will change
1946 sal_uInt16 i;
1947
1948 // Remove empty rows at the end
1949 // so that all exceeding (rDocument.MaxRow()) can be found by InsertRow (#35180#)
1950 // If sorted, all empty rows are at the end.
1951 SCSIZE nEmpty = GetEmptyLinesInBlock( nStartCol, nStartRow, nEndCol, nEndRow, DIR_BOTTOM );
1952 nEndRow -= nEmpty;
1953
1954 sal_uInt16 nLevelCount = 0; // Number of levels
1955 bool bDoThis = true;
1956 for (i=0; i<MAXSUBTOTAL && bDoThis; i++)
1957 if (rParam.bGroupActive[i])
1958 nLevelCount = i+1;
1959 else
1960 bDoThis = false;
1961
1962 if (nLevelCount==0) // do nothing
1963 return true;
1964
1965 SCCOL* nGroupCol = rParam.nField; // columns which will be used when grouping
1966
1967 // With (blank) as a separate category, subtotal rows from
1968 // the other columns must always be tested
1969 // (previously only when a column occurred more than once)
1970 bool bTestPrevSub = ( nLevelCount > 1 );
1971
1972 OUString aSubString;
1973
1974 bool bIgnoreCase = !rParam.bCaseSens;
1975
1976 OUString aCompString[MAXSUBTOTAL];
1977
1978 //TODO: sort?
1979
1980 ScStyleSheet* pStyle = static_cast<ScStyleSheet*>(rDocument.GetStyleSheetPool()->Find(
1981 ScResId(STR_STYLENAME_RESULTreinterpret_cast<char const *>("STR_STYLENAME_RESULT" "\004"
u8"Result")), SfxStyleFamily::Para ));
1982
1983 bool bSpaceLeft = true; // Success when inserting?
1984
1985 // For performance reasons collect formula entries so their
1986 // references don't have to be tested for updates each time a new row is
1987 // inserted
1988 RowEntry aRowEntry;
1989 ::std::vector< RowEntry > aRowVector;
1990
1991 for (sal_uInt16 nLevel=0; nLevel<nLevelCount && bSpaceLeft; nLevel++)
1992 {
1993 aRowEntry.nGroupNo = nLevelCount - nLevel - 1;
1994
1995 // how many results per level
1996 SCCOL nResCount = rParam.nSubTotals[aRowEntry.nGroupNo];
1997 // result functions
1998 ScSubTotalFunc* pResFunc = rParam.pFunctions[aRowEntry.nGroupNo];
1999
2000 if (nResCount > 0) // otherwise only sort
2001 {
2002 for (i=0; i<=aRowEntry.nGroupNo; i++)
2003 {
2004 GetString( nGroupCol[i], nStartRow, aSubString );
2005 if ( bIgnoreCase )
2006 aCompString[i] = ScGlobal::getCharClassPtr()->uppercase( aSubString );
2007 else
2008 aCompString[i] = aSubString;
2009 } // aSubString stays on the last
2010
2011 bool bBlockVis = false; // group visible?
2012 aRowEntry.nSubStartRow = nStartRow;
2013 for (SCROW nRow=nStartRow; nRow<=nEndRow+1 && bSpaceLeft; nRow++)
2014 {
2015 bool bChanged;
2016 if (nRow>nEndRow)
2017 bChanged = true;
2018 else
2019 {
2020 bChanged = false;
2021 OUString aString;
2022 for (i=0; i<=aRowEntry.nGroupNo && !bChanged; i++)
2023 {
2024 GetString( nGroupCol[i], nRow, aString );
2025 if (bIgnoreCase)
2026 aString = ScGlobal::getCharClassPtr()->uppercase(aString);
2027 // when sorting, blanks are separate group
2028 // otherwise blank cells are allowed below
2029 bChanged = ( ( !aString.isEmpty() || rParam.bDoSort ) &&
2030 aString != aCompString[i] );
2031 }
2032 if ( bChanged && bTestPrevSub )
2033 {
2034 // No group change on rows that will contain subtotal formulas
2035 bChanged = std::none_of(aRowVector.begin(), aRowVector.end(),
2036 [&nRow](const RowEntry& rEntry) { return rEntry.nDestRow == nRow; });
2037 }
2038 }
2039 if ( bChanged )
2040 {
2041 aRowEntry.nDestRow = nRow;
2042 aRowEntry.nFuncStart = aRowEntry.nSubStartRow;
2043 aRowEntry.nFuncEnd = nRow-1;
2044
2045 bSpaceLeft = rDocument.InsertRow( 0, nTab, rDocument.MaxCol(), nTab,
2046 aRowEntry.nDestRow, 1 );
2047 DBShowRow( aRowEntry.nDestRow, bBlockVis );
2048 if ( rParam.bPagebreak && nRow < rDocument.MaxRow() &&
2049 aRowEntry.nSubStartRow != nStartRow && nLevel == 0)
2050 SetRowBreak(aRowEntry.nSubStartRow, false, true);
2051
2052 if (bSpaceLeft)
2053 {
2054 for ( auto& rRowEntry : aRowVector)
2055 {
2056 if ( aRowEntry.nDestRow <= rRowEntry.nSubStartRow )
2057 ++rRowEntry.nSubStartRow;
2058 if ( aRowEntry.nDestRow <= rRowEntry.nDestRow )
2059 ++rRowEntry.nDestRow;
2060 if ( aRowEntry.nDestRow <= rRowEntry.nFuncStart )
2061 ++rRowEntry.nFuncStart;
2062 if ( aRowEntry.nDestRow <= rRowEntry.nFuncEnd )
2063 ++rRowEntry.nFuncEnd;
2064 }
2065 // collect formula positions
2066 aRowVector.push_back( aRowEntry );
2067
2068 OUString aOutString = aSubString;
2069 if (aOutString.isEmpty())
2070 aOutString = ScResId( STR_EMPTYDATAreinterpret_cast<char const *>("STR_EMPTYDATA" "\004" u8"(empty)"
) );
2071 aOutString += " ";
2072 const char* pStrId = STR_TABLE_ERGEBNISreinterpret_cast<char const *>("STR_TABLE_ERGEBNIS" "\004"
u8"Result");
2073 if ( nResCount == 1 )
2074 pStrId = lcl_GetSubTotalStrId(pResFunc[0]);
2075 aOutString += ScResId(pStrId);
2076 SetString( nGroupCol[aRowEntry.nGroupNo], aRowEntry.nDestRow, nTab, aOutString );
2077 ApplyStyle( nGroupCol[aRowEntry.nGroupNo], aRowEntry.nDestRow, pStyle );
2078
2079 ++nRow;
2080 ++nEndRow;
2081 aRowEntry.nSubStartRow = nRow;
2082 for (i=0; i<=aRowEntry.nGroupNo; i++)
2083 {
2084 GetString( nGroupCol[i], nRow, aSubString );
2085 if ( bIgnoreCase )
2086 aCompString[i] = ScGlobal::getCharClassPtr()->uppercase( aSubString );
2087 else
2088 aCompString[i] = aSubString;
2089 }
2090 }
2091 }
2092 bBlockVis = !RowFiltered(nRow);
2093 }
2094 }
2095 }
2096
2097 if (!aRowVector.empty())
2098 {
2099 // generate global total
2100 SCROW nGlobalStartRow = aRowVector[0].nSubStartRow;
2101 SCROW nGlobalStartFunc = aRowVector[0].nFuncStart;
2102 SCROW nGlobalEndRow = 0;
2103 SCROW nGlobalEndFunc = 0;
2104 for (const auto& rRowEntry : aRowVector)
2105 {
2106 nGlobalEndRow = (nGlobalEndRow < rRowEntry.nDestRow) ? rRowEntry.nDestRow : nGlobalEndRow;
2107 nGlobalEndFunc = (nGlobalEndFunc < rRowEntry.nFuncEnd) ? rRowEntry.nFuncEnd : nGlobalEndRow;
2108 }
2109
2110 for (sal_uInt16 nLevel = 0; nLevel<nLevelCount; nLevel++)
2111 {
2112 const sal_uInt16 nGroupNo = nLevelCount - nLevel - 1;
2113 const ScSubTotalFunc* pResFunc = rParam.pFunctions[nGroupNo];
2114 if (!pResFunc)
2115 {
2116 // No subtotal function given for this group => no formula or
2117 // label and do not insert a row.
2118 continue;
2119 }
2120
2121 // increment end row
2122 nGlobalEndRow++;
2123
2124 // add row entry for formula
2125 aRowEntry.nGroupNo = nGroupNo;
2126 aRowEntry.nSubStartRow = nGlobalStartRow;
2127 aRowEntry.nFuncStart = nGlobalStartFunc;
2128 aRowEntry.nDestRow = nGlobalEndRow;
2129 aRowEntry.nFuncEnd = nGlobalEndFunc;
2130
2131 // increment row
2132 nGlobalEndFunc++;
2133
2134 bSpaceLeft = rDocument.InsertRow(0, nTab, rDocument.MaxCol(), nTab, aRowEntry.nDestRow, 1);
2135
2136 if (bSpaceLeft)
2137 {
2138 aRowVector.push_back(aRowEntry);
2139 nEndRow++;
2140 DBShowRow(aRowEntry.nDestRow, true);
2141
2142 // insert label
2143 OUString label = ScResId(STR_TABLE_GRANDreinterpret_cast<char const *>("STR_TABLE_GRAND" "\004"
u8"Grand")) + " " + ScResId(lcl_GetSubTotalStrId(pResFunc[0]));
2144 SetString(nGroupCol[aRowEntry.nGroupNo], aRowEntry.nDestRow, nTab, label);
2145 ApplyStyle(nGroupCol[aRowEntry.nGroupNo], aRowEntry.nDestRow, pStyle);
2146 }
2147 }
2148 }
2149
2150 // now insert the formulas
2151 ScComplexRefData aRef;
2152 aRef.InitFlags();
2153 aRef.Ref1.SetAbsTab(nTab);
2154 aRef.Ref2.SetAbsTab(nTab);
2155 for (const auto& rRowEntry : aRowVector)
2156 {
2157 SCCOL nResCount = rParam.nSubTotals[rRowEntry.nGroupNo];
2158 SCCOL* nResCols = rParam.pSubTotals[rRowEntry.nGroupNo];
2159 ScSubTotalFunc* pResFunc = rParam.pFunctions[rRowEntry.nGroupNo];
2160 for ( SCCOL nResult=0; nResult < nResCount; ++nResult )
2161 {
2162 aRef.Ref1.SetAbsCol(nResCols[nResult]);
2163 aRef.Ref1.SetAbsRow(rRowEntry.nFuncStart);
2164 aRef.Ref2.SetAbsCol(nResCols[nResult]);
2165 aRef.Ref2.SetAbsRow(rRowEntry.nFuncEnd);
2166
2167 ScTokenArray aArr(rDocument);
2168 aArr.AddOpCode( ocSubTotal );
2169 aArr.AddOpCode( ocOpen );
2170 aArr.AddDouble( static_cast<double>(pResFunc[nResult]) );
2171 aArr.AddOpCode( ocSep );
2172 aArr.AddDoubleReference( aRef );
2173 aArr.AddOpCode( ocClose );
2174 aArr.AddOpCode( ocStop );
2175 ScFormulaCell* pCell = new ScFormulaCell(
2176 rDocument, ScAddress(nResCols[nResult], rRowEntry.nDestRow, nTab), aArr);
2177 if ( rParam.bIncludePattern )
2178 pCell->SetNeedNumberFormat(true);
2179
2180 SetFormulaCell(nResCols[nResult], rRowEntry.nDestRow, pCell);
2181 if ( nResCols[nResult] != nGroupCol[rRowEntry.nGroupNo] )
2182 {
2183 ApplyStyle( nResCols[nResult], rRowEntry.nDestRow, pStyle );
2184
2185 lcl_RemoveNumberFormat( this, nResCols[nResult], rRowEntry.nDestRow );
2186 }
2187 }
2188
2189 }
2190
2191 //TODO: according to setting, shift intermediate-sum rows up?
2192
2193 //TODO: create Outlines directly?
2194
2195 if (bSpaceLeft)
2196 DoAutoOutline( nStartCol, nStartRow, nEndCol, nEndRow );
2197
2198 rParam.nRow2 = nEndRow; // new end
2199 return bSpaceLeft;
2200}
2201
2202namespace {
2203
2204class QueryEvaluator
2205{
2206 ScDocument& mrDoc;
2207 svl::SharedStringPool& mrStrPool;
2208 const ScTable& mrTab;
2209 const ScQueryParam& mrParam;
2210 bool mpTestEqualCondition;
2211 utl::TransliterationWrapper* mpTransliteration;
2212 CollatorWrapper* mpCollator;
2213 const bool mbMatchWholeCell;
2214 const bool mbCaseSensitive;
2215
2216 static bool isPartialTextMatchOp(const ScQueryEntry& rEntry)
2217 {
2218 switch (rEntry.eOp)
2219 {
2220 // these operators can only be used with textural comparisons.
2221 case SC_CONTAINS:
2222 case SC_DOES_NOT_CONTAIN:
2223 case SC_BEGINS_WITH:
2224 case SC_ENDS_WITH:
2225 case SC_DOES_NOT_BEGIN_WITH:
2226 case SC_DOES_NOT_END_WITH:
2227 return true;
2228 default:
2229 ;
2230 }
2231 return false;
2232 }
2233
2234 static bool isTextMatchOp(const ScQueryEntry& rEntry)
2235 {
2236 if (isPartialTextMatchOp(rEntry))
2237 return true;
2238
2239 switch (rEntry.eOp)
2240 {
2241 // these operators can be used for either textural or value comparison.
2242 case SC_EQUAL:
2243 case SC_NOT_EQUAL:
2244 return true;
2245 default:
2246 ;
2247 }
2248 return false;
2249 }
2250
2251 bool isRealWildOrRegExp(const ScQueryEntry& rEntry) const
2252 {
2253 if (mrParam.eSearchType == utl::SearchParam::SearchType::Normal)
2254 return false;
2255
2256 return isTextMatchOp(rEntry);
2257 }
2258
2259 bool isTestWildOrRegExp(const ScQueryEntry& rEntry) const
2260 {
2261 if (!mpTestEqualCondition)
2262 return false;
2263
2264 if (mrParam.eSearchType == utl::SearchParam::SearchType::Normal)
2265 return false;
2266
2267 return (rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_GREATER_EQUAL);
2268 }
2269
2270 void setupTransliteratorIfNeeded()
2271 {
2272 if (!mpTransliteration)
2273 mpTransliteration = mrParam.bCaseSens ? ScGlobal::GetCaseTransliteration() : ScGlobal::GetpTransliteration();
2274 }
2275
2276 void setupCollatorIfNeeded()
2277 {
2278 if (!mpCollator)
2279 mpCollator = mrParam.bCaseSens ? ScGlobal::GetCaseCollator() : ScGlobal::GetCollator();
2280 }
2281
2282public:
2283 QueryEvaluator(ScDocument& rDoc, const ScTable& rTab, const ScQueryParam& rParam,
2284 bool pTestEqualCondition) :
2285 mrDoc(rDoc),
2286 mrStrPool(rDoc.GetSharedStringPool()),
2287 mrTab(rTab),
2288 mrParam(rParam),
2289 mpTestEqualCondition(pTestEqualCondition),
2290 mpTransliteration(nullptr),
2291 mpCollator(nullptr),
2292 mbMatchWholeCell(rDoc.GetDocOptions().IsMatchWholeCell()),
2293 mbCaseSensitive( rParam.bCaseSens )
2294 {
2295 }
2296
2297 bool isQueryByValue(
2298 const ScQueryEntry::Item& rItem, SCCOL nCol, SCROW nRow, ScRefCellValue& rCell)
2299 {
2300 if (rItem.meType == ScQueryEntry::ByString)
2301 return false;
2302
2303 if (!rCell.isEmpty())
2304 {
2305 if (rCell.meType == CELLTYPE_FORMULA && rCell.mpFormula->GetErrCode() != FormulaError::NONE)
2306 // Error values are compared as string.
2307 return false;
2308
2309 return rCell.hasNumeric();
2310 }
2311
2312 return mrTab.HasValueData(nCol, nRow);
2313 }
2314
2315 bool isQueryByString(
2316 const ScQueryEntry& rEntry, const ScQueryEntry::Item& rItem,
2317 SCCOL nCol, SCROW nRow, const ScRefCellValue& rCell)
2318 {
2319 if (isTextMatchOp(rEntry))
2320 return true;
2321
2322 if (rItem.meType != ScQueryEntry::ByString)
2323 return false;
2324
2325 if (!rCell.isEmpty())
2326 return rCell.hasString();
2327
2328 return mrTab.HasStringData(nCol, nRow);
2329 }
2330
2331 std::pair<bool,bool> compareByValue(
2332 const ScRefCellValue& rCell, SCCOL nCol, SCROW nRow,
2333 const ScQueryEntry& rEntry, const ScQueryEntry::Item& rItem,
2334 const ScInterpreterContext* pContext)
2335 {
2336 bool bOk = false;
2337 bool bTestEqual = false;
2338 double nCellVal;
2339 if (!rCell.isEmpty())
2340 {
2341 switch (rCell.meType)
2342 {
2343 case CELLTYPE_VALUE :
2344 nCellVal = rCell.mfValue;
2345 break;
2346 case CELLTYPE_FORMULA :
2347 nCellVal = rCell.mpFormula->GetValue();
2348 break;
2349 default:
2350 nCellVal = 0.0;
2351 }
2352
2353 }
2354 else
2355 nCellVal = mrTab.GetValue(nCol, nRow);
2356
2357 /* NOTE: lcl_PrepareQuery() prepares a filter query such that if a
2358 * date+time format was queried rEntry.bQueryByDate is not set. In
2359 * case other queries wanted to use this mechanism they should do
2360 * the same, in other words only if rEntry.nVal is an integer value
2361 * rEntry.bQueryByDate should be true and the time fraction be
2362 * stripped here. */
2363 if (rItem.meType == ScQueryEntry::ByDate)
2364 {
2365 sal_uInt32 nNumFmt = pContext ? mrTab.GetNumberFormat(*pContext, ScAddress(nCol, nRow, mrTab.GetTab())) :
2366 mrTab.GetNumberFormat(nCol, nRow);
2367 SvNumberFormatter* pFormatter = pContext ? pContext->GetFormatTable() : mrDoc.GetFormatTable();
2368 const SvNumberformat* pEntry = pFormatter->GetEntry(nNumFmt);
2369 if (pEntry)
2370 {
2371 SvNumFormatType nNumFmtType = pEntry->GetType();
2372 /* NOTE: Omitting the check for absence of
2373 * css::util::NumberFormat::TIME would include also date+time formatted
2374 * values of the same day. That may be desired in some
2375 * cases, querying all time values of a day, but confusing
2376 * in other cases. A user can always setup a standard
2377 * filter query for x >= date AND x < date+1 */
2378 if ((nNumFmtType & SvNumFormatType::DATE) && !(nNumFmtType & SvNumFormatType::TIME))
2379 {
2380 // The format is of date type. Strip off the time
2381 // element.
2382 nCellVal = ::rtl::math::approxFloor(nCellVal);
2383 }
2384 }
2385 }
2386
2387 switch (rEntry.eOp)
2388 {
2389 case SC_EQUAL :
2390 bOk = ::rtl::math::approxEqual(nCellVal, rItem.mfVal);
2391 break;
2392 case SC_LESS :
2393 bOk = (nCellVal < rItem.mfVal) && !::rtl::math::approxEqual(nCellVal, rItem.mfVal);
2394 break;
2395 case SC_GREATER :
2396 bOk = (nCellVal > rItem.mfVal) && !::rtl::math::approxEqual(nCellVal, rItem.mfVal);
2397 break;
2398 case SC_LESS_EQUAL :
2399 bOk = (nCellVal < rItem.mfVal) || ::rtl::math::approxEqual(nCellVal, rItem.mfVal);
2400 if ( bOk && mpTestEqualCondition )
2401 bTestEqual = ::rtl::math::approxEqual(nCellVal, rItem.mfVal);
2402 break;
2403 case SC_GREATER_EQUAL :
2404 bOk = (nCellVal > rItem.mfVal) || ::rtl::math::approxEqual( nCellVal, rItem.mfVal);
2405 if ( bOk && mpTestEqualCondition )
2406 bTestEqual = ::rtl::math::approxEqual(nCellVal, rItem.mfVal);
2407 break;
2408 case SC_NOT_EQUAL :
2409 bOk = !::rtl::math::approxEqual(nCellVal, rItem.mfVal);
2410 break;
2411 default:
2412 {
2413 // added to avoid warnings
2414 }
2415 }
2416
2417 return std::pair<bool,bool>(bOk, bTestEqual);
2418 }
2419
2420 std::pair<bool,bool> compareByString(
2421 ScRefCellValue& rCell, SCROW nRow, const ScQueryEntry& rEntry, const ScQueryEntry::Item& rItem,
2422 const ScInterpreterContext* pContext)
2423 {
2424 if (!rCell.isEmpty())
2425 {
2426 if (rCell.meType == CELLTYPE_FORMULA && rCell.mpFormula->GetErrCode() != FormulaError::NONE)
2427 {
2428 // Error cell is evaluated as string (for now).
2429 const svl::SharedString aCellStr = mrStrPool.intern(ScGlobal::GetErrorString(rCell.mpFormula->GetErrCode()));
2430 return compareByStringComparator(rEntry, rItem, &aCellStr, nullptr);
2431 }
2432 else if (rCell.meType == CELLTYPE_STRING)
2433 {
2434 return compareByStringComparator(rEntry, rItem, rCell.mpString, nullptr);
2435 }
2436 else
2437 {
2438 sal_uInt32 nFormat = pContext ? mrTab.GetNumberFormat( *pContext, ScAddress(static_cast<SCCOL>(rEntry.nField), nRow, mrTab.GetTab()) ) :
2439 mrTab.GetNumberFormat( static_cast<SCCOL>(rEntry.nField), nRow );
2440 OUString aStr;
2441 SvNumberFormatter* pFormatter = pContext ? pContext->GetFormatTable() : mrDoc.GetFormatTable();
2442 ScCellFormat::GetInputString(rCell, nFormat, aStr, *pFormatter, mrDoc);
2443 return compareByStringComparator(rEntry, rItem, nullptr, &aStr);
2444 }
2445 }
2446 else
2447 {
2448 OUString aStr;
2449 mrTab.GetInputString(static_cast<SCCOL>(rEntry.nField), nRow, aStr);
2450 return compareByStringComparator(rEntry, rItem, nullptr, &aStr);
2451 }
2452 }
2453
2454 // Called from compareByString() method, where different sources of strings are checked.
2455 // The value is placed inside one parameter: [pValueSource1] or [pValueSource2] but never in both.
2456 std::pair<bool,bool> compareByStringComparator(const ScQueryEntry& rEntry, const ScQueryEntry::Item& rItem,
2457 const svl::SharedString* pValueSource1, const OUString * pValueSource2)
2458 {
2459 bool bOk = false;
2460 bool bTestEqual = false;
2461 bool bMatchWholeCell = mbMatchWholeCell;
2462 if (isPartialTextMatchOp(rEntry))
2463 // may have to do partial textural comparison.
2464 bMatchWholeCell = false;
2465
2466 const bool bRealWildOrRegExp = isRealWildOrRegExp(rEntry);
2467 const bool bTestWildOrRegExp = isTestWildOrRegExp(rEntry);
2468
2469 // [pValueSource1] or [pValueSource2] but never both of them or none of them
2470 assert((pValueSource1 != nullptr) != (pValueSource2 != nullptr))(static_cast <bool> ((pValueSource1 != nullptr) != (pValueSource2
!= nullptr)) ? void (0) : __assert_fail ("(pValueSource1 != nullptr) != (pValueSource2 != nullptr)"
, "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 2470, __extension__ __PRETTY_FUNCTION__));
2471
2472 if ( bRealWildOrRegExp || bTestWildOrRegExp )
2473 {
2474 const OUString & rValue = pValueSource1 ? pValueSource1->getString() : *pValueSource2;
2475
2476 sal_Int32 nStart = 0;
2477 sal_Int32 nEnd = rValue.getLength();
2478
2479 // from 614 on, nEnd is behind the found text
2480 bool bMatch = false;
2481 if ( rEntry.eOp == SC_ENDS_WITH || rEntry.eOp == SC_DOES_NOT_END_WITH )
2482 {
2483 nEnd = 0;
2484 nStart = rValue.getLength();
2485 bMatch = rEntry.GetSearchTextPtr( mrParam.eSearchType, mrParam.bCaseSens, bMatchWholeCell )
2486 ->SearchBackward(rValue, &nStart, &nEnd);
2487 }
2488 else
2489 {
2490 bMatch = rEntry.GetSearchTextPtr( mrParam.eSearchType, mrParam.bCaseSens, bMatchWholeCell )
2491 ->SearchForward(rValue, &nStart, &nEnd);
2492 }
2493 if ( bMatch && bMatchWholeCell
2494 && (nStart != 0 || nEnd != rValue.getLength()) )
2495 bMatch = false; // RegExp must match entire cell string
2496 if ( bRealWildOrRegExp )
2497 {
2498 switch (rEntry.eOp)
2499 {
2500 case SC_EQUAL:
2501 case SC_CONTAINS:
2502 bOk = bMatch;
2503 break;
2504 case SC_NOT_EQUAL:
2505 case SC_DOES_NOT_CONTAIN:
2506 bOk = !bMatch;
2507 break;
2508 case SC_BEGINS_WITH:
2509 bOk = ( bMatch && (nStart == 0) );
2510 break;
2511 case SC_DOES_NOT_BEGIN_WITH:
2512 bOk = !( bMatch && (nStart == 0) );
2513 break;
2514 case SC_ENDS_WITH:
2515 bOk = ( bMatch && (nEnd == rValue.getLength()) );
2516 break;
2517 case SC_DOES_NOT_END_WITH:
2518 bOk = !( bMatch && (nEnd == rValue.getLength()) );
2519 break;
2520 default:
2521 {
2522 // added to avoid warnings
2523 }
2524 }
2525 }
2526 else
2527 bTestEqual = bMatch;
2528 }
2529 if ( !bRealWildOrRegExp )
2530 {
2531 // Simple string matching i.e. no regexp match.
2532 if (isTextMatchOp(rEntry))
2533 {
2534 if (rItem.meType != ScQueryEntry::ByString && rItem.maString.isEmpty())
2535 {
2536 // #i18374# When used from functions (match, countif, sumif, vlookup, hlookup, lookup),
2537 // the query value is assigned directly, and the string is empty. In that case,
2538 // don't find any string (isEqual would find empty string results in formula cells).
2539 bOk = false;
2540 if ( rEntry.eOp == SC_NOT_EQUAL )
2541 bOk = !bOk;
2542 }
2543 else if ( bMatchWholeCell )
2544 {
2545 if (pValueSource1)
2546 {
2547 // Fast string equality check by comparing string identifiers.
2548 if (mrParam.bCaseSens)
2549 {
2550 bOk = pValueSource1->getData() == rItem.maString.getData();
2551 }
2552 else
2553 {
2554 bOk = pValueSource1->getDataIgnoreCase() == rItem.maString.getDataIgnoreCase();
2555 }
2556 }
2557 else // if (pValueSource2)
2558 {
2559 if (mrParam.bCaseSens)
2560 {
2561 bOk = (*pValueSource2 == rItem.maString.getString());
2562 }
2563 else
2564 {
2565 // fallback
2566 const svl::SharedString rSource2(mrStrPool.intern(*pValueSource2));
2567 // Fast string equality check by comparing string identifiers.
2568 bOk = rSource2.getDataIgnoreCase() == rItem.maString.getDataIgnoreCase();
2569 }
2570 }
2571
2572 if ( rEntry.eOp == SC_NOT_EQUAL )
2573 bOk = !bOk;
2574 }
2575 else
2576 {
2577 // Where do we find a match (if at all)
2578 sal_Int32 nStrPos;
2579
2580 if (!mbCaseSensitive)
2581 { // Common case for vlookup etc.
2582 const svl::SharedString rSource(pValueSource1? *pValueSource1 : mrStrPool.intern(*pValueSource2));
2583
2584 const rtl_uString *pQuer = rItem.maString.getDataIgnoreCase();
2585 const rtl_uString *pCellStr = rSource.getDataIgnoreCase();
2586
2587 assert(pQuer != nullptr)(static_cast <bool> (pQuer != nullptr) ? void (0) : __assert_fail
("pQuer != nullptr", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 2587, __extension__ __PRETTY_FUNCTION__));
2588 assert(pCellStr != nullptr)(static_cast <bool> (pCellStr != nullptr) ? void (0) : __assert_fail
("pCellStr != nullptr", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 2588, __extension__ __PRETTY_FUNCTION__));
2589
2590 const sal_Int32 nIndex = (rEntry.eOp == SC_ENDS_WITH ||
2591 rEntry.eOp == SC_DOES_NOT_END_WITH) ?
2592 (pCellStr->length - pQuer->length) : 0;
2593
2594 if (nIndex < 0)
2595 nStrPos = -1;
2596 else if (rEntry.eOp == SC_EQUAL ||
2597 rEntry.eOp == SC_NOT_EQUAL)
2598 {
2599 nStrPos = pCellStr == pQuer ? 0 : -1;
2600 }
2601 else
2602 { // OUString::indexOf
2603 nStrPos = rtl_ustr_indexOfStr_WithLength(
2604 pCellStr->buffer + nIndex, pCellStr->length - nIndex,
2605 pQuer->buffer, pQuer->length );
2606
2607 if (nStrPos >= 0)
2608 nStrPos += nIndex;
2609 }
2610 }
2611 else
2612 {
2613 const OUString & rValue = pValueSource1 ? pValueSource1->getString() : *pValueSource2;
2614 const OUString aQueryStr = rItem.maString.getString();
2615 const LanguageType nLang = ScGlobal::xSysLocale->GetLanguageTag().getLanguageType();
2616 setupTransliteratorIfNeeded();
2617 const OUString aCell( mpTransliteration->transliterate(
2618 rValue, nLang, 0, rValue.getLength(),
2619 nullptr ) );
2620
2621 const OUString aQuer( mpTransliteration->transliterate(
2622 aQueryStr, nLang, 0, aQueryStr.getLength(),
2623 nullptr ) );
2624
2625 const sal_Int32 nIndex = (rEntry.eOp == SC_ENDS_WITH || rEntry.eOp == SC_DOES_NOT_END_WITH) ?
2626 (aCell.getLength() - aQuer.getLength()) : 0;
2627 nStrPos = ((nIndex < 0) ? -1 : aCell.indexOf( aQuer, nIndex ));
2628 }
2629 switch (rEntry.eOp)
2630 {
2631 case SC_EQUAL:
2632 bOk = ( nStrPos == 0 );
2633 break;
2634 case SC_CONTAINS:
2635 bOk = ( nStrPos != -1 );
2636 break;
2637 case SC_NOT_EQUAL:
2638 bOk = ( nStrPos != 0 );
2639 break;
2640 case SC_DOES_NOT_CONTAIN:
2641 bOk = ( nStrPos == -1 );
2642 break;
2643 case SC_BEGINS_WITH:
2644 bOk = ( nStrPos == 0 );
2645 break;
2646 case SC_DOES_NOT_BEGIN_WITH:
2647 bOk = ( nStrPos != 0 );
2648 break;
2649 case SC_ENDS_WITH:
2650 bOk = ( nStrPos >= 0 );
2651 break;
2652 case SC_DOES_NOT_END_WITH:
2653 bOk = ( nStrPos < 0 );
2654 break;
2655 default:
2656 {
2657 // added to avoid warnings
2658 }
2659 }
2660 }
2661 }
2662 else
2663 { // use collator here because data was probably sorted
2664 const OUString & rValue = pValueSource1 ? pValueSource1->getString() : *pValueSource2;
2665 setupCollatorIfNeeded();
2666 sal_Int32 nCompare = mpCollator->compareString(
2667 rValue, rItem.maString.getString());
2668 switch (rEntry.eOp)
2669 {
2670 case SC_LESS :
2671 bOk = (nCompare < 0);
2672 break;
2673 case SC_GREATER :
2674 bOk = (nCompare > 0);
2675 break;
2676 case SC_LESS_EQUAL :
2677 bOk = (nCompare <= 0);
2678 if ( bOk && mpTestEqualCondition && !bTestEqual )
2679 bTestEqual = (nCompare == 0);
2680 break;
2681 case SC_GREATER_EQUAL :
2682 bOk = (nCompare >= 0);
2683 if ( bOk && mpTestEqualCondition && !bTestEqual )
2684 bTestEqual = (nCompare == 0);
2685 break;
2686 default:
2687 {
2688 // added to avoid warnings
2689 }
2690 }
2691 }
2692 }
2693
2694 return std::pair<bool,bool>(bOk, bTestEqual);
2695 }
2696
2697 // To be called only if both isQueryByValue() and isQueryByString()
2698 // returned false and range lookup is wanted! In range lookup comparison
2699 // numbers are less than strings. Nothing else is compared.
2700 std::pair<bool,bool> compareByRangeLookup(
2701 const ScRefCellValue& rCell, SCCOL nCol, SCROW nRow,
2702 const ScQueryEntry& rEntry, const ScQueryEntry::Item& rItem)
2703 {
2704 bool bTestEqual = false;
2705
2706 if (rItem.meType == ScQueryEntry::ByString && rEntry.eOp != SC_LESS && rEntry.eOp != SC_LESS_EQUAL)
2707 return std::pair<bool,bool>(false, bTestEqual);
2708
2709 if (rItem.meType != ScQueryEntry::ByString && rEntry.eOp != SC_GREATER && rEntry.eOp != SC_GREATER_EQUAL)
2710 return std::pair<bool,bool>(false, bTestEqual);
2711
2712 if (!rCell.isEmpty())
2713 {
2714 if (rItem.meType == ScQueryEntry::ByString)
2715 {
2716 if (rCell.meType == CELLTYPE_FORMULA && rCell.mpFormula->GetErrCode() != FormulaError::NONE)
2717 // Error values are compared as string.
2718 return std::pair<bool,bool>(false, bTestEqual);
2719
2720 return std::pair<bool,bool>(rCell.hasNumeric(), bTestEqual);
2721 }
2722
2723 return std::pair<bool,bool>(!rCell.hasNumeric(), bTestEqual);
2724 }
2725
2726 if (rItem.meType == ScQueryEntry::ByString)
2727 return std::pair<bool,bool>(mrTab.HasValueData(nCol, nRow), bTestEqual);
2728
2729 return std::pair<bool,bool>(!mrTab.HasValueData(nCol, nRow), bTestEqual);
2730 }
2731};
2732
2733}
2734
2735bool ScTable::ValidQuery(
2736 SCROW nRow, const ScQueryParam& rParam, const ScRefCellValue* pCell, bool* pbTestEqualCondition,
2737 const ScInterpreterContext* pContext, sc::TableColumnBlockPositionSet* pBlockPos)
2738{
2739 if (!rParam.GetEntry(0).bDoQuery)
4
←
Assuming field 'bDoQuery' is true
→
5
←
Taking false branch
→
2740 return true;
2741
2742 //---------------------------------------------------------------
2743
2744 const SCSIZE nFixedBools = 32;
2745 bool aBool[nFixedBools];
2746 bool aTest[nFixedBools];
2747 SCSIZE nEntryCount = rParam.GetEntryCount();
2748 bool* pPasst = ( nEntryCount <= nFixedBools ? &aBool[0] : new bool[nEntryCount] );
6
←
Assuming 'nEntryCount' is <= 'nFixedBools'
→
7
←
'?' condition is true
→
2749 bool* pTest = ( nEntryCount
7.1
'nEntryCount' is <= 'nFixedBools'
7.1
'nEntryCount' is <= 'nFixedBools'
 <= nFixedBools ? &aTest[0] : new bool[nEntryCount] );
8
←
'?' condition is true
→
2750
2751 long nPos = -1;
2752 QueryEvaluator aEval(rDocument, *this, rParam, pbTestEqualCondition != nullptr);
2753 ScQueryParam::const_iterator it, itBeg = rParam.begin(), itEnd = rParam.end();
2754 for (it = itBeg; it != itEnd && (*it)->bDoQuery; ++it)
9
←
Calling 'operator!=<const std::unique_ptr<ScQueryEntry, std::default_delete<ScQueryEntry>> *, std::vector<std::unique_ptr<ScQueryEntry, std::default_delete<ScQueryEntry>>, std::allocator<std::unique_ptr<ScQueryEntry, std::default_delete<ScQueryEntry>>>>>'
→
12
←
Returning from 'operator!=<const std::unique_ptr<ScQueryEntry, std::default_delete<ScQueryEntry>> *, std::vector<std::unique_ptr<ScQueryEntry, std::default_delete<ScQueryEntry>>, std::allocator<std::unique_ptr<ScQueryEntry, std::default_delete<ScQueryEntry>>>>>'
→
2755 {
2756 const ScQueryEntry& rEntry = **it;
2757 SCCOL nCol = static_cast<SCCOL>(rEntry.nField);
2758
2759 // We can only handle one single direct query passed as a known pCell,
2760 // subsequent queries have to obtain the cell.
2761 ScRefCellValue aCell;
2762 if(pCell && it == itBeg)
2763 aCell = *pCell;
2764 else if( pBlockPos )
2765 { // hinted mdds access
2766 ScColumn* column = FetchColumn(nCol);
2767 aCell = column->GetCellValue(*pBlockPos->getBlockPosition( nCol ), nRow);
2768 }
2769 else
2770 aCell = GetCellValue(nCol, nRow);
2771
2772 std::pair<bool,bool> aRes(false, false);
2773
2774 const ScQueryEntry::QueryItemsType& rItems = rEntry.GetQueryItems();
2775 if (rItems.size() == 1 && rItems.front().meType == ScQueryEntry::ByEmpty)
2776 {
2777 bool hasData;
2778 if( pBlockPos )
2779 {
2780 ScColumn* column = FetchColumn(rEntry.nField);
2781 hasData = column->HasDataAt(*pBlockPos->getBlockPosition(rEntry.nField), nRow);
2782 }
2783 else
2784 hasData = aCol[rEntry.nField].HasDataAt(nRow);
2785 if (rEntry.IsQueryByEmpty())
2786 aRes.first = !hasData;
2787 else
2788 {
2789 assert(rEntry.IsQueryByNonEmpty())(static_cast <bool> (rEntry.IsQueryByNonEmpty()) ? void
(0) : __assert_fail ("rEntry.IsQueryByNonEmpty()", "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 2789, __extension__ __PRETTY_FUNCTION__));
2790 aRes.first = hasData;
2791 }
2792 }
2793 else
2794 {
2795 for (const auto& rItem : rItems)
2796 {
2797 if (aEval.isQueryByValue(rItem, nCol, nRow, aCell))
2798 {
2799 std::pair<bool,bool> aThisRes =
2800 aEval.compareByValue(aCell, nCol, nRow, rEntry, rItem, pContext);
2801 aRes.first |= aThisRes.first;
2802 aRes.second |= aThisRes.second;
2803 }
2804 else if (aEval.isQueryByString(rEntry, rItem, nCol, nRow, aCell))
2805 {
2806 std::pair<bool,bool> aThisRes =
2807 aEval.compareByString(aCell, nRow, rEntry, rItem, pContext);
2808 aRes.first |= aThisRes.first;
2809 aRes.second |= aThisRes.second;
2810 }
2811 else if (rParam.mbRangeLookup)
2812 {
2813 std::pair<bool,bool> aThisRes =
2814 aEval.compareByRangeLookup(aCell, nCol, nRow, rEntry, rItem);
2815 aRes.first |= aThisRes.first;
2816 aRes.second |= aThisRes.second;
2817 }
2818
2819 if (aRes.first && aRes.second)
2820 break;
2821 }
2822 }
2823
2824 if (nPos == -1)
2825 {
2826 nPos++;
2827 pPasst[nPos] = aRes.first;
2828 pTest[nPos] = aRes.second;
2829 }
2830 else
2831 {
2832 if (rEntry.eConnect == SC_AND)
2833 {
2834 pPasst[nPos] = pPasst[nPos] && aRes.first;
2835 pTest[nPos] = pTest[nPos] && aRes.second;
2836 }
2837 else
2838 {
2839 nPos++;
2840 pPasst[nPos] = aRes.first;
2841 pTest[nPos] = aRes.second;
2842 }
2843 }
2844 }
2845
2846 for ( long j=1; j <= nPos; j++ )
13
←
Loop condition is false. Execution continues on line 2852
→
2847 {
2848 pPasst[0] = pPasst[0] || pPasst[j];
2849 pTest[0] = pTest[0] || pTest[j];
2850 }
2851
2852 bool bRet = pPasst[0];
14
←
Assigned value is garbage or undefined
2853 if ( pPasst != &aBool[0] )
2854 delete [] pPasst;
2855 if ( pbTestEqualCondition )
2856 *pbTestEqualCondition = pTest[0];
2857 if ( pTest != &aTest[0] )
2858 delete [] pTest;
2859
2860 return bRet;
2861}
2862
2863void ScTable::TopTenQuery( ScQueryParam& rParam )
2864{
2865 bool bSortCollatorInitialized = false;
2866 SCSIZE nEntryCount = rParam.GetEntryCount();
2867 SCROW nRow1 = (rParam.bHasHeader ? rParam.nRow1 + 1 : rParam.nRow1);
2868 SCSIZE nCount = static_cast<SCSIZE>(rParam.nRow2 - nRow1 + 1);
2869 for ( SCSIZE i=0; (i<nEntryCount) && (rParam.GetEntry(i).bDoQuery); i++ )
2870 {
2871 ScQueryEntry& rEntry = rParam.GetEntry(i);
2872 ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
2873
2874 switch ( rEntry.eOp )
2875 {
2876 case SC_TOPVAL:
2877 case SC_BOTVAL:
2878 case SC_TOPPERC:
2879 case SC_BOTPERC:
2880 {
2881 ScSortParam aLocalSortParam( rParam, static_cast<SCCOL>(rEntry.nField) );
2882 aSortParam = aLocalSortParam; // used in CreateSortInfoArray, Compare
2883 if ( !bSortCollatorInitialized )
2884 {
2885 bSortCollatorInitialized = true;
2886 InitSortCollator( aLocalSortParam );
2887 }
2888 std::unique_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(aSortParam, nRow1, rParam.nRow2, bGlobalKeepQuery, false));
2889 DecoladeRow( pArray.get(), nRow1, rParam.nRow2 );
2890 QuickSort( pArray.get(), nRow1, rParam.nRow2 );
2891 std::unique_ptr<ScSortInfo[]> const & ppInfo = pArray->GetFirstArray();
2892 SCSIZE nValidCount = nCount;
2893 // Don't count note or blank cells, they are sorted to the end
2894 while (nValidCount > 0 && ppInfo[nValidCount-1].maCell.isEmpty())
2895 nValidCount--;
2896 // Don't count Strings, they are between Value and blank
2897 while (nValidCount > 0 && ppInfo[nValidCount-1].maCell.hasString())
2898 nValidCount--;
2899 if ( nValidCount > 0 )
2900 {
2901 if ( rItem.meType == ScQueryEntry::ByString )
2902 { // by string ain't going to work
2903 rItem.meType = ScQueryEntry::ByValue;
2904 rItem.mfVal = 10; // 10 and 10% respectively
2905 }
2906 SCSIZE nVal = (rItem.mfVal >= 1 ? static_cast<SCSIZE>(rItem.mfVal) : 1);
2907 SCSIZE nOffset = 0;
2908 switch ( rEntry.eOp )
2909 {
2910 case SC_TOPVAL:
2911 {
2912 rEntry.eOp = SC_GREATER_EQUAL;
2913 if ( nVal > nValidCount )
2914 nVal = nValidCount;
2915 nOffset = nValidCount - nVal; // 1 <= nVal <= nValidCount
2916 }
2917 break;
2918 case SC_BOTVAL:
2919 {
2920 rEntry.eOp = SC_LESS_EQUAL;
2921 if ( nVal > nValidCount )
2922 nVal = nValidCount;
2923 nOffset = nVal - 1; // 1 <= nVal <= nValidCount
2924 }
2925 break;
2926 case SC_TOPPERC:
2927 {
2928 rEntry.eOp = SC_GREATER_EQUAL;
2929 if ( nVal > 100 )
2930 nVal = 100;
2931 nOffset = nValidCount - (nValidCount * nVal / 100);
2932 if ( nOffset >= nValidCount )
2933 nOffset = nValidCount - 1;
2934 }
2935 break;
2936 case SC_BOTPERC:
2937 {
2938 rEntry.eOp = SC_LESS_EQUAL;
2939 if ( nVal > 100 )
2940 nVal = 100;
2941 nOffset = (nValidCount * nVal / 100);
2942 if ( nOffset >= nValidCount )
2943 nOffset = nValidCount - 1;
2944 }
2945 break;
2946 default:
2947 {
2948 // added to avoid warnings
2949 }
2950 }
2951 ScRefCellValue aCell = ppInfo[nOffset].maCell;
2952 if (aCell.hasNumeric())
2953 rItem.mfVal = aCell.getValue();
2954 else
2955 {
2956 OSL_FAIL( "TopTenQuery: pCell no ValueData" )do { if (true && (((sal_Bool)1))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "2956" ": "), "%s", "TopTenQuery: pCell no ValueData"); }
} while (false);
2957 rEntry.eOp = SC_GREATER_EQUAL;
2958 rItem.mfVal = 0;
2959 }
2960 }
2961 else
2962 {
2963 rEntry.eOp = SC_GREATER_EQUAL;
2964 rItem.meType = ScQueryEntry::ByValue;
2965 rItem.mfVal = 0;
2966 }
2967 }
2968 break;
2969 default:
2970 {
2971 // added to avoid warnings
2972 }
2973 }
2974 }
2975 if ( bSortCollatorInitialized )
2976 DestroySortCollator();
2977}
2978
2979namespace {
2980
2981class PrepareQueryItem
2982{
2983 const ScDocument& mrDoc;
2984public:
2985 explicit PrepareQueryItem(const ScDocument& rDoc) : mrDoc(rDoc) {}
2986
2987 void operator() (ScQueryEntry::Item& rItem)
2988 {
2989 // Double-check if the query by date is really appropriate.
2990
2991 if (rItem.meType != ScQueryEntry::ByDate)
2992 return;
2993
2994 sal_uInt32 nIndex = 0;
2995 bool bNumber = mrDoc.GetFormatTable()->
2996 IsNumberFormat(rItem.maString.getString(), nIndex, rItem.mfVal);
2997
2998 if (bNumber && ((nIndex % SV_COUNTRY_LANGUAGE_OFFSET10000) != 0))
2999 {
3000 const SvNumberformat* pEntry = mrDoc.GetFormatTable()->GetEntry(nIndex);
3001 if (pEntry)
3002 {
3003 SvNumFormatType nNumFmtType = pEntry->GetType();
3004 if (!(nNumFmtType & SvNumFormatType::DATE) || (nNumFmtType & SvNumFormatType::TIME))
3005 rItem.meType = ScQueryEntry::ByValue; // not a date only
3006 }
3007 else
3008 rItem.meType = ScQueryEntry::ByValue; // what the ... not a date
3009 }
3010 else
3011 rItem.meType = ScQueryEntry::ByValue; // not a date
3012 }
3013};
3014
3015void lcl_PrepareQuery( const ScDocument* pDoc, ScTable* pTab, ScQueryParam& rParam )
3016{
3017 bool bTopTen = false;
3018 SCSIZE nEntryCount = rParam.GetEntryCount();
3019
3020 for ( SCSIZE i = 0; i < nEntryCount; ++i )
3021 {
3022 ScQueryEntry& rEntry = rParam.GetEntry(i);
3023 if (!rEntry.bDoQuery)
3024 continue;
3025
3026 ScQueryEntry::QueryItemsType& rItems = rEntry.GetQueryItems();
3027 std::for_each(rItems.begin(), rItems.end(), PrepareQueryItem(*pDoc));
3028
3029 if ( !bTopTen )
3030 {
3031 switch ( rEntry.eOp )
3032 {
3033 case SC_TOPVAL:
3034 case SC_BOTVAL:
3035 case SC_TOPPERC:
3036 case SC_BOTPERC:
3037 {
3038 bTopTen = true;
3039 }
3040 break;
3041 default:
3042 {
3043 }
3044 }
3045 }
3046 }
3047
3048 if ( bTopTen )
3049 {
3050 pTab->TopTenQuery( rParam );
3051 }
3052}
3053
3054}
3055
3056SCSIZE ScTable::Query(const ScQueryParam& rParamOrg, bool bKeepSub)
3057{
3058 ScQueryParam aParam( rParamOrg );
3059 typedef std::unordered_set<OUString> StrSetType;
3060 StrSetType aStrSet;
3061
3062 bool bStarted = false;
3063 bool bOldResult = true;
3064 SCROW nOldStart = 0;
3065 SCROW nOldEnd = 0;
3066
3067 SCSIZE nCount = 0;
3068 SCROW nOutRow = 0;
3069 SCROW nHeader = aParam.bHasHeader ? 1 : 0;
3070
3071 lcl_PrepareQuery(&rDocument, this, aParam);
3072
3073 if (!aParam.bInplace)
3074 {
3075 nOutRow = aParam.nDestRow + nHeader;
3076 if (nHeader > 0)
3077 CopyData( aParam.nCol1, aParam.nRow1, aParam.nCol2, aParam.nRow1,
3078 aParam.nDestCol, aParam.nDestRow, aParam.nDestTab );
3079 }
3080
3081 sc::TableColumnBlockPositionSet blockPos( GetDoc(), nTab ); // cache mdds access
3082
3083 SCROW nRealRow2 = aParam.nRow2;
3084 for (SCROW j = aParam.nRow1 + nHeader; j <= nRealRow2; ++j)
3085 {
3086 bool bResult; // Filter result
3087 bool bValid = ValidQuery(j, aParam, nullptr, nullptr, nullptr, &blockPos);
3088 if (!bValid && bKeepSub) // Keep subtotals
3089 {
3090 for (SCCOL nCol=aParam.nCol1; nCol<=aParam.nCol2 && !bValid; nCol++)
3091 {
3092 ScRefCellValue aCell = GetCellValue(nCol, j);
3093 if (aCell.meType != CELLTYPE_FORMULA)
3094 continue;
3095
3096 if (!aCell.mpFormula->IsSubTotal())
3097 continue;
3098
3099 if (RefVisible(aCell.mpFormula))
3100 bValid = true;
3101 }
3102 }
3103 if (bValid)
3104 {
3105 if (aParam.bDuplicate)
3106 bResult = true;
3107 else
3108 {
3109 OUStringBuffer aStr;
3110 for (SCCOL k=aParam.nCol1; k <= aParam.nCol2; k++)
3111 {
3112 OUString aCellStr;
3113 GetString(k, j, aCellStr);
3114 aStr.append(aCellStr + u"\x0001");
3115 }
3116
3117 bResult = aStrSet.insert(aStr.makeStringAndClear()).second; // unique if inserted.
3118 }
3119 }
3120 else
3121 bResult = false;
3122
3123 if (aParam.bInplace)
3124 {
3125 if (bResult == bOldResult && bStarted)
3126 nOldEnd = j;
3127 else
3128 {
3129 if (bStarted)
3130 DBShowRows(nOldStart,nOldEnd, bOldResult);
3131 nOldStart = nOldEnd = j;
3132 bOldResult = bResult;
3133 }
3134 bStarted = true;
3135 }
3136 else
3137 {
3138 if (bResult)
3139 {
3140 CopyData( aParam.nCol1,j, aParam.nCol2,j, aParam.nDestCol,nOutRow,aParam.nDestTab );
3141 if( nTab == aParam.nDestTab ) // copy to self, changes may invalidate caching position hints
3142 blockPos.invalidate();
3143 ++nOutRow;
3144 }
3145 }
3146 if (bResult)
3147 ++nCount;
3148 }
3149
3150 if (aParam.bInplace && bStarted)
3151 DBShowRows(nOldStart,nOldEnd, bOldResult);
3152
3153 if (aParam.bInplace)
3154 SetDrawPageSize();
3155
3156 return nCount;
3157}
3158
3159bool ScTable::CreateExcelQuery(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, ScQueryParam& rQueryParam)
3160{
3161 bool bValid = true;
3162 std::unique_ptr<SCCOL[]> pFields(new SCCOL[nCol2-nCol1+1]);
3163 OUString aCellStr;
3164 SCCOL nCol = nCol1;
3165 OSL_ENSURE( rQueryParam.nTab != SCTAB_MAX, "rQueryParam.nTab no value, not bad but no good" )do { if (true && (!(rQueryParam.nTab != SCTAB_MAX))) {
sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"
), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "3165" ": "), "%s", "rQueryParam.nTab no value, not bad but no good"
); } } while (false);
3166 SCTAB nDBTab = (rQueryParam.nTab == SCTAB_MAX ? nTab : rQueryParam.nTab);
3167 SCROW nDBRow1 = rQueryParam.nRow1;
3168 SCCOL nDBCol2 = rQueryParam.nCol2;
3169 // First row must be column headers
3170 while (bValid && (nCol <= nCol2))
3171 {
3172 OUString aQueryStr;
3173 GetUpperCellString(nCol, nRow1, aQueryStr);
3174 bool bFound = false;
3175 SCCOL i = rQueryParam.nCol1;
3176 while (!bFound && (i <= nDBCol2))
3177 {
3178 if ( nTab == nDBTab )
3179 GetUpperCellString(i, nDBRow1, aCellStr);
3180 else
3181 rDocument.GetUpperCellString(i, nDBRow1, nDBTab, aCellStr);
3182 bFound = (aCellStr == aQueryStr);
3183 if (!bFound) i++;
3184 }
3185 if (bFound)
3186 pFields[nCol - nCol1] = i;
3187 else
3188 bValid = false;
3189 nCol++;
3190 }
3191 if (bValid)
3192 {
3193 sal_uLong nVisible = 0;
3194 for ( nCol=nCol1; nCol<=nCol2; nCol++ )
3195 nVisible += aCol[nCol].VisibleCount( nRow1+1, nRow2 );
3196
3197 if ( nVisible > SCSIZE_MAX / sizeof(void*) )
3198 {
3199 OSL_FAIL("too many filter criteria")do { if (true && (((sal_Bool)1))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "3199" ": "), "%s", "too many filter criteria"); } } while
(false);
3200 nVisible = 0;
3201 }
3202
3203 SCSIZE nNewEntries = nVisible;
3204 rQueryParam.Resize( nNewEntries );
3205
3206 SCSIZE nIndex = 0;
3207 SCROW nRow = nRow1 + 1;
3208 svl::SharedStringPool& rPool = rDocument.GetSharedStringPool();
3209 while (nRow <= nRow2)
3210 {
3211 nCol = nCol1;
3212 while (nCol <= nCol2)
3213 {
3214 GetInputString( nCol, nRow, aCellStr );
3215 if (!aCellStr.isEmpty())
3216 {
3217 if (nIndex < nNewEntries)
3218 {
3219 rQueryParam.GetEntry(nIndex).nField = pFields[nCol - nCol1];
3220 rQueryParam.FillInExcelSyntax(rPool, aCellStr, nIndex, nullptr);
3221 nIndex++;
3222 if (nIndex < nNewEntries)
3223 rQueryParam.GetEntry(nIndex).eConnect = SC_AND;
3224 }
3225 else
3226 bValid = false;
3227 }
3228 nCol++;
3229 }
3230 nRow++;
3231 if (nIndex < nNewEntries)
3232 rQueryParam.GetEntry(nIndex).eConnect = SC_OR;
3233 }
3234 }
3235 return bValid;
3236}
3237
3238bool ScTable::CreateStarQuery(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, ScQueryParam& rQueryParam)
3239{
3240 // A valid StarQuery must be at least 4 columns wide. To be precise it
3241 // should be exactly 4 columns ...
3242 // Additionally, if this wasn't checked, a formula pointing to a valid 1-3
3243 // column Excel style query range immediately left to itself would result
3244 // in a circular reference when the field name or operator or value (first
3245 // to third query range column) is obtained (#i58354#). Furthermore, if the
3246 // range wasn't sufficiently specified data changes wouldn't flag formula
3247 // cells for recalculation.
3248 if (nCol2 - nCol1 < 3)
3249 return false;
3250
3251 bool bValid;
3252 OUString aCellStr;
3253 SCSIZE nIndex = 0;
3254 SCROW nRow = nRow1;
3255 OSL_ENSURE( rQueryParam.nTab != SCTAB_MAX, "rQueryParam.nTab no value, not bad but no good" )do { if (true && (!(rQueryParam.nTab != SCTAB_MAX))) {
sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"
), ("/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
":" "3255" ": "), "%s", "rQueryParam.nTab no value, not bad but no good"
); } } while (false);
3256 SCTAB nDBTab = (rQueryParam.nTab == SCTAB_MAX ? nTab : rQueryParam.nTab);
3257 SCROW nDBRow1 = rQueryParam.nRow1;
3258 SCCOL nDBCol2 = rQueryParam.nCol2;
3259
3260 SCSIZE nNewEntries = static_cast<SCSIZE>(nRow2-nRow1+1);
3261 rQueryParam.Resize( nNewEntries );
3262 svl::SharedStringPool& rPool = rDocument.GetSharedStringPool();
3263
3264 do
3265 {
3266 ScQueryEntry& rEntry = rQueryParam.GetEntry(nIndex);
3267
3268 bValid = false;
3269 // First column AND/OR
3270 if (nIndex > 0)
3271 {
3272 GetUpperCellString(nCol1, nRow, aCellStr);
3273 if ( aCellStr == ScResId(STR_TABLE_ANDreinterpret_cast<char const *>("STR_TABLE_AND" "\004" u8"AND"
)) )
3274 {
3275 rEntry.eConnect = SC_AND;
3276 bValid = true;
3277 }
3278 else if ( aCellStr == ScResId(STR_TABLE_ORreinterpret_cast<char const *>("STR_TABLE_OR" "\004" u8"OR"
)) )
3279 {
3280 rEntry.eConnect = SC_OR;
3281 bValid = true;
3282 }
3283 }
3284 // Second column field name
3285 if ((nIndex < 1) || bValid)
3286 {
3287 bool bFound = false;
3288 GetUpperCellString(nCol1 + 1, nRow, aCellStr);
3289 for (SCCOL i=rQueryParam.nCol1; (i <= nDBCol2) && (!bFound); i++)
3290 {
3291 OUString aFieldStr;
3292 if ( nTab == nDBTab )
3293 GetUpperCellString(i, nDBRow1, aFieldStr);
3294 else
3295 rDocument.GetUpperCellString(i, nDBRow1, nDBTab, aFieldStr);
3296 bFound = (aCellStr == aFieldStr);
3297 if (bFound)
3298 {
3299 rEntry.nField = i;
3300 bValid = true;
3301 }
3302 else
3303 bValid = false;
3304 }
3305 }
3306 // Third column operator =<>...
3307 if (bValid)
3308 {
3309 GetUpperCellString(nCol1 + 2, nRow, aCellStr);
3310 if (aCellStr.startsWith("<"))
3311 {
3312 if (aCellStr[1] == '>')
3313 rEntry.eOp = SC_NOT_EQUAL;
3314 else if (aCellStr[1] == '=')
3315 rEntry.eOp = SC_LESS_EQUAL;
3316 else
3317 rEntry.eOp = SC_LESS;
3318 }
3319 else if (aCellStr.startsWith(">"))
3320 {
3321 if (aCellStr[1] == '=')
3322 rEntry.eOp = SC_GREATER_EQUAL;
3323 else
3324 rEntry.eOp = SC_GREATER;
3325 }
3326 else if (aCellStr.startsWith("="))
3327 rEntry.eOp = SC_EQUAL;
3328
3329 }
3330 // Fourth column values
3331 if (bValid)
3332 {
3333 OUString aStr;
3334 GetString(nCol1 + 3, nRow, aStr);
3335 rEntry.GetQueryItem().maString = rPool.intern(aStr);
3336 rEntry.bDoQuery = true;
3337 }
3338 nIndex++;
3339 nRow++;
3340 }
3341 while (bValid && (nRow <= nRow2) /* && (nIndex < MAXQUERY) */ );
3342 return bValid;
3343}
3344
3345bool ScTable::CreateQueryParam(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, ScQueryParam& rQueryParam)
3346{
3347 SCSIZE i, nCount;
3348 PutInOrder(nCol1, nCol2);
3349 PutInOrder(nRow1, nRow2);
3350
3351 nCount = rQueryParam.GetEntryCount();
3352 for (i=0; i < nCount; i++)
3353 rQueryParam.GetEntry(i).Clear();
3354
3355 // Standard query table
3356 bool bValid = CreateStarQuery(nCol1, nRow1, nCol2, nRow2, rQueryParam);
3357 // Excel Query table
3358 if (!bValid)
3359 bValid = CreateExcelQuery(nCol1, nRow1, nCol2, nRow2, rQueryParam);
3360
3361 SvNumberFormatter* pFormatter = rDocument.GetFormatTable();
3362 nCount = rQueryParam.GetEntryCount();
3363
3364 if (bValid)
3365 {
3366 // bQueryByString must be set
3367 for (i=0; i < nCount; i++)
3368 {
3369 ScQueryEntry::Item& rItem = rQueryParam.GetEntry(i).GetQueryItem();
3370
3371 sal_uInt32 nIndex = 0;
3372 bool bNumber = pFormatter->IsNumberFormat(
3373 rItem.maString.getString(), nIndex, rItem.mfVal);
3374
3375 rItem.meType = bNumber ? ScQueryEntry::ByValue : ScQueryEntry::ByString;
3376 }
3377 }
3378 else
3379 {
3380 for (i=0; i < nCount; i++)
3381 rQueryParam.GetEntry(i).Clear();
3382 }
3383 return bValid;
3384}
3385
3386bool ScTable::HasColHeader( SCCOL nStartCol, SCROW nStartRow, SCCOL nEndCol, SCROW nEndRow) const
3387{
3388 if (nStartRow == nEndRow)
3389 // Assume only data.
3390 /* XXX NOTE: previous behavior still checked this one row and could
3391 * evaluate it has header row, but that doesn't make much sense. */
3392 return false;
3393
3394 if (nStartCol == nEndCol)
3395 {
3396 CellType eFirstCellType = GetCellType(nStartCol, nStartRow);
3397 CellType eSecondCellType = GetCellType(nStartCol, nStartRow+1);
3398 return ((eFirstCellType == CELLTYPE_STRING || eFirstCellType == CELLTYPE_EDIT) &&
3399 (eSecondCellType != CELLTYPE_STRING && eSecondCellType != CELLTYPE_EDIT));
3400 }
3401
3402 for (SCCOL nCol=nStartCol; nCol<=nEndCol; nCol++)
3403 {
3404 CellType eType = GetCellType( nCol, nStartRow );
3405 // Any non-text cell in first row => not headers.
3406 if (eType != CELLTYPE_STRING && eType != CELLTYPE_EDIT)
3407 return false;
3408 }
3409
3410 // First row all text cells, any non-text cell in second row => headers.
3411 SCROW nTestRow = nStartRow + 1;
3412 for (SCCOL nCol=nStartCol; nCol<=nEndCol; nCol++)
3413 {
3414 CellType eType = GetCellType( nCol, nTestRow );
3415 if (eType != CELLTYPE_STRING && eType != CELLTYPE_EDIT)
3416 return true;
3417 }
3418
3419 // Also second row all text cells => first row not headers.
3420 return false;
3421}
3422
3423bool ScTable::HasRowHeader( SCCOL nStartCol, SCROW nStartRow, SCCOL nEndCol, SCROW nEndRow ) const
3424{
3425 if (nStartCol == nEndCol)
3426 // Assume only data.
3427 /* XXX NOTE: previous behavior still checked this one column and could
3428 * evaluate it has header column, but that doesn't make much sense. */
3429 return false;
3430
3431 if (nStartRow == nEndRow)
3432 {
3433 CellType eFirstCellType = GetCellType(nStartCol, nStartRow);
3434 CellType eSecondCellType = GetCellType(nStartCol+1, nStartRow);
3435 return ((eFirstCellType == CELLTYPE_STRING || eFirstCellType == CELLTYPE_EDIT) &&
3436 (eSecondCellType != CELLTYPE_STRING && eSecondCellType != CELLTYPE_EDIT));
3437 }
3438
3439 for (SCROW nRow=nStartRow; nRow<=nEndRow; nRow++)
3440 {
3441 CellType eType = GetCellType( nStartCol, nRow );
3442 // Any non-text cell in first column => not headers.
3443 if (eType != CELLTYPE_STRING && eType != CELLTYPE_EDIT)
3444 return false;
3445 }
3446
3447 // First column all text cells, any non-text cell in second column => headers.
3448 SCCOL nTestCol = nStartCol + 1;
3449 for (SCROW nRow=nStartRow; nRow<=nEndRow; nRow++)
3450 {
3451 CellType eType = GetCellType( nRow, nTestCol );
3452 if (eType != CELLTYPE_STRING && eType != CELLTYPE_EDIT)
3453 return true;
3454 }
3455
3456 // Also second column all text cells => first column not headers.
3457 return false;
3458}
3459
3460void ScTable::GetFilterEntries( SCCOL nCol, SCROW nRow1, SCROW nRow2, ScFilterEntries& rFilterEntries )
3461{
3462 sc::ColumnBlockConstPosition aBlockPos;
3463 aCol[nCol].InitBlockPosition(aBlockPos);
3464 aCol[nCol].GetFilterEntries(aBlockPos, nRow1, nRow2, rFilterEntries);
3465}
3466
3467void ScTable::GetFilteredFilterEntries(
3468 SCCOL nCol, SCROW nRow1, SCROW nRow2, const ScQueryParam& rParam, ScFilterEntries& rFilterEntries )
3469{
3470 sc::ColumnBlockConstPosition aBlockPos;
3471 aCol[nCol].InitBlockPosition(aBlockPos);
3472
3473 // remove the entry for this column from the query parameter
3474 ScQueryParam aParam( rParam );
3475 aParam.RemoveEntryByField(nCol);
3476
3477 lcl_PrepareQuery(&rDocument, this, aParam);
3478 for ( SCROW j = nRow1; j <= nRow2; ++j )
1
Assuming 'j' is <= 'nRow2'
→
2
←
Loop condition is true. Entering loop body
→
3479 {
3480 if (ValidQuery(j, aParam))
3
←
Calling 'ScTable::ValidQuery'
→
3481 {
3482 aCol[nCol].GetFilterEntries(aBlockPos, j, j, rFilterEntries);
3483 }
3484 }
3485}
3486
3487bool ScTable::GetDataEntries(SCCOL nCol, SCROW nRow, std::set<ScTypedStrData>& rStrings, bool bLimit)
3488{
3489 return aCol[nCol].GetDataEntries( nRow, rStrings, bLimit );
3490}
3491
3492sal_uLong ScTable::GetCellCount() const
3493{
3494 sal_uLong nCellCount = 0;
3495
3496 for ( SCCOL nCol=0; nCol < aCol.size(); nCol++ )
3497 nCellCount += aCol[nCol].GetCellCount();
3498
3499 return nCellCount;
3500}
3501
3502sal_uLong ScTable::GetWeightedCount() const
3503{
3504 sal_uLong nCellCount = 0;
3505
3506 for ( SCCOL nCol=0; nCol < aCol.size(); nCol++ )
3507 nCellCount += aCol[nCol].GetWeightedCount();
3508
3509 return nCellCount;
3510}
3511
3512sal_uLong ScTable::GetWeightedCount(SCROW nStartRow, SCROW nEndRow) const
3513{
3514 sal_uLong nCellCount = 0;
3515
3516 for ( SCCOL nCol=0; nCol < aCol.size(); nCol++ )
3517 nCellCount += aCol[nCol].GetWeightedCount(nStartRow, nEndRow);
3518
3519 return nCellCount;
3520}
3521
3522sal_uLong ScTable::GetCodeCount() const
3523{
3524 sal_uLong nCodeCount = 0;
3525
3526 for ( SCCOL nCol=0; nCol < aCol.size(); nCol++ )
3527 if ( aCol[nCol].GetCellCount() )
3528 nCodeCount += aCol[nCol].GetCodeCount();
3529
3530 return nCodeCount;
3531}
3532
3533sal_Int32 ScTable::GetMaxStringLen( SCCOL nCol, SCROW nRowStart,
3534 SCROW nRowEnd, rtl_TextEncoding eCharSet ) const
3535{
3536 if ( IsColValid( nCol ) )
3537 return aCol[nCol].GetMaxStringLen( nRowStart, nRowEnd, eCharSet );
3538 else
3539 return 0;
3540}
3541
3542sal_Int32 ScTable::GetMaxNumberStringLen(
3543 sal_uInt16& nPrecision, SCCOL nCol, SCROW nRowStart, SCROW nRowEnd ) const
3544{
3545 if ( IsColValid( nCol ) )
3546 return aCol[nCol].GetMaxNumberStringLen( nPrecision, nRowStart, nRowEnd );
3547 else
3548 return 0;
3549}
3550
3551void ScTable::UpdateSelectionFunction( ScFunctionData& rData, const ScMarkData& rMark )
3552{
3553 ScRangeList aRanges = rMark.GetMarkedRangesForTab( nTab );
3554 ScRange aMarkArea( ScAddress::UNINITIALIZED );
3555 if (rMark.IsMultiMarked())
3556 rMark.GetMultiMarkArea( aMarkArea );
3557 else if (rMark.IsMarked())
3558 rMark.GetMarkArea( aMarkArea );
3559 else
3560 {
3561 assert(!"ScTable::UpdateSelectionFunction - called without anything marked")(static_cast <bool> (!"ScTable::UpdateSelectionFunction - called without anything marked"
) ? void (0) : __assert_fail ("!\"ScTable::UpdateSelectionFunction - called without anything marked\""
, "/home/maarten/src/libreoffice/core/sc/source/core/data/table3.cxx"
, 3561, __extension__ __PRETTY_FUNCTION__));
3562 aMarkArea.aStart.SetCol(0);
3563 aMarkArea.aEnd.SetCol(rDocument.MaxCol());
3564 }
3565 const SCCOL nStartCol = aMarkArea.aStart.Col();
3566 const SCCOL nEndCol = ClampToAllocatedColumns(aMarkArea.aEnd.Col());
3567 for (SCCOL nCol = nStartCol; nCol <= nEndCol && !rData.getError(); ++nCol)
3568 {
3569 if (mpColFlags && ColHidden(nCol))
3570 continue;
3571
3572 aCol[nCol].UpdateSelectionFunction(aRanges, rData, *mpHiddenRows);
3573 }
3574}
3575
3576/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
←

/usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/bits/stl_iterator.h

1// Iterators -*- C++ -*-
2
3// Copyright (C) 2001-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996-1998
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_iterator.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{iterator}
54 *
55 * This file implements reverse_iterator, back_insert_iterator,
56 * front_insert_iterator, insert_iterator, __normal_iterator, and their
57 * supporting functions and overloaded operators.
58 */
59
60#ifndef _STL_ITERATOR_H1
61#define _STL_ITERATOR_H1 1
62
63#include <bits/cpp_type_traits.h>
64#include <ext/type_traits.h>
65#include <bits/move.h>
66#include <bits/ptr_traits.h>
67
68#if __cplusplus201703L >= 201103L
69# include <type_traits>
70#endif
71
72#if __cplusplus201703L > 201703L
73# define __cpp_lib_array_constexpr201803L 201811L
74# define __cpp_lib_constexpr_iterator 201811L
75#elif __cplusplus201703L == 201703L
76# define __cpp_lib_array_constexpr201803L 201803L
77#endif
78
79#if __cplusplus201703L > 201703L
80# include <compare>
81# include <new>
82# include <bits/iterator_concepts.h>
83#endif
84
85namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
86{
87_GLIBCXX_BEGIN_NAMESPACE_VERSION
88
89 /**
90 * @addtogroup iterators
91 * @{
92 */
93
94#if __cplusplus201703L > 201703L && __cpp_lib_concepts
95 namespace __detail
96 {
97 // Weaken iterator_category _Cat to _Limit if it is derived from that,
98 // otherwise use _Otherwise.
99 template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
100 using __clamp_iter_cat
101 = conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
102 }
103#endif
104
105 // 24.4.1 Reverse iterators
106 /**
107 * Bidirectional and random access iterators have corresponding reverse
108 * %iterator adaptors that iterate through the data structure in the
109 * opposite direction. They have the same signatures as the corresponding
110 * iterators. The fundamental relation between a reverse %iterator and its
111 * corresponding %iterator @c i is established by the identity:
112 * @code
113 * &*(reverse_iterator(i)) == &*(i - 1)
114 * @endcode
115 *
116 * <em>This mapping is dictated by the fact that while there is always a
117 * pointer past the end of an array, there might not be a valid pointer
118 * before the beginning of an array.</em> [24.4.1]/1,2
119 *
120 * Reverse iterators can be tricky and surprising at first. Their
121 * semantics make sense, however, and the trickiness is a side effect of
122 * the requirement that the iterators must be safe.
123 */
124 template<typename _Iterator>
125 class reverse_iterator
126 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
127 typename iterator_traits<_Iterator>::value_type,
128 typename iterator_traits<_Iterator>::difference_type,
129 typename iterator_traits<_Iterator>::pointer,
130 typename iterator_traits<_Iterator>::reference>
131 {
132 protected:
133 _Iterator current;
134
135 typedef iterator_traits<_Iterator> __traits_type;
136
137 public:
138 typedef _Iterator iterator_type;
139 typedef typename __traits_type::difference_type difference_type;
140 typedef typename __traits_type::pointer pointer;
141 typedef typename __traits_type::reference reference;
142
143#if __cplusplus201703L > 201703L && __cpp_lib_concepts
144 using iterator_concept
145 = conditional_t<random_access_iterator<_Iterator>,
146 random_access_iterator_tag,
147 bidirectional_iterator_tag>;
148 using iterator_category
149 = __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
150 random_access_iterator_tag>;
151#endif
152
153 /**
154 * The default constructor value-initializes member @p current.
155 * If it is a pointer, that means it is zero-initialized.
156 */
157 // _GLIBCXX_RESOLVE_LIB_DEFECTS
158 // 235 No specification of default ctor for reverse_iterator
159 // 1012. reverse_iterator default ctor should value initialize
160 _GLIBCXX17_CONSTEXPRconstexpr
161 reverse_iterator() : current() { }
162
163 /**
164 * This %iterator will move in the opposite direction that @p x does.
165 */
166 explicit _GLIBCXX17_CONSTEXPRconstexpr
167 reverse_iterator(iterator_type __x) : current(__x) { }
168
169 /**
170 * The copy constructor is normal.
171 */
172 _GLIBCXX17_CONSTEXPRconstexpr
173 reverse_iterator(const reverse_iterator& __x)
174 : current(__x.current) { }
175
176#if __cplusplus201703L >= 201103L
177 reverse_iterator& operator=(const reverse_iterator&) = default;
178#endif
179
180 /**
181 * A %reverse_iterator across other types can be copied if the
182 * underlying %iterator can be converted to the type of @c current.
183 */
184 template<typename _Iter>
185 _GLIBCXX17_CONSTEXPRconstexpr
186 reverse_iterator(const reverse_iterator<_Iter>& __x)
187 : current(__x.base()) { }
188
189 /**
190 * @return @c current, the %iterator used for underlying work.
191 */
192 _GLIBCXX17_CONSTEXPRconstexpr iterator_type
193 base() const
194 { return current; }
195
196 /**
197 * @return A reference to the value at @c --current
198 *
199 * This requires that @c --current is dereferenceable.
200 *
201 * @warning This implementation requires that for an iterator of the
202 * underlying iterator type, @c x, a reference obtained by
203 * @c *x remains valid after @c x has been modified or
204 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
205 */
206 _GLIBCXX17_CONSTEXPRconstexpr reference
207 operator*() const
208 {
209 _Iterator __tmp = current;
210 return *--__tmp;
211 }
212
213 /**
214 * @return A pointer to the value at @c --current
215 *
216 * This requires that @c --current is dereferenceable.
217 */
218 _GLIBCXX17_CONSTEXPRconstexpr pointer
219 operator->() const
220#if __cplusplus201703L > 201703L && __cpp_concepts >= 201907L
221 requires is_pointer_v<_Iterator>
222 || requires(const _Iterator __i) { __i.operator->(); }
223#endif
224 {
225 // _GLIBCXX_RESOLVE_LIB_DEFECTS
226 // 1052. operator-> should also support smart pointers
227 _Iterator __tmp = current;
228 --__tmp;
229 return _S_to_pointer(__tmp);
230 }
231
232 /**
233 * @return @c *this
234 *
235 * Decrements the underlying iterator.
236 */
237 _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator&
238 operator++()
239 {
240 --current;
241 return *this;
242 }
243
244 /**
245 * @return The original value of @c *this
246 *
247 * Decrements the underlying iterator.
248 */
249 _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator
250 operator++(int)
251 {
252 reverse_iterator __tmp = *this;
253 --current;
254 return __tmp;
255 }
256
257 /**
258 * @return @c *this
259 *
260 * Increments the underlying iterator.
261 */
262 _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator&
263 operator--()
264 {
265 ++current;
266 return *this;
267 }
268
269 /**
270 * @return A reverse_iterator with the previous value of @c *this
271 *
272 * Increments the underlying iterator.
273 */
274 _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator
275 operator--(int)
276 {
277 reverse_iterator __tmp = *this;
278 ++current;
279 return __tmp;
280 }
281
282 /**
283 * @return A reverse_iterator that refers to @c current - @a __n
284 *
285 * The underlying iterator must be a Random Access Iterator.
286 */
287 _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator
288 operator+(difference_type __n) const
289 { return reverse_iterator(current - __n); }
290
291 /**
292 * @return *this
293 *
294 * Moves the underlying iterator backwards @a __n steps.
295 * The underlying iterator must be a Random Access Iterator.
296 */
297 _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator&
298 operator+=(difference_type __n)
299 {
300 current -= __n;
301 return *this;
302 }
303
304 /**
305 * @return A reverse_iterator that refers to @c current - @a __n
306 *
307 * The underlying iterator must be a Random Access Iterator.
308 */
309 _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator
310 operator-(difference_type __n) const
311 { return reverse_iterator(current + __n); }
312
313 /**
314 * @return *this
315 *
316 * Moves the underlying iterator forwards @a __n steps.
317 * The underlying iterator must be a Random Access Iterator.
318 */
319 _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator&
320 operator-=(difference_type __n)
321 {
322 current += __n;
323 return *this;
324 }
325
326 /**
327 * @return The value at @c current - @a __n - 1
328 *
329 * The underlying iterator must be a Random Access Iterator.
330 */
331 _GLIBCXX17_CONSTEXPRconstexpr reference
332 operator[](difference_type __n) const
333 { return *(*this + __n); }
334
335 private:
336 template<typename _Tp>
337 static _GLIBCXX17_CONSTEXPRconstexpr _Tp*
338 _S_to_pointer(_Tp* __p)
339 { return __p; }
340
341 template<typename _Tp>
342 static _GLIBCXX17_CONSTEXPRconstexpr pointer
343 _S_to_pointer(_Tp __t)
344 { return __t.operator->(); }
345 };
346
347 //@{
348 /**
349 * @param __x A %reverse_iterator.
350 * @param __y A %reverse_iterator.
351 * @return A simple bool.
352 *
353 * Reverse iterators forward comparisons to their underlying base()
354 * iterators.
355 *
356 */
357#if __cplusplus201703L <= 201703L || ! defined __cpp_lib_concepts
358 template<typename _Iterator>
359 inline _GLIBCXX17_CONSTEXPRconstexpr bool
360 operator==(const reverse_iterator<_Iterator>& __x,
361 const reverse_iterator<_Iterator>& __y)
362 { return __x.base() == __y.base(); }
363
364 template<typename _Iterator>
365 inline _GLIBCXX17_CONSTEXPRconstexpr bool
366 operator<(const reverse_iterator<_Iterator>& __x,
367 const reverse_iterator<_Iterator>& __y)
368 { return __y.base() < __x.base(); }
369
370 template<typename _Iterator>
371 inline _GLIBCXX17_CONSTEXPRconstexpr bool
372 operator!=(const reverse_iterator<_Iterator>& __x,
373 const reverse_iterator<_Iterator>& __y)
374 { return !(__x == __y); }
375
376 template<typename _Iterator>
377 inline _GLIBCXX17_CONSTEXPRconstexpr bool
378 operator>(const reverse_iterator<_Iterator>& __x,
379 const reverse_iterator<_Iterator>& __y)
380 { return __y < __x; }
381
382 template<typename _Iterator>
383 inline _GLIBCXX17_CONSTEXPRconstexpr bool
384 operator<=(const reverse_iterator<_Iterator>& __x,
385 const reverse_iterator<_Iterator>& __y)
386 { return !(__y < __x); }
387
388 template<typename _Iterator>
389 inline _GLIBCXX17_CONSTEXPRconstexpr bool
390 operator>=(const reverse_iterator<_Iterator>& __x,
391 const reverse_iterator<_Iterator>& __y)
392 { return !(__x < __y); }
393
394 // _GLIBCXX_RESOLVE_LIB_DEFECTS
395 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
396 template<typename _IteratorL, typename _IteratorR>
397 inline _GLIBCXX17_CONSTEXPRconstexpr bool
398 operator==(const reverse_iterator<_IteratorL>& __x,
399 const reverse_iterator<_IteratorR>& __y)
400 { return __x.base() == __y.base(); }
401
402 template<typename _IteratorL, typename _IteratorR>
403 inline _GLIBCXX17_CONSTEXPRconstexpr bool
404 operator<(const reverse_iterator<_IteratorL>& __x,
405 const reverse_iterator<_IteratorR>& __y)
406 { return __y.base() < __x.base(); }
407
408 template<typename _IteratorL, typename _IteratorR>
409 inline _GLIBCXX17_CONSTEXPRconstexpr bool
410 operator!=(const reverse_iterator<_IteratorL>& __x,
411 const reverse_iterator<_IteratorR>& __y)
412 { return !(__x == __y); }
413
414 template<typename _IteratorL, typename _IteratorR>
415 inline _GLIBCXX17_CONSTEXPRconstexpr bool
416 operator>(const reverse_iterator<_IteratorL>& __x,
417 const reverse_iterator<_IteratorR>& __y)
418 { return __y < __x; }
419
420 template<typename _IteratorL, typename _IteratorR>
421 inline _GLIBCXX17_CONSTEXPRconstexpr bool
422 operator<=(const reverse_iterator<_IteratorL>& __x,
423 const reverse_iterator<_IteratorR>& __y)
424 { return !(__y < __x); }
425
426 template<typename _IteratorL, typename _IteratorR>
427 inline _GLIBCXX17_CONSTEXPRconstexpr bool
428 operator>=(const reverse_iterator<_IteratorL>& __x,
429 const reverse_iterator<_IteratorR>& __y)
430 { return !(__x < __y); }
431#else // C++20
432 template<typename _IteratorL, typename _IteratorR>
433 constexpr bool
434 operator==(const reverse_iterator<_IteratorL>& __x,
435 const reverse_iterator<_IteratorR>& __y)
436 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
437 { return __x.base() == __y.base(); }
438
439 template<typename _IteratorL, typename _IteratorR>
440 constexpr bool
441 operator!=(const reverse_iterator<_IteratorL>& __x,
442 const reverse_iterator<_IteratorR>& __y)
443 requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
444 { return __x.base() != __y.base(); }
445
446 template<typename _IteratorL, typename _IteratorR>
447 constexpr bool
448 operator<(const reverse_iterator<_IteratorL>& __x,
449 const reverse_iterator<_IteratorR>& __y)
450 requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
451 { return __x.base() > __y.base(); }
452
453 template<typename _IteratorL, typename _IteratorR>
454 constexpr bool
455 operator>(const reverse_iterator<_IteratorL>& __x,
456 const reverse_iterator<_IteratorR>& __y)
457 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
458 { return __x.base() < __y.base(); }
459
460 template<typename _IteratorL, typename _IteratorR>
461 constexpr bool
462 operator<=(const reverse_iterator<_IteratorL>& __x,
463 const reverse_iterator<_IteratorR>& __y)
464 requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
465 { return __x.base() >= __y.base(); }
466
467 template<typename _IteratorL, typename _IteratorR>
468 constexpr bool
469 operator>=(const reverse_iterator<_IteratorL>& __x,
470 const reverse_iterator<_IteratorR>& __y)
471 requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
472 { return __x.base() <= __y.base(); }
473
474 template<typename _IteratorL,
475 three_way_comparable_with<_IteratorL> _IteratorR>
476 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
477 operator<=>(const reverse_iterator<_IteratorL>& __x,
478 const reverse_iterator<_IteratorR>& __y)
479 { return __y.base() <=> __x.base(); }
480#endif // C++20
481 //@}
482
483#if __cplusplus201703L < 201103L
484 template<typename _Iterator>
485 inline typename reverse_iterator<_Iterator>::difference_type
486 operator-(const reverse_iterator<_Iterator>& __x,
487 const reverse_iterator<_Iterator>& __y)
488 { return __y.base() - __x.base(); }
489
490 template<typename _IteratorL, typename _IteratorR>
491 inline typename reverse_iterator<_IteratorL>::difference_type
492 operator-(const reverse_iterator<_IteratorL>& __x,
493 const reverse_iterator<_IteratorR>& __y)
494 { return __y.base() - __x.base(); }
495#else
496 // _GLIBCXX_RESOLVE_LIB_DEFECTS
497 // DR 685. reverse_iterator/move_iterator difference has invalid signatures
498 template<typename _IteratorL, typename _IteratorR>
499 inline _GLIBCXX17_CONSTEXPRconstexpr auto
500 operator-(const reverse_iterator<_IteratorL>& __x,
501 const reverse_iterator<_IteratorR>& __y)
502 -> decltype(__y.base() - __x.base())
503 { return __y.base() - __x.base(); }
504#endif
505
506 template<typename _Iterator>
507 inline _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator<_Iterator>
508 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
509 const reverse_iterator<_Iterator>& __x)
510 { return reverse_iterator<_Iterator>(__x.base() - __n); }
511
512#if __cplusplus201703L >= 201103L
513 // Same as C++14 make_reverse_iterator but used in C++11 mode too.
514 template<typename _Iterator>
515 inline _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator<_Iterator>
516 __make_reverse_iterator(_Iterator __i)
517 { return reverse_iterator<_Iterator>(__i); }
518
519# if __cplusplus201703L >= 201402L
520# define __cpp_lib_make_reverse_iterator201402 201402
521
522 // _GLIBCXX_RESOLVE_LIB_DEFECTS
523 // DR 2285. make_reverse_iterator
524 /// Generator function for reverse_iterator.
525 template<typename _Iterator>
526 inline _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator<_Iterator>
527 make_reverse_iterator(_Iterator __i)
528 { return reverse_iterator<_Iterator>(__i); }
529
530# if __cplusplus201703L > 201703L && defined __cpp_lib_concepts
531 template<typename _Iterator1, typename _Iterator2>
532 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
533 inline constexpr bool
534 disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
535 reverse_iterator<_Iterator2>> = true;
536# endif // C++20
537# endif // C++14
538
539 template<typename _Iterator>
540 _GLIBCXX20_CONSTEXPR
541 auto
542 __niter_base(reverse_iterator<_Iterator> __it)
543 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
544 { return __make_reverse_iterator(__niter_base(__it.base())); }
545
546 template<typename _Iterator>
547 struct __is_move_iterator<reverse_iterator<_Iterator> >
548 : __is_move_iterator<_Iterator>
549 { };
550
551 template<typename _Iterator>
552 _GLIBCXX20_CONSTEXPR
553 auto
554 __miter_base(reverse_iterator<_Iterator> __it)
555 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
556 { return __make_reverse_iterator(__miter_base(__it.base())); }
557#endif // C++11
558
559 // 24.4.2.2.1 back_insert_iterator
560 /**
561 * @brief Turns assignment into insertion.
562 *
563 * These are output iterators, constructed from a container-of-T.
564 * Assigning a T to the iterator appends it to the container using
565 * push_back.
566 *
567 * Tip: Using the back_inserter function to create these iterators can
568 * save typing.
569 */
570 template<typename _Container>
571 class back_insert_iterator
572 : public iterator<output_iterator_tag, void, void, void, void>
573 {
574 protected:
575 _Container* container;
576
577 public:
578 /// A nested typedef for the type of whatever container you used.
579 typedef _Container container_type;
580#if __cplusplus201703L > 201703L
581 using difference_type = ptrdiff_t;
582
583 constexpr back_insert_iterator() noexcept : container(nullptr) { }
584#endif
585
586 /// The only way to create this %iterator is with a container.
587 explicit _GLIBCXX20_CONSTEXPR
588 back_insert_iterator(_Container& __x)
589 : container(std::__addressof(__x)) { }
590
591 /**
592 * @param __value An instance of whatever type
593 * container_type::const_reference is; presumably a
594 * reference-to-const T for container<T>.
595 * @return This %iterator, for chained operations.
596 *
597 * This kind of %iterator doesn't really have a @a position in the
598 * container (you can think of the position as being permanently at
599 * the end, if you like). Assigning a value to the %iterator will
600 * always append the value to the end of the container.
601 */
602#if __cplusplus201703L < 201103L
603 back_insert_iterator&
604 operator=(typename _Container::const_reference __value)
605 {
606 container->push_back(__value);
607 return *this;
608 }
609#else
610 _GLIBCXX20_CONSTEXPR
611 back_insert_iterator&
612 operator=(const typename _Container::value_type& __value)
613 {
614 container->push_back(__value);
615 return *this;
616 }
617
618 _GLIBCXX20_CONSTEXPR
619 back_insert_iterator&
620 operator=(typename _Container::value_type&& __value)
621 {
622 container->push_back(std::move(__value));
623 return *this;
624 }
625#endif
626
627 /// Simply returns *this.
628 _GLIBCXX20_CONSTEXPR
629 back_insert_iterator&
630 operator*()
631 { return *this; }
632
633 /// Simply returns *this. (This %iterator does not @a move.)
634 _GLIBCXX20_CONSTEXPR
635 back_insert_iterator&
636 operator++()
637 { return *this; }
638
639 /// Simply returns *this. (This %iterator does not @a move.)
640 _GLIBCXX20_CONSTEXPR
641 back_insert_iterator
642 operator++(int)
643 { return *this; }
644 };
645
646 /**
647 * @param __x A container of arbitrary type.
648 * @return An instance of back_insert_iterator working on @p __x.
649 *
650 * This wrapper function helps in creating back_insert_iterator instances.
651 * Typing the name of the %iterator requires knowing the precise full
652 * type of the container, which can be tedious and impedes generic
653 * programming. Using this function lets you take advantage of automatic
654 * template parameter deduction, making the compiler match the correct
655 * types for you.
656 */
657 template<typename _Container>
658 _GLIBCXX20_CONSTEXPR
659 inline back_insert_iterator<_Container>
660 back_inserter(_Container& __x)
661 { return back_insert_iterator<_Container>(__x); }
662
663 /**
664 * @brief Turns assignment into insertion.
665 *
666 * These are output iterators, constructed from a container-of-T.
667 * Assigning a T to the iterator prepends it to the container using
668 * push_front.
669 *
670 * Tip: Using the front_inserter function to create these iterators can
671 * save typing.
672 */
673 template<typename _Container>
674 class front_insert_iterator
675 : public iterator<output_iterator_tag, void, void, void, void>
676 {
677 protected:
678 _Container* container;
679
680 public:
681 /// A nested typedef for the type of whatever container you used.
682 typedef _Container container_type;
683#if __cplusplus201703L > 201703L
684 using difference_type = ptrdiff_t;
685
686 constexpr front_insert_iterator() noexcept : container(nullptr) { }
687#endif
688
689 /// The only way to create this %iterator is with a container.
690 explicit _GLIBCXX20_CONSTEXPR
691 front_insert_iterator(_Container& __x)
692 : container(std::__addressof(__x)) { }
693
694 /**
695 * @param __value An instance of whatever type
696 * container_type::const_reference is; presumably a
697 * reference-to-const T for container<T>.
698 * @return This %iterator, for chained operations.
699 *
700 * This kind of %iterator doesn't really have a @a position in the
701 * container (you can think of the position as being permanently at
702 * the front, if you like). Assigning a value to the %iterator will
703 * always prepend the value to the front of the container.
704 */
705#if __cplusplus201703L < 201103L
706 front_insert_iterator&
707 operator=(typename _Container::const_reference __value)
708 {
709 container->push_front(__value);
710 return *this;
711 }
712#else
713 _GLIBCXX20_CONSTEXPR
714 front_insert_iterator&
715 operator=(const typename _Container::value_type& __value)
716 {
717 container->push_front(__value);
718 return *this;
719 }
720
721 _GLIBCXX20_CONSTEXPR
722 front_insert_iterator&
723 operator=(typename _Container::value_type&& __value)
724 {
725 container->push_front(std::move(__value));
726 return *this;
727 }
728#endif
729
730 /// Simply returns *this.
731 _GLIBCXX20_CONSTEXPR
732 front_insert_iterator&
733 operator*()
734 { return *this; }
735
736 /// Simply returns *this. (This %iterator does not @a move.)
737 _GLIBCXX20_CONSTEXPR
738 front_insert_iterator&
739 operator++()
740 { return *this; }
741
742 /// Simply returns *this. (This %iterator does not @a move.)
743 _GLIBCXX20_CONSTEXPR
744 front_insert_iterator
745 operator++(int)
746 { return *this; }
747 };
748
749 /**
750 * @param __x A container of arbitrary type.
751 * @return An instance of front_insert_iterator working on @p x.
752 *
753 * This wrapper function helps in creating front_insert_iterator instances.
754 * Typing the name of the %iterator requires knowing the precise full
755 * type of the container, which can be tedious and impedes generic
756 * programming. Using this function lets you take advantage of automatic
757 * template parameter deduction, making the compiler match the correct
758 * types for you.
759 */
760 template<typename _Container>
761 _GLIBCXX20_CONSTEXPR
762 inline front_insert_iterator<_Container>
763 front_inserter(_Container& __x)
764 { return front_insert_iterator<_Container>(__x); }
765
766 /**
767 * @brief Turns assignment into insertion.
768 *
769 * These are output iterators, constructed from a container-of-T.
770 * Assigning a T to the iterator inserts it in the container at the
771 * %iterator's position, rather than overwriting the value at that
772 * position.
773 *
774 * (Sequences will actually insert a @e copy of the value before the
775 * %iterator's position.)
776 *
777 * Tip: Using the inserter function to create these iterators can
778 * save typing.
779 */
780 template<typename _Container>
781 class insert_iterator
782 : public iterator<output_iterator_tag, void, void, void, void>
783 {
784#if __cplusplus201703L > 201703L && defined __cpp_lib_concepts
785 using _Iter = std::__detail::__range_iter_t<_Container>;
786
787 protected:
788 _Container* container = nullptr;
789 _Iter iter = _Iter();
790#else
791 typedef typename _Container::iterator _Iter;
792
793 protected:
794 _Container* container;
795 _Iter iter;
796#endif
797
798 public:
799 /// A nested typedef for the type of whatever container you used.
800 typedef _Container container_type;
801
802#if __cplusplus201703L > 201703L && defined __cpp_lib_concepts
803 using difference_type = ptrdiff_t;
804
805 insert_iterator() = default;
806#endif
807
808 /**
809 * The only way to create this %iterator is with a container and an
810 * initial position (a normal %iterator into the container).
811 */
812 _GLIBCXX20_CONSTEXPR
813 insert_iterator(_Container& __x, _Iter __i)
814 : container(std::__addressof(__x)), iter(__i) {}
815
816 /**
817 * @param __value An instance of whatever type
818 * container_type::const_reference is; presumably a
819 * reference-to-const T for container<T>.
820 * @return This %iterator, for chained operations.
821 *
822 * This kind of %iterator maintains its own position in the
823 * container. Assigning a value to the %iterator will insert the
824 * value into the container at the place before the %iterator.
825 *
826 * The position is maintained such that subsequent assignments will
827 * insert values immediately after one another. For example,
828 * @code
829 * // vector v contains A and Z
830 *
831 * insert_iterator i (v, ++v.begin());
832 * i = 1;
833 * i = 2;
834 * i = 3;
835 *
836 * // vector v contains A, 1, 2, 3, and Z
837 * @endcode
838 */
839#if __cplusplus201703L < 201103L
840 insert_iterator&
841 operator=(typename _Container::const_reference __value)
842 {
843 iter = container->insert(iter, __value);
844 ++iter;
845 return *this;
846 }
847#else
848 _GLIBCXX20_CONSTEXPR
849 insert_iterator&
850 operator=(const typename _Container::value_type& __value)
851 {
852 iter = container->insert(iter, __value);
853 ++iter;
854 return *this;
855 }
856
857 _GLIBCXX20_CONSTEXPR
858 insert_iterator&
859 operator=(typename _Container::value_type&& __value)
860 {
861 iter = container->insert(iter, std::move(__value));
862 ++iter;
863 return *this;
864 }
865#endif
866
867 /// Simply returns *this.
868 _GLIBCXX20_CONSTEXPR
869 insert_iterator&
870 operator*()
871 { return *this; }
872
873 /// Simply returns *this. (This %iterator does not @a move.)
874 _GLIBCXX20_CONSTEXPR
875 insert_iterator&
876 operator++()
877 { return *this; }
878
879 /// Simply returns *this. (This %iterator does not @a move.)
880 _GLIBCXX20_CONSTEXPR
881 insert_iterator&
882 operator++(int)
883 { return *this; }
884 };
885
886 /**
887 * @param __x A container of arbitrary type.
888 * @param __i An iterator into the container.
889 * @return An instance of insert_iterator working on @p __x.
890 *
891 * This wrapper function helps in creating insert_iterator instances.
892 * Typing the name of the %iterator requires knowing the precise full
893 * type of the container, which can be tedious and impedes generic
894 * programming. Using this function lets you take advantage of automatic
895 * template parameter deduction, making the compiler match the correct
896 * types for you.
897 */
898#if __cplusplus201703L > 201703L && defined __cpp_lib_concepts
899 template<typename _Container>
900 constexpr insert_iterator<_Container>
901 inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
902 { return insert_iterator<_Container>(__x, __i); }
903#else
904 template<typename _Container, typename _Iterator>
905 inline insert_iterator<_Container>
906 inserter(_Container& __x, _Iterator __i)
907 {
908 return insert_iterator<_Container>(__x,
909 typename _Container::iterator(__i));
910 }
911#endif
912
913 // @} group iterators
914
915_GLIBCXX_END_NAMESPACE_VERSION
916} // namespace
917
918namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
919{
920_GLIBCXX_BEGIN_NAMESPACE_VERSION
921
922 // This iterator adapter is @a normal in the sense that it does not
923 // change the semantics of any of the operators of its iterator
924 // parameter. Its primary purpose is to convert an iterator that is
925 // not a class, e.g. a pointer, into an iterator that is a class.
926 // The _Container parameter exists solely so that different containers
927 // using this template can instantiate different types, even if the
928 // _Iterator parameter is the same.
929 template<typename _Iterator, typename _Container>
930 class __normal_iterator
931 {
932 protected:
933 _Iterator _M_current;
934
935 typedef std::iterator_traits<_Iterator> __traits_type;
936
937 public:
938 typedef _Iterator iterator_type;
939 typedef typename __traits_type::iterator_category iterator_category;
940 typedef typename __traits_type::value_type value_type;
941 typedef typename __traits_type::difference_type difference_type;
942 typedef typename __traits_type::reference reference;
943 typedef typename __traits_type::pointer pointer;
944
945#if __cplusplus201703L > 201703L && __cpp_lib_concepts
946 using iterator_concept = std::__detail::__iter_concept<_Iterator>;
947#endif
948
949 _GLIBCXX_CONSTEXPRconstexpr __normal_iterator() _GLIBCXX_NOEXCEPTnoexcept
950 : _M_current(_Iterator()) { }
951
952 explicit _GLIBCXX20_CONSTEXPR
953 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPTnoexcept
954 : _M_current(__i) { }
955
956 // Allow iterator to const_iterator conversion
957 template<typename _Iter>
958 _GLIBCXX20_CONSTEXPR
959 __normal_iterator(const __normal_iterator<_Iter,
960 typename __enable_if<
961 (std::__are_same<_Iter, typename _Container::pointer>::__value),
962 _Container>::__type>& __i) _GLIBCXX_NOEXCEPTnoexcept
963 : _M_current(__i.base()) { }
964
965 // Forward iterator requirements
966 _GLIBCXX20_CONSTEXPR
967 reference
968 operator*() const _GLIBCXX_NOEXCEPTnoexcept
969 { return *_M_current; }
970
971 _GLIBCXX20_CONSTEXPR
972 pointer
973 operator->() const _GLIBCXX_NOEXCEPTnoexcept
974 { return _M_current; }
975
976 _GLIBCXX20_CONSTEXPR
977 __normal_iterator&
978 operator++() _GLIBCXX_NOEXCEPTnoexcept
979 {
980 ++_M_current;
981 return *this;
982 }
983
984 _GLIBCXX20_CONSTEXPR
985 __normal_iterator
986 operator++(int) _GLIBCXX_NOEXCEPTnoexcept
987 { return __normal_iterator(_M_current++); }
988
989 // Bidirectional iterator requirements
990 _GLIBCXX20_CONSTEXPR
991 __normal_iterator&
992 operator--() _GLIBCXX_NOEXCEPTnoexcept
993 {
994 --_M_current;
995 return *this;
996 }
997
998 _GLIBCXX20_CONSTEXPR
999 __normal_iterator
1000 operator--(int) _GLIBCXX_NOEXCEPTnoexcept
1001 { return __normal_iterator(_M_current--); }
1002
1003 // Random access iterator requirements
1004 _GLIBCXX20_CONSTEXPR
1005 reference
1006 operator[](difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
1007 { return _M_current[__n]; }
1008
1009 _GLIBCXX20_CONSTEXPR
1010 __normal_iterator&
1011 operator+=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
1012 { _M_current += __n; return *this; }
1013
1014 _GLIBCXX20_CONSTEXPR
1015 __normal_iterator
1016 operator+(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
1017 { return __normal_iterator(_M_current + __n); }
1018
1019 _GLIBCXX20_CONSTEXPR
1020 __normal_iterator&
1021 operator-=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
1022 { _M_current -= __n; return *this; }
1023
1024 _GLIBCXX20_CONSTEXPR
1025 __normal_iterator
1026 operator-(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
1027 { return __normal_iterator(_M_current - __n); }
1028
1029 _GLIBCXX20_CONSTEXPR
1030 const _Iterator&
1031 base() const _GLIBCXX_NOEXCEPTnoexcept
1032 { return _M_current; }
1033 };
1034
1035 // Note: In what follows, the left- and right-hand-side iterators are
1036 // allowed to vary in types (conceptually in cv-qualification) so that
1037 // comparison between cv-qualified and non-cv-qualified iterators be
1038 // valid. However, the greedy and unfriendly operators in std::rel_ops
1039 // will make overload resolution ambiguous (when in scope) if we don't
1040 // provide overloads whose operands are of the same type. Can someone
1041 // remind me what generic programming is about? -- Gaby
1042
1043#if __cpp_lib_three_way_comparison
1044 template<typename _IteratorL, typename _IteratorR, typename _Container>
1045 requires requires (_IteratorL __lhs, _IteratorR __rhs)
1046 { { __lhs == __rhs } -> std::convertible_to<bool>; }
1047 constexpr bool
1048 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1049 const __normal_iterator<_IteratorR, _Container>& __rhs)
1050 noexcept(noexcept(__lhs.base() == __rhs.base()))
1051 { return __lhs.base() == __rhs.base(); }
1052
1053 template<typename _IteratorL, typename _IteratorR, typename _Container>
1054 constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
1055 operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1056 const __normal_iterator<_IteratorR, _Container>& __rhs)
1057 noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1058 { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1059#else
1060 // Forward iterator requirements
1061 template<typename _IteratorL, typename _IteratorR, typename _Container>
1062 _GLIBCXX20_CONSTEXPR
1063 inline bool
1064 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1065 const __normal_iterator<_IteratorR, _Container>& __rhs)
1066 _GLIBCXX_NOEXCEPTnoexcept
1067 { return __lhs.base() == __rhs.base(); }
1068
1069 template<typename _Iterator, typename _Container>
1070 _GLIBCXX20_CONSTEXPR
1071 inline bool
1072 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
1073 const __normal_iterator<_Iterator, _Container>& __rhs)
1074 _GLIBCXX_NOEXCEPTnoexcept
1075 { return __lhs.base() == __rhs.base(); }
1076
1077 template<typename _IteratorL, typename _IteratorR, typename _Container>
1078 _GLIBCXX20_CONSTEXPR
1079 inline bool
1080 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1081 const __normal_iterator<_IteratorR, _Container>& __rhs)
1082 _GLIBCXX_NOEXCEPTnoexcept
1083 { return __lhs.base() != __rhs.base(); }
1084
1085 template<typename _Iterator, typename _Container>
1086 _GLIBCXX20_CONSTEXPR
1087 inline bool
1088 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
1089 const __normal_iterator<_Iterator, _Container>& __rhs)
1090 _GLIBCXX_NOEXCEPTnoexcept
1091 { return __lhs.base() != __rhs.base(); }
10
←
Assuming the condition is false
→
11
←
Returning zero, which participates in a condition later
→
1092
1093 // Random access iterator requirements
1094 template<typename _IteratorL, typename _IteratorR, typename _Container>
1095 inline bool
1096 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
1097 const __normal_iterator<_IteratorR, _Container>& __rhs)
1098 _GLIBCXX_NOEXCEPTnoexcept
1099 { return __lhs.base() < __rhs.base(); }
1100
1101 template<typename _Iterator, typename _Container>
1102 _GLIBCXX20_CONSTEXPR
1103 inline bool
1104 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
1105 const __normal_iterator<_Iterator, _Container>& __rhs)
1106 _GLIBCXX_NOEXCEPTnoexcept
1107 { return __lhs.base() < __rhs.base(); }
1108
1109 template<typename _IteratorL, typename _IteratorR, typename _Container>
1110 inline bool
1111 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1112 const __normal_iterator<_IteratorR, _Container>& __rhs)
1113 _GLIBCXX_NOEXCEPTnoexcept
1114 { return __lhs.base() > __rhs.base(); }
1115
1116 template<typename _Iterator, typename _Container>
1117 _GLIBCXX20_CONSTEXPR
1118 inline bool
1119 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
1120 const __normal_iterator<_Iterator, _Container>& __rhs)
1121 _GLIBCXX_NOEXCEPTnoexcept
1122 { return __lhs.base() > __rhs.base(); }
1123
1124 template<typename _IteratorL, typename _IteratorR, typename _Container>
1125 inline bool
1126 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1127 const __normal_iterator<_IteratorR, _Container>& __rhs)
1128 _GLIBCXX_NOEXCEPTnoexcept
1129 { return __lhs.base() <= __rhs.base(); }
1130
1131 template<typename _Iterator, typename _Container>
1132 _GLIBCXX20_CONSTEXPR
1133 inline bool
1134 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
1135 const __normal_iterator<_Iterator, _Container>& __rhs)
1136 _GLIBCXX_NOEXCEPTnoexcept
1137 { return __lhs.base() <= __rhs.base(); }
1138
1139 template<typename _IteratorL, typename _IteratorR, typename _Container>
1140 inline bool
1141 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1142 const __normal_iterator<_IteratorR, _Container>& __rhs)
1143 _GLIBCXX_NOEXCEPTnoexcept
1144 { return __lhs.base() >= __rhs.base(); }
1145
1146 template<typename _Iterator, typename _Container>
1147 _GLIBCXX20_CONSTEXPR
1148 inline bool
1149 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
1150 const __normal_iterator<_Iterator, _Container>& __rhs)
1151 _GLIBCXX_NOEXCEPTnoexcept
1152 { return __lhs.base() >= __rhs.base(); }
1153#endif // three-way comparison
1154
1155 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1156 // According to the resolution of DR179 not only the various comparison
1157 // operators but also operator- must accept mixed iterator/const_iterator
1158 // parameters.
1159 template<typename _IteratorL, typename _IteratorR, typename _Container>
1160#if __cplusplus201703L >= 201103L
1161 // DR 685.
1162 _GLIBCXX20_CONSTEXPR
1163 inline auto
1164 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1165 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1166 -> decltype(__lhs.base() - __rhs.base())
1167#else
1168 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1169 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1170 const __normal_iterator<_IteratorR, _Container>& __rhs)
1171#endif
1172 { return __lhs.base() - __rhs.base(); }
1173
1174 template<typename _Iterator, typename _Container>
1175 _GLIBCXX20_CONSTEXPR
1176 inline typename __normal_iterator<_Iterator, _Container>::difference_type
1177 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
1178 const __normal_iterator<_Iterator, _Container>& __rhs)
1179 _GLIBCXX_NOEXCEPTnoexcept
1180 { return __lhs.base() - __rhs.base(); }
1181
1182 template<typename _Iterator, typename _Container>
1183 _GLIBCXX20_CONSTEXPR
1184 inline __normal_iterator<_Iterator, _Container>
1185 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
1186 __n, const __normal_iterator<_Iterator, _Container>& __i)
1187 _GLIBCXX_NOEXCEPTnoexcept
1188 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1189
1190_GLIBCXX_END_NAMESPACE_VERSION
1191} // namespace
1192
1193namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
1194{
1195_GLIBCXX_BEGIN_NAMESPACE_VERSION
1196
1197 template<typename _Iterator, typename _Container>
1198 _GLIBCXX20_CONSTEXPR
1199 _Iterator
1200 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1201 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)noexcept(std::is_nothrow_copy_constructible<_Iterator>::
value)
1202 { return __it.base(); }
1203
1204#if __cplusplus201703L >= 201103L
1205 /**
1206 * @addtogroup iterators
1207 * @{
1208 */
1209
1210#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1211 template<semiregular _Sent>
1212 class move_sentinel
1213 {
1214 public:
1215 constexpr
1216 move_sentinel()
1217 noexcept(is_nothrow_default_constructible_v<_Sent>)
1218 : _M_last() { }
1219
1220 constexpr explicit
1221 move_sentinel(_Sent __s)
1222 noexcept(is_nothrow_move_constructible_v<_Sent>)
1223 : _M_last(std::move(__s)) { }
1224
1225 template<typename _S2> requires convertible_to<const _S2&, _Sent>
1226 constexpr
1227 move_sentinel(const move_sentinel<_S2>& __s)
1228 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1229 : _M_last(__s.base())
1230 { }
1231
1232 template<typename _S2> requires assignable_from<_Sent&, const _S2&>
1233 constexpr move_sentinel&
1234 operator=(const move_sentinel<_S2>& __s)
1235 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1236 {
1237 _M_last = __s.base();
1238 return *this;
1239 }
1240
1241 constexpr _Sent
1242 base() const
1243 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1244 { return _M_last; }
1245
1246 private:
1247 _Sent _M_last;
1248 };
1249#endif // C++20
1250
1251 // 24.4.3 Move iterators
1252 /**
1253 * Class template move_iterator is an iterator adapter with the same
1254 * behavior as the underlying iterator except that its dereference
1255 * operator implicitly converts the value returned by the underlying
1256 * iterator's dereference operator to an rvalue reference. Some
1257 * generic algorithms can be called with move iterators to replace
1258 * copying with moving.
1259 */
1260 template<typename _Iterator>
1261 class move_iterator
1262 {
1263 _Iterator _M_current;
1264
1265 using __traits_type = iterator_traits<_Iterator>;
1266#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1267 using __base_cat = typename __traits_type::iterator_category;
1268#else
1269 using __base_ref = typename __traits_type::reference;
1270#endif
1271
1272 public:
1273 using iterator_type = _Iterator;
1274
1275#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1276 using iterator_concept = input_iterator_tag;
1277 using iterator_category
1278 = __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
1279 using value_type = iter_value_t<_Iterator>;
1280 using difference_type = iter_difference_t<_Iterator>;
1281 using pointer = _Iterator;
1282 using reference = iter_rvalue_reference_t<_Iterator>;
1283#else
1284 typedef typename __traits_type::iterator_category iterator_category;
1285 typedef typename __traits_type::value_type value_type;
1286 typedef typename __traits_type::difference_type difference_type;
1287 // NB: DR 680.
1288 typedef _Iterator pointer;
1289 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1290 // 2106. move_iterator wrapping iterators returning prvalues
1291 typedef typename conditional<is_reference<__base_ref>::value,
1292 typename remove_reference<__base_ref>::type&&,
1293 __base_ref>::type reference;
1294#endif
1295
1296 _GLIBCXX17_CONSTEXPRconstexpr
1297 move_iterator()
1298 : _M_current() { }
1299
1300 explicit _GLIBCXX17_CONSTEXPRconstexpr
1301 move_iterator(iterator_type __i)
1302 : _M_current(std::move(__i)) { }
1303
1304 template<typename _Iter>
1305 _GLIBCXX17_CONSTEXPRconstexpr
1306 move_iterator(const move_iterator<_Iter>& __i)
1307 : _M_current(__i.base()) { }
1308
1309#if __cplusplus201703L <= 201703L
1310 _GLIBCXX17_CONSTEXPRconstexpr iterator_type
1311 base() const
1312 { return _M_current; }
1313#else
1314 constexpr iterator_type
1315 base() const &
1316#if __cpp_lib_concepts
1317 requires copy_constructible<iterator_type>
1318#endif
1319 { return _M_current; }
1320
1321 constexpr iterator_type
1322 base() &&
1323 { return std::move(_M_current); }
1324#endif
1325
1326 _GLIBCXX17_CONSTEXPRconstexpr reference
1327 operator*() const
1328 { return static_cast<reference>(*_M_current); }
1329
1330 _GLIBCXX17_CONSTEXPRconstexpr pointer
1331 operator->() const
1332 { return _M_current; }
1333
1334 _GLIBCXX17_CONSTEXPRconstexpr move_iterator&
1335 operator++()
1336 {
1337 ++_M_current;
1338 return *this;
1339 }
1340
1341 _GLIBCXX17_CONSTEXPRconstexpr move_iterator
1342 operator++(int)
1343 {
1344 move_iterator __tmp = *this;
1345 ++_M_current;
1346 return __tmp;
1347 }
1348
1349#if __cpp_lib_concepts
1350 constexpr void
1351 operator++(int) requires (!forward_iterator<_Iterator>)
1352 { ++_M_current; }
1353#endif
1354
1355 _GLIBCXX17_CONSTEXPRconstexpr move_iterator&
1356 operator--()
1357 {
1358 --_M_current;
1359 return *this;
1360 }
1361
1362 _GLIBCXX17_CONSTEXPRconstexpr move_iterator
1363 operator--(int)
1364 {
1365 move_iterator __tmp = *this;
1366 --_M_current;
1367 return __tmp;
1368 }
1369
1370 _GLIBCXX17_CONSTEXPRconstexpr move_iterator
1371 operator+(difference_type __n) const
1372 { return move_iterator(_M_current + __n); }
1373
1374 _GLIBCXX17_CONSTEXPRconstexpr move_iterator&
1375 operator+=(difference_type __n)
1376 {
1377 _M_current += __n;
1378 return *this;
1379 }
1380
1381 _GLIBCXX17_CONSTEXPRconstexpr move_iterator
1382 operator-(difference_type __n) const
1383 { return move_iterator(_M_current - __n); }
1384
1385 _GLIBCXX17_CONSTEXPRconstexpr move_iterator&
1386 operator-=(difference_type __n)
1387 {
1388 _M_current -= __n;
1389 return *this;
1390 }
1391
1392 _GLIBCXX17_CONSTEXPRconstexpr reference
1393 operator[](difference_type __n) const
1394 { return std::move(_M_current[__n]); }
1395
1396#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1397 template<sentinel_for<_Iterator> _Sent>
1398 friend constexpr bool
1399 operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1400 { return __x.base() == __y.base(); }
1401
1402 template<sized_sentinel_for<_Iterator> _Sent>
1403 friend constexpr iter_difference_t<_Iterator>
1404 operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1405 { return __x.base() - __y.base(); }
1406
1407 template<sized_sentinel_for<_Iterator> _Sent>
1408 friend constexpr iter_difference_t<_Iterator>
1409 operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1410 { return __x.base() - __y.base(); }
1411
1412 friend constexpr iter_rvalue_reference_t<_Iterator>
1413 iter_move(const move_iterator& __i)
1414 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1415 { return ranges::iter_move(__i._M_current); }
1416
1417 template<indirectly_swappable<_Iterator> _Iter2>
1418 friend constexpr void
1419 iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1420 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1421 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1422#endif // C++20
1423 };
1424
1425 template<typename _IteratorL, typename _IteratorR>
1426 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1427 operator==(const move_iterator<_IteratorL>& __x,
1428 const move_iterator<_IteratorR>& __y)
1429#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1430 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1431#endif
1432 { return __x.base() == __y.base(); }
1433
1434#if __cpp_lib_three_way_comparison
1435 template<typename _IteratorL,
1436 three_way_comparable_with<_IteratorL> _IteratorR>
1437 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1438 operator<=>(const move_iterator<_IteratorL>& __x,
1439 const move_iterator<_IteratorR>& __y)
1440 { return __x.base() <=> __y.base(); }
1441#else
1442 template<typename _IteratorL, typename _IteratorR>
1443 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1444 operator!=(const move_iterator<_IteratorL>& __x,
1445 const move_iterator<_IteratorR>& __y)
1446 { return !(__x == __y); }
1447#endif
1448
1449 template<typename _IteratorL, typename _IteratorR>
1450 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1451 operator<(const move_iterator<_IteratorL>& __x,
1452 const move_iterator<_IteratorR>& __y)
1453#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1454 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1455#endif
1456 { return __x.base() < __y.base(); }
1457
1458 template<typename _IteratorL, typename _IteratorR>
1459 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1460 operator<=(const move_iterator<_IteratorL>& __x,
1461 const move_iterator<_IteratorR>& __y)
1462#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1463 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1464#endif
1465 { return !(__y < __x); }
1466
1467 template<typename _IteratorL, typename _IteratorR>
1468 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1469 operator>(const move_iterator<_IteratorL>& __x,
1470 const move_iterator<_IteratorR>& __y)
1471#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1472 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1473#endif
1474 { return __y < __x; }
1475
1476 template<typename _IteratorL, typename _IteratorR>
1477 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1478 operator>=(const move_iterator<_IteratorL>& __x,
1479 const move_iterator<_IteratorR>& __y)
1480#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1481 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1482#endif
1483 { return !(__x < __y); }
1484
1485#if ! (__cplusplus201703L > 201703L && __cpp_lib_concepts)
1486 // Note: See __normal_iterator operators note from Gaby to understand
1487 // why we have these extra overloads for some move_iterator operators.
1488
1489 // These extra overloads are not needed in C++20, because the ones above
1490 // are constrained with a requires-clause and so overload resolution will
1491 // prefer them to greedy unconstrained function templates.
1492
1493 template<typename _Iterator>
1494 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1495 operator==(const move_iterator<_Iterator>& __x,
1496 const move_iterator<_Iterator>& __y)
1497 { return __x.base() == __y.base(); }
1498
1499 template<typename _Iterator>
1500 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1501 operator!=(const move_iterator<_Iterator>& __x,
1502 const move_iterator<_Iterator>& __y)
1503 { return !(__x == __y); }
1504
1505 template<typename _Iterator>
1506 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1507 operator<(const move_iterator<_Iterator>& __x,
1508 const move_iterator<_Iterator>& __y)
1509 { return __x.base() < __y.base(); }
1510
1511 template<typename _Iterator>
1512 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1513 operator<=(const move_iterator<_Iterator>& __x,
1514 const move_iterator<_Iterator>& __y)
1515 { return !(__y < __x); }
1516
1517 template<typename _Iterator>
1518 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1519 operator>(const move_iterator<_Iterator>& __x,
1520 const move_iterator<_Iterator>& __y)
1521 { return __y < __x; }
1522
1523 template<typename _Iterator>
1524 inline _GLIBCXX17_CONSTEXPRconstexpr bool
1525 operator>=(const move_iterator<_Iterator>& __x,
1526 const move_iterator<_Iterator>& __y)
1527 { return !(__x < __y); }
1528#endif // ! C++20
1529
1530 // DR 685.
1531 template<typename _IteratorL, typename _IteratorR>
1532 inline _GLIBCXX17_CONSTEXPRconstexpr auto
1533 operator-(const move_iterator<_IteratorL>& __x,
1534 const move_iterator<_IteratorR>& __y)
1535 -> decltype(__x.base() - __y.base())
1536 { return __x.base() - __y.base(); }
1537
1538 template<typename _Iterator>
1539 inline _GLIBCXX17_CONSTEXPRconstexpr move_iterator<_Iterator>
1540 operator+(typename move_iterator<_Iterator>::difference_type __n,
1541 const move_iterator<_Iterator>& __x)
1542 { return __x + __n; }
1543
1544 template<typename _Iterator>
1545 inline _GLIBCXX17_CONSTEXPRconstexpr move_iterator<_Iterator>
1546 make_move_iterator(_Iterator __i)
1547 { return move_iterator<_Iterator>(std::move(__i)); }
1548
1549 template<typename _Iterator, typename _ReturnType
1550 = typename conditional<__move_if_noexcept_cond
1551 <typename iterator_traits<_Iterator>::value_type>::value,
1552 _Iterator, move_iterator<_Iterator>>::type>
1553 inline _GLIBCXX17_CONSTEXPRconstexpr _ReturnType
1554 __make_move_if_noexcept_iterator(_Iterator __i)
1555 { return _ReturnType(__i); }
1556
1557 // Overload for pointers that matches std::move_if_noexcept more closely,
1558 // returning a constant iterator when we don't want to move.
1559 template<typename _Tp, typename _ReturnType
1560 = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1561 const _Tp*, move_iterator<_Tp*>>::type>
1562 inline _GLIBCXX17_CONSTEXPRconstexpr _ReturnType
1563 __make_move_if_noexcept_iterator(_Tp* __i)
1564 { return _ReturnType(__i); }
1565
1566#if __cplusplus201703L > 201703L && __cpp_lib_concepts
1567 // [iterators.common] Common iterators
1568
1569 namespace __detail
1570 {
1571 template<typename _It>
1572 concept __common_iter_has_arrow = indirectly_readable<const _It>
1573 && (requires(const _It& __it) { __it.operator->(); }
1574 || is_reference_v<iter_reference_t<_It>>
1575 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1576
1577 } // namespace __detail
1578
1579 /// An iterator/sentinel adaptor for representing a non-common range.
1580 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1581 requires (!same_as<_It, _Sent>) && copyable<_It>
1582 class common_iterator
1583 {
1584 template<typename _Tp, typename _Up>
1585 static constexpr bool
1586 _S_noexcept1()
1587 {
1588 if constexpr (is_trivially_default_constructible_v<_Tp>)
1589 return is_nothrow_assignable_v<_Tp, _Up>;
1590 else
1591 return is_nothrow_constructible_v<_Tp, _Up>;
1592 }
1593
1594 template<typename _It2, typename _Sent2>
1595 static constexpr bool
1596 _S_noexcept()
1597 { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1598
1599 class _Proxy
1600 {
1601 iter_value_t<_It> _M_keep;
1602
1603 _Proxy(iter_reference_t<_It>&& __x)
1604 : _M_keep(std::move(__x)) { }
1605
1606 friend class common_iterator;
1607
1608 public:
1609 const iter_value_t<_It>*
1610 operator->() const
1611 { return std::__addressof(_M_keep); }
1612 };
1613
1614 public:
1615 constexpr
1616 common_iterator()
1617 noexcept(is_nothrow_default_constructible_v<_It>)
1618 : _M_it(), _M_index(0)
1619 { }
1620
1621 constexpr
1622 common_iterator(_It __i)
1623 noexcept(is_nothrow_move_constructible_v<_It>)
1624 : _M_it(std::move(__i)), _M_index(0)
1625 { }
1626
1627 constexpr
1628 common_iterator(_Sent __s)
1629 noexcept(is_nothrow_move_constructible_v<_Sent>)
1630 : _M_sent(std::move(__s)), _M_index(1)
1631 { }
1632
1633 template<typename _It2, typename _Sent2>
1634 requires convertible_to<const _It2&, _It>
1635 && convertible_to<const _Sent2&, _Sent>
1636 constexpr
1637 common_iterator(const common_iterator<_It2, _Sent2>& __x)
1638 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1639 : _M_valueless(), _M_index(__x._M_index)
1640 {
1641 if (_M_index == 0)
1642 {
1643 if constexpr (is_trivially_default_constructible_v<_It>)
1644 _M_it = std::move(__x._M_it);
1645 else
1646 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1647 }
1648 else if (_M_index == 1)
1649 {
1650 if constexpr (is_trivially_default_constructible_v<_Sent>)
1651 _M_sent = std::move(__x._M_sent);
1652 else
1653 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1654 }
1655 }
1656
1657 constexpr
1658 common_iterator(const common_iterator& __x)
1659 noexcept(_S_noexcept<const _It&, const _Sent&>())
1660 : _M_valueless(), _M_index(__x._M_index)
1661 {
1662 if (_M_index == 0)
1663 {
1664 if constexpr (is_trivially_default_constructible_v<_It>)
1665 _M_it = std::move(__x._M_it);
1666 else
1667 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1668 }
1669 else if (_M_index == 1)
1670 {
1671 if constexpr (is_trivially_default_constructible_v<_Sent>)
1672 _M_sent = std::move(__x._M_sent);
1673 else
1674 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1675 }
1676 }
1677
1678 common_iterator&
1679 operator=(const common_iterator& __x)
1680 noexcept(is_nothrow_copy_assignable_v<_It>
1681 && is_nothrow_copy_assignable_v<_Sent>
1682 && is_nothrow_copy_constructible_v<_It>
1683 && is_nothrow_copy_constructible_v<_Sent>)
1684 {
1685 return this->operator=<_It, _Sent>(__x);
1686 }
1687
1688 template<typename _It2, typename _Sent2>
1689 requires convertible_to<const _It2&, _It>
1690 && convertible_to<const _Sent2&, _Sent>
1691 && assignable_from<_It&, const _It2&>
1692 && assignable_from<_Sent&, const _Sent2&>
1693 common_iterator&
1694 operator=(const common_iterator<_It2, _Sent2>& __x)
1695 noexcept(is_nothrow_constructible_v<_It, const _It2&>
1696 && is_nothrow_constructible_v<_Sent, const _Sent2&>
1697 && is_nothrow_assignable_v<_It, const _It2&>
1698 && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1699 {
1700 switch(_M_index << 2 | __x._M_index)
1701 {
1702 case 0b0000:
1703 _M_it = __x._M_it;
1704 break;
1705 case 0b0101:
1706 _M_sent = __x._M_sent;
1707 break;
1708 case 0b0001:
1709 _M_it.~_It();
1710 _M_index = -1;
1711 [[fallthrough]];
1712 case 0b1001:
1713 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1714 _M_index = 1;
1715 break;
1716 case 0b0100:
1717 _M_sent.~_Sent();
1718 _M_index = -1;
1719 [[fallthrough]];
1720 case 0b1000:
1721 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1722 _M_index = 0;
1723 break;
1724 default:
1725 __glibcxx_assert(__x._M_has_value());
1726 __builtin_unreachable();
1727 }
1728 return *this;
1729 }
1730
1731 ~common_iterator()
1732 {
1733 switch (_M_index)
1734 {
1735 case 0:
1736 _M_it.~_It();
1737 break;
1738 case 1:
1739 _M_sent.~_Sent();
1740 break;
1741 }
1742 }
1743
1744 decltype(auto)
1745 operator*()
1746 {
1747 __glibcxx_assert(_M_index == 0);
1748 return *_M_it;
1749 }
1750
1751 decltype(auto)
1752 operator*() const requires __detail::__dereferenceable<const _It>
1753 {
1754 __glibcxx_assert(_M_index == 0);
1755 return *_M_it;
1756 }
1757
1758 decltype(auto)
1759 operator->() const requires __detail::__common_iter_has_arrow<_It>
1760 {
1761 __glibcxx_assert(_M_index == 0);
1762 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1763 return _M_it;
1764 else if constexpr (is_reference_v<iter_reference_t<_It>>)
1765 {
1766 auto&& __tmp = *_M_it;
1767 return std::__addressof(__tmp);
1768 }
1769 else
1770 return _Proxy{*_M_it};
1771 }
1772
1773 common_iterator&
1774 operator++()
1775 {
1776 __glibcxx_assert(_M_index == 0);
1777 ++_M_it;
1778 return *this;
1779 }
1780
1781 decltype(auto)
1782 operator++(int)
1783 {
1784 __glibcxx_assert(_M_index == 0);
1785 if constexpr (forward_iterator<_It>)
1786 {
1787 common_iterator __tmp = *this;
1788 ++*this;
1789 return __tmp;
1790 }
1791 else
1792 return _M_it++;
1793 }
1794
1795 template<typename _It2, sentinel_for<_It> _Sent2>
1796 requires sentinel_for<_Sent, _It2>
1797 friend bool
1798 operator==(const common_iterator& __x,
1799 const common_iterator<_It2, _Sent2>& __y)
1800 {
1801 switch(__x._M_index << 2 | __y._M_index)
1802 {
1803 case 0b0000:
1804 case 0b0101:
1805 return true;
1806 case 0b0001:
1807 return __x._M_it == __y._M_sent;
1808 case 0b0100:
1809 return __x._M_sent == __y._M_it;
1810 default:
1811 __glibcxx_assert(__x._M_has_value());
1812 __glibcxx_assert(__y._M_has_value());
1813 __builtin_unreachable();
1814 }
1815 }
1816
1817 template<typename _It2, sentinel_for<_It> _Sent2>
1818 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1819 friend bool
1820 operator==(const common_iterator& __x,
1821 const common_iterator<_It2, _Sent2>& __y)
1822 {
1823 switch(__x._M_index << 2 | __y._M_index)
1824 {
1825 case 0b0101:
1826 return true;
1827 case 0b0000:
1828 return __x._M_it == __y._M_it;
1829 case 0b0001:
1830 return __x._M_it == __y._M_sent;
1831 case 0b0100:
1832 return __x._M_sent == __y._M_it;
1833 default:
1834 __glibcxx_assert(__x._M_has_value());
1835 __glibcxx_assert(__y._M_has_value());
1836 __builtin_unreachable();
1837 }
1838 }
1839
1840 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1841 requires sized_sentinel_for<_Sent, _It2>
1842 friend iter_difference_t<_It2>
1843 operator-(const common_iterator& __x,
1844 const common_iterator<_It2, _Sent2>& __y)
1845 {
1846 switch(__x._M_index << 2 | __y._M_index)
1847 {
1848 case 0b0101:
1849 return 0;
1850 case 0b0000:
1851 return __x._M_it - __y._M_it;
1852 case 0b0001:
1853 return __x._M_it - __y._M_sent;
1854 case 0b0100:
1855 return __x._M_sent - __y._M_it;
1856 default:
1857 __glibcxx_assert(__x._M_has_value());
1858 __glibcxx_assert(__y._M_has_value());
1859 __builtin_unreachable();
1860 }
1861 }
1862
1863 friend iter_rvalue_reference_t<_It>
1864 iter_move(const common_iterator& __i)
1865 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1866 requires input_iterator<_It>
1867 {
1868 __glibcxx_assert(__i._M_index == 0);
1869 return ranges::iter_move(__i._M_it);
1870 }
1871
1872 template<indirectly_swappable<_It> _It2, typename _Sent2>
1873 friend void
1874 iter_swap(const common_iterator& __x,
1875 const common_iterator<_It2, _Sent2>& __y)
1876 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1877 std::declval<const _It2&>())))
1878 {
1879 __glibcxx_assert(__x._M_index == 0);
1880 __glibcxx_assert(__y._M_index == 0);
1881 return ranges::iter_swap(__x._M_it, __y._M_it);
1882 }
1883
1884 private:
1885 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1886 friend class common_iterator;
1887
1888 bool _M_has_value() const noexcept { return _M_index < 2; }
1889
1890 union
1891 {
1892 _It _M_it;
1893 _Sent _M_sent;
1894 unsigned char _M_valueless;
1895 };
1896 unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
1897 };
1898
1899 template<typename _It, typename _Sent>
1900 struct incrementable_traits<common_iterator<_It, _Sent>>
1901 {
1902 using difference_type = iter_difference_t<_It>;
1903 };
1904
1905 namespace __detail
1906 {
1907 // FIXME: This has to be at namespace-scope because of PR 92103.
1908 template<typename _It, typename _Sent>
1909 struct __common_iter_ptr
1910 {
1911 using type = void;
1912 };
1913
1914 template<typename _It, typename _Sent>
1915 requires __detail::__common_iter_has_arrow<_It>
1916 struct __common_iter_ptr<_It, _Sent>
1917 {
1918 using common_iterator = std::common_iterator<_It, _Sent>;
1919
1920 using type
1921 = decltype(std::declval<const common_iterator&>().operator->());
1922 };
1923 } // namespace __detail
1924
1925 template<input_iterator _It, typename _Sent>
1926 struct iterator_traits<common_iterator<_It, _Sent>>
1927 {
1928 using iterator_concept = conditional_t<forward_iterator<_It>,
1929 forward_iterator_tag, input_iterator_tag>;
1930 using iterator_category = __detail::__clamp_iter_cat<
1931 typename iterator_traits<_It>::iterator_category,
1932 forward_iterator_tag, input_iterator_tag>;
1933 using value_type = iter_value_t<_It>;
1934 using difference_type = iter_difference_t<_It>;
1935 using pointer = typename __detail::__common_iter_ptr<_It, _Sent>::type;
1936 using reference = iter_reference_t<_It>;
1937 };
1938
1939 // [iterators.counted] Counted iterators
1940
1941 /// An iterator adaptor that keeps track of the distance to the end.
1942 template<input_or_output_iterator _It>
1943 class counted_iterator
1944 {
1945 public:
1946 using iterator_type = _It;
1947
1948 constexpr counted_iterator() = default;
1949
1950 constexpr
1951 counted_iterator(_It __i, iter_difference_t<_It> __n)
1952 : _M_current(std::move(__i)), _M_length(__n)
1953 { __glibcxx_assert(__n >= 0); }
1954
1955 template<typename _It2>
1956 requires convertible_to<const _It2&, _It>
1957 constexpr
1958 counted_iterator(const counted_iterator<_It2>& __x)
1959 : _M_current(__x._M_current), _M_length(__x._M_length)
1960 { }
1961
1962 template<typename _It2>
1963 requires assignable_from<_It&, const _It2&>
1964 constexpr counted_iterator&
1965 operator=(const counted_iterator<_It2>& __x)
1966 {
1967 _M_current = __x._M_current;
1968 _M_length = __x._M_length;
1969 return *this;
1970 }
1971
1972 constexpr _It
1973 base() const &
1974 noexcept(is_nothrow_copy_constructible_v<_It>)
1975 requires copy_constructible<_It>
1976 { return _M_current; }
1977
1978 constexpr _It
1979 base() &&
1980 noexcept(is_nothrow_move_constructible_v<_It>)
1981 { return std::move(_M_current); }
1982
1983 constexpr iter_difference_t<_It>
1984 count() const noexcept { return _M_length; }
1985
1986 constexpr decltype(auto)
1987 operator*()
1988 noexcept(noexcept(*_M_current))
1989 { return *_M_current; }
1990
1991 constexpr decltype(auto)
1992 operator*() const
1993 noexcept(noexcept(*_M_current))
1994 requires __detail::__dereferenceable<const _It>
1995 { return *_M_current; }
1996
1997 constexpr counted_iterator&
1998 operator++()
1999 {
2000 __glibcxx_assert(_M_length > 0);
2001 ++_M_current;
2002 --_M_length;
2003 return *this;
2004 }
2005
2006 decltype(auto)
2007 operator++(int)
2008 {
2009 __glibcxx_assert(_M_length > 0);
2010 --_M_length;
2011 __trytry
2012 {
2013 return _M_current++;
2014 } __catch(...)catch(...) {
2015 ++_M_length;
2016 throw;
2017 }
2018
2019 }
2020
2021 constexpr counted_iterator
2022 operator++(int) requires forward_iterator<_It>
2023 {
2024 auto __tmp = *this;
2025 ++*this;
2026 return __tmp;
2027 }
2028
2029 constexpr counted_iterator&
2030 operator--() requires bidirectional_iterator<_It>
2031 {
2032 --_M_current;
2033 ++_M_length;
2034 return *this;
2035 }
2036
2037 constexpr counted_iterator
2038 operator--(int) requires bidirectional_iterator<_It>
2039 {
2040 auto __tmp = *this;
2041 --*this;
2042 return __tmp;
2043 }
2044
2045 constexpr counted_iterator
2046 operator+(iter_difference_t<_It> __n) const
2047 requires random_access_iterator<_It>
2048 { return counted_iterator(_M_current + __n, _M_length - __n); }
2049
2050 friend constexpr counted_iterator
2051 operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2052 requires random_access_iterator<_It>
2053 { return __x + __n; }
2054
2055 constexpr counted_iterator&
2056 operator+=(iter_difference_t<_It> __n)
2057 requires random_access_iterator<_It>
2058 {
2059 __glibcxx_assert(__n <= _M_length);
2060 _M_current += __n;
2061 _M_length -= __n;
2062 return *this;
2063 }
2064
2065 constexpr counted_iterator
2066 operator-(iter_difference_t<_It> __n) const
2067 requires random_access_iterator<_It>
2068 { return counted_iterator(_M_current - __n, _M_length + __n); }
2069
2070 template<common_with<_It> _It2>
2071 friend constexpr iter_difference_t<_It2>
2072 operator-(const counted_iterator& __x,
2073 const counted_iterator<_It2>& __y)
2074 { return __y._M_length - __x._M_length; }
2075
2076 friend constexpr iter_difference_t<_It>
2077 operator-(const counted_iterator& __x, default_sentinel_t)
2078 { return -__x._M_length; }
2079
2080 friend constexpr iter_difference_t<_It>
2081 operator-(default_sentinel_t, const counted_iterator& __y)
2082 { return __y._M_length; }
2083
2084 constexpr counted_iterator&
2085 operator-=(iter_difference_t<_It> __n)
2086 requires random_access_iterator<_It>
2087 {
2088 __glibcxx_assert(-__n <= _M_length);
2089 _M_current -= __n;
2090 _M_length += __n;
2091 return *this;
2092 }
2093
2094 constexpr decltype(auto)
2095 operator[](iter_difference_t<_It> __n) const
2096 noexcept(noexcept(_M_current[__n]))
2097 requires random_access_iterator<_It>
2098 {
2099 __glibcxx_assert(__n < _M_length);
2100 return _M_current[__n];
2101 }
2102
2103 template<common_with<_It> _It2>
2104 friend constexpr bool
2105 operator==(const counted_iterator& __x,
2106 const counted_iterator<_It2>& __y)
2107 { return __x._M_length == __y._M_length; }
2108
2109 friend constexpr bool
2110 operator==(const counted_iterator& __x, default_sentinel_t)
2111 { return __x._M_length == 0; }
2112
2113 template<common_with<_It> _It2>
2114 friend constexpr strong_ordering
2115 operator<=>(const counted_iterator& __x,
2116 const counted_iterator<_It2>& __y)
2117 { return __y._M_length <=> __x._M_length; }
2118
2119 friend constexpr iter_rvalue_reference_t<_It>
2120 iter_move(const counted_iterator& __i)
2121 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2122 requires input_iterator<_It>
2123 { return ranges::iter_move(__i._M_current); }
2124
2125 template<indirectly_swappable<_It> _It2>
2126 friend constexpr void
2127 iter_swap(const counted_iterator& __x,
2128 const counted_iterator<_It2>& __y)
2129 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2130 { ranges::iter_swap(__x._M_current, __y._M_current); }
2131
2132 private:
2133 template<input_or_output_iterator _It2> friend class counted_iterator;
2134
2135 _It _M_current = _It();
2136 iter_difference_t<_It> _M_length = 0;
2137 };
2138
2139 template<typename _It>
2140 struct incrementable_traits<counted_iterator<_It>>
2141 {
2142 using difference_type = iter_difference_t<_It>;
2143 };
2144
2145 template<input_iterator _It>
2146 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2147 {
2148 using pointer = void;
2149 };
2150#endif // C++20
2151
2152 // @} group iterators
2153
2154 template<typename _Iterator>
2155 auto
2156 __niter_base(move_iterator<_Iterator> __it)
2157 -> decltype(make_move_iterator(__niter_base(__it.base())))
2158 { return make_move_iterator(__niter_base(__it.base())); }
2159
2160 template<typename _Iterator>
2161 struct __is_move_iterator<move_iterator<_Iterator> >
2162 {
2163 enum { __value = 1 };
2164 typedef __true_type __type;
2165 };
2166
2167 template<typename _Iterator>
2168 auto
2169 __miter_base(move_iterator<_Iterator> __it)
2170 -> decltype(__miter_base(__it.base()))
2171 { return __miter_base(__it.base()); }
2172
2173#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) std::make_move_iterator(_Iter)
2174#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) \
2175 std::__make_move_if_noexcept_iterator(_Iter)
2176#else
2177#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) (_Iter)
2178#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) (_Iter)
2179#endif // C++11
2180
2181#if __cpp_deduction_guides201703L >= 201606
2182 // These helper traits are used for deduction guides
2183 // of associative containers.
2184 template<typename _InputIterator>
2185 using __iter_key_t = remove_const_t<
2186 typename iterator_traits<_InputIterator>::value_type::first_type>;
2187
2188 template<typename _InputIterator>
2189 using __iter_val_t =
2190 typename iterator_traits<_InputIterator>::value_type::second_type;
2191
2192 template<typename _T1, typename _T2>
2193 struct pair;
2194
2195 template<typename _InputIterator>
2196 using __iter_to_alloc_t =
2197 pair<add_const_t<__iter_key_t<_InputIterator>>,
2198 __iter_val_t<_InputIterator>>;
2199#endif // __cpp_deduction_guides
2200
2201_GLIBCXX_END_NAMESPACE_VERSION
2202} // namespace
2203
2204#ifdef _GLIBCXX_DEBUG
2205# include <debug/stl_iterator.h>
2206#endif
2207
2208#endif