1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
/**
 * MOAB, a Mesh-Oriented datABase, is a software component for creating,
 * storing and accessing finite element mesh data.
 *
 * Copyright 2004 Sandia Corporation.  Under the terms of Contract
 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
 * retains certain rights in this software.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 */

/*!
  \brief Stores contiguous or partially contiguous values in an optimized
  fashion.  Partially contiguous accessing patterns is also optimized.

  \author Clinton Stimpson

  \date 15 April 2002

 *************  Range FAQ and tips ********************

 The purpose of this FAQ is to familiarize a user with
 the appropriate use of the Range template.

   ******* A few points about Range: *******
 1.  Range is not the be all of generic containers.
 2.  Range has its strengths and weaknesses as any other
     STL container has.
 3.  Strengths:
     a. For contiguous values, storage is extremely minimal.
     b. Searching through contiguous values, at best, is
        a constant time operation.
     b. Fairly compatible with most STL algorithms.
     c. Insertions of data from high value to low value
        is a linear operation (constant for each insertion).
     d. Removal of a value using an iterator is constant time.

 4.  Weaknesses:
     a. For non-contiguous values, storage is not minimal and is
        on the order of 4x the storage space as using a vector.
     b. Searching through non-contiguous values is linear
        time operation.
     c. Insertions of random data is VERY slow.

   Given the above characteristics of Ranges, you can now
   decide between Range and another STL container for your
   particular needs.


   ******* Tips *******
 1.  Be aware of what iterators are available.  Currently, there are
     three.  Range<T>::iterator, Range<T>::const_iterator,
     and Range<T>::RangeListIterator.
     iterator is derived from const_iterator.  const_iterator
     is derived from RangeListIterator.  RangeListIterator is a
     std::list<std::pair<T,T> >::const_iterator.
     If a particular algorithm could be more efficient by using
     RangeListIterator, do so.

     ie.

     Range<char> range1;
     ... put some stuff in range1
     Range<char> range2;

     // the SLOW way.
     std::copy(range1.begin(), range1.end(), range_inserter<...>(range2));

     // the FAST way.
     for(Range<char>::RangeListIterator iter = range1.begin(),
         iter != range1.end(); ++iter)
     {
       range2.insert(iter->first, iter->second);
     }

 2.  Prefer insert(val1, val2) over insert(val) where possible.

 3.  insert(val) and insert(val1, val2) have to perform searching
     to find out where to insert an item.  Searches are started
     from the beginning of the values.  Inserting larger values
     before smaller values will increase efficiency.

     ie.
     std::set<int> my_set;
     Range<int> my_range;
     .. perform some operations which set does efficiently.

     // now copy the results from the set into the range.
     // copy from the end of the set to the beginning of the set
     std::copy(my_set.rbegin(), my_set.rend(),
         range_inserter< Range<int> > ( my_range );

 4.  Use empty() instead of size() if you only need to find out
     if there is anything in the list.

 5.  Know what swap() does.  Sometimes it is useful.  It'll replace
     the contents of one list with another.

     void compute_and_get_some_set(
         Range<char> range1,
         Range<char> range2,
         Range<char>& results
         );
     {
       Range<char> tmp_results;
       .. perform some computation on range1 and range2
          and put results in tmp_results;
       .. filter tmp_results out for some special type.
       .. etc....
       // return results
       results.swap(tmp_results);
     }


   ******* FAQ *******
 1. Why won't this code compile?
    ------------------------
    class SomeClass
    {
    public:
      Range<int> range;
    };
    ....
    void some_function( const SomeClass& some_class )
    {
      Range<int>::iterator = some_class.range.begin();
    }
    ---------------------
    Solution:  you need to use
    Range<int>::const_iterator instead.

 2. Why doesn't this work right when I try to change the
    contents of an Range?

    // make a range that has the letters A,B,C in it.
    Range<char> my_chars('A', 'C');
    // make an iterator that points to 'A'.
    Range<char>::iterator iter = my_chars.begin();
    // change A to D
    *iter = 'D';
    // print contents of my_chars to stdout
    std::copy(my_chars.begin(), my_chars.end(),
              std::ostream_iterator(std::cout, " "));

    result is
      A B C
    instead of
      B C D

    When one calls *iter, which returns 'A', the actual storage of the value 'A'
    which is returned is in the iterator and not in the Range.  This allows
    for multiple iterators on a single Range and the Range does not have
    to keep track of which iterator is referencing which value.



*/

