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