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
  51     /// Returns if the cache is usable.
  52     bool isValid() const { return mValid; }
  53
  54     /// Remove from document structure and delete (!) cache on modify hint.
  55     virtual void Notify(const SfxHint& rHint) override;
  56
  57     const ScRange& getRange() const { return maRange; }
  58
  59     enum class ValueType
  60     {
  61         Values,
  62         StringsCaseSensitive,
  63         StringsCaseInsensitive
  64     };
  65     struct HashKey
  66     {
  67         ScRange range;
  68         ValueType valueType;
  69         ScQueryOp queryOp;
  70         ScQueryEntry::QueryType queryType;
  71         bool operator==(const HashKey& other) const
  72         {
  73             return range == other.range && valueType == other.valueType && queryOp == other.queryOp
  74                    && queryType == other.queryType;
  75         }
  76     };
  77     HashKey getHashKey() const { return { maRange, mValueType, mQueryOp, mQueryType }; }
  78     static HashKey makeHashKey(const ScRange& range, const ScQueryParam& param);
  79
  80     struct Hash
  81     {
  82         size_t operator()(const HashKey& key) const
  83         {
  84             // Range should be just one column.
  85             size_t hash = key.range.hashStartColumn();
  86             o3tl::hash_combine(hash, key.valueType);
  87             o3tl::hash_combine(hash, key.queryOp);
  88             o3tl::hash_combine(hash, key.queryType);
  89             return hash;
  90         }
  91     };
  92
  93     const std::vector<SCROW>& sortedRows() const { return mSortedRows; }
  94     size_t size() const { return mSortedRows.size(); }
  95     size_t indexForRow(SCROW row) const
  96     {
  97         assert(row >= maRange.aStart.Row() && row <= maRange.aEnd.Row());
  98         assert(mRowToIndex[row - maRange.aStart.Row()] != mSortedRows.max_size());
  99         return mRowToIndex[row - maRange.aStart.Row()];
 100     }
 101     SCROW rowForIndex(size_t index) const { return mSortedRows[index]; }
 102
 103 private:
 104     // Rows sorted by their value.
 105     std::vector<SCROW> mSortedRows;
 106     std::vector<size_t> mRowToIndex; // indexed by 'SCROW - maRange.aStart.Row()'
 107     ScRange maRange;
 108     ScDocument* mpDoc;
 109     bool mValid;
 110     ValueType mValueType;
 111     ScQueryOp mQueryOp;
 112     ScQueryEntry::QueryType mQueryType;
 113
 114     ScSortedRangeCache(const ScSortedRangeCache&) = delete;
 115     ScSortedRangeCache& operator=(const ScSortedRangeCache&) = delete;
 116 };
 117
 118 // Struct because including lookupcache.hxx in document.hxx isn't wanted.
 119 struct ScSortedRangeCacheMap
 120 {
 121     std::unordered_map<ScSortedRangeCache::HashKey, std::unique_ptr<ScSortedRangeCache>,
 122                        ScSortedRangeCache::Hash>
 123         aCacheMap;
 124 };
 125
 126 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */