cxtream  0.5.1
C++17 data pipeline with Python bindings.
vector.hpp
1 /****************************************************************************
2  * cxtream library
3  * Copyright (c) 2017, Cognexa Solutions s.r.o.
4  * Author(s) Filip Matzner
5  *
6  * This file is distributed under the MIT License.
7  * See the accompanying file LICENSE.txt for the complete license agreement.
8  ****************************************************************************/
10 
11 #ifndef CXTREAM_CORE_VECTOR_UTILS_HPP
12 #define CXTREAM_CORE_VECTOR_UTILS_HPP
13 
14 #include <cxtream/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 cxtream::utility {
37 
46 template<typename T, bool IsRange = ranges::Range<T>()>
47 struct ndims {
48 };
49 
50 template<typename T>
51 struct ndims<T, false> : std::integral_constant<long, 0L> {
52 };
53 
54 template<typename T>
55 struct ndims<T, true>
56  : std::integral_constant<long, ndims<ranges::range_value_type_t<T>>{} + 1L> {
57 };
58 
74 template<typename T, long Dims, template<typename...> typename Container = std::vector>
76  using type = Container<typename ndim_container<T, Dims-1, Container>::type>;
77  static_assert(Dims >= 0, "The number of dimensions has to be non-negative.");
78 };
79 
80 template<typename T, template<typename...> typename Container>
81 struct ndim_container<T, 0, Container> {
82  using type = T;
83 };
84 
85 template<typename T, long Dims, template<typename...> typename Container = std::vector>
86 using ndim_container_t = typename ndim_container<T, Dims, Container>::type;
87 
100 template<typename Rng, long Dim = -1L>
101 struct ndim_type
103  : ndim_type<typename ranges::range_value_type_t<Rng>, Dim - 1L> {
104  static_assert(Dim > 0, "Dimension has to be positive, zero or -1.");
106 };
107 
108 template<typename T>
109 struct ndim_type<T, 0L> {
110  using type = T;
111 };
112 
113 template<typename Rng>
114 struct ndim_type<Rng, -1L>
115  : ndim_type<Rng, ndims<Rng>{}> {
116 };
117 
119 template<typename T, long Dim = -1L>
120 using ndim_type_t = typename ndim_type<T, Dim>::type;
121 
122 // multidimensional range size //
123 
124 namespace detail {
125 
126  template<typename Rng, long Dim, long NDims>
127  struct ndim_size_impl {
128  static void impl(const Rng& rng, std::vector<std::vector<long>>& size_out)
129  {
130  size_out[Dim-1].push_back(ranges::size(rng));
131  for (auto& subrng : rng) {
132  ndim_size_impl<ranges::range_value_type_t<Rng>, Dim+1, NDims>
133  ::impl(subrng, size_out);
134  }
135  }
136  };
137 
138  template<typename Rng, long Dim>
139  struct ndim_size_impl<Rng, Dim, Dim> {
140  static void impl(const Rng& rng, std::vector<std::vector<long>>& size_out)
141  {
142  size_out[Dim-1].push_back(ranges::size(rng));
143  }
144  };
145 
146 } // namespace detail
147 
167 template<long NDims, typename Rng>
168 std::vector<std::vector<long>> ndim_size(const Rng& rng)
169 {
170  static_assert(NDims > 0);
171  std::vector<std::vector<long>> size_out(NDims);
172  detail::ndim_size_impl<Rng, 1, NDims>::impl(rng, size_out);
173  return size_out;
174 }
175 
180 template<typename Rng>
181 std::vector<std::vector<long>> ndim_size(const Rng& rng)
182 {
183  return utility::ndim_size<ndims<Rng>{}>(rng);
184 }
185 
186 // multidimensional range resize //
187 
188 namespace detail {
189 
190  template<long Dim, long NDims>
191  struct ndim_resize_impl {
192  template<typename Rng, typename ValT>
193  static void impl(Rng& vec,
194  const std::vector<std::vector<long>>& vec_size,
195  std::vector<long>& vec_size_idx,
196  const ValT& val)
197  {
198  vec.resize(vec_size[Dim-1][vec_size_idx[Dim-1]++]);
199  for (auto& subvec : vec) {
200  ndim_resize_impl<Dim+1, NDims>::impl(subvec, vec_size, vec_size_idx, val);
201  }
202  }
203  };
204 
205  template<long Dim>
206  struct ndim_resize_impl<Dim, Dim> {
207  template<typename Rng, typename ValT>
208  static void impl(Rng& vec,
209  const std::vector<std::vector<long>>& vec_size,
210  std::vector<long>& vec_size_idx,
211  const ValT& val)
212  {
213  vec.resize(vec_size[Dim-1][vec_size_idx[Dim-1]++], val);
214  }
215  };
216 
217 } // namespace detail
218 
238 template<long NDims, typename Rng, typename ValT = ndim_type_t<Rng, NDims>>
239 Rng& ndim_resize(Rng& vec,
240  const std::vector<std::vector<long>>& vec_size,
241  ValT val = ValT{})
242 {
243  // check that the size is valid
244  assert(vec_size.size() == NDims);
245  static_assert(NDims <= ndims<Rng>{} - ndims<ValT>{});
246  for (std::size_t i = 1; i < vec_size.size(); ++i) {
247  assert(vec_size[i].size() == ranges::accumulate(vec_size[i-1], 0UL));
248  }
249  // build initial indices
250  std::vector<long> vec_size_idx(vec_size.size());
251  // recursively resize
252  detail::ndim_resize_impl<1, NDims>::impl(vec, vec_size, vec_size_idx, val);
253  return vec;
254 }
255 
257 template<typename Rng, typename ValT = ndim_type_t<Rng>>
258 Rng& ndim_resize(Rng& vec,
259  const std::vector<std::vector<long>>& vec_size,
260  ValT val = ValT{})
261 {
262  return ndim_resize<ndims<Rng>{}-ndims<ValT>{}>(vec, vec_size, std::move(val));
263 }
264 
285 template<long NDims, typename Rng, typename ValT = ndim_type_t<Rng, NDims>>
286 Rng& ndim_pad(Rng& vec, ValT val = ValT{})
287 {
288  static_assert(NDims <= ndims<Rng>{} - ndims<ValT>{});
289  std::vector<std::vector<long>> vec_size = ndim_size<NDims>(vec);
290  // replace the sizes in each dimension with the max size in the same dimension
291  for (std::size_t i = 1; i < vec_size.size(); ++i) {
292  long max_size = ranges::max(vec_size[i]);
293  ranges::fill(vec_size[i], max_size);
294  }
295  return utility::ndim_resize<NDims>(vec, vec_size, std::move(val));
296 }
297 
299 template<typename Rng, typename ValT = ndim_type_t<Rng>>
300 Rng& ndim_pad(Rng& vec, ValT val = ValT{})
301 {
302  return utility::ndim_pad<ndims<Rng>{}-ndims<ValT>{}>(vec, std::move(val));
303 }
304 
305 // multidimensional range shape //
306 
307 namespace detail {
308 
309  template<typename Rng, long Dim, long NDims>
310  struct shape_impl {
311  static void impl(const Rng& rng, std::vector<long>& shape)
312  {
313  shape[Dim-1] = ranges::size(rng);
314  if (ranges::size(rng)) {
315  shape_impl<typename ranges::range_value_type_t<Rng>, Dim+1, NDims>
316  ::impl(*ranges::begin(rng), shape);
317  }
318  }
319  };
320 
321  template<typename Rng, long Dim>
322  struct shape_impl<Rng, Dim, Dim> {
323  static void impl(const Rng& rng, std::vector<long>& shape)
324  {
325  shape[Dim-1] = ranges::size(rng);
326  }
327  };
328 
329  // this is just for assertion purposes - check that the entire vector has a rectangular shape
330  template<typename Rng, long NDims>
331  struct check_rectangular_shape {
332  static bool all_same(std::vector<long>& vec)
333  {
334  return ranges::adjacent_find(vec, std::not_equal_to<long>{}) == ranges::end(vec);
335  }
336 
337  static bool impl(const Rng& rng)
338  {
339  std::vector<std::vector<long>> size = utility::ndim_size<NDims>(rng);
340  return ranges::all_of(size, all_same);
341  }
342  };
343 
344 } // namespace detail
345 
363 template<long NDims, typename Rng>
364 std::vector<long> shape(const Rng& rng)
365 {
366  static_assert(NDims > 0);
367  std::vector<long> shape(NDims);
368  // the ndim_size is not used for efficiency in ndebug mode (only the 0-th element is inspected)
369  detail::shape_impl<Rng, 1, NDims>::impl(rng, shape);
370  assert((detail::check_rectangular_shape<Rng, NDims>::impl(rng)));
371  return shape;
372 }
373 
378 template<typename Rng>
379 std::vector<long> shape(const Rng& rng)
380 {
381  return utility::shape<ndims<Rng>{}>(rng);
382 }
383 
384 // recursive range flatten //
385 
386 namespace detail {
387 
388  // recursively join the vector
389  template<long Dim>
390  struct flat_view_impl {
391  static auto impl()
392  {
393  return ranges::view::for_each([](auto& subrng) {
394  return subrng | flat_view_impl<Dim-1>::impl();
395  });
396  }
397  };
398 
399  // for 0, return the original vector
400  template<>
401  struct flat_view_impl<1> {
402  static auto impl()
403  {
404  return ranges::view::all;
405  }
406  };
407 
408 } // namespace detail
409 
426 template<long NDims, typename Rng>
427 auto flat_view(Rng& rng)
428 {
429  static_assert(NDims > 0);
430  return rng | detail::flat_view_impl<NDims>::impl();
431 }
432 
434 template<long NDims, typename Rng>
435 auto flat_view(const Rng& rng)
436 {
437  static_assert(NDims > 0);
438  return rng | detail::flat_view_impl<NDims>::impl();
439 }
440 
442 template<typename Rng>
443 auto flat_view(Rng&& rng)
444 {
445  return utility::flat_view<ndims<Rng>{}>(std::forward<Rng>(rng));
446 }
447 
448 // reshaped view of a multidimensional range //
449 
450 namespace detail {
451 
452  template<long N>
453  struct reshaped_view_impl_go {
454  static auto impl(const std::shared_ptr<std::vector<long>>& shape_ptr)
455  {
456  return ranges::view::chunk((*shape_ptr)[N-2])
457  | ranges::view::transform([shape_ptr](auto subview) {
458  return std::move(subview) | reshaped_view_impl_go<N-1>::impl(shape_ptr);
459  });
460  }
461  };
462 
463  template<>
464  struct reshaped_view_impl_go<1> {
465  static auto impl(const std::shared_ptr<std::vector<long>>&)
466  {
467  return ranges::view::all;
468  }
469  };
470 
471  template<long N, typename Rng>
472  auto reshaped_view_impl(Rng& vec, std::vector<long> shape)
473  {
474  assert(shape.size() == N);
475  auto flat = flat_view(vec);
476 
477  // if -1 present in the shape list, deduce the dimension
478  auto deduced_pos = ranges::find(shape, -1);
479  if (deduced_pos != shape.end()) {
480  auto flat_size = ranges::distance(flat);
481  auto shape_prod = -ranges::accumulate(shape, 1, std::multiplies<>{});
482  assert(flat_size % shape_prod == 0);
483  *deduced_pos = flat_size / shape_prod;
484  }
485 
486  // check that all the requested dimenstions have positive size
487  assert(ranges::all_of(shape, [](long s) { return s > 0; }));
488  // check that the user requests the same number of elements as there really is
489  assert(ranges::distance(flat) == ranges::accumulate(shape, 1, std::multiplies<>{}));
490  // calculate the cummulative product of the shape list in reverse order
491  shape |= ranges::action::reverse;
492  ranges::partial_sum(shape, shape, std::multiplies<>{});
493  // the recursive chunks will share a single copy of the shape list (performance)
494  auto shape_ptr = std::make_shared<std::vector<long>>(std::move(shape));
495  return std::move(flat) | detail::reshaped_view_impl_go<N>::impl(shape_ptr);
496  }
497 
498 } // namespace detail
499 
516 template<long N, typename Rng>
517 auto reshaped_view(Rng& rng, std::vector<long> shape)
518 {
519  return detail::reshaped_view_impl<N, Rng>(rng, std::move(shape));
520 }
521 
523 template<long N, typename Rng>
524 auto reshaped_view(const Rng& rng, std::vector<long> shape)
525 {
526  return detail::reshaped_view_impl<N, const Rng>(rng, std::move(shape));
527 }
528 
529 // generate //
530 
531 namespace detail {
532 
533  template<long Dim, long NDims>
534  struct generate_impl {
535  template<typename Rng, typename Gen>
536  static void impl(Rng& rng, Gen& gen, long gendims)
537  {
538  if (Dim > gendims) {
539  auto val = std::invoke(gen);
540  for (auto& elem : flat_view<NDims-Dim+1>(rng)) elem = val;
541  } else {
542  for (auto& subrng : rng) {
543  detail::generate_impl<Dim+1, NDims>::impl(subrng, gen, gendims);
544  }
545  }
546  }
547  };
548 
549  template<long Dim>
550  struct generate_impl<Dim, Dim> {
551  template<typename Rng, typename Gen>
552  static void impl(Rng& rng, Gen& gen, long gendims)
553  {
554  if (Dim > gendims) ranges::fill(rng, std::invoke(gen));
555  else for (auto& val : rng) val = std::invoke(gen);
556  }
557  };
558 
559 } // namespace detail
560 
604 template<long NDims, typename Rng, typename Gen>
605 constexpr void generate(Rng&& rng,
606  Gen&& gen,
607  long gendims = std::numeric_limits<long>::max())
608 {
609  static_assert(NDims > 0);
610  detail::generate_impl<1, NDims>::impl(rng, gen, gendims);
611 }
612 
614 template<typename Rng, typename Gen>
615 constexpr void generate(Rng&& rng,
616  Gen&& gen,
617  long gendims = std::numeric_limits<long>::max())
618 {
619  using GenT = std::result_of_t<Gen()>;
620  detail::generate_impl<1, ndims<Rng>{}-ndims<GenT>{}>::impl(rng, gen, gendims);
621 }
622 
655 template<long NDims,
656  typename Rng,
657  typename Prng = std::mt19937&,
658  typename Dist = std::uniform_real_distribution<double>>
659 constexpr void random_fill(Rng&& rng,
660  Dist&& dist = Dist{0, 1},
661  Prng&& prng = utility::random_generator,
662  long gendims = std::numeric_limits<long>::max())
663 {
664  auto gen = [&dist, &prng]() { return std::invoke(dist, prng); };
665  utility::generate<NDims>(std::forward<Rng>(rng), std::move(gen), gendims);
666 }
667 
669 template<typename Rng,
670  typename Prng = std::mt19937&,
671  typename Dist = std::uniform_real_distribution<double>>
672 constexpr void random_fill(Rng&& rng,
673  Dist&& dist = Dist{0, 1},
674  Prng&& prng = utility::random_generator,
675  long gendims = std::numeric_limits<long>::max())
676 {
677  auto gen = [&dist, &prng]() { return std::invoke(dist, prng); };
678  utility::generate(std::forward<Rng>(rng), std::move(gen), gendims);
679 }
680 
681 namespace detail {
682 
683  struct same_size_impl {
684  template<typename Rng, typename... Rngs>
685  constexpr bool operator()(Rng&& rng, Rngs&&... rngs) const
686  {
687  return (... && (ranges::size(rng) == ranges::size(rngs)));
688  }
689 
690  constexpr bool operator()() const
691  {
692  return true;
693  }
694  };
695 
696 } // namespace detail
697 
711 template<typename Tuple>
712 constexpr bool same_size(Tuple&& rngs)
713 {
714  return std::experimental::apply(detail::same_size_impl{}, rngs);
715 }
716 
717 } // namespace cxtream::utility
718 
719 #endif
std::vector< std::vector< long > > ndim_size(const Rng &rng)
Calculates the size of a multidimensional range.
Definition: vector.hpp:168
static thread_local std::mt19937 random_generator
Thread local pseudo-random number generator seeded by std::random_device.
Definition: random.hpp:20
constexpr auto transform(from_t< FromColumns... > f, to_t< ToColumns... > t, Fun fun, dim_t< Dim > d=dim_t< 1 >{})
Transform a subset of cxtream columns to a different subset of cxtream columns.
Definition: transform.hpp:177
constexpr 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:59
constexpr 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: vector.hpp:605
Gets the number of dimensions of a multidimensional range.
Definition: vector.hpp:47
Rng & ndim_pad(Rng &vec, ValT val=ValT{})
Pads a mutlidimensional range to a rectangular size.
Definition: vector.hpp:286
auto flat_view(Rng &rng)
Makes a flat view out of a multidimensional range.
Definition: vector.hpp:427
constexpr 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: vector.hpp:659
constexpr bool same_size(Tuple &&rngs)
Utility function which checks that all the ranges in a tuple have the same size.
Definition: vector.hpp:712
Fast declaration of a multidimensional container.
Definition: vector.hpp:75
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: vector.hpp:239
auto reshaped_view(Rng &rng, std::vector< long > shape)
Makes a view of a multidimensional range with a specific shape.
Definition: vector.hpp:517
std::vector< long > shape(const Rng &rng)
Calculates the shape of a multidimensional range.
Definition: vector.hpp:364