00001 // Functions used by iterators -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 2, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 /* 00032 * 00033 * Copyright (c) 1994 00034 * Hewlett-Packard Company 00035 * 00036 * Permission to use, copy, modify, distribute and sell this software 00037 * and its documentation for any purpose is hereby granted without fee, 00038 * provided that the above copyright notice appear in all copies and 00039 * that both that copyright notice and this permission notice appear 00040 * in supporting documentation. Hewlett-Packard Company makes no 00041 * representations about the suitability of this software for any 00042 * purpose. It is provided "as is" without express or implied warranty. 00043 * 00044 * 00045 * Copyright (c) 1996-1998 00046 * Silicon Graphics Computer Systems, Inc. 00047 * 00048 * Permission to use, copy, modify, distribute and sell this software 00049 * and its documentation for any purpose is hereby granted without fee, 00050 * provided that the above copyright notice appear in all copies and 00051 * that both that copyright notice and this permission notice appear 00052 * in supporting documentation. Silicon Graphics makes no 00053 * representations about the suitability of this software for any 00054 * purpose. It is provided "as is" without express or implied warranty. 00055 */ 00056 00057 /** @file stl_iterator_base_funcs.h 00058 * This is an internal header file, included by other library headers. 00059 * You should not attempt to use it directly. 00060 * 00061 * This file contains all of the general iterator-related utility 00062 * functions, such as distance() and advance(). 00063 */ 00064 00065 #ifndef _ITERATOR_BASE_FUNCS_H 00066 #define _ITERATOR_BASE_FUNCS_H 1 00067 00068 #pragma GCC system_header 00069 #include <bits/concept_check.h> 00070 00071 _GLIBCXX_BEGIN_NAMESPACE(std) 00072 00073 template<typename _InputIterator> 00074 inline typename iterator_traits<_InputIterator>::difference_type 00075 __distance(_InputIterator __first, _InputIterator __last, 00076 input_iterator_tag) 00077 { 00078 // concept requirements 00079 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00080 00081 typename iterator_traits<_InputIterator>::difference_type __n = 0; 00082 while (__first != __last) 00083 { 00084 ++__first; 00085 ++__n; 00086 } 00087 return __n; 00088 } 00089 00090 template<typename _RandomAccessIterator> 00091 inline typename iterator_traits<_RandomAccessIterator>::difference_type 00092 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 00093 random_access_iterator_tag) 00094 { 00095 // concept requirements 00096 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00097 _RandomAccessIterator>) 00098 return __last - __first; 00099 } 00100 00101 /** 00102 * @brief A generalization of pointer arithmetic. 00103 * @param first An input iterator. 00104 * @param last An input iterator. 00105 * @return The distance between them. 00106 * 00107 * Returns @c n such that first + n == last. This requires that @p last 00108 * must be reachable from @p first. Note that @c n may be negative. 00109 * 00110 * For random access iterators, this uses their @c + and @c - operations 00111 * and are constant time. For other %iterator classes they are linear time. 00112 */ 00113 template<typename _InputIterator> 00114 inline typename iterator_traits<_InputIterator>::difference_type 00115 distance(_InputIterator __first, _InputIterator __last) 00116 { 00117 // concept requirements -- taken care of in __distance 00118 return std::__distance(__first, __last, 00119 std::__iterator_category(__first)); 00120 } 00121 00122 template<typename _InputIterator, typename _Distance> 00123 inline void 00124 __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) 00125 { 00126 // concept requirements 00127 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00128 while (__n--) 00129 ++__i; 00130 } 00131 00132 template<typename _BidirectionalIterator, typename _Distance> 00133 inline void 00134 __advance(_BidirectionalIterator& __i, _Distance __n, 00135 bidirectional_iterator_tag) 00136 { 00137 // concept requirements 00138 __glibcxx_function_requires(_BidirectionalIteratorConcept< 00139 _BidirectionalIterator>) 00140 if (__n > 0) 00141 while (__n--) 00142 ++__i; 00143 else 00144 while (__n++) 00145 --__i; 00146 } 00147 00148 template<typename _RandomAccessIterator, typename _Distance> 00149 inline void 00150 __advance(_RandomAccessIterator& __i, _Distance __n, 00151 random_access_iterator_tag) 00152 { 00153 // concept requirements 00154 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00155 _RandomAccessIterator>) 00156 __i += __n; 00157 } 00158 00159 /** 00160 * @brief A generalization of pointer arithmetic. 00161 * @param i An input iterator. 00162 * @param n The "delta" by which to change @p i. 00163 * @return Nothing. 00164 * 00165 * This increments @p i by @p n. For bidirectional and random access 00166 * iterators, @p n may be negative, in which case @p i is decremented. 00167 * 00168 * For random access iterators, this uses their @c + and @c - operations 00169 * and are constant time. For other %iterator classes they are linear time. 00170 */ 00171 template<typename _InputIterator, typename _Distance> 00172 inline void 00173 advance(_InputIterator& __i, _Distance __n) 00174 { 00175 // concept requirements -- taken care of in __advance 00176 typename iterator_traits<_InputIterator>::difference_type __d = __n; 00177 std::__advance(__i, __d, std::__iterator_category(__i)); 00178 } 00179 00180 _GLIBCXX_END_NAMESPACE 00181 00182 #endif /* _ITERATOR_BASE_FUNCS_H */