#ifndef MOAB_RANGE_HPP
#define MOAB_RANGE_HPP

#include <string>
#include <iterator>
#include <iosfwd>
#include <algorithm>
#include <string>

#include "moab/Types.hpp"

namespace moab
{

struct range_iter_tag : public std::bidirectional_iterator_tag
{
};

struct range_base_iter
{
    typedef range_iter_tag iterator_category;
    typedef EntityID difference_type;
    typedef EntityHandle value_type;
    typedef EntityHandle* pointer;
    typedef EntityHandle& reference;
};

//! the class Range
class MOAB_EXPORT Range
{
  public:
    // forward declare the iterators
    class const_iterator;
    class const_reverse_iterator;
    typedef const_iterator iterator;
    typedef const_reverse_iterator reverse_iterator;

    friend Range intersect( const Range&, const Range& );
    friend Range subtract( const Range&, const Range& );

    //! just like subtract, but as an operator
    Range& operator-=( const Range& rhs );

    //! for short hand notation, lets typedef the
    //! container class that holds the ranges
    typedef EntityHandle value_type;

    //! default constructor
    Range();

    //! copy constructor
    Range( const Range& copy );

    //! another constructor that takes an initial range
    Range( EntityHandle val1, EntityHandle val2 );

    //! operator=
    Range& operator=( const Range& copy );

    //! destructor
    inline ~Range();

    //! return the beginning const iterator of this range
    inline const_iterator begin() const;

    //! return the beginning const reverse iterator of this range
    inline const_reverse_iterator rbegin() const;

    //! return the ending const iterator for this range
    inline const_iterator end() const;

    //! return the ending const reverse iterator for this range
    inline const_reverse_iterator rend() const;

    //! return the number of values this Ranges represents
    size_t size() const;

    //! return the number of range pairs in the list
    size_t psize() const;

    //! return whether empty or not
    //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
    inline bool empty() const;

    iterator insert( iterator hint, EntityHandle val );

    //! insert an item into the list and return the iterator for the inserted item
    iterator insert( EntityHandle val )
    {
        return insert( begin(), val );
    }

    //! insert a range of items into this list and return the iterator for the first
    //! inserted item
    iterator insert( iterator hint, EntityHandle first, EntityHandle last );

    //! insert a range of items into this list and return the iterator for the first
    //! inserted item
    iterator insert( EntityHandle val1, EntityHandle val2 )
    {
        return insert( begin(), val1, val2 );
    }

    template < typename T >
    iterator insert_list( T begin_iter, T end_iter );

    template < class T >
    iterator insert( typename T::const_iterator begin_iter, typename T::const_iterator end_iter )
    {
        return insert_list( begin_iter, end_iter );
    }

    template < typename T >
    iterator insert( const T* begin_iter, const T* end_iter )
    {
        return insert_list( begin_iter, end_iter );
    }

    //! remove an item from this list and return an iterator to the next item
    iterator erase( iterator iter );

    //! remove a range of items from the list
    iterator erase( iterator iter1, iterator iter2 );

    //! erases a value from this container
    inline iterator erase( EntityHandle val );

    //! get first entity in range
    inline const EntityHandle& front() const;
    //! get last entity in range
    inline const EntityHandle& back() const;
    //! remove first entity from range
    EntityHandle pop_front();
    //! remove last entity from range
    EntityHandle pop_back();

    //! find an item int the list and return an iterator at that value
    const_iterator find( EntityHandle val ) const;

    //! return an iterator to the first value >= val
    static const_iterator lower_bound( const_iterator first, const_iterator last, EntityHandle val );
    static const_iterator upper_bound( const_iterator first, const_iterator last, EntityHandle val );

    const_iterator lower_bound( EntityHandle val ) const
    {
        return lower_bound( begin(), end(), val );
    }
    const_iterator upper_bound( EntityHandle val ) const
    {
        return upper_bound( begin(), end(), val );
    }
    const_iterator lower_bound( EntityType type ) const;
    const_iterator upper_bound( EntityType type ) const;
    std::pair< const_iterator, const_iterator > equal_range( EntityType type ) const;
    const_iterator lower_bound( EntityType type, const_iterator first ) const;
    const_iterator upper_bound( EntityType type, const_iterator first ) const;

    //! True if all entities in range are of passed type
    //! (also true if range is empty)
    bool all_of_type( EntityType type ) const;
    //! True if all entities in range are of passed dimension
    //! (also true if range is empty)
    bool all_of_dimension( int dimension ) const;

    unsigned num_of_type( EntityType type ) const;
    unsigned num_of_dimension( int dim ) const;

    //! clears the contents of the list
    void clear();

    //! for debugging
    const std::string str_rep( const char* indent_prefix = NULL ) const;

    void print( const char* indent_prefix = NULL ) const;
    void print( std::ostream& s, const char* indent_prefix = NULL ) const;

    unsigned long get_memory_use() const;

    double compactness() const;

    void insert( Range::const_iterator begin, Range::const_iterator end );

    //! merges this Range with another range
    void merge( const Range& range )
    {
        insert( range.begin(), range.end() );
    }

    //! merge a subset of some other range
    void merge( Range::const_iterator beginr, Range::const_iterator endr )
    {
        insert( beginr, endr );
    }

    //! swap the contents of this range with another one
    void swap( Range& range );

    //! check for internal consistency
    void sanity_check() const;

    //! Check if this range is a non-strict superset of some other range
    bool contains( const Range& other ) const;

    //! return a subset of this range, by type
    Range subset_by_type( EntityType t ) const;

    //! return a subset of this range, by dimension
    Range subset_by_dimension( int dim ) const;

    struct PairNode : public std::pair< EntityHandle, EntityHandle >
    {

        PairNode() : std::pair< EntityHandle, EntityHandle >( 0, 0 ), mNext( NULL ), mPrev( NULL ) {}
        PairNode( PairNode* next, PairNode* prev, EntityHandle _first, EntityHandle _second )
            : std::pair< EntityHandle, EntityHandle >( _first, _second ), mNext( next ), mPrev( prev )
        {
        }

        PairNode* mNext;
        PairNode* mPrev;
    };

    EntityHandle operator[]( EntityID index ) const;

    int index( EntityHandle handle ) const;

  protected:
    //! the head of the list that contains pairs that represent the ranges
    //! this list is sorted and unique at all times
    PairNode mHead;

    //! if dead_node is not mHead, remove it from the list and free it's memory.
    void delete_pair_node( PairNode* dead_node );

  public:
    //! used to iterate over sub-ranges of a range
    class MOAB_EXPORT pair_iterator : public range_base_iter
    {
        friend class Range;

      public:
        pair_iterator() : mNode( NULL ) {}
        pair_iterator( PairNode* nodep ) : mNode( nodep ) {}
        pair_iterator( const pair_iterator& copy ) : mNode( copy.mNode ) {}
        pair_iterator( const const_iterator& copy ) : mNode( copy.mNode ) {}

        std::pair< EntityHandle, EntityHandle >* operator->()
        {
            return mNode;
        }

        pair_iterator& operator++()
        {
            mNode = mNode->mNext;
            return *this;
        }
        pair_iterator operator++( int )
        {
            pair_iterator tmp( *this );
            this->operator++();
            return tmp;
        }

        pair_iterator& operator--()
        {
            mNode = mNode->mPrev;
            return *this;
        }
        pair_iterator operator--( int )
        {
            pair_iterator tmp( *this );
            this->operator--();
            return tmp;
        }
        bool operator==( const pair_iterator& other ) const
        {
            return mNode == other.mNode;
        }

        bool operator!=( const pair_iterator& other ) const
        {
            return mNode != other.mNode;
        }

        PairNode* node()
        {
            return mNode;
        }

      private:
        PairNode* mNode;
    };

    class const_pair_iterator;

    //! a const iterator which iterates over an Range
    class MOAB_EXPORT const_iterator : public range_base_iter
    {
        friend class Range;
        friend class pair_iterator;
        friend class const_pair_iterator;
        friend EntityID operator-( const const_iterator&, const const_iterator& );

      public:
        //! default constructor - intialize base default constructor
        const_iterator() : mNode( NULL ), mValue( 0 ) {}

