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