/************************************************************** * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. * *************************************************************/ // MARKER(update_precomp.py): autogen include statement, do not remove #include "precompiled_svl.hxx" // compiled via include from itemset.cxx only! //======================================================================== #ifdef DBG_UTIL #define DBG_CHECK_RANGES(NUMTYPE, pArr) \ for ( const NUMTYPE *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(NUMTYPE,pArr) #endif //============================================================================ inline void Swap_Impl(const NUMTYPE *& rp1, const NUMTYPE *& rp2) { const NUMTYPE * pTemp = rp1; rp1 = rp2; rp2 = pTemp; } //======================================================================== NUMTYPE InitializeRanges_Impl( NUMTYPE *&rpRanges, va_list pArgs, NUMTYPE nWh1, NUMTYPE nWh2, NUMTYPE nNull ) /**

Description

Creates an sal_uInt16-ranges-array in 'rpRanges' using 'nWh1' and 'nWh2' as first range, 'nNull' as terminator or start of 2nd range and 'pArgs' as remaider. It returns the number of NUMTYPEs which are contained in the described set of NUMTYPEs. */ { NUMTYPE nSize = 0, nIns = 0; sal_uInt16 nCnt = 0; SvNums aNumArr( 11, 8 ); aNumArr.Insert( nWh1, nCnt++ ); aNumArr.Insert( nWh2, nCnt++ ); DBG_ASSERT( nWh1 <= nWh2, "Ungueltiger Bereich" ); nSize += nWh2 - nWh1 + 1; aNumArr.Insert( nNull, nCnt++ ); while ( 0 != ( nIns = sal::static_int_cast< NUMTYPE >( va_arg( pArgs, NUMTYPE_ARG ) ) ) ) { aNumArr.Insert( nIns, nCnt++ ); if ( 0 == (nCnt & 1) ) // 4,6,8, usw. { DBG_ASSERT( aNumArr[ nCnt-2 ] <= nIns, "Ungueltiger Bereich" ); nSize += nIns - aNumArr[ nCnt-2 ] + 1; } } va_end( pArgs ); DBG_ASSERT( 0 == (nCnt & 1), "ungerade Anzahl von Which-Paaren!" ); // so, jetzt sind alle Bereiche vorhanden und rpRanges = new NUMTYPE[ nCnt+1 ]; memcpy( rpRanges, aNumArr.GetData(), sizeof(NUMTYPE) * nCnt ); *(rpRanges+nCnt) = 0; return nSize; } //------------------------------------------------------------------------ NUMTYPE Count_Impl( const NUMTYPE *pRanges ) /**

Description

Determines the number of NUMTYPEs in an 0-terminated array of pairs of NUMTYPEs. The terminating 0 is not included in the count. */ { NUMTYPE nCount = 0; while ( *pRanges ) { nCount += 2; pRanges += 2; } return nCount; } //------------------------------------------------------------------------ NUMTYPE Capacity_Impl( const NUMTYPE *pRanges ) /**

Description

Determines the total number of NUMTYPEs described in an 0-terminated array of pairs of NUMTYPEs, each representing an range of NUMTYPEs. */ { NUMTYPE nCount = 0; if ( pRanges ) { while ( *pRanges ) { nCount += pRanges[1] - pRanges[0] + 1; pRanges += 2; } } return nCount; } //------------------------------------------------------------------------ SfxNumRanges::SfxNumRanges( const SfxNumRanges &rOrig ) /**

Description

Copy-Ctor. */ { if ( rOrig._pRanges ) { NUMTYPE nCount = Count_Impl( rOrig._pRanges ) + 1; _pRanges = new NUMTYPE[nCount]; memcpy( _pRanges, rOrig._pRanges, sizeof(NUMTYPE) * nCount ); } else _pRanges = 0; } //------------------------------------------------------------------------ SfxNumRanges::SfxNumRanges( NUMTYPE nWhich1, NUMTYPE nWhich2 ) /**

Description

Constructs an SfxNumRanges-instance from one range of NUMTYPEs. precondition: nWhich1 <= nWhich2 */ : _pRanges( new NUMTYPE[3] ) { _pRanges[0] = nWhich1; _pRanges[1] = nWhich2; _pRanges[2] = 0; } //------------------------------------------------------------------------ SfxNumRanges::SfxNumRanges( NUMTYPE_ARG nWh0, NUMTYPE_ARG nWh1, NUMTYPE_ARG nNull, ... ) /**

Description

Constructs an SfxNumRanges-instance from more than one sorted ranges of NUMTYPEs terminated with one 0. precondition: for each n >= 0 && n < nArgs nWh(2n) <= nWh(2n+1) && ( nWh(2n+2)-nWh(2n+1) ) > 1 */ { va_list pArgs; va_start( pArgs, nNull ); InitializeRanges_Impl( _pRanges, pArgs, sal::static_int_cast< NUMTYPE >(nWh0), sal::static_int_cast< NUMTYPE >(nWh1), sal::static_int_cast< NUMTYPE >(nNull)); DBG_CHECK_RANGES(NUMTYPE, _pRanges); } //------------------------------------------------------------------------ SfxNumRanges::SfxNumRanges( const NUMTYPE* pArr ) /**

Description

Constcurts an SfxNumRanges-instance from an sorted ranges of NUMTYPEs, 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 */ { DBG_CHECK_RANGES(NUMTYPE, pArr); NUMTYPE nCount = Count_Impl(pArr) + 1; _pRanges = new NUMTYPE[ nCount ]; memcpy( _pRanges, pArr, sizeof(NUMTYPE) * nCount ); } //------------------------------------------------------------------------ sal_Bool SfxNumRanges::operator==( const SfxNumRanges &rOther ) const { // Object pointers equal? if ( this == &rOther ) return sal_True; // Ranges pointers equal? if ( _pRanges == rOther._pRanges ) return sal_True; // Counts equal? NUMTYPE nCount = Count(); if ( nCount != rOther.Count() ) return sal_False; // Check arrays. NUMTYPE n = 0; while( _pRanges[ n ] != 0 ) { // Elements at current position equal? if ( _pRanges[ n ] != rOther._pRanges[ n ] ) return sal_False; ++n; } return sal_True; } //------------------------------------------------------------------------ SfxNumRanges& SfxNumRanges::operator = ( const SfxNumRanges &rRanges ) /**

Description

Assigns ranges from 'rRanges' to '*this'. */ { // special case: assign itself if ( &rRanges == this ) return *this; delete[] _pRanges; // special case: 'rRanges' is empty if ( rRanges.IsEmpty() ) _pRanges = 0; else { // copy ranges NUMTYPE nCount = Count_Impl( rRanges._pRanges ) + 1; _pRanges = new NUMTYPE[ nCount ]; memcpy( _pRanges, rRanges._pRanges, sizeof(NUMTYPE) * nCount ); } return *this; } //------------------------------------------------------------------------ SfxNumRanges& SfxNumRanges::operator += ( const SfxNumRanges &rRanges ) /**

Description

Merges *this with 'rRanges'. for each NUMTYPE n: this->Contains( n ) || rRanges.Contains( n ) => this'->Contains( n ) !this->Contains( n ) && !rRanges.Contains( n ) => !this'->Contains( n ) */ { // special cases: one is empty if ( rRanges.IsEmpty() ) return *this; if ( IsEmpty() ) return *this = rRanges; // First, run thru _pRanges and rRanges._pRanges and determine the size of // the new, merged ranges: NUMTYPE nCount = 0; const NUMTYPE * pRA = _pRanges; const NUMTYPE * 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 thru // _pRanges and rRanges._pRanges, copy the merged pairs into the new // ranges: NUMTYPE * pNew = new NUMTYPE[nCount + 1]; pRA = _pRanges; pRB = rRanges._pRanges; NUMTYPE * 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; } //------------------------------------------------------------------------ SfxNumRanges& SfxNumRanges::operator -= ( const SfxNumRanges &rRanges ) /**

Description

Removes 'rRanges' from '*this'. for each NUMTYPE n: this->Contains( n ) && rRanges.Contains( n ) => !this'->Contains( n ) this->Contains( n ) && !rRanges.Contains( n ) => this'->Contains( n ) !this->Contains( n ) => !this'->Contains( n ) */ { // special cases: one is empty if ( rRanges.IsEmpty() || IsEmpty() ) return *this; // differentiate 'rRanges' in a temporary copy of '*this' // (size is computed for maximal possibly split-count plus terminating 0) NUMTYPE nThisSize = Count_Impl(_pRanges); NUMTYPE nTargetSize = 1 + ( nThisSize + Count_Impl(rRanges._pRanges) ); NUMTYPE *pTarget = new NUMTYPE[ nTargetSize ]; memset( pTarget, 0, sizeof(NUMTYPE)*nTargetSize ); memcpy( pTarget, _pRanges, sizeof(NUMTYPE)*nThisSize ); NUMTYPE nPos1 = 0, nPos2 = 0, nTargetPos = 0; while( _pRanges[ nPos1 ] ) { NUMTYPE l1 = _pRanges[ nPos1 ]; // lower bound of interval 1 NUMTYPE u1 = _pRanges[ nPos1+1 ]; // upper bound of interval 1 NUMTYPE l2 = rRanges._pRanges[ nPos2 ]; // lower bound of interval 2 NUMTYPE u2 = rRanges._pRanges[ nPos2+1 ]; // upper bound of interval 2 // boundary cases // * subtrahend is empty -> copy the minuend if( !l2 ) { pTarget[ nTargetPos ] = l1; pTarget[ nTargetPos+1 ] = u1; nTargetPos += 2; nPos1 += 2; continue; } // * next subtrahend interval is completely higher -> copy the minuend if( u1 < l2 ) { pTarget[ nTargetPos ] = l1; pTarget[ nTargetPos+1 ] = u1; nTargetPos += 2; nPos1 += 2; continue; } // * next subtrahend interval is completely lower -> try next if( u2 < l1 ) { nPos2 += 2; continue; } // intersecting cases // * subtrahend cuts out from the beginning of the minuend if( l2 <= l1 && u2 <= u1 ) { // reduce minuend interval, try again (minuend might be affected by other subtrahend intervals) _pRanges[ nPos1 ] = u2 + 1; nPos2 += 2; // this cannot hurt any longer continue; } // * subtrahend cuts out from the end of the minuend if( l1 <= l2 && u1 <= u2 ) { // copy remaining part of minuend (cannot be affected by other intervals) if( l1 < l2 ) // anything left at all? { pTarget[ nTargetPos ] = l1; pTarget[ nTargetPos+1 ] = l2 - 1; nTargetPos += 2; // do not increment nPos2, might affect next minuend interval, too } nPos1 += 2; // nothing left at all continue; } // * subtrahend completely deletes minuend (larger or same at both ends) if( l1 >= l2 && u1 <= u2 ) { nPos1 += 2; // minuend deleted // do not increment nPos2, might affect next minuend interval, too continue; } // * subtrahend divides minuend into two pieces if( l1 <= l2 && u1 >= u2 ) // >= and <= since they may be something left only at one side { // left side if( l1 < l2 ) // anything left at all { pTarget[ nTargetPos ] = l1; pTarget[ nTargetPos+1 ] = l2 - 1; nTargetPos += 2; } // right side if( u1 > u2 ) // anything left at all { // reduce minuend interval, try again (minuend might be affected by other subtrahend itnervals ) _pRanges[ nPos1 ] = u2 + 1; } // subtrahend is completely used nPos2 += 2; continue; } // we should never be here DBG_ERROR( "SfxNumRanges::operator-=: internal error" ); } // while pTarget[ nTargetPos ] = 0; // assign the differentiated ranges delete[] _pRanges; NUMTYPE nUShorts = Count_Impl(pTarget) + 1; if ( 1 != nUShorts ) { _pRanges = new NUMTYPE[ nUShorts ]; memcpy( _pRanges, pTarget, nUShorts * sizeof(NUMTYPE) ); } else _pRanges = 0; delete [] pTarget; return *this; /* untested code from MI commented out (MDA, 28.01.97) do { // 1st range is smaller than 2nd range? if ( pRange1[1] < pRange2[0] ) // => keep 1st range pRange1 += 2; // 2nd range is smaller than 1st range? else if ( pRange2[1] < pRange1[0] ) // => skip 2nd range pRange2 += 2; // 2nd range totally overlaps the 1st range? else if ( pRange2[0] <= pRange1[0] && pRange2[1] >= pRange1[1] ) // => remove 1st range memmove( pRange1, pRange1+2, sizeof(NUMTYPE) * (pEndOfTarget-pRange1+2) ); // 2nd range overlaps only the beginning of 1st range? else if ( pRange2[0] <= pRange1[0] && pRange2[1] < pRange1[1] ) { // => cut the beginning of 1st range and goto next 2nd range pRange1[0] = pRange2[1] + 1; pRange2 += 2; } // 2nd range overlaps only the end of 1st range? else if ( pRange2[0] > pRange1[0] && pRange2[1] >= pRange1[0] ) // => cut the beginning of 1st range pRange1[0] = pRange2[1]+1; // 2nd range is a real subset of 1st range else { // => split 1st range and goto next 2nd range memmove( pRange1+3, pRange1+1, sizeof(NUMTYPE) * (pEndOfTarget-pRange1-1) ); pRange1[1] = pRange2[0] - 1; pRange1[2] = pRange2[1] + 1; pRange1 += 2; pRange2 += 2; } } while ( *pRange1 && *pRange2 ); // assign the differentiated ranges delete[] _pRanges; NUMTYPE nUShorts = Count_Impl(pTarget) + 1; if ( 1 != nUShorts ) { _pRanges = new NUMTYPE[ nUShorts ]; memcpy( _pRanges, pTarget, nUShorts * sizeof(NUMTYPE) ); _pRanges[ nUShorts-1 ] = 0; } else _pRanges = 0; return *this; */ } //------------------------------------------------------------------------ SfxNumRanges& SfxNumRanges::operator /= ( const SfxNumRanges &rRanges ) /**

Description

Determines intersection of '*this' with 'rRanges'. for each NUMTYPE n: this->Contains( n ) && rRanges.Contains( n ) => this'->Contains( n ) !this->Contains( n ) => !this'->Contains( n ) !rRanges.Contains( n ) => !this'->Contains( n ) */ { // boundary cases // * first set is empty -> nothing to be done // * second set is empty -> delete first set if( rRanges.IsEmpty() ) { delete[] _pRanges; _pRanges = new NUMTYPE[1]; _pRanges[0] = 0; return *this; } // intersect 'rRanges' in a temporary copy of '*this' // (size is computed for maximal possibly split-count plus terminating 0) NUMTYPE nThisSize = Count_Impl(_pRanges); NUMTYPE nTargetSize = 1 + ( nThisSize + Count_Impl(rRanges._pRanges) ); NUMTYPE *pTarget = new NUMTYPE[ nTargetSize ]; memset( pTarget, 0, sizeof(NUMTYPE)*nTargetSize ); memcpy( pTarget, _pRanges, sizeof(NUMTYPE)*nThisSize ); NUMTYPE nPos1 = 0, nPos2 = 0, nTargetPos = 0; while( _pRanges[ nPos1 ] != 0 && rRanges._pRanges[ nPos2 ] != 0 ) { NUMTYPE l1 = _pRanges[ nPos1 ]; // lower bound of interval 1 NUMTYPE u1 = _pRanges[ nPos1+1 ]; // upper bound of interval 1 NUMTYPE l2 = rRanges._pRanges[ nPos2 ]; // lower bound of interval 2 NUMTYPE u2 = rRanges._pRanges[ nPos2+1 ]; // upper bound of interval 2 if( u1 < l2 ) { // current interval in s1 is completely before ci in s2 nPos1 += 2; continue; } if( u2 < l1 ) { // ci in s2 is completely before ci in s1 nPos2 += 2; continue; } // assert: there exists an intersection between ci1 and ci2 if( l1 <= l2 ) { // c1 "is more to the left" than c2 if( u1 <= u2 ) { pTarget[ nTargetPos ] = l2; pTarget[ nTargetPos+1 ] = u1; nTargetPos += 2; nPos1 += 2; continue; } else { pTarget[ nTargetPos ] = l2; pTarget[ nTargetPos+1 ] = u2; nTargetPos += 2; nPos2 += 2; } } else { // c2 "is more to the left" than c1" if( u1 > u2 ) { pTarget[ nTargetPos ] = l1; pTarget[ nTargetPos+1 ] = u2; nTargetPos += 2; nPos2 += 2; } else { pTarget[ nTargetPos ] = l1; pTarget[ nTargetPos+1 ] = u1; nTargetPos += 2; nPos1 += 2; } } }; // while pTarget[ nTargetPos ] = 0; // assign the intersected ranges delete[] _pRanges; NUMTYPE nUShorts = Count_Impl(pTarget) + 1; if ( 1 != nUShorts ) { _pRanges = new NUMTYPE[ nUShorts ]; memcpy( _pRanges, pTarget, nUShorts * sizeof(NUMTYPE) ); } else _pRanges = 0; delete [] pTarget; return *this; } //------------------------------------------------------------------------ sal_Bool SfxNumRanges::Intersects( const SfxNumRanges &rRanges ) const /**

Description

Determines if at least one range in 'rRanges' intersects with one range in '*this'. sal_True, if there is at least one with: this->Contains( n ) && rRanges.Contains( n ) */ { // special cases: one is empty if ( rRanges.IsEmpty() || IsEmpty() ) return sal_False; // find at least one intersecting range const NUMTYPE *pRange1 = _pRanges; const NUMTYPE *pRange2 = rRanges._pRanges; do { // 1st range is smaller than 2nd range? if ( pRange1[1] < pRange2[0] ) // => keep 1st range pRange1 += 2; // 2nd range is smaller than 1st range? else if ( pRange2[1] < pRange1[0] ) // => skip 2nd range pRange2 += 2; // the ranges are overlappung else return sal_True; } while ( *pRange2 ); // no intersection found return sal_False; } //------------------------------------------------------------------------ NUMTYPE SfxNumRanges::Count() const /**

Description

Determines the number of USHORTs in the set described by the ranges of USHORTs in '*this'. */ { return Capacity_Impl( _pRanges ); } //------------------------------------------------------------------------ sal_Bool SfxNumRanges::Contains( NUMTYPE n ) const /**

Description

Determines if '*this' contains 'n'. */ { for ( NUMTYPE *pRange = _pRanges; *pRange && *pRange <= n; pRange += 2 ) if ( pRange[0] <= n && n <= pRange[1] ) return sal_True; return sal_False; }