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