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