1 /// \file 2 // Range v3 library 3 // 4 // Copyright Eric Niebler 2013-2014. 5 // Copyright Casey Carter 2017. 6 // 7 // Use, modification and distribution is subject to the 8 // Boost Software License, Version 1.0. (See accompanying 9 // file LICENSE_1_0.txt or copy at 10 // http://www.boost.org/LICENSE_1_0.txt) 11 // 12 // Project home: https://github.com/ericniebler/range-v3 13 // 14 15 #ifndef RANGES_V3_VIEW_CARTESIAN_PRODUCT_HPP 16 #define RANGES_V3_VIEW_CARTESIAN_PRODUCT_HPP 17 18 #include <cstdint> 19 20 #include <concepts/concepts.hpp> 21 22 #include <range/v3/range_fwd.hpp> 23 24 #include <range/v3/iterator/default_sentinel.hpp> 25 #include <range/v3/iterator/operations.hpp> 26 #include <range/v3/range/access.hpp> 27 #include <range/v3/range/concepts.hpp> 28 #include <range/v3/range/primitives.hpp> 29 #include <range/v3/range/traits.hpp> 30 #include <range/v3/utility/static_const.hpp> 31 #include <range/v3/utility/tuple_algorithm.hpp> 32 #include <range/v3/view/all.hpp> 33 #include <range/v3/view/empty.hpp> 34 #include <range/v3/view/facade.hpp> 35 #include <range/v3/view/view.hpp> // for dereference_fn 36 37 #include <range/v3/detail/prologue.hpp> 38 39 namespace ranges 40 { 41 /// \cond 42 namespace detail 43 { 44 template<typename State, typename Value> 45 using product_cardinality = std::integral_constant< 46 cardinality, 47 State::value == 0 || Value::value == 0 48 ? static_cast<cardinality>(0) 49 : State::value == unknown || Value::value == unknown 50 ? unknown 51 : State::value == infinite || Value::value == infinite 52 ? infinite 53 : State::value == finite || Value::value == finite 54 ? finite 55 : static_cast<cardinality>( 56 State::value * Value::value)>; 57 58 struct cartesian_size_fn 59 { 60 template(typename Size, typename Rng)( 61 /// \pre 62 requires integer_like_<Size> AND sized_range<Rng> AND 63 common_with<Size, range_size_t<Rng>>) operator ()ranges::detail::cartesian_size_fn64 common_type_t<Size, range_size_t<Rng>> operator()(Size s, Rng && rng) const 65 { 66 using S = common_type_t<Size, range_size_t<Rng>>; 67 return static_cast<S>(s) * static_cast<S>(ranges::size(rng)); 68 } 69 }; 70 71 template<typename... Views> 72 using cartesian_product_cardinality = 73 meta::fold<meta::list<range_cardinality<Views>...>, 74 std::integral_constant<cardinality, static_cast<cardinality>( 75 (sizeof...(Views) > 0))>, 76 meta::quote<detail::product_cardinality>>; 77 } // namespace detail 78 /// \endcond 79 80 /// \addtogroup group-views 81 /// @{ 82 83 // clang-format off 84 template<typename...Views> 85 CPP_concept cartesian_produce_view_can_const = 86 and_v<range<Views const>...>; 87 88 template(typename IsConst, typename... Views)( 89 concept (cartesian_produce_view_can_size_)(IsConst, Views...), 90 and_v<common_with<std::uintmax_t, range_size_t<meta::const_if<IsConst, Views>>>...> 91 ); 92 template<typename IsConst, typename...Views> 93 CPP_concept cartesian_produce_view_can_size = 94 and_v<sized_range<meta::const_if<IsConst, Views>>...> && 95 CPP_concept_ref(ranges::cartesian_produce_view_can_size_, IsConst, Views...); 96 97 template(typename IsConst, typename... Views)( 98 concept (cartesian_produce_view_can_distance_)(IsConst, Views...), 99 and_v<sized_sentinel_for< 100 iterator_t<meta::const_if<IsConst, Views>>, 101 iterator_t<meta::const_if<IsConst, Views>>>...> 102 ); 103 template<typename IsConst, typename...Views> 104 CPP_concept cartesian_produce_view_can_distance = 105 cartesian_produce_view_can_size<IsConst, Views...> && 106 CPP_concept_ref(ranges::cartesian_produce_view_can_distance_, IsConst, Views...); 107 108 template(typename IsConst, typename... Views)( 109 concept (cartesian_produce_view_can_random_)(IsConst, Views...), 110 and_v<random_access_iterator<iterator_t<meta::const_if<IsConst, Views>>>...> 111 ); 112 template<typename IsConst, typename...Views> 113 CPP_concept cartesian_produce_view_can_random = 114 cartesian_produce_view_can_distance<IsConst, Views...> && 115 CPP_concept_ref(ranges::cartesian_produce_view_can_random_, IsConst, Views...); 116 117 template(typename IsConst, typename... Views)( 118 concept (cartesian_produce_view_can_bidi_)(IsConst, Views...), 119 and_v<common_range<meta::const_if<IsConst, Views>>..., 120 bidirectional_iterator<iterator_t<meta::const_if<IsConst, Views>>>...> 121 ); 122 template<typename IsConst, typename...Views> 123 CPP_concept cartesian_produce_view_can_bidi = 124 cartesian_produce_view_can_random<IsConst, Views...> || 125 CPP_concept_ref(ranges::cartesian_produce_view_can_bidi_, IsConst, Views...); 126 // clang-format on 127 128 template<typename... Views> 129 struct cartesian_product_view 130 : view_facade<cartesian_product_view<Views...>, 131 detail::cartesian_product_cardinality<Views...>::value> 132 { 133 private: 134 friend range_access; 135 CPP_assert(and_v<(forward_range<Views> && view_<Views>)...>); 136 CPP_assert(sizeof...(Views) != 0); 137 138 static constexpr auto my_cardinality = 139 detail::cartesian_product_cardinality<Views...>::value; 140 141 std::tuple<Views...> views_; 142 143 template<bool IsConst_> 144 struct cursor 145 { 146 private: 147 using IsConst = meta::bool_<IsConst_>; 148 friend cursor<true>; 149 template<typename T> 150 using constify_if = meta::const_if_c<IsConst_, T>; 151 using difference_type = 152 common_type_t<std::intmax_t, range_difference_t<Views>...>; 153 154 constify_if<cartesian_product_view> * view_; 155 std::tuple<iterator_t<constify_if<Views>>...> its_; 156 next_ranges::cartesian_product_view::cursor157 void next_(meta::size_t<1>) 158 { 159 auto & v = std::get<0>(view_->views_); 160 auto & i = std::get<0>(its_); 161 auto const last = ranges::end(v); 162 RANGES_EXPECT(i != last); 163 ++i; 164 } 165 template<std::size_t N> next_ranges::cartesian_product_view::cursor166 void next_(meta::size_t<N>) 167 { 168 auto & v = std::get<N - 1>(view_->views_); 169 auto & i = std::get<N - 1>(its_); 170 auto const last = ranges::end(v); 171 RANGES_EXPECT(i != last); 172 if(++i == last) 173 { 174 i = ranges::begin(v); 175 next_(meta::size_t<N - 1>{}); 176 } 177 } prev_ranges::cartesian_product_view::cursor178 void prev_(meta::size_t<0>) 179 { 180 RANGES_EXPECT(false); 181 } 182 template<std::size_t N> prev_ranges::cartesian_product_view::cursor183 void prev_(meta::size_t<N>) 184 { 185 auto & v = std::get<N - 1>(view_->views_); 186 auto & i = std::get<N - 1>(its_); 187 if(i == ranges::begin(v)) 188 { 189 CPP_assert(cartesian_produce_view_can_bidi<IsConst, Views...>); 190 // cartesian_produce_view_can_bidi<IsConst, Views...> implies this 191 // advance call is O(1) 192 ranges::advance(i, ranges::end(v)); 193 prev_(meta::size_t<N - 1>{}); 194 } 195 --i; 196 } equal_ranges::cartesian_product_view::cursor197 bool equal_(cursor const &, meta::size_t<0>) const 198 { 199 return true; 200 } 201 template<std::size_t N> equal_ranges::cartesian_product_view::cursor202 bool equal_(cursor const & that, meta::size_t<N>) const 203 { 204 return std::get<N - 1>(its_) == std::get<N - 1>(that.its_) && 205 equal_(that, meta::size_t<N - 1>{}); 206 } distance_ranges::cartesian_product_view::cursor207 difference_type distance_(cursor const & that, meta::size_t<1>) const 208 { 209 return difference_type{std::get<0>(that.its_) - std::get<0>(its_)}; 210 } 211 template<std::size_t N> distance_ranges::cartesian_product_view::cursor212 difference_type distance_(cursor const & that, meta::size_t<N>) const 213 { 214 difference_type const d = distance_(that, meta::size_t<N - 1>{}); 215 auto const scale = ranges::distance(std::get<N - 1>(view_->views_)); 216 auto const increment = std::get<N - 1>(that.its_) - std::get<N - 1>(its_); 217 return difference_type{d * scale + increment}; 218 } advance_ranges::cartesian_product_view::cursor219 void advance_(meta::size_t<0>, difference_type) 220 { 221 RANGES_EXPECT(false); 222 } 223 RANGES_DIAGNOSTIC_PUSH 224 RANGES_DIAGNOSTIC_IGNORE_DIVIDE_BY_ZERO 225 template<std::size_t N> advance_ranges::cartesian_product_view::cursor226 void advance_(meta::size_t<N>, difference_type n) 227 { 228 if(n == 0) 229 return; 230 231 auto & i = std::get<N - 1>(its_); 232 auto const my_size = static_cast<difference_type>( 233 ranges::size(std::get<N - 1>(view_->views_))); 234 auto const first = ranges::begin(std::get<N - 1>(view_->views_)); 235 236 auto const idx = static_cast<difference_type>(i - first); 237 RANGES_EXPECT(0 <= idx); 238 RANGES_EXPECT(idx < my_size || (N == 1 && idx == my_size && n < 0)); 239 RANGES_EXPECT(n < INTMAX_MAX - idx); 240 n += idx; 241 242 auto n_div = n / my_size; 243 auto n_mod = n % my_size; 244 245 if(RANGES_CONSTEXPR_IF(N != 1)) 246 { 247 if(n_mod < 0) 248 { 249 n_mod += my_size; 250 --n_div; 251 } 252 advance_(meta::size_t<N - 1>{}, n_div); 253 } 254 RANGES_EXPECT(0 <= n_mod && n_mod < my_size); 255 256 if(RANGES_CONSTEXPR_IF(N == 1)) 257 { 258 if(n_div > 0) 259 { 260 RANGES_EXPECT(n_div == 1); 261 RANGES_EXPECT(n_mod == 0); 262 n_mod = my_size; 263 } 264 else if(n_div < 0) 265 { 266 RANGES_EXPECT(n_div == -1); 267 RANGES_EXPECT(n_mod == 0); 268 } 269 } 270 271 using D = iter_difference_t<decltype(first)>; 272 i = first + static_cast<D>(n_mod); 273 } 274 RANGES_DIAGNOSTIC_POP check_at_end_ranges::cartesian_product_view::cursor275 void check_at_end_(meta::size_t<1>, bool at_end = false) 276 { 277 if(at_end) 278 ranges::advance(std::get<0>(its_), 279 ranges::end(std::get<0>(view_->views_))); 280 } 281 template<std::size_t N> check_at_end_ranges::cartesian_product_view::cursor282 void check_at_end_(meta::size_t<N>, bool at_end = false) 283 { 284 return check_at_end_( 285 meta::size_t<N - 1>{}, 286 at_end || bool(std::get<N - 1>(its_) == 287 ranges::end(std::get<N - 1>(view_->views_)))); 288 } cursorranges::cartesian_product_view::cursor289 cursor(end_tag, constify_if<cartesian_product_view> * view, 290 std::true_type) // common_with 291 : cursor(begin_tag{}, view) 292 { 293 CPP_assert( 294 common_range<meta::at_c<meta::list<constify_if<Views>...>, 0>>); 295 std::get<0>(its_) = ranges::end(std::get<0>(view->views_)); 296 } cursorranges::cartesian_product_view::cursor297 cursor(end_tag, constify_if<cartesian_product_view> * view, 298 std::false_type) // !common_with 299 : cursor(begin_tag{}, view) 300 { 301 using View0 = meta::at_c<meta::list<constify_if<Views>...>, 0>; 302 CPP_assert(!common_range<View0> && random_access_range<View0> && 303 sized_range<View0>); 304 std::get<0>(its_) += ranges::distance(std::get<0>(view->views_)); 305 } 306 307 public: 308 using value_type = std::tuple<range_value_t<Views>...>; 309 310 cursor() = default; cursorranges::cartesian_product_view::cursor311 explicit cursor(begin_tag, constify_if<cartesian_product_view> * view) 312 : view_(view) 313 , its_(tuple_transform(view->views_, ranges::begin)) 314 { 315 // If any of the constituent views is empty, the cartesian_product is 316 // empty and this "begin" iterator needs to become an "end" iterator. 317 check_at_end_(meta::size_t<sizeof...(Views)>{}); 318 } cursorranges::cartesian_product_view::cursor319 explicit cursor(end_tag, constify_if<cartesian_product_view> * view) 320 : cursor( 321 end_tag{}, view, 322 meta::bool_< 323 common_range<meta::at_c<meta::list<constify_if<Views>...>, 0>>>{}) 324 {} 325 template(bool Other)( 326 /// \pre 327 requires IsConst_ AND CPP_NOT(Other)) // cursorranges::cartesian_product_view::cursor328 cursor(cursor<Other> that) 329 : view_(that.view_) 330 , its_(std::move(that.its_)) 331 {} 332 common_tuple<range_reference_t<constify_if<Views>>...> read() const 333 { 334 return tuple_transform(its_, detail::dereference_fn{}); 335 } nextranges::cartesian_product_view::cursor336 void next() 337 { 338 next_(meta::size_t<sizeof...(Views)>{}); 339 } equalranges::cartesian_product_view::cursor340 bool equal(default_sentinel_t) const 341 { 342 return std::get<0>(its_) == ranges::end(std::get<0>(view_->views_)); 343 } equalranges::cartesian_product_view::cursor344 bool equal(cursor const & that) const 345 { 346 return equal_(that, meta::size_t<sizeof...(Views)>{}); 347 } 348 CPP_member prevranges::cartesian_product_view::cursor349 auto prev() -> CPP_ret(void)( 350 /// \pre 351 requires cartesian_produce_view_can_bidi<IsConst, Views...>) 352 { 353 prev_(meta::size_t<sizeof...(Views)>{}); 354 } 355 CPP_auto_member CPP_funranges::cartesian_product_view::cursor356 auto CPP_fun(distance_to)(cursor const & that)( 357 const requires cartesian_produce_view_can_distance<IsConst, Views...>) 358 { 359 return distance_(that, meta::size_t<sizeof...(Views)>{}); 360 } 361 CPP_member advanceranges::cartesian_product_view::cursor362 auto advance(difference_type n) // 363 -> CPP_ret(void)( 364 /// \pre 365 requires cartesian_produce_view_can_random<IsConst, Views...>) 366 { 367 advance_(meta::size_t<sizeof...(Views)>{}, n); 368 } 369 }; begin_cursorranges::cartesian_product_view370 cursor<false> begin_cursor() 371 { 372 return cursor<false>{begin_tag{}, this}; 373 } 374 CPP_member begin_cursorranges::cartesian_product_view375 auto begin_cursor() const // 376 -> CPP_ret(cursor<true>)( 377 /// \pre 378 requires cartesian_produce_view_can_const<Views...>) 379 { 380 return cursor<true>{begin_tag{}, this}; 381 } 382 CPP_member end_cursorranges::cartesian_product_view383 auto end_cursor() // 384 -> CPP_ret(cursor<false>)( 385 /// \pre 386 requires cartesian_produce_view_can_bidi<std::false_type, Views...>) 387 { 388 return cursor<false>{end_tag{}, this}; 389 } 390 CPP_member end_cursorranges::cartesian_product_view391 auto end_cursor() const // 392 -> CPP_ret(cursor<true>)( 393 /// \pre 394 requires cartesian_produce_view_can_bidi<std::true_type, Views...>) 395 { 396 return cursor<true>{end_tag{}, this}; 397 } 398 CPP_member end_cursorranges::cartesian_product_view399 auto end_cursor() const // 400 -> CPP_ret(default_sentinel_t)( 401 /// \pre 402 requires (!cartesian_produce_view_can_bidi<std::true_type, Views...>)) 403 { 404 return {}; 405 } 406 407 public: 408 cartesian_product_view() = default; cartesian_product_viewranges::cartesian_product_view409 constexpr explicit cartesian_product_view(Views... views) 410 : views_{detail::move(views)...} 411 {} 412 template(typename...)( 413 /// \pre 414 requires (my_cardinality >= 0)) // 415 static constexpr std::size_t size() noexcept 416 { 417 return std::size_t{my_cardinality}; 418 } 419 CPP_auto_member 420 auto CPP_fun(size)()(const // 421 requires (my_cardinality < 0) && 422 cartesian_produce_view_can_size<std::true_type, Views...>) 423 { 424 return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{}); 425 } 426 CPP_auto_member 427 auto CPP_fun(size)()( 428 /// \pre 429 requires (my_cardinality < 0) && 430 cartesian_produce_view_can_size<std::false_type, Views...>) 431 { 432 return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{}); 433 } 434 }; 435 436 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17 437 template<typename... Rng> 438 cartesian_product_view(Rng &&...) // 439 -> cartesian_product_view<views::all_t<Rng>...>; 440 #endif 441 442 namespace views 443 { 444 struct cartesian_product_fn 445 { 446 constexpr empty_view<std::tuple<>> operator()() const noexcept 447 { 448 return {}; 449 } 450 template(typename... Rngs)( 451 /// \pre 452 requires (sizeof...(Rngs) != 0) AND 453 concepts::and_v<(forward_range<Rngs> && viewable_range<Rngs>)...>) 454 constexpr cartesian_product_view<all_t<Rngs>...> operator()(Rngs &&... rngs) 455 const 456 { 457 return cartesian_product_view<all_t<Rngs>...>{ 458 all(static_cast<Rngs &&>(rngs))...}; 459 } 460 #if defined(_MSC_VER) 461 template(typename Rng0)( 462 /// \pre 463 requires forward_range<Rng0> AND viewable_range<Rng0>) 464 constexpr cartesian_product_view<all_t<Rng0>> operator()(Rng0 && rng0) const 465 { 466 return cartesian_product_view<all_t<Rng0>>{ 467 all(static_cast<Rng0 &&>(rng0))}; 468 } 469 template(typename Rng0, typename Rng1)( 470 /// \pre 471 requires forward_range<Rng0> AND viewable_range<Rng0> AND 472 forward_range<Rng1> AND viewable_range<Rng1>) 473 constexpr cartesian_product_view<all_t<Rng0>, all_t<Rng1>> // 474 operator()(Rng0 && rng0, Rng1 && rng1) const 475 { 476 return cartesian_product_view<all_t<Rng0>, all_t<Rng1>>{ 477 all(static_cast<Rng0 &&>(rng0)), // 478 all(static_cast<Rng1 &&>(rng1))}; 479 } 480 template(typename Rng0, typename Rng1, typename Rng2)( 481 /// \pre 482 requires forward_range<Rng0> AND viewable_range<Rng0> AND 483 forward_range<Rng1> AND viewable_range<Rng1> AND 484 forward_range<Rng2> AND viewable_range<Rng2>) 485 constexpr cartesian_product_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>> // 486 operator()(Rng0 && rng0, Rng1 && rng1, Rng2 && rng2) const 487 { 488 return cartesian_product_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>>{ 489 all(static_cast<Rng0 &&>(rng0)), // 490 all(static_cast<Rng1 &&>(rng1)), // 491 all(static_cast<Rng2 &&>(rng2))}; 492 } 493 #endif 494 }; 495 496 RANGES_INLINE_VARIABLE(cartesian_product_fn, cartesian_product) 497 } // namespace views 498 499 /// @} 500 } // namespace ranges 501 502 #include <range/v3/detail/epilogue.hpp> 503 504 #endif 505