// -*- C++ -*-
#ifndef __STD_ITERATOR__
#define __STD_ITERATOR__

/***************************************************************************
 *
 * iterator - iterator declarations for the Standard Library
 *
 ***************************************************************************
 *    
 *  Copyright 2000 Compaq Computer Corporation
 *
 *  COMPAQ Registered in U.S. Patent and Trademark Office.
 *
 *  Confidential computer software. Valid license from Compaq required for
 *  possession, use or copying. Consistent with FAR 12.211 and 12.212,
 *  Commercial Computer Software, Computer Software Documentation, and
 *  Technical Data for Commercial Items are licensed to the U.S. Government
 *  under vendor's standard commercial license.
 *
 ****************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 ***************************************************************************
 *
 * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/

#include <stdcomp>
#include <stddefs>

#ifndef _RWSTD_NO_NEW_HEADER
#include <cstddef>
#else
#include <stddef.h>
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __save
#      pragma __environment __header_defaults
#   endif
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#pragma __extern_prefix __save
#pragma __extern_prefix "CXXL$" 
#endif

#ifdef _RWSTD_NO_BASE_CLASS_MATCH
#define _RWSTD_VALUE_TYPE(a) _RWvalue_type(*(a))
#else
#define _RWSTD_VALUE_TYPE(a) _RWvalue_type(a)
#endif

#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

//
// Standard iterator tags.
//
  
  struct input_iterator_tag
  {
    input_iterator_tag() {;}
  };

  struct output_iterator_tag
  {
    output_iterator_tag() {;}
  };

  struct forward_iterator_tag : public input_iterator_tag
  {
    forward_iterator_tag() {;}
  };

  struct bidirectional_iterator_tag : public forward_iterator_tag
  {
    bidirectional_iterator_tag() {;}
  };

  struct random_access_iterator_tag : public bidirectional_iterator_tag
  {
    random_access_iterator_tag() {;}
  };


//
// Basic iterators.
//

//
// Note that _RWSTD_SIMPLE_DEFAULT(x)
// will expand to: ' = x', or nothing,
// depending on your compiler's capabilities and/or
// flag settings (see stdcomp.h).
//
  template <class Category, class T,  
    class Distance _RWSTD_SIMPLE_DEFAULT(ptrdiff_t),
    class Pointer _RWSTD_SIMPLE_DEFAULT(T*),
    class Reference _RWSTD_SIMPLE_DEFAULT(T&)>
  struct iterator
  {
    typedef T value_type;
    typedef Distance difference_type;
    typedef Pointer pointer;
    typedef Reference reference;
    typedef Category iterator_category;
  };

#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

  template <class Iterator> struct iterator_traits
  {
    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 Iterator::iterator_category iterator_category;
  };
  template <class T> struct iterator_traits<T*>
  {
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;
    typedef random_access_iterator_tag iterator_category;
  };
  template <class T> struct iterator_traits<const T*>
  {
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef const T* pointer;
    typedef const T& reference;
    typedef random_access_iterator_tag iterator_category;
  };

  template <class ForwardIterator>
  inline _TYPENAME iterator_traits<ForwardIterator>::difference_type
  distance (ForwardIterator first, ForwardIterator last)
  {
    _TYPENAME iterator_traits<ForwardIterator>::difference_type n = 0;
    _RWdistance(first, last, n, 
               iterator_traits<ForwardIterator>::iterator_category());
    return n;
  }

  template <class ForwardIterator, class Distance>
  inline void advance (ForwardIterator& i, Distance n)
  {
    _RWadvance(i, n, 
          iterator_traits<ForwardIterator>::iterator_category());
  }

#endif /* _RWSTD_NO_CLASS_PARTIAL_SPEC */

//
// _RWiterator_category returns the category of an iterator
//

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

  template <class Category, class T, class Distance, 
            class Pointer, class Reference> 
  inline Category
  _RWiterator_category (const iterator<Category, T, Distance,Pointer,Reference>&)
  {
    _TYPENAME iterator<Category, T, Distance,T*,T&>::iterator_category tmp;
    return tmp;
  }

#if defined(__DECCXX) && !defined(__DECFIXCXXL1053)
  template <class T> 
  inline _TYPENAME T::iterator_category
  _RWiterator_category (const T&)
  {
    _TYPENAME T::iterator_category tmp;
    return tmp;
  }
#endif


//
// Special implementation function for determining whether
// or not we can back up an iterator
//
  template <class _TAG>
  inline bool _RWis_bidirectional_iterator(_TAG)
  { return false; }

  template <class _TAG>
  inline bool _RWis_random_access_iterator(_TAG)
  { return false; }

  inline bool _RWis_bidirectional_iterator(bidirectional_iterator_tag)
  { return true; }

  inline bool _RWis_bidirectional_iterator(random_access_iterator_tag)
  { return true; }

  inline bool _RWis_random_access_iterator(random_access_iterator_tag)
  { return true; }

//
// _RWvalue_type returns the type of value held by an iterator
//
  template <class Category,class T, class Distance,
            class Pointer, class Reference>
  inline T* _RWvalue_type (const iterator<Category,T, Distance,Pointer,Reference>&)
  {
    return _RWSTD_STATIC_CAST(T*,0);
  }

  template <class T>
  inline T* 
  _RWvalue_type (const T*)
  {
    return _RWSTD_STATIC_CAST(T*,0);
  }

#if defined(__DECCXX) && !defined(__DECFIXCXXL1053)
  template <class T> 
  inline _TYPENAME T::value_type*
  _RWvalue_type (const T&)
  {
    return _RWSTD_STATIC_CAST(_TYPENAME T::value_type*,0);
  }
#endif

//
// _RWdistance_type returns the difference type of an iterator
//
  template <class Category,class T, class Distance, 
            class Pointer, class Reference>
  inline Distance* 
  _RWdistance_type (const iterator<Category,T, Distance,Pointer,Reference>&)
  {
    return _RWSTD_STATIC_CAST(Distance*,0);
  }

  template <class T>
  inline ptrdiff_t* 
  _RWdistance_type (const T*)
  { 
    return _RWSTD_STATIC_CAST(ptrdiff_t*,0);
  }

#if defined(__DECCXX) && !defined(__DECFIXCXXL1053)
// add a distance_type for user-defined iterators
  template <class T>
  inline _TYPENAME T::difference_type*
  _RWdistance_type(const T&) 
  { 
    return _RWSTD_STATIC_CAST(_TYPENAME T::difference_type*,0);
  }
#endif

//
// Implementation specific iterator operations.
//

  template <class InputIterator, class Distance>
  void _RWadvance (InputIterator& i, Distance n, input_iterator_tag);

  template <class ForwardIterator, class Distance>
  void _RWadvance (ForwardIterator& i, Distance n, forward_iterator_tag);

  template <class BidirectionalIterator, class Distance>
  void _RWadvance (BidirectionalIterator& i, Distance n, 
                  bidirectional_iterator_tag);

  template <class InputIterator, class Distance>
  void _RWdistance (InputIterator first, InputIterator last, Distance& n, 
                   input_iterator_tag);

  template <class ForwardIterator, class Distance>
  void _RWdistance (ForwardIterator first, ForwardIterator last, Distance& n, 
                   forward_iterator_tag);

  template <class BidirectionalIterator, class Distance>
  void _RWdistance (BidirectionalIterator first, BidirectionalIterator last, 
                   Distance& n, bidirectional_iterator_tag);

  template <class RandomAccessIterator, class Distance>
  inline void _RWdistance (RandomAccessIterator first, RandomAccessIterator last, 
                          Distance& n, random_access_iterator_tag)
  {
    n = last - first;
  }

  template <class RandomAccessIterator, class Distance>
  inline void _RWadvance (RandomAccessIterator& i, Distance n, 
                         random_access_iterator_tag)
  {
    i += n;
  }

//
// End of implemention specific functions
//

  template <class ForwardIterator, class Distance>
  inline void distance (ForwardIterator first, ForwardIterator last, Distance& n)
  {
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    _RWdistance(first, last, n, _RWiterator_category(first));
#else
    _RWdistance(first, last, n, input_iterator_tag());
#endif
  }


#ifdef _RWSTD_NO_CLASS_PARTIAL_SPEC
  template <class ForwardIterator, class Distance>
  inline void advance (ForwardIterator& i, Distance n)
  {
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    _RWadvance(i, n, _RWiterator_category(i));
#else
    _RWadvance(i, n, input_iterator_tag());
#endif
  }
