sc/source/core/tool/rangecache.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 <rangecache.hxx>
  21 #include <cellvalue.hxx>
  22 #include <document.hxx>
  23 #include <brdcst.hxx>
  24 #include <queryevaluator.hxx>
  25 #include <queryparam.hxx>
  26
  27 #include <sal/log.hxx>
  28 #include <svl/numformat.hxx>
  29 #include <unotools/collatorwrapper.hxx>
  30
  31 static bool needsDescending(ScQueryOp op)
  32 {
  33     assert(op == SC_GREATER || op == SC_GREATER_EQUAL || op == SC_LESS || op == SC_LESS_EQUAL
  34            || op == SC_EQUAL);
  35     // We want all matching values to start in the sort order,
  36     // since the data is searched from start until the last matching one.
  37     return op == SC_GREATER || op == SC_GREATER_EQUAL;
  38 }
  39
  40 static ScSortedRangeCache::ValueType toValueType(const ScQueryParam& param)
  41 {
  42     assert(param.GetEntry(0).bDoQuery && !param.GetEntry(1).bDoQuery
  43            && param.GetEntry(0).GetQueryItems().size() == 1);
  44     assert(param.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString
  45            || param.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue);
  46     if (param.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue)
  47         return ScSortedRangeCache::ValueType::Values;
  48     return param.bCaseSens ? ScSortedRangeCache::ValueType::StringsCaseSensitive
  49                            : ScSortedRangeCache::ValueType::StringsCaseInsensitive;
  50 }
  51
  52 ScSortedRangeCache::ScSortedRangeCache(ScDocument* pDoc, const ScRange& rRange,
  53                                        const ScQueryParam& param, ScInterpreterContext* context,
  54                                        bool invalid, bool bNewSearchFunction,
  55                                        sal_uInt8 nSortedBinarySearch)
  56     : maRange(rRange)
  57     , mpDoc(pDoc)
  58     , mValid(false)
  59     , mRowSearch(param.bByRow)
  60     , mValueType(toValueType(param))
  61 {
  62     if (mRowSearch)
  63         assert(maRange.aStart.Col() == maRange.aEnd.Col());
  64     else
  65         assert(maRange.aStart.Row() == maRange.aEnd.Row());
  66     assert(maRange.aStart.Tab() == maRange.aEnd.Tab());
  67     SCTAB nTab = maRange.aStart.Tab();
  68     assert(param.GetEntry(0).bDoQuery && !param.GetEntry(1).bDoQuery
  69            && param.GetEntry(0).GetQueryItems().size() == 1);
  70     const ScQueryEntry& entry = param.GetEntry(0);
  71     const ScQueryEntry::Item& item = entry.GetQueryItem();
  72     mQueryOp = entry.eOp;
  73     mQueryType = item.meType;
  74
  75     if (invalid)
  76         return; // leave empty
  77
  78     SCROW startRow = maRange.aStart.Row();
  79     SCROW endRow = maRange.aEnd.Row();
  80     SCCOL startCol = maRange.aStart.Col();
  81     SCCOL endCol = maRange.aEnd.Col();
  82     if (!item.mbMatchEmpty)
  83         if (!pDoc->ShrinkToDataArea(nTab, startCol, startRow, endCol, endRow))
  84             return; // no data cells, no need for a cache
  85
  86     if (mValueType == ValueType::Values)
  87     {
  88         struct ColRowData
  89         {
  90             SCCOLROW col_row;
  91             double value;
  92         };
  93
  94         std::vector<ColRowData> colrowData;
  95         for (SCCOL nCol = startCol; nCol <= endCol; ++nCol)
  96         {
  97             for (SCROW nRow = startRow; nRow <= endRow; ++nRow)
  98             {
  99                 ScRefCellValue cell(pDoc->GetRefCellValue(ScAddress(nCol, nRow, nTab)));
 100                 if (ScQueryEvaluator::isQueryByValue(mQueryOp, mQueryType, cell))
 101                     colrowData.push_back(ColRowData{ mRowSearch ? nRow : nCol, cell.getValue() });
 102                 else if (ScQueryEvaluator::isQueryByString(mQueryOp, mQueryType, cell))
 103                 {
 104                     // Make sure that other possibilities in the generic handling
 105                     // in ScQueryEvaluator::processEntry() do not alter the results.
 106                     // (ByTextColor/ByBackgroundColor are blocked by CanBeUsedForSorterCache(),
 107                     // but isQueryByString() is possible if the cell content is a string.
 108                     // And including strings here would be tricky, as the string comparison
 109                     // may possibly(?) be different than a numeric one. So check if the string
 110                     // may possibly match a number, by converting it to one. If it can't match,
 111                     // then it's fine to ignore it (and it can happen e.g. if the query uses
 112                     // the whole column which includes a textual header). But if it can possibly
 113                     // match, then bail out and leave it to the unoptimized case.
 114                     // TODO Maybe it would actually work to use the numeric value obtained here?
 115                     if (!bNewSearchFunction && !ScQueryEvaluator::isMatchWholeCell(*pDoc, mQueryOp))
 116                         return; // substring matching cannot be sorted, but new search functions are sorted
 117                     sal_uInt32 format = 0;
 118                     double value;
 119                     if (context->NFIsNumberFormat(cell.getString(pDoc), format, value))
 120                         return;
 121                 }
 122             }
 123         }
 124
 125         if (nSortedBinarySearch == 0x00) //nBinarySearchDisabled = 0x00
 126         {
 127             std::stable_sort(
 128                 colrowData.begin(), colrowData.end(),
 129                 [](const ColRowData& d1, const ColRowData& d2) { return d1.value < d2.value; });
 130         }
 131         else if (nSortedBinarySearch == 0x01) //nSearchbAscd
 132         {
 133             // expected it is already sorted properly in Ascd mode.
 134         }
 135         else /*(nSortedBinarySearch == 0x02) nSearchbDesc*/
 136         {
 137             // expected it is already sorted properly in Desc mode, just need to reverse.
 138             std::reverse(colrowData.begin(), colrowData.end());
 139         }
 140
 141         if (needsDescending(entry.eOp))
 142         {
 143             for (auto it = colrowData.rbegin(); it != colrowData.rend(); ++it)
 144             {
 145                 if (mRowSearch)
 146                     mSortedRows.emplace_back(it->col_row);
 147                 else
 148                     mSortedCols.emplace_back(it->col_row);
 149             }
 150         }
 151         else
 152         {
 153             for (const ColRowData& d : colrowData)
 154             {
 155                 if (mRowSearch)
 156                     mSortedRows.emplace_back(d.col_row);
 157                 else
 158                     mSortedCols.emplace_back(d.col_row);
 159             }
 160         }
 161     }
 162     else
 163     {
 164         struct ColRowData
 165         {
 166             SCCOLROW col_row;
 167             OUString string;
 168         };
 169         std::vector<ColRowData> colrowData;
 170         // Try to reuse as much ScQueryEvaluator code as possible, this should
 171         // basically do the same comparisons.
 172         assert(pDoc->FetchTable(nTab) != nullptr);
 173         ScQueryEvaluator evaluator(*pDoc, *pDoc->FetchTable(nTab), param, context, nullptr,
 174                                    bNewSearchFunction);
 175         for (SCCOL nCol = startCol; nCol <= endCol; ++nCol)
 176         {
 177             for (SCROW nRow = startRow; nRow <= endRow; ++nRow)
 178             {
 179                 ScRefCellValue cell(pDoc->GetRefCellValue(ScAddress(nCol, nRow, nTab)));
 180                 // This should be used only with ScQueryEntry::ByString, and that
 181                 // means that ScQueryEvaluator::isQueryByString() should be the only
 182                 // possibility in the generic handling in ScQueryEvaluator::processEntry()
 183                 // (ByTextColor/ByBackgroundColor are blocked by CanBeUsedForSorterCache(),
 184                 // and isQueryByValue() is blocked by ScQueryEntry::ByString).
 185                 assert(mQueryType == ScQueryEntry::ByString);
 186                 assert(!ScQueryEvaluator::isQueryByValue(mQueryOp, mQueryType, cell));
 187                 if (ScQueryEvaluator::isQueryByString(mQueryOp, mQueryType, cell))
 188                 {
 189                     OUString string = evaluator.getCellString(cell, nRow, nCol);
 190                     colrowData.push_back(ColRowData{ mRowSearch ? nRow : nCol, string });
 191                 }
 192             }
 193         }
 194         CollatorWrapper& collator
 195             = ScGlobal::GetCollator(mValueType == ValueType::StringsCaseSensitive);
 196
 197         if (nSortedBinarySearch == 0x00) //nBinarySearchDisabled = 0x00
 198         {
 199             std::stable_sort(colrowData.begin(), colrowData.end(),
 200                              [&collator](const ColRowData& d1, const ColRowData& d2) {
 201                                  return collator.compareString(d1.string, d2.string) < 0;
 202                              });
 203         }
 204         else if (nSortedBinarySearch == 0x01) //nSearchbAscd
 205         {
 206             // expected it is already sorted properly in Asc mode.
 207         }
 208         else /*(nSortedBinarySearch == 0x02) nSearchbDesc*/
 209         {
 210             // expected it is already sorted properly in Desc mode, just need to reverse.
 211             std::reverse(colrowData.begin(), colrowData.end());
 212         }
 213
 214         if (needsDescending(entry.eOp))
 215         {
 216             for (auto it = colrowData.rbegin(); it != colrowData.rend(); ++it)
 217             {
 218                 if (mRowSearch)
 219                     mSortedRows.emplace_back(it->col_row);
 220                 else
 221                     mSortedCols.emplace_back(it->col_row);
 222             }
 223         }
 224         else
 225         {
 226             for (const ColRowData& d : colrowData)
 227             {
 228                 if (mRowSearch)
 229                     mSortedRows.emplace_back(d.col_row);
 230                 else
 231                     mSortedCols.emplace_back(d.col_row);
 232             }
 233         }
 234     }
 235
 236     if (mRowSearch)
 237     {
 238         mRowToIndex.resize(maRange.aEnd.Row() - maRange.aStart.Row() + 1, mSortedRows.max_size());
 239         for (size_t i = 0; i < mSortedRows.size(); ++i)
 240             mRowToIndex[mSortedRows[i] - maRange.aStart.Row()] = i;
 241     }
 242     else
 243     {
 244         mColToIndex.resize(maRange.aEnd.Col() - maRange.aStart.Col() + 1, mSortedCols.max_size());
 245         for (size_t i = 0; i < mSortedCols.size(); ++i)
 246             mColToIndex[mSortedCols[i] - maRange.aStart.Col()] = i;
 247     }
 248     mValid = true;
 249 }
 250
 251 void ScSortedRangeCache::Notify(const SfxHint& rHint)
 252 {
 253     if (!mpDoc->IsInDtorClear())
 254     {
 255         if (rHint.GetId() == SfxHintId::ScDataChanged || rHint.GetId() == SfxHintId::ScAreaChanged)
 256         {
 257             mpDoc->RemoveSortedRangeCache(*this);
 258             // this ScSortedRangeCache is deleted by RemoveSortedRangeCache
 259         }
 260     }
 261 }
 262
 263 ScSortedRangeCache::HashKey ScSortedRangeCache::makeHashKey(const ScRange& range,
 264                                                             const ScQueryParam& param)
 265 {
 266     assert(param.GetEntry(0).bDoQuery && !param.GetEntry(1).bDoQuery
 267            && param.GetEntry(0).GetQueryItems().size() == 1);
 268     const ScQueryEntry& entry = param.GetEntry(0);
 269     const ScQueryEntry::Item& item = entry.GetQueryItem();
 270     return { range, toValueType(param), entry.eOp, item.meType };
 271 }
 272
 273 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */