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