Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
Range.cpp
Go to the documentation of this file.
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; }
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; }
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 */
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 */
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
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
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 
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 
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 
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
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 
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
483 {
484  EntityHandle retval = front();
485  if( mHead.mNext->first == mHead.mNext->second ) // need to remove pair from range
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
495 {
496  EntityHandle retval = back();
497  if( mHead.mPrev->first == mHead.mPrev->second ) // need to remove pair from range
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 */
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 
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.
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();
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();
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 
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 
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 
833 {
834  Range::const_iterator result = lower_bound( first, last, val );
835  if( result != last && *result == val ) ++result;
836  return result;
837 }
838 
840 {
841  int err;
842  EntityHandle handle = CREATE_HANDLE( type, 0, err );
843  return err ? end() : lower_bound( begin(), end(), handle );
844 }
846 {
847  int err;
848  EntityHandle handle = CREATE_HANDLE( type, 0, err );
849  return err ? end() : lower_bound( first, end(), handle );
850 }
851 
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 }
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 {
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 {
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
967 {
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 {
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