#endif /* _RWSTD_NO_CLASS_PARTIAL_SPEC */

//
// Reverse iterator.     
//

//
//  Macros for reverse iterator to accomodate non-standard compilers
//
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
#define _RWSTD_REVERSE_ITERATOR_TEMPLATE template <class Iterator>
#define _RWSTD_REVERSE_ITERATOR_TYPE reverse_iterator<Iterator>
#else
#define _RWSTD_REVERSE_ITERATOR_TEMPLATE \
template <class Iterator, class Category, class T, class Reference,  class Pointer, class Distance>
#define _RWSTD_REVERSE_ITERATOR_TYPE \
 reverse_iterator<Iterator,Category,T,Reference,Pointer,Distance>
#endif


//
// Forward Declarations.
//
#ifdef _RWSTD_NO_UNDEFINED_FRIEND
  _RWSTD_REVERSE_ITERATOR_TEMPLATE class reverse_iterator;

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator== (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                          const _RWSTD_REVERSE_ITERATOR_TYPE& y);

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator< (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                         const _RWSTD_REVERSE_ITERATOR_TYPE& y);

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline 
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
  _TYPENAME iterator_traits<Iterator>::difference_type
#else
  Distance
#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC 
  operator- (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
             const _RWSTD_REVERSE_ITERATOR_TYPE& y);

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline _RWSTD_REVERSE_ITERATOR_TYPE
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
  operator+ (_TYPENAME iterator_traits<Iterator>::difference_type n, 
#if defined(__DECCXX) && !defined(__DECFIXCXXL979)
#if defined(__DECCXX) && !defined(__DECFIXCXXL980)
             const _RWSTD_REVERSE_ITERATOR_TYPE& x);
#else
             _RWSTD_REVERSE_ITERATOR_TYPE& x);
#endif
#else
             _RWSTD_REVERSE_ITERATOR_TYPE& x)
#endif
#else
#if defined(__DECCXX) && !defined(__DECFIXCXXL980)
  operator+ (Distance n, const _RWSTD_REVERSE_ITERATOR_TYPE& x);
#else
  operator+ (Distance n, _RWSTD_REVERSE_ITERATOR_TYPE& x);
#endif
#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC 
#endif // _RWSTD_NO_UNDEFINED_FRIEND

#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
  template <class Iterator>
  class reverse_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>
  {
    typedef reverse_iterator<Iterator> self;
  public:
    typedef typename iterator_traits<Iterator>::difference_type difference_type;
    typedef typename iterator_traits<Iterator>::value_type value_type;
    typedef typename iterator_traits<Iterator>::pointer pointer;
    typedef typename iterator_traits<Iterator>::reference reference;
  private:
#else
  template <class Iterator, class Category, class T, 
            class Reference _RWSTD_COMPLEX_DEFAULT(T&),
            class Pointer _RWSTD_COMPLEX_DEFAULT(T*), 
            class Distance _RWSTD_COMPLEX_DEFAULT(ptrdiff_t) >
  class reverse_iterator
   : public iterator<Category,T, Distance,Pointer,Reference>

  {
    typedef reverse_iterator<Iterator,Category,T,Reference,Pointer,Distance> self;
  public:
    typedef Distance difference_type;
    typedef T value_type;
    typedef Reference reference;
    typedef Pointer pointer;
  private:
#endif

#if defined(__DECCXX) && !defined(__DECFIXCXXL978)
    friend bool std::operator== <Iterator>    (const self& x, const self& y);
    friend bool std::operator<  <Iterator>    (const self& x, const self& y);
    friend difference_type std::operator- <Iterator> (const self& x, const self& y);
    friend self std::operator+ <Iterator>     (difference_type n, const self& x);
#else
    friend inline bool operator==    (const self& x, const self& y);
    friend inline bool operator<     (const self& x, const self& y);
    friend inline difference_type operator- (const self& x, const self& y);
    friend inline self operator+     (difference_type n, const self& x);
#endif
        
  protected:

    Iterator current;

  public:
    typedef Iterator iterator_type;

    reverse_iterator() {}
    _EXPLICIT reverse_iterator (Iterator x) : current(x) {}
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
    template <class U>
#if defined(__DECCXX) && !defined(__DECFIXCXXL1069)
    reverse_iterator (const reverse_iterator<U>& x) : current(x.base()) {}
#else
    reverse_iterator (const reverse_iterator<U>& x) : current(x) {}
#endif
#endif
    Iterator base () const { return current; }
    reference operator* () const 
    { Iterator tmp = current; return *--tmp; }
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
    pointer operator->() const 
    { reference tmp = operator*(); return (pointer)&tmp; }
#endif

    self& operator++ ()    { --current; return *this;                 }
    self  operator++ (int) { self tmp = *this; --current; return tmp; }
    self& operator-- ()    { ++current; return *this;                 }
    self  operator-- (int) { self tmp = *this; ++current; return tmp; }

    self  operator+  (difference_type n) const 
    {  self tmp(current - n); return tmp; }
    self& operator+= (difference_type n)       { current -= n; return *this;        }
    self  operator-  (difference_type n) const { self tmp(current + n); return tmp; }
    self& operator-= (difference_type n)       { current += n; return *this;        }

    reference operator[] (difference_type n) const { return *(*this + n); }
  };


  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator== (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                          const _RWSTD_REVERSE_ITERATOR_TYPE& y)
  {
    return x.current == y.current;
  }

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator< (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                         const _RWSTD_REVERSE_ITERATOR_TYPE& y)
  {
    return y.current < x.current;
  }

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator!= (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                          const _RWSTD_REVERSE_ITERATOR_TYPE& y)
  {
    return !(x == y);
  }

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator> (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                         const _RWSTD_REVERSE_ITERATOR_TYPE& y)
  {
    return y < x;
  }

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator<= (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                          const _RWSTD_REVERSE_ITERATOR_TYPE& y)
  {
    return !(y < x);
  }

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator>= (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                          const _RWSTD_REVERSE_ITERATOR_TYPE& y)
  {
    return !(x < y);
  }
#endif // _RWSTD_NO_NAMESPACE) || _RWSTD_NO_PART_SPEC_OVERLOAD

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline 
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
  _TYPENAME iterator_traits<Iterator>::difference_type
#else
  Distance
#endif
  operator- (const _RWSTD_REVERSE_ITERATOR_TYPE& x, 
                             const _RWSTD_REVERSE_ITERATOR_TYPE& y)
  {
    return y.current - x.current;
  }

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline _RWSTD_REVERSE_ITERATOR_TYPE
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
  operator+ (_TYPENAME iterator_traits<Iterator>::difference_type n, 
#if defined(__DECCXX) && !defined(__DECFIXCXXL980)
             const _RWSTD_REVERSE_ITERATOR_TYPE& x)
#else
             _RWSTD_REVERSE_ITERATOR_TYPE& x)
#endif
#else // NO PARTIAL SPEC
#if defined(__DECCXX) && !defined(__DECFIXCXXL980)
  operator+ (Distance n, const _RWSTD_REVERSE_ITERATOR_TYPE& x)
#else
  operator+ (Distance n, _RWSTD_REVERSE_ITERATOR_TYPE& x)
#endif
#endif
  {
    return _RWSTD_REVERSE_ITERATOR_TYPE(x.current - n);
  }


#ifdef _RWSTD_NO_CLASS_PARTIAL_SPEC
//
// Reverse bidirectional iterator.       
// This is needed to get around non-standard compilers that insist
// on instantiating all members of a class whether they're used 
// or not.
//

//
//  Macros for reverse iterator to accomodate non-standard compilers
//
#define _RWSTD_REVERSE_BI_ITERATOR_TYPE \
 _RWreverse_bi_iterator<Iterator,Category,T,Reference,Pointer,Distance>


//
// Forward Declarations.
//
#ifdef _RWSTD_NO_UNDEFINED_FRIEND

  _RWSTD_REVERSE_ITERATOR_TEMPLATE class _RWreverse_bi_iterator;

  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator== (const _RWSTD_REVERSE_BI_ITERATOR_TYPE& x, 
                          const _RWSTD_REVERSE_BI_ITERATOR_TYPE& y);

