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