sc/inc/rangecache.hxx

   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 #pragma once
  21
  22 #include "address.hxx"
  23 #include "queryentry.hxx"
  24 #include <o3tl/hash_combine.hxx>
  25 #include <svl/listener.hxx>
  26
  27 #include <memory>
  28 #include <unordered_map>
  29
  30 class ScDocument;
  31 struct ScInterpreterContext;
  32 struct ScQueryParam;
  33 struct ScSortedRangeCacheMap;
  34
  35 /** Sorted cache for one range used with interpreter functions such as VLOOKUP
  36     and MATCH. Caches sorted order for cells in the given range, which must
  37     be one column. This allows faster lookups when cells are not sorted.
  38
  39     The class has a vector of SCROW items, which is sorted according to values
  40     of those cells. Therefore e.g. binary search of those cells can be done
  41     by doing binary search of the vector while mapping the indexes to rows.
  42  */
  43
  44 class ScSortedRangeCache final : public SvtListener
  45 {
  46 public:
  47     /// MUST be new'd because Notify() deletes.
  48     ScSortedRangeCache(ScDocument* pDoc, const ScRange& rRange, const ScQueryParam& param,
  49                        ScInterpreterContext* context, bool invalid = false,
  50                        bool bNewSearchFunction = false, sal_uInt8 nSortedBinarySearch = 0x00);
  51
  52     /// Returns if the cache is usable.
  53     bool isValid() const { return mValid; }
  54
  55     /// Remove from document structure and delete (!) cache on modify hint.
  56     virtual void Notify(const SfxHint& rHint) override;
  57
  58     const ScRange& getRange() const { return maRange; }
  59
  60     enum class ValueType
  61     {
  62         Values,
  63         StringsCaseSensitive,
  64         StringsCaseInsensitive
  65     };
  66     struct HashKey
  67     {
  68         ScRange range;
  69         ValueType valueType;
  70         ScQueryOp queryOp;
  71         ScQueryEntry::QueryType queryType;
  72         bool operator==(const HashKey& other) const
  73         {
  74             return range == other.range && valueType == other.valueType && queryOp == other.queryOp
  75                    && queryType == other.queryType;
  76         }
  77     };
  78     HashKey getHashKey() const { return { maRange, mValueType, mQueryOp, mQueryType }; }
  79     static HashKey makeHashKey(const ScRange& range, const ScQueryParam& param);
  80
  81     struct Hash
  82     {
  83         size_t operator()(const HashKey& key) const
  84         {
  85             // Range should be just one column.
  86             size_t hash = key.range.hashStartColumn();
  87             o3tl::hash_combine(hash, key.valueType);
  88             o3tl::hash_combine(hash, key.queryOp);
  89             o3tl::hash_combine(hash, key.queryType);
  90             return hash;
  91         }
  92     };
  93
  94     /// Returns if the cache values in rows.
  95     bool isRowSearch() const { return mRowSearch; }
  96
  97     const std::vector<SCROW>& sortedRows() const { return mSortedRows; }
  98     size_t indexForRow(SCROW row) const
  99     {
 100         assert(row >= maRange.aStart.Row() && row <= maRange.aEnd.Row());
 101         assert(mRowToIndex[row - maRange.aStart.Row()] != mSortedRows.max_size());
 102         return mRowToIndex[row - maRange.aStart.Row()];
 103     }
 104     SCROW rowForIndex(size_t index) const { return mSortedRows[index]; }
 105
 106     const std::vector<SCCOLROW>& sortedCols() const { return mSortedCols; }
 107     size_t indexForCol(SCCOL col) const
 108     {
 109         assert(col >= maRange.aStart.Col() && col <= maRange.aEnd.Col());
 110         assert(mColToIndex[col - maRange.aStart.Col()] != mSortedCols.max_size());
 111         return mColToIndex[col - maRange.aStart.Col()];
 112     }
 113     SCCOL colForIndex(size_t index) const { return mSortedCols[index]; }
 114
 115 private:
 116     std::vector<SCROW> mSortedRows; // Rows sorted by their value.
 117     std::vector<SCCOLROW> mSortedCols; // Cols sorted by their value.
 118     std::vector<size_t> mRowToIndex; // indexed by 'SCROW - maRange.aStart.Row()'
 119     std::vector<size_t> mColToIndex; // indexed by 'SCCOL - maRange.aStart.Col()'
 120     ScRange maRange;
 121     ScDocument* mpDoc;
 122     bool mValid;
 123     bool mRowSearch;
 124     ValueType mValueType;
 125     ScQueryOp mQueryOp;
 126     ScQueryEntry::QueryType mQueryType;
 127
 128     ScSortedRangeCache(const ScSortedRangeCache&) = delete;
 129     ScSortedRangeCache& operator=(const ScSortedRangeCache&) = delete;
 130 };
 131
 132 // Struct because including lookupcache.hxx in document.hxx isn't wanted.
 133 struct ScSortedRangeCacheMap
 134 {
 135     std::unordered_map<ScSortedRangeCache::HashKey, std::unique_ptr<ScSortedRangeCache>,
 136                        ScSortedRangeCache::Hash>
 137         aCacheMap;
 138 };
 139
 140 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */