MOAB: Mesh Oriented datABase  (version 5.2.1)
Range.hpp
Go to the documentation of this file.
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 <string>
00171 
00172 #include "moab/Types.hpp"
00173 
00174 namespace moab
00175 {
00176 
00177 struct range_iter_tag : public std::bidirectional_iterator_tag
00178 {
00179 };
00180 
00181 struct range_base_iter
00182 {
00183     typedef range_iter_tag iterator_category;
00184     typedef EntityID difference_type;
00185     typedef EntityHandle value_type;
00186     typedef EntityHandle* pointer;
00187     typedef EntityHandle& reference;
00188 };
00189 
00190 //! the class Range
00191 class Range
00192 {
00193   public:
00194     // forward declare the iterators
00195     class const_iterator;
00196     class const_reverse_iterator;
00197     typedef const_iterator iterator;
00198     typedef const_reverse_iterator reverse_iterator;
00199 
00200     friend Range intersect( const Range&, const Range& );
00201     friend Range subtract( const Range&, const Range& );
00202 
00203     //! just like subtract, but as an operator
00204     Range& operator-=( const Range& rhs );
00205 
00206     //! for short hand notation, lets typedef the
00207     //! container class that holds the ranges
00208     typedef EntityHandle value_type;
00209 
00210     //! default constructor
00211     Range();
00212 
00213     //! copy constructor
00214     Range( const Range& copy );
00215 
00216     //! another constructor that takes an initial range
00217     Range( EntityHandle val1, EntityHandle val2 );
00218 
00219     //! operator=
00220     Range& operator=( const Range& copy );
00221 
00222     //! destructor
00223     inline ~Range();
00224 
00225     //! return the beginning const iterator of this range
00226     inline const_iterator begin() const;
00227 
00228     //! return the beginning const reverse iterator of this range
00229     inline const_reverse_iterator rbegin() const;
00230 
00231     //! return the ending const iterator for this range
00232     inline const_iterator end() const;
00233 
00234     //! return the ending const reverse iterator for this range
00235     inline const_reverse_iterator rend() const;
00236 
00237     //! return the number of values this Ranges represents
00238     size_t size() const;
00239 
00240     //! return the number of range pairs in the list
00241     size_t psize() const;
00242 
00243     //! return whether empty or not
00244     //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
00245     inline bool empty() const;
00246 
00247     iterator insert( iterator hint, EntityHandle val );
00248 
00249     //! insert an item into the list and return the iterator for the inserted item
00250     iterator insert( EntityHandle val )
00251     {
00252         return insert( begin(), val );
00253     }
00254 
00255     //! insert a range of items into this list and return the iterator for the first
00256     //! inserted item
00257     iterator insert( iterator hint, EntityHandle first, EntityHandle last );
00258 
00259     //! insert a range of items into this list and return the iterator for the first
00260     //! inserted item
00261     iterator insert( EntityHandle val1, EntityHandle val2 )
00262     {
00263         return insert( begin(), val1, val2 );
00264     }
00265 
00266     template < typename T >
00267     iterator insert_list( T begin_iter, T end_iter );
00268 
00269     template < class T >
00270     iterator insert( typename T::const_iterator begin_iter, typename T::const_iterator end_iter )
00271     {
00272         return insert_list( begin_iter, end_iter );
00273     }
00274 
00275     template < typename T >
00276     iterator insert( const T* begin_iter, const T* end_iter )
00277     {
00278         return insert_list( begin_iter, end_iter );
00279     }
00280 
00281     //! remove an item from this list and return an iterator to the next item
00282     iterator erase( iterator iter );
00283 
00284     //! remove a range of items from the list
00285     iterator erase( iterator iter1, iterator iter2 );
00286 
00287     //! erases a value from this container
00288     inline iterator erase( EntityHandle val );
00289 
00290     //! get first entity in range
00291     inline const EntityHandle& front() const;
00292     //! get last entity in range
00293     inline const EntityHandle& back() const;
00294     //! remove first entity from range
00295     EntityHandle pop_front();
00296     //! remove last entity from range
00297     EntityHandle pop_back();
00298 
00299     //! find an item int the list and return an iterator at that value
00300     const_iterator find( EntityHandle val ) const;
00301 
00302     //! return an iterator to the first value >= val
00303     static const_iterator lower_bound( const_iterator first, const_iterator last, EntityHandle val );
00304     static const_iterator upper_bound( const_iterator first, const_iterator last, EntityHandle val );
00305 
00306     const_iterator lower_bound( EntityHandle val ) const
00307     {
00308         return lower_bound( begin(), end(), val );
00309     }
00310     const_iterator upper_bound( EntityHandle val ) const
00311     {
00312         return upper_bound( begin(), end(), val );
00313     }
00314     const_iterator lower_bound( EntityType type ) const;
00315     const_iterator upper_bound( EntityType type ) const;
00316     std::pair< const_iterator, const_iterator > equal_range( EntityType type ) const;
00317     const_iterator lower_bound( EntityType type, const_iterator first ) const;
00318     const_iterator upper_bound( EntityType type, const_iterator first ) const;
00319 
00320     //! True if all entities in range are of passed type
00321     //! (also true if range is empty)
00322     bool all_of_type( EntityType type ) const;
00323     //! True if all entities in range are of passed dimension
00324     //! (also true if range is empty)
00325     bool all_of_dimension( int dimension ) const;
00326 
00327     unsigned num_of_type( EntityType type ) const;
00328     unsigned num_of_dimension( int dim ) const;
00329 
00330     //! clears the contents of the list
00331     void clear();
00332 
00333     //! for debugging
00334     const std::string str_rep( const char* indent_prefix = NULL ) const;
00335 
00336     void print( const char* indent_prefix = NULL ) const;
00337     void print( std::ostream& s, const char* indent_prefix = NULL ) const;
00338 
00339     unsigned long get_memory_use() const;
00340 
00341     double compactness() const;
00342 
00343     void insert( Range::const_iterator begin, Range::const_iterator end );
00344 
00345     //! merges this Range with another range
00346     void merge( const Range& range )
00347     {
00348         insert( range.begin(), range.end() );
00349     }
00350 
00351     //! merge a subset of some other range
00352     void merge( Range::const_iterator beginr, Range::const_iterator endr )
00353     {
00354         insert( beginr, endr );
00355     }
00356 
00357     //! swap the contents of this range with another one
00358     void swap( Range& range );
00359 
00360     //! check for internal consistency
00361     void sanity_check() const;
00362 
00363     //! Check if this range is a non-strict superset of some other range
00364     bool contains( const Range& other ) const;
00365 
00366     //! return a subset of this range, by type
00367     Range subset_by_type( EntityType t ) const;
00368 
00369     //! return a subset of this range, by dimension
00370     Range subset_by_dimension( int dim ) const;
00371 
00372     struct PairNode : public std::pair< EntityHandle, EntityHandle >
00373     {
00374 
00375         PairNode() : std::pair< EntityHandle, EntityHandle >( 0, 0 ), mNext( NULL ), mPrev( NULL ) {}
00376         PairNode( PairNode* next, PairNode* prev, EntityHandle _first, EntityHandle _second )
00377             : std::pair< EntityHandle, EntityHandle >( _first, _second ), mNext( next ), mPrev( prev )
00378         {
00379         }
00380 
00381         PairNode* mNext;
00382         PairNode* mPrev;
00383     };
00384 
00385     EntityHandle operator[]( EntityID index ) const;
00386 
00387     int index( EntityHandle handle ) const;
00388 
00389   protected:
00390     //! the head of the list that contains pairs that represent the ranges
00391     //! this list is sorted and unique at all times
00392     PairNode mHead;
00393 
00394     //! if dead_node is not mHead, remove it from the list and free it's memory.
00395     void delete_pair_node( PairNode* dead_node );
00396 
00397   public:
00398     //! used to iterate over sub-ranges of a range
00399     class pair_iterator : public range_base_iter
00400     {
00401         friend class Range;
00402 
00403       public:
00404         pair_iterator() : mNode( NULL ) {}
00405         pair_iterator( PairNode* nodep ) : mNode( nodep ) {}
00406         pair_iterator( const pair_iterator& copy ) : mNode( copy.mNode ) {}
00407         pair_iterator( const const_iterator& copy ) : mNode( copy.mNode ) {}
00408 
00409         std::pair< EntityHandle, EntityHandle >* operator->()
00410         {
00411             return mNode;
00412         }
00413 
00414         pair_iterator& operator++()
00415         {
00416             mNode = mNode->mNext;
00417             return *this;
00418         }
00419         pair_iterator operator++( int )
00420         {
00421             pair_iterator tmp( *this );
00422             this->operator++();
00423             return tmp;
00424         }
00425 
00426         pair_iterator& operator--()
00427         {
00428             mNode = mNode->mPrev;
00429             return *this;
00430         }
00431         pair_iterator operator--( int )
00432         {
00433             pair_iterator tmp( *this );
00434             this->operator--();
00435             return tmp;
00436         }
00437         bool operator==( const pair_iterator& other ) const
00438         {
00439             return mNode == other.mNode;
00440         }
00441 
00442         bool operator!=( const pair_iterator& other ) const
00443         {
00444             return mNode != other.mNode;
00445         }
00446 
00447         PairNode* node()
00448         {
00449             return mNode;
00450         }
00451 
00452       private:
00453         PairNode* mNode;
00454     };
00455 
00456     class const_pair_iterator;
00457 
00458     //! a const iterator which iterates over an Range
00459     class const_iterator : public range_base_iter
00460     {
00461         friend class Range;
00462         friend class pair_iterator;
00463         friend class const_pair_iterator;
00464         friend EntityID operator-( const const_iterator&, const const_iterator& );
00465 
00466       public:
00467         //! default constructor - intialize base default constructor
00468         const_iterator() : mNode( NULL ), mValue( 0 ) {}
00469 
00470         //! constructor used by Range
00471         const_iterator( const PairNode* iter, const EntityHandle val )
00472             : mNode( const_cast< PairNode* >( iter ) ), mValue( val )
00473         {
00474         }
00475 
00476         //! dereference that value this iterator points to
00477         //! returns a const reference
00478         const EntityHandle& operator*() const
00479         {
00480             return mValue;
00481         }
00482 
00483         //! prefix incrementer
00484         const_iterator& operator++()
00485         {
00486             // see if we need to increment the base iterator
00487             if( mValue == mNode->second )
00488             {
00489                 mNode  = mNode->mNext;
00490                 mValue = mNode->first;
00491             }
00492             // if not, just increment the value in the range
00493             else
00494                 ++mValue;
00495             return *this;
00496         }
00497 
00498         //! postfix incrementer
00499         const_iterator operator++( int )
00500         {
00501             // make a temporary copy
00502             const_iterator tmp( *this );
00503             // increment self
00504             this->operator++();
00505             // return the copy
00506             return tmp;
00507         }
00508 
00509         //! prefix decrementer
00510         const_iterator& operator--()
00511         {
00512             // see if we need to decrement the base iterator
00513             if( mValue == mNode->first )
00514             {
00515                 mNode = mNode->mPrev;
00516                 ;
00517                 mValue = mNode->second;
00518             }
00519             // if not, just decrement the value
00520             else
00521                 --mValue;
00522             return *this;
00523         }
00524 
00525         //! postfix decrementer
00526         const_iterator operator--( int )
00527         {
00528             // make a copy of this
00529             const_iterator tmp( *this );
00530             // decrement self
00531             this->operator--();
00532             // return the copy
00533             return tmp;
00534         }
00535 
00536         //! Advance iterator specified amount.
00537         //! Potentially O(n), but typically better.  Always
00538         //! more efficient than calling operator++ step times.
00539         const_iterator& operator+=( EntityID step );
00540 
00541         //! Regress iterator specified amount.
00542         //! Potentially O(n), but typically better.  Always
00543         //! more efficient than calling operator-- step times.
00544         const_iterator& operator-=( EntityID step );
00545 
00546         //! equals operator
00547         bool operator==( const const_iterator& other ) const
00548         {
00549             // see if the base iterator is the same and the
00550             // value of this iterator is the same
00551             return ( mNode == other.mNode ) && ( mValue == other.mValue );
00552         }
00553 
00554         //! not equals operator
00555         bool operator!=( const const_iterator& other ) const
00556         {
00557             // call == operator and not it.
00558             return ( mNode != other.mNode ) || ( mValue != other.mValue );
00559         }
00560 
00561         /**\brief get an iterator at the end of the block
00562          *
00563          * Get an iterator at the end of the block of consecutive
00564          * handles that this iterator is currently contained in.
00565          * That is, if the range contains blocks of consecutive
00566          * handles of the form { [1,5], [7,100], ... } and this
00567          * iterator is at any handle in the range [7,100], return
00568          * an iterator at the '100' handle.
00569          *
00570          * Never returns begin() or end() unless this iterator is
00571          * at begin() or end().  May return the same location as
00572          * this iterator.
00573          */
00574         inline const_iterator end_of_block() const;
00575 
00576         /**\brief get an iterator at the start of the block
00577          *
00578          * Get an iterator at the start of the block of consecutive
00579          * handles that this iterator is currently contained in.
00580          * That is, if the range contains blocks of consecutive
00581          * handles of the form { [1,5], [7,100], ... } and this
00582          * iterator is at any handle in the range [7,100], return
00583          * an iterator at the '7' handle.
00584          *
00585          * Never returns end() unless this iterator is
00586          * at end().  May return the same location as
00587          * this iterator.
00588          */
00589         inline const_iterator start_of_block() const;
00590 
00591       protected:
00592         //! the node we are pointing at
00593         PairNode* mNode;
00594         //! the value in the range
00595         EntityHandle mValue;
00596     };
00597 
00598     //! a const reverse iterator which iterates over an Range
00599     class const_reverse_iterator : public range_base_iter
00600     {
00601         friend class Range;
00602         friend class pair_iterator;
00603 
00604       public:
00605         //! default constructor - intialize base default constructor
00606         const_reverse_iterator() {}
00607 
00608         const_reverse_iterator( const_iterator fwd_iter ) : myIter( fwd_iter ) {}
00609 
00610         //! constructor used by Range
00611         const_reverse_iterator( const PairNode* iter, const EntityHandle val ) : myIter( iter, val ) {}
00612 
00613         //! dereference that value this iterator points to
00614         //! returns a const reference
00615         const EntityHandle& operator*() const
00616         {
00617             return *myIter;
00618         }
00619 
00620         //! prefix incrementer
00621         const_reverse_iterator& operator++()
00622         {
00623             --myIter;
00624             return *this;
00625         }
00626 
00627         //! postfix incrementer
00628         const_reverse_iterator operator++( int )
00629         {
00630             return const_reverse_iterator( myIter-- );
00631         }
00632 
00633         //! prefix decrementer
00634         const_reverse_iterator& operator--()
00635         {
00636             ++myIter;
00637             return *this;
00638         }
00639 
00640         //! postfix decrementer
00641         const_reverse_iterator operator--( int )
00642         {
00643             return const_reverse_iterator( myIter++ );
00644         }
00645 
00646         //! Advance iterator specified amount.
00647         //! Potentially O(n), but typically better.  Always
00648         //! more efficient than calling operator++ step times.
00649         const_reverse_iterator& operator+=( EntityID step )
00650         {
00651             myIter -= step;
00652             return *this;
00653         }
00654 
00655         //! Regress iterator specified amount.
00656         //! Potentially O(n), but typically better.  Always
00657         //! more efficient than calling operator-- step times.
00658         const_reverse_iterator& operator-=( EntityID step )
00659         {
00660             myIter += step;
00661             return *this;
00662         }
00663 
00664         //! equals operator
00665         bool operator==( const const_reverse_iterator& other ) const
00666         {
00667             return myIter == other.myIter;
00668         }
00669 
00670         //! not equals operator
00671         bool operator!=( const const_reverse_iterator& other ) const
00672         {
00673             return myIter != other.myIter;
00674         }
00675 
00676       protected:
00677         //! the node we are pointing at
00678         const_iterator myIter;
00679     };
00680 
00681   public:
00682     class const_pair_iterator
00683     {
00684       public:
00685         const_pair_iterator() : myNode( NULL ) {}
00686         const_pair_iterator( const PairNode* node ) : myNode( node ) {}
00687         const_pair_iterator( const const_iterator& i ) : myNode( i.mNode ) {}
00688 
00689         const PairNode& operator*() const
00690         {
00691             return *myNode;
00692         }
00693 
00694         const PairNode* operator->() const
00695         {
00696             return myNode;
00697         }
00698 
00699         const_pair_iterator& operator--()
00700         {
00701             myNode = myNode->mPrev;
00702             return *this;
00703         }
00704 
00705         const_pair_iterator& operator++()
00706         {
00707             myNode = myNode->mNext;
00708             return *this;
00709         }
00710 
00711         const_pair_iterator operator--( int )
00712         {
00713             const_pair_iterator rval( *this );
00714             this->operator--();
00715             return rval;
00716         }
00717 
00718         const_pair_iterator operator++( int )
00719         {
00720             const_pair_iterator rval( *this );
00721             this->operator++();
00722             return rval;
00723         }
00724 
00725         bool operator==( const const_pair_iterator& other ) const
00726         {
00727             return other.myNode == myNode;
00728         }
00729 
00730         bool operator!=( const const_pair_iterator& other ) const
00731         {
00732             return other.myNode != myNode;
00733         }
00734 
00735       private:
00736         const PairNode* myNode;
00737     };
00738 
00739     pair_iterator pair_begin()
00740     {
00741         return pair_iterator( mHead.mNext );
00742     }
00743     pair_iterator pair_end()
00744     {
00745         return pair_iterator( &mHead );
00746     }
00747 
00748     const_pair_iterator const_pair_begin() const
00749     {
00750         return const_pair_iterator( mHead.mNext );
00751     }
00752     const_pair_iterator const_pair_end() const
00753     {
00754         return const_pair_iterator( &mHead );
00755     }
00756     const_pair_iterator pair_begin() const
00757     {
00758         return const_pair_iterator( mHead.mNext );
00759     }
00760     const_pair_iterator pair_end() const
00761     {
00762         return const_pair_iterator( &mHead );
00763     }
00764 };
00765 
00766 //! intersect two ranges, placing the results in the return range
00767 Range intersect( const Range&, const Range& );
00768 
00769 //! subtract range2 from this, placing the results in the return range
00770 Range subtract( const Range& from, const Range& );
00771 
00772 //! unite two ranges, placing the results in the return range
00773 inline Range unite( const Range& r1, const Range& r2 )
00774 {
00775     Range r( r1 );
00776     r.insert( r2.begin(), r2.end() );
00777     return r;
00778 }
00779 
00780 inline Range::const_iterator operator+( const Range::const_iterator& it, EntityID step )
00781 {
00782     Range::const_iterator tmp( it );
00783     return tmp += step;
00784 }
00785 
00786 inline Range::const_iterator operator+( EntityID step, const Range::const_iterator& it )
00787 {
00788     Range::const_iterator tmp( it );
00789     return tmp += step;
00790 }
00791 
00792 inline Range::const_iterator operator-( const Range::const_iterator& it, EntityID step )
00793 {
00794     Range::const_iterator tmp( it );
00795     return tmp -= step;
00796 }
00797 
00798 inline Range::const_iterator operator-( EntityID step, const Range::const_iterator& it )
00799 {
00800     Range::const_iterator tmp( it );
00801     return tmp -= step;
00802 }
00803 
00804 EntityID operator-( const Range::const_iterator& it1, const Range::const_iterator& it2 );
00805 
00806 //! Use as you would an STL back_inserter
00807 /**
00808  *  e.g. std::copy(list.begin(), list.end(), range_inserter(my_range);
00809  * Also, see comments/instructions at the top of this class declaration
00810  */
00811 class range_inserter
00812 {
00813 
00814   protected:
00815     Range* container;
00816 
00817   public:
00818     // constructor
00819     explicit range_inserter( Range& x ) : container( &x ) {}
00820     range_inserter& operator=( const Range::value_type& value )
00821     {
00822         container->insert( value );
00823         return *this;
00824     }
00825 
00826     range_inserter& operator*()
00827     {
00828         return *this;
00829     }
00830     range_inserter& operator++()
00831     {
00832         return *this;
00833     }
00834     range_inserter& operator++( int )
00835     {
00836         return *this;
00837     }
00838 
00839     typedef EntityHandle value_type;
00840     typedef EntityID difference_type;
00841     typedef std::output_iterator_tag iterator_category;
00842     typedef EntityHandle* pointer;
00843     typedef EntityHandle& reference;
00844 };
00845 
00846 inline Range::Range()
00847 {
00848     // set the head node to point to itself
00849     mHead.mNext = mHead.mPrev = &mHead;
00850     mHead.first = mHead.second = 0;
00851 }
00852 
00853 //! destructor
00854 inline Range::~Range()
00855 {
00856     clear();
00857 }
00858 
00859 //! return the beginning const iterator of this range
00860 inline Range::const_iterator Range::begin() const
00861 {
00862     return const_iterator( mHead.mNext, mHead.mNext->first );
00863 }
00864 
00865 //! return the beginning const reverse iterator of this range
00866 inline Range::const_reverse_iterator Range::rbegin() const
00867 {
00868     return const_reverse_iterator( mHead.mPrev, mHead.mPrev->second );
00869 }
00870 
00871 //! return the ending const iterator for this range
00872 inline Range::const_iterator Range::end() const
00873 {
00874     return const_iterator( &mHead, mHead.first );
00875 }
00876 
00877 //! return the ending const reverse iterator for this range
00878 inline Range::const_reverse_iterator Range::rend() const
00879 {
00880     return const_reverse_iterator( &mHead, mHead.second );
00881 }
00882 
00883 //! return whether empty or not
00884 //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
00885 inline bool Range::empty() const
00886 {
00887     return ( mHead.mNext == &mHead );
00888 }
00889 
00890 //! erases a value from this container
00891 inline Range::iterator Range::erase( EntityHandle val )
00892 {
00893     return erase( find( val ) );
00894 }
00895 
00896 inline Range::const_iterator Range::const_iterator::end_of_block() const
00897 {
00898     return Range::const_iterator( mNode, mNode->second );
00899 }
00900 
00901 inline Range::const_iterator Range::const_iterator::start_of_block() const
00902 {
00903     return Range::const_iterator( mNode, mNode->first );
00904 }
00905 
00906 //! get first entity in range
00907 inline const EntityHandle& Range::front() const
00908 {
00909     return mHead.mNext->first;
00910 }
00911 //! get last entity in range
00912 inline const EntityHandle& Range::back() const
00913 {
00914     return mHead.mPrev->second;
00915 }
00916 
00917 inline std::ostream& operator<<( std::ostream& s, const Range& r )
00918 {
00919     r.print( s );
00920     return s;
00921 }
00922 
00923 bool operator==( const Range& r1, const Range& r2 );
00924 inline bool operator!=( const Range& r1, const Range& r2 )
00925 {
00926     return !( r1 == r2 );
00927 }
00928 
00929 inline EntityHandle Range::operator[]( EntityID indexp ) const
00930 {
00931     Range::const_iterator i = begin();
00932     i += indexp;
00933     return *i;
00934 }
00935 
00936 inline int Range::index( EntityHandle handle ) const
00937 {
00938     if( handle < *begin() || handle > *rbegin() ) return -1;
00939 
00940     unsigned int i                 = 0;
00941     Range::const_pair_iterator pit = const_pair_begin();
00942     while( handle > ( *pit ).second && pit != const_pair_end() )
00943     {
00944         i += ( *pit ).second - ( *pit ).first + 1;
00945         ++pit;
00946     }
00947     if( handle < ( *pit ).first || pit == const_pair_end() ) return -1;
00948 
00949     return i + handle - ( *pit ).first;
00950 }
00951 
00952 inline double Range::compactness() const
00953 {
00954     unsigned int num_ents = size();
00955     return ( num_ents ? ( (double)get_memory_use() / (double)( num_ents * sizeof( EntityHandle ) ) ) : -1 );
00956 }
00957 
00958 template < typename Iterator >
00959 Range::iterator Range::insert_list( Iterator begin_iter, Iterator end_iter )
00960 {
00961     size_t n             = std::distance( begin_iter, end_iter );
00962     EntityHandle* sorted = new EntityHandle[n];
00963     std::copy( begin_iter, end_iter, sorted );
00964     std::sort( sorted, sorted + n );
00965     iterator hint = begin();
00966     size_t i      = 0;
00967     while( i < n )
00968     {
00969         size_t j = i + 1;
00970         while( j < n && sorted[j] == 1 + sorted[j - 1] )
00971             ++j;
00972         hint = insert( hint, sorted[i], sorted[i] + ( ( j - i ) - 1 ) );
00973         i    = j;
00974     }
00975     delete[] sorted;
00976     return hint;
00977 }
00978 
00979 inline size_t Range::psize() const
00980 {
00981     size_t i = 0;
00982     Range::const_pair_iterator pit;
00983     for( pit = const_pair_begin(), i = 0; pit != const_pair_end(); ++pit, i++ )
00984         ;
00985 
00986     return i;
00987 }
00988 
00989 }  // namespace moab
00990 
00991 #endif  // MOAB_RANGE_HPP
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines