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     void                        Reset( const D& rValue );
  76     void                        SetValue( A nPos, const D& rValue );
  77     void                        SetValue( A nStart, A nEnd, const D& rValue );
  78     [[nodiscard]]
  79     const D&                    GetValue( A nPos ) const;
  80     [[nodiscard]]
  81     A                           GetLastPos() const { return pData[nCount-1].nEnd; }
  82
  83     /** Get value for a row, and it's region end row */
  84     [[nodiscard]]
  85     const D&                    GetValue( A nPos, size_t& nIndex, A& nEnd ) const;
  86
  87     /** Get range data for a row, i.e. value and start and end rows with that value */
  88     [[nodiscard]]
  89     RangeData                   GetRangeData( A nPos ) const;
  90
  91     /** Get next value and it's region end row. If nIndex<nCount, nIndex is
  92         incremented first. If the resulting nIndex>=nCount, the value of the
  93         last entry is returned again. */
  94     [[nodiscard]]
  95     const D&                    GetNextValue( size_t& nIndex, A& nEnd ) const;
  96
  97     /** Insert rows before nStart and copy value for inserted rows from
  98         nStart-1, return that value. */
  99     const D&                    Insert( A nStart, size_t nCount );
 100     void                        InsertPreservingSize( A nStart, size_t nCount, const D& rFillValue );
 101
 102     void                        Remove( A nStart, size_t nCount );
 103     void                        RemovePreservingSize( A nStart, size_t nCount, const D& rFillValue );
 104
 105     /** Copy rArray.nStart+nSourceDy to this.nStart */
 106     void                        CopyFrom( const ScCompressedArray& rArray,
 107                                     A nStart, A nEnd )
 108                                 { CopyFrom(rArray, nStart, nEnd, nStart); }
 109     void                        CopyFrom( const ScCompressedArray& rArray,
 110                                     A nDestStart, A nDestEnd, A nSrcStart );
 111
 112     // methods public for the coupled array sum methods
 113     /** Obtain index into entries for nPos */
 114     SC_DLLPUBLIC size_t                      Search( A nPos ) const;
 115
 116     Iterator                    begin() const { return Iterator(*this); }
 117
 118 protected:
 119     size_t                      nCount;
 120     size_t                      nLimit;
 121     std::unique_ptr<DataEntry[]> pData;
 122     A                           nMaxAccess;
 123 };
 124
 125 template< typename A, typename D >
 126 void ScCompressedArray<A,D>::Reset( const D& rValue )
 127 {
 128     // Create a temporary copy in case we got a reference passed that points to
 129     // a part of the array to be reallocated.
 130     D aTmpVal( rValue);
 131     nCount = nLimit = 1;
 132     pData.reset(new DataEntry[1]);
 133     pData[0].aValue = aTmpVal;
 134     pData[0].nEnd = nMaxAccess;
 135 }
 136
 137 template< typename A, typename D >
 138 void ScCompressedArray<A,D>::SetValue( A nPos, const D& rValue )
 139 {
 140     SetValue( nPos, nPos, rValue);
 141 }
 142
 143 template< typename A, typename D >
 144 const D& ScCompressedArray<A,D>::GetValue( A nPos ) const
 145 {
 146     size_t nIndex = Search( nPos);
 147     return pData[nIndex].aValue;
 148 }
 149
 150 template< typename A, typename D >
 151 const D& ScCompressedArray<A,D>::GetValue( A nPos, size_t& nIndex, A& nEnd ) const
 152 {
 153     nIndex = Search( nPos);
 154     nEnd = pData[nIndex].nEnd;
 155     return pData[nIndex].aValue;
 156 }
 157
 158 template< typename A, typename D >
 159 typename ScCompressedArray<A,D>::RangeData ScCompressedArray<A,D>::GetRangeData( A nPos ) const
 160 {
 161     size_t nIndex = Search( nPos);
 162     RangeData aData;
 163     aData.mnRow1 = nIndex == 0 ? 0 : pData[nIndex - 1].nEnd + 1;
 164     aData.mnRow2 = pData[nIndex].nEnd;
 165     aData.maValue = pData[nIndex].aValue;
 166     return aData;
 167 }
 168
 169 template< typename A, typename D >
 170 const D& ScCompressedArray<A,D>::GetNextValue( size_t& nIndex, A& nEnd ) const
 171 {
 172     if (nIndex < nCount)
 173         ++nIndex;
 174     size_t nEntry = (nIndex < nCount ? nIndex : nCount-1);
 175     nEnd = pData[nEntry].nEnd;
 176     return pData[nEntry].aValue;
 177 }
 178
 179 //  ScBitMaskCompressedArray
 180 /** The data type represents bits, manageable by bitwise operations.
 181  */
 182
 183 template< typename A, typename D > class ScBitMaskCompressedArray final : public ScCompressedArray<A,D>
 184 {
 185 public:
 186                                 ScBitMaskCompressedArray( A nMaxAccessP,
 187                                         const D& rValue )
 188                                     : ScCompressedArray<A,D>( nMaxAccessP, rValue )
 189                                     {}
 190     void                        AndValue( A nPos, const D& rValueToAnd );
 191     void                        OrValue( A nPos, const D& rValueToOr );
 192     void                        AndValue( A nStart, A nEnd, const D& rValueToAnd );
 193     void                        OrValue( A nStart, A nEnd, const D& rValueToOr );
 194
 195     /** Copy values from rArray and bitwise AND them with rValueToAnd. */
 196     void                        CopyFromAnded(
 197                                     const ScBitMaskCompressedArray& rArray,
 198                                     A nStart, A nEnd, const D& rValueToAnd );
 199
 200     /** Return the last row where an entry meets the condition:
 201         ((aValue & rBitMask) != 0), start searching at 0. If no entry
 202         meets this condition, ::std::numeric_limits<A>::max() is returned. */
 203     A                           GetLastAnyBitAccess( const D& rBitMask ) const;
 204 };
 205
 206 template< typename A, typename D >
 207 void ScBitMaskCompressedArray<A,D>::AndValue( A nPos, const D& rValueToAnd )
 208 {
 209     const D& rValue = this->GetValue( nPos);
 210     if ((rValue & rValueToAnd) != rValue)
 211         this->SetValue( nPos, rValue & rValueToAnd);
 212 }
 213
 214 template< typename A, typename D >
 215 void ScBitMaskCompressedArray<A,D>::OrValue( A nPos, const D& rValueToOr )
 216 {
 217     const D& rValue = this->GetValue( nPos);
 218     if ((rValue | rValueToOr) != rValue)
 219         this->SetValue( nPos, rValue | rValueToOr);
 220 }
 221
 222 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */