OmniSciDB  04ee39c94c
CartesianProductIterator< T > Class Template Reference

#include <CartesianProduct.h>

+ Inheritance diagram for CartesianProductIterator< T >:
+ Collaboration diagram for CartesianProductIterator< T >:

Public Member Functions

 CartesianProductIterator ()=delete
 Delete default constructor. More...
 
 CartesianProductIterator (T const &structure, std::size_t pos)
 Constructor setting the underlying iterator and position. More...
 

Private Types

using OuterContainer = T
 Give types more descriptive names. More...
 
using Container = typename T::value_type
 
using Content = typename T::value_type::value_type
 

Private Member Functions

void increment ()
 Increment iterator. More...
 
bool equal (CartesianProductIterator< T > const &other) const
 Check for equality. More...
 
std::vector< Content > const & dereference () const
 Dereference iterator. More...
 

Private Attributes

OuterContainer const & structure_
 The part we are iterating over. More...
 
std::vector< typename Container::const_iterator > position_
 The position in the Cartesian product. More...
 
std::size_t absolutePosition_ = 0
 The position just indexed by an integer. More...
 
std::vector< typename Container::const_iterator > cbegins_
 The begin iterators, saved for convenience and performance. More...
 
std::vector< typename Container::const_iterator > cends_
 The end iterators, saved for convenience and performance. More...
 
std::vector< std::vector< Content > > result_ {std::vector<Content>()}
 Used for returning references. More...
 
std::size_t size_ = 0
 The size of the instance of OuterContainer. More...
 

Friends

class boost::iterator_core_access
 Grant access to boost::iterator_facade. More...
 

Detailed Description

template<typename T>
class CartesianProductIterator< T >

Class iterating over the Cartesian product of a forward iterable container of forward iterable containers

Definition at line 30 of file CartesianProduct.h.

Member Typedef Documentation

◆ Container

template<typename T>
using CartesianProductIterator< T >::Container = typename T::value_type
private

Definition at line 51 of file CartesianProduct.h.

◆ Content

template<typename T>
using CartesianProductIterator< T >::Content = typename T::value_type::value_type
private

Definition at line 52 of file CartesianProduct.h.

◆ OuterContainer

template<typename T>
using CartesianProductIterator< T >::OuterContainer = T
private

Give types more descriptive names.

Definition at line 50 of file CartesianProduct.h.

Constructor & Destructor Documentation

◆ CartesianProductIterator() [1/2]

template<typename T>
CartesianProductIterator< T >::CartesianProductIterator ( )
delete

Delete default constructor.

◆ CartesianProductIterator() [2/2]

template<typename T >
CartesianProductIterator< T >::CartesianProductIterator ( T const &  structure,
std::size_t  pos 
)
explicit

Constructor setting the underlying iterator and position.

Parameters
[in]structureThe underlying structure
[in]posThe position the iterator should be initialized to. std::numeric_limits<std::size_t>::max()stands for the end, the position after the last element.

Definition at line 99 of file CartesianProduct.h.

References CartesianProductIterator< T >::absolutePosition_, CartesianProductIterator< T >::cbegins_, CartesianProductIterator< T >::cends_, CartesianProductIterator< T >::increment(), CartesianProductIterator< T >::position_, CartesianProductIterator< T >::size_, and CartesianProductIterator< T >::structure_.

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 }
OuterContainer const & structure_
The part we are iterating over.
std::size_t absolutePosition_
The position just indexed by an integer.
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.
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.
+ Here is the call graph for this function:

Member Function Documentation

◆ dereference()

template<typename T >
std::vector< typename T::value_type::value_type > const & CartesianProductIterator< T >::dereference ( ) const
private

Dereference iterator.

Definition at line 157 of file CartesianProduct.h.

References CartesianProductIterator< T >::absolutePosition_, CartesianProductIterator< T >::position_, run-benchmark-import::result, CartesianProductIterator< T >::result_, and CartesianProductIterator< T >::size_.