#endif // _RWSTD_NO_UNDEFINED_FRIEND

  template <class Iterator, class Category, class T, 
            class Reference _RWSTD_COMPLEX_DEFAULT(T&),
            class Pointer _RWSTD_COMPLEX_DEFAULT(T*), 
            class Distance _RWSTD_COMPLEX_DEFAULT(ptrdiff_t) >
  class _RWreverse_bi_iterator
   : public iterator<Category,T, Distance,Pointer,Reference>

  {
    typedef _RWreverse_bi_iterator<Iterator,Category,T,Reference,Pointer,Distance> self;
    typedef Distance difference_type;
    typedef T value_type;
    typedef Reference reference;
    typedef Pointer pointer;

#if defined(__DECCXX) && !defined(__DECFIXCXXL978)
    friend bool operator== <Iterator,Category,T,Reference,Pointer,Distance>   (const self& x, const self& y);
#else
    friend inline bool operator==    (const self& x, const self& y);
#endif
        
  protected:

    Iterator current;

  public:
    typedef Iterator iterator_type;

    _RWreverse_bi_iterator() {}
    _EXPLICIT _RWreverse_bi_iterator (Iterator x) : current(x) {}
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
    template <class U>
    _EXPLICIT _RWreverse_bi_iterator (const reverse_iterator<U>) : current(x) {}
#endif
    Iterator base () const { return current; }
    reference operator* () const 
    { Iterator tmp = current; return *--tmp; }
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
    pointer operator->() const 
    { reference tmp = operator*(); return (pointer)&tmp; }
#endif

    self& operator++ ()    { --current; return *this;                 }
    self  operator++ (int) { self tmp = *this; --current; return tmp; }
    self& operator-- ()    { ++current; return *this;                 }
    self  operator-- (int) { self tmp = *this; ++current; return tmp; }
  };


  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator== (const _RWSTD_REVERSE_BI_ITERATOR_TYPE& x, 
                          const _RWSTD_REVERSE_BI_ITERATOR_TYPE& y)
  {
    return x.current == y.current;
  }

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
  _RWSTD_REVERSE_ITERATOR_TEMPLATE
  inline bool operator!= (const _RWSTD_REVERSE_BI_ITERATOR_TYPE& x, 
                          const _RWSTD_REVERSE_BI_ITERATOR_TYPE& y)
  {
    return !(x == y);
  }

#endif  // _RWSTD_NO_NAMESPACE || _RWSTD_NO_PART_SPEC_OVERLOAD
#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC

//
// Back insert iterator.
//

  template <class Container>
  class back_insert_iterator 
    : public iterator<output_iterator_tag,
#if defined(__DECCXX) && !defined(__DECFIXCXXL1201)
	void, void, void, void>
#else
                      _TYPENAME Container::value_type,
                      _TYPENAME Container::difference_type,
                      _TYPENAME Container::pointer,
                      _TYPENAME Container::reference> 
#endif
  {
  protected:

    Container* container;

  public:
    typedef Container container_type;
    typedef _TYPENAME Container::value_type value_type;

    _EXPLICIT back_insert_iterator (Container& x) : container(&x) {}
    back_insert_iterator<Container>&
#if defined(__DECCXX) && !defined(__DECFIXCXXL1042)
    operator= (const _TYPENAME Container::const_reference value)
#else
    operator= (const _TYPENAME Container::value_type& value)
#endif
    {
      container->push_back(value); return *this;
    }
    back_insert_iterator<Container>& operator*  ()    { return *this; }
    back_insert_iterator<Container>& operator++ ()    { return *this; }
    back_insert_iterator<Container> operator++ (int) { return *this; }
  };

  template <class Container>
  inline back_insert_iterator<Container> back_inserter (Container& x)
  {
    return back_insert_iterator<Container>(x);
  }

//
// Front insert iterator.
//

  template <class Container>
  class front_insert_iterator 
    : public iterator<output_iterator_tag,
                      _TYPENAME Container::value_type,
                      _TYPENAME Container::difference_type,
                      _TYPENAME Container::pointer,
                      _TYPENAME Container::reference> 
  {
  protected:

    Container* container;

  public:
    typedef Container container_type;
    typedef _TYPENAME Container::value_type value_type;

    _EXPLICIT front_insert_iterator (Container& x) : container(&x) {}
    front_insert_iterator<Container>&
#if defined(__DECCXX) && !defined(__DECFIXCXXL1042)
    operator= (const _TYPENAME Container::const_reference value)
#else
    operator= (const _TYPENAME Container::value_type& value)
#endif
    { 
      container->push_front(value); return *this;
    }
    front_insert_iterator<Container>& operator*  ()    { return *this; }
    front_insert_iterator<Container>& operator++ ()    { return *this; }
    front_insert_iterator<Container> operator++ (int) { return *this; }
  };

  template <class Container>
  inline front_insert_iterator<Container> front_inserter (Container& x)
  {
    return front_insert_iterator<Container>(x);
  }

