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 #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     // methods public for the coupled array sum methods
  91     /** Obtain index into entries for nPos */
  92     SC_DLLPUBLIC size_t                      Search( A nPos ) const;
  93
  94 protected:
  95     size_t                      nCount;
  96     size_t                      nLimit;
  97     size_t                      nDelta;
  98     DataEntry*                  pData;
  99     A                           nMaxAccess;
 100 };
 101
 102 template< typename A, typename D >
 103 void ScCompressedArray<A,D>::Reset( const D& rValue )
 104 {
 105     // Create a temporary copy in case we got a reference passed that points to
 106     // a part of the array to be reallocated.
 107     D aTmpVal( rValue);
 108     delete[] pData;
 109     nCount = nLimit = 1;
 110     pData = new DataEntry[1];
 111     pData[0].aValue = aTmpVal;
 112     pData[0].nEnd = nMaxAccess;
 113 }
 114
 115 template< typename A, typename D >
 116 void ScCompressedArray<A,D>::SetValue( A nPos, const D& rValue )
 117 {
 118     SetValue( nPos, nPos, rValue);
 119 }
 120
 121 template< typename A, typename D >
 122 const D& ScCompressedArray<A,D>::GetValue( A nPos ) const
 123 {
 124     size_t nIndex = Search( nPos);
 125     return pData[nIndex].aValue;
 126 }
 127
 128 template< typename A, typename D >
 129 const D& ScCompressedArray<A,D>::GetValue( A nPos, size_t& nIndex, A& nEnd ) const
 130 {
 131     nIndex = Search( nPos);
 132     nEnd = pData[nIndex].nEnd;
 133     return pData[nIndex].aValue;
 134 }
 135
 136 template< typename A, typename D >
 137 const D& ScCompressedArray<A,D>::GetNextValue( size_t& nIndex, A& nEnd ) const
 138 {
 139     if (nIndex < nCount)
 140         ++nIndex;
 141     size_t nEntry = (nIndex < nCount ? nIndex : nCount-1);
 142     nEnd = pData[nEntry].nEnd;
 143     return pData[nEntry].aValue;
 144 }
 145
 146 //  ScBitMaskCompressedArray
 147 /** The data type represents bits, managable by bitwise operations.
 148  */
 149
 150 template< typename A, typename D > class ScBitMaskCompressedArray : public ScCompressedArray<A,D>
 151 {
 152 public:
 153                                 ScBitMaskCompressedArray( A nMaxAccessP,
 154                                         const D& rValue,
 155                                         size_t nDeltaP = nScCompressedArrayDelta )
 156                                     : ScCompressedArray<A,D>( nMaxAccessP, rValue, nDeltaP)
 157                                     {}
 158                                 ScBitMaskCompressedArray( A nMaxAccessP,
 159                                         const D* pDataArray, size_t nDataCount )
 160                                     : ScCompressedArray<A,D>( nMaxAccessP,
 161                                             pDataArray, nDataCount)
 162                                     {}
 163     void                        AndValue( A nPos, const D& rValueToAnd );
 164     void                        OrValue( A nPos, const D& rValueToOr );
 165     void                        AndValue( A nStart, A nEnd, const D& rValueToAnd );
 166     void                        OrValue( A nStart, A nEnd, const D& rValueToOr );
 167
 168     /** Copy values from rArray and bitwise AND them with rValueToAnd. */
 169     void                        CopyFromAnded(
 170                                     const ScBitMaskCompressedArray& rArray,
 171                                     A nStart, A nEnd, const D& rValueToAnd,
 172                                     long nSourceDy = 0 );
 173
 174     /** Return the last row where an entry meets the condition:
 175         ((aValue & rBitMask) != 0), start searching at nStart. If no entry
 176         meets this condition, ::std::numeric_limits<A>::max() is returned. */
 177     A                           GetLastAnyBitAccess( A nStart,
 178                                     const D& rBitMask ) const;
 179 };
 180
 181 template< typename A, typename D >
 182 void ScBitMaskCompressedArray<A,D>::AndValue( A nPos, const D& rValueToAnd )
 183 {
 184     const D& rValue = this->GetValue( nPos);
 185     if ((rValue & rValueToAnd) != rValue)
 186         this->SetValue( nPos, rValue & rValueToAnd);
 187 }
 188
 189 template< typename A, typename D >
 190 void ScBitMaskCompressedArray<A,D>::OrValue( A nPos, const D& rValueToOr )
 191 {
 192     const D& rValue = this->GetValue( nPos);
 193     if ((rValue | rValueToOr) != rValue)
 194         this->SetValue( nPos, rValue | rValueToOr);
 195 }
 196
 197 #endif // INCLUDED_SC_INC_COMPRESSEDARRAY_HXX
 198
 199 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */