iterator.h revision 7ad046f5968d4709c3c68d165387d13f1da7bab6
17ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// 27ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 37ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// The LLVM Compiler Infrastructure 47ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 57ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file is distributed under the University of Illinois Open Source 67ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// License. See LICENSE.TXT for details. 77ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 87ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 97ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#ifndef LLVM_ADT_ITERATOR_H 117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#define LLVM_ADT_ITERATOR_H 127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <cstddef> 147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <iterator> 157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensnamespace llvm { 177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief CRTP base class which implements the entire standard iterator facade 197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// in terms of a minimal subset of the interface. 207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Use this when it is reasonable to implement most of the iterator 227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// functionality in terms of a core subset. If you need special behavior or 237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// there are performance implications for this, you may want to override the 247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// relevant members instead. 257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Note, one abstraction that this does *not* provide is implementing 277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// subtraction in terms of addition by negating the difference. Negation isn't 287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// always information preserving, and I can see very reasonable iterator 297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// designs where this doesn't work well. It doesn't really force much added 307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// boilerplate anyways. 317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Another abstraction that this doesn't provide is implementing increment in 337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// terms of addition of one. These aren't equivalent for all iterator 347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// categories, and respecting that adds a lot of complexity for little gain. 357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename DerivedT, typename IteratorCategoryT, typename T, 367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, 377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename ReferenceT = T &> 387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensclass iterator_facade_base 397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, 407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ReferenceT> { 417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensprotected: 427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens enum { 437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsRandomAccess = 447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value, 457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsBidirectional = 467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value, 477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens }; 487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// A proxy object for computing a reference via indirecting a copy of an 507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// iterator. This is used in APIs which need to produce a reference via 517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// indirection but for which the iterator object might be a temporary. The 527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// proxy preserves the iterator internally and exposes the indirected 537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// reference via a conversion operator. 547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens class ReferenceProxy { 557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens friend iterator_facade_base; 567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT I; 587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ReferenceProxy(DerivedT I) : I(std::move(I)) {} 607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens public: 627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens operator ReferenceT() const { return *I; } 637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens }; 647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT operator+(DifferenceTypeT n) const { 677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsRandomAccess, 697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The '+' operator is only defined for random access iterators."); 707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT tmp = *static_cast<const DerivedT *>(this); 717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens tmp += n; 727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return tmp; 737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { 757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsRandomAccess, 777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The '+' operator is only defined for random access iterators."); 787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return i + n; 797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT operator-(DifferenceTypeT n) const { 817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsRandomAccess, 837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The '-' operator is only defined for random access iterators."); 847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT tmp = *static_cast<const DerivedT *>(this); 857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens tmp -= n; 867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return tmp; 877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT &operator++() { 907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return static_cast<DerivedT *>(this)->operator+=(1); 917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT operator++(int) { 937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT tmp = *static_cast<DerivedT *>(this); 947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++*static_cast<DerivedT *>(this); 957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return tmp; 967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT &operator--() { 987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsBidirectional, 1007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The decrement operator is only defined for bidirectional iterators."); 1017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return static_cast<DerivedT *>(this)->operator-=(1); 1027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT operator--(int) { 1047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 1057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsBidirectional, 1067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The decrement operator is only defined for bidirectional iterators."); 1077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT tmp = *static_cast<DerivedT *>(this); 1087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens --*static_cast<DerivedT *>(this); 1097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return tmp; 1107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator!=(const DerivedT &RHS) const { 1137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return !static_cast<const DerivedT *>(this)->operator==(RHS); 1147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator>(const DerivedT &RHS) const { 1177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 1187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsRandomAccess, 1197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "Relational operators are only defined for random access iterators."); 1207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return !static_cast<const DerivedT *>(this)->operator<(RHS) && 1217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens !static_cast<const DerivedT *>(this)->operator==(RHS); 1227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator<=(const DerivedT &RHS) const { 1247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 1257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsRandomAccess, 1267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "Relational operators are only defined for random access iterators."); 1277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return !static_cast<const DerivedT *>(this)->operator>(RHS); 1287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator>=(const DerivedT &RHS) const { 1307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 1317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IsRandomAccess, 1327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "Relational operators are only defined for random access iterators."); 1337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return !static_cast<const DerivedT *>(this)->operator<(RHS); 1347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens PointerT operator->() const { 1377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return &static_cast<const DerivedT *>(this)->operator*(); 1387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ReferenceProxy operator[](DifferenceTypeT n) const { 1407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert(IsRandomAccess, 1417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "Subscripting is only defined for random access iterators."); 1427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n)); 1437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 1457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief CRTP base class for adapting an iterator to a different type. 1477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 1487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// This class can be used through CRTP to adapt one iterator into another. 1497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Typically this is done through providing in the derived class a custom \c 1507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// operator* implementation. Other methods can be overridden as well. 1517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate < 1527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename DerivedT, typename WrappedIteratorT, 1537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename IteratorCategoryT = 1547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::iterator_traits<WrappedIteratorT>::iterator_category, 1557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, 1567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename DifferenceTypeT = 1577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::iterator_traits<WrappedIteratorT>::difference_type, 1587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename PointerT = typename std::conditional< 1597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::is_same<T, typename std::iterator_traits< 1607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens WrappedIteratorT>::value_type>::value, 1617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type, 1627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename ReferenceT = typename std::conditional< 1637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::is_same<T, typename std::iterator_traits< 1647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens WrappedIteratorT>::value_type>::value, 1657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type, 1667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Don't provide these, they are mostly to act as aliases below. 1677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> 1687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensclass iterator_adaptor_base 1697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : public iterator_facade_base<DerivedT, IteratorCategoryT, T, 1707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DifferenceTypeT, PointerT, ReferenceT> { 1717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef typename iterator_adaptor_base::iterator_facade_base BaseT; 1727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensprotected: 1747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens WrappedIteratorT I; 1757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens iterator_adaptor_base() = default; 1777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {} 1797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const WrappedIteratorT &wrapped() const { return I; } 1817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 1837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef DifferenceTypeT difference_type; 1847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT &operator+=(difference_type n) { 1867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 1877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BaseT::IsRandomAccess, 1887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The '+=' operator is only defined for random access iterators."); 1897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens I += n; 1907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *static_cast<DerivedT *>(this); 1917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT &operator-=(difference_type n) { 1937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 1947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BaseT::IsRandomAccess, 1957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The '-=' operator is only defined for random access iterators."); 1967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens I -= n; 1977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *static_cast<DerivedT *>(this); 1987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens using BaseT::operator-; 2007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens difference_type operator-(const DerivedT &RHS) const { 2017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 2027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BaseT::IsRandomAccess, 2037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The '-' operator is only defined for random access iterators."); 2047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return I - RHS.I; 2057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // We have to explicitly provide ++ and -- rather than letting the facade 2087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // forward to += because WrappedIteratorT might not support +=. 2097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens using BaseT::operator++; 2107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT &operator++() { 2117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++I; 2127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *static_cast<DerivedT *>(this); 2137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens using BaseT::operator--; 2157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens DerivedT &operator--() { 2167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 2177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BaseT::IsBidirectional, 2187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "The decrement operator is only defined for bidirectional iterators."); 2197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens --I; 2207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *static_cast<DerivedT *>(this); 2217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator==(const DerivedT &RHS) const { return I == RHS.I; } 2247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator<(const DerivedT &RHS) const { 2257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert( 2267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BaseT::IsRandomAccess, 2277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "Relational operators are only defined for random access iterators."); 2287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return I < RHS.I; 2297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ReferenceT operator*() const { return *I; } 2327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief An iterator type that allows iterating over the pointees via some 2357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// other iterator. 2367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 2377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// The typical usage of this is to expose a type that iterates over Ts, but 2387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// which is implemented with some iterator over T*s: 2397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 2407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \code 2417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator; 2427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \endcode 2437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename WrappedIteratorT, 2447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename T = typename std::remove_reference< 2457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens decltype(**std::declval<WrappedIteratorT>())>::type> 2467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct pointee_iterator 2477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : iterator_adaptor_base< 2487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens pointee_iterator<WrappedIteratorT>, WrappedIteratorT, 2497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::iterator_traits<WrappedIteratorT>::iterator_category, 2507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens T> { 2517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens pointee_iterator() = default; 2527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename U> 2537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens pointee_iterator(U &&u) 2547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} 2557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens T &operator*() const { return **this->I; } 2577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename WrappedIteratorT, 2607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename T = decltype(&*std::declval<WrappedIteratorT>())> 2617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensclass pointer_iterator 2627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : public iterator_adaptor_base<pointer_iterator<WrappedIteratorT>, 2637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens WrappedIteratorT, T> { 2647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mutable T Ptr; 2657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 2677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens pointer_iterator() {} 2687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens explicit pointer_iterator(WrappedIteratorT u) 2707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : pointer_iterator::iterator_adaptor_base(std::move(u)) {} 2717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens T &operator*() { return Ptr = &*this->I; } 2737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const T &operator*() const { return Ptr = &*this->I; } 2747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#endif 279