197403Sobrien// Functions used by iterators -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * 3397403Sobrien * Copyright (c) 1994 3497403Sobrien * Hewlett-Packard Company 3597403Sobrien * 3697403Sobrien * Permission to use, copy, modify, distribute and sell this software 3797403Sobrien * and its documentation for any purpose is hereby granted without fee, 3897403Sobrien * provided that the above copyright notice appear in all copies and 3997403Sobrien * that both that copyright notice and this permission notice appear 4097403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4197403Sobrien * representations about the suitability of this software for any 4297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4397403Sobrien * 4497403Sobrien * 4597403Sobrien * Copyright (c) 1996-1998 4697403Sobrien * Silicon Graphics Computer Systems, Inc. 4797403Sobrien * 4897403Sobrien * Permission to use, copy, modify, distribute and sell this software 4997403Sobrien * and its documentation for any purpose is hereby granted without fee, 5097403Sobrien * provided that the above copyright notice appear in all copies and 5197403Sobrien * that both that copyright notice and this permission notice appear 5297403Sobrien * in supporting documentation. Silicon Graphics makes no 5397403Sobrien * representations about the suitability of this software for any 5497403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5597403Sobrien */ 5697403Sobrien 5797403Sobrien/** @file stl_iterator_base_funcs.h 5897403Sobrien * This is an internal header file, included by other library headers. 5997403Sobrien * You should not attempt to use it directly. 6097403Sobrien * 6197403Sobrien * This file contains all of the general iterator-related utility 6297403Sobrien * functions, such as distance() and advance(). 6397403Sobrien */ 6497403Sobrien 65132720Skan#ifndef _ITERATOR_BASE_FUNCS_H 66132720Skan#define _ITERATOR_BASE_FUNCS_H 1 6797403Sobrien 6897403Sobrien#pragma GCC system_header 6997403Sobrien#include <bits/concept_check.h> 7097403Sobrien 71169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 72169691Skan 73117397Skan template<typename _InputIterator> 74117397Skan inline typename iterator_traits<_InputIterator>::difference_type 75117397Skan __distance(_InputIterator __first, _InputIterator __last, 76117397Skan input_iterator_tag) 77117397Skan { 78117397Skan // concept requirements 79132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 80132720Skan 81117397Skan typename iterator_traits<_InputIterator>::difference_type __n = 0; 82132720Skan while (__first != __last) 83132720Skan { 84132720Skan ++__first; 85132720Skan ++__n; 86132720Skan } 87117397Skan return __n; 8897403Sobrien } 89132720Skan 90117397Skan template<typename _RandomAccessIterator> 91117397Skan inline typename iterator_traits<_RandomAccessIterator>::difference_type 92117397Skan __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 93117397Skan random_access_iterator_tag) 94117397Skan { 95117397Skan // concept requirements 96132720Skan __glibcxx_function_requires(_RandomAccessIteratorConcept< 97132720Skan _RandomAccessIterator>) 98117397Skan return __last - __first; 99117397Skan } 100132720Skan 101117397Skan /** 102117397Skan * @brief A generalization of pointer arithmetic. 103117397Skan * @param first An input iterator. 104117397Skan * @param last An input iterator. 105117397Skan * @return The distance between them. 106117397Skan * 107117397Skan * Returns @c n such that first + n == last. This requires that @p last 108117397Skan * must be reachable from @p first. Note that @c n may be negative. 109117397Skan * 110117397Skan * For random access iterators, this uses their @c + and @c - operations 111117397Skan * and are constant time. For other %iterator classes they are linear time. 112117397Skan */ 113117397Skan template<typename _InputIterator> 114117397Skan inline typename iterator_traits<_InputIterator>::difference_type 115117397Skan distance(_InputIterator __first, _InputIterator __last) 116117397Skan { 117117397Skan // concept requirements -- taken care of in __distance 118132720Skan return std::__distance(__first, __last, 119132720Skan std::__iterator_category(__first)); 120117397Skan } 121132720Skan 122132720Skan template<typename _InputIterator, typename _Distance> 123117397Skan inline void 124132720Skan __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) 125117397Skan { 126117397Skan // concept requirements 127132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 128132720Skan while (__n--) 129132720Skan ++__i; 130117397Skan } 131132720Skan 132117397Skan template<typename _BidirectionalIterator, typename _Distance> 133117397Skan inline void 134117397Skan __advance(_BidirectionalIterator& __i, _Distance __n, 135169691Skan bidirectional_iterator_tag) 136117397Skan { 137117397Skan // concept requirements 138132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 139132720Skan _BidirectionalIterator>) 140117397Skan if (__n > 0) 141132720Skan while (__n--) 142132720Skan ++__i; 143117397Skan else 144132720Skan while (__n++) 145132720Skan --__i; 146117397Skan } 147132720Skan 148117397Skan template<typename _RandomAccessIterator, typename _Distance> 149117397Skan inline void 150117397Skan __advance(_RandomAccessIterator& __i, _Distance __n, 151117397Skan random_access_iterator_tag) 152117397Skan { 153117397Skan // concept requirements 154132720Skan __glibcxx_function_requires(_RandomAccessIteratorConcept< 155132720Skan _RandomAccessIterator>) 156117397Skan __i += __n; 157117397Skan } 158132720Skan 159117397Skan /** 160117397Skan * @brief A generalization of pointer arithmetic. 161117397Skan * @param i An input iterator. 162117397Skan * @param n The "delta" by which to change @p i. 163117397Skan * @return Nothing. 164117397Skan * 165117397Skan * This increments @p i by @p n. For bidirectional and random access 166117397Skan * iterators, @p n may be negative, in which case @p i is decremented. 167117397Skan * 168117397Skan * For random access iterators, this uses their @c + and @c - operations 169117397Skan * and are constant time. For other %iterator classes they are linear time. 170117397Skan */ 171117397Skan template<typename _InputIterator, typename _Distance> 172117397Skan inline void 173117397Skan advance(_InputIterator& __i, _Distance __n) 174117397Skan { 175117397Skan // concept requirements -- taken care of in __advance 176169691Skan typename iterator_traits<_InputIterator>::difference_type __d = __n; 177169691Skan std::__advance(__i, __d, std::__iterator_category(__i)); 178117397Skan } 17997403Sobrien 180169691Skan_GLIBCXX_END_NAMESPACE 181169691Skan 182132720Skan#endif /* _ITERATOR_BASE_FUNCS_H */ 183