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

#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)
// for g++ 3.00
////////////////////////////////////////////////////////////////////////
// __normal_iterator
////////////////////////////////////////////////////////////////////////
template<typename _Iterator, typename _Container>
class __normal_iterator
  : 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>
{

public:
  typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
  typedef iterator_traits<_Iterator>  			__traits_type;
  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 ;
};

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


#endif // G__GNUC>=3

#pragma endif