HiPipe  0.6.0
C++17 data pipeline with Python bindings.
ndim.hpp
1 /****************************************************************************
2  * hipipe library
3  * Copyright (c) 2017, Cognexa Solutions s.r.o.
4  * Copyright (c) 2018, Iterait a.s.
5  * Author(s) Filip Matzner
6  *
7  * This file is distributed under the MIT License.
8  * See the accompanying file LICENSE.txt for the complete license agreement.
9  ****************************************************************************/
11 
12 #pragma once
13 
14 #include <hipipe/core/utility/random.hpp>
15 
16 #include <range/v3/action/reverse.hpp>
17 #include <range/v3/algorithm/adjacent_find.hpp>
18 #include <range/v3/algorithm/all_of.hpp>
19 #include <range/v3/algorithm/fill.hpp>
20 #include <range/v3/algorithm/find.hpp>
21 #include <range/v3/algorithm/max.hpp>
22 #include <range/v3/numeric/accumulate.hpp>
23 #include <range/v3/view/all.hpp>
24 #include <range/v3/view/chunk.hpp>
25 #include <range/v3/view/for_each.hpp>
26 
27 #include <cassert>
28 #include <cmath>
29 #include <functional>
30 #include <memory>
31 #include <random>
32 #include <type_traits>
33 #include <utility>
34 #include <vector>
35 
36 namespace hipipe::utility {
37 
46 template<typename Rng, typename PrevRng = void, bool IsRange = ranges::Range<Rng>()>
47 struct ndims {
48 };
49 
50 template<typename Rng, typename PrevRng>
51 struct ndims<Rng, PrevRng, false> : std::integral_constant<long, 0L> {
52 };
53 
54 template<typename Rng, typename PrevRng>
55 struct ndims<Rng, PrevRng, true>
56  : std::integral_constant<long, ndims<ranges::range_value_type_t<Rng>, Rng>{} + 1> {
57 };
58 
59 // For recursive ranges, such as std::filesystem::path, do not recurse further and
60 // consider it to be a scalar.
61 template<typename Rng>
62 struct ndims<Rng, Rng, true> : std::integral_constant<long, -1L> {
63 };
64 
73 template<typename, template<typename...> typename>
74 struct is_specialization : std::false_type {};
75 
76 template<template<typename...> typename Template, typename... Args>
77 struct is_specialization<Template<Args...>, Template> : std::true_type {};
78 
94 template<typename T, long Dims, template<typename...> typename Container = std::vector>
96  using type = Container<typename ndim_container<T, Dims-1, Container>::type>;
97  static_assert(Dims >= 0, "The number of dimensions has to be non-negative.");
98 };
99 
100 template<typename T, template<typename...> typename Container>
101 struct ndim_container<T, 0, Container> {
102  using type = T;
103 };
104 
105 template<typename T, long Dims, template<typename...> typename Container = std::vector>
106 using ndim_container_t = typename ndim_container<T, Dims, Container>::type;
107 
120 template<typename Rng, long Dim = -1L>
121 struct ndim_type
123  : ndim_type<typename ranges::range_value_type_t<Rng>, Dim - 1L> {
124  static_assert(Dim > 0, "Dimension has to be positive, zero or -1.");
126 };
127 
128 template<typename T>
129 struct ndim_type<T, 0L> {
130  using type = T;
131 };
132 
133 template<typename Rng>
134 struct ndim_type<Rng, -1L>
135  : ndim_type<Rng, ndims<Rng>{}> {
136 };
137 
139 template<typename T, long Dim = -1L>
140 using ndim_type_t = typename ndim_type<T, Dim>::type;
141 
142 // multidimensional range size //
143 
144 namespace detail {
145 
146  template<typename Rng, long Dim, long NDims>
147  struct ndim_size_impl {
148  static void impl(const Rng& rng, std::vector<std::vector<long>>& size_out)
149  {
150  size_out[Dim-1].push_back(ranges::size(rng));
151  for (auto& subrng : rng) {
152  ndim_size_impl<ranges::range_value_type_t<Rng>, Dim+1, NDims>
153  ::impl(subrng, size_out);
154  }
155  }
156  };
157 
158  template<typename Rng, long Dim>
159  struct ndim_size_impl<Rng, Dim, Dim> {
160  static void impl(const Rng& rng, std::vector<std::vector<long>>& size_out)
161  {
162  size_out[Dim-1].push_back(ranges::size(rng));
163  }
164  };
165 
166 } // namespace detail
167 
187 template<long NDims, typename Rng>
188 std::vector<std::vector<long>> ndim_size(const Rng& rng)
189 {
190  static_assert(NDims > 0);
191  std::vector<std::vector<long>> size_out(NDims);
192  detail::ndim_size_impl<Rng, 1, NDims>::impl(rng, size_out);
193  return size_out;
194 }
195 
200 template<typename Rng>
201 std::vector<std::vector<long>> ndim_size(const Rng& rng)
202 {
203  return utility::ndim_size<ndims<Rng>{}>(rng);
204 }
205 
206 // multidimensional range resize //
207 
208 namespace detail {
209 
210  template<long Dim, long NDims>
211  struct ndim_resize_impl {
212  template<typename Rng, typename ValT>
213  static void impl(Rng& vec,
214  const std::vector<std::vector<long>>& vec_size,
215  std::vector<long>& vec_size_idx,
216  const ValT& val)
217  {
218  vec.resize(vec_size[Dim-1][vec_size_idx[Dim-1]++]);
219  for (auto& subvec : vec) {
220  ndim_resize_impl<Dim+1, NDims>::impl(subvec, vec_size, vec_size_idx, val);
221  }
222  }
223  };
224 
225  template<long Dim>
226  struct ndim_resize_impl<Dim, Dim> {
227  template<typename Rng, typename ValT>
228  static void impl(Rng& vec,
229  const std::vector<std::vector<long>>& vec_size,
230  std::vector<long>& vec_size_idx,
231  const ValT& val)
232  {
233  vec.resize(vec_size[Dim-1][vec_size_idx[Dim-1]++], val);
234  }
235  };
236 
237 } // namespace detail
238 
258 template<long NDims, typename Rng, typename ValT = ndim_type_t<Rng, NDims>>
259 Rng& ndim_resize(Rng& vec,
260  const std::vector<std::vector<long>>& vec_size,
261  ValT val = ValT{})
262 {
263  // check that the size is valid
264  assert(vec_size.size() == NDims);
265  static_assert(NDims <= ndims<Rng>{} - ndims<ValT>{});
266  for (std::size_t i = 1; i < vec_size.size(); ++i) {
267  assert(vec_size[i].size() == ranges::accumulate(vec_size[i-1], 0UL));
268  }
269  // build initial indices
270  std::vector<long> vec_size_idx(vec_size.size());
271  // recursively resize
272  detail::ndim_resize_impl<1, NDims>::impl(vec, vec_size, vec_size_idx, val);
273  return vec;
274 }
275 
277 template<typename Rng, typename ValT = ndim_type_t<Rng>>
278 Rng& ndim_resize(Rng& vec,
279  const std::vector<std::vector<long>>& vec_size,
280  ValT val = ValT{})
281 {
282  return ndim_resize<ndims<Rng>{}-ndims<ValT>{}>(vec, vec_size, std::move(val));
283 }
284 
305 template<long NDims, typename Rng, typename ValT = ndim_type_t<Rng, NDims>>
306 Rng& ndim_pad(Rng& vec, ValT val = ValT{})
307 {
308  static_assert(NDims <= ndims<Rng>{} - ndims<ValT>{});
309  std::vector<std::vector<long>> vec_size = ndim_size<NDims>(vec);
310  // replace the sizes in each dimension with the max size in the same dimension
311  for (std::size_t i = 1; i < vec_size.size(); ++i) {
312  long max_size = ranges::max(vec_size[i]);
313  ranges::fill(vec_size[i], max_size);
314  }
315  return utility::ndim_resize<NDims>(vec, vec_size, std::move(val));
316 }
317 
319 template<typename Rng, typename ValT = ndim_type_t<Rng>>
320 Rng& ndim_pad(Rng& vec, ValT val = ValT{})
321 {
322  return utility::ndim_pad<ndims<Rng>{}-ndims<ValT>{}>(vec, std::move(val));
323 }
324 
325 // multidimensional range shape //
326 
327 namespace detail {
328 
329  template<typename Rng, long Dim, long NDims>
330  struct shape_impl {
331  static void impl(const Rng& rng, std::vector<long>& shape)
332  {
333  shape[Dim-1] = ranges::size(rng);
334  if (ranges::size(rng)) {
335  shape_impl<typename ranges::range_value_type_t<Rng>, Dim+1, NDims>
336  ::impl(*ranges::begin(rng), shape);
337  }
338  }
339  };
340 
341  template<typename Rng, long Dim>
342  struct shape_impl<Rng, Dim, Dim> {
343  static void impl(const Rng& rng, std::vector<long>& shape)
344  {
345  shape[Dim-1] = ranges::size(rng);
346  }
347  };
348 
349  // this is just for assertion purposes - check that the entire vector has a rectangular shape
350  template<typename Rng, long NDims>
351  struct check_rectangular_shape {
352  static bool all_same(std::vector<long>& vec)
353  {
354  return ranges::adjacent_find(vec, std::not_equal_to<long>{}) == ranges::end(vec);
355  }
356 
357  static bool impl(const Rng& rng)
358  {
359  std::vector<std::vector<long>> size = utility::ndim_size<NDims>(rng);
360  return ranges::all_of(size, all_same);
361  }
362  };
363 
364 } // namespace detail
365 
383 template<long NDims, typename Rng>
384 std::vector<long> shape(const Rng& rng)
385 {
386  static_assert(NDims > 0);
387  std::vector<long> shape(NDims);
388  // the ndim_size is not used for efficiency in ndebug mode (only the 0-th element is inspected)
389  detail::shape_impl<Rng, 1, NDims>::impl(rng, shape);
390  assert((detail::check_rectangular_shape<Rng, NDims>::impl(rng)));
391  return shape;
392 }
393 
398 template<typename Rng>
399 std::vector<long> shape(const Rng& rng)
400 {
401  return utility::shape<ndims<Rng>{}>(rng);
402 }
403 
404 // recursive range flatten //
405 
406 namespace detail {
407 
408  // recursively join the vector
409  template<long Dim>
410  struct flat_view_impl {
411  static auto impl()
412  {
413  return ranges::view::for_each([](auto& subrng) {
414  return flat_view_impl<Dim-1>::impl()(subrng);
415  });
416  }
417  };
418 
419  // for 0, return the original vector
420  template<>
421  struct flat_view_impl<1> {
422  static auto impl()
423  {
424  return ranges::view::all;
425  }
426  };
427 
428 } // namespace detail
429 
446 template<long NDims, typename Rng>
447 auto flat_view(Rng& rng)
448 {
449  static_assert(NDims > 0);
450  return detail::flat_view_impl<NDims>::impl()(rng);
451 }
452 
454 template<long NDims, typename Rng>
455 auto flat_view(const Rng& rng)
456 {
457  static_assert(NDims > 0);
458  return detail::flat_view_impl<NDims>::impl()(rng);
459 }
460 
462 template<typename Rng>
463 auto flat_view(Rng&& rng)
464 {
465  return utility::flat_view<ndims<Rng>{}>(std::forward<Rng>(rng));
466 }
467 
468 // reshaped view of a multidimensional range //
469 
470 namespace detail {
471 
472  template<long N>
473  struct reshaped_view_impl_go {
474  static auto impl(const std::shared_ptr<std::vector<long>>& shape_ptr)
475  {
476  return ranges::view::chunk((*shape_ptr)[N-2])
477  | ranges::view::transform([shape_ptr](auto subview) {
478  return reshaped_view_impl_go<N-1>::impl(shape_ptr)(std::move(subview));
479  });
480  }
481  };
482 
483  template<>
484  struct reshaped_view_impl_go<1> {
485  static auto impl(const std::shared_ptr<std::vector<long>>&)
486  {
487  return ranges::view::all;
488  }
489  };
490 
491  template<long N, typename Rng>
492  auto reshaped_view_impl(Rng& vec, std::vector<long> shape)
493  {
494  assert(shape.size() == N);
495  auto flat = flat_view(vec);
496 
497  // if -1 present in the shape list, deduce the dimension
498  auto deduced_pos = ranges::find(shape, -1);
499  if (deduced_pos != shape.end()) {
500  auto flat_size = ranges::distance(flat);
501  auto shape_prod = -ranges::accumulate(shape, 1, std::multiplies<>{});
502  assert(flat_size % shape_prod == 0);
503  *deduced_pos = flat_size / shape_prod;
504  }
505 
506  // check that all the requested dimenstions have positive size
507  assert(ranges::all_of(shape, [](long s) { return s > 0; }));
508  // check that the user requests the same number of elements as there really is
509  assert(ranges::distance(flat) == ranges::accumulate(shape, 1, std::multiplies<>{}));
510  // calculate the cummulative product of the shape list in reverse order
511  shape |= ranges::action::reverse;
512  ranges::partial_sum(shape, shape, std::multiplies<>{});
513  // the recursive chunks will share a single copy of the shape list (performance)
514  auto shape_ptr = std::make_shared<std::vector<long>>(std::move(shape));
515  return detail::reshaped_view_impl_go<N>::impl(shape_ptr)(std::move(flat));
516  }
517 
518 } // namespace detail
519 
536 template<long N, typename Rng>
537 auto reshaped_view(Rng& rng, std::vector<long> shape)
538 {
539  return detail::reshaped_view_impl<N, Rng>(rng, std::move(shape));
540 }
541 
543 template<long N, typename Rng>
544 auto reshaped_view(const Rng& rng, std::vector<long> shape)
545 {
546  return detail::reshaped_view_impl<N, const Rng>(rng, std::move(shape));
547 }
548 
549 // generate //
550 
551 namespace detail {
552 
553  template<long Dim, long NDims>
554  struct generate_impl {
555  template<typename Rng, typename Gen>
556  static void impl(Rng& rng, Gen& gen, long gendims)
557  {
558  if (Dim > gendims) {
559  auto val = std::invoke(gen);
560  for (auto& elem : flat_view<NDims-Dim+1>(rng)) elem = val;
561  } else {
562  for (auto& subrng : rng) {
563  detail::generate_impl<Dim+1, NDims>::impl(subrng, gen, gendims);
564  }
565  }
566  }
567  };
568 
569  template<long Dim>
570  struct generate_impl<Dim, Dim> {
571  template<typename Rng, typename Gen>
572  static void impl(Rng& rng, Gen& gen, long gendims)
573  {
574  if (Dim > gendims) ranges::fill(rng, std::invoke(gen));
575  else for (auto& val : rng) val = std::invoke(gen);
576  }
577  };
578 
579 } // namespace detail
580 
624 template<long NDims, typename Rng, typename Gen>
625 void generate(Rng&& rng,
626  Gen&& gen,
627  long gendims = std::numeric_limits<long>::max())
628 {
629  static_assert(NDims > 0);
630  detail::generate_impl<1, NDims>::impl(rng, gen, gendims);
631 }
632 
634 template<typename Rng, typename Gen>
635 void generate(Rng&& rng,
636  Gen&& gen,
637  long gendims = std::numeric_limits<long>::max())
638 {
639  using GenT = std::result_of_t<Gen()>;
640  detail::generate_impl<1, ndims<Rng>{}-ndims<GenT>{}>::impl(rng, gen, gendims);
641 }
642 
675 template<long NDims,
676  typename Rng,
677  typename Prng = std::mt19937&,
678  typename Dist = std::uniform_real_distribution<double>>
679 void random_fill(Rng&& rng,
680  Dist&& dist = Dist{0, 1},
681  Prng&& prng = utility::random_generator,
682  long gendims = std::numeric_limits<long>::max())
683 {
684  auto gen = [&dist, &prng]() { return std::invoke(dist, prng); };
685  utility::generate<NDims>(std::forward<Rng>(rng), std::move(gen), gendims);
686 }
687 
689 template<typename Rng,
690  typename Prng = std::mt19937&,
691  typename Dist = std::uniform_real_distribution<double>>
692 void random_fill(Rng&& rng,
693  Dist&& dist = Dist{0, 1},
694  Prng&& prng = utility::random_generator,
695  long gendims = std::numeric_limits<long>::max())
696 {
697  auto gen = [&dist, &prng]() { return std::invoke(dist, prng); };
698  utility::generate(std::forward<Rng>(rng), std::move(gen), gendims);
699 }
700 
701 namespace detail {
702 
703  struct same_size_impl {
704  template<typename Rng, typename... Rngs>
705  bool operator()(Rng&& rng, Rngs&&... rngs) const
706  {
707  return (... && (ranges::size(rng) == ranges::size(rngs)));
708  }
709 
710  bool operator()() const
711  {
712  return true;
713  }
714  };
715 
716 } // namespace detail
717 
731 template<typename Tuple>
732 bool same_size(Tuple&& rngs)
733 {
734  return std::apply(detail::same_size_impl{}, rngs);
735 }
736 
737 } // namespace hipipe::utility
Detect whether the given type is a specialization of the given container template.
Definition: ndim.hpp:74
auto reshaped_view(Rng &rng, std::vector< long > shape)
Makes a view of a multidimensional range with a specific shape.
Definition: ndim.hpp:537
void generate(Rng &&rng, Gen &&gen, long gendims=std::numeric_limits< long >::max())
Fill a multidimensional range with values generated by a nullary function.
Definition: ndim.hpp:625
auto for_each(from_t< FromColumns... > f, Fun fun, dim_t< Dim > d=dim_t< 1 >{})
Apply a function to a subset of stream columns.
Definition: for_each.hpp:62
Rng & ndim_pad(Rng &vec, ValT val=ValT{})
Pads a mutlidimensional range to a rectangular size.
Definition: ndim.hpp:306
Gets the number of dimensions of a multidimensional range.
Definition: ndim.hpp:47
auto transform(from_t< FromColumns... > f, to_t< ToColumns... > t, Fun fun, dim_t< Dim > d=dim_t< 1 >{})
Transform a subset of hipipe columns to a different subset of hipipe columns.
Definition: transform.hpp:187
Definition: ndim.hpp:144
static thread_local std::mt19937 random_generator
Thread local pseudo-random number generator seeded by std::random_device.
Definition: random.hpp:21
void random_fill(Rng &&rng, Dist &&dist=Dist{0, 1}, Prng &&prng=utility::random_generator, long gendims=std::numeric_limits< long >::max())
Fill a multidimensional range with random values.
Definition: ndim.hpp:679
std::vector< std::vector< long > > ndim_size(const Rng &rng)
Calculates the size of a multidimensional range.
Definition: ndim.hpp:188
Rng & ndim_resize(Rng &vec, const std::vector< std::vector< long >> &vec_size, ValT val=ValT{})
Resizes a multidimensional range to the given size.
Definition: ndim.hpp:259
bool same_size(Tuple &&rngs)
Utility function which checks that all the ranges in a tuple have the same size.
Definition: ndim.hpp:732
auto flat_view(Rng &rng)
Makes a flat view out of a multidimensional range.
Definition: ndim.hpp:447
Fast declaration of a multidimensional container.
Definition: ndim.hpp:95
std::vector< long > shape(const Rng &rng)
Calculates the shape of a multidimensional range.
Definition: ndim.hpp:384