1*e4b17023SJohn Marino // Functions used by iterators -*- C++ -*-
2*e4b17023SJohn Marino
3*e4b17023SJohn Marino // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4*e4b17023SJohn Marino // Free Software Foundation, Inc.
5*e4b17023SJohn Marino //
6*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library. This library is free
7*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the
8*e4b17023SJohn Marino // terms of the GNU General Public License as published by the
9*e4b17023SJohn Marino // Free Software Foundation; either version 3, or (at your option)
10*e4b17023SJohn Marino // any later version.
11*e4b17023SJohn Marino
12*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful,
13*e4b17023SJohn Marino // but WITHOUT ANY WARRANTY; without even the implied warranty of
14*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15*e4b17023SJohn Marino // GNU General Public License for more details.
16*e4b17023SJohn Marino
17*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional
18*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version
19*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation.
20*e4b17023SJohn Marino
21*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License and
22*e4b17023SJohn Marino // a copy of the GCC Runtime Library Exception along with this program;
23*e4b17023SJohn Marino // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>.
25*e4b17023SJohn Marino
26*e4b17023SJohn Marino /*
27*e4b17023SJohn Marino *
28*e4b17023SJohn Marino * Copyright (c) 1994
29*e4b17023SJohn Marino * Hewlett-Packard Company
30*e4b17023SJohn Marino *
31*e4b17023SJohn Marino * Permission to use, copy, modify, distribute and sell this software
32*e4b17023SJohn Marino * and its documentation for any purpose is hereby granted without fee,
33*e4b17023SJohn Marino * provided that the above copyright notice appear in all copies and
34*e4b17023SJohn Marino * that both that copyright notice and this permission notice appear
35*e4b17023SJohn Marino * in supporting documentation. Hewlett-Packard Company makes no
36*e4b17023SJohn Marino * representations about the suitability of this software for any
37*e4b17023SJohn Marino * purpose. It is provided "as is" without express or implied warranty.
38*e4b17023SJohn Marino *
39*e4b17023SJohn Marino *
40*e4b17023SJohn Marino * Copyright (c) 1996-1998
41*e4b17023SJohn Marino * Silicon Graphics Computer Systems, Inc.
42*e4b17023SJohn Marino *
43*e4b17023SJohn Marino * Permission to use, copy, modify, distribute and sell this software
44*e4b17023SJohn Marino * and its documentation for any purpose is hereby granted without fee,
45*e4b17023SJohn Marino * provided that the above copyright notice appear in all copies and
46*e4b17023SJohn Marino * that both that copyright notice and this permission notice appear
47*e4b17023SJohn Marino * in supporting documentation. Silicon Graphics makes no
48*e4b17023SJohn Marino * representations about the suitability of this software for any
49*e4b17023SJohn Marino * purpose. It is provided "as is" without express or implied warranty.
50*e4b17023SJohn Marino */
51*e4b17023SJohn Marino
52*e4b17023SJohn Marino /** @file bits/stl_iterator_base_funcs.h
53*e4b17023SJohn Marino * This is an internal header file, included by other library headers.
54*e4b17023SJohn Marino * Do not attempt to use it directly. @headername{iterator}
55*e4b17023SJohn Marino *
56*e4b17023SJohn Marino * This file contains all of the general iterator-related utility
57*e4b17023SJohn Marino * functions, such as distance() and advance().
58*e4b17023SJohn Marino */
59*e4b17023SJohn Marino
60*e4b17023SJohn Marino #ifndef _STL_ITERATOR_BASE_FUNCS_H
61*e4b17023SJohn Marino #define _STL_ITERATOR_BASE_FUNCS_H 1
62*e4b17023SJohn Marino
63*e4b17023SJohn Marino #pragma GCC system_header
64*e4b17023SJohn Marino
65*e4b17023SJohn Marino #include <bits/concept_check.h>
66*e4b17023SJohn Marino
_GLIBCXX_VISIBILITY(default)67*e4b17023SJohn Marino namespace std _GLIBCXX_VISIBILITY(default)
68*e4b17023SJohn Marino {
69*e4b17023SJohn Marino _GLIBCXX_BEGIN_NAMESPACE_VERSION
70*e4b17023SJohn Marino
71*e4b17023SJohn Marino template<typename _InputIterator>
72*e4b17023SJohn Marino inline typename iterator_traits<_InputIterator>::difference_type
73*e4b17023SJohn Marino __distance(_InputIterator __first, _InputIterator __last,
74*e4b17023SJohn Marino input_iterator_tag)
75*e4b17023SJohn Marino {
76*e4b17023SJohn Marino // concept requirements
77*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
78*e4b17023SJohn Marino
79*e4b17023SJohn Marino typename iterator_traits<_InputIterator>::difference_type __n = 0;
80*e4b17023SJohn Marino while (__first != __last)
81*e4b17023SJohn Marino {
82*e4b17023SJohn Marino ++__first;
83*e4b17023SJohn Marino ++__n;
84*e4b17023SJohn Marino }
85*e4b17023SJohn Marino return __n;
86*e4b17023SJohn Marino }
87*e4b17023SJohn Marino
88*e4b17023SJohn Marino template<typename _RandomAccessIterator>
89*e4b17023SJohn Marino inline typename iterator_traits<_RandomAccessIterator>::difference_type
90*e4b17023SJohn Marino __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
91*e4b17023SJohn Marino random_access_iterator_tag)
92*e4b17023SJohn Marino {
93*e4b17023SJohn Marino // concept requirements
94*e4b17023SJohn Marino __glibcxx_function_requires(_RandomAccessIteratorConcept<
95*e4b17023SJohn Marino _RandomAccessIterator>)
96*e4b17023SJohn Marino return __last - __first;
97*e4b17023SJohn Marino }
98*e4b17023SJohn Marino
99*e4b17023SJohn Marino /**
100*e4b17023SJohn Marino * @brief A generalization of pointer arithmetic.
101*e4b17023SJohn Marino * @param __first An input iterator.
102*e4b17023SJohn Marino * @param __last An input iterator.
103*e4b17023SJohn Marino * @return The distance between them.
104*e4b17023SJohn Marino *
105*e4b17023SJohn Marino * Returns @c n such that __first + n == __last. This requires
106*e4b17023SJohn Marino * that @p __last must be reachable from @p __first. Note that @c
107*e4b17023SJohn Marino * n may be negative.
108*e4b17023SJohn Marino *
109*e4b17023SJohn Marino * For random access iterators, this uses their @c + and @c - operations
110*e4b17023SJohn Marino * and are constant time. For other %iterator classes they are linear time.
111*e4b17023SJohn Marino */
112*e4b17023SJohn Marino template<typename _InputIterator>
113*e4b17023SJohn Marino inline typename iterator_traits<_InputIterator>::difference_type
114*e4b17023SJohn Marino distance(_InputIterator __first, _InputIterator __last)
115*e4b17023SJohn Marino {
116*e4b17023SJohn Marino // concept requirements -- taken care of in __distance
117*e4b17023SJohn Marino return std::__distance(__first, __last,
118*e4b17023SJohn Marino std::__iterator_category(__first));
119*e4b17023SJohn Marino }
120*e4b17023SJohn Marino
121*e4b17023SJohn Marino template<typename _InputIterator, typename _Distance>
122*e4b17023SJohn Marino inline void
123*e4b17023SJohn Marino __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
124*e4b17023SJohn Marino {
125*e4b17023SJohn Marino // concept requirements
126*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
127*e4b17023SJohn Marino while (__n--)
128*e4b17023SJohn Marino ++__i;
129*e4b17023SJohn Marino }
130*e4b17023SJohn Marino
131*e4b17023SJohn Marino template<typename _BidirectionalIterator, typename _Distance>
132*e4b17023SJohn Marino inline void
133*e4b17023SJohn Marino __advance(_BidirectionalIterator& __i, _Distance __n,
134*e4b17023SJohn Marino bidirectional_iterator_tag)
135*e4b17023SJohn Marino {
136*e4b17023SJohn Marino // concept requirements
137*e4b17023SJohn Marino __glibcxx_function_requires(_BidirectionalIteratorConcept<
138*e4b17023SJohn Marino _BidirectionalIterator>)
139*e4b17023SJohn Marino if (__n > 0)
140*e4b17023SJohn Marino while (__n--)
141*e4b17023SJohn Marino ++__i;
142*e4b17023SJohn Marino else
143*e4b17023SJohn Marino while (__n++)
144*e4b17023SJohn Marino --__i;
145*e4b17023SJohn Marino }
146*e4b17023SJohn Marino
147*e4b17023SJohn Marino template<typename _RandomAccessIterator, typename _Distance>
148*e4b17023SJohn Marino inline void
149*e4b17023SJohn Marino __advance(_RandomAccessIterator& __i, _Distance __n,
150*e4b17023SJohn Marino random_access_iterator_tag)
151*e4b17023SJohn Marino {
152*e4b17023SJohn Marino // concept requirements
153*e4b17023SJohn Marino __glibcxx_function_requires(_RandomAccessIteratorConcept<
154*e4b17023SJohn Marino _RandomAccessIterator>)
155*e4b17023SJohn Marino __i += __n;
156*e4b17023SJohn Marino }
157*e4b17023SJohn Marino
158*e4b17023SJohn Marino /**
159*e4b17023SJohn Marino * @brief A generalization of pointer arithmetic.
160*e4b17023SJohn Marino * @param __i An input iterator.
161*e4b17023SJohn Marino * @param __n The @a delta by which to change @p __i.
162*e4b17023SJohn Marino * @return Nothing.
163*e4b17023SJohn Marino *
164*e4b17023SJohn Marino * This increments @p i by @p n. For bidirectional and random access
165*e4b17023SJohn Marino * iterators, @p __n may be negative, in which case @p __i is decremented.
166*e4b17023SJohn Marino *
167*e4b17023SJohn Marino * For random access iterators, this uses their @c + and @c - operations
168*e4b17023SJohn Marino * and are constant time. For other %iterator classes they are linear time.
169*e4b17023SJohn Marino */
170*e4b17023SJohn Marino template<typename _InputIterator, typename _Distance>
171*e4b17023SJohn Marino inline void
172*e4b17023SJohn Marino advance(_InputIterator& __i, _Distance __n)
173*e4b17023SJohn Marino {
174*e4b17023SJohn Marino // concept requirements -- taken care of in __advance
175*e4b17023SJohn Marino typename iterator_traits<_InputIterator>::difference_type __d = __n;
176*e4b17023SJohn Marino std::__advance(__i, __d, std::__iterator_category(__i));
177*e4b17023SJohn Marino }
178*e4b17023SJohn Marino
179*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
180*e4b17023SJohn Marino
181*e4b17023SJohn Marino template<typename _ForwardIterator>
182*e4b17023SJohn Marino inline _ForwardIterator
183*e4b17023SJohn Marino next(_ForwardIterator __x, typename
184*e4b17023SJohn Marino iterator_traits<_ForwardIterator>::difference_type __n = 1)
185*e4b17023SJohn Marino {
186*e4b17023SJohn Marino std::advance(__x, __n);
187*e4b17023SJohn Marino return __x;
188*e4b17023SJohn Marino }
189*e4b17023SJohn Marino
190*e4b17023SJohn Marino template<typename _BidirectionalIterator>
191*e4b17023SJohn Marino inline _BidirectionalIterator
192*e4b17023SJohn Marino prev(_BidirectionalIterator __x, typename
193*e4b17023SJohn Marino iterator_traits<_BidirectionalIterator>::difference_type __n = 1)
194*e4b17023SJohn Marino {
195*e4b17023SJohn Marino std::advance(__x, -__n);
196*e4b17023SJohn Marino return __x;
197*e4b17023SJohn Marino }
198*e4b17023SJohn Marino
199*e4b17023SJohn Marino #endif // __GXX_EXPERIMENTAL_CXX0X__
200*e4b17023SJohn Marino
201*e4b17023SJohn Marino _GLIBCXX_END_NAMESPACE_VERSION
202*e4b17023SJohn Marino } // namespace
203*e4b17023SJohn Marino
204*e4b17023SJohn Marino #endif /* _STL_ITERATOR_BASE_FUNCS_H */
205