xtensor
 
Loading...
Searching...
No Matches
xsort.hpp
1/***************************************************************************
2 * Copyright (c) Johan Mabille, Sylvain Corlay and Wolf Vollprecht *
3 * Copyright (c) QuantStack *
4 * *
5 * Distributed under the terms of the BSD 3-Clause License. *
6 * *
7 * The full license is in the file LICENSE, distributed with this software. *
8 ****************************************************************************/
9
10#ifndef XTENSOR_SORT_HPP
11#define XTENSOR_SORT_HPP
12
13#include <algorithm>
14#include <cmath>
15#include <iterator>
16#include <utility>
17
18#include <xtl/xcompare.hpp>
19
20#include "../containers/xadapt.hpp"
21#include "../containers/xarray.hpp"
22#include "../containers/xtensor.hpp"
23#include "../core/xeval.hpp"
24#include "../core/xmath.hpp"
25#include "../core/xtensor_config.hpp"
26#include "../core/xtensor_forward.hpp"
27#include "../misc/xmanipulation.hpp"
28#include "../views/xindex_view.hpp"
29#include "../views/xslice.hpp" // for xnone
30#include "../views/xview.hpp"
31
32namespace xt
33{
40
41 namespace detail
42 {
43 template <class T>
44 std::ptrdiff_t adjust_secondary_stride(std::ptrdiff_t stride, T shape)
45 {
46 return stride != 0 ? stride : static_cast<std::ptrdiff_t>(shape);
47 }
48
49 template <class E>
50 inline std::ptrdiff_t get_secondary_stride(const E& ev)
51 {
52 if (ev.layout() == layout_type::row_major)
53 {
54 return adjust_secondary_stride(ev.strides()[ev.dimension() - 2], *(ev.shape().end() - 1));
55 }
56
57 return adjust_secondary_stride(ev.strides()[1], *(ev.shape().begin()));
58 }
59
60 template <class E>
61 inline std::size_t leading_axis_n_iters(const E& ev)
62 {
63 if (ev.layout() == layout_type::row_major)
64 {
65 return std::accumulate(
66 ev.shape().begin(),
67 ev.shape().end() - 1,
68 std::size_t(1),
69 std::multiplies<>()
70 );
71 }
72 return std::accumulate(ev.shape().begin() + 1, ev.shape().end(), std::size_t(1), std::multiplies<>());
73 }
74
75 template <class E, class F>
76 inline void call_over_leading_axis(E& ev, F&& fct)
77 {
78 XTENSOR_ASSERT(ev.dimension() >= 2);
79
80 const std::size_t n_iters = leading_axis_n_iters(ev);
81 const std::ptrdiff_t secondary_stride = get_secondary_stride(ev);
82
83 const auto begin = ev.data();
84 const auto end = begin + n_iters * secondary_stride;
85 for (auto iter = begin; iter != end; iter += secondary_stride)
86 {
87 fct(iter, iter + secondary_stride);
88 }
89 }
90
91 template <class E1, class E2, class F>
92 inline void call_over_leading_axis(E1& e1, E2& e2, F&& fct)
93 {
94 XTENSOR_ASSERT(e1.dimension() >= 2);
95 XTENSOR_ASSERT(e1.dimension() == e2.dimension());
96
97 const std::size_t n_iters = leading_axis_n_iters(e1);
98 const std::ptrdiff_t secondary_stride1 = get_secondary_stride(e1);
99 const std::ptrdiff_t secondary_stride2 = get_secondary_stride(e2);
100 XTENSOR_ASSERT(secondary_stride1 == secondary_stride2);
101
102 const auto begin1 = e1.data();
103 const auto end1 = begin1 + n_iters * secondary_stride1;
104 const auto begin2 = e2.data();
105 const auto end2 = begin2 + n_iters * secondary_stride2;
106 auto iter1 = begin1;
107 auto iter2 = begin2;
108 for (; (iter1 != end1) && (iter2 != end2); iter1 += secondary_stride1, iter2 += secondary_stride2)
109 {
110 fct(iter1, iter1 + secondary_stride1, iter2, iter2 + secondary_stride2);
111 }
112 }
113
114 template <class E>
115 inline std::size_t leading_axis(const E& e)
116 {
117 if (e.layout() == layout_type::row_major)
118 {
119 return e.dimension() - 1;
120 }
121 else if (e.layout() == layout_type::column_major)
122 {
123 return 0;
124 }
125 XTENSOR_THROW(std::runtime_error, "Layout not supported.");
126 }
127
128 // get permutations to transpose and reverse-transpose array
129 inline std::pair<dynamic_shape<std::size_t>, dynamic_shape<std::size_t>>
130 get_permutations(std::size_t dim, std::size_t ax, layout_type layout)
131 {
132 dynamic_shape<std::size_t> permutation(dim);
133 std::iota(permutation.begin(), permutation.end(), std::size_t(0));
134 permutation.erase(permutation.begin() + std::ptrdiff_t(ax));
135
136 if (layout == layout_type::row_major)
137 {
138 permutation.push_back(ax);
139 }
140 else
141 {
142 permutation.insert(permutation.begin(), ax);
143 }
144
145 // TODO find a more clever way to get reverse permutation?
146 dynamic_shape<std::size_t> reverse_permutation;
147 for (std::size_t i = 0; i < dim; ++i)
148 {
149 auto it = std::find(permutation.begin(), permutation.end(), i);
150 reverse_permutation.push_back(std::size_t(std::distance(permutation.begin(), it)));
151 }
152
153 return std::make_pair(std::move(permutation), std::move(reverse_permutation));
154 }
155
156 template <class R, class E, class F>
157 inline R map_axis(const E& e, std::ptrdiff_t axis, F&& lambda)
158 {
159 if (e.dimension() == 1)
160 {
161 R res = e;
162 lambda(res.begin(), res.end());
163 return res;
164 }
165
166 const std::size_t ax = normalize_axis(e.dimension(), axis);
167 if (ax == detail::leading_axis(e))
168 {
169 R res = e;
170 detail::call_over_leading_axis(res, std::forward<F>(lambda));
171 return res;
172 }
173
174 dynamic_shape<std::size_t> permutation, reverse_permutation;
175 std::tie(permutation, reverse_permutation) = get_permutations(e.dimension(), ax, e.layout());
176 R res = transpose(e, permutation);
177 detail::call_over_leading_axis(res, std::forward<F>(lambda));
178 res = transpose(res, reverse_permutation);
179 return res;
180 }
181
182 template <class VT>
183 struct flatten_sort_result_type_impl
184 {
185 using type = VT;
186 };
187
188 template <class VT, std::size_t N, layout_type L>
189 struct flatten_sort_result_type_impl<xtensor<VT, N, L>>
190 {
191 using type = xtensor<VT, 1, L>;
192 };
193
194 template <class VT, class S, layout_type L>
195 struct flatten_sort_result_type_impl<xtensor_fixed<VT, S, L>>
196 {
197 using type = xtensor_fixed<VT, xshape<fixed_compute_size<S>::value>, L>;
198 };
199
200 template <class VT>
201 struct flatten_sort_result_type : flatten_sort_result_type_impl<common_tensor_type_t<VT>>
202 {
203 };
204
205 template <class VT>
206 using flatten_sort_result_type_t = typename flatten_sort_result_type<VT>::type;
207
208 template <class E, class R = flatten_sort_result_type_t<E>>
209 inline auto flat_sort_impl(const xexpression<E>& e)
210 {
211 const auto& de = e.derived_cast();
212 R ev;
213 ev.resize({static_cast<typename R::shape_type::value_type>(de.size())});
214
215 std::copy(de.cbegin(), de.cend(), ev.begin());
216 std::sort(ev.begin(), ev.end());
217
218 return ev;
219 }
220 }
221
222 template <class E>
223 inline auto sort(const xexpression<E>& e, placeholders::xtuph /*t*/)
224 {
225 return detail::flat_sort_impl(e);
226 }
227
228 namespace detail
229 {
230 template <class T>
231 struct sort_eval_type
232 {
233 using type = typename T::temporary_type;
234 };
235
236 template <class T, std::size_t... I, layout_type L>
237 struct sort_eval_type<xtensor_fixed<T, fixed_shape<I...>, L>>
238 {
239 using type = xtensor<T, sizeof...(I), L>;
240 };
241 }
242
254 template <class E>
255 inline auto sort(const xexpression<E>& e, std::ptrdiff_t axis = -1)
256 {
257 using eval_type = typename detail::sort_eval_type<E>::type;
258
259 return detail::map_axis<eval_type>(
260 e.derived_cast(),
261 axis,
262 [](auto begin, auto end)
263 {
264 std::sort(begin, end);
265 }
266 );
267 }
268
269 /*****************************
270 * Implementation of argsort *
271 *****************************/
272
278 enum class sorting_method
279 {
290 };
291
292 namespace detail
293 {
294 template <class ConstRandomIt, class RandomIt, class Compare, class Method>
295 inline void argsort_iter(
296 ConstRandomIt data_begin,
297 ConstRandomIt data_end,
298 RandomIt idx_begin,
299 RandomIt idx_end,
300 Compare comp,
301 Method method
302 )
303 {
304 XTENSOR_ASSERT(std::distance(data_begin, data_end) >= 0);
305 XTENSOR_ASSERT(std::distance(idx_begin, idx_end) == std::distance(data_begin, data_end));
306 (void) idx_end; // TODO(C++17) [[maybe_unused]] only used in assertion.
307
308 std::iota(idx_begin, idx_end, 0);
309 switch (method)
310 {
312 {
313 std::sort(
314 idx_begin,
315 idx_end,
316 [&](const auto i, const auto j)
317 {
318 return comp(*(data_begin + i), *(data_begin + j));
319 }
320 );
321 }
323 {
324 std::stable_sort(
325 idx_begin,
326 idx_end,
327 [&](const auto i, const auto j)
328 {
329 return comp(*(data_begin + i), *(data_begin + j));
330 }
331 );
332 }
333 }
334 }
335
336 template <class ConstRandomIt, class RandomIt, class Method>
337 inline void
338 argsort_iter(ConstRandomIt data_begin, ConstRandomIt data_end, RandomIt idx_begin, RandomIt idx_end, Method method)
339 {
340 return argsort_iter(
341 std::move(data_begin),
342 std::move(data_end),
343 std::move(idx_begin),
344 std::move(idx_end),
345 [](const auto& x, const auto& y) -> bool
346 {
347 return x < y;
348 },
349 method
350 );
351 }
352
353 template <class VT, class T>
354 struct rebind_value_type
355 {
357 };
358
359 template <class VT, class EC, layout_type L>
360 struct rebind_value_type<VT, xarray<EC, L>>
361 {
362 using type = xarray<VT, L>;
363 };
364
365 template <class VT, class EC, std::size_t N, layout_type L>
366 struct rebind_value_type<VT, xtensor<EC, N, L>>
367 {
368 using type = xtensor<VT, N, L>;
369 };
370
371 template <class VT, class ET, class S, layout_type L>
372 struct rebind_value_type<VT, xtensor_fixed<ET, S, L>>
373 {
374 using type = xtensor_fixed<VT, S, L>;
375 };
376
377 template <class VT, class T>
378 struct flatten_rebind_value_type
379 {
380 using type = typename rebind_value_type<VT, T>::type;
381 };
382
383 template <class VT, class EC, std::size_t N, layout_type L>
384 struct flatten_rebind_value_type<VT, xtensor<EC, N, L>>
385 {
386 using type = xtensor<VT, 1, L>;
387 };
388
389 template <class VT, class ET, class S, layout_type L>
390 struct flatten_rebind_value_type<VT, xtensor_fixed<ET, S, L>>
391 {
392 using type = xtensor_fixed<VT, xshape<fixed_compute_size<S>::value>, L>;
393 };
394
395 template <class T>
396 struct argsort_result_type
397 {
398 using type = typename rebind_value_type<typename T::temporary_type::size_type, typename T::temporary_type>::type;
399 };
400
401 template <class T>
402 struct linear_argsort_result_type
403 {
404 using type = typename flatten_rebind_value_type<
405 typename T::temporary_type::size_type,
406 typename T::temporary_type>::type;
407 };
408
409 template <class E, class R = typename detail::linear_argsort_result_type<E>::type, class Method>
410 inline auto flatten_argsort_impl(const xexpression<E>& e, Method method)
411 {
412 const auto& de = e.derived_cast();
413
414 auto cit = de.template begin<layout_type::row_major>();
415 using const_iterator = decltype(cit);
416 auto ad = xiterator_adaptor<const_iterator, const_iterator>(cit, cit, de.size());
417
418 using result_type = R;
419 result_type result;
420 result.resize({de.size()});
421
422 detail::argsort_iter(de.cbegin(), de.cend(), result.begin(), result.end(), method);
423
424 return result;
425 }
426 }
427
428 template <class E>
429 inline auto
431 {
432 return detail::flatten_argsort_impl(e, method);
433 }
434
450 template <class E>
451 inline auto
452 argsort(const xexpression<E>& e, std::ptrdiff_t axis = -1, sorting_method method = sorting_method::quick)
453 {
454 using eval_type = typename detail::sort_eval_type<E>::type;
455 using result_type = typename detail::argsort_result_type<eval_type>::type;
456
457 const auto& de = e.derived_cast();
458
459 std::size_t ax = normalize_axis(de.dimension(), axis);
460
461 if (de.dimension() == 1)
462 {
463 return detail::flatten_argsort_impl<E, result_type>(e, method);
464 }
465
466 const auto argsort = [&method](auto res_begin, auto res_end, auto ev_begin, auto ev_end)
467 {
468 detail::argsort_iter(ev_begin, ev_end, res_begin, res_end, method);
469 };
470
471 if (ax == detail::leading_axis(de))
472 {
473 result_type res = result_type::from_shape(de.shape());
474 detail::call_over_leading_axis(res, de, argsort);
475 return res;
476 }
477
478 dynamic_shape<std::size_t> permutation, reverse_permutation;
479 std::tie(permutation, reverse_permutation) = detail::get_permutations(de.dimension(), ax, de.layout());
480 eval_type ev = transpose(de, permutation);
481 result_type res = result_type::from_shape(ev.shape());
482 detail::call_over_leading_axis(res, ev, argsort);
483 res = transpose(res, reverse_permutation);
484 return res;
485 }
486
487 /************************************************
488 * Implementation of partition and argpartition *
489 ************************************************/
490
491 namespace detail
492 {
504 template <class RandomIt, class Iter, class Compare>
505 inline void
506 partition_iter(RandomIt data_begin, RandomIt data_end, Iter kth_begin, Iter kth_end, Compare comp)
507 {
508 XTENSOR_ASSERT(std::distance(data_begin, data_end) >= 0);
509 XTENSOR_ASSERT(std::distance(kth_begin, kth_end) >= 0);
510
511 using idx_type = typename std::iterator_traits<Iter>::value_type;
512
513 idx_type k_last = static_cast<idx_type>(std::distance(data_begin, data_end));
514 for (; kth_begin != kth_end; ++kth_begin)
515 {
516 std::nth_element(data_begin, data_begin + *kth_begin, data_begin + k_last, std::move(comp));
517 k_last = *kth_begin;
518 }
519 }
520
521 template <class RandomIt, class Iter>
522 inline void partition_iter(RandomIt data_begin, RandomIt data_end, Iter kth_begin, Iter kth_end)
523 {
524 return partition_iter(
525 std::move(data_begin),
526 std::move(data_end),
527 std::move(kth_begin),
528 std::move(kth_end),
529 [](const auto& x, const auto& y) -> bool
530 {
531 return x < y;
532 }
533 );
534 }
535 }
536
564 template <class E, xtl::non_integral_concept C, class R = detail::flatten_sort_result_type_t<E>>
565 inline R partition(const xexpression<E>& e, C kth_container, placeholders::xtuph /*ax*/)
566 {
567 const auto& de = e.derived_cast();
568
569 R ev = R::from_shape({de.size()});
570 std::sort(kth_container.begin(), kth_container.end());
571
572 std::copy(de.linear_cbegin(), de.linear_cend(), ev.linear_begin()); // flatten
573
574 detail::partition_iter(ev.linear_begin(), ev.linear_end(), kth_container.rbegin(), kth_container.rend());
575
576 return ev;
577 }
578
579 template <class E, class I, std::size_t N, class R = detail::flatten_sort_result_type_t<E>>
580 inline R partition(const xexpression<E>& e, const I (&kth_container)[N], placeholders::xtuph tag)
581 {
582 return partition(
583 e,
584 xtl::forward_sequence<std::array<std::size_t, N>, decltype(kth_container)>(kth_container),
585 tag
586 );
587 }
588
589 template <class E, class R = detail::flatten_sort_result_type_t<E>>
590 inline R partition(const xexpression<E>& e, std::size_t kth, placeholders::xtuph tag)
591 {
592 return partition(e, std::array<std::size_t, 1>({kth}), tag);
593 }
594
595 template <class E, xtl::non_integral_concept C>
596 inline auto partition(const xexpression<E>& e, C kth_container, std::ptrdiff_t axis = -1)
597 {
598 using eval_type = typename detail::sort_eval_type<E>::type;
599
600 std::sort(kth_container.begin(), kth_container.end());
601
602 return detail::map_axis<eval_type>(
603 e.derived_cast(),
604 axis,
605 [&kth_container](auto begin, auto end)
606 {
607 detail::partition_iter(begin, end, kth_container.rbegin(), kth_container.rend());
608 }
609 );
610 }
611
612 template <class E, class T, std::size_t N>
613 inline auto partition(const xexpression<E>& e, const T (&kth_container)[N], std::ptrdiff_t axis = -1)
614 {
615 return partition(
616 e,
617 xtl::forward_sequence<std::array<std::size_t, N>, decltype(kth_container)>(kth_container),
618 axis
619 );
620 }
621
622 template <class E>
623 inline auto partition(const xexpression<E>& e, std::size_t kth, std::ptrdiff_t axis = -1)
624 {
625 return partition(e, std::array<std::size_t, 1>({kth}), axis);
626 }
627
655 template <
656 class E,
657 xtl::non_integral_concept C,
658 class R = typename detail::linear_argsort_result_type<typename detail::sort_eval_type<E>::type>::type>
659 inline R argpartition(const xexpression<E>& e, C kth_container, placeholders::xtuph)
660 {
661 using eval_type = typename detail::sort_eval_type<E>::type;
662 using result_type = typename detail::linear_argsort_result_type<eval_type>::type;
663
664 const auto& de = e.derived_cast();
665
666 result_type res = result_type::from_shape({de.size()});
667
668 std::sort(kth_container.begin(), kth_container.end());
669
670 std::iota(res.linear_begin(), res.linear_end(), 0);
671
672 detail::partition_iter(
673 res.linear_begin(),
674 res.linear_end(),
675 kth_container.rbegin(),
676 kth_container.rend(),
677 [&de](std::size_t a, std::size_t b)
678 {
679 return de[a] < de[b];
680 }
681 );
682
683 return res;
684 }
685
686 template <class E, class I, std::size_t N>
687 inline auto argpartition(const xexpression<E>& e, const I (&kth_container)[N], placeholders::xtuph tag)
688 {
689 return argpartition(
690 e,
691 xtl::forward_sequence<std::array<std::size_t, N>, decltype(kth_container)>(kth_container),
692 tag
693 );
694 }
695
696 template <class E>
697 inline auto argpartition(const xexpression<E>& e, std::size_t kth, placeholders::xtuph tag)
698 {
699 return argpartition(e, std::array<std::size_t, 1>({kth}), tag);
700 }
701
702 template <class E, xtl::non_integral_concept C>
703 inline auto argpartition(const xexpression<E>& e, C kth_container, std::ptrdiff_t axis = -1)
704 {
705 using eval_type = typename detail::sort_eval_type<E>::type;
706 using result_type = typename detail::argsort_result_type<eval_type>::type;
707
708 const auto& de = e.derived_cast();
709
710 if (de.dimension() == 1)
711 {
712 return argpartition<E, C, result_type>(e, std::forward<C>(kth_container), xnone());
713 }
714
715 std::sort(kth_container.begin(), kth_container.end());
716 const auto argpartition_w_kth =
717 [&kth_container](auto res_begin, auto res_end, auto ev_begin, auto /*ev_end*/)
718 {
719 std::iota(res_begin, res_end, 0);
720 detail::partition_iter(
721 res_begin,
722 res_end,
723 kth_container.rbegin(),
724 kth_container.rend(),
725 [&ev_begin](auto const& i, auto const& j)
726 {
727 return *(ev_begin + i) < *(ev_begin + j);
728 }
729 );
730 };
731
732 const std::size_t ax = normalize_axis(de.dimension(), axis);
733 if (ax == detail::leading_axis(de))
734 {
735 result_type res = result_type::from_shape(de.shape());
736 detail::call_over_leading_axis(res, de, argpartition_w_kth);
737 return res;
738 }
739
740 dynamic_shape<std::size_t> permutation, reverse_permutation;
741 std::tie(permutation, reverse_permutation) = detail::get_permutations(de.dimension(), ax, de.layout());
742 eval_type ev = transpose(de, permutation);
743 result_type res = result_type::from_shape(ev.shape());
744 detail::call_over_leading_axis(res, ev, argpartition_w_kth);
745 res = transpose(res, reverse_permutation);
746 return res;
747 }
748
749 template <class E, class I, std::size_t N>
750 inline auto argpartition(const xexpression<E>& e, const I (&kth_container)[N], std::ptrdiff_t axis = -1)
751 {
752 return argpartition(
753 e,
754 xtl::forward_sequence<std::array<std::size_t, N>, decltype(kth_container)>(kth_container),
755 axis
756 );
757 }
758
759 template <class E>
760 inline auto argpartition(const xexpression<E>& e, std::size_t kth, std::ptrdiff_t axis = -1)
761 {
762 return argpartition(e, std::array<std::size_t, 1>({kth}), axis);
763 }
764
765 /******************
766 * xt::quantile *
767 ******************/
768
769 namespace detail
770 {
771 template <class S, class I, class K, class O>
772 inline void select_indices_impl(
773 const S& shape,
774 const I& indices,
775 std::size_t axis,
776 std::size_t current_dim,
777 const K& current_index,
778 O& out
779 )
780 {
781 using id_t = typename K::value_type;
782 if ((current_dim < shape.size() - 1) && (current_dim == axis))
783 {
784 for (auto i : indices)
785 {
786 auto idx = current_index;
787 idx[current_dim] = i;
788 select_indices_impl(shape, indices, axis, current_dim + 1, idx, out);
789 }
790 }
791 else if ((current_dim < shape.size() - 1) && (current_dim != axis))
792 {
793 for (id_t i = 0; xtl::cmp_less(i, shape[current_dim]); ++i)
794 {
795 auto idx = current_index;
796 idx[current_dim] = i;
797 select_indices_impl(shape, indices, axis, current_dim + 1, idx, out);
798 }
799 }
800 else if ((current_dim == shape.size() - 1) && (current_dim == axis))
801 {
802 for (auto i : indices)
803 {
804 auto idx = current_index;
805 idx[current_dim] = i;
806 out.push_back(std::move(idx));
807 }
808 }
809 else if ((current_dim == shape.size() - 1) && (current_dim != axis))
810 {
811 for (id_t i = 0; xtl::cmp_less(i, shape[current_dim]); ++i)
812 {
813 auto idx = current_index;
814 idx[current_dim] = i;
815 out.push_back(std::move(idx));
816 }
817 }
818 }
819
820 template <class S, class I>
821 inline auto select_indices(const S& shape, const I& indices, std::size_t axis)
822 {
823 using index_type = get_strides_t<S>;
824 auto out = std::vector<index_type>();
825 select_indices_impl(shape, indices, axis, 0, xtl::make_sequence<index_type>(shape.size()), out);
826 return out;
827 }
828
829 // TODO remove when fancy index views are implemented
830 // Poor man's indexing along a single axis as in NumPy a[:, [1, 3, 4]]
831 template <class E, class I>
832 inline auto fancy_indexing(E&& e, const I& indices, std::ptrdiff_t axis)
833 {
834 const std::size_t ax = normalize_axis(e.dimension(), axis);
835 using shape_t = get_strides_t<typename std::decay_t<E>::shape_type>;
836 auto shape = xtl::forward_sequence<shape_t, decltype(e.shape())>(e.shape());
837 shape[ax] = indices.size();
838 return reshape_view(
839 index_view(std::forward<E>(e), select_indices(e.shape(), indices, ax)),
840 std::move(shape)
841 );
842 }
843
844 template <class T, class I, class P>
845 inline auto quantile_kth_gamma(std::size_t n, const P& probas, T alpha, T beta)
846 {
847 const auto m = alpha + probas * (T(1) - alpha - beta);
848 // Evaluting since reused a lot
849 const auto p_n_m = eval(probas * static_cast<T>(n) + m - 1);
850 // Previous (virtual) index, may be out of bounds
851 const auto j = floor(p_n_m);
852 const auto j_jp1 = concatenate(xtuple(j, j + 1));
853 // Both interpolation indices, k and k+1
854 const auto k_kp1 = xt::cast<std::size_t>(clip(j_jp1, T(0), T(n - 1)));
855 // Both interpolation coefficients, 1-gamma and gamma
856 const auto omg_g = concatenate(xtuple(T(1) - (p_n_m - j), p_n_m - j));
857 return std::make_pair(eval(k_kp1), eval(omg_g));
858 }
859
860 // TODO should implement unsqueeze rather
861 template <class S>
862 inline auto unsqueeze_shape(const S& shape, std::size_t axis)
863 {
864 XTENSOR_ASSERT(axis <= shape.size());
865 auto new_shape = xtl::forward_sequence<xt::svector<std::size_t>, decltype(shape)>(shape);
866 new_shape.insert(new_shape.begin() + axis, 1);
867 return new_shape;
868 }
869 }
870
900 template <class T = double, class E, class P>
901 inline auto quantile(E&& e, const P& probas, std::ptrdiff_t axis, T alpha, T beta)
902 {
903 XTENSOR_ASSERT(all(0. <= probas));
904 XTENSOR_ASSERT(all(probas <= 1.));
905 XTENSOR_ASSERT(0. <= alpha);
906 XTENSOR_ASSERT(alpha <= 1.);
907 XTENSOR_ASSERT(0. <= beta);
908 XTENSOR_ASSERT(beta <= 1.);
909
910 using tmp_shape_t = get_strides_t<typename std::decay_t<E>::shape_type>;
911 using id_t = typename tmp_shape_t::value_type;
912
913 const std::size_t ax = normalize_axis(e.dimension(), axis);
914 const std::size_t n = e.shape()[ax];
915 auto kth_gamma = detail::quantile_kth_gamma<T, id_t, P>(n, probas, alpha, beta);
916
917 // Select relevant values for computing interpolating quantiles
918 auto e_partition = xt::partition(std::forward<E>(e), kth_gamma.first, ax);
919 auto e_kth = detail::fancy_indexing(std::move(e_partition), std::move(kth_gamma.first), ax);
920
921 // Reshape interpolation coefficients
922 auto gm1_g_shape = xtl::make_sequence<tmp_shape_t>(e.dimension(), 1);
923 gm1_g_shape[ax] = kth_gamma.second.size();
924 auto gm1_g_reshaped = reshape_view(std::move(kth_gamma.second), std::move(gm1_g_shape));
925
926 // Compute interpolation
927 // TODO(C++20) use (and create) xt::lerp in C++
928 auto e_kth_g = std::move(e_kth) * std::move(gm1_g_reshaped);
929 // Reshape pairwise interpolate for suming along new axis
930 auto e_kth_g_shape = detail::unsqueeze_shape(e_kth_g.shape(), ax);
931 e_kth_g_shape[ax] = 2;
932 e_kth_g_shape[ax + 1] /= 2;
933 auto quantiles = xt::sum(reshape_view(std::move(e_kth_g), std::move(e_kth_g_shape)), ax);
934 // Cannot do a transpose on a non-strided expression so we have to eval
935 return moveaxis(eval(std::move(quantiles)), ax, 0);
936 }
937
938 // Static proba array overload
939 template <class T = double, class E, std::size_t N>
940 inline auto quantile(E&& e, const T (&probas)[N], std::ptrdiff_t axis, T alpha, T beta)
941 {
942 return quantile(std::forward<E>(e), adapt(probas, {N}), axis, alpha, beta);
943 }
944
954 template <class T = double, class E, class P>
955 inline auto quantile(E&& e, const P& probas, T alpha, T beta)
956 {
957 return quantile(xt::ravel(std::forward<E>(e)), probas, 0, alpha, beta);
958 }
959
960 // Static proba array overload
961 template <class T = double, class E, std::size_t N>
962 inline auto quantile(E&& e, const T (&probas)[N], T alpha, T beta)
963 {
964 return quantile(std::forward<E>(e), adapt(probas, {N}), alpha, beta);
965 }
966
993
1003 template <class T = double, class E, class P>
1004 inline auto
1005 quantile(E&& e, const P& probas, std::ptrdiff_t axis, quantile_method method = quantile_method::linear)
1006 {
1007 T alpha = 0.;
1008 T beta = 0.;
1009 switch (method)
1010 {
1012 {
1013 alpha = 0.;
1014 beta = 1.;
1015 break;
1016 }
1018 {
1019 alpha = 0.5;
1020 beta = 0.5;
1021 break;
1022 }
1024 {
1025 alpha = 0.;
1026 beta = 0.;
1027 break;
1028 }
1030 {
1031 alpha = 1.;
1032 beta = 1.;
1033 break;
1034 }
1036 {
1037 alpha = 1. / 3.;
1038 beta = 1. / 3.;
1039 break;
1040 }
1042 {
1043 alpha = 3. / 8.;
1044 beta = 3. / 8.;
1045 break;
1046 }
1047 }
1048 return quantile(std::forward<E>(e), probas, axis, alpha, beta);
1049 }
1050
1051 // Static proba array overload
1052 template <class T = double, class E, std::size_t N>
1053 inline auto
1054 quantile(E&& e, const T (&probas)[N], std::ptrdiff_t axis, quantile_method method = quantile_method::linear)
1055 {
1056 return quantile(std::forward<E>(e), adapt(probas, {N}), axis, method);
1057 }
1058
1070 template <class T = double, class E, class P>
1071 inline auto quantile(E&& e, const P& probas, quantile_method method = quantile_method::linear)
1072 {
1073 return quantile(xt::ravel(std::forward<E>(e)), probas, 0, method);
1074 }
1075
1076 // Static proba array overload
1077 template <class T = double, class E, std::size_t N>
1078 inline auto quantile(E&& e, const T (&probas)[N], quantile_method method = quantile_method::linear)
1079 {
1080 return quantile(std::forward<E>(e), adapt(probas, {N}), method);
1081 }
1082
1083 /****************
1084 * xt::median *
1085 ****************/
1086
1087 template <class E>
1088 inline typename std::decay_t<E>::value_type median(E&& e)
1089 {
1090 using value_type = typename std::decay_t<E>::value_type;
1091 auto sz = e.size();
1092 if (sz % 2 == 0)
1093 {
1094 std::size_t szh = sz / 2; // integer floor div
1095 std::array<std::size_t, 2> kth = {szh - 1, szh};
1096 auto values = xt::partition(xt::flatten(e), kth);
1097 return (values[kth[0]] + values[kth[1]]) / value_type(2);
1098 }
1099 else
1100 {
1101 std::array<std::size_t, 1> kth = {(sz - 1) / 2};
1102 auto values = xt::partition(xt::flatten(e), kth);
1103 return values[kth[0]];
1104 }
1105 }
1106
1120 template <class E>
1121 inline auto median(E&& e, std::ptrdiff_t axis)
1122 {
1123 std::size_t ax = normalize_axis(e.dimension(), axis);
1124 std::size_t sz = e.shape()[ax];
1125 xstrided_slice_vector sv(e.dimension(), xt::all());
1126
1127 if (sz % 2 == 0)
1128 {
1129 std::size_t szh = sz / 2; // integer floor div
1130 std::array<std::size_t, 2> kth = {szh - 1, szh};
1131 auto values = xt::partition(std::forward<E>(e), kth, static_cast<ptrdiff_t>(ax));
1132 sv[ax] = xt::range(szh - 1, szh + 1);
1133 return xt::mean(xt::strided_view(std::move(values), std::move(sv)), {ax});
1134 }
1135 else
1136 {
1137 std::size_t szh = (sz - 1) / 2;
1138 std::array<std::size_t, 1> kth = {(sz - 1) / 2};
1139 auto values = xt::partition(std::forward<E>(e), kth, static_cast<ptrdiff_t>(ax));
1140 sv[ax] = xt::range(szh, szh + 1);
1141 return xt::mean(xt::strided_view(std::move(values), std::move(sv)), {ax});
1142 }
1143 }
1144
1145 namespace detail
1146 {
1147 template <class T>
1148 struct argfunc_result_type
1149 {
1150 using type = xarray<std::size_t>;
1151 };
1152
1153 template <class T, std::size_t N>
1154 struct argfunc_result_type<xtensor<T, N>>
1155 {
1156 using type = xtensor<std::size_t, N - 1>;
1157 };
1158
1159 template <layout_type L, class E, class F>
1160 inline typename argfunc_result_type<E>::type arg_func_impl(const E& e, std::size_t axis, F&& cmp)
1161 {
1162 using eval_type = typename detail::sort_eval_type<E>::type;
1163 using value_type = typename E::value_type;
1164 using result_type = typename argfunc_result_type<E>::type;
1165 using result_shape_type = typename result_type::shape_type;
1166
1167 if (e.dimension() == 1)
1168 {
1169 auto begin = e.template begin<L>();
1170 auto end = e.template end<L>();
1171 // todo C++17 : constexpr
1172 if (std::is_same<F, std::less<value_type>>::value)
1173 {
1174 std::size_t i = static_cast<std::size_t>(std::distance(begin, std::min_element(begin, end)));
1175 return xtensor<size_t, 0>{i};
1176 }
1177 else
1178 {
1179 std::size_t i = static_cast<std::size_t>(std::distance(begin, std::max_element(begin, end)));
1180 return xtensor<size_t, 0>{i};
1181 }
1182 }
1183
1184 result_shape_type alt_shape;
1185 xt::resize_container(alt_shape, e.dimension() - 1);
1186
1187 // Excluding copy, copy all of shape except for axis
1188 std::copy(e.shape().cbegin(), e.shape().cbegin() + std::ptrdiff_t(axis), alt_shape.begin());
1189 std::copy(
1190 e.shape().cbegin() + std::ptrdiff_t(axis) + 1,
1191 e.shape().cend(),
1192 alt_shape.begin() + std::ptrdiff_t(axis)
1193 );
1194
1195 result_type result = result_type::from_shape(std::move(alt_shape));
1196 auto result_iter = result.template begin<L>();
1197
1198 auto arg_func_lambda = [&result_iter, &cmp](auto begin, auto end)
1199 {
1200 std::size_t idx = 0;
1201 value_type val = *begin;
1202 ++begin;
1203 for (std::size_t i = 1; begin != end; ++begin, ++i)
1204 {
1205 if (cmp(*begin, val))
1206 {
1207 val = *begin;
1208 idx = i;
1209 }
1210 }
1211 *result_iter = idx;
1212 ++result_iter;
1213 };
1214
1215 if (axis != detail::leading_axis(e))
1216 {
1217 dynamic_shape<std::size_t> permutation, reverse_permutation;
1218 std::tie(
1219 permutation,
1220 reverse_permutation
1221 ) = detail::get_permutations(e.dimension(), axis, e.layout());
1222
1223 // note: creating copy
1224 eval_type input = transpose(e, permutation);
1225 detail::call_over_leading_axis(input, arg_func_lambda);
1226 return result;
1227 }
1228 else
1229 {
1230 auto&& input = eval(e);
1231 detail::call_over_leading_axis(input, arg_func_lambda);
1232 return result;
1233 }
1234 }
1235 }
1236
1237 template <layout_type L = XTENSOR_DEFAULT_TRAVERSAL, class E>
1238 inline auto argmin(const xexpression<E>& e)
1239 {
1240 using value_type = typename E::value_type;
1241 auto&& ed = eval(e.derived_cast());
1242 auto begin = ed.template begin<L>();
1243 auto end = ed.template end<L>();
1244 std::size_t i = static_cast<std::size_t>(std::distance(begin, std::min_element(begin, end)));
1245 return xtensor<size_t, 0>{i};
1246 }
1247
1258 template <layout_type L = XTENSOR_DEFAULT_TRAVERSAL, class E>
1259 inline auto argmin(const xexpression<E>& e, std::ptrdiff_t axis)
1260 {
1261 using value_type = typename E::value_type;
1262 auto&& ed = eval(e.derived_cast());
1263 std::size_t ax = normalize_axis(ed.dimension(), axis);
1264 return detail::arg_func_impl<L>(ed, ax, std::less<value_type>());
1265 }
1266
1267 template <layout_type L = XTENSOR_DEFAULT_TRAVERSAL, class E>
1268 inline auto argmax(const xexpression<E>& e)
1269 {
1270 using value_type = typename E::value_type;
1271 auto&& ed = eval(e.derived_cast());
1272 auto begin = ed.template begin<L>();
1273 auto end = ed.template end<L>();
1274 std::size_t i = static_cast<std::size_t>(std::distance(begin, std::max_element(begin, end)));
1275 return xtensor<size_t, 0>{i};
1276 }
1277
1289 template <layout_type L = XTENSOR_DEFAULT_TRAVERSAL, class E>
1290 inline auto argmax(const xexpression<E>& e, std::ptrdiff_t axis)
1291 {
1292 using value_type = typename E::value_type;
1293 auto&& ed = eval(e.derived_cast());
1294 std::size_t ax = normalize_axis(ed.dimension(), axis);
1295 return detail::arg_func_impl<L>(ed, ax, std::greater<value_type>());
1296 }
1297
1305 template <class E>
1306 inline auto unique(const xexpression<E>& e)
1307 {
1308 auto sorted = sort(e, xnone());
1309 auto end = std::unique(sorted.begin(), sorted.end());
1310 std::size_t sz = static_cast<std::size_t>(std::distance(sorted.begin(), end));
1311 // TODO check if we can shrink the vector without reallocation
1312 using value_type = typename E::value_type;
1313 auto result = xtensor<value_type, 1>::from_shape({sz});
1314 std::copy(sorted.begin(), end, result.begin());
1315 return result;
1316 }
1317
1326 template <class E1, class E2>
1327 inline auto setdiff1d(const xexpression<E1>& ar1, const xexpression<E2>& ar2)
1328 {
1329 using value_type = typename E1::value_type;
1330
1331 auto unique1 = unique(ar1);
1332 auto unique2 = unique(ar2);
1333
1334 auto tmp = xtensor<value_type, 1>::from_shape({unique1.size()});
1335
1336 auto end = std::set_difference(unique1.begin(), unique1.end(), unique2.begin(), unique2.end(), tmp.begin());
1337
1338 std::size_t sz = static_cast<std::size_t>(std::distance(tmp.begin(), end));
1339
1340 auto result = xtensor<value_type, 1>::from_shape({sz});
1341
1342 std::copy(tmp.begin(), end, result.begin());
1343
1344 return result;
1345 }
1346}
1347
1348#endif
Base class for xexpressions.
derived_type & derived_cast() &noexcept
Returns a reference to the actual derived type of the xexpression.
auto clip(E1 &&e1, E2 &&lo, E3 &&hi) noexcept -> detail::xfunction_type_t< math::clamp_fun, E1, E2, E3 >
Clip values between hi and lo.
Definition xmath.hpp:815
auto cast(E &&e) noexcept -> detail::xfunction_type_t< typename detail::cast< R >::functor, E >
Element-wise static_cast.
bool all(E &&e)
Any.
auto floor(E &&e) noexcept -> detail::xfunction_type_t< math::floor_fun, E >
floor function.
Definition xmath.hpp:1589
auto sum(E &&e, X &&axes, EVS es=EVS())
Sum of elements over given axes.
Definition xmath.hpp:1838
auto mean(E &&e, X &&axes, EVS es=EVS())
Mean of elements over given axes.
Definition xmath.hpp:1932
auto adapt(C &&container, const SC &shape, layout_type l=L)
Constructs:
auto eval(T &&t) -> std::enable_if_t< detail::is_container< std::decay_t< T > >::value, T && >
Force evaluation of xexpression.
Definition xeval.hpp:46
auto flatten(E &&e)
Return a flatten view of the given expression.
auto moveaxis(E &&e, std::ptrdiff_t src, std::ptrdiff_t dest)
Return a new expression with an axis move to a new position.
auto ravel(E &&e)
Return a flatten view of the given expression.
auto transpose(E &&e) noexcept
Returns a transpose view by reversing the dimensions of xexpression e.
quantile_method
Quantile interpolation method.
Definition xsort.hpp:979
auto unique(const xexpression< E > &e)
Find unique elements of a xexpression.
Definition xsort.hpp:1306
R partition(const xexpression< E > &e, C kth_container, placeholders::xtuph)
Partially sort xexpression.
Definition xsort.hpp:565
auto quantile(E &&e, const P &probas, std::ptrdiff_t axis, T alpha, T beta)
Compute quantiles over the given axis.
Definition xsort.hpp:901
auto setdiff1d(const xexpression< E1 > &ar1, const xexpression< E2 > &ar2)
Find the set difference of two xexpressions.
Definition xsort.hpp:1327
R argpartition(const xexpression< E > &e, C kth_container, placeholders::xtuph)
Partially sort arguments.
Definition xsort.hpp:659
@ weibull
Method 6 of (Hyndman and Fan, 1996) with alpha=0 and beta=0.
Definition xsort.hpp:985
@ interpolated_inverted_cdf
Method 4 of (Hyndman and Fan, 1996) with alpha=0 and beta=1.
Definition xsort.hpp:981
@ linear
Method 7 of (Hyndman and Fan, 1996) with alpha=1 and beta=1.
Definition xsort.hpp:987
@ normal_unbiased
Method 9 of (Hyndman and Fan, 1996) with alpha=3/8 and beta=3/8.
Definition xsort.hpp:991
@ median_unbiased
Method 8 of (Hyndman and Fan, 1996) with alpha=1/3 and beta=1/3.
Definition xsort.hpp:989
@ hazen
Method 5 of (Hyndman and Fan, 1996) with alpha=1/2 and beta=1/2.
Definition xsort.hpp:983
standard mathematical functions for xexpressions
auto range(A start_val, B stop_val)
Select a range from start_val to stop_val (excluded).
Definition xslice.hpp:818
auto all() noexcept
Returns a slice representing a full dimension, to be used as an argument of view function.
Definition xslice.hpp:234
std::vector< xstrided_slice< std::ptrdiff_t > > xstrided_slice_vector
vector of slices used to build a xstrided_view
xarray_container< uvector< T, A >, L, xt::svector< typename uvector< T, A >::size_type, 4, SA, true > > xarray
Alias template on xarray_container with default parameters for data container type and shape / stride...
auto concatenate(std::tuple< CT... > &&t, std::size_t axis=0)
Concatenates xexpressions along axis.
Definition xbuilder.hpp:830
layout_type
Definition xlayout.hpp:24
xfixed_container< T, FSH, L, Sharable > xtensor_fixed
Alias template on xfixed_container with default parameters for layout type.
xtensor_container< uvector< T, A >, N, L > xtensor
Alias template on xtensor_container with default parameters for data container type.
auto index_view(E &&e, I &&indices) noexcept
creates an indexview from a container of indices.
sorting_method
Sorting method.
Definition xsort.hpp:279
@ quick
Faster method but with no guarantee on preservation of order of equal elements https://en....
Definition xsort.hpp:284
@ stable
Slower method but with guarantee on preservation of order of equal elements https://en....
Definition xsort.hpp:289
auto strided_view(E &&e, S &&shape, X &&stride, std::size_t offset=0, layout_type layout=L) noexcept
Construct a strided view from an xexpression, shape, strides and offset.
auto xtuple(Types &&... args)
Creates tuples from arguments for concatenate and stack.
Definition xbuilder.hpp:707