Branch data Line data Source code
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 "moab/Types.hpp"
171 : :
172 : : namespace moab
173 : : {
174 : :
175 : : struct range_iter_tag : public std::bidirectional_iterator_tag
176 : : {
177 : : };
178 : :
179 : 65212405 : struct range_base_iter
180 : : {
181 : : typedef range_iter_tag iterator_category;
182 : : typedef EntityID difference_type;
183 : : typedef EntityHandle value_type;
184 : : typedef EntityHandle* pointer;
185 : : typedef EntityHandle& reference;
186 : : };
187 : :
188 : : //! the class Range
189 : : class Range
190 : : {
191 : : public:
192 : : // forward declare the iterators
193 : : class const_iterator;
194 : : class const_reverse_iterator;
195 : : typedef const_iterator iterator;
196 : : typedef const_reverse_iterator reverse_iterator;
197 : :
198 : : friend Range intersect( const Range&, const Range& );
199 : : friend Range subtract( const Range&, const Range& );
200 : :
201 : : //! just like subtract, but as an operator
202 : : Range& operator-=( const Range& rhs );
203 : :
204 : : //! for short hand notation, lets typedef the
205 : : //! container class that holds the ranges
206 : : typedef EntityHandle value_type;
207 : :
208 : : //! default constructor
209 : : Range();
210 : :
211 : : //! copy constructor
212 : : Range( const Range& copy );
213 : :
214 : : //! another constructor that takes an initial range
215 : : Range( EntityHandle val1, EntityHandle val2 );
216 : :
217 : : //! operator=
218 : : Range& operator=( const Range& copy );
219 : :
220 : : //! destructor
221 : : inline ~Range();
222 : :
223 : : //! return the beginning const iterator of this range
224 : : inline const_iterator begin() const;
225 : :
226 : : //! return the beginning const reverse iterator of this range
227 : : inline const_reverse_iterator rbegin() const;
228 : :
229 : : //! return the ending const iterator for this range
230 : : inline const_iterator end() const;
231 : :
232 : : //! return the ending const reverse iterator for this range
233 : : inline const_reverse_iterator rend() const;
234 : :
235 : : //! return the number of values this Ranges represents
236 : : size_t size() const;
237 : :
238 : : //! return the number of range pairs in the list
239 : : size_t psize() const;
240 : :
241 : : //! return whether empty or not
242 : : //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
243 : : inline bool empty() const;
244 : :
245 : : iterator insert( iterator hint, EntityHandle val );
246 : :
247 : : //! insert an item into the list and return the iterator for the inserted item
248 : 6853769 : iterator insert( EntityHandle val )
249 : : {
250 : 6853769 : return insert( begin(), val );
251 : : }
252 : :
253 : : //! insert a range of items into this list and return the iterator for the first
254 : : //! inserted item
255 : : iterator insert( iterator hint, EntityHandle first, EntityHandle last );
256 : :
257 : : //! insert a range of items into this list and return the iterator for the first
258 : : //! inserted item
259 : 276310 : iterator insert( EntityHandle val1, EntityHandle val2 )
260 : : {
261 : 276310 : return insert( begin(), val1, val2 );
262 : : }
263 : :
264 : : template < typename T >
265 : : iterator insert_list( T begin_iter, T end_iter );
266 : :
267 : : template < class T >
268 : 0 : iterator insert( typename T::const_iterator begin_iter, typename T::const_iterator end_iter )
269 : : {
270 : 0 : return insert_list( begin_iter, end_iter );
271 : : }
272 : :
273 : : template < typename T >
274 : 0 : iterator insert( const T* begin_iter, const T* end_iter )
275 : : {
276 : 0 : return insert_list( begin_iter, end_iter );
277 : : }
278 : :
279 : : //! remove an item from this list and return an iterator to the next item
280 : : iterator erase( iterator iter );
281 : :
282 : : //! remove a range of items from the list
283 : : iterator erase( iterator iter1, iterator iter2 );
284 : :
285 : : //! erases a value from this container
286 : : inline iterator erase( EntityHandle val );
287 : :
288 : : //! get first entity in range
289 : : inline const EntityHandle& front() const;
290 : : //! get last entity in range
291 : : inline const EntityHandle& back() const;
292 : : //! remove first entity from range
293 : : EntityHandle pop_front();
294 : : //! remove last entity from range
295 : : EntityHandle pop_back();
296 : :
297 : : //! find an item int the list and return an iterator at that value
298 : : const_iterator find( EntityHandle val ) const;
299 : :
300 : : //! return an iterator to the first value >= val
301 : : static const_iterator lower_bound( const_iterator first, const_iterator last, EntityHandle val );
302 : : static const_iterator upper_bound( const_iterator first, const_iterator last, EntityHandle val );
303 : :
304 : 0 : const_iterator lower_bound( EntityHandle val ) const
305 : : {
306 : 0 : return lower_bound( begin(), end(), val );
307 : : }
308 : 0 : const_iterator upper_bound( EntityHandle val ) const
309 : : {
310 : 0 : return upper_bound( begin(), end(), val );
311 : : }
312 : : const_iterator lower_bound( EntityType type ) const;
313 : : const_iterator upper_bound( EntityType type ) const;
314 : : std::pair< const_iterator, const_iterator > equal_range( EntityType type ) const;
315 : : const_iterator lower_bound( EntityType type, const_iterator first ) const;
316 : : const_iterator upper_bound( EntityType type, const_iterator first ) const;
317 : :
318 : : //! True if all entities in range are of passed type
319 : : //! (also true if range is empty)
320 : : bool all_of_type( EntityType type ) const;
321 : : //! True if all entities in range are of passed dimension
322 : : //! (also true if range is empty)
323 : : bool all_of_dimension( int dimension ) const;
324 : :
325 : : unsigned num_of_type( EntityType type ) const;
326 : : unsigned num_of_dimension( int dim ) const;
327 : :
328 : : //! clears the contents of the list
329 : : void clear();
330 : :
331 : : //! for debugging
332 : : const std::string str_rep( const char* indent_prefix = NULL ) const;
333 : :
334 : : void print( const char* indent_prefix = NULL ) const;
335 : : void print( std::ostream& s, const char* indent_prefix = NULL ) const;
336 : :
337 : : unsigned long get_memory_use() const;
338 : :
339 : : double compactness() const;
340 : :
341 : : void insert( Range::const_iterator begin, Range::const_iterator end );
342 : :
343 : : //! merges this Range with another range
344 : 274325 : void merge( const Range& range )
345 : : {
346 : 274325 : insert( range.begin(), range.end() );
347 : 274325 : }
348 : :
349 : : //! merge a subset of some other range
350 : 28293 : void merge( Range::const_iterator beginr, Range::const_iterator endr )
351 : : {
352 : 28293 : insert( beginr, endr );
353 : 28293 : }
354 : :
355 : : //! swap the contents of this range with another one
356 : : void swap( Range& range );
357 : :
358 : : //! check for internal consistency
359 : : void sanity_check() const;
360 : :
361 : : //! Check if this range is a non-strict superset of some other range
362 : : bool contains( const Range& other ) const;
363 : :
364 : : //! return a subset of this range, by type
365 : : Range subset_by_type( EntityType t ) const;
366 : :
367 : : //! return a subset of this range, by dimension
368 : : Range subset_by_dimension( int dim ) const;
369 : :
370 : : struct PairNode : public std::pair< EntityHandle, EntityHandle >
371 : : {
372 : :
373 [ + - ]: 890216 : PairNode() : std::pair< EntityHandle, EntityHandle >( 0, 0 ), mNext( NULL ), mPrev( NULL ) {}
374 : 4597395 : PairNode( PairNode* next, PairNode* prev, EntityHandle _first, EntityHandle _second )
375 : 4597395 : : std::pair< EntityHandle, EntityHandle >( _first, _second ), mNext( next ), mPrev( prev )
376 : : {
377 : 4597395 : }
378 : :
379 : : PairNode* mNext;
380 : : PairNode* mPrev;
381 : : };
382 : :
383 : : EntityHandle operator[]( EntityID index ) const;
384 : :
385 : : int index( EntityHandle handle ) const;
386 : :
387 : : protected:
388 : : //! the head of the list that contains pairs that represent the ranges
389 : : //! this list is sorted and unique at all times
390 : : PairNode mHead;
391 : :
392 : : //! if dead_node is not mHead, remove it from the list and free it's memory.
393 : : void delete_pair_node( PairNode* dead_node );
394 : :
395 : : public:
396 : : //! used to iterate over sub-ranges of a range
397 : : class pair_iterator : public range_base_iter
398 : : {
399 : : friend class Range;
400 : :
401 : : public:
402 : : pair_iterator() : mNode( NULL ) {}
403 : 208324 : pair_iterator( PairNode* nodep ) : mNode( nodep ) {}
404 : : pair_iterator( const pair_iterator& copy ) : mNode( copy.mNode ) {}
405 : 2383454 : pair_iterator( const const_iterator& copy ) : mNode( copy.mNode ) {}
406 : :
407 : 3831468 : std::pair< EntityHandle, EntityHandle >* operator->()
408 : : {
409 : 3831468 : return mNode;
410 : : }
411 : :
412 : 431774 : pair_iterator& operator++()
413 : : {
414 : 431774 : mNode = mNode->mNext;
415 : 431774 : return *this;
416 : : }
417 : : pair_iterator operator++( int )
418 : : {
419 : : pair_iterator tmp( *this );
420 : : this->operator++();
421 : : return tmp;
422 : : }
423 : :
424 : : pair_iterator& operator--()
425 : : {
426 : : mNode = mNode->mPrev;
427 : : return *this;
428 : : }
429 : : pair_iterator operator--( int )
430 : : {
431 : : pair_iterator tmp( *this );
432 : : this->operator--();
433 : : return tmp;
434 : : }
435 : 325167 : bool operator==( const pair_iterator& other ) const
436 : : {
437 : 325167 : return mNode == other.mNode;
438 : : }
439 : :
440 : 863719 : bool operator!=( const pair_iterator& other ) const
441 : : {
442 : 863719 : return mNode != other.mNode;
443 : : }
444 : :
445 : 436930 : PairNode* node()
446 : : {
447 : 436930 : return mNode;
448 : : }
449 : :
450 : : private:
451 : : PairNode* mNode;
452 : : };
453 : :
454 : : class const_pair_iterator;
455 : :
456 : : //! a const iterator which iterates over an Range
457 : : class const_iterator : public range_base_iter
458 : : {
459 : : friend class Range;
460 : : friend class pair_iterator;
461 : : friend class const_pair_iterator;
462 : : friend EntityID operator-( const const_iterator&, const const_iterator& );
463 : :
464 : : public:
465 : : //! default constructor - intialize base default constructor
466 : 534036 : const_iterator() : mNode( NULL ), mValue( 0 ) {}
467 : :
468 : : //! constructor used by Range
469 : 58987704 : const_iterator( const PairNode* iter, const EntityHandle val )
470 : 58987704 : : mNode( const_cast< PairNode* >( iter ) ), mValue( val )
471 : : {
472 : 58987704 : }
473 : :
474 : : //! dereference that value this iterator points to
475 : : //! returns a const reference
476 : 30925589 : const EntityHandle& operator*() const
477 : : {
478 : 30925589 : return mValue;
479 : : }
480 : :
481 : : //! prefix incrementer
482 : 12014193 : const_iterator& operator++()
483 : : {
484 : : // see if we need to increment the base iterator
485 [ + + ]: 12014193 : if( mValue == mNode->second )
486 : : {
487 : 2463939 : mNode = mNode->mNext;
488 : 2463939 : mValue = mNode->first;
489 : : }
490 : : // if not, just increment the value in the range
491 : : else
492 : 9550254 : ++mValue;
493 : 12014193 : return *this;
494 : : }
495 : :
496 : : //! postfix incrementer
497 : 95240 : const_iterator operator++( int )
498 : : {
499 : : // make a temporary copy
500 : 95240 : const_iterator tmp( *this );
501 : : // increment self
502 [ + - ]: 95240 : this->operator++();
503 : : // return the copy
504 : 95240 : return tmp;
505 : : }
506 : :
507 : : //! prefix decrementer
508 : 914556 : const_iterator& operator--()
509 : : {
510 : : // see if we need to decrement the base iterator
511 [ + + ]: 914556 : if( mValue == mNode->first )
512 : : {
513 : 300993 : mNode = mNode->mPrev;
514 : : ;
515 : 300993 : mValue = mNode->second;
516 : : }
517 : : // if not, just decrement the value
518 : : else
519 : 613563 : --mValue;
520 : 914556 : return *this;
521 : : }
522 : :
523 : : //! postfix decrementer
524 : 12 : const_iterator operator--( int )
525 : : {
526 : : // make a copy of this
527 : 12 : const_iterator tmp( *this );
528 : : // decrement self
529 [ + - ]: 12 : this->operator--();
530 : : // return the copy
531 : 12 : return tmp;
532 : : }
533 : :
534 : : //! Advance iterator specified amount.
535 : : //! Potentially O(n), but typically better. Always
536 : : //! more efficient than calling operator++ step times.
537 : : const_iterator& operator+=( EntityID step );
538 : :
539 : : //! Regress iterator specified amount.
540 : : //! Potentially O(n), but typically better. Always
541 : : //! more efficient than calling operator-- step times.
542 : : const_iterator& operator-=( EntityID step );
543 : :
544 : : //! equals operator
545 : 12311747 : bool operator==( const const_iterator& other ) const
546 : : {
547 : : // see if the base iterator is the same and the
548 : : // value of this iterator is the same
549 [ + + ][ + + ]: 12311747 : return ( mNode == other.mNode ) && ( mValue == other.mValue );
550 : : }
551 : :
552 : : //! not equals operator
553 : 12339846 : bool operator!=( const const_iterator& other ) const
554 : : {
555 : : // call == operator and not it.
556 [ + + ][ + + ]: 12339846 : return ( mNode != other.mNode ) || ( mValue != other.mValue );
557 : : }
558 : :
559 : : /**\brief get an iterator at the end of the block
560 : : *
561 : : * Get an iterator at the end of the block of consecutive
562 : : * handles that this iterator is currently contained in.
563 : : * That is, if the range contains blocks of consecutive
564 : : * handles of the form { [1,5], [7,100], ... } and this
565 : : * iterator is at any handle in the range [7,100], return
566 : : * an iterator at the '100' handle.
567 : : *
568 : : * Never returns begin() or end() unless this iterator is
569 : : * at begin() or end(). May return the same location as
570 : : * this iterator.
571 : : */
572 : : inline const_iterator end_of_block() const;
573 : :
574 : : /**\brief get an iterator at the start of the block
575 : : *
576 : : * Get an iterator at the start of the block of consecutive
577 : : * handles that this iterator is currently contained in.
578 : : * That is, if the range contains blocks of consecutive
579 : : * handles of the form { [1,5], [7,100], ... } and this
580 : : * iterator is at any handle in the range [7,100], return
581 : : * an iterator at the '7' handle.
582 : : *
583 : : * Never returns end() unless this iterator is
584 : : * at end(). May return the same location as
585 : : * this iterator.
586 : : */
587 : : inline const_iterator start_of_block() const;
588 : :
589 : : protected:
590 : : //! the node we are pointing at
591 : : PairNode* mNode;
592 : : //! the value in the range
593 : : EntityHandle mValue;
594 : : };
595 : :
596 : : //! a const reverse iterator which iterates over an Range
597 : : class const_reverse_iterator : public range_base_iter
598 : : {
599 : : friend class Range;
600 : : friend class pair_iterator;
601 : :
602 : : public:
603 : : //! default constructor - intialize base default constructor
604 : 2 : const_reverse_iterator() {}
605 : :
606 : 24 : const_reverse_iterator( const_iterator fwd_iter ) : myIter( fwd_iter ) {}
607 : :
608 : : //! constructor used by Range
609 : 9323562 : const_reverse_iterator( const PairNode* iter, const EntityHandle val ) : myIter( iter, val ) {}
610 : :
611 : : //! dereference that value this iterator points to
612 : : //! returns a const reference
613 : 5513144 : const EntityHandle& operator*() const
614 : : {
615 : 5513144 : return *myIter;
616 : : }
617 : :
618 : : //! prefix incrementer
619 : 910522 : const_reverse_iterator& operator++()
620 : : {
621 : 910522 : --myIter;
622 : 910522 : return *this;
623 : : }
624 : :
625 : : //! postfix incrementer
626 : 12 : const_reverse_iterator operator++( int )
627 : : {
628 : 12 : return const_reverse_iterator( myIter-- );
629 : : }
630 : :
631 : : //! prefix decrementer
632 : : const_reverse_iterator& operator--()
633 : : {
634 : : ++myIter;
635 : : return *this;
636 : : }
637 : :
638 : : //! postfix decrementer
639 : : const_reverse_iterator operator--( int )
640 : : {
641 : : return const_reverse_iterator( myIter++ );
642 : : }
643 : :
644 : : //! Advance iterator specified amount.
645 : : //! Potentially O(n), but typically better. Always
646 : : //! more efficient than calling operator++ step times.
647 : : const_reverse_iterator& operator+=( EntityID step )
648 : : {
649 : : myIter -= step;
650 : : return *this;
651 : : }
652 : :
653 : : //! Regress iterator specified amount.
654 : : //! Potentially O(n), but typically better. Always
655 : : //! more efficient than calling operator-- step times.
656 : : const_reverse_iterator& operator-=( EntityID step )
657 : : {
658 : : myIter += step;
659 : : return *this;
660 : : }
661 : :
662 : : //! equals operator
663 : : bool operator==( const const_reverse_iterator& other ) const
664 : : {
665 : : return myIter == other.myIter;
666 : : }
667 : :
668 : : //! not equals operator
669 : 925856 : bool operator!=( const const_reverse_iterator& other ) const
670 : : {
671 : 925856 : return myIter != other.myIter;
672 : : }
673 : :
674 : : protected:
675 : : //! the node we are pointing at
676 : : const_iterator myIter;
677 : : };
678 : :
679 : : public:
680 : : class const_pair_iterator
681 : : {
682 : : public:
683 : 2795 : const_pair_iterator() : myNode( NULL ) {}
684 : 10972321 : const_pair_iterator( const PairNode* node ) : myNode( node ) {}
685 : 1236301 : const_pair_iterator( const const_iterator& i ) : myNode( i.mNode ) {}
686 : :
687 : 13122528 : const PairNode& operator*() const
688 : : {
689 : 13122528 : return *myNode;
690 : : }
691 : :
692 : 10498146 : const PairNode* operator->() const
693 : : {
694 : 10498146 : return myNode;
695 : : }
696 : :
697 : 88050 : const_pair_iterator& operator--()
698 : : {
699 : 88050 : myNode = myNode->mPrev;
700 : 88050 : return *this;
701 : : }
702 : :
703 : 2498431 : const_pair_iterator& operator++()
704 : : {
705 : 2498431 : myNode = myNode->mNext;
706 : 2498431 : return *this;
707 : : }
708 : :
709 : : const_pair_iterator operator--( int )
710 : : {
711 : : const_pair_iterator rval( *this );
712 : : this->operator--();
713 : : return rval;
714 : : }
715 : :
716 : : const_pair_iterator operator++( int )
717 : : {
718 : : const_pair_iterator rval( *this );
719 : : this->operator++();
720 : : return rval;
721 : : }
722 : :
723 : 3723863 : bool operator==( const const_pair_iterator& other ) const
724 : : {
725 : 3723863 : return other.myNode == myNode;
726 : : }
727 : :
728 : 4708711 : bool operator!=( const const_pair_iterator& other ) const
729 : : {
730 : 4708711 : return other.myNode != myNode;
731 : : }
732 : :
733 : : private:
734 : : const PairNode* myNode;
735 : : };
736 : :
737 : 104162 : pair_iterator pair_begin()
738 : : {
739 : 104162 : return pair_iterator( mHead.mNext );
740 : : }
741 : 0 : pair_iterator pair_end()
742 : : {
743 : 0 : return pair_iterator( &mHead );
744 : : }
745 : :
746 : 3927323 : const_pair_iterator const_pair_begin() const
747 : : {
748 : 3927323 : return const_pair_iterator( mHead.mNext );
749 : : }
750 : 7044854 : const_pair_iterator const_pair_end() const
751 : : {
752 : 7044854 : return const_pair_iterator( &mHead );
753 : : }
754 : 48 : const_pair_iterator pair_begin() const
755 : : {
756 : 48 : return const_pair_iterator( mHead.mNext );
757 : : }
758 : 96 : const_pair_iterator pair_end() const
759 : : {
760 : 96 : return const_pair_iterator( &mHead );
761 : : }
762 : : };
763 : :
764 : : //! intersect two ranges, placing the results in the return range
765 : : Range intersect( const Range&, const Range& );
766 : :
767 : : //! subtract range2 from this, placing the results in the return range
768 : : Range subtract( const Range& from, const Range& );
769 : :
770 : : //! unite two ranges, placing the results in the return range
771 : 9 : inline Range unite( const Range& r1, const Range& r2 )
772 : : {
773 : 9 : Range r( r1 );
774 [ + - ][ + - ]: 9 : r.insert( r2.begin(), r2.end() );
[ + - ]
775 : 9 : return r;
776 : : }
777 : :
778 : 121541 : inline Range::const_iterator operator+( const Range::const_iterator& it, EntityID step )
779 : : {
780 : 121541 : Range::const_iterator tmp( it );
781 [ + - ]: 121541 : return tmp += step;
782 : : }
783 : :
784 : : inline Range::const_iterator operator+( EntityID step, const Range::const_iterator& it )
785 : : {
786 : : Range::const_iterator tmp( it );
787 : : return tmp += step;
788 : : }
789 : :
790 : 178 : inline Range::const_iterator operator-( const Range::const_iterator& it, EntityID step )
791 : : {
792 : 178 : Range::const_iterator tmp( it );
793 [ + - ]: 178 : return tmp -= step;
794 : : }
795 : :
796 : : inline Range::const_iterator operator-( EntityID step, const Range::const_iterator& it )
797 : : {
798 : : Range::const_iterator tmp( it );
799 : : return tmp -= step;
800 : : }
801 : :
802 : : EntityID operator-( const Range::const_iterator& it1, const Range::const_iterator& it2 );
803 : :
804 : : //! Use as you would an STL back_inserter
805 : : /**
806 : : * e.g. std::copy(list.begin(), list.end(), range_inserter(my_range);
807 : : * Also, see comments/instructions at the top of this class declaration
808 : : */
809 : : class range_inserter
810 : : {
811 : :
812 : : protected:
813 : : Range* container;
814 : :
815 : : public:
816 : : // constructor
817 : 416753 : explicit range_inserter( Range& x ) : container( &x ) {}
818 : 1472345 : range_inserter& operator=( const Range::value_type& value )
819 : : {
820 : 1472345 : container->insert( value );
821 : 1472345 : return *this;
822 : : }
823 : :
824 : 1472345 : range_inserter& operator*()
825 : : {
826 : 1472345 : return *this;
827 : : }
828 : 1472345 : range_inserter& operator++()
829 : : {
830 : 1472345 : return *this;
831 : : }
832 : : range_inserter& operator++( int )
833 : : {
834 : : return *this;
835 : : }
836 : :
837 : : typedef EntityHandle value_type;
838 : : typedef EntityID difference_type;
839 : : typedef std::output_iterator_tag iterator_category;
840 : : typedef EntityHandle* pointer;
841 : : typedef EntityHandle& reference;
842 : : };
843 : :
844 : 1362632 : inline Range::Range()
845 : : {
846 : : // set the head node to point to itself
847 : 681316 : mHead.mNext = mHead.mPrev = &mHead;
848 : 681316 : mHead.first = mHead.second = 0;
849 : 681316 : }
850 : :
851 : : //! destructor
852 : 890196 : inline Range::~Range()
853 : : {
854 : 890196 : clear();
855 : 890196 : }
856 : :
857 : : //! return the beginning const iterator of this range
858 : 13718600 : inline Range::const_iterator Range::begin() const
859 : : {
860 : 13718600 : return const_iterator( mHead.mNext, mHead.mNext->first );
861 : : }
862 : :
863 : : //! return the beginning const reverse iterator of this range
864 : 3735925 : inline Range::const_reverse_iterator Range::rbegin() const
865 : : {
866 : 3735925 : return const_reverse_iterator( mHead.mPrev, mHead.mPrev->second );
867 : : }
868 : :
869 : : //! return the ending const iterator for this range
870 : 22206910 : inline Range::const_iterator Range::end() const
871 : : {
872 : 22206910 : return const_iterator( &mHead, mHead.first );
873 : : }
874 : :
875 : : //! return the ending const reverse iterator for this range
876 : 925856 : inline Range::const_reverse_iterator Range::rend() const
877 : : {
878 : 925856 : return const_reverse_iterator( &mHead, mHead.second );
879 : : }
880 : :
881 : : //! return whether empty or not
882 : : //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
883 : 438188 : inline bool Range::empty() const
884 : : {
885 : 438188 : return ( mHead.mNext == &mHead );
886 : : }
887 : :
888 : : //! erases a value from this container
889 : 61481 : inline Range::iterator Range::erase( EntityHandle val )
890 : : {
891 : 61481 : return erase( find( val ) );
892 : : }
893 : :
894 : 2194 : inline Range::const_iterator Range::const_iterator::end_of_block() const
895 : : {
896 : 2194 : return Range::const_iterator( mNode, mNode->second );
897 : : }
898 : :
899 : 661 : inline Range::const_iterator Range::const_iterator::start_of_block() const
900 : : {
901 : 661 : return Range::const_iterator( mNode, mNode->first );
902 : : }
903 : :
904 : : //! get first entity in range
905 : 31354 : inline const EntityHandle& Range::front() const
906 : : {
907 : 31354 : return mHead.mNext->first;
908 : : }
909 : : //! get last entity in range
910 : 30635 : inline const EntityHandle& Range::back() const
911 : : {
912 : 30635 : return mHead.mPrev->second;
913 : : }
914 : :
915 : 0 : inline std::ostream& operator<<( std::ostream& s, const Range& r )
916 : : {
917 : 0 : r.print( s );
918 : 0 : return s;
919 : : }
920 : :
921 : : bool operator==( const Range& r1, const Range& r2 );
922 : 236 : inline bool operator!=( const Range& r1, const Range& r2 )
923 : : {
924 : 236 : return !( r1 == r2 );
925 : : }
926 : :
927 : 101145 : inline EntityHandle Range::operator[]( EntityID indexp ) const
928 : : {
929 [ + - ]: 101145 : Range::const_iterator i = begin();
930 [ + - ]: 101145 : i += indexp;
931 [ + - ]: 101145 : return *i;
932 : : }
933 : :
934 : 3720595 : inline int Range::index( EntityHandle handle ) const
935 : : {
936 [ + - ][ + - ]: 3720595 : if( handle < *begin() || handle > *rbegin() ) return -1;
[ + - ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ]
[ # # # # ]
937 : :
938 : 3720576 : unsigned int i = 0;
939 [ + - ]: 3720576 : Range::const_pair_iterator pit = const_pair_begin();
940 [ + - ][ + + ]: 4347344 : while( handle > ( *pit ).second && pit != const_pair_end() )
[ + - ][ + - ]
[ + - ][ + + ]
[ + + # # ]
941 : : {
942 [ + - ][ + - ]: 626768 : i += ( *pit ).second - ( *pit ).first + 1;
943 [ + - ]: 626768 : ++pit;
944 : : }
945 [ + - ][ + - ]: 3720576 : if( handle < ( *pit ).first || pit == const_pair_end() ) return -1;
[ + - ][ + - ]
[ - + ][ + - ]
[ - + ][ # # ]
946 : :
947 [ + - ]: 3720595 : return i + handle - ( *pit ).first;
948 : : }
949 : :
950 : 5 : inline double Range::compactness() const
951 : : {
952 : 5 : unsigned int num_ents = size();
953 [ - + ]: 5 : return ( num_ents ? ( (double)get_memory_use() / (double)( num_ents * sizeof( EntityHandle ) ) ) : -1 );
954 : : }
955 : :
956 : : template < typename Iterator >
957 : 15 : Range::iterator Range::insert_list( Iterator begin_iter, Iterator end_iter )
958 : : {
959 [ + - ]: 15 : size_t n = std::distance( begin_iter, end_iter );
960 [ + - ][ + - ]: 15 : EntityHandle* sorted = new EntityHandle[n];
961 [ + - ]: 15 : std::copy( begin_iter, end_iter, sorted );
962 [ + - ]: 15 : std::sort( sorted, sorted + n );
963 [ + - ]: 15 : iterator hint = begin();
964 : 15 : size_t i = 0;
965 [ + + ]: 34 : while( i < n )
966 : : {
967 : 19 : size_t j = i + 1;
968 [ + + ][ + + ]: 56 : while( j < n && sorted[j] == 1 + sorted[j - 1] )
969 : 37 : ++j;
970 [ + - ]: 19 : hint = insert( hint, sorted[i], sorted[i] + ( ( j - i ) - 1 ) );
971 : 19 : i = j;
972 : : }
973 [ + - ]: 15 : delete[] sorted;
974 : 15 : return hint;
975 : : }
976 : :
977 : 107 : inline size_t Range::psize() const
978 : : {
979 : 107 : size_t i = 0;
980 [ + - ]: 107 : Range::const_pair_iterator pit;
981 [ + - ][ + - ]: 214 : for( pit = const_pair_begin(), i = 0; pit != const_pair_end(); ++pit, i++ )
[ + - ][ + - ]
[ + + ]
982 : : ;
983 : :
984 : 107 : return i;
985 : : }
986 : :
987 : : } // namespace moab
988 : :
989 : : #endif // MOAB_RANGE_HPP
|
