include/rw/_iterbase.h - stdcxx - Git at Google

 /***************************************************************************
  *
  * _iterbase.h - Definitions of iterator primitives
  *
  * This is an internal header file used to implement the C++ Standard
  * Library. It should never be #included directly by a program.
  *
  * $Id$
  *
  ***************************************************************************
  *
  * 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.
  *
  ***************************************************************************
  *
  * Copyright 2005-2006 The Apache Software Foundation or its licensors,
  * as applicable.
  *
  * Copyright 1994-2006 Rogue Wave Software.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  *
  **************************************************************************/

 #ifndef _RWSTD_RW_ITERBASE_H_INCLUDED
 #define _RWSTD_RW_ITERBASE_H_INCLUDED

 #ifndef _RWSTD_RW_DEFS_H_INCLUDED
 #  include <rw/_defs.h>
 #endif   // _RWSTD_RW_DEFS_H_INCLUDED


 _RWSTD_NAMESPACE (std) {


 // 24.3.1 - Iterator traits
 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;
 };


 // 24.3.3 - Standard iterator tags
 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 { };


 #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

 template <class _TypeT>
 struct iterator_traits<_TypeT*>
 {
     typedef _TypeT                     value_type;
     typedef _RWSTD_PTRDIFF_T           difference_type;
     typedef value_type*                pointer;
     typedef value_type&                reference;
     typedef random_access_iterator_tag iterator_category;
 };


 template <class _TypeT>
 struct iterator_traits<const _TypeT*>
 {
     typedef _TypeT                     value_type;
     typedef _RWSTD_PTRDIFF_T           difference_type;
     typedef const value_type*          pointer;
     typedef const value_type&          reference;
     typedef random_access_iterator_tag iterator_category;
 };

 #endif   // _RWSTD_NO_CLASS_PARTIAL_SPEC


 // 24.3.2 - Basic iterator
 template <class _Category, class _TypeT,
           class _Distance = _RWSTD_PTRDIFF_T,
           class _Pointer = _TypeT*,
           class _Reference = _TypeT&>
 struct iterator
 {
     typedef _TypeT     value_type;
     typedef _Distance  difference_type;
     typedef _Pointer   pointer;
     typedef _Reference reference;
     typedef _Category  iterator_category;
 };


 // returns the category of an iterator
 template <class _TypeT>
 inline random_access_iterator_tag __iterator_category (const _TypeT*)
 {
     return random_access_iterator_tag ();
 }


 template <class _Category, class _TypeT, class _Distance,
           class _Pointer, class _Reference>
 inline _Category
 __iterator_category (const iterator<_Category, _TypeT,
                                     _Distance, _Pointer, _Reference>&)
 {
     typedef _TYPENAME iterator<_Category, _TypeT, _Distance, _TypeT*,
                                _TypeT&>::iterator_category _IterCategory;

     return _IterCategory ();
 }


 template <class _Tag>
 inline bool __is_input_iterator (_Tag)
 {
     return false;
 }


 template <class _Tag>
 inline bool __is_bidirectional_iterator (_Tag)
 {
     return false;
 }


 template <class _Tag>
 inline bool __is_random_access_iterator (_Tag)
 {
     return false;
 }


 _RWSTD_SPECIALIZED_FUNCTION
 inline bool __is_input_iterator (input_iterator_tag)
 {
     return true;
 }


 _RWSTD_SPECIALIZED_FUNCTION
 inline bool __is_bidirectional_iterator (bidirectional_iterator_tag)
 {
     return true;
 }


 _RWSTD_SPECIALIZED_FUNCTION
 inline bool __is_bidirectional_iterator (random_access_iterator_tag)
 {
     return true;
 }


 _RWSTD_SPECIALIZED_FUNCTION
 inline bool __is_random_access_iterator (random_access_iterator_tag)
 {
     return true;
 }


 #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

 template <class _Iterator>
 inline _TYPENAME iterator_traits<_Iterator>::value_type*
 __value_type (const _Iterator*)
 {
     return 0;
 }

 #else   // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

 template <class _Category, class _TypeT, class _Distance,
           class _Pointer, class _Reference>
 inline _TypeT*
 __value_type (const iterator<_Category, _TypeT, _Distance,
                              _Pointer, _Reference>*)
 {
     return 0;
 }

 template <class _TypeT>
 inline _TypeT* __value_type (const _TypeT* const*)
 {
     return 0;
 }

 #endif   // _RWSTD_NO_CLASS_PARTIAL_SPEC


 #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

 template <class _Iterator>
 inline _TYPENAME iterator_traits<_Iterator>::difference_type*
 __distance_type (_Iterator)
 {
     return 0;
 }

 #else   // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

 template <class _Category, class _TypeT, class _Distance,
           class _Pointer, class _Reference>
 inline _Distance*
 __distance_type (iterator<_Category, _TypeT, _Distance, _Pointer, _Reference>)
 {
     return 0;
 }

 template <class _TypeT>
 inline _RWSTD_PTRDIFF_T* __distance_type (const _TypeT*)
 {
     return 0;
 }

 #endif   // _RWSTD_NO_CLASS_PARTIAL_SPEC


 // 24.3.4 - Iterator operations

 template <class _InputIterator, class _Distance>
 inline void __advance (_InputIterator &__it, _Distance __n, input_iterator_tag)
 {
     _RWSTD_ASSERT (__n == 0 || __n > 0);

     while (__n > 0) {
         --__n;
         ++__it;
     }
 }


 template <class _ForwardIterator, class _Distance>
 inline void __advance (_ForwardIterator &__it, _Distance __n,
                        forward_iterator_tag)
 {
     __advance (__it, __n, input_iterator_tag ());
 }


 template <class _BidirectionalIterator, class _Distance>
 inline void __advance (_BidirectionalIterator &__it, _Distance __n,
                        bidirectional_iterator_tag)
 {
     if (__n > 0)
         __advance (__it, __n, input_iterator_tag ());
     else
         while (__n) {
             ++__n;
             --__it;
         }
 }


 template <class _RandomAccessIterator, class _Distance>
 inline void __advance (_RandomAccessIterator& __it, _Distance __n,
                        random_access_iterator_tag)
 {
     __it += __n;
 }


 // 24.3.4, p2
 template <class _InputIterator, class _Distance>
 inline void advance (_InputIterator& __it, _Distance __n)
 {
     __advance (__it, __n, _RWSTD_ITERATOR_CATEGORY (_InputIterator, __it));
 }


 template <class _InputIterator, class _Distance>
 inline void __distance (const _InputIterator &__first,
                         const _InputIterator &__last,
                         _Distance            &__n,
                         input_iterator_tag)
 {
     for (_InputIterator __it = __first; !(__it == __last); ++__it)
         ++__n;
 }


 template <class _ForwardIterator, class _Distance>
 inline void __distance (const _ForwardIterator &__first,
                         const _ForwardIterator &__last,
                         _Distance              &__n,
                         forward_iterator_tag)
 {
     __distance (__first, __last, __n, input_iterator_tag ());
 }

 template <class _BidirectionalIterator, class _Distance>
 inline void __distance (const _BidirectionalIterator &__first,
                         const _BidirectionalIterator &__last,
                         _Distance                    &__n,
                         bidirectional_iterator_tag)
 {
     __distance (__first, __last, __n, input_iterator_tag ());
 }


 template <class _RandomAccessIterator, class _Distance>
 inline void __distance (const _RandomAccessIterator &__first,
                         const _RandomAccessIterator &__last,
                         _Distance                   &__n,
                         random_access_iterator_tag)
 {
     __n = __last - __first;
 }


 #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

 // 24.3.4, p4
 template <class _ForwardIterator>
 inline _TYPENAME iterator_traits<_ForwardIterator>::difference_type
 distance (const _ForwardIterator &__first, const _ForwardIterator &__last)
 {
     _TYPENAME iterator_traits<_ForwardIterator>::difference_type __n = 0;

     __distance (__first, __last, __n,
                 _RWSTD_ITERATOR_CATEGORY (_ForwardIterator, __first));

     return __n;
 }

 #endif   // _RWSTD_NO_CLASS_PARTIAL_SPEC


 #if    !defined (_RWSTD_NO_EXT_VOID_DISTANCE) \
     || defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

 template <class _ForwardIterator, class _Distance>
 inline void distance (const _ForwardIterator &__first,
                       const _ForwardIterator &__last,
                       _Distance              &__n)
 {
     __distance (__first, __last, __n,
                 _RWSTD_ITERATOR_CATEGORY (_ForwardIterator, __first));
 }

 #endif   // !_RWSTD_NO_EXT_VOID_DISTANCE || _RWSTD_NO_CLASS_PARTIAL_SPEC


 }   // namespace std


 _RWSTD_NAMESPACE (__rw) {

 // __rw_distance: Same purpose as 3-parameter distance function, but
 // with return value.

 template <class _ForwardIterator, class _Distance>
 inline _Distance
 __rw_distance (const _ForwardIterator &__first,
                const _ForwardIterator &__last,
                _Distance               __n)
 {
     _STD::__distance (__first, __last, __n,
                       _RWSTD_ITERATOR_CATEGORY (_ForwardIterator, __first));
     return __n;
 }


 }   // namespace __rw


 #ifndef _RWSTD_NO_DEBUG_ITER

 _RWSTD_NAMESPACE (__rw) {

 // __rw_debug_iter - iterator adapter with debugging support
 // _Iterator is either iterator or const_iterator; if the latter,
 // _MutableIterator should be iterator to allow for implicit
 // conversions from non-const (mutable) to const_iterator objects


 template <class _Container, class _Iterator, class _MutableIterator>
 class __rw_debug_iter
 {
     typedef _Container                                container_type;
     typedef _Iterator                                 iterator_type;
     typedef _STD::iterator_traits<iterator_type>      traits_type;

 public:

     typedef _TYPENAME traits_type::value_type         value_type;
     typedef _TYPENAME traits_type::difference_type    difference_type;
     typedef _TYPENAME traits_type::reference          reference;
     typedef _TYPENAME traits_type::pointer            pointer;
     typedef _TYPENAME traits_type::iterator_category  iterator_category;

     typedef __rw_debug_iter <container_type, _MutableIterator,
                              _MutableIterator>        _C_mutable_iterator;

     __rw_debug_iter (): _C_cont (0) { }

     __rw_debug_iter (const container_type &__cont, const iterator_type &__it)
         : _C_iter (__it), _C_cont (&__cont) { }

     // no copy ctor other than the one below is defined
     // will use a compiler generated one if _Iterator != _MutableIterator
     __rw_debug_iter (const _C_mutable_iterator &__rhs)
         : _C_iter (__rhs._C_iter), _C_cont (__rhs._C_cont) { }

     __rw_debug_iter& operator= (const __rw_debug_iter &__rhs) {
         _C_iter = __rhs._C_iter;
         _C_cont = __rhs._C_cont;
         return *this;
     }

     reference operator* () const {
         _RWSTD_ASSERT (_C_is_dereferenceable ());
         return *_C_iter;
     }

     reference operator[] (difference_type __n) const {
         _RWSTD_ASSERT ((*this + __n)._C_is_dereferenceable ());
         return _C_iter [__n];
     }

     _RWSTD_OPERATOR_ARROW (pointer operator-> () const);

     __rw_debug_iter& operator++ () {
         _RWSTD_ASSERT (!_C_is_end ());
         return ++_C_iter, *this;
     }

     __rw_debug_iter& operator-- () {
         _RWSTD_ASSERT (!_C_is_begin ());
         return --_C_iter, *this;
     }

     __rw_debug_iter operator++ (int) {
         __rw_debug_iter __tmp = *this;
         return ++*this, __tmp;
     }

     __rw_debug_iter operator-- (int) {
         __rw_debug_iter __tmp = *this;
         return --*this, __tmp;
     }

     __rw_debug_iter& operator+= (difference_type __n) {
         _C_iter += __n;
         _RWSTD_ASSERT (   !(_C_iter < _C_cont->begin ()._C_iter)
                        && !(_C_cont->end ()._C_iter < _C_iter));
         return *this;
     }

     __rw_debug_iter& operator-= (difference_type __n) {
         _C_iter -= __n;
         _RWSTD_ASSERT (   !(_C_iter < _C_cont->begin ()._C_iter)
                        && !(_C_cont->end ()._C_iter < _C_iter));
         return *this;
     }

     __rw_debug_iter operator+ (difference_type __n) const {
         return __rw_debug_iter (*this) += __n;
     }

     __rw_debug_iter operator- (difference_type __n) const {
         return __rw_debug_iter (*this) -= __n;
     }

     bool _C_is_begin () const {
         return _C_cont && _C_cont->begin () == *this;
     }

     bool _C_is_end () const {
         return _C_cont && _C_cont->end () == *this;
     }

     bool _C_is_dereferenceable () const {
         return !_C_is_end ();
     }

     bool _C_valid_range (const __rw_debug_iter &__it) const {
         return _C_cont && _C_cont == __it._C_cont;
     }

     const iterator_type& base () const {
         return _C_iter;
     }

     iterator_type& base () {
         return _C_iter;
     }

 #if    !defined (_RWSTD_NO_MEMBER_TEMPLATES) \
     && (!defined (__IBMCPP__) || __IBMCPP__ > 502)

     // IBM xlC 5.0 fails to find these member template operators,
     // yet it complains about ambiguity if they are defined along
     // with the non-members below...

     // operators are templatized to assure const/non-const symmetry

     template <class _Iter>
     difference_type
     operator- (const __rw_debug_iter<container_type, _Iter,
                                      _MutableIterator> &__rhs) const {
         _RWSTD_ASSERT (_C_cont && _C_cont == __rhs._C_cont);
         return _C_iter - __rhs._C_iter;
     }

     template <class _Iter>
     bool
     operator== (const __rw_debug_iter<container_type, _Iter,
                                       _MutableIterator> &__rhs) const {
         return _C_iter == __rhs._C_iter;
     }

     template <class _Iter>
     bool
     operator< (const __rw_debug_iter<container_type, _Iter,
                                      _MutableIterator> &__rhs) const {
         return _C_iter < __rhs._C_iter;
     }

     template <class _Iter>
     bool
     operator!= (const __rw_debug_iter<container_type, _Iter,
                                       _MutableIterator> &__rhs) const {
         return !(_C_iter == __rhs._C_iter);
     }

     template <class _Iter>
     bool
     operator<= (const __rw_debug_iter<container_type, _Iter,
                                       _MutableIterator> &__rhs) const {
         return !(__rhs._C_iter < _C_iter);
     }

     template <class _Iter>
     bool
     operator> (const __rw_debug_iter<container_type, _Iter,
                                      _MutableIterator> &__rhs) const {
         return __rhs._C_iter < _C_iter;
     }

     template <class _Iter>
     bool
     operator>= (const __rw_debug_iter<container_type, _Iter,
                                       _MutableIterator> &__rhs) const {
         return !(_C_iter < __rhs._C_iter);
     }

 #endif   // !_RWSTD_NO_MEMBER_TEMPLATES && __IBMCPP__ > 502

     iterator_type         _C_iter;   // wrapped iterator
     const container_type *_C_cont;   // associated container
 };


 }   // namespace __rw


 _RWSTD_NAMESPACE (std) {


 #ifndef _RWSTD_NO_NONDEDUCED_CONTEXT
 # define _RWSTD_CONT_DIFF_TYPE _TYPENAME _Cont::difference_type
 #else
 # define _RWSTD_CONT_DIFF_TYPE _RWSTD_PTRDIFF_T
 #endif

 template <class _Cont, class _Iter, class _MutIter>
 inline _RW::__rw_debug_iter<_Cont, _Iter, _MutIter>
 operator+ (_RWSTD_CONT_DIFF_TYPE                               __n,
            const _RW::__rw_debug_iter<_Cont, _Iter, _MutIter> &__x)
 {
     return __x + __n;
 }

 #undef _RWSTD_CONT_DIFF_TYPE


 #if    defined (_RWSTD_NO_MEMBER_TEMPLATES)   \
     || defined (__IBMCPP__) && __IBMCPP__ <= 502

 // IBM xlC 5.0 fails to find the member template operators
 // defined above in the presence of namespaces...

 // with no support for member templates namespace-scope (non-member)
 // operators must be used - these will cause ambiguities with those
 // in std::rel_ops if the latter are found during lookup


 // _Iter1 may differ from _Iter2 if the function operands are const
 // and non-const iterators, respectively (allows symmetry)

 template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
 inline _TYPENAME _Cont::difference_type
 operator- (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
            const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
 {
     _RWSTD_ASSERT (__x._C_cont && __x._C_cont == __y._C_cont);
     return __x._C_iter - __y._C_iter;
 }

 template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
 inline bool
 operator== (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
             const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
 {
     return __x._C_iter == __y._C_iter;
 }

 template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
 inline bool
 operator< (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
            const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
 {
     _RWSTD_ASSERT (__x._C_cont && __x._C_cont == __y._C_cont);
     return __x._C_iter < __y._C_iter;
 }

 template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
 inline bool
 operator!= (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
             const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
 {
     return !(__x == __y);
 }

 template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
 inline bool
 operator<= (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
             const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
 {
     return !(__y < __x);
 }

 template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
 inline bool
 operator>= (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
             const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
 {
     return !(__x < __y);
 }

 template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
 inline bool
 operator> (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
            const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
 {
     return __y < __x;
 }

 #endif   // _RWSTD_NO_MEMBER_TEMPLATES && __IBMCPP__ <= 502

 }   // namespace std


 _RWSTD_NAMESPACE (__rw) {


 #define _RWSTD_DEBUG_ITER(cont, it, mutit) __rw_debug_iter< cont, it, mutit >


 template <class _Cont, class _Iter, class _MutIter>
 inline bool
 __rw_valid_range (const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__first,
                   const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__last)
 {
     return __first._C_cont && __first._C_cont == __last._C_cont;
 }


 template <class _Iterator>
 inline bool
 __rw_valid_range (const _Iterator &, const _Iterator &)
 {
     return true;
 }


 template <class _Cont, class _Iter, class _MutIter>
 inline bool
 __rw_in_range (const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__it,
                const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__first,
                const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__last)
 {
     return    __rw_valid_range (__first, __it)
            && __rw_valid_range (__it, __last);
 }


 template <class _Iterator>
 inline bool
 __rw_in_range (const _Iterator&, const _Iterator&, const _Iterator&)
 {
     return true;
 }


 template <class _Cont, class _Iter, class _MutIter>
 inline bool
 __rw_dereferenceable (const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__it)
 {
     return __it._C_is_dereferenceable ();
 }


 template <class _Iterator>
 inline bool
 __rw_dereferenceable (const _Iterator&)
 {
     return true;
 }


 template <class _TypeT>
 inline bool
 __rw_dereferenceable (const _TypeT *__ptr)
 {
     return 0 != __ptr;
 }

 }   // namespace __rw

 #undef _RWSTD_DEBUG_ITER

 #endif   // _RWSTD_NO_DEBUG_ITER


 #endif   // _RWSTD_RW_ITERBASE_H_INCLUDED
	/***************************************************************************
	*
	* _iterbase.h - Definitions of iterator primitives
	*
	* This is an internal header file used to implement the C++ Standard
	* Library. It should never be #included directly by a program.
	*
	* $Id$
	*
	***************************************************************************
	*
	* 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.
	*
	***************************************************************************
	*
	* Copyright 2005-2006 The Apache Software Foundation or its licensors,
	* as applicable.
	*
	* Copyright 1994-2006 Rogue Wave Software.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*
	**************************************************************************/

	#ifndef _RWSTD_RW_ITERBASE_H_INCLUDED
	#define _RWSTD_RW_ITERBASE_H_INCLUDED

	#ifndef _RWSTD_RW_DEFS_H_INCLUDED
	# include <rw/_defs.h>
	#endif // _RWSTD_RW_DEFS_H_INCLUDED


	_RWSTD_NAMESPACE (std) {


	// 24.3.1 - Iterator traits
	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;
	};


	// 24.3.3 - Standard iterator tags
	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 { };


	#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

	template <class _TypeT>
	struct iterator_traits<_TypeT*>
	{
	typedef _TypeT value_type;
	typedef _RWSTD_PTRDIFF_T difference_type;
	typedef value_type* pointer;
	typedef value_type& reference;
	typedef random_access_iterator_tag iterator_category;
	};


	template <class _TypeT>
	struct iterator_traits<const _TypeT*>
	{
	typedef _TypeT value_type;
	typedef _RWSTD_PTRDIFF_T difference_type;
	typedef const value_type* pointer;
	typedef const value_type& reference;
	typedef random_access_iterator_tag iterator_category;
	};

	#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC


	// 24.3.2 - Basic iterator
	template <class _Category, class _TypeT,
	class _Distance = _RWSTD_PTRDIFF_T,
	class _Pointer = _TypeT*,
	class _Reference = _TypeT&>
	struct iterator
	{
	typedef _TypeT value_type;
	typedef _Distance difference_type;
	typedef _Pointer pointer;
	typedef _Reference reference;
	typedef _Category iterator_category;
	};


	// returns the category of an iterator
	template <class _TypeT>
	inline random_access_iterator_tag __iterator_category (const _TypeT*)
	{
	return random_access_iterator_tag ();
	}


	template <class _Category, class _TypeT, class _Distance,
	class _Pointer, class _Reference>
	inline _Category
	__iterator_category (const iterator<_Category, _TypeT,
	_Distance, _Pointer, _Reference>&)
	{
	typedef _TYPENAME iterator<_Category, _TypeT, _Distance, _TypeT*,
	_TypeT&>::iterator_category _IterCategory;

	return _IterCategory ();
	}


	template <class _Tag>
	inline bool __is_input_iterator (_Tag)
	{
	return false;
	}


	template <class _Tag>
	inline bool __is_bidirectional_iterator (_Tag)
	{
	return false;
	}


	template <class _Tag>
	inline bool __is_random_access_iterator (_Tag)
	{
	return false;
	}


	_RWSTD_SPECIALIZED_FUNCTION
	inline bool __is_input_iterator (input_iterator_tag)
	{
	return true;
	}


	_RWSTD_SPECIALIZED_FUNCTION
	inline bool __is_bidirectional_iterator (bidirectional_iterator_tag)
	{
	return true;
	}


	_RWSTD_SPECIALIZED_FUNCTION
	inline bool __is_bidirectional_iterator (random_access_iterator_tag)
	{
	return true;
	}


	_RWSTD_SPECIALIZED_FUNCTION
	inline bool __is_random_access_iterator (random_access_iterator_tag)
	{
	return true;
	}


	#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

	template <class _Iterator>
	inline _TYPENAME iterator_traits<_Iterator>::value_type*
	__value_type (const _Iterator*)
	{
	return 0;
	}

	#else // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

	template <class _Category, class _TypeT, class _Distance,
	class _Pointer, class _Reference>
	inline _TypeT*
	__value_type (const iterator<_Category, _TypeT, _Distance,
	_Pointer, _Reference>*)
	{
	return 0;
	}

	template <class _TypeT>
	inline _TypeT* __value_type (const _TypeT* const*)
	{
	return 0;
	}

	#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC


	#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

	template <class _Iterator>
	inline _TYPENAME iterator_traits<_Iterator>::difference_type*
	__distance_type (_Iterator)
	{
	return 0;
	}

	#else // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

	template <class _Category, class _TypeT, class _Distance,
	class _Pointer, class _Reference>
	inline _Distance*
	__distance_type (iterator<_Category, _TypeT, _Distance, _Pointer, _Reference>)
	{
	return 0;
	}

	template <class _TypeT>
	inline _RWSTD_PTRDIFF_T* __distance_type (const _TypeT*)
	{
	return 0;
	}

	#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC


	// 24.3.4 - Iterator operations

	template <class _InputIterator, class _Distance>
	inline void __advance (_InputIterator &__it, _Distance __n, input_iterator_tag)
	{
	_RWSTD_ASSERT (__n == 0 \|\| __n > 0);

	while (__n > 0) {
	--__n;
	++__it;
	}
	}


	template <class _ForwardIterator, class _Distance>
	inline void __advance (_ForwardIterator &__it, _Distance __n,
	forward_iterator_tag)
	{
	__advance (__it, __n, input_iterator_tag ());
	}


	template <class _BidirectionalIterator, class _Distance>
	inline void __advance (_BidirectionalIterator &__it, _Distance __n,
	bidirectional_iterator_tag)
	{
	if (__n > 0)
	__advance (__it, __n, input_iterator_tag ());
	else
	while (__n) {
	++__n;
	--__it;
	}
	}


	template <class _RandomAccessIterator, class _Distance>
	inline void __advance (_RandomAccessIterator& __it, _Distance __n,
	random_access_iterator_tag)
	{
	__it += __n;
	}


	// 24.3.4, p2
	template <class _InputIterator, class _Distance>
	inline void advance (_InputIterator& __it, _Distance __n)
	{
	__advance (__it, __n, _RWSTD_ITERATOR_CATEGORY (_InputIterator, __it));
	}


	template <class _InputIterator, class _Distance>
	inline void __distance (const _InputIterator &__first,
	const _InputIterator &__last,
	_Distance &__n,
	input_iterator_tag)
	{
	for (_InputIterator __it = __first; !(__it == __last); ++__it)
	++__n;
	}


	template <class _ForwardIterator, class _Distance>
	inline void __distance (const _ForwardIterator &__first,
	const _ForwardIterator &__last,
	_Distance &__n,
	forward_iterator_tag)
	{
	__distance (__first, __last, __n, input_iterator_tag ());
	}

	template <class _BidirectionalIterator, class _Distance>
	inline void __distance (const _BidirectionalIterator &__first,
	const _BidirectionalIterator &__last,
	_Distance &__n,
	bidirectional_iterator_tag)
	{
	__distance (__first, __last, __n, input_iterator_tag ());
	}


	template <class _RandomAccessIterator, class _Distance>
	inline void __distance (const _RandomAccessIterator &__first,
	const _RandomAccessIterator &__last,
	_Distance &__n,
	random_access_iterator_tag)
	{
	__n = __last - __first;
	}


	#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

	// 24.3.4, p4
	template <class _ForwardIterator>
	inline _TYPENAME iterator_traits<_ForwardIterator>::difference_type
	distance (const _ForwardIterator &__first, const _ForwardIterator &__last)
	{
	_TYPENAME iterator_traits<_ForwardIterator>::difference_type __n = 0;

	__distance (__first, __last, __n,
	_RWSTD_ITERATOR_CATEGORY (_ForwardIterator, __first));

	return __n;
	}

	#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC


	#if !defined (_RWSTD_NO_EXT_VOID_DISTANCE) \
	\|\| defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

	template <class _ForwardIterator, class _Distance>
	inline void distance (const _ForwardIterator &__first,
	const _ForwardIterator &__last,
	_Distance &__n)
	{
	__distance (__first, __last, __n,
	_RWSTD_ITERATOR_CATEGORY (_ForwardIterator, __first));
	}

	#endif // !_RWSTD_NO_EXT_VOID_DISTANCE \|\| _RWSTD_NO_CLASS_PARTIAL_SPEC


	} // namespace std


	_RWSTD_NAMESPACE (__rw) {

	// __rw_distance: Same purpose as 3-parameter distance function, but
	// with return value.

	template <class _ForwardIterator, class _Distance>
	inline _Distance
	__rw_distance (const _ForwardIterator &__first,
	const _ForwardIterator &__last,
	_Distance __n)
	{
	_STD::__distance (__first, __last, __n,
	_RWSTD_ITERATOR_CATEGORY (_ForwardIterator, __first));
	return __n;
	}


	} // namespace __rw


	#ifndef _RWSTD_NO_DEBUG_ITER

	_RWSTD_NAMESPACE (__rw) {

	// __rw_debug_iter - iterator adapter with debugging support
	// _Iterator is either iterator or const_iterator; if the latter,
	// _MutableIterator should be iterator to allow for implicit
	// conversions from non-const (mutable) to const_iterator objects


	template <class _Container, class _Iterator, class _MutableIterator>
	class __rw_debug_iter
	{
	typedef _Container container_type;
	typedef _Iterator iterator_type;
	typedef _STD::iterator_traits<iterator_type> traits_type;

	public:

	typedef _TYPENAME traits_type::value_type value_type;
	typedef _TYPENAME traits_type::difference_type difference_type;
	typedef _TYPENAME traits_type::reference reference;
	typedef _TYPENAME traits_type::pointer pointer;
	typedef _TYPENAME traits_type::iterator_category iterator_category;

	typedef __rw_debug_iter <container_type, _MutableIterator,
	_MutableIterator> _C_mutable_iterator;

	__rw_debug_iter (): _C_cont (0) { }

	__rw_debug_iter (const container_type &__cont, const iterator_type &__it)
	: _C_iter (__it), _C_cont (&__cont) { }

	// no copy ctor other than the one below is defined
	// will use a compiler generated one if _Iterator != _MutableIterator
	__rw_debug_iter (const _C_mutable_iterator &__rhs)
	: _C_iter (__rhs._C_iter), _C_cont (__rhs._C_cont) { }

	__rw_debug_iter& operator= (const __rw_debug_iter &__rhs) {
	_C_iter = __rhs._C_iter;
	_C_cont = __rhs._C_cont;
	return *this;
	}

	reference operator* () const {
	_RWSTD_ASSERT (_C_is_dereferenceable ());
	return *_C_iter;
	}

	reference operator[] (difference_type __n) const {
	_RWSTD_ASSERT ((*this + __n)._C_is_dereferenceable ());
	return _C_iter [__n];
	}

	_RWSTD_OPERATOR_ARROW (pointer operator-> () const);

	__rw_debug_iter& operator++ () {
	_RWSTD_ASSERT (!_C_is_end ());
	return ++_C_iter, *this;
	}

	__rw_debug_iter& operator-- () {
	_RWSTD_ASSERT (!_C_is_begin ());
	return --_C_iter, *this;
	}

	__rw_debug_iter operator++ (int) {
	__rw_debug_iter __tmp = *this;
	return ++*this, __tmp;
	}

	__rw_debug_iter operator-- (int) {
	__rw_debug_iter __tmp = *this;
	return --*this, __tmp;
	}

	__rw_debug_iter& operator+= (difference_type __n) {
	_C_iter += __n;
	_RWSTD_ASSERT ( !(_C_iter < _C_cont->begin ()._C_iter)
	&& !(_C_cont->end ()._C_iter < _C_iter));
	return *this;
	}

	__rw_debug_iter& operator-= (difference_type __n) {
	_C_iter -= __n;
	_RWSTD_ASSERT ( !(_C_iter < _C_cont->begin ()._C_iter)
	&& !(_C_cont->end ()._C_iter < _C_iter));
	return *this;
	}

	__rw_debug_iter operator+ (difference_type __n) const {
	return __rw_debug_iter (*this) += __n;
	}

	__rw_debug_iter operator- (difference_type __n) const {
	return __rw_debug_iter (*this) -= __n;
	}

	bool _C_is_begin () const {
	return _C_cont && _C_cont->begin () == *this;
	}

	bool _C_is_end () const {
	return _C_cont && _C_cont->end () == *this;
	}

	bool _C_is_dereferenceable () const {
	return !_C_is_end ();
	}

	bool _C_valid_range (const __rw_debug_iter &__it) const {
	return _C_cont && _C_cont == __it._C_cont;
	}

	const iterator_type& base () const {
	return _C_iter;
	}

	iterator_type& base () {
	return _C_iter;
	}

	#if !defined (_RWSTD_NO_MEMBER_TEMPLATES) \
	&& (!defined (__IBMCPP__) \|\| __IBMCPP__ > 502)

	// IBM xlC 5.0 fails to find these member template operators,
	// yet it complains about ambiguity if they are defined along
	// with the non-members below...

	// operators are templatized to assure const/non-const symmetry

	template <class _Iter>
	difference_type
	operator- (const __rw_debug_iter<container_type, _Iter,
	_MutableIterator> &__rhs) const {
	_RWSTD_ASSERT (_C_cont && _C_cont == __rhs._C_cont);
	return _C_iter - __rhs._C_iter;
	}

	template <class _Iter>
	bool
	operator== (const __rw_debug_iter<container_type, _Iter,
	_MutableIterator> &__rhs) const {
	return _C_iter == __rhs._C_iter;
	}

	template <class _Iter>
	bool
	operator< (const __rw_debug_iter<container_type, _Iter,
	_MutableIterator> &__rhs) const {
	return _C_iter < __rhs._C_iter;
	}

	template <class _Iter>
	bool
	operator!= (const __rw_debug_iter<container_type, _Iter,
	_MutableIterator> &__rhs) const {
	return !(_C_iter == __rhs._C_iter);
	}

	template <class _Iter>
	bool
	operator<= (const __rw_debug_iter<container_type, _Iter,
	_MutableIterator> &__rhs) const {
	return !(__rhs._C_iter < _C_iter);
	}

	template <class _Iter>
	bool
	operator> (const __rw_debug_iter<container_type, _Iter,
	_MutableIterator> &__rhs) const {
	return __rhs._C_iter < _C_iter;
	}

	template <class _Iter>
	bool
	operator>= (const __rw_debug_iter<container_type, _Iter,
	_MutableIterator> &__rhs) const {
	return !(_C_iter < __rhs._C_iter);
	}

	#endif // !_RWSTD_NO_MEMBER_TEMPLATES && __IBMCPP__ > 502

	iterator_type _C_iter; // wrapped iterator
	const container_type *_C_cont; // associated container
	};


	} // namespace __rw


	_RWSTD_NAMESPACE (std) {


	#ifndef _RWSTD_NO_NONDEDUCED_CONTEXT
	# define _RWSTD_CONT_DIFF_TYPE _TYPENAME _Cont::difference_type
	#else
	# define _RWSTD_CONT_DIFF_TYPE _RWSTD_PTRDIFF_T
	#endif

	template <class _Cont, class _Iter, class _MutIter>
	inline _RW::__rw_debug_iter<_Cont, _Iter, _MutIter>
	operator+ (_RWSTD_CONT_DIFF_TYPE __n,
	const _RW::__rw_debug_iter<_Cont, _Iter, _MutIter> &__x)
	{
	return __x + __n;
	}

	#undef _RWSTD_CONT_DIFF_TYPE


	#if defined (_RWSTD_NO_MEMBER_TEMPLATES) \
	\|\| defined (__IBMCPP__) && __IBMCPP__ <= 502

	// IBM xlC 5.0 fails to find the member template operators
	// defined above in the presence of namespaces...

	// with no support for member templates namespace-scope (non-member)
	// operators must be used - these will cause ambiguities with those
	// in std::rel_ops if the latter are found during lookup


	// _Iter1 may differ from _Iter2 if the function operands are const
	// and non-const iterators, respectively (allows symmetry)

	template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
	inline _TYPENAME _Cont::difference_type
	operator- (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
	const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
	{
	_RWSTD_ASSERT (__x._C_cont && __x._C_cont == __y._C_cont);
	return __x._C_iter - __y._C_iter;
	}

	template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
	inline bool
	operator== (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
	const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
	{
	return __x._C_iter == __y._C_iter;
	}

	template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
	inline bool
	operator< (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
	const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
	{
	_RWSTD_ASSERT (__x._C_cont && __x._C_cont == __y._C_cont);
	return __x._C_iter < __y._C_iter;
	}

	template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
	inline bool
	operator!= (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
	const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
	{
	return !(__x == __y);
	}

	template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
	inline bool
	operator<= (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
	const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
	{
	return !(__y < __x);
	}

	template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
	inline bool
	operator>= (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
	const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
	{
	return !(__x < __y);
	}

	template <class _Cont, class _Iter1, class _Iter2, class _MutIter>
	inline bool
	operator> (const _RW::__rw_debug_iter<_Cont, _Iter1, _MutIter> &__x,
	const _RW::__rw_debug_iter<_Cont, _Iter2, _MutIter> &__y)
	{
	return __y < __x;
	}

	#endif // _RWSTD_NO_MEMBER_TEMPLATES && __IBMCPP__ <= 502

	} // namespace std


	_RWSTD_NAMESPACE (__rw) {


	#define _RWSTD_DEBUG_ITER(cont, it, mutit) __rw_debug_iter< cont, it, mutit >


	template <class _Cont, class _Iter, class _MutIter>
	inline bool
	__rw_valid_range (const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__first,
	const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__last)
	{
	return __first._C_cont && __first._C_cont == __last._C_cont;
	}


	template <class _Iterator>
	inline bool
	__rw_valid_range (const _Iterator &, const _Iterator &)
	{
	return true;
	}


	template <class _Cont, class _Iter, class _MutIter>
	inline bool
	__rw_in_range (const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__it,
	const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__first,
	const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__last)
	{
	return __rw_valid_range (__first, __it)
	&& __rw_valid_range (__it, __last);
	}


	template <class _Iterator>
	inline bool
	__rw_in_range (const _Iterator&, const _Iterator&, const _Iterator&)
	{
	return true;
	}


	template <class _Cont, class _Iter, class _MutIter>
	inline bool
	__rw_dereferenceable (const _RWSTD_DEBUG_ITER(_Cont, _Iter, _MutIter) &__it)
	{
	return __it._C_is_dereferenceable ();
	}


	template <class _Iterator>
	inline bool
	__rw_dereferenceable (const _Iterator&)
	{
	return true;
	}


	template <class _TypeT>
	inline bool
	__rw_dereferenceable (const _TypeT *__ptr)
	{
	return 0 != __ptr;
	}

	} // namespace __rw

	#undef _RWSTD_DEBUG_ITER

	#endif // _RWSTD_NO_DEBUG_ITER


	#endif // _RWSTD_RW_ITERBASE_H_INCLUDED