Adding integer sequence and algorithms
This PR adds integer sequence and two algorithms (sum and exclusive
scan). Those will be needed to implement a sized cost function using
variadic templates.
Change-Id: I8e98d7c11fac94286fe9c364633406e59438f059
diff --git a/include/ceres/internal/integer_sequence.h b/include/ceres/internal/integer_sequence.h
new file mode 100644
index 0000000..3936b92
--- /dev/null
+++ b/include/ceres/internal/integer_sequence.h
@@ -0,0 +1,106 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2018 Google Inc. All rights reserved.
+// http://ceres-solver.org/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * 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.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 THE COPYRIGHT OWNER 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.
+//
+// Author: jodebo_beck@gmx.de (Johannes Beck)
+//
+// This class mimics std::integer_sequence. That is the reason to follow the
+// naming convention of the stl and not the google one. Once Ceres switches
+// to c++ 14 this class can be removed.
+
+#ifndef CERES_PUBLIC_INTERNAL_INTEGER_SEQUENCE_H_
+#define CERES_PUBLIC_INTERNAL_INTEGER_SEQUENCE_H_
+
+#if __cplusplus >= 201402L
+// We have at least c++ 14 support. Use integer_sequence from the standard.
+// Sometimes the STL implementation uses a compiler intrinsic to generate
+// the sequences which will speed up compilation.
+#include <utility>
+
+namespace ceres {
+namespace internal {
+template <typename T, T... Ns>
+using integer_sequence = std::integer_sequence<T, Ns...>;
+
+template <typename T, T N>
+using make_integer_sequence = std::make_integer_sequence<T, N>;
+
+} // namespace internal
+} // namespace ceres
+#else
+
+namespace ceres {
+namespace internal {
+
+template <typename T, T... Ns>
+struct integer_sequence {
+ using value_type = T;
+};
+
+// Implementation of make_integer_sequence.
+//
+// Recursively instantiate make_integer_sequence_impl until Ns
+// contains the sequence 0, 1, ..., Total-1.
+//
+// Example for Total = 4:
+// T CurIdx, Total, Ns...
+// make_integer_sequence_impl<int, 0, 4 >
+// make_integer_sequence_impl<int, 1, 4, 0 >
+// make_integer_sequence_impl<int, 2, 4, 0, 1 >
+// make_integer_sequence_impl<int, 3, 4, 0, 1, 2 >
+// make_integer_sequence_impl<int, 4, 4, 0, 1, 2, 3>
+// ^^^^^^^^^^
+// resulting sequence.
+//
+// The implemented algorithm has linear complexity for simplicity. A O(log(N))
+// implementation can be found e.g. here:
+// https://stackoverflow.com/questions/17424477/implementation-c14-make-integer-sequence
+template <typename T, T CurIdx, T Total, T... Ns>
+struct make_integer_sequence_impl {
+ using type = typename make_integer_sequence_impl<T, CurIdx + 1, Total, Ns...,
+ CurIdx>::type;
+};
+
+// End of 'recursion' when CurIdx reaches Total. All indices 0, 1, ..., N-1 are
+// contained in Ns. The final integer_sequence is created here.
+template <typename T, T Total, T... Ns>
+struct make_integer_sequence_impl<T, Total, Total, Ns...> {
+ using type = integer_sequence<T, Ns...>;
+};
+
+// A helper alias template to simplify creation of integer_sequence with 0, 1,
+// ..., N-1 as Ns:
+template <typename T, T N>
+using make_integer_sequence =
+ typename make_integer_sequence_impl<T, 0, N>::type;
+
+} // namespace internal
+} // namespace ceres
+
+#endif
+
+#endif // CERES_PUBLIC_INTERNAL_INTEGER_SEQUENCE_H_
diff --git a/include/ceres/internal/integer_sequence_algorithm.h b/include/ceres/internal/integer_sequence_algorithm.h
new file mode 100644
index 0000000..bdeab93
--- /dev/null
+++ b/include/ceres/internal/integer_sequence_algorithm.h
@@ -0,0 +1,165 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2018 Google Inc. All rights reserved.
+// http://ceres-solver.org/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * 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.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 THE COPYRIGHT OWNER 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.
+//
+// Author: jodebo_beck@gmx.de (Johannes Beck)
+//
+// Algorithms to be used together with integer_sequence, like computing the sum
+// or the exclusive scan (sometimes called exclusive prefix sum) at compile
+// time.
+
+#ifndef CERES_PUBLIC_INTERNAL_INTEGER_SEQUENCE_ALGORITHM_H_
+#define CERES_PUBLIC_INTERNAL_INTEGER_SEQUENCE_ALGORITHM_H_
+
+#include "integer_sequence.h"
+
+namespace ceres {
+namespace internal {
+
+// Implementation of calculating the sum of an integer sequence.
+// Recursively instantiate SumImpl and calculate the sum of the N first
+// numbers. This reduces the number of instantiations and speeds up
+// compilation.
+//
+// Examples:
+// 1) integer_sequence<int, 5>:
+// Value = 5
+//
+// 2) integer_sequence<int, 4, 2>:
+// Value = 4 + 2 + SumImpl<integer_sequence<int>>::Value
+// Value = 4 + 2 + 0
+//
+// 3) integer_sequence<int, 2, 1, 4>:
+// Value = 2 + 1 + SumImpl<integer_sequence<int, 4>>::Value
+// Value = 2 + 1 + 4
+template <typename Seq>
+struct SumImpl;
+
+// Strip of and sum the first number.
+template <typename T, T N, T... Ns>
+struct SumImpl<integer_sequence<T, N, Ns...>> {
+ static constexpr T Value = N + SumImpl<integer_sequence<T, Ns...>>::Value;
+};
+
+// Strip of and sum the first two numbers.
+template <typename T, T N1, T N2, T... Ns>
+struct SumImpl<integer_sequence<T, N1, N2, Ns...>> {
+ static constexpr T Value =
+ N1 + N2 + SumImpl<integer_sequence<T, Ns...>>::Value;
+};
+
+// Strip of and sum the first four numbers.
+template <typename T, T N1, T N2, T N3, T N4, T... Ns>
+struct SumImpl<integer_sequence<T, N1, N2, N3, N4, Ns...>> {
+ static constexpr T Value =
+ N1 + N2 + N3 + N4 + SumImpl<integer_sequence<T, Ns...>>::Value;
+};
+
+// Only one number is left. 'Value' is just that number ('recursion' ends).
+template <typename T, T N>
+struct SumImpl<integer_sequence<T, N>> {
+ static constexpr T Value = N;
+};
+
+// No number is left. 'Value' is the identity element (for sum this is zero).
+template <typename T>
+struct SumImpl<integer_sequence<T>> {
+ static constexpr T Value = T(0);
+};
+
+// Calculate the sum of an integer sequence. The resulting sum will be stored in
+// 'Value'.
+template <typename Seq>
+class Sum {
+ using T = typename Seq::value_type;
+
+ public:
+ static constexpr T Value = SumImpl<Seq>::Value;
+};
+
+// Implementation of calculating an exclusive scan (exclusive prefix sum) of an
+// integer sequence. Exclusive means that the i-th input element is not included
+// in the i-th sum. Calculating the exclusive scan for an input array I results
+// in the following output R:
+//
+// R[0] = 0
+// R[1] = I[0];
+// R[2] = I[0] + I[1];
+// R[3] = I[0] + I[1] + I[2];
+// ...
+//
+// In C++17 std::exclusive_scan does the same operation at runtime (but
+// cannot be used to calculate the prefix sum at compile time). See
+// https://en.cppreference.com/w/cpp/algorithm/exclusive_scan for a more
+// detailed description.
+//
+// Example for integer_sequence<int, 1, 4, 3> (seq := integer_sequence):
+// T , Sum, Ns... , Rs...
+// ExclusiveScanImpl<int, 0, seq<int, 1, 4, 3>, seq<int >>
+// ExclusiveScanImpl<int, 1, seq<int, 4, 3>, seq<int, 0 >>
+// ExclusiveScanImpl<int, 5, seq<int, 3>, seq<int, 0, 1 >>
+// ExclusiveScanImpl<int, 8, seq<int >, seq<int, 0, 1, 5>>
+// ^^^^^^^^^^^^^^^^^
+// resulting sequence
+template <typename T, T Sum, typename SeqIn, typename SeqOut>
+struct ExclusiveScanImpl;
+
+template <typename T, T Sum, T N, T... Ns, T... Rs>
+struct ExclusiveScanImpl<T, Sum, integer_sequence<T, N, Ns...>,
+ integer_sequence<T, Rs...>> {
+ using Type =
+ typename ExclusiveScanImpl<T, Sum + N, integer_sequence<T, Ns...>,
+ integer_sequence<T, Rs..., Sum>>::Type;
+};
+
+// End of 'recursion'. The resulting type is SeqOut.
+template <typename T, T Sum, typename SeqOut>
+struct ExclusiveScanImpl<T, Sum, integer_sequence<T>, SeqOut> {
+ using Type = SeqOut;
+};
+
+// Calculates the exclusive scan of the specified integer sequence. The last
+// element (the total) is not included in the resulting sequence so they have
+// same length. This means the exclusive scan of integer_sequence<int, 1, 2, 3>
+// will be integer_sequence<int, 0, 1, 3>.
+template <typename Seq>
+class ExclusiveScanT {
+ using T = typename Seq::value_type;
+
+ public:
+ using Type =
+ typename ExclusiveScanImpl<T, T(0), Seq, integer_sequence<T>>::Type;
+};
+
+// Helper to use exclusive scan without typename.
+template <typename Seq>
+using ExclusiveScan = typename ExclusiveScanT<Seq>::Type;
+
+} // namespace internal
+} // namespace ceres
+
+#endif // CERES_PUBLIC_INTERNAL_INTEGER_SEQUENCE_ALGORITHM_H_
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index e90562a..fbce418 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -431,6 +431,8 @@
ceres_test(implicit_schur_complement)
ceres_test(inner_product_computer)
ceres_test(invert_psd_matrix)
+ ceres_test(integer_sequence)
+ ceres_test(integer_sequence_algorithm)
ceres_test(is_close)
ceres_test(iterative_refiner)
ceres_test(iterative_schur_complement_solver)
diff --git a/internal/ceres/integer_sequence_algorithm_test.cc b/internal/ceres/integer_sequence_algorithm_test.cc
new file mode 100644
index 0000000..a6c85d0
--- /dev/null
+++ b/internal/ceres/integer_sequence_algorithm_test.cc
@@ -0,0 +1,71 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2018 Google Inc. All rights reserved.
+// http://ceres-solver.org/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * 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.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 THE COPYRIGHT OWNER 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.
+//
+// Author: jodebo_beck@gmx.de (Johannes Beck)
+
+#include "ceres/internal/integer_sequence_algorithm.h"
+
+#include <type_traits>
+
+namespace ceres {
+namespace internal {
+
+// Unit tests for summation of integer sequence.
+static_assert(Sum<integer_sequence<int>>::Value == 0,
+ "Unit test of summing up an integer sequence failed.");
+static_assert(Sum<integer_sequence<int, 2>>::Value == 2,
+ "Unit test of summing up an integer sequence failed.");
+static_assert(Sum<integer_sequence<int, 2, 3>>::Value == 5,
+ "Unit test of summing up an integer sequence failed.");
+static_assert(Sum<integer_sequence<int, 2, 3, 10>>::Value == 15,
+ "Unit test of summing up an integer sequence failed.");
+static_assert(Sum<integer_sequence<int, 2, 3, 10, 4>>::Value == 19,
+ "Unit test of summing up an integer sequence failed.");
+static_assert(Sum<integer_sequence<int, 2, 3, 10, 4, 1>>::Value == 20,
+ "Unit test of summing up an integer sequence failed.");
+
+// Unit tests for exclusive scan of integer sequence.
+static_assert(std::is_same<ExclusiveScan<integer_sequence<int>>,
+ integer_sequence<int>>::value,
+ "Unit test of calculating the exclusive scan of an integer "
+ "sequence failed.");
+static_assert(std::is_same<ExclusiveScan<integer_sequence<int, 2>>,
+ integer_sequence<int, 0>>::value,
+ "Unit test of calculating the exclusive scan of an integer "
+ "sequence failed.");
+static_assert(std::is_same<ExclusiveScan<integer_sequence<int, 2, 1>>,
+ integer_sequence<int, 0, 2>>::value,
+ "Unit test of calculating the exclusive scan of an integer "
+ "sequence failed.");
+static_assert(std::is_same<ExclusiveScan<integer_sequence<int, 2, 1, 10>>,
+ integer_sequence<int, 0, 2, 3>>::value,
+ "Unit test of calculating the exclusive scan of an integer "
+ "sequence failed.");
+
+} // namespace internal
+} // namespace ceres
diff --git a/internal/ceres/integer_sequence_test.cc b/internal/ceres/integer_sequence_test.cc
new file mode 100644
index 0000000..ab3559a
--- /dev/null
+++ b/internal/ceres/integer_sequence_test.cc
@@ -0,0 +1,58 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2018 Google Inc. All rights reserved.
+// http://ceres-solver.org/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * 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.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 THE COPYRIGHT OWNER 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.
+//
+// Author: jodebo_beck@gmx.de (Johannes Beck)
+
+#include "ceres/internal/integer_sequence.h"
+
+#include <type_traits>
+
+namespace ceres {
+namespace internal {
+
+// Unit test for integer_sequence<...>::value_type
+static_assert(std::is_same<integer_sequence<unsigned int, 0>::value_type,
+ unsigned int>::value,
+ "Unit test of integer sequence value type failed.");
+
+// Unit tests for make_integer_sequence
+static_assert(
+ std::is_same<make_integer_sequence<int, 0>, integer_sequence<int>>::value,
+ "Unit test of make integer sequence failed.");
+static_assert(std::is_same<make_integer_sequence<int, 1>,
+ integer_sequence<int, 0>>::value,
+ "Unit test of make integer sequence failed.");
+static_assert(std::is_same<make_integer_sequence<int, 2>,
+ integer_sequence<int, 0, 1>>::value,
+ "Unit test of make integer sequence failed.");
+static_assert(std::is_same<make_integer_sequence<int, 3>,
+ integer_sequence<int, 0, 1, 2>>::value,
+ "Unit test of make integer sequence failed.");
+
+} // namespace internal
+} // namespace ceres
