Enumerate the elements of n-th order tensor (C++ class, CRTP)

Readme.txt

Enumerate the elements of n-th order tensor (C++ class, CRTP)
n階テンソルの要素を列挙する C++ クラス CRTP 版

CRTP: Curiously Recurring Template Pattern

Example:

```
$ make
g++ -std=c++11 -o tensor_enum_sample sample_main.cc

$ ./tensor_enum_sample
Enumerate all indices of 3rd-order 2x3x4 tensor
  --- begin = {0, 0, 0}, end = {2, 3, 4} ---
 0 0 0
 0 0 1
 0 0 2
 0 0 3
 0 1 0
 0 1 1
 0 1 2
 0 1 3
 0 2 0
 0 2 1
 0 2 2
 0 2 3
 1 0 0
 1 0 1
 1 0 2
 1 0 3
 1 1 0
 1 1 1
 1 1 2
 1 1 3
 1 2 0
 1 2 1
 1 2 2
 1 2 3
true

Enumerate some indices of 3rd-order 2x3x4 tensor
  --- begin = {0, 1, 0}, end = {2, 2, 4} ---
 0 1 0
 0 1 1
 0 1 2
 0 1 3
 1 1 0
 1 1 1
 1 1 2
 1 1 3
true

Enumerate some indices of 3rd-order 2x3x4 tensor
  --- begin = {0, 1, 0}, end = {2, 1, 4} ---
false

Enumerate all indices of 2nd-order 5x5 tensor (matrix)
  --- begin = {0, 0}, end = {5, 5} ---
 0 0
 0 1
 0 2
 0 3
 0 4
 1 0
 1 1
 1 2
 1 3
 1 4
 2 0
 2 1
 2 2
 2 3
 2 4
 3 0
 3 1
 3 2
 3 3
 3 4
 4 0
 4 1
 4 2
 4 3
 4 4
true

Enumerate all indices of 4th-order 2x2x2x2 tensor
  --- begin = {0, 0, 0, 0}, end = {2, 2, 2, 2} ---
 0 0 0 0
 0 0 0 1
 0 0 1 0
 0 0 1 1
 0 1 0 0
 0 1 0 1
 0 1 1 0
 0 1 1 1
 1 0 0 0
 1 0 0 1
 1 0 1 0
 1 0 1 1
 1 1 0 0
 1 1 0 1
 1 1 1 0
 1 1 1 1
true


$
```

Variations:

Virtual function
https://gist.github.com/trueroad/6987b5470ec337e8ba5ef12f4cce8cef

CRTP (Curiously Recurring Template Pattern)
https://gist.github.com/trueroad/a924c947aef244947d368a30f18e0be2

Closure
https://gist.github.com/trueroad/deb5a9b90781f7c40e7a6bb2b22fb2c1

Makefile

CXX = g++

tensor_enum_sample: sample_main.cc tensor_enum.hh
	$(CXX) -std=c++11 -o tensor_enum_sample sample_main.cc

clean:
	-rm -fr *~

sample_main.cc

//
// Sample for
// `Enumerate the elements of n-th order tensor (C++ class, CRTP)'
//
// Copyright (C) 2016 Masamichi Hosoda. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//

#include "tensor_enum.hh"
#include <vector>
#include <iostream>

// Show the indices of n-th order tensor
class TensorShowIndices: public TensorEnumerateElements<TensorShowIndices>
{
public:
  enumerated ();
};

// Show the enumerated index
TensorShowIndices::enumerated ()
{
  for (auto it = index_.begin (); it != index_.end (); ++it)
    {
      std::cout << " " << *it;
    }
  std::cout << std::endl;
}

