 |
Mesh Oriented datABase
(version 5.5.1)
An array-based unstructured mesh library
|
|
Mesh Oriented datABase
(version 5.5.1)
An array-based unstructured mesh library
|
1 /**
2 * MOAB, a Mesh-Oriented datABase, is a software component for creating,
3 * storing and accessing finite element mesh data.
4 *
5 * Copyright 2004 Sandia Corporation. Under the terms of Contract
6 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
7 * retains certain rights in this software.
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
13 *
14 */
15
16 /*!
17 \brief Stores contiguous or partially contiguous values in an optimized
18 fashion. Partially contiguous accessing patterns is also optimized.
19
20 \author Clinton Stimpson
21
22 \date 15 April 2002
23
24 ************* Range FAQ and tips ********************
25
26 The purpose of this FAQ is to familiarize a user with
27 the appropriate use of the Range template.
28
29 ******* A few points about Range: *******
30 1. Range is not the be all of generic containers.
31 2. Range has its strengths and weaknesses as any other
32 STL container has.
33 3. Strengths:
34 a. For contiguous values, storage is extremely minimal.
35 b. Searching through contiguous values, at best, is
36 a constant time operation.
37 b. Fairly compatible with most STL algorithms.
38 c. Insertions of data from high value to low value
39 is a linear operation (constant for each insertion).
40 d. Removal of a value using an iterator is constant time.
41
42 4. Weaknesses:
43 a. For non-contiguous values, storage is not minimal and is
44 on the order of 4x the storage space as using a vector.
45 b. Searching through non-contiguous values is linear
46 time operation.
47 c. Insertions of random data is VERY slow.
48
49 Given the above characteristics of Ranges, you can now
50 decide between Range and another STL container for your
51 particular needs.
52
53
54 ******* Tips *******
55 1. Be aware of what iterators are available. Currently, there are
56 three. Range<T>::iterator, Range<T>::const_iterator,
57 and Range<T>::RangeListIterator.
58 iterator is derived from const_iterator. const_iterator
59 is derived from RangeListIterator. RangeListIterator is a
60 std::list<std::pair<T,T> >::const_iterator.
61 If a particular algorithm could be more efficient by using
62 RangeListIterator, do so.
63
64 ie.
65
66 Range<char> range1;
67 ... put some stuff in range1
68 Range<char> range2;
69
70 // the SLOW way.
71 std::copy(range1.begin(), range1.end(), range_inserter<...>(range2));
72
73 // the FAST way.
74 for(Range<char>::RangeListIterator iter = range1.begin(),
75 iter != range1.end(); ++iter)
76 {
77 range2.insert(iter->first, iter->second);
78 }
79
80 2. Prefer insert(val1, val2) over insert(val) where possible.
81
82 3. insert(val) and insert(val1, val2) have to perform searching
83 to find out where to insert an item. Searches are started
84 from the beginning of the values. Inserting larger values
85 before smaller values will increase efficiency.
86
87 ie.
88 std::set<int> my_set;
89 Range<int> my_range;
90 .. perform some operations which set does efficiently.
91
92 // now copy the results from the set into the range.
93 // copy from the end of the set to the beginning of the set
94 std::copy(my_set.rbegin(), my_set.rend(),
95 range_inserter< Range<int> > ( my_range );
96
97 4. Use empty() instead of size() if you only need to find out
98 if there is anything in the list.
99
100 5. Know what swap() does. Sometimes it is useful. It'll replace
101 the contents of one list with another.
102
103 void compute_and_get_some_set(
104 Range<char> range1,
105 Range<char> range2,
106 Range<char>& results
107 );
108 {
109 Range<char> tmp_results;
110 .. perform some computation on range1 and range2
111 and put results in tmp_results;
112 .. filter tmp_results out for some special type.
113 .. etc....
114 // return results
115 results.swap(tmp_results);
116 }
117
118
119 ******* FAQ *******
120 1. Why won't this code compile?
121 ------------------------
122 class SomeClass
123 {
124 public:
125 Range<int> range;
126 };
127 ....
128 void some_function( const SomeClass& some_class )
129 {
130 Range<int>::iterator = some_class.range.begin();
131 }
132 ---------------------
133 Solution: you need to use
134 Range<int>::const_iterator instead.
135
136 2. Why doesn't this work right when I try to change the
137 contents of an Range?
138
139 // make a range that has the letters A,B,C in it.
140 Range<char> my_chars('A', 'C');
141 // make an iterator that points to 'A'.
142 Range<char>::iterator iter = my_chars.begin();
143 // change A to D
144 *iter = 'D';
145 // print contents of my_chars to stdout
146 std::copy(my_chars.begin(), my_chars.end(),
147 std::ostream_iterator(std::cout, " "));
148
149 result is
150 A B C
151 instead of
152 B C D
153
154 When one calls *iter, which returns 'A', the actual storage of the value 'A'
155 which is returned is in the iterator and not in the Range. This allows
156 for multiple iterators on a single Range and the Range does not have
157 to keep track of which iterator is referencing which value.
158
159
160
161 */
162
163 #ifndef MOAB_RANGE_HPP
164 #define MOAB_RANGE_HPP
165
166 #include <string>
167 #include <iterator>
168 #include <iosfwd>
169 #include <algorithm>
170 #include <string>
171
172 #include "moab/Types.hpp"
173
174 namespace moab
175 {
176
177 struct range_iter_tag : public std::bidirectional_iterator_tag
178 {
179 };
180
181 struct range_base_iter
182 {
183 typedef range_iter_tag iterator_category;
184 typedef EntityID difference_type;
185 typedef EntityHandle value_type;
186 typedef EntityHandle* pointer;
187 typedef EntityHandle& reference;
188 };
189
190 //! the class Range
191 class MOAB_EXPORT Range
192 {
193 public:
194 // forward declare the iterators
195 class const_iterator;
196 class const_reverse_iterator;
197 typedef const_iterator iterator;
198 typedef const_reverse_iterator reverse_iterator;
199
200 friend Range intersect( const Range&, const Range& );
201 friend Range subtract( const Range&, const Range& );
202
203 //! just like subtract, but as an operator
204 Range& operator-=( const Range& rhs );
205
206 //! for short hand notation, lets typedef the
207 //! container class that holds the ranges
208 typedef EntityHandle value_type;
209
210 //! default constructor
211 Range();
212
213 //! copy constructor
214 Range( const Range& copy );
215
216 //! another constructor that takes an initial range
217 Range( EntityHandle val1, EntityHandle val2 );
218
219 //! operator=
220 Range& operator=( const Range& copy );
221
222 //! destructor
223 inline ~Range();
224
225 //! return the beginning const iterator of this range
226 inline const_iterator begin() const;
227
228 //! return the beginning const reverse iterator of this range
229 inline const_reverse_iterator rbegin() const;
230
231 //! return the ending const iterator for this range
232 inline const_iterator end() const;
233
234 //! return the ending const reverse iterator for this range
235 inline const_reverse_iterator rend() const;
236
237 //! return the number of values this Ranges represents
238 size_t size() const;
239
240 //! return the number of range pairs in the list
241 size_t psize() const;
242
243 //! return whether empty or not
244 //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
245 inline bool empty() const;
246
247 iterator insert( iterator hint, EntityHandle val );
248
249 //! insert an item into the list and return the iterator for the inserted item
250 iterator insert( EntityHandle val )
251 {
252 return insert( begin(), val );
253 }
254
255 //! insert a range of items into this list and return the iterator for the first
256 //! inserted item
257 iterator insert( iterator hint, EntityHandle first, EntityHandle last );
258
259 //! insert a range of items into this list and return the iterator for the first
260 //! inserted item
261 iterator insert( EntityHandle val1, EntityHandle val2 )
262 {
263 return insert( begin(), val1, val2 );
264 }
265
266 template < typename T >
267 iterator insert_list( T begin_iter, T end_iter );
268
269 template < class T >
270 iterator insert( typename T::const_iterator begin_iter, typename T::const_iterator end_iter )
271 {
272 return insert_list( begin_iter, end_iter );
273 }
274
275 template < typename T >
276 iterator insert( const T* begin_iter, const T* end_iter )
277 {
278 return insert_list( begin_iter, end_iter );
279 }
280
281 //! remove an item from this list and return an iterator to the next item
282 iterator erase( iterator iter );
283
284 //! remove a range of items from the list
285 iterator erase( iterator iter1, iterator iter2 );
286
287 //! erases a value from this container
288 inline iterator erase( EntityHandle val );
289
290 //! get first entity in range
291 inline const EntityHandle& front() const;
292 //! get last entity in range
293 inline const EntityHandle& back() const;
294 //! remove first entity from range
295 EntityHandle pop_front();
296 //! remove last entity from range
297 EntityHandle pop_back();
298
299 //! find an item int the list and return an iterator at that value
300 const_iterator find( EntityHandle val ) const;
301
302 //! return an iterator to the first value >= val
303 static const_iterator lower_bound( const_iterator first, const_iterator last, EntityHandle val );
304 static const_iterator upper_bound( const_iterator first, const_iterator last, EntityHandle val );
305
306 const_iterator lower_bound( EntityHandle val ) const
307 {
308 return lower_bound( begin(), end(), val );
309 }
310 const_iterator upper_bound( EntityHandle val ) const
311 {
312 return upper_bound( begin(), end(), val );
313 }
314 const_iterator lower_bound( EntityType type ) const;
315 const_iterator upper_bound( EntityType type ) const;
316 std::pair< const_iterator, const_iterator > equal_range( EntityType type ) const;
317 const_iterator lower_bound( EntityType type, const_iterator first ) const;
318 const_iterator upper_bound( EntityType type, const_iterator first ) const;
319
320 //! True if all entities in range are of passed type
321 //! (also true if range is empty)
322 bool all_of_type( EntityType type ) const;
323 //! True if all entities in range are of passed dimension
324 //! (also true if range is empty)
325 bool all_of_dimension( int dimension ) const;
326
327 unsigned num_of_type( EntityType type ) const;
328 unsigned num_of_dimension( int dim ) const;
329
330 //! clears the contents of the list
331 void clear();
332
333 //! for debugging
334 const std::string str_rep( const char* indent_prefix = NULL ) const;
335
336 void print( const char* indent_prefix = NULL ) const;
337 void print( std::ostream& s, const char* indent_prefix = NULL ) const;
338
339 unsigned long get_memory_use() const;
340
341 double compactness() const;
342
343 void insert( Range::const_iterator begin, Range::const_iterator end );
344
345 //! merges this Range with another range
346 void merge( const Range& range )
347 {
348 insert( range.begin(), range.end() );
349 }
350
351 //! merge a subset of some other range
352 void merge( Range::const_iterator beginr, Range::const_iterator endr )
353 {
354 insert( beginr, endr );
355 }
356
357 //! swap the contents of this range with another one
358 void swap( Range& range );
359
360 //! check for internal consistency
361 void sanity_check() const;
362
363 //! Check if this range is a non-strict superset of some other range
364 bool contains( const Range& other ) const;
365
366 //! return a subset of this range, by type
367 Range subset_by_type( EntityType t ) const;
368
369 //! return a subset of this range, by dimension
370 Range subset_by_dimension( int dim ) const;
371
372 struct PairNode : public std::pair< EntityHandle, EntityHandle >
373 {
374
375 PairNode() : std::pair< EntityHandle, EntityHandle >( 0, 0 ), mNext( NULL ), mPrev( NULL ) {}
376 PairNode( PairNode* next, PairNode* prev, EntityHandle _first, EntityHandle _second )
377 : std::pair< EntityHandle, EntityHandle >( _first, _second ), mNext( next ), mPrev( prev )
378 {
379 }
380
381 PairNode* mNext;
382 PairNode* mPrev;
383 };
384
385 EntityHandle operator[]( EntityID index ) const;
386
387 int index( EntityHandle handle ) const;
388
389 protected:
390 //! the head of the list that contains pairs that represent the ranges
391 //! this list is sorted and unique at all times
392 PairNode mHead;
393
394 //! if dead_node is not mHead, remove it from the list and free it's memory.
395 void delete_pair_node( PairNode* dead_node );
396
397 public:
398 //! used to iterate over sub-ranges of a range
399 class MOAB_EXPORT pair_iterator : public range_base_iter
400 {
401 friend class Range;
402
403 public:
404 pair_iterator() : mNode( NULL ) {}
405 pair_iterator( PairNode* nodep ) : mNode( nodep ) {}
406 pair_iterator( const pair_iterator& copy ) : mNode( copy.mNode ) {}
407 pair_iterator( const const_iterator& copy ) : mNode( copy.mNode ) {}
408
409 std::pair< EntityHandle, EntityHandle >* operator->()
410 {
411 return mNode;
412 }
413
414 pair_iterator& operator++()
415 {
416 mNode = mNode->mNext;
417 return *this;
418 }
419 pair_iterator operator++( int )
420 {
421 pair_iterator tmp( *this );
422 this->operator++();
423 return tmp;
424 }
425
426 pair_iterator& operator--()
427 {
428 mNode = mNode->mPrev;
429 return *this;
430 }
431 pair_iterator operator--( int )
432 {
433 pair_iterator tmp( *this );
434 this->operator--();
435 return tmp;
436 }
437 bool operator==( const pair_iterator& other ) const
438 {
439 return mNode == other.mNode;
440 }
441
442 bool operator!=( const pair_iterator& other ) const
443 {
444 return mNode != other.mNode;
445 }
446
447 PairNode* node()
448 {
449 return mNode;
450 }
451
452 private:
453 PairNode* mNode;
454 };
455
456 class const_pair_iterator;
457
458 //! a const iterator which iterates over an Range
459 class MOAB_EXPORT const_iterator : public range_base_iter
460 {
461 friend class Range;
462 friend class pair_iterator;
463 friend class const_pair_iterator;
464 friend EntityID operator-( const const_iterator&, const const_iterator& );
465
466 public:
467 //! default constructor - intialize base default constructor
468 const_iterator() : mNode( NULL ), mValue( 0 ) {}
469
470 //! constructor used by Range
471 const_iterator( const PairNode* iter, const EntityHandle val )
472 : mNode( const_cast< PairNode* >( iter ) ), mValue( val )
473 {
474 }
475
476 //! dereference that value this iterator points to
477 //! returns a const reference
478 const EntityHandle& operator*() const
479 {
480 return mValue;
481 }
482
483 //! prefix incrementer
484 const_iterator& operator++()
485 {
486 // see if we need to increment the base iterator
487 if( mValue == mNode->second )
488 {
489 mNode = mNode->mNext;
490 mValue = mNode->first;
491 }
492 // if not, just increment the value in the range
493 else
494 ++mValue;
495 return *this;
496 }
497
498 //! postfix incrementer
499 const_iterator operator++( int )
500 {
501 // make a temporary copy
502 const_iterator tmp( *this );
503 // increment self
504 this->operator++();
505 // return the copy
506 return tmp;
507 }
508
509 //! prefix decrementer
510 const_iterator& operator--()
511 {
512 // see if we need to decrement the base iterator
513 if( mValue == mNode->first )
514 {
515 mNode = mNode->mPrev;
516 ;
517 mValue = mNode->second;
518 }
519 // if not, just decrement the value
520 else
521 --mValue;
522 return *this;
523 }
524
525 //! postfix decrementer
526 const_iterator operator--( int )
527 {
528 // make a copy of this
529 const_iterator tmp( *this );
530 // decrement self
531 this->operator--();
532 // return the copy
533 return tmp;
534 }
535
536 //! Advance iterator specified amount.
537 //! Potentially O(n), but typically better. Always
538 //! more efficient than calling operator++ step times.
539 const_iterator& operator+=( EntityID step );
540
541 //! Regress iterator specified amount.
542 //! Potentially O(n), but typically better. Always
543 //! more efficient than calling operator-- step times.
544 const_iterator& operator-=( EntityID step );
545
546 //! equals operator
547 bool operator==( const const_iterator& other ) const
548 {
549 // see if the base iterator is the same and the
550 // value of this iterator is the same
551 return ( mNode == other.mNode ) && ( mValue == other.mValue );
552 }
553
554 //! not equals operator
555 bool operator!=( const const_iterator& other ) const
556 {
557 // call == operator and not it.
558 return ( mNode != other.mNode ) || ( mValue != other.mValue );
559 }
560
561 /**\brief get an iterator at the end of the block
562 *
563 * Get an iterator at the end of the block of consecutive
564 * handles that this iterator is currently contained in.
565 * That is, if the range contains blocks of consecutive
566 * handles of the form { [1,5], [7,100], ... } and this
567 * iterator is at any handle in the range [7,100], return
568 * an iterator at the '100' handle.
569 *
570 * Never returns begin() or end() unless this iterator is
571 * at begin() or end(). May return the same location as
572 * this iterator.
573 */
574 inline const_iterator end_of_block() const;
575
576 /**\brief get an iterator at the start of the block
577 *
578 * Get an iterator at the start of the block of consecutive
579 * handles that this iterator is currently contained in.
580 * That is, if the range contains blocks of consecutive
581 * handles of the form { [1,5], [7,100], ... } and this
582 * iterator is at any handle in the range [7,100], return
583 * an iterator at the '7' handle.
584 *
585 * Never returns end() unless this iterator is
586 * at end(). May return the same location as
587 * this iterator.
588 */
589 inline const_iterator start_of_block() const;
590
591 protected:
592 //! the node we are pointing at
593 PairNode* mNode;
594 //! the value in the range
595 EntityHandle mValue;
596 };
597
598 //! a const reverse iterator which iterates over an Range
599 class MOAB_EXPORT const_reverse_iterator : public range_base_iter
600 {
601 friend class Range;
602 friend class pair_iterator;
603
604 public:
605 //! default constructor - intialize base default constructor
606 const_reverse_iterator() {}
607
608 const_reverse_iterator( const_iterator fwd_iter ) : myIter( fwd_iter ) {}
609
610 //! constructor used by Range
611 const_reverse_iterator( const PairNode* iter, const EntityHandle val ) : myIter( iter, val ) {}
612
613 //! dereference that value this iterator points to
614 //! returns a const reference
615 const EntityHandle& operator*() const
616 {
617 return *myIter;
618 }
619
620 //! prefix incrementer
621 const_reverse_iterator& operator++()
622 {
623 --myIter;
624 return *this;
625 }
626
627 //! postfix incrementer
628 const_reverse_iterator operator++( int )
629 {
630 return const_reverse_iterator( myIter-- );
631 }
632
633 //! prefix decrementer
634 const_reverse_iterator& operator--()
635 {
636 ++myIter;
637 return *this;
638 }
639
640 //! postfix decrementer
641 const_reverse_iterator operator--( int )
642 {
643 return const_reverse_iterator( myIter++ );
644 }
645
646 //! Advance iterator specified amount.
647 //! Potentially O(n), but typically better. Always
648 //! more efficient than calling operator++ step times.
649 const_reverse_iterator& operator+=( EntityID step )
650 {
651 myIter -= step;
652 return *this;
653 }
654
655 //! Regress iterator specified amount.
656 //! Potentially O(n), but typically better. Always
657 //! more efficient than calling operator-- step times.
658 const_reverse_iterator& operator-=( EntityID step )
659 {
660 myIter += step;
661 return *this;
662 }
663
664 //! equals operator
665 bool operator==( const const_reverse_iterator& other ) const
666 {
667 return myIter == other.myIter;
668 }
669
670 //! not equals operator
671 bool operator!=( const const_reverse_iterator& other ) const
672 {
673 return myIter != other.myIter;
674 }
675
676 protected:
677 //! the node we are pointing at
678 const_iterator myIter;
679 };
680
681 public:
682 class MOAB_EXPORT const_pair_iterator
683 {
684 public:
685 const_pair_iterator() : myNode( NULL ) {}
686 const_pair_iterator( const PairNode* node ) : myNode( node ) {}
687 const_pair_iterator( const const_iterator& i ) : myNode( i.mNode ) {}
688
689 const PairNode& operator*() const
690 {
691 return *myNode;
692 }
693
694 const PairNode* operator->() const
695 {
696 return myNode;
697 }
698
699 const_pair_iterator& operator--()
700 {
701 myNode = myNode->mPrev;
702 return *this;
703 }
704
705 const_pair_iterator& operator++()
706 {
707 myNode = myNode->mNext;
708 return *this;
709 }
710
711 const_pair_iterator operator--( int )
712 {
713 const_pair_iterator rval( *this );
714 this->operator--();
715 return rval;
716 }
717
718 const_pair_iterator operator++( int )
719 {
720 const_pair_iterator rval( *this );
721 this->operator++();
722 return rval;
723 }
724
725 bool operator==( const const_pair_iterator& other ) const
726 {
727 return other.myNode == myNode;
728 }
729
730 bool operator!=( const const_pair_iterator& other ) const
731 {
732 return other.myNode != myNode;
733 }
734
735 private:
736 const PairNode* myNode;
737 };
738
739 pair_iterator pair_begin()
740 {
741 return pair_iterator( mHead.mNext );
742 }
743 pair_iterator pair_end()
744 {
745 return pair_iterator( &mHead );
746 }
747
748 const_pair_iterator const_pair_begin() const
749 {
750 return const_pair_iterator( mHead.mNext );
751 }
752 const_pair_iterator const_pair_end() const
753 {
754 return const_pair_iterator( &mHead );
755 }
756 const_pair_iterator pair_begin() const
757 {
758 return const_pair_iterator( mHead.mNext );
759 }
760 const_pair_iterator pair_end() const
761 {
762 return const_pair_iterator( &mHead );
763 }
764 };
765
766 //! intersect two ranges, placing the results in the return range
767 Range intersect( const Range&, const Range& );
768
769 //! subtract range2 from this, placing the results in the return range
770 Range subtract( const Range& from, const Range& );
771
772 //! unite two ranges, placing the results in the return range
773 inline Range unite( const Range& r1, const Range& r2 )
774 {
775 Range r( r1 );
776 r.insert( r2.begin(), r2.end() );
777 return r;
778 }
779
780 inline Range::const_iterator operator+( const Range::const_iterator& it, EntityID step )
781 {
782 Range::const_iterator tmp( it );
783 return tmp += step;
784 }
785
786 inline Range::const_iterator operator+( EntityID step, const Range::const_iterator& it )
787 {
788 Range::const_iterator tmp( it );
789 return tmp += step;
790 }
791
792 inline Range::const_iterator operator-( const Range::const_iterator& it, EntityID step )
793 {
794 Range::const_iterator tmp( it );
795 return tmp -= step;
796 }
797
798 inline Range::const_iterator operator-( EntityID step, const Range::const_iterator& it )
799 {
800 Range::const_iterator tmp( it );
801 return tmp -= step;
802 }
803
804 EntityID operator-( const Range::const_iterator& it1, const Range::const_iterator& it2 );
805
806 //! Use as you would an STL back_inserter
807 /**
808 * e.g. std::copy(list.begin(), list.end(), range_inserter(my_range);
809 * Also, see comments/instructions at the top of this class declaration
810 */
811 class MOAB_EXPORT range_inserter
812 {
813
814 protected:
815 Range* container;
816
817 public:
818 // constructor
819 explicit range_inserter( Range& x ) : container( &x ) {}
820 range_inserter& operator=( const Range::value_type& value )
821 {
822 container->insert( value );
823 return *this;
824 }
825
826 range_inserter& operator*()
827 {
828 return *this;
829 }
830 range_inserter& operator++()
831 {
832 return *this;
833 }
834 range_inserter& operator++( int )
835 {
836 return *this;
837 }
838
839 typedef EntityHandle value_type;
840 typedef EntityID difference_type;
841 typedef std::output_iterator_tag iterator_category;
842 typedef EntityHandle* pointer;
843 typedef EntityHandle& reference;
844 };
845
846 inline Range::Range()
847 {
848 // set the head node to point to itself
849 mHead.mNext = mHead.mPrev = &mHead;
850 mHead.first = mHead.second = 0;
851 }
852
853 //! destructor
854 inline Range::~Range()
855 {
856 clear();
857 }
858
859 //! return the beginning const iterator of this range
860 inline Range::const_iterator Range::begin() const
861 {
862 return const_iterator( mHead.mNext, mHead.mNext->first );
863 }
864
865 //! return the beginning const reverse iterator of this range
866 inline Range::const_reverse_iterator Range::rbegin() const
867 {
868 return const_reverse_iterator( mHead.mPrev, mHead.mPrev->second );
869 }
870
871 //! return the ending const iterator for this range
872 inline Range::const_iterator Range::end() const
873 {
874 return const_iterator( &mHead, mHead.first );
875 }
876
877 //! return the ending const reverse iterator for this range
878 inline Range::const_reverse_iterator Range::rend() const
879 {
880 return const_reverse_iterator( &mHead, mHead.second );
881 }
882
883 //! return whether empty or not
884 //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
885 inline bool Range::empty() const
886 {
887 return ( mHead.mNext == &mHead );
888 }
889
890 //! erases a value from this container
891 inline Range::iterator Range::erase( EntityHandle val )
892 {
893 return erase( find( val ) );
894 }
895
896 inline Range::const_iterator Range::const_iterator::end_of_block() const
897 {
898 return Range::const_iterator( mNode, mNode->second );
899 }
900
901 inline Range::const_iterator Range::const_iterator::start_of_block() const
902 {
903 return Range::const_iterator( mNode, mNode->first );
904 }
905
906 //! get first entity in range
907 inline const EntityHandle& Range::front() const
908 {
909 return mHead.mNext->first;
910 }
911 //! get last entity in range
912 inline const EntityHandle& Range::back() const
913 {
914 return mHead.mPrev->second;
915 }
916
917 inline std::ostream& operator<<( std::ostream& s, const Range& r )
918 {
919 r.print( s );
920 return s;
921 }
922
923 bool operator==( const Range& r1, const Range& r2 );
924 inline bool operator!=( const Range& r1, const Range& r2 )
925 {
926 return !( r1 == r2 );
927 }
928
929 inline EntityHandle Range::operator[]( EntityID indexp ) const
930 {
931 Range::const_iterator i = begin();
932 i += indexp;
933 return *i;
934 }
935
936 inline int Range::index( EntityHandle handle ) const
937 {
938 if( handle < *begin() || handle > *rbegin() ) return -1;
939
940 unsigned int i = 0;
941 Range::const_pair_iterator pit = const_pair_begin();
942 while( handle > ( *pit ).second && pit != const_pair_end() )
943 {
944 i += ( *pit ).second - ( *pit ).first + 1;
945 ++pit;
946 }
947 if( handle < ( *pit ).first || pit == const_pair_end() ) return -1;
948
949 return i + handle - ( *pit ).first;
950 }
951
952 inline double Range::compactness() const
953 {
954 unsigned int num_ents = size();
955 return ( num_ents ? ( (double)get_memory_use() / (double)( num_ents * sizeof( EntityHandle ) ) ) : -1 );
956 }
957
958 template < typename Iterator >
959 Range::iterator Range::insert_list( Iterator begin_iter, Iterator end_iter )
960 {
961 size_t n = std::distance( begin_iter, end_iter );
962 EntityHandle* sorted = new EntityHandle[n];
963 std::copy( begin_iter, end_iter, sorted );
964 std::sort( sorted, sorted + n );
965 iterator hint = begin();
966 size_t i = 0;
967 while( i < n )
968 {
969 size_t j = i + 1;
970 while( j < n && sorted[j] == 1 + sorted[j - 1] )
971 ++j;
972 hint = insert( hint, sorted[i], sorted[i] + ( ( j - i ) - 1 ) );
973 i = j;
974 }
975 delete[] sorted;
976 return hint;
977 }
978
979 inline size_t Range::psize() const
980 {
981 size_t i = 0;
982 Range::const_pair_iterator pit;
983 for( pit = const_pair_begin(), i = 0; pit != const_pair_end(); ++pit, i++ )
984 ;
985
986 return i;
987 }
988
989 } // namespace moab
990
991 #endif // MOAB_RANGE_HPP
1.9.1.