moab
|
00001 00164 #ifndef MOAB_RANGE_HPP 00165 #define MOAB_RANGE_HPP 00166 00167 #include <iterator> 00168 #include <iosfwd> 00169 #include <algorithm> 00170 #include "moab/Types.hpp" 00171 00172 namespace moab { 00173 00174 struct range_iter_tag : public std::bidirectional_iterator_tag {}; 00175 00176 struct range_base_iter 00177 { 00178 typedef range_iter_tag iterator_category; 00179 typedef EntityID difference_type; 00180 typedef EntityHandle value_type; 00181 typedef EntityHandle* pointer; 00182 typedef EntityHandle& reference; 00183 }; 00184 00185 00187 class Range 00188 { 00189 public: 00190 00191 // forward declare the iterators 00192 class const_iterator; 00193 class const_reverse_iterator; 00194 typedef const_iterator iterator; 00195 typedef const_reverse_iterator reverse_iterator; 00196 00197 friend Range intersect( const Range&, const Range& ); 00198 friend Range subtract( const Range&, const Range& ); 00199 00201 Range &operator-=(const Range &rhs); 00202 00205 typedef EntityHandle value_type; 00206 00208 Range(); 00209 00211 Range(const Range& copy); 00212 00214 Range( EntityHandle val1, EntityHandle val2 ); 00215 00217 Range& operator=(const Range& copy); 00218 00220 inline ~Range(); 00221 00223 inline const_iterator begin() const; 00224 00226 inline const_reverse_iterator rbegin() const; 00227 00229 inline const_iterator end() const; 00230 00232 inline const_reverse_iterator rend() const; 00233 00235 size_t size() const; 00236 00238 size_t psize() const; 00239 00242 inline bool empty() const; 00243 00244 iterator insert( iterator hint, EntityHandle val ); 00245 00247 iterator insert(EntityHandle val) 00248 { return insert( begin(), val ); } 00249 00252 iterator insert( iterator hint, EntityHandle first, EntityHandle last ); 00253 00256 iterator insert(EntityHandle val1, EntityHandle val2) 00257 { return insert( begin(), val1, val2 ); } 00258 00259 template <typename T> 00260 iterator insert_list( T begin_iter, T end_iter ); 00261 00262 template <class T> 00263 iterator insert( typename T::const_iterator begin_iter, typename T::const_iterator end_iter ) 00264 { return insert_list( begin_iter, end_iter ); } 00265 00266 template <typename T> 00267 iterator insert( const T* begin_iter, const T* end_iter ) 00268 { return insert_list( begin_iter, end_iter ); } 00269 00271 iterator erase(iterator iter); 00272 00274 iterator erase( iterator iter1, iterator iter2); 00275 00277 inline iterator erase(EntityHandle val); 00278 00280 inline const EntityHandle& front() const; 00282 inline const EntityHandle& back() const; 00284 EntityHandle pop_front(); 00286 EntityHandle pop_back(); 00287 00289 const_iterator find(EntityHandle val) const; 00290 00292 static const_iterator lower_bound(const_iterator first, 00293 const_iterator last, 00294 EntityHandle val); 00295 static const_iterator upper_bound(const_iterator first, 00296 const_iterator last, 00297 EntityHandle val); 00298 00299 const_iterator lower_bound( EntityHandle val ) const 00300 { return lower_bound( begin(), end(), val ); } 00301 const_iterator upper_bound( EntityHandle val ) const 00302 { return upper_bound( begin(), end(), val ); } 00303 const_iterator lower_bound( EntityType type ) const; 00304 const_iterator upper_bound( EntityType type ) const; 00305 std::pair<const_iterator, const_iterator> equal_range( EntityType type ) const; 00306 const_iterator lower_bound( EntityType type, const_iterator first ) const; 00307 const_iterator upper_bound( EntityType type, const_iterator first ) const; 00308 00311 bool all_of_type( EntityType type ) const; 00314 bool all_of_dimension( int dimension ) const; 00315 00316 unsigned num_of_type( EntityType type ) const; 00317 unsigned num_of_dimension( int dim ) const; 00318 00320 void clear(); 00321 00323 void print(const char *indent_prefix = NULL) const; 00324 void print(std::ostream& s, const char *indent_prefix = NULL) const; 00325 00326 unsigned long get_memory_use() const; 00327 00328 double compactness() const; 00329 00330 void insert( Range::const_iterator begin, 00331 Range::const_iterator end ); 00332 00334 void merge( const Range& range ) 00335 { insert( range.begin(), range.end() ); } 00336 00338 void merge( Range::const_iterator beginr, 00339 Range::const_iterator endr ) 00340 { insert( beginr, endr ); } 00341 00343 void swap( Range &range ); 00344 00346 void sanity_check() const; 00347 00349 bool contains( const Range& other ) const; 00350 00352 Range subset_by_type(EntityType t) const; 00353 00355 Range subset_by_dimension(int dim) const; 00356 00357 struct PairNode : public std::pair<EntityHandle,EntityHandle> 00358 { 00359 00360 PairNode() : std::pair<EntityHandle,EntityHandle>(0, 0), mNext(NULL), mPrev(NULL) {} 00361 PairNode(PairNode* next, PairNode* prev, 00362 EntityHandle _first, EntityHandle _second) 00363 : std::pair<EntityHandle,EntityHandle>(_first,_second), mNext(next), mPrev(prev) {} 00364 00365 PairNode* mNext; 00366 PairNode* mPrev; 00367 }; 00368 00369 00370 EntityHandle operator[](EntityID index) const; 00371 00372 int index(EntityHandle handle) const; 00373 00374 protected: 00375 00378 PairNode mHead; 00379 00381 void delete_pair_node( PairNode* dead_node ); 00382 00383 public: 00384 00386 class pair_iterator : public range_base_iter 00387 { 00388 friend class Range; 00389 public: 00390 pair_iterator() : mNode(NULL) {} 00391 pair_iterator(PairNode *nodep) : mNode(nodep) {} 00392 pair_iterator(const pair_iterator& copy) 00393 : mNode(copy.mNode) {} 00394 pair_iterator(const const_iterator& copy) 00395 : mNode(copy.mNode) {} 00396 00397 std::pair<EntityHandle,EntityHandle>* operator->() { return mNode; } 00398 00399 pair_iterator& operator++() 00400 { 00401 mNode = mNode->mNext; 00402 return *this; 00403 } 00404 pair_iterator operator++(int) 00405 { 00406 pair_iterator tmp(*this); 00407 this->operator ++(); 00408 return tmp; 00409 } 00410 00411 pair_iterator& operator--() 00412 { 00413 mNode = mNode->mPrev; 00414 return *this; 00415 } 00416 pair_iterator operator--(int) 00417 { 00418 pair_iterator tmp(*this); 00419 this->operator--(); 00420 return tmp; 00421 } 00422 bool operator==(const pair_iterator& other) const 00423 { 00424 return mNode == other.mNode; 00425 } 00426 00427 bool operator!=(const pair_iterator& other) const 00428 { 00429 return mNode != other.mNode; 00430 } 00431 00432 PairNode* node() { return mNode; } 00433 00434 private: 00435 00436 PairNode* mNode; 00437 }; 00438 00439 class const_pair_iterator; 00440 00442 class const_iterator : public range_base_iter 00443 { 00444 friend class Range; 00445 friend class pair_iterator; 00446 friend class const_pair_iterator; 00447 friend EntityID operator-( const const_iterator&, const const_iterator& ); 00448 public: 00450 const_iterator() : mNode(NULL), mValue(0) {} 00451 00453 const_iterator( const PairNode* iter, const EntityHandle val) 00454 : mNode(const_cast<PairNode*>(iter)), mValue(val) {} 00455 00458 const EntityHandle& operator*() const { return mValue; } 00459 00461 const_iterator& operator++() 00462 { 00463 // see if we need to increment the base iterator 00464 if(mValue == mNode->second) 00465 { 00466 mNode = mNode->mNext; 00467 mValue = mNode->first; 00468 } 00469 // if not, just increment the value in the range 00470 else 00471 ++mValue; 00472 return *this; 00473 } 00474 00476 const_iterator operator++(int) 00477 { 00478 // make a temporary copy 00479 const_iterator tmp(*this); 00480 // increment self 00481 this->operator ++(); 00482 // return the copy 00483 return tmp; 00484 } 00485 00487 const_iterator& operator--() 00488 { 00489 // see if we need to decrement the base iterator 00490 if(mValue == mNode->first) 00491 { 00492 mNode = mNode->mPrev;; 00493 mValue = mNode->second; 00494 } 00495 // if not, just decrement the value 00496 else 00497 --mValue; 00498 return *this; 00499 } 00500 00502 const_iterator operator--(int) 00503 { 00504 // make a copy of this 00505 const_iterator tmp(*this); 00506 // decrement self 00507 this->operator --(); 00508 // return the copy 00509 return tmp; 00510 } 00511 00515 const_iterator& operator+=( EntityID step ); 00516 00520 const_iterator& operator-=( EntityID step ); 00521 00523 bool operator==( const const_iterator& other ) const 00524 { 00525 // see if the base iterator is the same and the 00526 // value of this iterator is the same 00527 return (mNode == other.mNode) && (mValue == other.mValue); 00528 } 00529 00531 bool operator!=( const const_iterator& other ) const 00532 { 00533 // call == operator and not it. 00534 return (mNode != other.mNode) || (mValue != other.mValue); 00535 } 00536 00550 inline const_iterator end_of_block() const; 00551 00565 inline const_iterator start_of_block() const; 00566 00567 protected: 00568 00570 PairNode* mNode; 00572 EntityHandle mValue; 00573 }; 00574 00576 class const_reverse_iterator : public range_base_iter 00577 { 00578 friend class Range; 00579 friend class pair_iterator; 00580 public: 00582 const_reverse_iterator() {} 00583 00584 const_reverse_iterator( const_iterator fwd_iter ) : myIter(fwd_iter) {} 00585 00587 const_reverse_iterator( const PairNode* iter, const EntityHandle val) 00588 : myIter(iter, val) {} 00589 00592 const EntityHandle& operator*() const { return *myIter; } 00593 00595 const_reverse_iterator& operator++() 00596 { 00597 --myIter; 00598 return *this; 00599 } 00600 00602 const_reverse_iterator operator++(int) 00603 { 00604 return const_reverse_iterator( myIter-- ); 00605 } 00606 00608 const_reverse_iterator& operator--() 00609 { 00610 ++myIter; 00611 return *this; 00612 } 00613 00615 const_reverse_iterator operator--(int) 00616 { 00617 return const_reverse_iterator( myIter++ ); 00618 } 00619 00623 const_reverse_iterator& operator+=( EntityID step ) 00624 { 00625 myIter -= step; 00626 return *this; 00627 } 00628 00632 const_reverse_iterator& operator-=( EntityID step ) 00633 { 00634 myIter += step; 00635 return *this; 00636 } 00637 00639 bool operator==( const const_reverse_iterator& other ) const 00640 { 00641 return myIter == other.myIter; 00642 } 00643 00645 bool operator!=( const const_reverse_iterator& other ) const 00646 { 00647 return myIter != other.myIter; 00648 } 00649 00650 protected: 00651 00653 const_iterator myIter; 00654 }; 00655 00656 public: 00657 00658 class const_pair_iterator { 00659 public: 00660 const_pair_iterator() : myNode(NULL) {} 00661 const_pair_iterator( const PairNode* node ) : myNode(node) {} 00662 const_pair_iterator( const const_iterator& i ) : myNode(i.mNode) {} 00663 00664 const PairNode& operator*() const 00665 { return *myNode; } 00666 00667 const PairNode* operator->() const 00668 { return myNode; } 00669 00670 const_pair_iterator& operator--() 00671 { myNode = myNode->mPrev; return *this; } 00672 00673 const_pair_iterator& operator++() 00674 { myNode = myNode->mNext; return *this; } 00675 00676 const_pair_iterator operator--(int) 00677 { const_pair_iterator rval(*this); this->operator--(); return rval; } 00678 00679 const_pair_iterator operator++(int) 00680 { const_pair_iterator rval(*this); this->operator++(); return rval; } 00681 00682 bool operator==( const const_pair_iterator& other ) const 00683 { return other.myNode == myNode; } 00684 00685 bool operator!=( const const_pair_iterator& other ) const 00686 { return other.myNode != myNode; } 00687 00688 private: 00689 const PairNode* myNode; 00690 }; 00691 00692 pair_iterator pair_begin() { return pair_iterator(mHead.mNext); } 00693 pair_iterator pair_end() { return pair_iterator(&mHead); } 00694 00695 const_pair_iterator const_pair_begin() const { return const_pair_iterator( mHead.mNext ); } 00696 const_pair_iterator const_pair_end() const { return const_pair_iterator( &mHead ); } 00697 const_pair_iterator pair_begin() const { return const_pair_iterator( mHead.mNext ); } 00698 const_pair_iterator pair_end() const { return const_pair_iterator( &mHead ); } 00699 00700 }; 00701 00702 00704 Range intersect( const Range&, const Range& ); 00705 00707 Range subtract( const Range& from, const Range& ); 00708 00710 inline Range unite( const Range& r1, const Range& r2 ) 00711 { Range r(r1); r.insert(r2.begin(), r2.end()); return r; } 00712 00713 00714 inline Range::const_iterator 00715 operator+( const Range::const_iterator& it, EntityID step ) 00716 { Range::const_iterator tmp(it); return tmp += step; } 00717 00718 inline Range::const_iterator 00719 operator+( EntityID step, const Range::const_iterator& it ) 00720 { Range::const_iterator tmp(it); return tmp += step; } 00721 00722 inline Range::const_iterator 00723 operator-( const Range::const_iterator& it, EntityID step ) 00724 { Range::const_iterator tmp(it); return tmp -= step; } 00725 00726 inline Range::const_iterator 00727 operator-( EntityID step, const Range::const_iterator& it ) 00728 { Range::const_iterator tmp(it); return tmp -= step; } 00729 00730 EntityID 00731 operator-( const Range::const_iterator& it1, const Range::const_iterator& it2 ); 00732 00734 00738 class range_inserter 00739 { 00740 00741 protected: 00742 Range* container; 00743 00744 public: 00745 //constructor 00746 explicit range_inserter(Range& x) : container(&x) {} 00747 range_inserter& 00748 operator=(const Range::value_type& value) 00749 { 00750 container->insert(value); 00751 return *this; 00752 } 00753 00754 range_inserter& operator*() { return *this; } 00755 range_inserter& operator++() { return *this; } 00756 range_inserter& operator++(int) { return *this; } 00757 00758 typedef EntityHandle value_type; 00759 typedef EntityID difference_type; 00760 typedef std::output_iterator_tag iterator_category; 00761 typedef EntityHandle* pointer; 00762 typedef EntityHandle& reference; 00763 }; 00764 00765 00766 inline Range::Range() 00767 { 00768 // set the head node to point to itself 00769 mHead.mNext = mHead.mPrev = &mHead; 00770 mHead.first = mHead.second = 0; 00771 } 00772 00774 inline Range::~Range() 00775 { 00776 clear(); 00777 } 00778 00780 inline Range::const_iterator Range::begin() const 00781 { 00782 return const_iterator(mHead.mNext, mHead.mNext->first); 00783 } 00784 00786 inline Range::const_reverse_iterator Range::rbegin() const 00787 { 00788 return const_reverse_iterator(mHead.mPrev, mHead.mPrev->second); 00789 } 00790 00792 inline Range::const_iterator Range::end() const 00793 { 00794 return const_iterator(&mHead, mHead.first); 00795 } 00796 00798 inline Range::const_reverse_iterator Range::rend() const 00799 { 00800 return const_reverse_iterator(&mHead, mHead.second); 00801 } 00802 00805 inline bool Range::empty() const 00806 { 00807 return (mHead.mNext == &mHead); 00808 } 00809 00811 inline Range::iterator Range::erase(EntityHandle val) 00812 { 00813 return erase(find(val)); 00814 } 00815 00816 inline Range::const_iterator Range::const_iterator::end_of_block() const 00817 { return Range::const_iterator( mNode, mNode->second ); } 00818 00819 inline Range::const_iterator Range::const_iterator::start_of_block() const 00820 { return Range::const_iterator( mNode, mNode->first ); } 00821 00823 inline const EntityHandle& Range::front() const 00824 { return mHead.mNext->first; } 00826 inline const EntityHandle& Range::back() const 00827 { return mHead.mPrev->second; } 00828 00829 inline std::ostream& operator<<( std::ostream& s, const Range& r ) 00830 { r.print(s); return s; } 00831 00832 bool operator==( const Range& r1, const Range& r2 ); 00833 inline bool operator!=( const Range& r1, const Range& r2 ) 00834 { return !(r1 == r2); } 00835 00836 inline EntityHandle Range::operator[](EntityID indexp) const 00837 { 00838 Range::const_iterator i = begin(); 00839 i += indexp; 00840 return *i; 00841 } 00842 00843 inline int Range::index(EntityHandle handle) const 00844 { 00845 if (handle < *begin() || handle > *rbegin()) return -1; 00846 00847 unsigned int i = 0; 00848 Range::const_pair_iterator pit = const_pair_begin(); 00849 while (handle > (*pit).second && pit != const_pair_end()) { 00850 i += (*pit).second - (*pit).first + 1; 00851 pit++; 00852 } 00853 if (handle < (*pit).first || pit == const_pair_end()) return -1; 00854 00855 return i + handle - (*pit).first; 00856 } 00857 00858 inline double Range::compactness() const 00859 { 00860 unsigned int num_ents = size(); 00861 return (num_ents ? ((double)get_memory_use() / (double) (num_ents*sizeof(EntityHandle))) : -1); 00862 } 00863 00864 template <typename Iterator> 00865 Range::iterator Range::insert_list( Iterator begin_iter, Iterator end_iter ) 00866 { 00867 size_t n = std::distance(begin_iter, end_iter); 00868 EntityHandle* sorted = new EntityHandle[n]; 00869 std::copy( begin_iter, end_iter, sorted ); 00870 std::sort( sorted, sorted + n ); 00871 iterator hint = begin(); 00872 size_t i = 0; 00873 while (i < n) { 00874 size_t j = i + 1; 00875 while (j < n && sorted[j] == 1+sorted[j-1]) 00876 ++j; 00877 hint = insert( hint, sorted[i], sorted[i] + ((j - i) - 1) ); 00878 i = j; 00879 } 00880 delete [] sorted; 00881 return hint; 00882 } 00883 00884 inline size_t Range::psize() const 00885 { 00886 size_t i = 0; 00887 Range::const_pair_iterator pit; 00888 for (pit = const_pair_begin(), i = 0; 00889 pit != const_pair_end(); pit++, i++); 00890 00891 return i; 00892 } 00893 00894 } // namespace moab 00895 00896 #endif // MOAB_RANGE_HPP 00897 00898 00899