## Recursive template metaprogramming (Part III)

On the previous part, I went through some practice on abstractions when writing recursions.

This part would be the last part of the current topic. I would implement `MergeSort` with recursive template metaprogramming.

Continue reading “Recursive template metaprogramming (Part III)”

## Recursive template metaprogramming (Part II)

Previously I wrote about basic utility and simple examples of recursive template programming. On this part I will show how to write `Find`, `Remove`, `PopFront`, `PopBack`.

Continue reading “Recursive template metaprogramming (Part II)”

## Recursive template metaprogramming (Part I)

This article is a writeup to practice on recursive template metaprogramming. It is that may come in handy for compile time operations. I want to thank yoco for giving me a tutorial and introduction to the topic.

Continue reading “Recursive template metaprogramming (Part I)”

## Sorting std::unique_ptr in associative containers

Continue reading “Sorting std::unique_ptr in associative containers”

## Value Category（值類別）- 1 / 2

Continue reading “Value Category（值類別）- 1 / 2”

## Value Category（值類別）- 2 / 2

Continue reading “Value Category（值類別）- 2 / 2”

## 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.

### 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.

## CRTP

CRTP 全名 Curiously Recurring Template Pattern ，又被稱作 F-bound polymorphism ，F-bound quantification 中的一種形式。故事要先從型態轉型開始。