157  {
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 }
std::size_t absolutePosition_
The position just indexed by an integer.
std::vector< typename Container::const_iterator > position_
The position in the Cartesian product.
std::vector< std::vector< Content > > result_
Used for returning references.
std::size_t size_
The size of the instance of OuterContainer.

◆ equal()

template<typename T >
bool CartesianProductIterator< T >::equal ( CartesianProductIterator< T > const &  other) const
private

Check for equality.

Definition at line 173 of file CartesianProduct.h.

References CartesianProductIterator< T >::absolutePosition_, and CartesianProductIterator< T >::structure_.

173  {
174  return absolutePosition_ == other.absolutePosition_ && structure_ == other.structure_;
175 }
OuterContainer const & structure_
The part we are iterating over.
std::size_t absolutePosition_
The position just indexed by an integer.

◆ increment()

template<typename T >
void CartesianProductIterator< T >::increment ( )
private

Increment iterator.

Definition at line 131 of file CartesianProduct.h.

References CartesianProductIterator< T >::absolutePosition_, CartesianProductIterator< T >::cbegins_, CartesianProductIterator< T >::cends_, CartesianProductIterator< T >::position_, CartesianProductIterator< T >::result_, and CartesianProductIterator< T >::size_.

Referenced by CartesianProductIterator< T >::CartesianProductIterator().

131  {
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 }
std::size_t absolutePosition_
The position just indexed by an integer.
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.
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.
+ Here is the caller graph for this function:

Friends And Related Function Documentation

◆ boost::iterator_core_access

template<typename T>
friend class boost::iterator_core_access
friend

Grant access to boost::iterator_facade.

Definition at line 56 of file CartesianProduct.h.

Member Data Documentation

◆ absolutePosition_

template<typename T>
std::size_t CartesianProductIterator< T >::absolutePosition_ = 0
private

◆ cbegins_

template<typename T>
std::vector<typename Container::const_iterator> CartesianProductIterator< T >::cbegins_
private

The begin iterators, saved for convenience and performance.

Definition at line 82 of file CartesianProduct.h.

Referenced by CartesianProductIterator< T >::CartesianProductIterator(), and CartesianProductIterator< T >::increment().

◆ cends_

template<typename T>
std::vector<typename Container::const_iterator> CartesianProductIterator< T >::cends_
private

The end iterators, saved for convenience and performance.

Definition at line 85 of file CartesianProduct.h.

Referenced by CartesianProductIterator< T >::CartesianProductIterator(), and CartesianProductIterator< T >::increment().

◆ position_

template<typename T>
std::vector<typename Container::const_iterator> CartesianProductIterator< T >::position_
private

The position in the Cartesian product.

For each element of structure_, give the position in it. The empty vector represents the end position. Note that this vector has a size equal to structure->size(), or is empty.

Definition at line 76 of file CartesianProduct.h.

Referenced by CartesianProductIterator< T >::CartesianProductIterator(), CartesianProductIterator< T >::dereference(), and CartesianProductIterator< T >::increment().

◆ result_

template<typename T>
std::vector<std::vector<Content> > CartesianProductIterator< T >::result_ {std::vector<Content>()}
mutableprivate

Used for returning references.

We initialize with one empty element, so that we only need to add more elements in increment().

Definition at line 92 of file CartesianProduct.h.

Referenced by CartesianProductIterator< T >::dereference(), and CartesianProductIterator< T >::increment().

◆ size_

template<typename T>
std::size_t CartesianProductIterator< T >::size_ = 0
private

◆ structure_

template<typename T>
OuterContainer const& CartesianProductIterator< T >::structure_
private

The part we are iterating over.

Definition at line 68 of file CartesianProduct.h.

Referenced by CartesianProductIterator< T >::CartesianProductIterator(), and CartesianProductIterator< T >::equal().


The documentation for this class was generated from the following file: