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 
25 namespace 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 //    }
39 template <typename BaseIterator, typename Function>
40 class 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 
TransformIterator(BaseIterator base,Function fn)61   TransformIterator(BaseIterator base, Function fn)
62       : data_(base, fn) { }
63 
64   template <typename OtherBI>
TransformIterator(const TransformIterator<OtherBI,Function> & other)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.
base()132   BaseIterator base() const {
133     return data_.base_;
134   }
135 
136   // Retrieve the transformation function.
GetFunction()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:
DataData145     Data(BaseIterator base, Function fn) : Function(fn), base_(base) { }
146 
147     BaseIterator base_;
148   };
149 
150   Data data_;
151 };
152 
153 template <typename BaseIterator1, typename BaseIterator2, typename Function>
154 bool operator==(const TransformIterator<BaseIterator1, Function>& lhs,
155                 const TransformIterator<BaseIterator2, Function>& rhs) {
156   return lhs.base() == rhs.base();
157 }
158 
159 template <typename BaseIterator1, typename BaseIterator2, typename Function>
160 bool operator!=(const TransformIterator<BaseIterator1, Function>& lhs,
161                 const TransformIterator<BaseIterator2, Function>& rhs) {
162   return !(lhs == rhs);
163 }
164 
165 template <typename BaseIterator, typename Function>
MakeTransformIterator(BaseIterator base,Function f)166 TransformIterator<BaseIterator, Function> MakeTransformIterator(BaseIterator base, Function f) {
167   return TransformIterator<BaseIterator, Function>(base, f);
168 }
169 
170 template <typename BaseRange, typename Function>
MakeTransformRange(BaseRange & range,Function f)171 auto 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