1/* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#ifndef ART_RUNTIME_BASE_TRANSFORM_ITERATOR_H_ 18#define ART_RUNTIME_BASE_TRANSFORM_ITERATOR_H_ 19 20#include <iterator> 21#include <type_traits> 22 23#include "base/iteration_range.h" 24 25namespace art { 26 27// The transform iterator transforms values from the base iterator with a given 28// transformation function. It can serve as a replacement for std::transform(), i.e. 29// std::copy(MakeTransformIterator(begin, f), MakeTransformIterator(end, f), out) 30// is equivalent to 31// std::transform(begin, end, f) 32// If the function returns an l-value reference or a wrapper that supports assignment, 33// the TransformIterator can be used also as an output iterator, i.e. 34// std::copy(begin, end, MakeTransformIterator(out, f)) 35// is equivalent to 36// for (auto it = begin; it != end; ++it) { 37// f(*out++) = *it; 38// } 39template <typename BaseIterator, typename Function> 40class TransformIterator { 41 private: 42 static_assert(std::is_base_of< 43 std::input_iterator_tag, 44 typename std::iterator_traits<BaseIterator>::iterator_category>::value, 45 "Transform iterator base must be an input iterator."); 46 47 using InputType = typename std::iterator_traits<BaseIterator>::reference; 48 using ResultType = typename std::result_of<Function(InputType)>::type; 49 50 public: 51 using iterator_category = typename std::iterator_traits<BaseIterator>::iterator_category; 52 using value_type = 53 typename std::remove_const<typename std::remove_reference<ResultType>::type>::type; 54 using difference_type = typename std::iterator_traits<BaseIterator>::difference_type; 55 using pointer = typename std::conditional< 56 std::is_reference<ResultType>::value, 57 typename std::add_pointer<typename std::remove_reference<ResultType>::type>::type, 58 TransformIterator>::type; 59 using reference = ResultType; 60 61 TransformIterator(BaseIterator base, Function fn) 62 : data_(base, fn) { } 63 64 template <typename OtherBI> 65 TransformIterator(const TransformIterator<OtherBI, Function>& other) // NOLINT, implicit 66 : data_(other.base(), other.GetFunction()) { 67 } 68 69 TransformIterator& operator++() { 70 ++data_.base_; 71 return *this; 72 } 73 74 TransformIterator& operator++(int) { 75 TransformIterator tmp(*this); 76 ++*this; 77 return tmp; 78 } 79 80 TransformIterator& operator--() { 81 static_assert( 82 std::is_base_of<std::bidirectional_iterator_tag, 83 typename std::iterator_traits<BaseIterator>::iterator_category>::value, 84 "BaseIterator must be bidirectional iterator to use operator--()"); 85 --data_.base_; 86 return *this; 87 } 88 89 TransformIterator& operator--(int) { 90 TransformIterator tmp(*this); 91 --*this; 92 return tmp; 93 } 94 95 reference operator*() const { 96 return GetFunction()(*base()); 97 } 98 99 reference operator[](difference_type n) const { 100 static_assert( 101 std::is_base_of<std::random_access_iterator_tag, 102 typename std::iterator_traits<BaseIterator>::iterator_category>::value, 103 "BaseIterator must be random access iterator to use operator[]"); 104 return GetFunction()(base()[n]); 105 } 106 107 TransformIterator operator+(difference_type n) const { 108 static_assert( 109 std::is_base_of<std::random_access_iterator_tag, 110 typename std::iterator_traits<BaseIterator>::iterator_category>::value, 111 "BaseIterator must be random access iterator to use operator+"); 112 return TransformIterator(base() + n, GetFunction()); 113 } 114 115 TransformIterator operator-(difference_type n) const { 116 static_assert( 117 std::is_base_of<std::random_access_iterator_tag, 118 typename std::iterator_traits<BaseIterator>::iterator_category>::value, 119 "BaseIterator must be random access iterator to use operator-"); 120 return TransformIterator(base() - n, GetFunction()); 121 } 122 123 difference_type operator-(const TransformIterator& other) const { 124 static_assert( 125 std::is_base_of<std::random_access_iterator_tag, 126 typename std::iterator_traits<BaseIterator>::iterator_category>::value, 127 "BaseIterator must be random access iterator to use operator-"); 128 return base() - other.base(); 129 } 130 131 // Retrieve the base iterator. 132 BaseIterator base() const { 133 return data_.base_; 134 } 135 136 // Retrieve the transformation function. 137 const Function& GetFunction() const { 138 return static_cast<const Function&>(data_); 139 } 140 141 private: 142 // Allow EBO for state-less Function. 143 struct Data : Function { 144 public: 145 Data(BaseIterator base, Function fn) : Function(fn), base_(base) { } 146 147 BaseIterator base_; 148 }; 149 150 Data data_; 151}; 152 153template <typename BaseIterator1, typename BaseIterator2, typename Function> 154bool operator==(const TransformIterator<BaseIterator1, Function>& lhs, 155 const TransformIterator<BaseIterator2, Function>& rhs) { 156 return lhs.base() == rhs.base(); 157} 158 159template <typename BaseIterator1, typename BaseIterator2, typename Function> 160bool operator!=(const TransformIterator<BaseIterator1, Function>& lhs, 161 const TransformIterator<BaseIterator2, Function>& rhs) { 162 return !(lhs == rhs); 163} 164 165template <typename BaseIterator, typename Function> 166TransformIterator<BaseIterator, Function> MakeTransformIterator(BaseIterator base, Function f) { 167 return TransformIterator<BaseIterator, Function>(base, f); 168} 169 170template <typename BaseRange, typename Function> 171auto MakeTransformRange(BaseRange& range, Function f) { 172 return MakeIterationRange(MakeTransformIterator(range.begin(), f), 173 MakeTransformIterator(range.end(), f)); 174} 175 176} // namespace art 177 178#endif // ART_RUNTIME_BASE_TRANSFORM_ITERATOR_H_ 179