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