xref: /dflybsd-src/contrib/gcc-4.7/libstdc++-v3/include/bits/stl_iterator_base_funcs.h (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
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