        //! constructor used by Range
        const_iterator( const PairNode* iter, const EntityHandle val )
            : mNode( const_cast< PairNode* >( iter ) ), mValue( val )
        {
        }

        //! dereference that value this iterator points to
        //! returns a const reference
        const EntityHandle& operator*() const
        {
            return mValue;
        }

        //! prefix incrementer
        const_iterator& operator++()
        {
            // see if we need to increment the base iterator
            if( mValue == mNode->second )
            {
                mNode  = mNode->mNext;
                mValue = mNode->first;
            }
            // if not, just increment the value in the range
            else
                ++mValue;
            return *this;
        }

        //! postfix incrementer
        const_iterator operator++( int )
        {
            // make a temporary copy
            const_iterator tmp( *this );
            // increment self
            this->operator++();
            // return the copy
            return tmp;
        }

        //! prefix decrementer
        const_iterator& operator--()
        {
            // see if we need to decrement the base iterator
            if( mValue == mNode->first )
            {
                mNode = mNode->mPrev;
                ;
                mValue = mNode->second;
            }
            // if not, just decrement the value
            else
                --mValue;
            return *this;
        }

        //! postfix decrementer
        const_iterator operator--( int )
        {
            // make a copy of this
            const_iterator tmp( *this );
            // decrement self
            this->operator--();
            // return the copy
            return tmp;
        }

        //! Advance iterator specified amount.
        //! Potentially O(n), but typically better.  Always
        //! more efficient than calling operator++ step times.
        const_iterator& operator+=( EntityID step );

        //! Regress iterator specified amount.
        //! Potentially O(n), but typically better.  Always
        //! more efficient than calling operator-- step times.
        const_iterator& operator-=( EntityID step );

        //! equals operator
        bool operator==( const const_iterator& other ) const
        {
            // see if the base iterator is the same and the
            // value of this iterator is the same
            return ( mNode == other.mNode ) && ( mValue == other.mValue );
        }

        //! not equals operator
        bool operator!=( const const_iterator& other ) const
        {
            // call == operator and not it.
            return ( mNode != other.mNode ) || ( mValue != other.mValue );
        }

        /**\brief get an iterator at the end of the block
         *
         * Get an iterator at the end of the block of consecutive
         * handles that this iterator is currently contained in.
         * That is, if the range contains blocks of consecutive
         * handles of the form { [1,5], [7,100], ... } and this
         * iterator is at any handle in the range [7,100], return
         * an iterator at the '100' handle.
         *
         * Never returns begin() or end() unless this iterator is
         * at begin() or end().  May return the same location as
         * this iterator.
         */
        inline const_iterator end_of_block() const;

        /**\brief get an iterator at the start of the block
         *
         * Get an iterator at the start of the block of consecutive
         * handles that this iterator is currently contained in.
         * That is, if the range contains blocks of consecutive
         * handles of the form { [1,5], [7,100], ... } and this
         * iterator is at any handle in the range [7,100], return
         * an iterator at the '7' handle.
         *
         * Never returns end() unless this iterator is
         * at end().  May return the same location as
         * this iterator.
         */
        inline const_iterator start_of_block() const;

      protected:
        //! the node we are pointing at
        PairNode* mNode;
        //! the value in the range
        EntityHandle mValue;
    };

    //! a const reverse iterator which iterates over an Range
    class MOAB_EXPORT const_reverse_iterator : public range_base_iter
    {
        friend class Range;
        friend class pair_iterator;

      public:
        //! default constructor - intialize base default constructor
        const_reverse_iterator() {}

        const_reverse_iterator( const_iterator fwd_iter ) : myIter( fwd_iter ) {}

        //! constructor used by Range
        const_reverse_iterator( const PairNode* iter, const EntityHandle val ) : myIter( iter, val ) {}

        //! dereference that value this iterator points to
        //! returns a const reference
        const EntityHandle& operator*() const
        {
            return *myIter;
        }

        //! prefix incrementer
        const_reverse_iterator& operator++()
        {
            --myIter;
            return *this;
        }

        //! postfix incrementer
        const_reverse_iterator operator++( int )
        {
            return const_reverse_iterator( myIter-- );
        }

        //! prefix decrementer
        const_reverse_iterator& operator--()
        {
            ++myIter;
            return *this;
        }

