Branch data Line data Source code
1 : : /**
2 : : * MOAB, a Mesh-Oriented datABase, is a software component for creating,
3 : : * storing and accessing finite element mesh data.
4 : : *
5 : : * Copyright 2004 Sandia Corporation. Under the terms of Contract
6 : : * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
7 : : * retains certain rights in this software.
8 : : *
9 : : * This library is free software; you can redistribute it and/or
10 : : * modify it under the terms of the GNU Lesser General Public
11 : : * License as published by the Free Software Foundation; either
12 : : * version 2.1 of the License, or (at your option) any later version.
13 : : *
14 : : */
15 : :
16 : : /****************************************************
17 : : * File : Range.cpp
18 : : *
19 : : * Purpose : Stores contiguous or partially
20 : : * contiguous values in an optimized
21 : : * fashion. Partially contiguous
22 : : * accessing patterns is also optimized.
23 : : *
24 : : * Creator : Clinton Stimpson
25 : : *
26 : : * Date : 15 April 2002
27 : : *
28 : : *******************************************************/
29 : :
30 : : #include <assert.h>
31 : : #include "moab/Range.hpp"
32 : : #include "Internals.hpp"
33 : : #include "moab/CN.hpp"
34 : : #include <iostream>
35 : : #include <sstream>
36 : : #include <string>
37 : :
38 : : #ifdef HAVE_BOOST_POOL_SINGLETON_POOL_HPP
39 : : #include <boost/pool/singleton_pool.hpp>
40 : : typedef boost::singleton_pool< moab::Range::PairNode, sizeof( moab::Range::PairNode ) > PairAlloc;
41 : : // static inline moab::Range::PairNode* alloc_pair()
42 : : // { return new (PairAlloc::malloc()) moab::Range::PairNode; }
43 : : static inline moab::Range::PairNode* alloc_pair( moab::Range::PairNode* n, moab::Range::PairNode* p,
44 : : moab::EntityHandle f, moab::EntityHandle s )
45 : : {
46 : : return new( PairAlloc::malloc() ) moab::Range::PairNode( n, p, f, s );
47 : : }
48 : : static inline void free_pair( moab::Range::PairNode* node )
49 : : {
50 : : node->~PairNode();
51 : : PairAlloc::free( node );
52 : : }
53 : : #else
54 : : // static inline moab::Range::PairNode* alloc_pair()
55 : : // { return new moab::Range::PairNode; }
56 : 4597395 : static inline moab::Range::PairNode* alloc_pair( moab::Range::PairNode* n, moab::Range::PairNode* p,
57 : : moab::EntityHandle f, moab::EntityHandle s )
58 : : {
59 [ + - ]: 4597395 : return new moab::Range::PairNode( n, p, f, s );
60 : : }
61 : 4597390 : static inline void free_pair( moab::Range::PairNode* node )
62 : : {
63 : 4597390 : delete node;
64 : 4597390 : }
65 : : #endif
66 : :
67 : : namespace moab
68 : : {
69 : :
70 : : /*!
71 : : returns the number of values this list represents
72 : : */
73 : 883681 : size_t Range::size() const
74 : : {
75 : : // go through each pair and add up the number of values
76 : : // we have.
77 : 883681 : size_t sz = 0;
78 [ + + ]: 7992685 : for( PairNode* iter = mHead.mNext; iter != &mHead; iter = iter->mNext )
79 : : {
80 : 7109004 : sz += ( ( iter->second - iter->first ) + 1 );
81 : : }
82 : 883681 : return sz;
83 : : }
84 : :
85 : : /*!
86 : : advance iterator
87 : : */
88 : 230471 : Range::const_iterator& Range::const_iterator::operator+=( EntityID sstep )
89 : : {
90 : : // Check negative now to avoid infinite loop below.
91 [ - + ]: 230471 : if( sstep < 0 ) { return operator-=( -sstep ); }
92 : 230471 : EntityHandle step = sstep;
93 : :
94 : : // Handle current PairNode. Either step is within the current
95 : : // node or need to remove the remainder of the current node
96 : : // from step.
97 : 230471 : EntityHandle this_node_rem = mNode->second - mValue;
98 [ + + ]: 230471 : if( this_node_rem >= step )
99 : : {
100 : 122942 : mValue += step;
101 : 122942 : return *this;
102 : : }
103 : 107529 : step -= this_node_rem + 1;
104 : :
105 : : // For each node we are stepping past, decrement step
106 : : // by the size of the node.
107 : 107529 : PairNode* node = mNode->mNext;
108 : 107529 : EntityHandle node_size = node->second - node->first + 1;
109 [ + + ]: 341504 : while( step >= node_size )
110 : : {
111 : 233975 : step -= node_size;
112 : 233975 : node = node->mNext;
113 : 233975 : node_size = node->second - node->first + 1;
114 : : }
115 : :
116 : : // Advance into the resulting node by whatever is
117 : : // left in step.
118 : 107529 : mNode = node;
119 : 107529 : mValue = mNode->first + step;
120 : 107529 : return *this;
121 : : }
122 : :
123 : : /*!
124 : : regress iterator
125 : : */
126 : 179 : Range::const_iterator& Range::const_iterator::operator-=( EntityID sstep )
127 : : {
128 : : // Check negative now to avoid infinite loop below.
129 [ - + ]: 179 : if( sstep < 0 ) { return operator+=( -sstep ); }
130 : 179 : EntityHandle step = sstep;
131 : :
132 : : // Handle current PairNode. Either step is within the current
133 : : // node or need to remove the remainder of the current node
134 : : // from step.
135 : 179 : EntityHandle this_node_rem = mValue - mNode->first;
136 [ - + ]: 179 : if( this_node_rem >= step )
137 : : {
138 : 0 : mValue -= step;
139 : 0 : return *this;
140 : : }
141 : 179 : step -= this_node_rem + 1;
142 : :
143 : : // For each node we are stepping past, decrement step
144 : : // by the size of the node.
145 : 179 : PairNode* node = mNode->mPrev;
146 : 179 : EntityHandle node_size = node->second - node->first + 1;
147 [ - + ]: 179 : while( step >= node_size )
148 : : {
149 : 0 : step -= node_size;
150 : 0 : node = node->mPrev;
151 : 0 : node_size = node->second - node->first + 1;
152 : : }
153 : :
154 : : // Advance into the resulting node by whatever is
155 : : // left in step.
156 : 179 : mNode = node;
157 : 179 : mValue = mNode->second - step;
158 : 179 : return *this;
159 : : }
160 : :
161 : : //! another constructor that takes an initial range
162 : 852 : Range::Range( EntityHandle val1, EntityHandle val2 )
163 : : {
164 : 426 : mHead.mNext = mHead.mPrev = alloc_pair( &mHead, &mHead, val1, val2 );
165 : 426 : mHead.first = mHead.second = 0;
166 : 426 : }
167 : :
168 : : //! copy constructor
169 : 416948 : Range::Range( const Range& copy )
170 : : {
171 : : // set the head node to point to itself
172 : 208474 : mHead.mNext = mHead.mPrev = &mHead;
173 : 208474 : mHead.first = mHead.second = 0;
174 : :
175 : 208474 : const PairNode* copy_node = copy.mHead.mNext;
176 : 208474 : PairNode* new_node = &mHead;
177 [ + + ]: 645527 : for( ; copy_node != &( copy.mHead ); copy_node = copy_node->mNext )
178 : : {
179 : 437053 : PairNode* tmp_node = alloc_pair( new_node->mNext, new_node, copy_node->first, copy_node->second );
180 : 437053 : new_node->mNext->mPrev = tmp_node;
181 : 437053 : new_node->mNext = tmp_node;
182 : 437053 : new_node = tmp_node;
183 : : }
184 : 208474 : }
185 : :
186 : : //! clears the contents of the list
187 : 1608825 : void Range::clear()
188 : : {
189 : 1608825 : PairNode* tmp_node = mHead.mNext;
190 [ + + ]: 5582324 : while( tmp_node != &mHead )
191 : : {
192 : 3973499 : PairNode* to_delete = tmp_node;
193 : 3973499 : tmp_node = tmp_node->mNext;
194 : 3973499 : free_pair( to_delete );
195 : : }
196 : 1608825 : mHead.mNext = &mHead;
197 : 1608825 : mHead.mPrev = &mHead;
198 : 1608825 : }
199 : :
200 : 107075 : Range& Range::operator=( const Range& copy )
201 : : {
202 : 107075 : clear();
203 : 107075 : const PairNode* copy_node = copy.mHead.mNext;
204 : 107075 : PairNode* new_node = &mHead;
205 [ + + ]: 160591 : for( ; copy_node != &( copy.mHead ); copy_node = copy_node->mNext )
206 : : {
207 : 53516 : PairNode* tmp_node = alloc_pair( new_node->mNext, new_node, copy_node->first, copy_node->second );
208 : 53516 : new_node->mNext->mPrev = tmp_node;
209 : 53516 : new_node->mNext = tmp_node;
210 : 53516 : new_node = tmp_node;
211 : : }
212 : 107075 : return *this;
213 : : }
214 : :
215 : : /*!
216 : : inserts a single value into this range
217 : : */
218 : :
219 : 6877011 : Range::iterator Range::insert( Range::iterator hint, EntityHandle val )
220 : : {
221 : : // don't allow zero-valued handles in Range
222 [ - + ]: 6877011 : if( val == 0 ) return end();
223 : :
224 : : // if this is empty, just add it and return an iterator to it
225 [ + + ]: 6877011 : if( &mHead == mHead.mNext )
226 : : {
227 : 578354 : mHead.mNext = mHead.mPrev = alloc_pair( &mHead, &mHead, val, val );
228 : 578354 : return iterator( mHead.mNext, val );
229 : : }
230 : :
231 : : // find the location in the list where we can safely insert
232 : : // new items and keep it ordered
233 : 6298657 : PairNode* hter = hint.mNode;
234 [ + + ]: 6298657 : PairNode* jter = hter->first <= val ? hter : mHead.mNext;
235 [ + + ][ + + ]: 31489380 : for( ; ( jter != &mHead ) && ( jter->second < val ); jter = jter->mNext )
236 : : ;
237 : 6298657 : PairNode* iter = jter;
238 : 6298657 : jter = jter->mPrev;
239 : :
240 : : // if this val is already in the list
241 [ + + ][ + + ]: 6298657 : if( ( iter->first <= val && iter->second >= val ) && ( iter != &mHead ) )
[ + - ]
242 : : {
243 : : // return an iterator pointing to this location
244 : 30208 : return iterator( iter, val );
245 : : }
246 : :
247 : : // one of a few things can happen at this point
248 : : // 1. this range needs to be backwardly extended
249 : : // 2. the previous range needs to be forwardly extended
250 : : // 3. a new range needs to be added
251 : :
252 : : // extend this range back a bit
253 [ + + ][ + - ]: 6268449 : else if( ( iter->first == ( val + 1 ) ) && ( iter != &mHead ) )
254 : : {
255 : 3288630 : iter->first = val;
256 : : // see if we need to merge two ranges
257 [ + + ][ + + ]: 3288630 : if( ( iter != mHead.mNext ) && ( jter->second == ( val - 1 ) ) )
258 : : {
259 : 176654 : jter->second = iter->second;
260 : 176654 : iter->mPrev->mNext = iter->mNext;
261 : 176654 : iter->mNext->mPrev = iter->mPrev;
262 : 176654 : free_pair( iter );
263 : 176654 : return iterator( jter, val );
264 : : }
265 : : else
266 : : {
267 : 3111976 : return iterator( iter, val );
268 : : }
269 : : }
270 : : // extend the previous range forward a bit
271 [ + + ][ + + ]: 2979819 : else if( ( jter->second == ( val - 1 ) ) && ( iter != mHead.mNext ) )
272 : : {
273 : 686824 : jter->second = val;
274 : 686824 : return iterator( jter, val );
275 : : }
276 : : // make a new range
277 : : else
278 : : {
279 : 2292995 : PairNode* new_node = alloc_pair( iter, iter->mPrev, val, val );
280 : 2292995 : iter->mPrev = new_node->mPrev->mNext = new_node;
281 : 2292995 : return iterator( new_node, val );
282 : : }
283 : : }
284 : :
285 : 1825062 : Range::iterator Range::insert( Range::iterator prev, EntityHandle val1, EntityHandle val2 )
286 : : {
287 [ + - ][ + + ]: 1825062 : if( val1 == 0 || val1 > val2 ) return end();
288 : :
289 : : // Empty
290 [ + + ]: 1825054 : if( mHead.mNext == &mHead )
291 : : {
292 [ + - ][ - + ]: 278111 : assert( prev == end() );
293 : 278111 : PairNode* new_node = alloc_pair( &mHead, &mHead, val1, val2 );
294 : 278111 : mHead.mNext = mHead.mPrev = new_node;
295 : 278111 : return iterator( mHead.mNext, val1 );
296 : : }
297 : :
298 : 1546943 : PairNode* iter = prev.mNode;
299 : : // If iterator is at end, set it to last.
300 : : // Thus if the hint was to append, we start searching
301 : : // at the end of the list.
302 [ - + ]: 1546943 : if( iter == &mHead ) iter = mHead.mPrev;
303 : : // if hint (prev) is past insert position, reset it to the beginning.
304 [ + - ][ + + ]: 1546943 : if( iter != &mHead && iter->first > val2 + 1 ) iter = mHead.mNext;
305 : :
306 : : // If hint is bogus then search backwards
307 [ + + ][ + + ]: 1546944 : while( iter != mHead.mNext && iter->mPrev->second >= val1 - 1 )
308 : 1 : iter = iter->mPrev;
309 : :
310 : : // Input range is before beginning?
311 [ + + ][ + + ]: 1546943 : if( iter->mPrev == &mHead && val2 < iter->first - 1 )
312 : : {
313 : 38386 : PairNode* new_node = alloc_pair( iter, &mHead, val1, val2 );
314 : 38386 : mHead.mNext = iter->mPrev = new_node;
315 : 38386 : return iterator( mHead.mNext, val1 );
316 : : }
317 : :
318 : : // Find first intersecting list entry, or the next entry
319 : : // if none intersects.
320 [ + + ][ + + ]: 2706069 : while( iter != &mHead && iter->second + 1 < val1 )
321 : 1197512 : iter = iter->mNext;
322 : :
323 : : // Need to insert new pair (don't intersect any existing pair)?
324 [ + + ][ + + ]: 1508557 : if( iter == &mHead || iter->first - 1 > val2 )
325 : : {
326 : 896984 : PairNode* new_node = alloc_pair( iter, iter->mPrev, val1, val2 );
327 : 896984 : iter->mPrev = iter->mPrev->mNext = new_node;
328 : 896984 : return iterator( iter->mPrev, val1 );
329 : : }
330 : :
331 : : // Make the first intersecting pair the union of itself with [val1,val2]
332 [ + + ]: 611573 : if( iter->first > val1 ) iter->first = val1;
333 [ + + ]: 611573 : if( iter->second >= val2 ) return iterator( iter, val1 );
334 : 411072 : iter->second = val2;
335 : :
336 : : // Merge any remaining pairs that intersect [val1,val2]
337 [ + + ][ + + ]: 418597 : while( iter->mNext != &mHead && iter->mNext->first <= val2 + 1 )
338 : : {
339 : 7525 : PairNode* dead = iter->mNext;
340 : 7525 : iter->mNext = dead->mNext;
341 : 7525 : dead->mNext->mPrev = iter;
342 : :
343 [ + + ]: 7525 : if( dead->second > val2 ) iter->second = dead->second;
344 : 7525 : free_pair( dead );
345 : : }
346 : :
347 : 1825062 : return iterator( iter, val1 );
348 : : }
349 : :
350 : : /*!
351 : : erases an item from this list and returns an iterator to the next item
352 : : */
353 : :
354 : 61997 : Range::iterator Range::erase( iterator iter )
355 : : {
356 : : // one of a few things could happen
357 : : // 1. shrink a range
358 : : // 2. split a range
359 : : // 3. remove a range
360 : :
361 [ + - ][ + - ]: 61997 : if( iter == end() ) return end();
[ + + ][ + - ]
362 : :
363 : : // the iterator most likely to be returned
364 : 61994 : iterator new_iter = iter;
365 [ + - ]: 61994 : ++new_iter;
366 : :
367 : 61994 : PairNode* kter = iter.mNode;
368 : :
369 : : // just remove the range
370 [ + + ]: 61994 : if( kter->first == kter->second )
371 : : {
372 : 9450 : kter->mNext->mPrev = kter->mPrev;
373 : 9450 : kter->mPrev->mNext = kter->mNext;
374 : 9450 : free_pair( kter );
375 : 9450 : return new_iter;
376 : : }
377 : : // shrink it
378 [ + + ]: 52544 : else if( kter->first == iter.mValue )
379 : : {
380 : 17050 : kter->first++;
381 : 17050 : return new_iter;
382 : : }
383 : : // shrink it the other way
384 [ + + ]: 35494 : else if( kter->second == iter.mValue )
385 : : {
386 : 16256 : kter->second--;
387 : 16256 : return new_iter;
388 : : }
389 : : // split the range
390 : : else
391 : : {
392 [ + - ]: 19238 : PairNode* new_node = alloc_pair( iter.mNode->mNext, iter.mNode, iter.mValue + 1, kter->second );
393 : 19238 : new_node->mPrev->mNext = new_node->mNext->mPrev = new_node;
394 : 19238 : iter.mNode->second = iter.mValue - 1;
395 [ + - ]: 19238 : new_iter = const_iterator( new_node, new_node->first );
396 : 61997 : return new_iter;
397 : : }
398 : : }
399 : :
400 : : //! remove a range of items from the list
401 : 205 : Range::iterator Range::erase( iterator iter1, iterator iter2 )
402 : : {
403 [ + - ]: 205 : iterator result;
404 : :
405 [ + + ]: 205 : if( iter1.mNode == iter2.mNode )
406 : : {
407 [ + + ]: 23 : if( iter2.mValue <= iter1.mValue )
408 : : {
409 : : // empty range OK, otherwise invalid input
410 : 20 : return iter2;
411 : : }
412 : :
413 : : // If both iterators reference the same pair node, then
414 : : // we're either removing values from the front of the
415 : : // node or splitting the node. We can never be removing
416 : : // the last value in the node in this case because iter2
417 : : // points *after* the last entry to be removed.
418 : :
419 : 3 : PairNode* node = iter1.mNode;
420 [ + + ]: 3 : if( iter1.mValue == node->first )
421 : : {
422 : 2 : node->first = iter2.mValue;
423 : 2 : result = iter2;
424 : : }
425 : : else
426 : : {
427 [ + - ]: 1 : PairNode* new_node = alloc_pair( node->mNext, node, iter2.mValue, node->second );
428 : 1 : new_node->mNext->mPrev = new_node;
429 : 1 : new_node->mPrev->mNext = new_node;
430 : 1 : node->second = iter1.mValue - 1;
431 [ + - ]: 3 : result = iterator( new_node, new_node->first );
432 : : }
433 : : }
434 : : else
435 : : {
436 [ - + ]: 182 : if( iter1.mNode == &mHead ) return iter1;
437 : 182 : PairNode* dn = iter1.mNode;
438 [ + + ]: 182 : if( iter1.mValue > dn->first )
439 : : {
440 : 12 : dn->second = iter1.mValue - 1;
441 : 12 : dn = dn->mNext;
442 : : }
443 [ + + ]: 182 : if( iter2.mNode != &mHead ) iter2.mNode->first = iter2.mValue;
444 [ + + ]: 371 : while( dn != iter2.mNode )
445 : : {
446 : 189 : PairNode* dead = dn;
447 : 189 : dn = dn->mNext;
448 : :
449 : 189 : dead->mPrev->mNext = dead->mNext;
450 : 189 : dead->mNext->mPrev = dead->mPrev;
451 : : // dead->mPrev = dead->mNext = 0;
452 [ + - ]: 189 : delete_pair_node( dead );
453 : : }
454 : :
455 : 182 : result = iter2;
456 : : }
457 : :
458 : 205 : return result;
459 : : }
460 : :
461 : 430262 : void Range::delete_pair_node( PairNode* node )
462 : : {
463 [ + - ]: 430262 : if( node != &mHead )
464 : : { // pop_front() and pop_back() rely on this check
465 : 430262 : node->mPrev->mNext = node->mNext;
466 : 430262 : node->mNext->mPrev = node->mPrev;
467 : 430262 : free_pair( node );
468 : : }
469 : 430262 : }
470 : :
471 : : //! remove first entity from range
472 : 136 : EntityHandle Range::pop_front()
473 : : {
474 : 136 : EntityHandle retval = front();
475 [ + - ]: 136 : if( mHead.mNext->first == mHead.mNext->second ) // need to remove pair from range
476 : 136 : delete_pair_node( mHead.mNext );
477 : : else
478 : 0 : ++( mHead.mNext->first ); // otherwise just adjust start value of pair
479 : :
480 : 136 : return retval;
481 : : }
482 : :
483 : : //! remove last entity from range
484 : 0 : EntityHandle Range::pop_back()
485 : : {
486 : 0 : EntityHandle retval = back();
487 [ # # ]: 0 : if( mHead.mPrev->first == mHead.mPrev->second ) // need to remove pair from range
488 : 0 : delete_pair_node( mHead.mPrev );
489 : : else
490 : 0 : --( mHead.mPrev->second ); // otherwise just adjust end value of pair
491 : :
492 : 0 : return retval;
493 : : }
494 : :
495 : : /*!
496 : : finds a value in the list.
497 : : this method is preferred over other algorithms because
498 : : it can be found faster this way.
499 : : */
500 : 11607304 : Range::const_iterator Range::find( EntityHandle val ) const
501 : : {
502 : : // iterator through the list
503 : 11607304 : PairNode* iter = mHead.mNext;
504 [ + + ][ + + ]: 101839128 : for( ; iter != &mHead && ( val > iter->second ); iter = iter->mNext )
505 : : ;
506 [ + + ][ + + ]: 11607304 : return ( ( iter->second >= val ) && ( iter->first <= val ) ) ? const_iterator( iter, val ) : end();
507 : : }
508 : :
509 : : /*!
510 : : merges another Range with this one
511 : : */
512 : :
513 : 303504 : void Range::insert( Range::const_iterator begini, Range::const_iterator endi )
514 : : {
515 [ + - ][ + + ]: 578430 : if( begini == endi ) return;
516 : :
517 : 274926 : PairNode* node = begini.mNode;
518 [ + + ]: 274926 : if( endi.mNode == node )
519 : : {
520 [ + - ][ + - ]: 1 : insert( *begini, ( *endi ) - 1 );
[ + - ]
521 : 1 : return;
522 : : }
523 : :
524 [ + - ][ + - ]: 274925 : Range::iterator hint = insert( *begini, node->second );
525 : 274925 : node = node->mNext;
526 [ + + ]: 537880 : while( node != endi.mNode )
527 : : {
528 [ + - ]: 262955 : hint = insert( hint, node->first, node->second );
529 : 262955 : node = node->mNext;
530 : : }
531 : :
532 [ + - ][ + + ]: 274925 : if( *endi > node->first )
533 : : {
534 [ + - ][ + - ]: 1 : if( *endi <= node->second )
535 [ + - ][ + - ]: 1 : insert( hint, node->first, *(endi)-1 );
536 : : else
537 [ # # ]: 274925 : insert( hint, node->first, node->second );
538 : : }
539 : : }
540 : :
541 : : #include <algorithm>
542 : :
543 : : // checks the range to make sure everything is A-Ok.
544 : 0 : void Range::sanity_check() const
545 : : {
546 [ # # ][ # # ]: 0 : if( empty() ) return;
547 : :
548 : 0 : const PairNode* node = mHead.mNext;
549 [ # # ]: 0 : std::vector< const PairNode* > seen_before;
550 : 0 : bool stop_it = false;
551 : :
552 [ # # ]: 0 : for( ; stop_it == false; node = node->mNext )
553 : : {
554 : : // have we seen this node before?
555 [ # # ][ # # ]: 0 : assert( std::find( seen_before.begin(), seen_before.end(), node ) == seen_before.end() );
[ # # ]
556 [ # # ]: 0 : seen_before.push_back( node );
557 : :
558 : : // is the connection correct?
559 [ # # ]: 0 : assert( node->mNext->mPrev == node );
560 : :
561 : : // are the values right?
562 [ # # ]: 0 : assert( node->first <= node->second );
563 [ # # ][ # # ]: 0 : if( node != &mHead && node->mPrev != &mHead ) assert( node->mPrev->second < node->first );
[ # # ]
564 : :
565 [ # # ]: 0 : if( node == &mHead ) stop_it = true;
566 : 0 : }
567 : : }
568 : :
569 : 0 : const std::string Range::str_rep( const char* indent_prefix ) const
570 : : {
571 [ # # ][ # # ]: 0 : std::stringstream str_stream;
572 [ # # ]: 0 : std::string indent_prefix_str;
573 [ # # ][ # # ]: 0 : if( NULL != indent_prefix ) { indent_prefix_str += indent_prefix; }
574 : :
575 [ # # ][ # # ]: 0 : if( empty() )
576 : : {
577 [ # # ][ # # ]: 0 : str_stream << indent_prefix_str << "\tempty" << std::endl;
[ # # ]
578 [ # # ][ # # ]: 0 : return str_stream.str().c_str();
579 : : }
580 : :
581 [ # # ][ # # ]: 0 : for( const_pair_iterator i = const_pair_begin(); i != const_pair_end(); ++i )
[ # # ][ # # ]
[ # # ]
582 : : {
583 [ # # ][ # # ]: 0 : EntityType t1 = TYPE_FROM_HANDLE( i->first );
584 [ # # ][ # # ]: 0 : EntityType t2 = TYPE_FROM_HANDLE( i->second );
585 : :
586 [ # # ][ # # ]: 0 : str_stream << indent_prefix_str << "\t" << CN::EntityTypeName( t1 ) << " " << ID_FROM_HANDLE( i->first );
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
587 [ # # ][ # # ]: 0 : if( i->first != i->second )
[ # # ]
588 : : {
589 [ # # ]: 0 : str_stream << " - ";
590 [ # # ][ # # ]: 0 : if( t1 != t2 ) str_stream << CN::EntityTypeName( t2 ) << " ";
[ # # ][ # # ]
591 [ # # ][ # # ]: 0 : str_stream << ID_FROM_HANDLE( i->second );
[ # # ]
592 : : }
593 [ # # ]: 0 : str_stream << std::endl;
594 : : }
595 : :
596 [ # # ]: 0 : return str_stream.str();
597 : : }
598 : :
599 : 0 : void Range::print( std::ostream& stream, const char* indent_prefix ) const
600 : : {
601 [ # # ]: 0 : stream << str_rep( indent_prefix );
602 : 0 : }
603 : :
604 : : // for debugging
605 : 0 : void Range::print( const char* indent_prefix ) const
606 : : {
607 : 0 : print( std::cout, indent_prefix );
608 : 0 : }
609 : :
610 : : // intersect two ranges, placing the results in the return range
611 : : #define MAX( a, b ) ( a < b ? b : a )
612 : : #define MIN( a, b ) ( a > b ? b : a )
613 : 1422 : Range intersect( const Range& range1, const Range& range2 )
614 : : {
615 [ + - ][ + - ]: 1422 : Range::const_pair_iterator r_it[2] = { range1.const_pair_begin(), range2.const_pair_begin() };
616 : : EntityHandle low_it, high_it;
617 : :
618 [ + - ]: 1422 : Range lhs;
619 [ + - ]: 1422 : Range::iterator hint = lhs.begin();
620 : :
621 : : // terminate the while loop when at least one "start" iterator is at the
622 : : // end of the list
623 [ + - ][ + - ]: 66912 : while( r_it[0] != range1.end() && r_it[1] != range2.end() )
[ + - ][ + + ]
[ + - ][ + - ]
[ + - ][ + + ]
[ + + ][ + + ]
[ + - ][ + - ]
[ + + # #
# # # # #
# ]
624 : : {
625 : :
626 [ + - ][ + - ]: 65490 : if( r_it[0]->second < r_it[1]->first )
[ + + ]
627 : : // 1st subrange completely below 2nd subrange
628 [ + - ]: 44 : ++r_it[0];
629 [ + - ][ + - ]: 65446 : else if( r_it[1]->second < r_it[0]->first )
[ + + ]
630 : : // 2nd subrange completely below 1st subrange
631 [ + - ]: 17208 : ++r_it[1];
632 : :
633 : : else
634 : : {
635 : : // else ranges overlap; first find greater start and lesser end
636 [ + - ][ + - ]: 48238 : low_it = MAX( r_it[0]->first, r_it[1]->first );
[ + + ][ + - ]
[ + - ]
637 [ + - ][ + - ]: 48238 : high_it = MIN( r_it[0]->second, r_it[1]->second );
[ + + ][ + - ]
[ + - ]
638 : :
639 : : // insert into result
640 [ + - ]: 48238 : hint = lhs.insert( hint, low_it, high_it );
641 : :
642 : : // now find bounds of this insertion and increment corresponding iterator
643 [ + - ][ + + ]: 48238 : if( high_it == r_it[0]->second ) ++r_it[0];
[ + - ]
644 [ + - ][ + + ]: 48238 : if( high_it == r_it[1]->second ) ++r_it[1];
[ + - ]
645 : : }
646 : : }
647 : :
648 : 1422 : return lhs;
649 : : }
650 : :
651 : 104027 : Range subtract( const Range& range1, const Range& range2 )
652 : : {
653 : 104027 : const bool braindead = false;
654 : :
655 : : if( braindead )
656 : : {
657 : : // brain-dead implementation right now
658 : : Range res( range1 );
659 : : for( Range::const_iterator rit = range2.begin(); rit != range2.end(); ++rit )
660 : : res.erase( *rit );
661 : :
662 : : return res;
663 : : }
664 : : else
665 : : {
666 [ + - ]: 104027 : Range lhs( range1 );
667 : :
668 [ + - ]: 104027 : Range::pair_iterator r_it0 = lhs.pair_begin();
669 [ + - ]: 104027 : Range::const_pair_iterator r_it1 = range2.const_pair_begin();
670 : :
671 : : // terminate the while loop when at least one "start" iterator is at the
672 : : // end of the list
673 [ + - ][ + - ]: 861780 : while( r_it0 != lhs.end() && r_it1 != range2.end() )
[ + - ][ + + ]
[ + - ][ + - ]
[ + - ][ + + ]
[ + + ][ + + ]
[ + - ][ + - ]
[ + + # #
# # # # #
# ]
674 : : {
675 : : // case a: pair wholly within subtracted pair
676 [ + - ][ + - ]: 757753 : if( r_it0->first >= r_it1->first && r_it0->second <= r_it1->second )
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ]
677 : : {
678 [ + - ]: 429803 : Range::PairNode* rtmp = r_it0.node();
679 [ + - ]: 429803 : ++r_it0;
680 [ + - ]: 429803 : lhs.delete_pair_node( rtmp );
681 : : }
682 : : // case b: pair overlaps upper part of subtracted pair
683 [ + - ][ + - ]: 327950 : else if( r_it0->first <= r_it1->second && r_it0->first >= r_it1->first )
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ]
684 : : {
685 [ + - ][ + - ]: 284 : r_it0->first = r_it1->second + 1;
686 [ + - ]: 284 : ++r_it1;
687 : : }
688 : : // case c: pair overlaps lower part of subtracted pair
689 [ + - ][ + - ]: 327666 : else if( r_it0->second >= r_it1->first && r_it0->second <= r_it1->second )
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ]
690 : : {
691 [ + - ][ + - ]: 283 : r_it0->second = r_it1->first - 1;
692 [ + - ]: 283 : ++r_it0;
693 : : }
694 : : // case d: pair completely surrounds subtracted pair
695 [ + - ][ + - ]: 327383 : else if( r_it0->first < r_it1->first && r_it0->second > r_it1->second )
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ]
696 : : {
697 : : Range::PairNode* new_node =
698 [ + - ][ + - ]: 2321 : alloc_pair( r_it0.node(), r_it0.node()->mPrev, r_it0->first, r_it1->first - 1 );
[ + - ][ + - ]
[ + - ]
699 : 2321 : new_node->mPrev->mNext = new_node->mNext->mPrev = new_node;
700 [ + - ][ + - ]: 2321 : r_it0.node()->first = r_it1->second + 1;
701 [ + - ]: 2321 : ++r_it1;
702 : : }
703 : : else
704 : : {
705 [ + - ][ + - ]: 326590 : while( r_it0->second < r_it1->first && r_it0 != lhs.end() )
[ + + ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
[ + + ][ + +
# # # # ]
706 [ + - ]: 1528 : ++r_it0;
707 [ + - ][ + - ]: 325062 : if( r_it0 == lhs.end() ) break;
[ + - ][ - + ]
708 [ + - ][ + - ]: 666335 : while( r_it1->second < r_it0->first && r_it1 != range2.end() )
[ + + ][ + - ]
[ + - ][ + - ]
[ + + ][ + + ]
[ + + ][ + +
# # # # ]
709 [ + - ]: 341273 : ++r_it1;
710 : : }
711 : : }
712 : :
713 [ + - ]: 104027 : return lhs;
714 : : }
715 : : }
716 : :
717 : 135 : Range& Range::operator-=( const Range& range2 )
718 : : {
719 : 135 : const bool braindead = false;
720 : :
721 : : if( braindead )
722 : : {
723 : : // brain-dead implementation right now
724 : : Range res( *this );
725 : : for( Range::const_iterator rit = range2.begin(); rit != range2.end(); ++rit )
726 : : res.erase( *rit );
727 : :
728 : : return *this;
729 : : }
730 : : else
731 : : {
732 [ + - ]: 135 : Range::pair_iterator r_it0 = this->pair_begin();
733 [ + - ]: 135 : Range::const_pair_iterator r_it1 = range2.const_pair_begin();
734 : :
735 : : // terminate the while loop when at least one "start" iterator is at the
736 : : // end of the list
737 [ + - ][ + - ]: 386 : while( r_it0 != this->end() && r_it1 != range2.end() )
[ + - ][ + + ]
[ + - ][ + - ]
[ + - ][ + + ]
[ + + ][ + + ]
[ + - ][ + - ]
[ + + # #
# # # # #
# ]
738 : : {
739 : : // case a: pair wholly within subtracted pair
740 [ + - ][ + - ]: 251 : if( r_it0->first >= r_it1->first && r_it0->second <= r_it1->second )
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ]
741 : : {
742 [ + - ]: 134 : Range::PairNode* rtmp = r_it0.node();
743 [ + - ]: 134 : ++r_it0;
744 [ + - ]: 134 : this->delete_pair_node( rtmp );
745 : : }
746 : : // case b: pair overlaps upper part of subtracted pair
747 [ + - ][ + - ]: 117 : else if( r_it0->first <= r_it1->second && r_it0->first >= r_it1->first )
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ]
748 : : {
749 [ + - ][ + - ]: 1 : r_it0->first = r_it1->second + 1;
750 [ + - ]: 1 : ++r_it1;
751 : : }
752 : : // case c: pair overlaps lower part of subtracted pair
753 [ + - ][ + - ]: 116 : else if( r_it0->second >= r_it1->first && r_it0->second <= r_it1->second )
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ]
754 : : {
755 [ + - ][ + - ]: 1 : r_it0->second = r_it1->first - 1;
756 [ + - ]: 1 : ++r_it0;
757 : : }
758 : : // case d: pair completely surrounds subtracted pair
759 [ + - ][ + - ]: 115 : else if( r_it0->first < r_it1->first && r_it0->second > r_it1->second )
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ]
760 : : {
761 : : Range::PairNode* new_node =
762 [ + - ][ + - ]: 10 : alloc_pair( r_it0.node(), r_it0.node()->mPrev, r_it0->first, r_it1->first - 1 );
[ + - ][ + - ]
[ + - ]
763 : 10 : new_node->mPrev->mNext = new_node->mNext->mPrev = new_node;
764 [ + - ][ + - ]: 10 : r_it0.node()->first = r_it1->second + 1;
765 [ + - ]: 10 : ++r_it1;
766 : : }
767 : : else
768 : : {
769 [ + - ][ + - ]: 130 : while( r_it0->second < r_it1->first && r_it0 != this->end() )
[ + + ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
[ + + ][ + +
# # # # ]
770 [ + - ]: 25 : ++r_it0;
771 [ + - ][ + - ]: 105 : if( r_it0 == this->end() ) break;
[ + - ][ - + ]
772 [ + - ][ + - ]: 2919 : while( r_it1->second < r_it0->first && r_it1 != range2.end() )
[ + + ][ + - ]
[ + - ][ + - ]
[ + + ][ + + ]
[ + + ][ + +
# # # # ]
773 [ + - ]: 2814 : ++r_it1;
774 : : }
775 : : }
776 : 135 : return *this;
777 : : }
778 : : }
779 : :
780 : 123003 : EntityID operator-( const Range::const_iterator& it2, const Range::const_iterator& it1 )
781 : : {
782 [ + + ][ - + ]: 123003 : assert( !it2.mValue || *it2 >= *it1 );
783 [ + + ]: 123003 : if( it2.mNode == it1.mNode ) { return *it2 - *it1; }
784 : :
785 : 59938 : EntityID result = it1.mNode->second - it1.mValue + 1;
786 [ + + ]: 62343 : for( Range::PairNode* n = it1.mNode->mNext; n != it2.mNode; n = n->mNext )
787 : 2405 : result += n->second - n->first + 1;
788 [ + + ]: 59938 : if( it2.mValue ) // (it2.mNode != &mHead)
789 : 113 : result += it2.mValue - it2.mNode->first;
790 : 59938 : return result;
791 : : }
792 : :
793 : 145421 : Range::const_iterator Range::lower_bound( Range::const_iterator first, Range::const_iterator last, EntityHandle val )
794 : : {
795 : : // Find the first pair whose end is >= val
796 : : PairNode* iter;
797 [ + + ]: 562989 : for( iter = first.mNode; iter != last.mNode; iter = iter->mNext )
798 : : {
799 [ + + ]: 472518 : if( iter->second >= val )
800 : : {
801 : : // This is the correct pair. Either 'val' is in the range, or
802 : : // the range starts before 'val' and iter->first IS the lower_bound.
803 [ + + ]: 54950 : if( iter->first > val ) return const_iterator( iter, iter->first );
804 : 2 : return const_iterator( iter, val );
805 : : }
806 : : }
807 : :
808 [ - + ]: 90471 : if( iter->first >= val )
809 : 0 : return const_iterator( iter, iter->first );
810 [ - + ]: 90471 : else if( *last > val )
811 : 0 : return const_iterator( iter, val );
812 : : else
813 : 90471 : return last;
814 : : }
815 : :
816 : 4 : Range::const_iterator Range::upper_bound( Range::const_iterator first, Range::const_iterator last, EntityHandle val )
817 : : {
818 [ + - ]: 4 : Range::const_iterator result = lower_bound( first, last, val );
819 [ + - ][ + - ]: 4 : if( result != last && *result == val ) ++result;
[ + - ][ - + ]
[ - + ][ # # ]
820 : 4 : return result;
821 : : }
822 : :
823 : 76782 : Range::const_iterator Range::lower_bound( EntityType type ) const
824 : : {
825 : : int err;
826 [ + - ]: 76782 : EntityHandle handle = CREATE_HANDLE( type, 0, err );
827 [ - + ][ # # ]: 76782 : return err ? end() : lower_bound( begin(), end(), handle );
[ + - ][ + - ]
[ + - ]
828 : : }
829 : 63802 : Range::const_iterator Range::lower_bound( EntityType type, const_iterator first ) const
830 : : {
831 : : int err;
832 [ + - ]: 63802 : EntityHandle handle = CREATE_HANDLE( type, 0, err );
833 [ - + ][ # # ]: 63802 : return err ? end() : lower_bound( first, end(), handle );
[ + - ][ + - ]
834 : : }
835 : :
836 : 7 : Range::const_iterator Range::upper_bound( EntityType type ) const
837 : : {
838 : : // if (type+1) overflows, err will be true and we return end().
839 : : int err;
840 [ + - ]: 7 : EntityHandle handle = CREATE_HANDLE( type + 1, 0, err );
841 [ - + ][ # # ]: 7 : return err ? end() : lower_bound( begin(), end(), handle );
[ + - ][ + - ]
[ + - ]
842 : : }
843 : 0 : Range::const_iterator Range::upper_bound( EntityType type, const_iterator first ) const
844 : : {
845 : : // if (type+1) overflows, err will be true and we return end().
846 : : int err;
847 [ # # ]: 0 : EntityHandle handle = CREATE_HANDLE( type + 1, 0, err );
848 [ # # ][ # # ]: 0 : return err ? end() : lower_bound( first, end(), handle );
[ # # ][ # # ]
849 : : }
850 : :
851 : 2044 : std::pair< Range::const_iterator, Range::const_iterator > Range::equal_range( EntityType type ) const
852 : : {
853 [ + - ]: 2044 : std::pair< Range::const_iterator, Range::const_iterator > result;
854 : : int err;
855 [ + - ]: 2044 : EntityHandle handle = CREATE_HANDLE( type, 0, err );
856 [ - + ][ # # ]: 2044 : result.first = err ? end() : lower_bound( begin(), end(), handle );
[ + - ][ + - ]
[ + - ]
857 : : // if (type+1) overflows, err will be true and we return end().
858 [ + - ]: 2044 : handle = CREATE_HANDLE( type + 1, 0, err );
859 [ - + ][ # # ]: 2044 : result.second = err ? end() : lower_bound( result.first, end(), handle );
[ + - ][ + - ]
860 : 2044 : return result;
861 : : }
862 : :
863 : 477 : bool Range::all_of_type( EntityType type ) const
864 : : {
865 [ + + ][ + - ]: 477 : return empty() || ( TYPE_FROM_HANDLE( front() ) == type && TYPE_FROM_HANDLE( back() ) == type );
[ + - ]
866 : : }
867 : :
868 : 28084 : bool Range::all_of_dimension( int dimension ) const
869 : : {
870 [ + + ]: 56157 : return empty() || ( CN::Dimension( TYPE_FROM_HANDLE( front() ) ) == dimension &&
[ + + + + ]
871 : 56157 : CN::Dimension( TYPE_FROM_HANDLE( back() ) ) == dimension );
872 : : }
873 : :
874 : 0 : unsigned Range::num_of_type( EntityType type ) const
875 : : {
876 [ # # ]: 0 : const_pair_iterator iter = const_pair_begin();
877 [ # # ][ # # ]: 0 : while( iter != const_pair_end() && TYPE_FROM_HANDLE( ( *iter ).second ) < type )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ]
[ # # # # ]
878 [ # # ]: 0 : ++iter;
879 : :
880 : 0 : unsigned count = 0;
881 [ # # ][ # # ]: 0 : for( ; iter != const_pair_end(); ++iter )
[ # # ][ # # ]
882 : : {
883 [ # # ][ # # ]: 0 : EntityType start_type = TYPE_FROM_HANDLE( ( *iter ).first );
884 [ # # ][ # # ]: 0 : EntityType end_type = TYPE_FROM_HANDLE( ( *iter ).second );
885 [ # # ]: 0 : if( start_type > type ) break;
886 : :
887 [ # # ][ # # ]: 0 : EntityID sid = start_type < type ? 1 : ID_FROM_HANDLE( ( *iter ).first );
[ # # ]
888 [ # # ][ # # ]: 0 : EntityID eid = end_type > type ? MB_END_ID : ID_FROM_HANDLE( ( *iter ).second );
[ # # ]
889 : 0 : count += eid - sid + 1;
890 : : }
891 : :
892 : 0 : return count;
893 : : }
894 : :
895 : 0 : unsigned Range::num_of_dimension( int dim ) const
896 : : {
897 [ # # ]: 0 : const_pair_iterator iter = const_pair_begin();
898 [ # # ][ # # ]: 0 : while( iter != const_pair_end() && CN::Dimension( TYPE_FROM_HANDLE( ( *iter ).second ) ) < dim )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # # # ]
899 [ # # ]: 0 : ++iter;
900 : :
901 : : int junk;
902 : 0 : unsigned count = 0;
903 [ # # ][ # # ]: 0 : for( ; iter != const_pair_end(); ++iter )
[ # # ][ # # ]
904 : : {
905 [ # # ][ # # ]: 0 : int start_dim = CN::Dimension( TYPE_FROM_HANDLE( ( *iter ).first ) );
[ # # ]
906 [ # # ][ # # ]: 0 : int end_dim = CN::Dimension( TYPE_FROM_HANDLE( ( *iter ).second ) );
[ # # ]
907 [ # # ]: 0 : if( start_dim > dim ) break;
908 : :
909 [ # # ][ # # ]: 0 : EntityHandle sh = start_dim < dim ? CREATE_HANDLE( CN::TypeDimensionMap[dim].first, 1, junk ) : ( *iter ).first;
[ # # ]
910 : : EntityHandle eh =
911 [ # # ][ # # ]: 0 : end_dim > dim ? CREATE_HANDLE( CN::TypeDimensionMap[dim].second, MB_END_ID, junk ) : ( *iter ).second;
[ # # ]
912 : 0 : count += eh - sh + 1;
913 : : }
914 : :
915 : 0 : return count;
916 : : }
917 : :
918 : : //! swap the contents of this range with another one
919 : : //! THIS FUNCTION MUST NOT BE INLINED, THAT WILL ELIMINATE RANGE_EMPTY AND THIS_EMPTY
920 : : //! BY SUBSTITUTION AND THE FUNCTION WON'T WORK RIGHT!
921 : 75655 : void Range::swap( Range& range )
922 : : {
923 : : // update next/prev nodes of head of both ranges
924 : 75655 : bool range_empty = ( range.mHead.mNext == &( range.mHead ) );
925 : 75655 : bool this_empty = ( mHead.mNext == &mHead );
926 : :
927 [ + + ]: 75655 : range.mHead.mNext->mPrev = ( range_empty ? &( range.mHead ) : &mHead );
928 [ + + ]: 75655 : range.mHead.mPrev->mNext = ( range_empty ? &( range.mHead ) : &mHead );
929 [ + + ]: 75655 : mHead.mNext->mPrev = ( this_empty ? &mHead : &( range.mHead ) );
930 [ + + ]: 75655 : mHead.mPrev->mNext = ( this_empty ? &mHead : &( range.mHead ) );
931 : :
932 : : // switch data in head nodes of both ranges
933 : 75655 : PairNode *range_next = range.mHead.mNext, *range_prev = range.mHead.mPrev;
934 [ + + ]: 75655 : range.mHead.mNext = ( this_empty ? &( range.mHead ) : mHead.mNext );
935 [ + + ]: 75655 : range.mHead.mPrev = ( this_empty ? &( range.mHead ) : mHead.mPrev );
936 [ + + ]: 75655 : mHead.mNext = ( range_empty ? &mHead : range_next );
937 [ + + ]: 75655 : mHead.mPrev = ( range_empty ? &mHead : range_prev );
938 : 75655 : }
939 : :
940 : : //! return a subset of this range, by type
941 : 100 : Range Range::subset_by_type( EntityType t ) const
942 : : {
943 [ + - ]: 100 : Range result;
944 [ + - ]: 100 : std::pair< const_iterator, const_iterator > iters = equal_range( t );
945 [ + - ]: 100 : result.insert( iters.first, iters.second );
946 : 100 : return result;
947 : : }
948 : :
949 : : //! return a subset of this range, by type
950 : 362 : Range Range::subset_by_dimension( int d ) const
951 : : {
952 [ + - ]: 362 : EntityHandle handle1 = CREATE_HANDLE( CN::TypeDimensionMap[d].first, 0 );
953 [ + - ][ + - ]: 362 : iterator st = lower_bound( begin(), end(), handle1 );
[ + - ]
954 : :
955 [ + - ]: 362 : iterator en;
956 [ + - ]: 362 : if( d < 4 )
957 : : { // dimension 4 is MBENTITYSET
958 [ + - ]: 362 : EntityHandle handle2 = CREATE_HANDLE( CN::TypeDimensionMap[d + 1].first, 0 );
959 [ + - ][ + - ]: 362 : en = lower_bound( st, end(), handle2 );
960 : : }
961 : : else
962 : : {
963 [ # # ]: 0 : en = end();
964 : : }
965 : :
966 [ + - ]: 362 : Range result;
967 [ + - ]: 362 : result.insert( st, en );
968 : 362 : return result;
969 : : }
970 : :
971 : 301 : bool operator==( const Range& r1, const Range& r2 )
972 : : {
973 [ + - ][ + - ]: 301 : Range::const_pair_iterator i1, i2;
974 [ + - ]: 301 : i1 = r1.const_pair_begin();
975 [ + - ]: 301 : i2 = r2.const_pair_begin();
976 [ + - ][ + - ]: 2965 : for( ; i1 != r1.const_pair_end(); ++i1, ++i2 )
[ + - ][ + - ]
[ + + ]
977 [ + - ][ + - ]: 2672 : if( i2 == r2.const_pair_end() || i1->first != i2->first || i1->second != i2->second ) return false;
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + + ][ # # ]
978 [ + - ][ + - ]: 301 : return i2 == r2.const_pair_end();
979 : : }
980 : :
981 : 0 : unsigned long Range::get_memory_use() const
982 : : {
983 : 0 : unsigned long result = 0;
984 [ # # ]: 0 : for( const PairNode* n = mHead.mNext; n != &mHead; n = n->mNext )
985 : 0 : result += sizeof( PairNode );
986 : 0 : return result;
987 : : }
988 : :
989 : 1154 : bool Range::contains( const Range& othr ) const
990 : : {
991 [ + + ]: 1154 : if( othr.empty() ) return true;
992 [ + + ]: 1151 : if( empty() ) return false;
993 : :
994 : : // neither range is empty, so both have valid pair nodes
995 : : // other than dummy mHead
996 : 525 : const PairNode* this_node = mHead.mNext;
997 : 525 : const PairNode* othr_node = othr.mHead.mNext;
998 : : for( ;; )
999 : : {
1000 : : // Loop while the node in this list is entirely before
1001 : : // the node in the other list.
1002 [ + + ]: 623 : while( this_node->second < othr_node->first )
1003 : : {
1004 : 75 : this_node = this_node->mNext;
1005 [ + + ]: 75 : if( this_node == &mHead ) return false;
1006 : : }
1007 : : // If other node is not entirely contained in this node
1008 : : // then other list is not contained in this list
1009 [ + + ]: 548 : if( this_node->first > othr_node->first ) break;
1010 : : // Loop while other node is entirely contained in this node.
1011 [ + + ]: 257 : while( othr_node->second <= this_node->second )
1012 : : {
1013 : 154 : othr_node = othr_node->mNext;
1014 [ + + ]: 154 : if( othr_node == &othr.mHead ) return true;
1015 : : }
1016 : : // If other node overlapped end of this node
1017 [ + + ]: 103 : if( othr_node->first <= this_node->second ) break;
1018 : : }
1019 : :
1020 : : // should be unreachable
1021 : 456 : return false;
1022 : : }
1023 : :
1024 [ + - ][ + - ]: 244 : } // namespace moab
|
