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