        //! postfix decrementer
        const_reverse_iterator operator--( int )
        {
            return const_reverse_iterator( myIter++ );
        }

        //! Advance iterator specified amount.
        //! Potentially O(n), but typically better.  Always
        //! more efficient than calling operator++ step times.
        const_reverse_iterator& operator+=( EntityID step )
        {
            myIter -= step;
            return *this;
        }

        //! Regress iterator specified amount.
        //! Potentially O(n), but typically better.  Always
        //! more efficient than calling operator-- step times.
        const_reverse_iterator& operator-=( EntityID step )
        {
            myIter += step;
            return *this;
        }

        //! equals operator
        bool operator==( const const_reverse_iterator& other ) const
        {
            return myIter == other.myIter;
        }

        //! not equals operator
        bool operator!=( const const_reverse_iterator& other ) const
        {
            return myIter != other.myIter;
        }

      protected:
        //! the node we are pointing at
        const_iterator myIter;
    };

  public:
    class MOAB_EXPORT const_pair_iterator
    {
      public:
        const_pair_iterator() : myNode( NULL ) {}
        const_pair_iterator( const PairNode* node ) : myNode( node ) {}
        const_pair_iterator( const const_iterator& i ) : myNode( i.mNode ) {}

        const PairNode& operator*() const
        {
            return *myNode;
        }

        const PairNode* operator->() const
        {
            return myNode;
        }

        const_pair_iterator& operator--()
        {
            myNode = myNode->mPrev;
            return *this;
        }

        const_pair_iterator& operator++()
        {
            myNode = myNode->mNext;
            return *this;
        }

        const_pair_iterator operator--( int )
        {
            const_pair_iterator rval( *this );
            this->operator--();
            return rval;
        }

        const_pair_iterator operator++( int )
        {
            const_pair_iterator rval( *this );
            this->operator++();
            return rval;
        }

        bool operator==( const const_pair_iterator& other ) const
        {
            return other.myNode == myNode;
        }

        bool operator!=( const const_pair_iterator& other ) const
        {
            return other.myNode != myNode;
        }

      private:
        const PairNode* myNode;
    };

    pair_iterator pair_begin()
    {
        return pair_iterator( mHead.mNext );
    }
    pair_iterator pair_end()
    {
        return pair_iterator( &mHead );
    }

    const_pair_iterator const_pair_begin() const
    {
        return const_pair_iterator( mHead.mNext );
    }
    const_pair_iterator const_pair_end() const
    {
        return const_pair_iterator( &mHead );
    }
    const_pair_iterator pair_begin() const
    {
        return const_pair_iterator( mHead.mNext );
    }
    const_pair_iterator pair_end() const
    {
        return const_pair_iterator( &mHead );
    }
};

//! intersect two ranges, placing the results in the return range
Range intersect( const Range&, const Range& );

//! subtract range2 from this, placing the results in the return range
Range subtract( const Range& from, const Range& );

//! unite two ranges, placing the results in the return range
inline Range unite( const Range& r1, const Range& r2 )
{
    Range r( r1 );
    r.insert( r2.begin(), r2.end() );
    return r;
}

inline Range::const_iterator operator+( const Range::const_iterator& it, EntityID step )
{
    Range::const_iterator tmp( it );
    return tmp += step;
}

inline Range::const_iterator operator+( EntityID step, const Range::const_iterator& it )
{
    Range::const_iterator tmp( it );
    return tmp += step;
}

inline Range::const_iterator operator-( const Range::const_iterator& it, EntityID step )
{
    Range::const_iterator tmp( it );
    return tmp -= step;
}

inline Range::const_iterator operator-( EntityID step, const Range::const_iterator& it )
{
    Range::const_iterator tmp( it );
    return tmp -= step;
}

EntityID operator-( const Range::const_iterator& it1, const Range::const_iterator& it2 );

//! Use as you would an STL back_inserter
/**
 *  e.g. std::copy(list.begin(), list.end(), range_inserter(my_range);
 * Also, see comments/instructions at the top of this class declaration
 */
class MOAB_EXPORT range_inserter
{

  protected:
    Range* container;

  public:
    // constructor
    explicit range_inserter( Range& x ) : container( &x ) {}
    range_inserter& operator=( const Range::value_type& value )
    {
        container->insert( value );
        return *this;
    }

