Range.hpp

Go to the documentation of this file.

#ifndef MOAB_RANGE_HPP
#define MOAB_RANGE_HPP

#include <iterator>
#include <iosfwd>
#include <algorithm>
#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;
};


class 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& );

  Range &operator-=(const Range &rhs);
    
  typedef EntityHandle value_type;

  Range();

  Range(const Range& copy);

  Range( EntityHandle val1, EntityHandle val2 );

  Range& operator=(const Range& copy);
  
  inline ~Range();

  inline const_iterator begin() const;
  
  inline const_reverse_iterator rbegin() const;
 
  inline const_iterator end() const;
  
  inline const_reverse_iterator rend() const;

  size_t size() const;

  size_t psize() const;
  
  inline bool empty() const;

  iterator insert( iterator hint, EntityHandle val );

  iterator insert(EntityHandle val)
    { return insert( begin(), val ); }
  
  iterator insert( iterator hint, EntityHandle first, EntityHandle last );
  
  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 ); }
  
  iterator erase(iterator iter);

  iterator erase( iterator iter1, iterator iter2);

  inline iterator erase(EntityHandle val);
  
  inline const EntityHandle& front() const;
  inline const EntityHandle& back() const;
  EntityHandle pop_front();
  EntityHandle pop_back();
  
  const_iterator find(EntityHandle val) const;

  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;
  
  bool all_of_type( EntityType type ) const;
  bool all_of_dimension( int dimension ) const;
  
  unsigned num_of_type( EntityType type ) const;
  unsigned num_of_dimension( int dim ) const;
  
  void clear();
  
  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 );

  void merge( const Range& range )
    { insert( range.begin(), range.end() ); }
  
  void merge( Range::const_iterator beginr,
              Range::const_iterator endr )
    { insert( beginr, endr ); }

  void swap( Range &range );

  void sanity_check() const;
  
  bool contains( const Range& other ) const;

  Range subset_by_type(EntityType t) const;
  
  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:

  PairNode mHead;
  
  void delete_pair_node( PairNode* dead_node );

public:

  class 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;

  class 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:
    const_iterator() : mNode(NULL), mValue(0) {}

    const_iterator( const PairNode* iter, const EntityHandle val) 
      : mNode(const_cast<PairNode*>(iter)), mValue(val)  {} 

    const EntityHandle& operator*() const { return  mValue; }

    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;
    }

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

    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;
    }

    const_iterator operator--(int)
    {
      // make a copy of this
      const_iterator tmp(*this);
      // decrement self
      this->operator --();
      // return the copy
      return tmp;
    }
    
    const_iterator& operator+=( EntityID step );
    
    const_iterator& operator-=( EntityID step );

    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);
    }

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

  protected:

    PairNode* mNode;
    EntityHandle mValue;
  };

  class const_reverse_iterator : public range_base_iter
  {
    friend class Range;
    friend class pair_iterator;
  public:
    const_reverse_iterator() {}
    
    const_reverse_iterator( const_iterator fwd_iter ) : myIter(fwd_iter) {}

    const_reverse_iterator( const PairNode* iter, const EntityHandle val) 
      : myIter(iter, val)  {} 

    const EntityHandle& operator*() const { return  *myIter; }

    const_reverse_iterator& operator++()
    {
      --myIter;
      return *this;
    }

    const_reverse_iterator operator++(int)
    {
      return const_reverse_iterator( myIter-- );
    }

    const_reverse_iterator& operator--()
    {
      ++myIter;
      return *this;
    }

    const_reverse_iterator operator--(int)
    {
      return const_reverse_iterator( myIter++ );
    }
    
    const_reverse_iterator& operator+=( EntityID step )
    {
      myIter -= step;
      return *this;
    }

    const_reverse_iterator& operator-=( EntityID step )
    {
      myIter += step;
      return *this;
    }

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

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

  protected:

    const_iterator myIter;
  };

public:

  class 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 ); }

};

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

Range subtract( const Range& from, const 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 );


class 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;
}
  
inline Range::~Range()
{
  clear();
}

inline Range::const_iterator Range::begin() const
{
  return const_iterator(mHead.mNext, mHead.mNext->first);
}
  
inline Range::const_reverse_iterator Range::rbegin() const
{
  return const_reverse_iterator(mHead.mPrev, mHead.mPrev->second);
}
 
inline Range::const_iterator Range::end() const
{
  return const_iterator(&mHead, mHead.first);
}
  
inline Range::const_reverse_iterator Range::rend() const
{
  return const_reverse_iterator(&mHead, mHead.second);
}

inline bool Range::empty() const
{
  return (mHead.mNext == &mHead);
}

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 ); }

inline const EntityHandle& Range::front() const
  { return mHead.mNext->first; }
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