svtools/source/items1/nranges.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: nranges.cxx,v $
  10  * $Revision: 1.7 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_svtools.hxx"
  33
  34 // compiled via include from itemset.cxx only!
  35
  36 //========================================================================
  37
  38 #ifdef DBG_UTIL
  39
  40 #define DBG_CHECK_RANGES(NUMTYPE, pArr)                                                                 \
  41     for ( const NUMTYPE *pRange = pArr; *pRange; pRange += 2 )          \
  42     {                                                                   \
  43         DBG_ASSERT( pRange[0] <= pRange[1], "ranges must be sorted" );  \
  44         DBG_ASSERT( !pRange[2] || ( pRange[2] - pRange[1] ) > 1,        \
  45                     "ranges must be sorted and discrete" );             \
  46     }
  47
  48 #else
  49
  50 #define DBG_CHECK_RANGES(NUMTYPE,pArr)
  51
  52 #endif
  53
  54 //============================================================================
  55 inline void Swap_Impl(const NUMTYPE *& rp1, const NUMTYPE *& rp2)
  56 {
  57     const NUMTYPE * pTemp = rp1;
  58     rp1 = rp2;
  59     rp2 = pTemp;
  60 }
  61
  62 //========================================================================
  63
  64 NUMTYPE InitializeRanges_Impl( NUMTYPE *&rpRanges, va_list pArgs,
  65                                NUMTYPE nWh1, NUMTYPE nWh2, NUMTYPE nNull )
  66
  67 /**     <H3>Description</H3>
  68
  69     Creates an USHORT-ranges-array in 'rpRanges' using 'nWh1' and 'nWh2' as
  70     first range, 'nNull' as terminator or start of 2nd range and 'pArgs' as
  71     remaider.
  72
  73     It returns the number of NUMTYPEs which are contained in the described
  74     set of NUMTYPEs.
  75 */
  76
  77 {
  78     NUMTYPE nSize = 0, nIns = 0;
  79     USHORT nCnt = 0;
  80     SvNums aNumArr( 11, 8 );
  81     aNumArr.Insert( nWh1, nCnt++ );
  82     aNumArr.Insert( nWh2, nCnt++ );
  83     DBG_ASSERT( nWh1 <= nWh2, "Ungueltiger Bereich" );
  84     nSize += nWh2 - nWh1 + 1;
  85     aNumArr.Insert( nNull, nCnt++ );
  86     while ( 0 !=
  87             ( nIns =
  88               sal::static_int_cast< NUMTYPE >(
  89                   va_arg( pArgs, NUMTYPE_ARG ) ) ) )
  90     {
  91         aNumArr.Insert( nIns, nCnt++ );
  92         if ( 0 == (nCnt & 1) )           // 4,6,8, usw.
  93         {
  94             DBG_ASSERT( aNumArr[ nCnt-2 ] <= nIns, "Ungueltiger Bereich" );
  95             nSize += nIns - aNumArr[ nCnt-2 ] + 1;
  96         }
  97     }
  98     va_end( pArgs );
  99
 100     DBG_ASSERT( 0 == (nCnt & 1), "ungerade Anzahl von Which-Paaren!" );
 101
 102     // so, jetzt sind alle Bereiche vorhanden und
 103     rpRanges = new NUMTYPE[ nCnt+1 ];
 104     memcpy( rpRanges, aNumArr.GetData(), sizeof(NUMTYPE) * nCnt );
 105     *(rpRanges+nCnt) = 0;
 106
 107     return nSize;
 108 }
 109
 110 //------------------------------------------------------------------------
 111
 112 NUMTYPE Count_Impl( const NUMTYPE *pRanges )
 113
 114 /**     <H3>Description</H3>
 115
 116     Determines the number of NUMTYPEs in an 0-terminated array of pairs of
 117     NUMTYPEs. The terminating 0 is not included in the count.
 118 */
 119
 120 {
 121     NUMTYPE nCount = 0;
 122     while ( *pRanges )
 123     {
 124         nCount += 2;
 125         pRanges += 2;
 126     }
 127     return nCount;
 128 }
 129
 130 //------------------------------------------------------------------------
 131
 132 NUMTYPE Capacity_Impl( const NUMTYPE *pRanges )
 133
 134 /**     <H3>Description</H3>
 135
 136     Determines the total number of NUMTYPEs described in an 0-terminated
 137     array of pairs of NUMTYPEs, each representing an range of NUMTYPEs.
 138 */
 139
 140 {
 141     NUMTYPE nCount = 0;
 142
 143     if ( pRanges )
 144     {
 145         while ( *pRanges )
 146         {
 147             nCount += pRanges[1] - pRanges[0] + 1;
 148             pRanges += 2;
 149         }
 150     }
 151     return nCount;
 152 }
 153
 154 //------------------------------------------------------------------------
 155
 156 SfxNumRanges::SfxNumRanges( const SfxNumRanges &rOrig )
 157
 158 /**     <H3>Description</H3>
 159
 160     Copy-Ctor.
 161 */
 162
 163 {
 164     if ( rOrig._pRanges )
 165     {
 166         NUMTYPE nCount = Count_Impl( rOrig._pRanges ) + 1;
 167         _pRanges = new NUMTYPE[nCount];
 168         memcpy( _pRanges, rOrig._pRanges, sizeof(NUMTYPE) * nCount );
 169     }
 170     else
 171         _pRanges = 0;
 172 }
 173
 174 //------------------------------------------------------------------------
 175
 176 SfxNumRanges::SfxNumRanges( NUMTYPE nWhich1, NUMTYPE nWhich2 )
 177
 178 /**     <H3>Description</H3>
 179
 180     Constructs an SfxNumRanges-instance from one range of NUMTYPEs.
 181
 182     precondition:
 183         nWhich1 <= nWhich2
 184 */
 185
 186 :   _pRanges( new NUMTYPE[3] )
 187 {
 188     _pRanges[0] = nWhich1;
 189     _pRanges[1] = nWhich2;
 190     _pRanges[2] = 0;
 191 }
 192
 193 //------------------------------------------------------------------------
 194
 195 SfxNumRanges::SfxNumRanges( NUMTYPE_ARG nWh0, NUMTYPE_ARG nWh1, NUMTYPE_ARG nNull, ... )
 196
 197 /**     <H3>Description</H3>
 198
 199     Constructs an SfxNumRanges-instance from more than one sorted ranges of
 200     NUMTYPEs terminated with one 0.
 201
 202     precondition: for each n >= 0 && n < nArgs
 203         nWh(2n) <= nWh(2n+1) && ( nWh(2n+2)-nWh(2n+1) ) > 1
 204 */
 205
 206 {
 207     va_list pArgs;
 208     va_start( pArgs, nNull );
 209     InitializeRanges_Impl(
 210         _pRanges, pArgs, sal::static_int_cast< NUMTYPE >(nWh0),
 211         sal::static_int_cast< NUMTYPE >(nWh1),
 212         sal::static_int_cast< NUMTYPE >(nNull));
 213     DBG_CHECK_RANGES(NUMTYPE, _pRanges);
 214 }
 215
 216 //------------------------------------------------------------------------
 217
 218 SfxNumRanges::SfxNumRanges( const NUMTYPE* pArr )
 219
 220 /**     <H3>Description</H3>
 221
 222     Constcurts an SfxNumRanges-instance from an sorted ranges of NUMTYPEs,
 223     terminates with on 0.
 224
 225     precondition: for each n >= 0 && n < (sizeof(pArr)-1)
 226         pArr[2n] <= pArr[2n+1] && ( pArr[2n+2]-pArr[2n+1] ) > 1
 227 */
 228
 229 {
 230     DBG_CHECK_RANGES(NUMTYPE, pArr);
 231     NUMTYPE nCount = Count_Impl(pArr) + 1;
 232     _pRanges = new NUMTYPE[ nCount ];
 233     memcpy( _pRanges, pArr, sizeof(NUMTYPE) * nCount );
 234 }
 235
 236 //------------------------------------------------------------------------
 237
 238 BOOL SfxNumRanges::operator==( const SfxNumRanges &rOther ) const
 239 {
 240     // Object pointers equal?
 241     if ( this == &rOther )
 242         return TRUE;
 243
 244     // Ranges pointers equal?
 245     if ( _pRanges == rOther._pRanges )
 246         return TRUE;
 247
 248     // Counts equal?
 249     NUMTYPE nCount = Count();
 250     if ( nCount != rOther.Count() )
 251         return FALSE;
 252
 253     // Check arrays.
 254     NUMTYPE n = 0;
 255     while( _pRanges[ n ] != 0 )
 256     {
 257         // Elements at current position equal?
 258         if ( _pRanges[ n ] != rOther._pRanges[ n ] )
 259             return FALSE;
 260
 261         ++n;
 262     }
 263
 264     return TRUE;
 265 }
 266
 267 //------------------------------------------------------------------------
 268
 269 SfxNumRanges& SfxNumRanges::operator =
 270 (
 271     const SfxNumRanges &rRanges
 272 )
 273
 274 /**     <H3>Description</H3>
 275
 276     Assigns ranges from 'rRanges' to '*this'.
 277 */
 278
 279 {
 280     // special case: assign itself
 281     if ( &rRanges == this )
 282         return *this;
 283
 284     delete[] _pRanges;
 285
 286     // special case: 'rRanges' is empty
 287     if ( rRanges.IsEmpty() )
 288         _pRanges = 0;
 289     else
 290     {
 291         // copy ranges
 292         NUMTYPE nCount = Count_Impl( rRanges._pRanges ) + 1;
 293         _pRanges = new NUMTYPE[ nCount ];
 294         memcpy( _pRanges, rRanges._pRanges, sizeof(NUMTYPE) * nCount );
 295     }
 296     return *this;
 297 }
 298
 299 //------------------------------------------------------------------------
 300
 301 SfxNumRanges& SfxNumRanges::operator +=
 302 (
 303     const SfxNumRanges &rRanges
 304 )
 305
 306 /**     <H3>Description</H3>
 307
 308     Merges *this with 'rRanges'.
 309
 310     for each NUMTYPE n:
 311         this->Contains( n ) || rRanges.Contains( n ) => this'->Contains( n )
 312         !this->Contains( n ) && !rRanges.Contains( n ) => !this'->Contains( n )
 313 */
 314
 315 {
 316     // special cases: one is empty
 317     if ( rRanges.IsEmpty() )
 318         return *this;
 319     if ( IsEmpty() )
 320         return *this = rRanges;
 321
 322     // First, run thru _pRanges and rRanges._pRanges and determine the size of
 323     // the new, merged ranges:
 324     NUMTYPE nCount = 0;
 325     const NUMTYPE * pRA = _pRanges;
 326     const NUMTYPE * pRB = rRanges._pRanges;
 327
 328     for (;;)
 329     {
 330         // The first pair of pRA has a lower lower bound than the first pair
 331         // of pRB:
 332         if (pRA[0] > pRB[0])
 333             Swap_Impl(pRA, pRB);
 334
 335         // We are done with the merging if at least pRA is exhausted:
 336         if (!pRA[0])
 337             break;
 338
 339         for (;;)
 340         {
 341             // Skip those pairs in pRB that completely lie in the first pair
 342             // of pRA:
 343             while (pRB[1] <= pRA[1])
 344             {
 345                 pRB += 2;
 346
 347                 // Watch out for exhaustion of pRB:
 348                 if (!pRB[0])
 349                 {
 350                     Swap_Impl(pRA, pRB);
 351                     goto count_rest;
 352                 }
 353             }
 354
 355             // If the next pair of pRA does not at least touch the current new
 356             // pair, we are done with the current new pair:
 357             if (pRB[0] > pRA[1] + 1)
 358                 break;
 359
 360             // The next pair of pRB extends the current new pair; first,
 361             // extend the current new pair (we are done if pRB is then
 362             // exhausted); second, switch the roles of pRA and pRB in order to
 363             // merge in those following pairs of the original pRA that will
 364             // lie in the (now larger) current new pair or will even extend it
 365             // further:
 366             pRA += 2;
 367             if (!pRA[0])
 368                 goto count_rest;
 369             Swap_Impl(pRA, pRB);
 370         }
 371
 372         // Done with the current new pair:
 373         pRA += 2;
 374         nCount += 2;
 375     }
 376
 377     // Only pRB has more pairs available, pRA is already exhausted:
 378 count_rest:
 379     for (; pRB[0]; pRB += 2)
 380         nCount += 2;
 381
 382     // Now, create new ranges of the correct size and, on a second run thru
 383     // _pRanges and rRanges._pRanges, copy the merged pairs into the new
 384     // ranges:
 385     NUMTYPE * pNew = new NUMTYPE[nCount + 1];
 386     pRA = _pRanges;
 387     pRB = rRanges._pRanges;
 388     NUMTYPE * pRN = pNew;
 389
 390     for (;;)
 391     {
 392         // The first pair of pRA has a lower lower bound than the first pair
 393         // of pRB:
 394         if (pRA[0] > pRB[0])
 395             Swap_Impl(pRA, pRB);
 396
 397         // We are done with the merging if at least pRA is exhausted:
 398         if (!pRA[0])
 399             break;
 400
 401         // Lower bound of current new pair is already known:
 402         *pRN++ = pRA[0];
 403
 404         for (;;)
 405         {
 406             // Skip those pairs in pRB that completely lie in the first pair
 407             // of pRA:
 408             while (pRB[1] <= pRA[1])
 409             {
 410                 pRB += 2;
 411
 412                 // Watch out for exhaustion of pRB:
 413                 if (!pRB[0])
 414                 {
 415                     Swap_Impl(pRA, pRB);
 416                     ++pRB;
 417                     goto copy_rest;
 418                 }
 419             }
 420
 421             // If the next pair of pRA does not at least touch the current new
 422             // pair, we are done with the current new pair:
 423             if (pRB[0] > pRA[1] + 1)
 424                 break;
 425
 426             // The next pair of pRB extends the current new pair; first,
 427             // extend the current new pair (we are done if pRB is then
 428             // exhausted); second, switch the roles of pRA and pRB in order to
 429             // merge in those following pairs of the original pRA that will
 430             // lie in the (now larger) current new pair or will even extend it
 431             // further:
 432             pRA += 2;
 433             if (!pRA[0])
 434             {
 435                 ++pRB;
 436                 goto copy_rest;
 437             }
 438             Swap_Impl(pRA, pRB);
 439         }
 440
 441         // Done with the current new pair, now upper bound is also known:
 442         *pRN++ = pRA[1];
 443         pRA += 2;
 444     }
 445
 446     // Only pRB has more pairs available (which are copied to the new ranges
 447     // unchanged), pRA is already exhausted:
 448 copy_rest:
 449     for (; *pRB;)
 450         *pRN++ = *pRB++;
 451     *pRN = 0;
 452
 453     delete[] _pRanges;
 454     _pRanges = pNew;
 455
 456     return *this;
 457 }
 458
 459 //------------------------------------------------------------------------
 460
 461 SfxNumRanges& SfxNumRanges::operator -=
 462 (
 463     const SfxNumRanges &rRanges
 464 )
 465
 466 /**     <H3>Description</H3>
 467
 468     Removes 'rRanges' from '*this'.
 469
 470     for each NUMTYPE n:
 471         this->Contains( n ) && rRanges.Contains( n ) => !this'->Contains( n )
 472         this->Contains( n ) && !rRanges.Contains( n ) => this'->Contains( n )
 473         !this->Contains( n ) => !this'->Contains( n )
 474 */
 475
 476 {
 477     // special cases: one is empty
 478     if ( rRanges.IsEmpty() || IsEmpty() )
 479         return *this;
 480
 481     // differentiate 'rRanges' in a temporary copy of '*this'
 482     // (size is computed for maximal possibly split-count plus terminating 0)
 483     NUMTYPE nThisSize = Count_Impl(_pRanges);
 484     NUMTYPE nTargetSize = 1 + (  nThisSize + Count_Impl(rRanges._pRanges) );
 485     NUMTYPE *pTarget = new NUMTYPE[ nTargetSize ];
 486     memset( pTarget, sizeof(NUMTYPE)*nTargetSize, 0 );
 487     memcpy( pTarget, _pRanges, sizeof(NUMTYPE)*nThisSize );
 488
 489     NUMTYPE nPos1 = 0, nPos2 = 0, nTargetPos = 0;
 490     while( _pRanges[ nPos1 ] )
 491     {
 492         NUMTYPE l1 = _pRanges[ nPos1 ];          // lower bound of interval 1
 493         NUMTYPE u1 = _pRanges[ nPos1+1 ];        // upper bound of interval 1
 494         NUMTYPE l2 = rRanges._pRanges[ nPos2 ];          // lower bound of interval 2
 495         NUMTYPE u2 = rRanges._pRanges[ nPos2+1 ];        // upper bound of interval 2
 496
 497         // boundary cases
 498         // * subtrahend is empty -> copy the minuend
 499         if( !l2 )
 500         {
 501             pTarget[ nTargetPos ] = l1;
 502             pTarget[ nTargetPos+1 ] = u1;
 503             nTargetPos += 2;
 504             nPos1 += 2;
 505             continue;
 506         }
 507         // * next subtrahend interval is completely higher -> copy the minuend
 508         if( u1 < l2 )
 509         {
 510             pTarget[ nTargetPos ] = l1;
 511             pTarget[ nTargetPos+1 ] = u1;
 512             nTargetPos += 2;
 513             nPos1 += 2;
 514             continue;
 515         }
 516
 517         // * next subtrahend interval is completely lower -> try next
 518         if( u2 < l1 )
 519         {
 520             nPos2 += 2;
 521             continue;
 522         }
 523
 524         // intersecting cases
 525         // * subtrahend cuts out from the beginning of the minuend
 526         if( l2 <= l1 && u2 <= u1 )
 527         {
 528             // reduce minuend interval, try again (minuend might be affected by other subtrahend intervals)
 529             _pRanges[ nPos1 ] = u2 + 1;
 530             nPos2 += 2; // this cannot hurt any longer
 531             continue;
 532         }
 533
 534         // * subtrahend cuts out from the end of the minuend
 535         if( l1 <= l2 && u1 <= u2 )
 536         {
 537             // copy remaining part of minuend (cannot be affected by other intervals)
 538             if( l1 < l2 ) // anything left at all?
 539             {
 540                 pTarget[ nTargetPos ] = l1;
 541                 pTarget[ nTargetPos+1 ] = l2 - 1;
 542                 nTargetPos += 2;
 543                 // do not increment nPos2, might affect next minuend interval, too
 544             }
 545             nPos1 += 2; // nothing left at all
 546             continue;
 547         }
 548
 549         // * subtrahend completely deletes minuend (larger or same at both ends)
 550         if( l1 >= l2 && u1 <= u2 )
 551         {
 552             nPos1 += 2; // minuend deleted
 553             // do not increment nPos2, might affect next minuend interval, too
 554             continue;
 555         }
 556
 557         // * subtrahend divides minuend into two pieces
 558         if( l1 <= l2 && u1 >= u2 ) // >= and <= since they may be something left only at one side
 559         {
 560             // left side
 561             if( l1 < l2 ) // anything left at all
 562             {
 563                 pTarget[ nTargetPos ] = l1;
 564                 pTarget[ nTargetPos+1 ] = l2 - 1;
 565                 nTargetPos += 2;
 566             }
 567
 568             // right side
 569             if( u1 > u2 ) // anything left at all
 570             {
 571                 // reduce minuend interval, try again (minuend might be affected by other subtrahend itnervals )
 572                 _pRanges[ nPos1 ] = u2 + 1;
 573             }
 574
 575             // subtrahend is completely used
 576             nPos2 += 2;
 577             continue;
 578         }
 579
 580         // we should never be here
 581         DBG_ERROR( "SfxNumRanges::operator-=: internal error" );
 582     } // while
 583
 584     pTarget[ nTargetPos ] = 0;
 585
 586     // assign the differentiated ranges
 587     delete[] _pRanges;
 588
 589     NUMTYPE nUShorts = Count_Impl(pTarget) + 1;
 590     if ( 1 != nUShorts )
 591     {
 592         _pRanges = new NUMTYPE[ nUShorts ];
 593         memcpy( _pRanges, pTarget, nUShorts * sizeof(NUMTYPE) );
 594     }
 595     else
 596         _pRanges = 0;
 597
 598     delete [] pTarget;
 599     return *this;
 600
 601     /* untested code from MI commented out (MDA, 28.01.97)
 602     do
 603     {
 604         // 1st range is smaller than 2nd range?
 605         if ( pRange1[1] < pRange2[0] )
 606             // => keep 1st range
 607             pRange1 += 2;
 608
 609         // 2nd range is smaller than 1st range?
 610         else if ( pRange2[1] < pRange1[0] )
 611             // => skip 2nd range
 612             pRange2 += 2;
 613
 614         // 2nd range totally overlaps the 1st range?
 615         else if ( pRange2[0] <= pRange1[0] && pRange2[1] >= pRange1[1] )
 616             // => remove 1st range
 617             memmove( pRange1, pRange1+2, sizeof(NUMTYPE) * (pEndOfTarget-pRange1+2) );
 618
 619         // 2nd range overlaps only the beginning of 1st range?
 620         else if ( pRange2[0] <= pRange1[0] && pRange2[1] < pRange1[1] )
 621         {
 622             // => cut the beginning of 1st range and goto next 2nd range
 623             pRange1[0] = pRange2[1] + 1;
 624             pRange2 += 2;
 625         }
 626
 627         // 2nd range overlaps only the end of 1st range?
 628         else if ( pRange2[0] > pRange1[0] && pRange2[1] >= pRange1[0] )
 629             // => cut the beginning of 1st range
 630             pRange1[0] = pRange2[1]+1;
 631
 632         // 2nd range is a real subset of 1st range
 633         else
 634         {
 635             // => split 1st range and goto next 2nd range
 636             memmove( pRange1+3, pRange1+1, sizeof(NUMTYPE) * (pEndOfTarget-pRange1-1) );
 637             pRange1[1] = pRange2[0] - 1;
 638             pRange1[2] = pRange2[1] + 1;
 639             pRange1 += 2;
 640             pRange2 += 2;
 641         }
 642     }
 643     while ( *pRange1 && *pRange2 );
 644
 645     // assign the differentiated ranges
 646     delete[] _pRanges;
 647     NUMTYPE nUShorts = Count_Impl(pTarget) + 1;
 648     if ( 1 != nUShorts )
 649     {
 650         _pRanges = new NUMTYPE[ nUShorts ];
 651         memcpy( _pRanges, pTarget, nUShorts * sizeof(NUMTYPE) );
 652         _pRanges[ nUShorts-1 ] = 0;
 653     }
 654     else
 655         _pRanges = 0;
 656     return *this;
 657     */
 658 }
 659
 660 //------------------------------------------------------------------------
 661
 662 SfxNumRanges& SfxNumRanges::operator /=
 663 (
 664     const SfxNumRanges &rRanges
 665 )
 666
 667 /**     <H3>Description</H3>
 668
 669     Determines intersection of '*this' with 'rRanges'.
 670
 671     for each NUMTYPE n:
 672         this->Contains( n ) && rRanges.Contains( n ) => this'->Contains( n )
 673         !this->Contains( n ) => !this'->Contains( n )
 674         !rRanges.Contains( n ) => !this'->Contains( n )
 675 */
 676
 677 {
 678     // boundary cases
 679     // * first set is empty -> nothing to be done
 680     // * second set is empty -> delete first set
 681     if( rRanges.IsEmpty() )
 682     {
 683         delete[] _pRanges;
 684
 685         _pRanges = new NUMTYPE[1];
 686         _pRanges[0] = 0;
 687
 688         return *this;
 689     }
 690
 691     // intersect 'rRanges' in a temporary copy of '*this'
 692     // (size is computed for maximal possibly split-count plus terminating 0)
 693     NUMTYPE nThisSize = Count_Impl(_pRanges);
 694     NUMTYPE nTargetSize = 1 + (  nThisSize + Count_Impl(rRanges._pRanges) );
 695     NUMTYPE *pTarget = new NUMTYPE[ nTargetSize ];
 696     memset( pTarget, sizeof(NUMTYPE)*nTargetSize, 0 );
 697     memcpy( pTarget, _pRanges, sizeof(NUMTYPE)*nThisSize );
 698
 699     NUMTYPE nPos1 = 0, nPos2 = 0, nTargetPos = 0;
 700     while( _pRanges[ nPos1 ] != 0 && rRanges._pRanges[ nPos2 ] != 0 )
 701     {
 702         NUMTYPE l1 = _pRanges[ nPos1 ];          // lower bound of interval 1
 703         NUMTYPE u1 = _pRanges[ nPos1+1 ];        // upper bound of interval 1
 704         NUMTYPE l2 = rRanges._pRanges[ nPos2 ];          // lower bound of interval 2
 705         NUMTYPE u2 = rRanges._pRanges[ nPos2+1 ];        // upper bound of interval 2
 706
 707         if( u1 < l2 )
 708         {
 709             // current interval in s1 is completely before ci in s2
 710             nPos1 += 2;
 711             continue;
 712         }
 713         if( u2 < l1 )
 714         {
 715             // ci in s2 is completely before ci in s1
 716             nPos2 += 2;
 717             continue;
 718         }
 719
 720         // assert: there exists an intersection between ci1 and ci2
 721
 722         if( l1 <= l2 )
 723         {
 724             // c1 "is more to the left" than c2
 725
 726             if( u1 <= u2 )
 727             {
 728                 pTarget[ nTargetPos ] = l2;
 729                 pTarget[ nTargetPos+1 ] = u1;
 730                 nTargetPos += 2;
 731                 nPos1 += 2;
 732                 continue;
 733             }
 734             else
 735             {
 736                 pTarget[ nTargetPos ] = l2;
 737                 pTarget[ nTargetPos+1 ] = u2;
 738                 nTargetPos += 2;
 739                 nPos2 += 2;
 740             }
 741         }
 742         else
 743         {
 744             // c2 "is more to the left" than c1"
 745
 746             if( u1 > u2 )
 747             {
 748                 pTarget[ nTargetPos ] = l1;
 749                 pTarget[ nTargetPos+1 ] = u2;
 750                 nTargetPos += 2;
 751                 nPos2 += 2;
 752             }
 753             else
 754             {
 755                 pTarget[ nTargetPos ] = l1;
 756                 pTarget[ nTargetPos+1 ] = u1;
 757                 nTargetPos += 2;
 758                 nPos1 += 2;
 759             }
 760         }
 761     }; // while
 762     pTarget[ nTargetPos ] = 0;
 763
 764     // assign the intersected ranges
 765     delete[] _pRanges;
 766
 767     NUMTYPE nUShorts = Count_Impl(pTarget) + 1;
 768     if ( 1 != nUShorts )
 769     {
 770         _pRanges = new NUMTYPE[ nUShorts ];
 771         memcpy( _pRanges, pTarget, nUShorts * sizeof(NUMTYPE) );
 772     }
 773     else
 774         _pRanges = 0;
 775
 776     delete [] pTarget;
 777     return *this;
 778 }
 779
 780 //------------------------------------------------------------------------
 781
 782 BOOL SfxNumRanges::Intersects( const SfxNumRanges &rRanges ) const
 783
 784 /**     <H3>Description</H3>
 785
 786     Determines if at least one range in 'rRanges' intersects with one
 787     range in '*this'.
 788
 789     TRUE, if there is at least one with:
 790         this->Contains( n ) && rRanges.Contains( n )
 791 */
 792
 793 {
 794     // special cases: one is empty
 795     if ( rRanges.IsEmpty() || IsEmpty() )
 796         return FALSE;
 797
 798     // find at least one intersecting range
 799     const NUMTYPE *pRange1 = _pRanges;
 800     const NUMTYPE *pRange2 = rRanges._pRanges;
 801
 802     do
 803     {
 804         // 1st range is smaller than 2nd range?
 805         if ( pRange1[1] < pRange2[0] )
 806             // => keep 1st range
 807             pRange1 += 2;
 808
 809         // 2nd range is smaller than 1st range?
 810         else if ( pRange2[1] < pRange1[0] )
 811             // => skip 2nd range
 812             pRange2 += 2;
 813
 814         // the ranges are overlappung
 815         else
 816             return TRUE;
 817     }
 818     while ( *pRange2 );
 819
 820     // no intersection found
 821     return FALSE;
 822 }
 823
 824 //------------------------------------------------------------------------
 825
 826 NUMTYPE SfxNumRanges::Count() const
 827
 828 /**     <H3>Description</H3>
 829
 830     Determines the number of USHORTs in the set described by the ranges
 831     of USHORTs in '*this'.
 832 */
 833
 834 {
 835     return Capacity_Impl( _pRanges );
 836 }
 837
 838 //------------------------------------------------------------------------
 839
 840 BOOL SfxNumRanges::Contains( NUMTYPE n ) const
 841
 842 /**     <H3>Description</H3>
 843
 844     Determines if '*this' contains 'n'.
 845 */
 846
 847 {
 848     for ( NUMTYPE *pRange = _pRanges; *pRange && *pRange <= n; pRange += 2 )
 849         if ( pRange[0] <= n && n <= pRange[1] )
 850             return TRUE;
 851     return FALSE;
 852
 853 }