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