OmniSciDB  c07336695a
CartesianProduct.h
Go to the documentation of this file.
1 /*
2  * Copyright 2017 MapD Technologies, Inc.
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 // http://stackoverflow.com/questions/5279051/how-can-i-create-cartesian-product-of-vector-of-vectors
18 
19 #include <cassert>
20 
21 #include <limits>
22 #include <stdexcept>
23 #include <vector>
24 
25 #include <boost/iterator/iterator_facade.hpp>
26 
29 template <typename T>
31  : public boost::iterator_facade<CartesianProductIterator<T>,
32  std::vector<typename T::value_type::value_type> const,
33  boost::forward_traversal_tag> {
34  public:
36  CartesianProductIterator() = delete;
37 
39 
45  explicit CartesianProductIterator(T const& structure, std::size_t pos);
46 
47  private:
49  // \{
50  using OuterContainer = T;
51  using Container = typename T::value_type;
52  using Content = typename T::value_type::value_type;
53  // \}
54 
57 
59  void increment();
60 
62  bool equal(CartesianProductIterator<T> const& other) const;
63 
65  std::vector<Content> const& dereference() const;
66 
69 
71 
76  std::vector<typename Container::const_iterator> position_;
77 
79  std::size_t absolutePosition_ = 0;
80 
82  std::vector<typename Container::const_iterator> cbegins_;
83 
85  std::vector<typename Container::const_iterator> cends_;
86 
88 
92  mutable std::vector<std::vector<Content>> result_{std::vector<Content>()};
93 
95  std::size_t size_ = 0;
96 };
97 
98 template <typename T>
100  std::size_t pos)
101  : structure_(structure) {
102  for (auto& entry : structure_) {
103  cbegins_.push_back(entry.cbegin());
104  cends_.push_back(entry.cend());
105  ++size_;
106  }
107 
108  if (pos == std::numeric_limits<std::size_t>::max() || size_ == 0) {
109  absolutePosition_ = std::numeric_limits<std::size_t>::max();
110  return;
111  }
112 
113  // Initialize with all cbegin() position
114  position_.reserve(size_);
115  for (std::size_t i = 0; i != size_; ++i) {
116  position_.push_back(cbegins_[i]);
117  if (cbegins_[i] == cends_[i]) {
118  // Empty member, so Cartesian product is empty
119  absolutePosition_ = std::numeric_limits<std::size_t>::max();
120  return;
121  }
122  }
123 
124  // Increment to wanted position
125  for (std::size_t i = 0; i < pos; ++i) {
126  increment();
127  }
128 }
129 
130 template <typename T>
132  if (absolutePosition_ == std::numeric_limits<std::size_t>::max()) {
133  return;
134  }
135 
136  std::size_t pos = size_ - 1;
137 
138  // Descend as far as necessary
139  while (++(position_[pos]) == cends_[pos] && pos != 0) {
140  --pos;
141  }
142  if (position_[pos] == cends_[pos]) {
143  assert(pos == 0);
144  absolutePosition_ = std::numeric_limits<std::size_t>::max();
145  return;
146  }
147  // Set all to begin behind pos
148  for (++pos; pos != size_; ++pos) {
149  position_[pos] = cbegins_[pos];
150  }
152  result_.emplace_back();
153 }
154 
155 template <typename T>
156 std::vector<typename T::value_type::value_type> const&
158  if (absolutePosition_ == std::numeric_limits<std::size_t>::max()) {
159  throw new std::out_of_range("Out of bound dereference in CartesianProductIterator\n");
160  }
162  if (result.empty()) {
163  result.reserve(size_);
164  for (auto& iterator : position_) {
165  result.push_back(*iterator);
166  }
167  }
168 
169  return result;
170 }
171 
172 template <typename T>
174  return absolutePosition_ == other.absolutePosition_ && structure_ == other.structure_;
175 }
176 
179 // iterates over the Cartesian product of the forward iterable containers
180 template <typename T>
182  public:
184  explicit CartesianProduct(T const& t) : t_(t) {}
185 
188 
191  return CartesianProductIterator<T>(t_, std::numeric_limits<std::size_t>::max());
192  }
193 
194  private:
195  T const& t_;
196 };
CartesianProductIterator< T > begin() const
Iterator to beginning of Cartesian product.
CartesianProductIterator()=delete
Delete default constructor.
CartesianProductIterator< T > end() const
Iterator behind the last element of the Cartesian product.
OuterContainer const & structure_
The part we are iterating over.
std::size_t absolutePosition_
The position just indexed by an integer.
std::vector< Content > const & dereference() const
Dereference iterator.
void increment()
Increment iterator.
std::vector< typename Container::const_iterator > position_
The position in the Cartesian product.
std::vector< typename Container::const_iterator > cends_
The end iterators, saved for convenience and performance.
typename T::value_type::value_type Content
bool equal(CartesianProductIterator< T > const &other) const
Check for equality.
typename T::value_type Container
std::vector< std::vector< Content > > result_
Used for returning references.
std::vector< typename Container::const_iterator > cbegins_
The begin iterators, saved for convenience and performance.
std::size_t size_
The size of the instance of OuterContainer.
CartesianProduct(T const &t)
Constructor from type T.
friend class boost::iterator_core_access
Grant access to boost::iterator_facade.
T OuterContainer
Give types more descriptive names.