int main()
{
  TensorShowIndices tensor_show;

  {
    std::cout << "Enumerate all indices of 3rd-order 2x3x4 tensor"
              << std::endl
              << "  --- begin = {0, 0, 0}, end = {2, 3, 4} ---"
              << std::endl;

    bool retval = tensor_show.loop ({0, 0, 0}, {2, 3, 4});
    std::cout << std::boolalpha << retval << std::endl << std::endl;
  }

  {
    std::cout << "Enumerate some indices of 3rd-order 2x3x4 tensor"
              << std::endl
              << "  --- begin = {0, 1, 0}, end = {2, 2, 4} ---"
              << std::endl;

    bool retval = tensor_show.loop ({0, 1, 0}, {2, 2, 4});
    std::cout << std::boolalpha << retval << std::endl << std::endl;
  }

  {
    std::cout << "Enumerate some indices of 3rd-order 2x3x4 tensor"
              << std::endl
              << "  --- begin = {0, 1, 0}, end = {2, 1, 4} ---"
              << std::endl;

    bool retval = tensor_show.loop ({0, 1, 0}, {2, 1, 4});
    std::cout << std::boolalpha << retval << std::endl << std::endl;
  }

  {
    std::cout << "Enumerate all indices of 2nd-order 5x5 tensor (matrix)"
              << std::endl
              << "  --- begin = {0, 0}, end = {5, 5} ---"
              << std::endl;

    bool retval = tensor_show.loop ({0, 0}, {5, 5});
    std::cout << std::boolalpha << retval << std::endl << std::endl;
  }

  {
    std::cout << "Enumerate all indices of 4th-order 2x2x2x2 tensor"
              << std::endl
              << "  --- begin = {0, 0, 0, 0}, end = {2, 2, 2, 2} ---"
              << std::endl;

    bool retval = tensor_show.loop ({0, 0, 0, 0}, {2, 2, 2, 2});
    std::cout << std::boolalpha << retval << std::endl << std::endl;
  }

  return 0;
}

tensor_enum.hh

//
// Enumerate the elements of n-th order tensor (C++ class, CRTP)
//
// Copyright (C) 2016 Masamichi Hosoda. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//

#ifndef TENSOR_ENUM_HH
#define TENSOR_ENUM_HH

#include <vector>
#include <algorithm>

// Enumerate the elements of n-th order tensor
template <class Derived>
class TensorEnumerateElements
{
public:
  bool loop (const std::vector<int> &begin,
             const std::vector<int> &end);

  TensorEnumerateElements () = default;
  // Destructor is non-virtual protected.

  TensorEnumerateElements (TensorEnumerateElements const&) = delete;
  TensorEnumerateElements& operator= (TensorEnumerateElements const&) = delete;
  TensorEnumerateElements (TensorEnumerateElements &&) = delete;
  TensorEnumerateElements& operator= (TensorEnumerateElements &&) = delete;

protected:
  std::vector<int> index_;

  enumerated ()
  {
    static_cast<Derived*>(this)->enumerated ();
  }

  ~TensorEnumerateElements () = default;  // non-virtual protected destructor
};

template <class Derived>
bool TensorEnumerateElements<Derived>::loop (const std::vector<int> &begin,
                                             const std::vector<int> &end)
{
  // Check tensor order
  if (begin.size () != end.size ())
    return false;

  // Check begin < end
  auto begin_it = begin.begin ();
  auto end_it = end.begin ();
  while (begin_it != begin.end ())
    {
      if (*begin_it >= *end_it)
        return false;

      ++begin_it;
      ++end_it;
    }

  // Main loop
  index_ = begin;
  do
    {
      enumerated ();

      // Count up index
      auto index_r_it = index_.rbegin ();
      auto begin_r_it = begin.rbegin ();
      auto end_r_it = end.rbegin ();
      while (index_r_it != index_.rend ())
        {
          ++(*index_r_it);
          if (*index_r_it < *end_r_it)
            break;

          *index_r_it = *begin_r_it;  // Carry

          ++index_r_it;
          ++begin_r_it;
          ++end_r_it;
        }
    }
  while(!std::equal (index_.begin (), index_.end (), begin.begin ()));

  return true;
}

#endif // TENSOR_ENUM_HH