sc/inc/compressedarray.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 <cstddef>
  23 #include <memory>
  24
  25 #include "scdllapi.h"
  26
  27 /** Compressed array of row (or column) entries, e.g. heights, flags, ...
  28
  29     The array stores ranges of values such that equal consecutive values occupy only
  30     one entry. Initially it consists of one DataEntry with an implied start
  31     row/column of 0 and an end row/column of access type maximum value.
  32
  33     typename A := access type, e.g. SCROW or SCCOL, must be a POD.
  34
  35     typename D := data type, e.g. sal_uInt16 or sal_uInt8 or whatever, may also be a
  36     struct or class.
  37
  38     D::operator==() and D::operator=() must be implemented. Force template
  39     instantiation for a specific type in source/core/data/compressedarray.cxx
  40
  41     TODO: Currently the allocated memory never shrinks, must manually invoke
  42     Resize() if needed.
  43  */
  44
  45 template< typename A, typename D > class ScCompressedArray
  46 {
  47 public:
  48     class Iterator
  49     {
  50         friend ScCompressedArray;
  51         const ScCompressedArray& mrArray;
  52         size_t             mnIndex = 0;
  53         A                  mnRegion = 0;
  54         Iterator(const ScCompressedArray& rArray) : mrArray(rArray) {}
  55         Iterator(const ScCompressedArray& rArray, size_t nIndex, A nRegion) : mrArray(rArray), mnIndex(nIndex), mnRegion(nRegion) {}
  56     public:
  57         void operator++();
  58         Iterator operator+(size_t) const;
  59         const D & operator*() const { return mrArray.pData[mnIndex].aValue; }
  60     };
  61     struct DataEntry
  62     {
  63         A   nEnd;           // start is end of previous entry + 1
  64         D   aValue;
  65     };
  66     struct RangeData
  67     {
  68         A mnRow1, mnRow2;
  69         D maValue;
  70     };
  71
  72     /** Construct with nMaxAccess=MAXROW, for example. */
  73                                 ScCompressedArray( A nMaxAccess,
  74                                         const D& rValue );
  75     virtual                     ~ScCompressedArray();
  76     void                        Reset( const D& rValue );
  77     void                        SetValue( A nPos, const D& rValue );
  78     void                        SetValue( A nStart, A nEnd, const D& rValue );
  79     [[nodiscard]]
  80     const D&                    GetValue( A nPos ) const;
  81     [[nodiscard]]
  82     A                           GetLastPos() const { return pData[nCount-1].nEnd; }
  83
  84     /** Get value for a row, and it's region end row */
  85     [[nodiscard]]
  86     const D&                    GetValue( A nPos, size_t& nIndex, A& nEnd ) const;
  87
  88     /** Get range data for a row, i.e. value and start and end rows with that value */
  89     [[nodiscard]]
  90     RangeData                   GetRangeData( A nPos ) const;
  91
  92     /** Get next value and it's region end row. If nIndex<nCount, nIndex is
  93         incremented first. If the resulting nIndex>=nCount, the value of the
  94         last entry is returned again. */
  95     [[nodiscard]]
  96     const D&                    GetNextValue( size_t& nIndex, A& nEnd ) const;
  97
  98     /** Insert rows before nStart and copy value for inserted rows from
  99         nStart-1, return that value. */
 100     const D&                    Insert( A nStart, size_t nCount );
 101     void                        InsertPreservingSize( A nStart, size_t nCount, const D& rFillValue );
 102
 103     void                        Remove( A nStart, size_t nCount );
 104     void                        RemovePreservingSize( A nStart, size_t nCount, const D& rFillValue );
 105
 106     /** Copy rArray.nStart+nSourceDy to this.nStart */
 107     void                        CopyFrom( const ScCompressedArray& rArray,
 108                                     A nStart, A nEnd )
 109                                 { CopyFrom(rArray, nStart, nEnd, nStart); }
 110     void                        CopyFrom( const ScCompressedArray& rArray,
 111                                     A nDestStart, A nDestEnd, A nSrcStart );
 112
 113     // methods public for the coupled array sum methods
 114     /** Obtain index into entries for nPos */
 115     SC_DLLPUBLIC size_t                      Search( A nPos ) const;
 116
 117     Iterator                    begin() const { return Iterator(*this); }
 118
 119 protected:
 120     size_t                      nCount;
 121     size_t                      nLimit;
 122     std::unique_ptr<DataEntry[]> pData;
 123     A                           nMaxAccess;
 124 };
 125
 126 template< typename A, typename D >
 127 void ScCompressedArray<A,D>::Reset( const D& rValue )
 128 {
 129     // Create a temporary copy in case we got a reference passed that points to
 130     // a part of the array to be reallocated.
 131     D aTmpVal( rValue);
 132     nCount = nLimit = 1;
 133     pData.reset(new DataEntry[1]);
 134     pData[0].aValue = aTmpVal;
 135     pData[0].nEnd = nMaxAccess;
 136 }
 137
 138 template< typename A, typename D >
 139 void ScCompressedArray<A,D>::SetValue( A nPos, const D& rValue )
 140 {
 141     SetValue( nPos, nPos, rValue);
 142 }
 143
 144 template< typename A, typename D >
 145 const D& ScCompressedArray<A,D>::GetValue( A nPos ) const
 146 {
 147     size_t nIndex = Search( nPos);
 148     return pData[nIndex].aValue;
 149 }
 150
 151 template< typename A, typename D >
 152 const D& ScCompressedArray<A,D>::GetValue( A nPos, size_t& nIndex, A& nEnd ) const
 153 {
 154     nIndex = Search( nPos);
 155     nEnd = pData[nIndex].nEnd;
 156     return pData[nIndex].aValue;
 157 }
 158
 159 template< typename A, typename D >
 160 typename ScCompressedArray<A,D>::RangeData ScCompressedArray<A,D>::GetRangeData( A nPos ) const
 161 {
 162     size_t nIndex = Search( nPos);
 163     RangeData aData;
 164     aData.mnRow1 = nIndex == 0 ? 0 : pData[nIndex - 1].nEnd + 1;
 165     aData.mnRow2 = pData[nIndex].nEnd;
 166     aData.maValue = pData[nIndex].aValue;
 167     return aData;
 168 }
 169
 170 template< typename A, typename D >
 171 const D& ScCompressedArray<A,D>::GetNextValue( size_t& nIndex, A& nEnd ) const
 172 {
 173     if (nIndex < nCount)
 174         ++nIndex;
 175     size_t nEntry = (nIndex < nCount ? nIndex : nCount-1);
 176     nEnd = pData[nEntry].nEnd;
 177     return pData[nEntry].aValue;
 178 }
 179
 180 //  ScBitMaskCompressedArray
 181 /** The data type represents bits, manageable by bitwise operations.
 182  */
 183
 184 template< typename A, typename D > class ScBitMaskCompressedArray final : public ScCompressedArray<A,D>
 185 {
 186 public:
 187                                 ScBitMaskCompressedArray( A nMaxAccessP,
 188                                         const D& rValue )
 189                                     : ScCompressedArray<A,D>( nMaxAccessP, rValue )
 190                                     {}
 191     void                        AndValue( A nPos, const D& rValueToAnd );
 192     void                        OrValue( A nPos, const D& rValueToOr );
 193     void                        AndValue( A nStart, A nEnd, const D& rValueToAnd );
 194     void                        OrValue( A nStart, A nEnd, const D& rValueToOr );
 195
 196     /** Copy values from rArray and bitwise AND them with rValueToAnd. */
 197     void                        CopyFromAnded(
 198                                     const ScBitMaskCompressedArray& rArray,
 199                                     A nStart, A nEnd, const D& rValueToAnd );
 200
 201     /** Return the last row where an entry meets the condition:
 202         ((aValue & rBitMask) != 0), start searching at 0. If no entry
 203         meets this condition, ::std::numeric_limits<A>::max() is returned. */
 204     A                           GetLastAnyBitAccess( const D& rBitMask ) const;
 205 };
 206
 207 template< typename A, typename D >
 208 void ScBitMaskCompressedArray<A,D>::AndValue( A nPos, const D& rValueToAnd )
 209 {
 210     const D& rValue = this->GetValue( nPos);
 211     if ((rValue & rValueToAnd) != rValue)
 212         this->SetValue( nPos, rValue & rValueToAnd);
 213 }
 214
 215 template< typename A, typename D >
 216 void ScBitMaskCompressedArray<A,D>::OrValue( A nPos, const D& rValueToOr )
 217 {
 218     const D& rValue = this->GetValue( nPos);
 219     if ((rValue | rValueToOr) != rValue)
 220         this->SetValue( nPos, rValue | rValueToOr);
 221 }
 222
 223 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */