// lib/prec_stl/iterator

#pragma ifndef PREC_STL_ITERATOR
#pragma define PREC_STL_ITERATOR
#pragma link off global PREC_STL_ITERATOR;
#pragma link C++ nestedtypedef;
#pragma link C++ nestedclass;
#if defined(G__HP_aCC) || defined(G__SUNPRO_C)
#pragma mask_newdelete 0x1c;
#else
#pragma mask_newdelete 0x10;
#endif

// Imported from STL HP implementation 1994
// Imported from STL SGI implementation 1997 
// Imported from ANSI/ISO C++ draft Nov 1997
// Modified by Masaharu Goto
// May need to improve for the latest standard

#ifndef G__VISUAL
////////////////////////////////////////////////////////////////////////
// iterator_tag
////////////////////////////////////////////////////////////////////////
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag {};
struct bidirectional_iterator_tag {};
struct random_access_iterator_tag {};

////////////////////////////////////////////////////////////////////////
// iterator template
////////////////////////////////////////////////////////////////////////
template <class T, class Distance> struct input_iterator {};
struct output_iterator {};
template <class T, class Distance> struct forward_iterator {};
template <class T, class Distance> struct bidirectional_iterator {};
template <class T, class Distance> struct random_access_iterator {};
#else
struct output_iterator;
#endif

////////////////////////////////////////////////////////////////////////
// iterator_category overloaded function
////////////////////////////////////////////////////////////////////////
template <class T, class Distance> 
inline input_iterator_tag 
iterator_category(const input_iterator<T, Distance>&) {
    return input_iterator_tag();
}

inline output_iterator_tag iterator_category(const output_iterator&) {
    return output_iterator_tag();
}

template <class T, class Distance> 
inline forward_iterator_tag
iterator_category(const forward_iterator<T, Distance>&) {
    return forward_iterator_tag();
}

template <class T, class Distance> 
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator<T, Distance>&) {
    return bidirectional_iterator_tag();
}

template <class T, class Distance> 
inline random_access_iterator_tag
iterator_category(const random_access_iterator<T, Distance>&) {
    return random_access_iterator_tag();
}

template <class T>
inline random_access_iterator_tag 
iterator_category(const T*) {
    return random_access_iterator_tag();
}


// iterator_traits, iterator and reverse_iterator template may not be
// needed for precompiled library interface 

////////////////////////////////////////////////////////////////////////
// iterator_traits
////////////////////////////////////////////////////////////////////////

template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_type;
  typedef typename Iterator::difference_type   difference_type;
  typedef typename Iterator::pointer           pointer;
  typedef typename Iterator::reference         reference;
};

// template partial specialization, implement in cint5.15.14 1587
template <class T>
struct iterator_traits<T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

// incomplete implementation in cint5.15.14 1587, need some fix
// iterator_traits<const int*> is changed as iterator_traits<const int* const>
// or something, but cint5.15.14 can not handle this well
template <class T>
struct iterator_traits<const T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

////////////////////////////////////////////////////////////////////////
// iterator
////////////////////////////////////////////////////////////////////////
template<class Category, class T, class Distance = ptrdiff_t,
         class Pointer = T*, class Reference = T&>
struct iterator {
  typedef T         value_type;
  typedef Distance  difference_type;
  typedef Pointer   pointer;
  typedef Reference reference;
  typedef Category  iterator_category;
};


////////////////////////////////////////////////////////////////////////
// reverse_iterator
////////////////////////////////////////////////////////////////////////
template <class Iterator>
class reverse_iterator 
#if defined(G__KCC)
  : public iterator<iterator_traits<Iterator>::iterator_category,
                    iterator_traits<Iterator>::value_type,
                    iterator_traits<Iterator>::difference_type,
                    iterator_traits<Iterator>::pointer,
                    iterator_traits<Iterator>::reference> 
#endif
{
#if 0
 protected:
  Iterator current;
#endif
 public:
#if defined(G__KCC)
   typedef Iterator iterator_type;
   typedef typename iterator_traits<Iterator>::difference_type difference_type;
   typedef typename iterator_traits<Iterator>::reference reference;
   typedef typename iterator_traits<Iterator>::pointer pointer;
#else
   typedef Iterator::pointer   pointer;
   typedef Iterator::reference reference;
   typedef ptrdiff_t difference_type;
#endif

   reverse_iterator();
   //reverse_iterator(Iterator x);
#if 0
   template <class U> reverse_iterator(const reverse_iterator<U>& u);
#endif
   Iterator base() const;      // explicit
   reference operator*() const;
   pointer   operator->() const;
   reverse_iterator& operator++();
   reverse_iterator  operator++(int);
   reverse_iterator& operator--();
   reverse_iterator  operator--(int);
   reverse_iterator  operator+ (difference_type n) const;
   reverse_iterator& operator+=(difference_type n);
   reverse_iterator  operator- (difference_type n) const;
   reverse_iterator& operator-=(difference_type n);
   reference operator[](difference_type n) const;
}; 

#if defined(G__BORLANDCC5) 
template <class T>
class reverse_iterator<T*> {
 public:
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
   reverse_iterator();
   //reverse_iterator(Iterator x);
#if 0
   template <class U> reverse_iterator(const reverse_iterator<U>& u);
#endif
   //Iterator base() const;      // explicit
   reference operator*() const;
   pointer   operator->() const;
   reverse_iterator& operator++();
   reverse_iterator  operator++(int);
   reverse_iterator& operator--();
   reverse_iterator  operator--(int);
   reverse_iterator  operator+ (difference_type n) const;
   reverse_iterator& operator+=(difference_type n);
   reverse_iterator  operator- (difference_type n) const;
   reverse_iterator& operator-=(difference_type n);
   reference operator[](difference_type n) const;
};
#endif

#ifdef G__VISUAL
// VC++5.0 has different symbol names

////////////////////////////////////////////////////////////////////////
// iterator_tag
////////////////////////////////////////////////////////////////////////
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag
	: public input_iterator_tag {};
struct bidirectional_iterator_tag
	: public forward_iterator_tag {};
struct random_access_iterator_tag
	: public bidirectional_iterator_tag  {};

////////////////////////////////////////////////////////////////////////
// iterator template
////////////////////////////////////////////////////////////////////////
template <class T, class Distance> struct input_iterator {};
struct output_iterator {};
template <class T, class Distance> struct forward_iterator {};
template <class T, class Distance> struct _Bidit {};
template <class T, class Distance> struct _Ranit {};

////////////////////////////////////////////////////////////////////////
// _Iter_cat overloaded function
////////////////////////////////////////////////////////////////////////
template <class T, class Distance> 
inline input_iterator_tag 
_Iter_cat(const input_iterator<T, Distance>&) {
    return input_iterator_tag();
}

inline output_iterator_tag _Iter_cat(const output_iterator&) {
    return output_iterator_tag();
}

template <class T, class Distance> 
inline forward_iterator_tag
_Iter_cat(const forward_iterator<T, Distance>&) {
    return forward_iterator_tag();
}

template <class T, class Distance> 
inline bidirectional_iterator_tag
_Iter_cat(const _Bidit<T, Distance>&) {
    return bidirectional_iterator_tag();
}

template <class T, class Distance> 
inline random_access_iterator_tag
_Iter_cat(const _Ranit<T, Distance>&) {
    return random_access_iterator_tag();
}

template <class T>
inline random_access_iterator_tag 
_Iter_cat(const T*) {
    return random_access_iterator_tag();
}
#endif

#if (G__GNUC>=3) && !defined(G__KCC)

#if (G__GNUC_MINOR<1) 
// for g++ 3.00
////////////////////////////////////////////////////////////////////////
// __normal_iterator
////////////////////////////////////////////////////////////////////////
template<typename _Iterator, typename _Container>
class __normal_iterator
  : public std::iterator<std::iterator_traits<_Iterator>::iterator_category,
                    std::iterator_traits<_Iterator>::value_type,
                    std::iterator_traits<_Iterator>::difference_type,
                    std::iterator_traits<_Iterator>::pointer,
                    std::iterator_traits<_Iterator>::reference>
{

public:
  typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
  typedef std::iterator_traits<_Iterator> 		__traits_type;
  typedef typename _Iterator::iterator_category 	iterator_category;
  typedef typename _Iterator::value_type 		value_type;
  typedef typename _Iterator::difference_type 	difference_type;
  typedef typename _Iterator::pointer          	pointer;
  typedef typename _Iterator::reference 		reference;

  //typedef typename __traits_type::iterator_category 	iterator_category;
  //typedef typename __traits_type::value_type 		value_type;
  //typedef typename __traits_type::difference_type 	difference_type;
  //typedef typename __traits_type::pointer          	pointer;
  //typedef typename __traits_type::reference 		reference;

  __normal_iterator() ;

#ifndef __CINT__ //this can be a problem, may need solution not to mask this
  explicit __normal_iterator(const _Iterator& __i) ;
#endif

  // Allow iterator to const_iterator conversion
  template<typename _Iter>
  inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i);

  //There was a big hussle compiling operator*(), partial template 
  //specialization for iterator_traits<T*> used in __normal_iterator.

  // Forward iterator requirements
  reference operator*() const ; 

  pointer operator->() const ;

  normal_iterator_type& operator++() ;

  normal_iterator_type operator++(int) ;

  // Bidirectional iterator requirements
  normal_iterator_type& operator--() ;

  normal_iterator_type operator--(int) ;

  // Random access iterator requirements
  reference operator[](const difference_type& __n) const;

  normal_iterator_type& operator+=(const difference_type& __n);

  normal_iterator_type operator+(const difference_type& __n) const;

  normal_iterator_type& operator-=(const difference_type& __n);

  normal_iterator_type operator-(const difference_type& __n) const;

  difference_type operator-(const normal_iterator_type& __i) const;

  const _Iterator& base() const ;

  friend bool operator==(const __normal_iterator<_Iterator,_Container>&,
		const __normal_iterator<_Iterator,_Container>&);
  friend bool operator!=(const __normal_iterator<_Iterator,_Container>&,
		const __normal_iterator<_Iterator,_Container>&);
  friend bool operator<(const __normal_iterator<_Iterator,_Container>&,
		const __normal_iterator<_Iterator,_Container>&);
  friend bool operator>(const __normal_iterator<_Iterator,_Container>&,
		const __normal_iterator<_Iterator,_Container>&);
  friend bool operator<=(const __normal_iterator<_Iterator,_Container>&,
		const __normal_iterator<_Iterator,_Container>&);
  friend bool operator>=(const __normal_iterator<_Iterator,_Container>&,
		const __normal_iterator<_Iterator,_Container>&);
};

// forward iterator requirements

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
	   const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return __lhs.base() == __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
	   const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return !(__lhs == __rhs); }

// random access iterator requirements

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool 
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
	  const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return __lhs.base() < __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
	  const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return __rhs < __lhs; }

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
	   const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return !(__rhs < __lhs); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
	   const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return !(__lhs < __rhs); }

template<typename _Iterator, typename _Container>
inline __normal_iterator<_Iterator, _Container>
operator+(__normal_iterator<_Iterator, _Container>::difference_type __n,
          const __normal_iterator<_Iterator, _Container>& __i)
{ return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }

#else // (G__GNUC_MINOR>=1) 

#ifdef G__OLDIMPLEMENTATION1703
// for g++ 3.1,3.2
namespace __gnu_cxx
{  
  // This iterator adapter is 'normal' in the sense that it does not
  // change the semantics of any of the operators of its iterator
  // parameter.  Its primary purpose is to convert an iterator that is
  // not a class, e.g. a pointer, into an iterator that is a class.
  // The _Container parameter exists solely so that different containers
  // using this template can instantiate different types, even if the
  // _Iterator parameter is the same.
  using std::iterator_traits;
  using std::iterator;
  template<typename _Iterator, typename _Container>
    class __normal_iterator
      : public iterator<typename iterator_traits<_Iterator>::iterator_category,
                        typename iterator_traits<_Iterator>::value_type,
                        typename iterator_traits<_Iterator>::difference_type,
                        typename iterator_traits<_Iterator>::pointer,
                        typename iterator_traits<_Iterator>::reference>
    {
    protected:
      _Iterator _M_current;
      
    public:
      typedef typename iterator_traits<_Iterator>::difference_type 	
      							       difference_type;
      typedef typename iterator_traits<_Iterator>::reference   reference;
      typedef typename iterator_traits<_Iterator>::pointer     pointer;

      __normal_iterator() : _M_current(_Iterator()) { }

      explicit 
      __normal_iterator(const _Iterator& __i) : _M_current(__i) { }

      // Allow iterator to const_iterator conversion
      template<typename _Iter>
      inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
	: _M_current(__i.base()) { }

      // Forward iterator requirements
      reference
      operator*() const { return *_M_current; }
      
      pointer
      operator->() const { return _M_current; }
      
      __normal_iterator&
      operator++() { ++_M_current; return *this; }
      
      __normal_iterator
      operator++(int) { return __normal_iterator(_M_current++); }
      
      // Bidirectional iterator requirements
      __normal_iterator&
      operator--() { --_M_current; return *this; }
      
      __normal_iterator
      operator--(int) { return __normal_iterator(_M_current--); }
      
      // Random access iterator requirements
      reference
      operator[](const difference_type& __n) const
      { return _M_current[__n]; }
      
      __normal_iterator&
      operator+=(const difference_type& __n)
      { _M_current += __n; return *this; }

      __normal_iterator
      operator+(const difference_type& __n) const
      { return __normal_iterator(_M_current + __n); }
      
      __normal_iterator&
      operator-=(const difference_type& __n)
      { _M_current -= __n; return *this; }
      
      __normal_iterator
      operator-(const difference_type& __n) const
      { return __normal_iterator(_M_current - __n); }
      
      const _Iterator& 
      base() const { return _M_current; }
    };