    range_inserter& operator*()
    {
        return *this;
    }
    range_inserter& operator++()
    {
        return *this;
    }
    range_inserter& operator++( int )
    {
        return *this;
    }

    typedef EntityHandle value_type;
    typedef EntityID difference_type;
    typedef std::output_iterator_tag iterator_category;
    typedef EntityHandle* pointer;
    typedef EntityHandle& reference;
};

inline Range::Range()
{
    // set the head node to point to itself
    mHead.mNext = mHead.mPrev = &mHead;
    mHead.first = mHead.second = 0;
}

//! destructor
inline Range::~Range()
{
    clear();
}

//! return the beginning const iterator of this range
inline Range::const_iterator Range::begin() const
{
    return const_iterator( mHead.mNext, mHead.mNext->first );
}

//! return the beginning const reverse iterator of this range
inline Range::const_reverse_iterator Range::rbegin() const
{
    return const_reverse_iterator( mHead.mPrev, mHead.mPrev->second );
}

//! return the ending const iterator for this range
inline Range::const_iterator Range::end() const
{
    return const_iterator( &mHead, mHead.first );
}

//! return the ending const reverse iterator for this range
inline Range::const_reverse_iterator Range::rend() const
{
    return const_reverse_iterator( &mHead, mHead.second );
}

//! return whether empty or not
//! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
inline bool Range::empty() const
{
    return ( mHead.mNext == &mHead );
}

//! erases a value from this container
inline Range::iterator Range::erase( EntityHandle val )
{
    return erase( find( val ) );
}

inline Range::const_iterator Range::const_iterator::end_of_block() const
{
    return Range::const_iterator( mNode, mNode->second );
}

inline Range::const_iterator Range::const_iterator::start_of_block() const
{
    return Range::const_iterator( mNode, mNode->first );
}

//! get first entity in range
inline const EntityHandle& Range::front() const
{
    return mHead.mNext->first;
}
//! get last entity in range
inline const EntityHandle& Range::back() const
{
    return mHead.mPrev->second;
}

inline std::ostream& operator<<( std::ostream& s, const Range& r )
{
    r.print( s );
    return s;
}

bool operator==( const Range& r1, const Range& r2 );
inline bool operator!=( const Range& r1, const Range& r2 )
{
    return !( r1 == r2 );
}

inline EntityHandle Range::operator[]( EntityID indexp ) const
{
    Range::const_iterator i = begin();
    i += indexp;
    return *i;
}

inline int Range::index( EntityHandle handle ) const
{
    if( handle < *begin() || handle > *rbegin() ) return -1;

    unsigned int i                 = 0;
    Range::const_pair_iterator pit = const_pair_begin();
    while( handle > ( *pit ).second && pit != const_pair_end() )
    {
        i += ( *pit ).second - ( *pit ).first + 1;
        ++pit;
    }
    if( handle < ( *pit ).first || pit == const_pair_end() ) return -1;

    return i + handle - ( *pit ).first;
}

inline double Range::compactness() const
{
    unsigned int num_ents = size();
    return ( num_ents ? ( (double)get_memory_use() / (double)( num_ents * sizeof( EntityHandle ) ) ) : -1 );
}

template < typename Iterator >
Range::iterator Range::insert_list( Iterator begin_iter, Iterator end_iter )
{
    size_t n             = std::distance( begin_iter, end_iter );
    EntityHandle* sorted = new EntityHandle[n];
    std::copy( begin_iter, end_iter, sorted );
    std::sort( sorted, sorted + n );
    iterator hint = begin();
    size_t i      = 0;
    while( i < n )
    {
        size_t j = i + 1;
        while( j < n && sorted[j] == 1 + sorted[j - 1] )
            ++j;
        hint = insert( hint, sorted[i], sorted[i] + ( ( j - i ) - 1 ) );
        i    = j;
    }
    delete[] sorted;
    return hint;
}

inline size_t Range::psize() const
{
    size_t i = 0;
    Range::const_pair_iterator pit;
    for( pit = const_pair_begin(), i = 0; pit != const_pair_end(); ++pit, i++ )
        ;

    return i;
}

}  // namespace moab

#endif  // MOAB_RANGE_HPP