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