1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements. See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership. The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License. You may obtain a copy of the License at
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied. See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18#ifndef ARROW_UTIL_LAZY_H
19#define ARROW_UTIL_LAZY_H
20
21#include <iterator>
22#include <utility>
23
24namespace arrow {
25namespace internal {
26
27/// Create a range from a callable which takes a single index parameter
28/// and returns the value of iterator on each call and a length.
29/// Only iterators obtained from the same range should be compared, the
30/// behaviour generally similar to other STL containers.
31template <typename Generator>
32class LazyRange {
33 private:
34 // callable which generates the values
35 // has to be defined at the beginning of the class for type deduction
36 const Generator gen_;
37 // the length of the range
38 int64_t length_;
39#ifdef _MSC_VER
40 // workaround to VS2010 not supporting decltype properly
41 // see https://stackoverflow.com/questions/21782846/decltype-for-class-member-function
42 static Generator gen_static_;
43#endif
44
45 public:
46#ifdef _MSC_VER
47 using return_type = decltype(gen_static_(0));
48#else
49 using return_type = decltype(gen_(0));
50#endif
51
52 /// Construct a new range from a callable and length
53 LazyRange(Generator gen, int64_t length) : gen_(gen), length_(length) {}
54
55 // Class of the dependent iterator, created implicitly by begin and end
56 class RangeIter {
57 public:
58 using difference_type = int64_t;
59 using value_type = return_type;
60 using reference = const value_type&;
61 using pointer = const value_type*;
62 using iterator_category = std::forward_iterator_tag;
63
64#ifdef _MSC_VER
65 // msvc complains about unchecked iterators,
66 // see https://stackoverflow.com/questions/21655496/error-c4996-checked-iterators
67 using _Unchecked_type = typename LazyRange<Generator>::RangeIter;
68#endif
69
70 RangeIter(const LazyRange<Generator>& range, int64_t index)
71 : range_(range), index_(index) {}
72
73 const return_type operator*() { return range_.gen_(index_); }
74
75 RangeIter operator+(difference_type length) {
76 return RangeIter(range_, index_ + length);
77 }
78
79 // pre-increment
80 RangeIter& operator++() {
81 ++index_;
82 return *this;
83 }
84
85 // post-increment
86 RangeIter operator++(int) {
87 auto copy = RangeIter(*this);
88 ++index_;
89 return copy;
90 }
91
92 bool operator==(const typename LazyRange<Generator>::RangeIter& other) const {
93 return this->index_ == other.index_ && &this->range_ == &other.range_;
94 }
95
96 bool operator!=(const typename LazyRange<Generator>::RangeIter& other) const {
97 return this->index_ != other.index_ || &this->range_ != &other.range_;
98 }
99
100 int64_t operator-(const typename LazyRange<Generator>::RangeIter& other) {
101 return this->index_ - other.index_;
102 }
103
104 private:
105 // parent range reference
106 const LazyRange& range_;
107 // current index
108 int64_t index_;
109 };
110
111 friend class RangeIter;
112
113 // Create a new begin const iterator
114 RangeIter begin() { return RangeIter(*this, 0); }
115
116 // Create a new end const iterator
117 RangeIter end() { return RangeIter(*this, length_); }
118};
119
120/// Helper function to create a lazy range from a callable (e.g. lambda) and length
121template <typename Generator>
122LazyRange<Generator> MakeLazyRange(Generator&& gen, int64_t length) {
123 return LazyRange<Generator>(std::forward<Generator>(gen), length);
124}
125
126} // namespace internal
127} // namespace arrow
128#endif
129