CartesianProduct.h

Go to the documentation of this file.

/*
 * Copyright 2022 HEAVY.AI, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// http://stackoverflow.com/questions/5279051/how-can-i-create-cartesian-product-of-vector-of-vectors

#include <cassert>

#include <limits>
#include <stdexcept>
#include <vector>

#include <boost/iterator/iterator_facade.hpp>

template <typename T>
class CartesianProductIterator
    : public boost::iterator_facade<CartesianProductIterator<T>,
                                    std::vector<typename T::value_type::value_type> const,
                                    boost::forward_traversal_tag> {
 public:
  CartesianProductIterator() = delete;


  explicit CartesianProductIterator(T const& structure, std::size_t pos);

 private:
  // \{
  using OuterContainer = T;
  using Container = typename T::value_type;
  using Content = typename T::value_type::value_type;
  // \}

  friend class boost::iterator_core_access;

  void increment();

  bool equal(CartesianProductIterator<T> const& other) const;

  std::vector<Content> const& dereference() const;

  OuterContainer const& structure_;


  std::vector<typename Container::const_iterator> position_;

  std::size_t absolutePosition_ = 0;

  std::vector<typename Container::const_iterator> cbegins_;

  std::vector<typename Container::const_iterator> cends_;


  mutable std::vector<std::vector<Content>> result_{std::vector<Content>()};

  std::size_t size_ = 0;
};

template <typename T>
CartesianProductIterator<T>::CartesianProductIterator(OuterContainer const& structure,
                                                      std::size_t pos)
    : structure_(structure) {
  for (auto& entry : structure_) {
    cbegins_.push_back(entry.cbegin());
    cends_.push_back(entry.cend());
    ++size_;
  }

  if (pos == std::numeric_limits<std::size_t>::max() || size_ == 0) {
    absolutePosition_ = std::numeric_limits<std::size_t>::max();
    return;
  }

  // Initialize with all cbegin() position
  position_.reserve(size_);
  for (std::size_t i = 0; i != size_; ++i) {
    position_.push_back(cbegins_[i]);
    if (cbegins_[i] == cends_[i]) {
      // Empty member, so Cartesian product is empty
      absolutePosition_ = std::numeric_limits<std::size_t>::max();
      return;
    }
  }

  // Increment to wanted position
  for (std::size_t i = 0; i < pos; ++i) {
    increment();
  }
}

template <typename T>
void CartesianProductIterator<T>::increment() {
  if (absolutePosition_ == std::numeric_limits<std::size_t>::max()) {
    return;
  }

  std::size_t pos = size_ - 1;

  // Descend as far as necessary
  while (++(position_[pos]) == cends_[pos] && pos != 0) {
    --pos;
  }
  if (position_[pos] == cends_[pos]) {
    assert(pos == 0);
    absolutePosition_ = std::numeric_limits<std::size_t>::max();
    return;
  }
  // Set all to begin behind pos
  for (++pos; pos != size_; ++pos) {
    position_[pos] = cbegins_[pos];
  }
  ++absolutePosition_;
  result_.emplace_back();
}

template <typename T>
std::vector<typename T::value_type::value_type> const&
CartesianProductIterator<T>::dereference() const {
  if (absolutePosition_ == std::numeric_limits<std::size_t>::max()) {
    throw new std::out_of_range("Out of bound dereference in CartesianProductIterator\n");
  }
  auto& result = result_[absolutePosition_];
  if (result.empty()) {
    result.reserve(size_);
    for (auto& iterator : position_) {
      result.push_back(*iterator);
    }
  }

  return result;
}

template <typename T>
bool CartesianProductIterator<T>::equal(CartesianProductIterator<T> const& other) const {
  return absolutePosition_ == other.absolutePosition_ && structure_ == other.structure_;
}

// iterates over the Cartesian product of the forward iterable containers
template <typename T>
class CartesianProduct {
 public:
  explicit CartesianProduct(T const& t) : t_(t) {}

  CartesianProductIterator<T> begin() const { return CartesianProductIterator<T>(t_, 0); }

  CartesianProductIterator<T> end() const {
    return CartesianProductIterator<T>(t_, std::numeric_limits<std::size_t>::max());
  }

 private:
  T const& t_;
};