  // Note: In what follows, the left- and right-hand-side iterators are
  // allowed to vary in types (conceptually in cv-qualification) so that
  // comparaison between cv-qualified and non-cv-qualified iterators be
  // valid.  However, the greedy and unfriendly operators in std::rel_ops
  // will make overload resolution ambiguous (when in scope) if we don't
  // provide overloads whose operands are of the same type.  Can someone
  // remind me what generic programming is about? -- Gaby
  
  // Forward iterator requirements
  template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
	     const __normal_iterator<_IteratorR, _Container>& __rhs)
  { return __lhs.base() == __rhs.base(); }

  template<typename _Iterator, typename _Container>
  inline bool
  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
             const __normal_iterator<_Iterator, _Container>& __rhs)
  { return __lhs.base() == __rhs.base(); }

  template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
	     const __normal_iterator<_IteratorR, _Container>& __rhs)
  { return __lhs.base() != __rhs.base(); }

  template<typename _Iterator, typename _Container>
  inline bool
  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
             const __normal_iterator<_Iterator, _Container>& __rhs)
  { return __lhs.base() != __rhs.base(); }

  // Random access iterator requirements
  template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool 
  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
	    const __normal_iterator<_IteratorR, _Container>& __rhs)
  { return __lhs.base() < __rhs.base(); }

  template<typename _Iterator, typename _Container>
  inline bool
  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
             const __normal_iterator<_Iterator, _Container>& __rhs)
  { return __lhs.base() < __rhs.base(); }

  template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
	    const __normal_iterator<_IteratorR, _Container>& __rhs)
  { return __lhs.base() > __rhs.base(); }

  template<typename _Iterator, typename _Container>
  inline bool
  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
	    const __normal_iterator<_Iterator, _Container>& __rhs)
  { return __lhs.base() > __rhs.base(); }

  template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
	     const __normal_iterator<_IteratorR, _Container>& __rhs)
  { return __lhs.base() <= __rhs.base(); }

  template<typename _Iterator, typename _Container>
  inline bool
  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
	     const __normal_iterator<_Iterator, _Container>& __rhs)
  { return __lhs.base() <= __rhs.base(); }

  template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
	     const __normal_iterator<_IteratorR, _Container>& __rhs)
  { return __lhs.base() >= __rhs.base(); }

  template<typename _Iterator, typename _Container>
  inline bool
  operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
	     const __normal_iterator<_Iterator, _Container>& __rhs)
  { return __lhs.base() >= __rhs.base(); }

  // _GLIBCPP_RESOLVE_LIB_DEFECTS
  // According to the resolution of DR179 not only the various comparison
  // operators but also operator- must accept mixed iterator/const_iterator
  // parameters.
  template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
	     const __normal_iterator<_IteratorR, _Container>& __rhs)
  { return __lhs.base() - __rhs.base(); }

  template<typename _Iterator, typename _Container>
  inline __normal_iterator<_Iterator, _Container>
  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type __n,
	    const __normal_iterator<_Iterator, _Container>& __i)
  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
} // namespace __gnu_cxx
#endif

#endif // G__GNUC_MINOR


#endif // G__GNUC>=3

#pragma endif
