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 "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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines