diff options
| -rw-r--r-- | include/svl/nranges.hxx | 22 | ||||
| -rw-r--r-- | svl/source/items/itemset.cxx | 56 | ||||
| -rw-r--r-- | svl/source/items/nranges.cxx | 250 |
3 files changed, 52 insertions, 276 deletions
diff --git a/include/svl/nranges.hxx b/include/svl/nranges.hxx index d3744755b823..d9329d1007f1 100644 --- a/include/svl/nranges.hxx +++ b/include/svl/nranges.hxx @@ -22,28 +22,6 @@ #include <cstdarg> #include <sal/types.h> -class SfxUShortRanges -{ - sal_uInt16* _pRanges; // 0-terminated array of sal_uInt16-pairs - -public: - SfxUShortRanges( const SfxUShortRanges &rOrig ); - SfxUShortRanges( sal_uInt16 nWhich1, sal_uInt16 nWhich2 ); - SfxUShortRanges( const sal_uInt16* nNumTable ); - ~SfxUShortRanges() - { delete [] _pRanges; } - - SfxUShortRanges& operator = ( const SfxUShortRanges & ); - - SfxUShortRanges& operator += ( const SfxUShortRanges & ); - - bool IsEmpty() const - { return !_pRanges || 0 == *_pRanges; } - - operator const sal_uInt16* () const - { return _pRanges; } -}; - /** * Creates a sal_uInt16-ranges-array in 'rpRanges' using 'nWh1' and 'nWh2' as * first range, 'nNull' as terminator or start of 2nd range and 'pArgs' as diff --git a/svl/source/items/itemset.cxx b/svl/source/items/itemset.cxx index c10430514061..745d96a86c67 100644 --- a/svl/source/items/itemset.cxx +++ b/svl/source/items/itemset.cxx @@ -593,10 +593,58 @@ void SfxItemSet::MergeRange( sal_uInt16 nFrom, sal_uInt16 nTo ) if ( nFrom == nTo && ( eItemState == SfxItemState::DEFAULT || eItemState == SfxItemState::SET ) ) return; - // merge new range - SfxUShortRanges aRanges( m_pWhichRanges ); - aRanges += SfxUShortRanges( nFrom, nTo ); - SetRanges( aRanges ); +#ifdef DBG_UTIL + assert(nFrom <= nTo); + for (const sal_uInt16 *pRange = m_pWhichRanges; *pRange; pRange += 2) + { + assert(pRange[0] <= pRange[1]); + // ranges must be sorted and discrete + assert(!pRange[2] || (pRange[2] - pRange[1]) > 1); + } +#endif + + // create vector of ranges (sal_uInt16 pairs of lower and upper bound) + const size_t nOldCount = Count_Impl(m_pWhichRanges); + std::vector<std::pair<sal_uInt16, sal_uInt16>> aRangesTable; + aRangesTable.reserve(nOldCount/2 + 1); + bool bAdded = false; + for (size_t i = 0; i < nOldCount; i += 2) + { + if (!bAdded && m_pWhichRanges[i] >= nFrom) + { // insert new range, keep ranges sorted + aRangesTable.emplace_back(std::pair<sal_uInt16, sal_uInt16>(nFrom, nTo)); + bAdded = true; + } + // insert current range + aRangesTable.emplace_back(std::pair<sal_uInt16, sal_uInt16>(m_pWhichRanges[i], m_pWhichRanges[i+1])); + } + if (!bAdded) + aRangesTable.emplace_back(std::pair<sal_uInt16, sal_uInt16>(nFrom, nTo)); + + // true if ranges overlap or adjoin, false if ranges are separate + auto needMerge = [](std::pair<sal_uInt16, sal_uInt16> lhs, std::pair<sal_uInt16, sal_uInt16> rhs) + {return (lhs.first-1) <= rhs.second && (rhs.first-1) <= lhs.second;}; + + std::vector<std::pair<sal_uInt16, sal_uInt16> >::iterator it = aRangesTable.begin(); + // check neighbouring ranges, find first range which overlaps or adjoins a previous range + while ((it = std::is_sorted_until(it, aRangesTable.end(), needMerge)) != aRangesTable.end()) + { + --it; // merge with previous range + // lower bounds are sorted, implies: it->first = min(it[0].first, it[1].first) + it->second = std::max(it[0].second, it[1].second); + aRangesTable.erase(std::next(it)); + } + + // construct range array + const size_t nNewSize = 2 * aRangesTable.size() + 1; + std::vector<sal_uInt16> aRanges(nNewSize); + for (size_t i = 0; i < (nNewSize - 1); i +=2) + std::tie(aRanges[i], aRanges[i+1]) = aRangesTable[i/2]; + + // null terminate to be compatible with sal_uInt16* array pointers + aRanges.back() = 0; + + SetRanges( aRanges.data() ); } /** diff --git a/svl/source/items/nranges.cxx b/svl/source/items/nranges.cxx index 85ed671e9122..9dfb87675ee0 100644 --- a/svl/source/items/nranges.cxx +++ b/svl/source/items/nranges.cxx @@ -19,35 +19,10 @@ #include <svl/nranges.hxx> #include <cassert> -#include <cstring> #include <vector> -#include <osl/diagnose.h> #include <tools/debug.hxx> -#ifdef DBG_UTIL - -#define DBG_CHECK_RANGES(sal_uInt16, pArr) \ - for ( const sal_uInt16 *pRange = pArr; *pRange; pRange += 2 ) \ - { \ - DBG_ASSERT( pRange[0] <= pRange[1], "ranges must be sorted" ); \ - DBG_ASSERT( !pRange[2] || ( pRange[2] - pRange[1] ) > 1, \ - "ranges must be sorted and discrete" ); \ - } - -#else - -#define DBG_CHECK_RANGES(sal_uInt16,pArr) - -#endif - -inline void Swap_Impl(const sal_uInt16 *& rp1, const sal_uInt16 *& rp2) -{ - const sal_uInt16 * pTemp = rp1; - rp1 = rp2; - rp2 = pTemp; -} - /** * Creates a sal_uInt16-ranges-array in 'rpRanges' using 'nWh1' and 'nWh2' as * first range, 'nNull' as terminator or start of 2nd range and 'pArgs' as @@ -127,229 +102,4 @@ sal_uInt16 Capacity_Impl( const sal_uInt16 *pRanges ) return nCount; } -/** - * Copy ctor - */ -SfxUShortRanges::SfxUShortRanges( const SfxUShortRanges &rOrig ) -{ - if ( rOrig._pRanges ) - { - sal_uInt16 nCount = Count_Impl( rOrig._pRanges ) + 1; - _pRanges = new sal_uInt16[nCount]; - memcpy( _pRanges, rOrig._pRanges, sizeof(sal_uInt16) * nCount ); - } - else - _pRanges = nullptr; -} - -/** - * Constructs a SfxUShortRanges instance from one range of sal_uInt16s. - * - * Precondition: nWhich1 <= nWhich2 - */ -SfxUShortRanges::SfxUShortRanges( sal_uInt16 nWhich1, sal_uInt16 nWhich2 ) -: _pRanges( new sal_uInt16[3] ) -{ - _pRanges[0] = nWhich1; - _pRanges[1] = nWhich2; - _pRanges[2] = 0; -} - -/** - * Constructs an SfxUShortRanges-instance from an sorted ranges of sal_uInt16s, - * terminates with on 0. - * - * Precondition: for each n >= 0 && n < (sizeof(pArr)-1) - * pArr[2n] <= pArr[2n+1] && ( pArr[2n+2]-pArr[2n+1] ) > 1 - */ -SfxUShortRanges::SfxUShortRanges( const sal_uInt16* pArr ) -{ - DBG_CHECK_RANGES(sal_uInt16, pArr); - sal_uInt16 nCount = Count_Impl(pArr) + 1; - _pRanges = new sal_uInt16[ nCount ]; - memcpy( _pRanges, pArr, sizeof(sal_uInt16) * nCount ); -} - - -/** - * Assigns ranges from 'rRanges' to '*this'. - */ -SfxUShortRanges& SfxUShortRanges::operator = -( - const SfxUShortRanges &rRanges -) -{ - // special case: assign itself - if ( &rRanges == this ) - return *this; - - delete[] _pRanges; - - // special case: 'rRanges' is empty - if ( rRanges.IsEmpty() ) - _pRanges = nullptr; - else - { - // copy ranges - sal_uInt16 nCount = Count_Impl( rRanges._pRanges ) + 1; - _pRanges = new sal_uInt16[ nCount ]; - memcpy( _pRanges, rRanges._pRanges, sizeof(sal_uInt16) * nCount ); - } - return *this; -} - -/** - * Merges *this with 'rRanges'. - * for each sal_uInt16 n: - * this->Contains( n ) || rRanges.Contains( n ) => this'->Contains( n ) - * !this->Contains( n ) && !rRanges.Contains( n ) => !this'->Contains( n ) - */ -SfxUShortRanges& SfxUShortRanges::operator += -( - const SfxUShortRanges &rRanges -) -{ - // special cases: one is empty - if ( rRanges.IsEmpty() ) - return *this; - if ( IsEmpty() ) - return *this = rRanges; - - // First, run through _pRanges and rRanges._pRanges and determine the size of - // the new, merged ranges: - sal_uInt16 nCount = 0; - const sal_uInt16 * pRA = _pRanges; - const sal_uInt16 * pRB = rRanges._pRanges; - - for (;;) - { - // The first pair of pRA has a lower lower bound than the first pair - // of pRB: - if (pRA[0] > pRB[0]) - Swap_Impl(pRA, pRB); - - // We are done with the merging if at least pRA is exhausted: - if (!pRA[0]) - break; - - for (;;) - { - // Skip those pairs in pRB that completely lie in the first pair - // of pRA: - while (pRB[1] <= pRA[1]) - { - pRB += 2; - - // Watch out for exhaustion of pRB: - if (!pRB[0]) - { - Swap_Impl(pRA, pRB); - goto count_rest; - } - } - - // If the next pair of pRA does not at least touch the current new - // pair, we are done with the current new pair: - if (pRB[0] > pRA[1] + 1) - break; - - // The next pair of pRB extends the current new pair; first, - // extend the current new pair (we are done if pRB is then - // exhausted); second, switch the roles of pRA and pRB in order to - // merge in those following pairs of the original pRA that will - // lie in the (now larger) current new pair or will even extend it - // further: - pRA += 2; - if (!pRA[0]) - goto count_rest; - Swap_Impl(pRA, pRB); - } - - // Done with the current new pair: - pRA += 2; - nCount += 2; - } - - // Only pRB has more pairs available, pRA is already exhausted: -count_rest: - for (; pRB[0]; pRB += 2) - nCount += 2; - - // Now, create new ranges of the correct size and, on a second run through - // _pRanges and rRanges._pRanges, copy the merged pairs into the new - // ranges: - sal_uInt16 * pNew = new sal_uInt16[nCount + 1]; - pRA = _pRanges; - pRB = rRanges._pRanges; - sal_uInt16 * pRN = pNew; - - for (;;) - { - // The first pair of pRA has a lower lower bound than the first pair - // of pRB: - if (pRA[0] > pRB[0]) - Swap_Impl(pRA, pRB); - - // We are done with the merging if at least pRA is exhausted: - if (!pRA[0]) - break; - - // Lower bound of current new pair is already known: - *pRN++ = pRA[0]; - - for (;;) - { - // Skip those pairs in pRB that completely lie in the first pair - // of pRA: - while (pRB[1] <= pRA[1]) - { - pRB += 2; - - // Watch out for exhaustion of pRB: - if (!pRB[0]) - { - Swap_Impl(pRA, pRB); - ++pRB; - goto copy_rest; - } - } - - // If the next pair of pRA does not at least touch the current new - // pair, we are done with the current new pair: - if (pRB[0] > pRA[1] + 1) - break; - - // The next pair of pRB extends the current new pair; first, - // extend the current new pair (we are done if pRB is then - // exhausted); second, switch the roles of pRA and pRB in order to - // merge in those following pairs of the original pRA that will - // lie in the (now larger) current new pair or will even extend it - // further: - pRA += 2; - if (!pRA[0]) - { - ++pRB; - goto copy_rest; - } - Swap_Impl(pRA, pRB); - } - - // Done with the current new pair, now upper bound is also known: - *pRN++ = pRA[1]; - pRA += 2; - } - - // Only pRB has more pairs available (which are copied to the new ranges - // unchanged), pRA is already exhausted: -copy_rest: - for (; *pRB;) - *pRN++ = *pRB++; - *pRN = 0; - - delete[] _pRanges; - _pRanges = pNew; - - return *this; -} - /* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |