ublas/tensor/multi_index_utility.hpp

0001 //
0002 //  Copyright (c) 2018-2019, Cem Bassoy, cem.bassoy@gmail.com
0003 //
0004 //  Distributed under the Boost Software License, Version 1.0. (See
0005 //  accompanying file LICENSE_1_0.txt or copy at
0006 //  http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 //  The authors gratefully acknowledge the support of
0009 //  Fraunhofer IOSB, Ettlingen, Germany
0010 //
0011
0012 #ifndef BOOST_UBLAS_TENSOR_MULTI_INDEX_UTILITY_HPP
0013 #define BOOST_UBLAS_TENSOR_MULTI_INDEX_UTILITY_HPP
0014
0015
0016 #include <tuple>
0017 #include <type_traits>
0018
0019
0020 namespace boost   {
0021 namespace numeric {
0022 namespace ublas   {
0023 namespace detail  {
0024
0025
0026 template<class ... index_types>
0027 struct has_index_impl;
0028
0029 template<class itype_left, class itype_right>
0030 struct has_index_impl<itype_left, itype_right>
0031 {
0032     static constexpr bool value = itype_left::value == itype_right::value;
0033 };
0034
0035 template<class itype_left>
0036 struct has_index_impl <itype_left, std::tuple<> >
0037 {
0038     static constexpr bool value = false;
0039 };
0040
0041 template<class itype_left, class itype_right>
0042 struct has_index_impl <itype_left, std::tuple<itype_right> >
0043 {
0044     static constexpr bool value = has_index_impl<itype_left,itype_right>::value;
0045 };
0046
0047 template<class itype_left, class itype_right, class ... index_types>
0048 struct has_index_impl <itype_left, std::tuple<itype_right, index_types...> >
0049 {
0050     using next_type = has_index_impl<itype_left, std::tuple<index_types...>>;
0051     static constexpr bool value = has_index_impl<itype_left,itype_right>::value || next_type::value;
0052 };
0053 } // namespace detail
0054
0055
0056
0057 /** @brief has_index is true if index occurs once or more in a multi-index
0058  *
0059  * @note a multi-index represents as tuple of single indexes of type boost::numeric::ublas::index::index_type
0060  *
0061  * @code auto has_index_value = has_index<index_type<1>, std::tuple<index_type<2>,index_type<1>> >::value; @endcode
0062  *
0063  * @tparam index_type type of index
0064  * @tparam tuple_type type of std::tuple representing a multi-index
0065 */
0066 template<class index_type, class tuple_type>
0067 struct has_index
0068 {
0069     static constexpr bool value = detail::has_index_impl<std::decay_t<index_type>,std::decay_t<tuple_type>>::value;
0070 };
0071
0072 } // namespace ublas
0073 } // namespace numeric
0074 } // namespace boost
0075
0076 ////////////////////////////////////////////////
0077 ////////////////////////////////////////////////
0078
0079 namespace boost   {
0080 namespace numeric {
0081 namespace ublas   {
0082 namespace detail  {
0083
0084
0085 template<class ... index_types>
0086 struct valid_multi_index_impl;
0087
0088 template<>
0089 struct valid_multi_index_impl<std::tuple<>>
0090 {
0091     static constexpr bool value = true;
0092 };
0093
0094 template<class itype>
0095 struct valid_multi_index_impl<std::tuple<itype>>
0096 {
0097     static constexpr bool value = true;
0098 };
0099
0100
0101 template<class itype, class ... index_types>
0102 struct valid_multi_index_impl<std::tuple<itype,index_types...>>
0103 {
0104     using ttype     = std::tuple<index_types...>;
0105     using has_index_type = has_index<itype, ttype>;
0106
0107     static constexpr bool is_index_zero   = itype::value==0ul;
0108     static constexpr bool has_index_value = has_index_type::value && !is_index_zero;
0109     static constexpr bool value = !has_index_value && valid_multi_index_impl<ttype>::value;
0110 };
0111 } // namespace detail
0112
0113 /** @brief valid_multi_index is true if indexes occur only once in a multi-index
0114  *
0115  * @note a multi-index represents as tuple of single indexes of type boost::numeric::ublas::index::index_type
0116  *
0117  * @code auto valid = valid_multi_index<  std::tuple<index_type<2>,index_type<1>>  >::value;
0118  * @endcode
0119  *
0120  * @tparam tuple_type type of std::tuple representing a multi-index
0121 */
0122 template<class tupe_type>
0123 struct valid_multi_index
0124 {
0125     static constexpr bool value = detail::valid_multi_index_impl<std::decay_t<tupe_type>>::value;
0126 };
0127
0128 } // namespace ublas
0129 } // namespace numeric
0130 } // namespace boost
0131
0132 ////////////////////////////////////////////////
0133 ////////////////////////////////////////////////
0134
0135 namespace boost   {
0136 namespace numeric {
0137 namespace ublas   {
0138 namespace detail  {
0139
0140 template<class ... index_types >
0141 struct number_equal_indexes_impl;
0142
0143 template<class ... itypes_right >
0144 struct number_equal_indexes_impl < std::tuple<>, std::tuple<itypes_right...>>
0145 {
0146     static constexpr unsigned value  = 0;
0147 };
0148
0149 template<class itype, class ... itypes_left, class ... itypes_right>
0150 struct number_equal_indexes_impl < std::tuple<itype,itypes_left...>, std::tuple<itypes_right...>>
0151 {
0152     using tuple_right = std::tuple<itypes_right...>;
0153     using has_index_type = has_index<itype, tuple_right>;
0154
0155     static constexpr bool is_index_zero   = itype::value==0ul;
0156     static constexpr bool has_index_value = has_index_type::value && !is_index_zero;
0157
0158     using next_type = number_equal_indexes_impl< std::tuple<itypes_left...>, tuple_right >;
0159     static constexpr unsigned v = has_index_value ? 1 : 0;
0160     static constexpr unsigned value  = v + next_type::value;
0161 };
0162 } // namespace detail
0163
0164
0165 /** @brief number_equal_indexes contains the number of equal indexes of two multi-indexes
0166  *
0167  * @note a multi-index represents as tuple of single indexes of type boost::numeric::ublas::index::index_type
0168  *
0169  *
0170  * @code auto num = number_equal_indexes<
0171  *                        std::tuple<index_type<2>,index_type<1>>,
0172  *                        std::tuple<index_type<1>,index_type<3>>  >::value;
0173  * @endcode
0174  *
0175  * @tparam tuple_type_left  type of left std::tuple representing a multi-index
0176  * @tparam tuple_type_right type of right std::tuple representing a multi-index
0177 */
0178 template<class tuple_left, class tuple_right>
0179 struct number_equal_indexes
0180 {
0181     static constexpr unsigned value  =
0182         detail::number_equal_indexes_impl< std::decay_t<tuple_left>, std::decay_t<tuple_right>>::value;
0183 };
0184
0185 } // namespace ublas
0186 } // namespace numeric
0187 } // namespace boost
0188
0189
0190 ////////////////////////////////////////////////
0191 ////////////////////////////////////////////////
0192
0193 namespace boost   {
0194 namespace numeric {
0195 namespace ublas   {
0196 namespace detail  {
0197
0198
0199 template<std::size_t r, std::size_t m, class itype, class ttype>
0200 struct index_position_impl
0201 {
0202     static constexpr auto is_same = std::is_same< std::decay_t<itype>, std::decay_t<std::tuple_element_t<r,ttype>> >::value;
0203     static constexpr auto value   = is_same ? r : index_position_impl<r+1,m,itype,ttype>::value;
0204 };
0205
0206
0207
0208 template<std::size_t m, class itype, class ttype>
0209 struct index_position_impl < m, m, itype, ttype>
0210 {
0211     static constexpr auto value = std::tuple_size<ttype>::value;
0212 };
0213
0214 } // namespace detail
0215
0216
0217
0218 /** @brief index_position contains the zero-based index position of an index type within a multi-index
0219  *
0220  * @note a multi-index represents as tuple of single indexes of type boost::numeric::ublas::index::index_type
0221  *
0222  * @code auto num = index_position<
0223  *                       index_type<1>,
0224  *                       std::tuple<index_type<2>,index_type<1>>  >::value;
0225  * @endcode
0226  *
0227  * @returns value returns 0 and N-1 if index_type is found, N otherwise where N is tuple_size_v<tuple_type>.
0228  *
0229  * @tparam index_type type of index
0230  * @tparam tuple_type type of std::tuple that is searched for index
0231 */
0232 template<class index_type, class tuple_type>
0233 struct index_position
0234 {
0235     static constexpr auto value  = detail::index_position_impl<0ul,std::tuple_size<tuple_type>::value,std::decay_t<index_type>,std::decay_t<tuple_type>>::value;
0236 };
0237
0238 } // namespace ublas
0239 } // namespace numeric
0240 } // namespace boost
0241
0242 ////////////////////////////////////////////////
0243 ////////////////////////////////////////////////
0244
0245
0246 namespace boost   {
0247 namespace numeric {
0248 namespace ublas   {
0249 namespace detail  {
0250
0251 template<std::size_t r, std::size_t m>
0252 struct index_position_pairs_impl
0253 {
0254     template<class array_type, class tuple_left, class tuple_right>
0255     static constexpr void run(array_type& out, tuple_left const& lhs, tuple_right const& rhs, std::size_t p)
0256     {
0257         using index_type     = std::tuple_element_t<r-1,tuple_left>;
0258         using has_index_type = has_index<index_type, tuple_right>;
0259         using get_index_type = index_position<index_type,tuple_right>;
0260         using next_type      = index_position_pairs_impl<r+1,m>;
0261         if constexpr ( has_index_type::value && index_type::value != 0)
0262             out[p++] = std::make_pair(r-1,get_index_type::value);
0263         next_type::run( out, lhs, rhs, p );
0264     }
0265 };
0266
0267 template<std::size_t m>
0268 struct index_position_pairs_impl<m,m>
0269 {
0270     template<class array_type, class tuple_left, class tuple_right>
0271     static constexpr void run(array_type& out, tuple_left const& , tuple_right const& , std::size_t p)
0272     {
0273         using index_type     = std::tuple_element_t<m-1,tuple_left>;
0274         using has_index_type = has_index<index_type, tuple_right>;
0275         using get_index_type = index_position<index_type, tuple_right>;
0276         if constexpr ( has_index_type::value && index_type::value != 0 )
0277             out[p] = std::make_pair(m-1,get_index_type::value);
0278     }
0279 };
0280
0281 template<std::size_t r>
0282 struct index_position_pairs_impl<r,0>
0283 {
0284     template<class array_type, class tuple_left, class tuple_right>
0285     static constexpr void run(array_type&, tuple_left const& , tuple_right const& , std::size_t)
0286     {}
0287 };
0288
0289
0290 } // namespace detail
0291
0292
0293 /** @brief index_position_pairs returns zero-based index positions of matching indexes of two multi-indexes
0294  *
0295  * @note a multi-index represents as tuple of single indexes of type boost::numeric::ublas::index::index_type
0296  *
0297  * @code auto pairs = index_position_pairs(std::make_tuple(_a,_b), std::make_tuple(_b,_c));
0298  * @endcode
0299  *
0300  * @returns a std::array instance containing index position pairs of type std::pair<std::size_t, std::size_t>.
0301  *
0302  * @param lhs left std::tuple instance representing a multi-index
0303  * @param rhs right std::tuple instance representing a multi-index
0304 */
0305 template<class tuple_left, class tuple_right>
0306 auto index_position_pairs(tuple_left const& lhs, tuple_right const& rhs)
0307 {
0308     using pair_type = std::pair<std::size_t,std::size_t>;
0309     constexpr auto m = std::tuple_size<tuple_left >::value;
0310     constexpr auto p = number_equal_indexes<tuple_left, tuple_right>::value;
0311     auto array = std::array<pair_type,p>{};
0312     detail::index_position_pairs_impl<1,m>::run(array, lhs, rhs,0);
0313     return array;
0314 }
0315
0316 } // namespace ublas
0317 } // namespace numeric
0318 } // namespace boost
0319
0320 ////////////////////////////
0321 ////////////////////////////
0322 ////////////////////////////
0323 ////////////////////////////
0324
0325
0326 namespace boost   {
0327 namespace numeric {
0328 namespace ublas   {
0329 namespace detail  {
0330
0331 template<class array_type, std::size_t ... R>
0332 constexpr auto array_to_vector_impl( array_type const& array, std::index_sequence<R...> )
0333 {
0334     return std::make_pair(
0335           std::vector<std::size_t>{std::get<0>( std::get<R>(array) )+1 ...} ,
0336           std::vector<std::size_t>{std::get<1>( std::get<R>(array) )+1 ...} );
0337 }
0338
0339 } // namespace detail
0340
0341
0342 /** @brief array_to_vector converts a std::array of zero-based index position pairs into two std::vector of one-based index positions
0343  *
0344  * @code auto two_vectors = array_to_vector(std::make_array ( std::make_pair(1,2), std::make_pair(3,4) ) ) ;
0345  * @endcode
0346  *
0347  * @returns two std::vector of one-based index positions
0348  *
0349  * @param array std::array of zero-based index position pairs
0350 */
0351 template<class pair_type, std::size_t N>
0352 constexpr auto array_to_vector( std::array<pair_type,N> const& array)
0353 {
0354     constexpr auto sequence = std::make_index_sequence<N>{};
0355     return detail::array_to_vector_impl( array, sequence );
0356 }
0357
0358
0359 } // namespace ublas
0360 } // namespace numeric
0361 } // namespace boost
0362
0363
0364 #endif // _BOOST_UBLAS_TENSOR_MULTI_INDEX_UTILITY_HPP_