1// Functions used by iterators -*- C++ -*- 
2 
3// Copyright (C) 2001-2019 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_funcs.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 
56 * functions, such as distance() and advance(). 
57 */ 
58 
59#ifndef _STL_ITERATOR_BASE_FUNCS_H 
60#define _STL_ITERATOR_BASE_FUNCS_H 1 
61 
62#pragma GCC system_header 
63 
64#include <bits/concept_check.h> 
65#include <debug/assertions.h> 
66 
67namespace std _GLIBCXX_VISIBILITY(default) 
68{ 
69_GLIBCXX_BEGIN_NAMESPACE_VERSION 
70 
71_GLIBCXX_BEGIN_NAMESPACE_CONTAINER 
72 // Forward declaration for the overloads of __distance. 
73 template <typename> struct _List_iterator; 
74 template <typename> struct _List_const_iterator; 
75_GLIBCXX_END_NAMESPACE_CONTAINER 
76 
77 template<typename _InputIterator> 
78 inline _GLIBCXX14_CONSTEXPR 
79 typename iterator_traits<_InputIterator>::difference_type 
80 __distance(_InputIterator __first, _InputIterator __last, 
81 input_iterator_tag) 
82 { 
83 // concept requirements 
84 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 
85 
86 typename iterator_traits<_InputIterator>::difference_type __n = 0; 
87 while (__first != __last) 
88 { 
89 ++__first; 
90 ++__n; 
91 } 
92 return __n; 
93 } 
94 
95 template<typename _RandomAccessIterator> 
96 inline _GLIBCXX14_CONSTEXPR 
97 typename iterator_traits<_RandomAccessIterator>::difference_type 
98 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 
99 random_access_iterator_tag) 
100 { 
101 // concept requirements 
102 __glibcxx_function_requires(_RandomAccessIteratorConcept< 
103 _RandomAccessIterator>) 
104 return __last - __first; 
105 } 
106 
107#if _GLIBCXX_USE_CXX11_ABI 
108 // Forward declaration because of the qualified call in distance. 
109 template<typename _Tp> 
110 ptrdiff_t 
111 __distance(_GLIBCXX_STD_C::_List_iterator<_Tp>, 
112 _GLIBCXX_STD_C::_List_iterator<_Tp>, 
113 input_iterator_tag); 
114 
115 template<typename _Tp> 
116 ptrdiff_t 
117 __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp>, 
118 _GLIBCXX_STD_C::_List_const_iterator<_Tp>, 
119 input_iterator_tag); 
120#endif 
121 
122 /** 
123 * @brief A generalization of pointer arithmetic. 
124 * @param __first An input iterator. 
125 * @param __last An input iterator. 
126 * @return The distance between them. 
127 * 
128 * Returns @c n such that __first + n == __last. This requires 
129 * that @p __last must be reachable from @p __first. Note that @c 
130 * n may be negative. 
131 * 
132 * For random access iterators, this uses their @c + and @c - operations 
133 * and are constant time. For other %iterator classes they are linear time. 
134 */ 
135 template<typename _InputIterator> 
136 inline _GLIBCXX17_CONSTEXPR 
137 typename iterator_traits<_InputIterator>::difference_type 
138 distance(_InputIterator __first, _InputIterator __last) 
139 { 
140 // concept requirements -- taken care of in __distance 
141 return std::__distance(__first, __last, 
142 std::__iterator_category(__first)); 
143 } 
144 
145 template<typename _InputIterator, typename _Distance> 
146 inline _GLIBCXX14_CONSTEXPR void 
147 __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) 
148 { 
149 // concept requirements 
150 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 
151 __glibcxx_assert(__n >= 0); 
152 while (__n--) 
153 ++__i; 
154 } 
155 
156 template<typename _BidirectionalIterator, typename _Distance> 
157 inline _GLIBCXX14_CONSTEXPR void 
158 __advance(_BidirectionalIterator& __i, _Distance __n, 
159 bidirectional_iterator_tag) 
160 { 
161 // concept requirements 
162 __glibcxx_function_requires(_BidirectionalIteratorConcept< 
163 _BidirectionalIterator>) 
164 if (__n > 0) 
165 while (__n--) 
166 ++__i; 
167 else 
168 while (__n++) 
169 --__i; 
170 } 
171 
172 template<typename _RandomAccessIterator, typename _Distance> 
173 inline _GLIBCXX14_CONSTEXPR void 
174 __advance(_RandomAccessIterator& __i, _Distance __n, 
175 random_access_iterator_tag) 
176 { 
177 // concept requirements 
178 __glibcxx_function_requires(_RandomAccessIteratorConcept< 
179 _RandomAccessIterator>) 
180 if (__builtin_constant_p(__n) && __n == 1) 
181 ++__i; 
182 else if (__builtin_constant_p(__n) && __n == -1) 
183 --__i; 
184 else 
185 __i += __n; 
186 } 
187 
188 /** 
189 * @brief A generalization of pointer arithmetic. 
190 * @param __i An input iterator. 
191 * @param __n The @a delta by which to change @p __i. 
192 * @return Nothing. 
193 * 
194 * This increments @p i by @p n. For bidirectional and random access 
195 * iterators, @p __n may be negative, in which case @p __i is decremented. 
196 * 
197 * For random access iterators, this uses their @c + and @c - operations 
198 * and are constant time. For other %iterator classes they are linear time. 
199 */ 
200 template<typename _InputIterator, typename _Distance> 
201 inline _GLIBCXX17_CONSTEXPR void 
202 advance(_InputIterator& __i, _Distance __n) 
203 { 
204 // concept requirements -- taken care of in __advance 
205 typename iterator_traits<_InputIterator>::difference_type __d = __n; 
206 std::__advance(__i, __d, std::__iterator_category(__i)); 
207 } 
208 
209#if __cplusplus >= 201103L 
210 
211 template<typename _InputIterator> 
212 inline _GLIBCXX17_CONSTEXPR _InputIterator 
213 next(_InputIterator __x, typename 
214 iterator_traits<_InputIterator>::difference_type __n = 1) 
215 { 
216 // concept requirements 
217 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 
218 std::advance(__x, __n); 
219 return __x; 
220 } 
221 
222 template<typename _BidirectionalIterator> 
223 inline _GLIBCXX17_CONSTEXPR _BidirectionalIterator 
224 prev(_BidirectionalIterator __x, typename 
225 iterator_traits<_BidirectionalIterator>::difference_type __n = 1)  
226 { 
227 // concept requirements 
228 __glibcxx_function_requires(_BidirectionalIteratorConcept< 
229 _BidirectionalIterator>) 
230 std::advance(__x, -__n); 
231 return __x; 
232 } 
233 
234#endif // C++11 
235 
236_GLIBCXX_END_NAMESPACE_VERSION 
237} // namespace 
238 
239#endif /* _STL_ITERATOR_BASE_FUNCS_H */ 
240