Cartesian Coordinate Iterator

As I start getting familiar with STL, it came to me that rather than just simply using the library, I should further more practice on writing my own libraries. It is a practice of the process to formulate my requirement, extract them into fundamentals, and lastly provide clear interface to users. This practice also helps me get more familiar with the language itself.

This post is a practice on writing a Cartesian Coordinate iterator using C++. I would explain my interfaces, you can check out the full implementation on my Github.

Before starting I would like to thank poyenc for your review and helpful comments. <(_ _)>

Requirement / Motivation

It is important know where the problems come from, to formulate them and sort out the requirements. I was recently dealing with coordinate mapping and iterating through multidimensional data.

Therefore I came out with 2 requirements:

1. To iterate lexicographically from (n, c, h, w) to (maxN, maxC, maxH, maxW)
2. During iteration, I can access the current coordinate or offset

Container vs. Iterator

Containers are abstraction of data structures with collection of items. Iterator gives access to a single element inside a container.

So starting from constructor of the iterator, it should allow the user to give whatever container as long as the container is sequential and of the correct datatype.

Declaring shape of the data (constructor)

Following the requirements above, the maximum coordinate shall be set. The constructor of CartesianCoordinate will first take maximum coordinate. The following is the revised-implementation.

CartesianCoordinate() = delete;
CartesianCoordinate(std::initializer_list<T> maxAxis)
  : m_maxAxis(maxAxis)
{
  static_assert(std::is_unsigned<T>::value && std::is_integral<T>::value, "T should be unsigned integral");
  initializeVolume(maxAxis);
}
template <typename ContainerT>
CartesianCoordinate(ContainerT maxAxis)
  : m_maxAxis(maxAxis)
{
  static_assert(std::is_unsigned<typename ContainerT::value_type>::value &&
                std::is_integral<typename ContainerT::value_type>::value,
                "ContainerT should be of unsigned integral");
  static_assert(std::is_same<T, typename ContainerT::value_type>::value, "ContainerT value type should match T");
  initializeVolume(maxAxis);
}

Further more this is a C++11 implementation, so I have to check datatype of the input containers. For C++14 or above there is std::integer_sequence or more for compile time integer sequences.

Underlying iterator

For iteration over coordinates it is rather simple, possible use-case includes functionalities like ++ , -- , += value , -= value . A former iterator also needs to implement pointer, reference, and operator member functions.

Iteration over coordinate (requirement 1)

The data structure abstracts coordinate as underlying elements. It gives interface like std::vector , letting users take begin , end , and at .

iterator begin() const { return iterator(0); }
iterator end() const { return iterator(m_maxOffset); }
iterator at(std::initializer_list<T> startAxis) const
{
  assert(startAxis.size() == m_maxAxis.size() && "argument should be match the dimension initialized");
  offset_type currOffset = calcOffset(m_maxAxis.size(), 
  std::begin(startAxis));
  return iterator(currOffset);
}
template <typename ContainerT>
iterator at(ContainerT startAxis) const
{
  static_assert(std::is_same<T, typename ContainerT::value_type>::value, "ContainerT value type should match T");
  assert(startAxis.size() == m_maxAxis.size() && "argument should be match the dimension initialized");
  offset_type currOffset = calcOffset(m_maxAxis.size(), 
  std::begin(startAxis));
  return iterator(currOffset);
}

Access during iterator (requirement 2)

User may want to know the coordinate or offset of the current iteration. The library shall give the user maximum ability to customize. Therefore, coordOf takes an iterator (OutputIterator), so the user is able to use any sequential container it desires.

offset_type offsetOf(iterator it) const { return it(); }
template <typename OutputIterator>
void coordOf(iterator it, OutputIterator out) const
{
  offset_type temp = it();
  typename container_type::size_type maxDim = m_maxAxis.size();
  for (typename container_type::size_type idx = 0; idx < maxDim; ++idx) {
    *out++ = temp / m_volume[idx];
    temp = temp % m_volume[idx];
  }
}

Use-case: for-loop

// from (0, 0, 0, 0) to (1, 1, 2, 2) 
CartesianCoordinate<unsigned> shape({2, 2, 3, 3}); 
for (decltype(shape)::iterator it = shape.begin(); it != shape.end(); ++it);
CartesianCoordinate<unsigned> coord({1, 1, 1, 1});
for (auto elem : coord);// from coord to shape.end()

Use-case: integration with STL

auto result =
    std::accumulate(std::begin(coord), std::end(coord), 0, [](const unsigned& a, const unsigned& b) { return a + b; });

Use-case: offset / coordinate

for (decltype(shape)::iterator it = shape.at({1, 1, 1, 1}); it != shape.end(); ++it) {
  std::vector<unsigned int> getCoord;
  shape.coordOf(it, std::back_inserter(getCoord));
  decltype(shape)::offset_type currOffset = shape.offsetOf(it);
}

Github

You can check out the full implementation on my Github.

Original link: eopXD