1    	// Types used in iterator implementation -*- C++ -*-
2    	
3    	// Copyright (C) 2001-2017 Free Software Foundation, Inc.
4    	//
5    	// This file is part of the GNU ISO C++ Library.  This library is free
6    	// software; you can redistribute it and/or modify it under the
7    	// terms of the GNU General Public License as published by the
8    	// Free Software Foundation; either version 3, or (at your option)
9    	// any later version.
10   	
11   	// This library is distributed in the hope that it will be useful,
12   	// but WITHOUT ANY WARRANTY; without even the implied warranty of
13   	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   	// GNU General Public License for more details.
15   	
16   	// Under Section 7 of GPL version 3, you are granted additional
17   	// permissions described in the GCC Runtime Library Exception, version
18   	// 3.1, as published by the Free Software Foundation.
19   	
20   	// You should have received a copy of the GNU General Public License and
21   	// a copy of the GCC Runtime Library Exception along with this program;
22   	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23   	// <http://www.gnu.org/licenses/>.
24   	
25   	/*
26   	 *
27   	 * Copyright (c) 1994
28   	 * Hewlett-Packard Company
29   	 *
30   	 * Permission to use, copy, modify, distribute and sell this software
31   	 * and its documentation for any purpose is hereby granted without fee,
32   	 * provided that the above copyright notice appear in all copies and
33   	 * that both that copyright notice and this permission notice appear
34   	 * in supporting documentation.  Hewlett-Packard Company makes no
35   	 * representations about the suitability of this software for any
36   	 * purpose.  It is provided "as is" without express or implied warranty.
37   	 *
38   	 *
39   	 * Copyright (c) 1996-1998
40   	 * Silicon Graphics Computer Systems, Inc.
41   	 *
42   	 * Permission to use, copy, modify, distribute and sell this software
43   	 * and its documentation for any purpose is hereby granted without fee,
44   	 * provided that the above copyright notice appear in all copies and
45   	 * that both that copyright notice and this permission notice appear
46   	 * in supporting documentation.  Silicon Graphics makes no
47   	 * representations about the suitability of this software for any
48   	 * purpose.  It is provided "as is" without express or implied warranty.
49   	 */
50   	
51   	/** @file bits/stl_iterator_base_types.h
52   	 *  This is an internal header file, included by other library headers.
53   	 *  Do not attempt to use it directly. @headername{iterator}
54   	 *
55   	 *  This file contains all of the general iterator-related utility types,
56   	 *  such as iterator_traits and struct iterator.
57   	 */
58   	
59   	#ifndef _STL_ITERATOR_BASE_TYPES_H
60   	#define _STL_ITERATOR_BASE_TYPES_H 1
61   	
62   	#pragma GCC system_header
63   	
64   	#include <bits/c++config.h>
65   	
66   	#if __cplusplus >= 201103L
67   	# include <type_traits>  // For __void_t, is_convertible
68   	#endif
69   	
70   	namespace std _GLIBCXX_VISIBILITY(default)
71   	{
72   	_GLIBCXX_BEGIN_NAMESPACE_VERSION
73   	
74   	  /**
75   	   *  @defgroup iterators Iterators
76   	   *  Abstractions for uniform iterating through various underlying types.
77   	  */
78   	  //@{ 
79   	
80   	  /**
81   	   *  @defgroup iterator_tags Iterator Tags
82   	   *  These are empty types, used to distinguish different iterators.  The
83   	   *  distinction is not made by what they contain, but simply by what they
84   	   *  are.  Different underlying algorithms can then be used based on the
85   	   *  different operations supported by different iterator types.
86   	  */
87   	  //@{ 
88   	  ///  Marking input iterators.
89   	  struct input_iterator_tag { };
90   	
91   	  ///  Marking output iterators.
92   	  struct output_iterator_tag { };
93   	
94   	  /// Forward iterators support a superset of input iterator operations.
95   	  struct forward_iterator_tag : public input_iterator_tag { };
96   	
97   	  /// Bidirectional iterators support a superset of forward iterator
98   	  /// operations.
99   	  struct bidirectional_iterator_tag : public forward_iterator_tag { };
100  	
101  	  /// Random-access iterators support a superset of bidirectional
102  	  /// iterator operations.
103  	  struct random_access_iterator_tag : public bidirectional_iterator_tag { };
104  	  //@}
105  	
106  	  /**
107  	   *  @brief  Common %iterator class.
108  	   *
109  	   *  This class does nothing but define nested typedefs.  %Iterator classes
110  	   *  can inherit from this class to save some work.  The typedefs are then
111  	   *  used in specializations and overloading.
112  	   *
113  	   *  In particular, there are no default implementations of requirements
114  	   *  such as @c operator++ and the like.  (How could there be?)
115  	  */
116  	  template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
117  	           typename _Pointer = _Tp*, typename _Reference = _Tp&>
118  	    struct iterator
119  	    {
120  	      /// One of the @link iterator_tags tag types@endlink.
121  	      typedef _Category  iterator_category;
122  	      /// The type "pointed to" by the iterator.
123  	      typedef _Tp        value_type;
124  	      /// Distance between iterators is represented as this type.
125  	      typedef _Distance  difference_type;
126  	      /// This type represents a pointer-to-value_type.
127  	      typedef _Pointer   pointer;
128  	      /// This type represents a reference-to-value_type.
129  	      typedef _Reference reference;
130  	    };
131  	
132  	  /**
133  	   *  @brief  Traits class for iterators.
134  	   *
135  	   *  This class does nothing but define nested typedefs.  The general
136  	   *  version simply @a forwards the nested typedefs from the Iterator
137  	   *  argument.  Specialized versions for pointers and pointers-to-const
138  	   *  provide tighter, more correct semantics.
139  	  */
140  	#if __cplusplus >= 201103L
141  	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
142  	  // 2408. SFINAE-friendly common_type/iterator_traits is missing in C++14
143  	  template<typename _Iterator, typename = __void_t<>>
144  	    struct __iterator_traits { };
145  	
146  	  template<typename _Iterator>
147  	    struct __iterator_traits<_Iterator,
148  				     __void_t<typename _Iterator::iterator_category,
149  					      typename _Iterator::value_type,
150  					      typename _Iterator::difference_type,
151  					      typename _Iterator::pointer,
152  					      typename _Iterator::reference>>
153  	    {
154  	      typedef typename _Iterator::iterator_category iterator_category;
155  	      typedef typename _Iterator::value_type        value_type;
156  	      typedef typename _Iterator::difference_type   difference_type;
157  	      typedef typename _Iterator::pointer           pointer;
158  	      typedef typename _Iterator::reference         reference;
159  	    };
160  	
161  	  template<typename _Iterator>
162  	    struct iterator_traits
163  	    : public __iterator_traits<_Iterator> { };
164  	#else
165  	  template<typename _Iterator>
166  	    struct iterator_traits
167  	    {
168  	      typedef typename _Iterator::iterator_category iterator_category;
169  	      typedef typename _Iterator::value_type        value_type;
170  	      typedef typename _Iterator::difference_type   difference_type;
171  	      typedef typename _Iterator::pointer           pointer;
172  	      typedef typename _Iterator::reference         reference;
173  	    };
174  	#endif
175  	
176  	  /// Partial specialization for pointer types.
177  	  template<typename _Tp>
178  	    struct iterator_traits<_Tp*>
179  	    {
180  	      typedef random_access_iterator_tag iterator_category;
181  	      typedef _Tp                         value_type;
182  	      typedef ptrdiff_t                   difference_type;
183  	      typedef _Tp*                        pointer;
184  	      typedef _Tp&                        reference;
185  	    };
186  	
187  	  /// Partial specialization for const pointer types.
188  	  template<typename _Tp>
189  	    struct iterator_traits<const _Tp*>
190  	    {
191  	      typedef random_access_iterator_tag iterator_category;
192  	      typedef _Tp                         value_type;
193  	      typedef ptrdiff_t                   difference_type;
194  	      typedef const _Tp*                  pointer;
195  	      typedef const _Tp&                  reference;
196  	    };
197  	
198  	  /**
199  	   *  This function is not a part of the C++ standard but is syntactic
200  	   *  sugar for internal library use only.
201  	  */
202  	  template<typename _Iter>
203  	    inline _GLIBCXX_CONSTEXPR
204  	    typename iterator_traits<_Iter>::iterator_category
205  	    __iterator_category(const _Iter&)
206  	    { return typename iterator_traits<_Iter>::iterator_category(); }
207  	
208  	  //@}
209  	
210  	#if __cplusplus < 201103L
211  	  // If _Iterator has a base returns it otherwise _Iterator is returned
212  	  // untouched
213  	  template<typename _Iterator, bool _HasBase>
214  	    struct _Iter_base
215  	    {
216  	      typedef _Iterator iterator_type;
217  	      static iterator_type _S_base(_Iterator __it)
218  	      { return __it; }
219  	    };
220  	
221  	  template<typename _Iterator>
222  	    struct _Iter_base<_Iterator, true>
223  	    {
224  	      typedef typename _Iterator::iterator_type iterator_type;
225  	      static iterator_type _S_base(_Iterator __it)
226  	      { return __it.base(); }
227  	    };
228  	#endif
229  	
230  	#if __cplusplus >= 201103L
231  	  template<typename _InIter>
232  	    using _RequireInputIter = typename
233  	      enable_if<is_convertible<typename
234  			iterator_traits<_InIter>::iterator_category,
235  				       input_iterator_tag>::value>::type;
236  	#endif
237  	
238  	_GLIBCXX_END_NAMESPACE_VERSION
239  	} // namespace
240  	
241  	#endif /* _STL_ITERATOR_BASE_TYPES_H */
242  	
243