//
// Insert iterator.
//

  template <class Container>
  class insert_iterator
    : public iterator<output_iterator_tag,
                      _TYPENAME Container::value_type,
                      _TYPENAME Container::difference_type,
                      _TYPENAME Container::pointer,
                      _TYPENAME Container::reference> 
  {
  private:
    _TYPENAME Container::iterator iter;

  protected:
    Container*                   container;

  public:
    typedef Container container_type;
    typedef _TYPENAME Container::value_type value_type;

    insert_iterator (Container& x, _TYPENAME Container::iterator i)
      : container(&x), iter(i) {}
    insert_iterator<Container>&
#if defined(__DECCXX) && !defined(__DECFIXCXXL1042)
    operator= (const _TYPENAME Container::const_reference value)
#else
    operator= (const _TYPENAME Container::value_type& value)
#endif
    { 
      iter = container->insert(iter, value); ++iter; return *this;
    }
    insert_iterator<Container>& operator*  ()    { return *this; }
    insert_iterator<Container>& operator++ ()    { return *this; }
    insert_iterator<Container>& operator++ (int) { return *this; }
  };

  template <class Container, class Iterator>
  inline insert_iterator<Container> inserter (Container& x, Iterator i)
  {
    _TYPENAME Container::iterator c(i);
    insert_iterator<Container> tmp(x, c);
    return tmp;
  }

#ifndef __RW_TRAITS
  template <class charT> struct _RWSTDExportTemplate char_traits;
  _RWSTD_TEMPLATE struct _RWSTDExport char_traits<char>;
#ifndef _RWSTD_NO_WIDE_CHAR
  _RWSTD_TEMPLATE struct _RWSTDExport char_traits<wchar_t>;
#endif
#endif // __RW_TRAITS

#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#ifdef _RW_STD_IOSTREAM
//#include <iostream>
#else
#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#   pragma __extern_prefix __restore
#endif

#include <iostream.h>

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#pragma __extern_prefix __save
#pragma __extern_prefix "CXXL$" 
#endif

#endif


#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

#ifndef __USE_STD_IOSTREAM // DECFIXCXXL591
#ifndef _RW_STD_IOSTREAM
//
// Stream iterators.
//

#ifdef _RWSTD_NO_UNDEFINED_FRIEND
  template <class T, class charT, class traits, class Distance>
  class istream_iterator;

  template <class T, class charT, class traits, class Distance>
  bool operator== (const istream_iterator<T, charT,traits,Distance>& x,
                   const istream_iterator<T, charT,traits,Distance>& y);
#endif

#if defined(__DECCXX) && !defined(__DECFIXCXXL591) && defined(__STD_IOSFWD__)
  template <class T, class charT, class traits, class Distance>
#else
  template <class T, class charT = char, 
            class traits = char_traits<charT>, 
            class Distance = ptrdiff_t>
#endif
  class istream_iterator 
    : public iterator<input_iterator_tag,T,Distance,const T*,const T&>
  {
#if defined(__DECCXX) && !defined(__DECFIXCXXL978)
    friend bool operator== <T,charT,traits, Distance> (const istream_iterator<T, charT,traits,Distance>& x,
#else
    friend inline bool operator== (const istream_iterator<T, charT,traits,Distance>& x,
#endif
                            const istream_iterator<T, charT,traits,Distance>& y);
  protected:

    istream* stream;
    T        value;
    bool     end_marker;

    void read ()
    {
#if defined(__DECCXX) && !defined(__DECFIXCXXL1306)
      if(!default_ctor){
           end_marker=true;
            if(*stream) {
                if(!stream->eof())
                    end_marker=false;
                if (!end_marker) {
                    *stream >> value;
                    if(!*stream)
                        end_marker=true;
                }
            }
        }
#else
      end_marker = (*stream) ? true : false;
      if (end_marker) *stream >> value;
      end_marker = (*stream) ? true : false;
#endif
    }

#if defined(__DECCXX) && !defined(__DECFIXCXXL1306)
    bool default_ctor;
#endif

  public:
    typedef T value_type;
    typedef charT char_type;
    typedef traits traits_type;
    typedef istream istream_type;

#if defined(__DECCXX) && !defined(__DECFIXCXXL1306)
    istream_iterator () : stream(&cin), default_ctor(true), end_marker(true) {}
#else
    istream_iterator () : stream(&cin), end_marker(false) {}
#endif

#if defined(__DECCXX) && !defined(__DECFIXCXXL1306)
    istream_iterator (istream& s) : stream(&s), default_ctor(false) { read(); }
#else
    istream_iterator (istream& s) : stream(&s) { read(); }
#endif

    istream_iterator ( const istream_iterator<T,charT,traits,Distance>& x )
#if defined(__DECCXX) && !defined(__DECFIXCXXL1306)
      :stream(x.stream) , value(x.value) , default_ctor (x.default_ctor), end_marker(x.end_marker)
#else
      :stream(x.stream) , value(x.value) , end_marker(x.end_marker)
#endif
    { }
    const T& operator* () const { return value; }
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
    const T* operator->() const { return &value; }
#endif
    istream_iterator<T, charT,traits,Distance>& operator++ ()
    { 
      read(); return *this;
    }
    istream_iterator<T, charT,traits,Distance> operator++ (int)
    {
      istream_iterator<T, charT,traits,Distance> tmp = *this; 
      read(); 
      return tmp;
    }
  };

  template <class T, class charT, class traits, class Distance>
  inline bool operator== (const istream_iterator<T, charT,traits,Distance>& x,
                          const istream_iterator<T, charT,traits,Distance>& y)
  {

    return (x.stream == y.stream && x.end_marker == y.end_marker) ||
#if defined(__DECCXX) && !defined(__DECFIXCXXL1306)
    (x.default_ctor == true && y.default_ctor == true) ||
    (x.end_marker == true && y.end_marker == true);
#else
    x.end_marker == false && y.end_marker == false;
#endif

  }

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
  template <class T, class charT, class traits, class Distance>
  inline bool operator!= (const istream_iterator<T, charT,traits,Distance>& x,
                          const istream_iterator<T, charT,traits,Distance>& y)
  {
    return !(x == y);
  }
#endif

#ifndef _RWSTD_NO_COMPLEX_DEFAULT_TEMPLATES
#if defined(__DECCXX) && !defined(__DECFIXCXXL591) && defined(__STD_IOSFWD__)
  template <class T, class charT, class traits>
#else
  template <class T, class charT = char, 
  class traits = char_traits<charT> >
#endif
#else
  template <class T, class charT, class traits>
#endif
  class ostream_iterator : public iterator<output_iterator_tag,T,ptrdiff_t,T*,T&>
  {
  protected:

    ostream* stream;
    const char*    str;

  public:
    typedef T value_type;
    typedef charT char_type;
    typedef traits traits_type;
    typedef ostream istream_type;

    ostream_iterator (ostream& s) : stream(&s), str(0) { ; }
    ostream_iterator (ostream& s,const char* c) 
      : stream(&s), str((char *)c)  { ; }
    ostream_iterator ( const ostream_iterator<T,charT,traits>& x )
      :stream(x.stream) , str(x.str)
    { ; }
    ostream_iterator<T,charT,traits>& operator= (const T& value)
    { 
      *stream << value;
      if (str) *stream << str;
      return *this;
    }
    ostream_iterator<T,charT,traits>& operator*  ()    { return *this; }
    ostream_iterator<T,charT,traits>& operator++ ()    { return *this; } 
    ostream_iterator<T,charT,traits>& operator++ (int) { return *this; }
  };


#endif /* _RW_STD_IOSTREAM */
#endif // DECFIXCXXL591


#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#   pragma __extern_prefix __restore
#endif

#ifdef _RWSTD_COMPILE_INSTANTIATE
#include <iterator.cc>
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __restore
#   endif
#endif

#endif /* __STD_ITERATOR__ */
