MOAB: Mesh Oriented datABase
(version 5.2.1)
|
00001 /** 00002 * MOAB, a Mesh-Oriented datABase, is a software component for creating, 00003 * storing and accessing finite element mesh data. 00004 * 00005 * Copyright 2004 Sandia Corporation. Under the terms of Contract 00006 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government 00007 * retains certain rights in this software. 00008 * 00009 * This library is free software; you can redistribute it and/or 00010 * modify it under the terms of the GNU Lesser General Public 00011 * License as published by the Free Software Foundation; either 00012 * version 2.1 of the License, or (at your option) any later version. 00013 * 00014 */ 00015 00016 /*! 00017 \brief Stores contiguous or partially contiguous values in an optimized 00018 fashion. Partially contiguous accessing patterns is also optimized. 00019 00020 \author Clinton Stimpson 00021 00022 \date 15 April 2002 00023 00024 ************* Range FAQ and tips ******************** 00025 00026 The purpose of this FAQ is to familiarize a user with 00027 the appropriate use of the Range template. 00028 00029 ******* A few points about Range: ******* 00030 1. Range is not the be all of generic containers. 00031 2. Range has its strengths and weaknesses as any other 00032 STL container has. 00033 3. Strengths: 00034 a. For contiguous values, storage is extremely minimal. 00035 b. Searching through contiguous values, at best, is 00036 a constant time operation. 00037 b. Fairly compatible with most STL algorithms. 00038 c. Insertions of data from high value to low value 00039 is a linear operation (constant for each insertion). 00040 d. Removal of a value using an iterator is constant time. 00041 00042 4. Weaknesses: 00043 a. For non-contiguous values, storage is not minimal and is 00044 on the order of 4x the storage space as using a vector. 00045 b. Searching through non-contiguous values is linear 00046 time operation. 00047 c. Insertions of random data is VERY slow. 00048 00049 Given the above characteristics of Ranges, you can now 00050 decide between Range and another STL container for your 00051 particular needs. 00052 00053 00054 ******* Tips ******* 00055 1. Be aware of what iterators are available. Currently, there are 00056 three. Range<T>::iterator, Range<T>::const_iterator, 00057 and Range<T>::RangeListIterator. 00058 iterator is derived from const_iterator. const_iterator 00059 is derived from RangeListIterator. RangeListIterator is a 00060 std::list<std::pair<T,T> >::const_iterator. 00061 If a particular algorithm could be more efficient by using 00062 RangeListIterator, do so. 00063 00064 ie. 00065 00066 Range<char> range1; 00067 ... put some stuff in range1 00068 Range<char> range2; 00069 00070 // the SLOW way. 00071 std::copy(range1.begin(), range1.end(), range_inserter<...>(range2)); 00072 00073 // the FAST way. 00074 for(Range<char>::RangeListIterator iter = range1.begin(), 00075 iter != range1.end(); ++iter) 00076 { 00077 range2.insert(iter->first, iter->second); 00078 } 00079 00080 2. Prefer insert(val1, val2) over insert(val) where possible. 00081 00082 3. insert(val) and insert(val1, val2) have to perform searching 00083 to find out where to insert an item. Searches are started 00084 from the beginning of the values. Inserting larger values 00085 before smaller values will increase efficiency. 00086 00087 ie. 00088 std::set<int> my_set; 00089 Range<int> my_range; 00090 .. perform some operations which set does efficiently. 00091 00092 // now copy the results from the set into the range. 00093 // copy from the end of the set to the beginning of the set 00094 std::copy(my_set.rbegin(), my_set.rend(), 00095 range_inserter< Range<int> > ( my_range ); 00096 00097 4. Use empty() instead of size() if you only need to find out 00098 if there is anything in the list. 00099 00100 5. Know what swap() does. Sometimes it is useful. It'll replace 00101 the contents of one list with another. 00102 00103 void compute_and_get_some_set( 00104 Range<char> range1, 00105 Range<char> range2, 00106 Range<char>& results 00107 ); 00108 { 00109 Range<char> tmp_results; 00110 .. perform some computation on range1 and range2 00111 and put results in tmp_results; 00112 .. filter tmp_results out for some special type. 00113 .. etc.... 00114 // return results 00115 results.swap(tmp_results); 00116 } 00117 00118 00119 ******* FAQ ******* 00120 1. Why won't this code compile? 00121 ------------------------ 00122 class SomeClass 00123 { 00124 public: 00125 Range<int> range; 00126 }; 00127 .... 00128 void some_function( const SomeClass& some_class ) 00129 { 00130 Range<int>::iterator = some_class.range.begin(); 00131 } 00132 --------------------- 00133 Solution: you need to use 00134 Range<int>::const_iterator instead. 00135 00136 2. Why doesn't this work right when I try to change the 00137 contents of an Range? 00138 00139 // make a range that has the letters A,B,C in it. 00140 Range<char> my_chars('A', 'C'); 00141 // make an iterator that points to 'A'. 00142 Range<char>::iterator iter = my_chars.begin(); 00143 // change A to D 00144 *iter = 'D'; 00145 // print contents of my_chars to stdout 00146 std::copy(my_chars.begin(), my_chars.end(), 00147 std::ostream_iterator(std::cout, " ")); 00148 00149 result is 00150 A B C 00151 instead of 00152 B C D 00153 00154 When one calls *iter, which returns 'A', the actual storage of the value 'A' 00155 which is returned is in the iterator and not in the Range. This allows 00156 for multiple iterators on a single Range and the Range does not have 00157 to keep track of which iterator is referencing which value. 00158 00159 00160 00161 */ 00162 00163 #ifndef MOAB_RANGE_HPP 00164 #define MOAB_RANGE_HPP 00165 00166 #include <string> 00167 #include <iterator> 00168 #include <iosfwd> 00169 #include <algorithm> 00170 #include "moab/Types.hpp" 00171 00172 namespace moab 00173 { 00174 00175 struct range_iter_tag : public std::bidirectional_iterator_tag 00176 { 00177 }; 00178 00179 struct range_base_iter 00180 { 00181 typedef range_iter_tag iterator_category; 00182 typedef EntityID difference_type; 00183 typedef EntityHandle value_type; 00184 typedef EntityHandle* pointer; 00185 typedef EntityHandle& reference; 00186 }; 00187 00188 //! the class Range 00189 class Range 00190 { 00191 public: 00192 // forward declare the iterators 00193 class const_iterator; 00194 class const_reverse_iterator; 00195 typedef const_iterator iterator; 00196 typedef const_reverse_iterator reverse_iterator; 00197 00198 friend Range intersect( const Range&, const Range& ); 00199 friend Range subtract( const Range&, const Range& ); 00200 00201 //! just like subtract, but as an operator 00202 Range& operator-=( const Range& rhs ); 00203 00204 //! for short hand notation, lets typedef the 00205 //! container class that holds the ranges 00206 typedef EntityHandle value_type; 00207 00208 //! default constructor 00209 Range(); 00210 00211 //! copy constructor 00212 Range( const Range& copy ); 00213 00214 //! another constructor that takes an initial range 00215 Range( EntityHandle val1, EntityHandle val2 ); 00216 00217 //! operator= 00218 Range& operator=( const Range& copy ); 00219 00220 //! destructor 00221 inline ~Range(); 00222 00223 //! return the beginning const iterator of this range 00224 inline const_iterator begin() const; 00225 00226 //! return the beginning const reverse iterator of this range 00227 inline const_reverse_iterator rbegin() const; 00228 00229 //! return the ending const iterator for this range 00230 inline const_iterator end() const; 00231 00232 //! return the ending const reverse iterator for this range 00233 inline const_reverse_iterator rend() const; 00234 00235 //! return the number of values this Ranges represents 00236 size_t size() const; 00237 00238 //! return the number of range pairs in the list 00239 size_t psize() const; 00240 00241 //! return whether empty or not 00242 //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())" 00243 inline bool empty() const; 00244 00245 iterator insert( iterator hint, EntityHandle val ); 00246 00247 //! insert an item into the list and return the iterator for the inserted item 00248 iterator insert( EntityHandle val ) 00249 { 00250 return insert( begin(), val ); 00251 } 00252 00253 //! insert a range of items into this list and return the iterator for the first 00254 //! inserted item 00255 iterator insert( iterator hint, EntityHandle first, EntityHandle last ); 00256 00257 //! insert a range of items into this list and return the iterator for the first 00258 //! inserted item 00259 iterator insert( EntityHandle val1, EntityHandle val2 ) 00260 { 00261 return insert( begin(), val1, val2 ); 00262 } 00263 00264 template < typename T > 00265 iterator insert_list( T begin_iter, T end_iter ); 00266 00267 template < class T > 00268 iterator insert( typename T::const_iterator begin_iter, typename T::const_iterator end_iter ) 00269 { 00270 return insert_list( begin_iter, end_iter ); 00271 } 00272 00273 template < typename T > 00274 iterator insert( const T* begin_iter, const T* end_iter ) 00275 { 00276 return insert_list( begin_iter, end_iter ); 00277 } 00278 00279 //! remove an item from this list and return an iterator to the next item 00280 iterator erase( iterator iter ); 00281 00282 //! remove a range of items from the list 00283 iterator erase( iterator iter1, iterator iter2 ); 00284 00285 //! erases a value from this container 00286 inline iterator erase( EntityHandle val ); 00287 00288 //! get first entity in range 00289 inline const EntityHandle& front() const; 00290 //! get last entity in range 00291 inline const EntityHandle& back() const; 00292 //! remove first entity from range 00293 EntityHandle pop_front(); 00294 //! remove last entity from range 00295 EntityHandle pop_back(); 00296 00297 //! find an item int the list and return an iterator at that value 00298 const_iterator find( EntityHandle val ) const; 00299 00300 //! return an iterator to the first value >= val 00301 static const_iterator lower_bound( const_iterator first, const_iterator last, EntityHandle val ); 00302 static const_iterator upper_bound( const_iterator first, const_iterator last, EntityHandle val ); 00303 00304 const_iterator lower_bound( EntityHandle val ) const 00305 { 00306 return lower_bound( begin(), end(), val ); 00307 } 00308 const_iterator upper_bound( EntityHandle val ) const 00309 { 00310 return upper_bound( begin(), end(), val ); 00311 } 00312 const_iterator lower_bound( EntityType type ) const; 00313 const_iterator upper_bound( EntityType type ) const; 00314 std::pair< const_iterator, const_iterator > equal_range( EntityType type ) const; 00315 const_iterator lower_bound( EntityType type, const_iterator first ) const; 00316 const_iterator upper_bound( EntityType type, const_iterator first ) const; 00317 00318 //! True if all entities in range are of passed type 00319 //! (also true if range is empty) 00320 bool all_of_type( EntityType type ) const; 00321 //! True if all entities in range are of passed dimension 00322 //! (also true if range is empty) 00323 bool all_of_dimension( int dimension ) const; 00324 00325 unsigned num_of_type( EntityType type ) const; 00326 unsigned num_of_dimension( int dim ) const; 00327 00328 //! clears the contents of the list 00329 void clear(); 00330 00331 //! for debugging 00332 const std::string str_rep( const char* indent_prefix = NULL ) const; 00333 00334 void print( const char* indent_prefix = NULL ) const; 00335 void print( std::ostream& s, const char* indent_prefix = NULL ) const; 00336 00337 unsigned long get_memory_use() const; 00338 00339 double compactness() const; 00340 00341 void insert( Range::const_iterator begin, Range::const_iterator end ); 00342 00343 //! merges this Range with another range 00344 void merge( const Range& range ) 00345 { 00346 insert( range.begin(), range.end() ); 00347 } 00348 00349 //! merge a subset of some other range 00350 void merge( Range::const_iterator beginr, Range::const_iterator endr ) 00351 { 00352 insert( beginr, endr ); 00353 } 00354 00355 //! swap the contents of this range with another one 00356 void swap( Range& range ); 00357 00358 //! check for internal consistency 00359 void sanity_check() const; 00360 00361 //! Check if this range is a non-strict superset of some other range 00362 bool contains( const Range& other ) const; 00363 00364 //! return a subset of this range, by type 00365 Range subset_by_type( EntityType t ) const; 00366 00367 //! return a subset of this range, by dimension 00368 Range subset_by_dimension( int dim ) const; 00369 00370 struct PairNode : public std::pair< EntityHandle, EntityHandle > 00371 { 00372 00373 PairNode() : std::pair< EntityHandle, EntityHandle >( 0, 0 ), mNext( NULL ), mPrev( NULL ) {} 00374 PairNode( PairNode* next, PairNode* prev, EntityHandle _first, EntityHandle _second ) 00375 : std::pair< EntityHandle, EntityHandle >( _first, _second ), mNext( next ), mPrev( prev ) 00376 { 00377 } 00378 00379 PairNode* mNext; 00380 PairNode* mPrev; 00381 }; 00382 00383 EntityHandle operator[]( EntityID index ) const; 00384 00385 int index( EntityHandle handle ) const; 00386 00387 protected: 00388 //! the head of the list that contains pairs that represent the ranges 00389 //! this list is sorted and unique at all times 00390 PairNode mHead; 00391 00392 //! if dead_node is not mHead, remove it from the list and free it's memory. 00393 void delete_pair_node( PairNode* dead_node ); 00394 00395 public: 00396 //! used to iterate over sub-ranges of a range 00397 class pair_iterator : public range_base_iter 00398 { 00399 friend class Range; 00400 00401 public: 00402 pair_iterator() : mNode( NULL ) {} 00403 pair_iterator( PairNode* nodep ) : mNode( nodep ) {} 00404 pair_iterator( const pair_iterator& copy ) : mNode( copy.mNode ) {} 00405 pair_iterator( const const_iterator& copy ) : mNode( copy.mNode ) {} 00406 00407 std::pair< EntityHandle, EntityHandle >* operator->() 00408 { 00409 return mNode; 00410 } 00411 00412 pair_iterator& operator++() 00413 { 00414 mNode = mNode->mNext; 00415 return *this; 00416 } 00417 pair_iterator operator++( int ) 00418 { 00419 pair_iterator tmp( *this ); 00420 this->operator++(); 00421 return tmp; 00422 } 00423 00424 pair_iterator& operator--() 00425 { 00426 mNode = mNode->mPrev; 00427 return *this; 00428 } 00429 pair_iterator operator--( int ) 00430 { 00431 pair_iterator tmp( *this ); 00432 this->operator--(); 00433 return tmp; 00434 } 00435 bool operator==( const pair_iterator& other ) const 00436 { 00437 return mNode == other.mNode; 00438 } 00439 00440 bool operator!=( const pair_iterator& other ) const 00441 { 00442 return mNode != other.mNode; 00443 } 00444 00445 PairNode* node() 00446 { 00447 return mNode; 00448 } 00449 00450 private: 00451 PairNode* mNode; 00452 }; 00453 00454 class const_pair_iterator; 00455 00456 //! a const iterator which iterates over an Range 00457 class const_iterator : public range_base_iter 00458 { 00459 friend class Range; 00460 friend class pair_iterator; 00461 friend class const_pair_iterator; 00462 friend EntityID operator-( const const_iterator&, const const_iterator& ); 00463 00464 public: 00465 //! default constructor - intialize base default constructor 00466 const_iterator() : mNode( NULL ), mValue( 0 ) {} 00467 00468 //! constructor used by Range 00469 const_iterator( const PairNode* iter, const EntityHandle val ) 00470 : mNode( const_cast< PairNode* >( iter ) ), mValue( val ) 00471 { 00472 } 00473 00474 //! dereference that value this iterator points to 00475 //! returns a const reference 00476 const EntityHandle& operator*() const 00477 { 00478 return mValue; 00479 } 00480 00481 //! prefix incrementer 00482 const_iterator& operator++() 00483 { 00484 // see if we need to increment the base iterator 00485 if( mValue == mNode->second ) 00486 { 00487 mNode = mNode->mNext; 00488 mValue = mNode->first; 00489 } 00490 // if not, just increment the value in the range 00491 else 00492 ++mValue; 00493 return *this; 00494 } 00495 00496 //! postfix incrementer 00497 const_iterator operator++( int ) 00498 { 00499 // make a temporary copy 00500 const_iterator tmp( *this ); 00501 // increment self 00502 this->operator++(); 00503 // return the copy 00504 return tmp; 00505 } 00506 00507 //! prefix decrementer 00508 const_iterator& operator--() 00509 { 00510 // see if we need to decrement the base iterator 00511 if( mValue == mNode->first ) 00512 { 00513 mNode = mNode->mPrev; 00514 ; 00515 mValue = mNode->second; 00516 } 00517 // if not, just decrement the value 00518 else 00519 --mValue; 00520 return *this; 00521 } 00522 00523 //! postfix decrementer 00524 const_iterator operator--( int ) 00525 { 00526 // make a copy of this 00527 const_iterator tmp( *this ); 00528 // decrement self 00529 this->operator--(); 00530 // return the copy 00531 return tmp; 00532 } 00533 00534 //! Advance iterator specified amount. 00535 //! Potentially O(n), but typically better. Always 00536 //! more efficient than calling operator++ step times. 00537 const_iterator& operator+=( EntityID step ); 00538 00539 //! Regress iterator specified amount. 00540 //! Potentially O(n), but typically better. Always 00541 //! more efficient than calling operator-- step times. 00542 const_iterator& operator-=( EntityID step ); 00543 00544 //! equals operator 00545 bool operator==( const const_iterator& other ) const 00546 { 00547 // see if the base iterator is the same and the 00548 // value of this iterator is the same 00549 return ( mNode == other.mNode ) && ( mValue == other.mValue ); 00550 } 00551 00552 //! not equals operator 00553 bool operator!=( const const_iterator& other ) const 00554 { 00555 // call == operator and not it. 00556 return ( mNode != other.mNode ) || ( mValue != other.mValue ); 00557 } 00558 00559 /**\brief get an iterator at the end of the block 00560 * 00561 * Get an iterator at the end of the block of consecutive 00562 * handles that this iterator is currently contained in. 00563 * That is, if the range contains blocks of consecutive 00564 * handles of the form { [1,5], [7,100], ... } and this 00565 * iterator is at any handle in the range [7,100], return 00566 * an iterator at the '100' handle. 00567 * 00568 * Never returns begin() or end() unless this iterator is 00569 * at begin() or end(). May return the same location as 00570 * this iterator. 00571 */ 00572 inline const_iterator end_of_block() const; 00573 00574 /**\brief get an iterator at the start of the block 00575 * 00576 * Get an iterator at the start of the block of consecutive 00577 * handles that this iterator is currently contained in. 00578 * That is, if the range contains blocks of consecutive 00579 * handles of the form { [1,5], [7,100], ... } and this 00580 * iterator is at any handle in the range [7,100], return 00581 * an iterator at the '7' handle. 00582 * 00583 * Never returns end() unless this iterator is 00584 * at end(). May return the same location as 00585 * this iterator. 00586 */ 00587 inline const_iterator start_of_block() const; 00588 00589 protected: 00590 //! the node we are pointing at 00591 PairNode* mNode; 00592 //! the value in the range 00593 EntityHandle mValue; 00594 }; 00595 00596 //! a const reverse iterator which iterates over an Range 00597 class const_reverse_iterator : public range_base_iter 00598 { 00599 friend class Range; 00600 friend class pair_iterator; 00601 00602 public: 00603 //! default constructor - intialize base default constructor 00604 const_reverse_iterator() {} 00605 00606 const_reverse_iterator( const_iterator fwd_iter ) : myIter( fwd_iter ) {} 00607 00608 //! constructor used by Range 00609 const_reverse_iterator( const PairNode* iter, const EntityHandle val ) : myIter( iter, val ) {} 00610 00611 //! dereference that value this iterator points to 00612 //! returns a const reference 00613 const EntityHandle& operator*() const 00614 { 00615 return *myIter; 00616 } 00617 00618 //! prefix incrementer 00619 const_reverse_iterator& operator++() 00620 { 00621 --myIter; 00622 return *this; 00623 } 00624 00625 //! postfix incrementer 00626 const_reverse_iterator operator++( int ) 00627 { 00628 return const_reverse_iterator( myIter-- ); 00629 } 00630 00631 //! prefix decrementer 00632 const_reverse_iterator& operator--() 00633 { 00634 ++myIter; 00635 return *this; 00636 } 00637 00638 //! postfix decrementer 00639 const_reverse_iterator operator--( int ) 00640 { 00641 return const_reverse_iterator( myIter++ ); 00642 } 00643 00644 //! Advance iterator specified amount. 00645 //! Potentially O(n), but typically better. Always 00646 //! more efficient than calling operator++ step times. 00647 const_reverse_iterator& operator+=( EntityID step ) 00648 { 00649 myIter -= step; 00650 return *this; 00651 } 00652 00653 //! Regress iterator specified amount. 00654 //! Potentially O(n), but typically better. Always 00655 //! more efficient than calling operator-- step times. 00656 const_reverse_iterator& operator-=( EntityID step ) 00657 { 00658 myIter += step; 00659 return *this; 00660 } 00661 00662 //! equals operator 00663 bool operator==( const const_reverse_iterator& other ) const 00664 { 00665 return myIter == other.myIter; 00666 } 00667 00668 //! not equals operator 00669 bool operator!=( const const_reverse_iterator& other ) const 00670 { 00671 return myIter != other.myIter; 00672 } 00673 00674 protected: 00675 //! the node we are pointing at 00676 const_iterator myIter; 00677 }; 00678 00679 public: 00680 class const_pair_iterator 00681 { 00682 public: 00683 const_pair_iterator() : myNode( NULL ) {} 00684 const_pair_iterator( const PairNode* node ) : myNode( node ) {} 00685 const_pair_iterator( const const_iterator& i ) : myNode( i.mNode ) {} 00686 00687 const PairNode& operator*() const 00688 { 00689 return *myNode; 00690 } 00691 00692 const PairNode* operator->() const 00693 { 00694 return myNode; 00695 } 00696 00697 const_pair_iterator& operator--() 00698 { 00699 myNode = myNode->mPrev; 00700 return *this; 00701 } 00702 00703 const_pair_iterator& operator++() 00704 { 00705 myNode = myNode->mNext; 00706 return *this; 00707 } 00708 00709 const_pair_iterator operator--( int ) 00710 { 00711 const_pair_iterator rval( *this ); 00712 this->operator--(); 00713 return rval; 00714 } 00715 00716 const_pair_iterator operator++( int ) 00717 { 00718 const_pair_iterator rval( *this ); 00719 this->operator++(); 00720 return rval; 00721 } 00722 00723 bool operator==( const const_pair_iterator& other ) const 00724 { 00725 return other.myNode == myNode; 00726 } 00727 00728 bool operator!=( const const_pair_iterator& other ) const 00729 { 00730 return other.myNode != myNode; 00731 } 00732 00733 private: 00734 const PairNode* myNode; 00735 }; 00736 00737 pair_iterator pair_begin() 00738 { 00739 return pair_iterator( mHead.mNext ); 00740 } 00741 pair_iterator pair_end() 00742 { 00743 return pair_iterator( &mHead ); 00744 } 00745 00746 const_pair_iterator const_pair_begin() const 00747 { 00748 return const_pair_iterator( mHead.mNext ); 00749 } 00750 const_pair_iterator const_pair_end() const 00751 { 00752 return const_pair_iterator( &mHead ); 00753 } 00754 const_pair_iterator pair_begin() const 00755 { 00756 return const_pair_iterator( mHead.mNext ); 00757 } 00758 const_pair_iterator pair_end() const 00759 { 00760 return const_pair_iterator( &mHead ); 00761 } 00762 }; 00763 00764 //! intersect two ranges, placing the results in the return range 00765 Range intersect( const Range&, const Range& ); 00766 00767 //! subtract range2 from this, placing the results in the return range 00768 Range subtract( const Range& from, const Range& ); 00769 00770 //! unite two ranges, placing the results in the return range 00771 inline Range unite( const Range& r1, const Range& r2 ) 00772 { 00773 Range r( r1 ); 00774 r.insert( r2.begin(), r2.end() ); 00775 return r; 00776 } 00777 00778 inline Range::const_iterator operator+( const Range::const_iterator& it, EntityID step ) 00779 { 00780 Range::const_iterator tmp( it ); 00781 return tmp += step; 00782 } 00783 00784 inline Range::const_iterator operator+( EntityID step, const Range::const_iterator& it ) 00785 { 00786 Range::const_iterator tmp( it ); 00787 return tmp += step; 00788 } 00789 00790 inline Range::const_iterator operator-( const Range::const_iterator& it, EntityID step ) 00791 { 00792 Range::const_iterator tmp( it ); 00793 return tmp -= step; 00794 } 00795 00796 inline Range::const_iterator operator-( EntityID step, const Range::const_iterator& it ) 00797 { 00798 Range::const_iterator tmp( it ); 00799 return tmp -= step; 00800 } 00801 00802 EntityID operator-( const Range::const_iterator& it1, const Range::const_iterator& it2 ); 00803 00804 //! Use as you would an STL back_inserter 00805 /** 00806 * e.g. std::copy(list.begin(), list.end(), range_inserter(my_range); 00807 * Also, see comments/instructions at the top of this class declaration 00808 */ 00809 class range_inserter 00810 { 00811 00812 protected: 00813 Range* container; 00814 00815 public: 00816 // constructor 00817 explicit range_inserter( Range& x ) : container( &x ) {} 00818 range_inserter& operator=( const Range::value_type& value ) 00819 { 00820 container->insert( value ); 00821 return *this; 00822 } 00823 00824 range_inserter& operator*() 00825 { 00826 return *this; 00827 } 00828 range_inserter& operator++() 00829 { 00830 return *this; 00831 } 00832 range_inserter& operator++( int ) 00833 { 00834 return *this; 00835 } 00836 00837 typedef EntityHandle value_type; 00838 typedef EntityID difference_type; 00839 typedef std::output_iterator_tag iterator_category; 00840 typedef EntityHandle* pointer; 00841 typedef EntityHandle& reference; 00842 }; 00843 00844 inline Range::Range() 00845 { 00846 // set the head node to point to itself 00847 mHead.mNext = mHead.mPrev = &mHead; 00848 mHead.first = mHead.second = 0; 00849 } 00850 00851 //! destructor 00852 inline Range::~Range() 00853 { 00854 clear(); 00855 } 00856 00857 //! return the beginning const iterator of this range 00858 inline Range::const_iterator Range::begin() const 00859 { 00860 return const_iterator( mHead.mNext, mHead.mNext->first ); 00861 } 00862 00863 //! return the beginning const reverse iterator of this range 00864 inline Range::const_reverse_iterator Range::rbegin() const 00865 { 00866 return const_reverse_iterator( mHead.mPrev, mHead.mPrev->second ); 00867 } 00868 00869 //! return the ending const iterator for this range 00870 inline Range::const_iterator Range::end() const 00871 { 00872 return const_iterator( &mHead, mHead.first ); 00873 } 00874 00875 //! return the ending const reverse iterator for this range 00876 inline Range::const_reverse_iterator Range::rend() const 00877 { 00878 return const_reverse_iterator( &mHead, mHead.second ); 00879 } 00880 00881 //! return whether empty or not 00882 //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())" 00883 inline bool Range::empty() const 00884 { 00885 return ( mHead.mNext == &mHead ); 00886 } 00887 00888 //! erases a value from this container 00889 inline Range::iterator Range::erase( EntityHandle val ) 00890 { 00891 return erase( find( val ) ); 00892 } 00893 00894 inline Range::const_iterator Range::const_iterator::end_of_block() const 00895 { 00896 return Range::const_iterator( mNode, mNode->second ); 00897 } 00898 00899 inline Range::const_iterator Range::const_iterator::start_of_block() const 00900 { 00901 return Range::const_iterator( mNode, mNode->first ); 00902 } 00903 00904 //! get first entity in range 00905 inline const EntityHandle& Range::front() const 00906 { 00907 return mHead.mNext->first; 00908 } 00909 //! get last entity in range 00910 inline const EntityHandle& Range::back() const 00911 { 00912 return mHead.mPrev->second; 00913 } 00914 00915 inline std::ostream& operator<<( std::ostream& s, const Range& r ) 00916 { 00917 r.print( s ); 00918 return s; 00919 } 00920 00921 bool operator==( const Range& r1, const Range& r2 ); 00922 inline bool operator!=( const Range& r1, const Range& r2 ) 00923 { 00924 return !( r1 == r2 ); 00925 } 00926 00927 inline EntityHandle Range::operator[]( EntityID indexp ) const 00928 { 00929 Range::const_iterator i = begin(); 00930 i += indexp; 00931 return *i; 00932 } 00933 00934 inline int Range::index( EntityHandle handle ) const 00935 { 00936 if( handle < *begin() || handle > *rbegin() ) return -1; 00937 00938 unsigned int i = 0; 00939 Range::const_pair_iterator pit = const_pair_begin(); 00940 while( handle > ( *pit ).second && pit != const_pair_end() ) 00941 { 00942 i += ( *pit ).second - ( *pit ).first + 1; 00943 ++pit; 00944 } 00945 if( handle < ( *pit ).first || pit == const_pair_end() ) return -1; 00946 00947 return i + handle - ( *pit ).first; 00948 } 00949 00950 inline double Range::compactness() const 00951 { 00952 unsigned int num_ents = size(); 00953 return ( num_ents ? ( (double)get_memory_use() / (double)( num_ents * sizeof( EntityHandle ) ) ) : -1 ); 00954 } 00955 00956 template < typename Iterator > 00957 Range::iterator Range::insert_list( Iterator begin_iter, Iterator end_iter ) 00958 { 00959 size_t n = std::distance( begin_iter, end_iter ); 00960 EntityHandle* sorted = new EntityHandle[n]; 00961 std::copy( begin_iter, end_iter, sorted ); 00962 std::sort( sorted, sorted + n ); 00963 iterator hint = begin(); 00964 size_t i = 0; 00965 while( i < n ) 00966 { 00967 size_t j = i + 1; 00968 while( j < n && sorted[j] == 1 + sorted[j - 1] ) 00969 ++j; 00970 hint = insert( hint, sorted[i], sorted[i] + ( ( j - i ) - 1 ) ); 00971 i = j; 00972 } 00973 delete[] sorted; 00974 return hint; 00975 } 00976 00977 inline size_t Range::psize() const 00978 { 00979 size_t i = 0; 00980 Range::const_pair_iterator pit; 00981 for( pit = const_pair_begin(), i = 0; pit != const_pair_end(); ++pit, i++ ) 00982 ; 00983 00984 return i; 00985 } 00986 00987 } // namespace moab 00988 00989 #endif // MOAB_RANGE_HPP