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