moab
Range.hpp
Go to the documentation of this file.
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines