![]() |
Mesh Oriented datABase
(version 5.4.1)
Array-based unstructured mesh datastructure
|
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::iterator, Range::const_iterator,
00057 and Range::RangeListIterator.
00058 iterator is derived from const_iterator. const_iterator
00059 is derived from RangeListIterator. RangeListIterator is a
00060 std::list >::const_iterator.
00061 If a particular algorithm could be more efficient by using
00062 RangeListIterator, do so.
00063
00064 ie.
00065
00066 Range range1;
00067 ... put some stuff in range1
00068 Range range2;
00069
00070 // the SLOW way.
00071 std::copy(range1.begin(), range1.end(), range_inserter<...>(range2));
00072
00073 // the FAST way.
00074 for(Range::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 my_set;
00089 Range 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 > ( 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 range1,
00105 Range range2,
00106 Range& results
00107 );
00108 {
00109 Range 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 range;
00126 };
00127 ....
00128 void some_function( const SomeClass& some_class )
00129 {
00130 Range::iterator = some_class.range.begin();
00131 }
00132 ---------------------
00133 Solution: you need to use
00134 Range::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 my_chars('A', 'C');
00141 // make an iterator that points to 'A'.
00142 Range::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
00167 #include
00168 #include
00169 #include
00170 #include
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 MOAB_EXPORT 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 MOAB_EXPORT 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 MOAB_EXPORT 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 MOAB_EXPORT 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 MOAB_EXPORT 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 MOAB_EXPORT 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