diff options
author | Anton Samokhvalov <pg83@yandex.ru> | 2022-02-10 16:45:15 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:15 +0300 |
commit | 72cb13b4aff9bc9cf22e49251bc8fd143f82538f (patch) | |
tree | da2c34829458c7d4e74bdfbdf85dff449e9e7fb8 /util/generic/algorithm.h | |
parent | 778e51ba091dc39e7b7fcab2b9cf4dbedfb6f2b5 (diff) | |
download | ydb-72cb13b4aff9bc9cf22e49251bc8fd143f82538f.tar.gz |
Restoring authorship annotation for Anton Samokhvalov <pg83@yandex.ru>. Commit 1 of 2.
Diffstat (limited to 'util/generic/algorithm.h')
-rw-r--r-- | util/generic/algorithm.h | 374 |
1 files changed, 187 insertions, 187 deletions
diff --git a/util/generic/algorithm.h b/util/generic/algorithm.h index badfb88993..b6d759535e 100644 --- a/util/generic/algorithm.h +++ b/util/generic/algorithm.h @@ -1,16 +1,16 @@ #pragma once - + #include "is_in.h" #include "utility.h" - + #include <util/system/defaults.h> #include <util/generic/fwd.h> -#include <numeric> -#include <algorithm> -#include <iterator> +#include <numeric> +#include <algorithm> +#include <iterator> #include <utility> - + namespace NPrivate { template <class I, class F, class P> I ExtremeElementBy(I begin, I end, F func, P pred) { @@ -33,16 +33,16 @@ namespace NPrivate { } } -template <class T> +template <class T> static inline void Sort(T f, T l) { - std::sort(f, l); -} - -template <class T, class C> + std::sort(f, l); +} + +template <class T, class C> static inline void Sort(T f, T l, C c) { - std::sort(f, l, c); -} - + std::sort(f, l, c); +} + template <class TContainer> static inline void Sort(TContainer& container) { Sort(container.begin(), container.end()); @@ -65,14 +65,14 @@ static inline void SortBy(TContainer& container, const TGetKey& getKey) { template <class T> static inline void StableSort(T f, T l) { - std::stable_sort(f, l); -} - -template <class T, class C> + std::stable_sort(f, l); +} + +template <class T, class C> static inline void StableSort(T f, T l, C c) { - std::stable_sort(f, l, c); -} - + std::stable_sort(f, l, c); +} + template <class TContainer> static inline void StableSort(TContainer& container) { StableSort(container.begin(), container.end()); @@ -94,30 +94,30 @@ static inline void StableSortBy(TContainer& container, const TGetKey& getKey) { } template <class T> -static inline void PartialSort(T f, T m, T l) { - std::partial_sort(f, m, l); -} - -template <class T, class C> -static inline void PartialSort(T f, T m, T l, C c) { - std::partial_sort(f, m, l, c); -} - +static inline void PartialSort(T f, T m, T l) { + std::partial_sort(f, m, l); +} + +template <class T, class C> +static inline void PartialSort(T f, T m, T l, C c) { + std::partial_sort(f, m, l, c); +} + template <class T, class R> static inline R PartialSortCopy(T f, T l, R of, R ol) { - return std::partial_sort_copy(f, l, of, ol); + return std::partial_sort_copy(f, l, of, ol); } template <class T, class R, class C> static inline R PartialSortCopy(T f, T l, R of, R ol, C c) { - return std::partial_sort_copy(f, l, of, ol, c); -} - -template <class I, class T> -static inline I Find(I f, I l, const T& v) { - return std::find(f, l, v); + return std::partial_sort_copy(f, l, of, ol, c); } +template <class I, class T> +static inline I Find(I f, I l, const T& v) { + return std::find(f, l, v); +} + template <class C, class T> static inline auto Find(C&& c, const T& v) { using std::begin; @@ -140,11 +140,11 @@ static inline auto FindPtr(C&& c, const T& v) { return FindPtr(begin(c), end(c), v); } -template <class I, class P> -static inline I FindIf(I f, I l, P p) { - return std::find_if(f, l, p); -} - +template <class I, class P> +static inline I FindIf(I f, I l, P p) { + return std::find_if(f, l, p); +} + template <class C, class P> static inline auto FindIf(C&& c, P p) { using std::begin; @@ -153,24 +153,24 @@ static inline auto FindIf(C&& c, P p) { return FindIf(begin(c), end(c), p); } -template <class I, class P> +template <class I, class P> static inline bool AllOf(I f, I l, P pred) { return std::all_of(f, l, pred); } -template <class C, class P> +template <class C, class P> static inline bool AllOf(const C& c, P pred) { using std::begin; using std::end; return AllOf(begin(c), end(c), pred); } -template <class I, class P> +template <class I, class P> static inline bool AnyOf(I f, I l, P pred) { return std::any_of(f, l, pred); } -template <class C, class P> +template <class C, class P> static inline bool AnyOf(const C& c, P pred) { using std::begin; using std::end; @@ -178,13 +178,13 @@ static inline bool AnyOf(const C& c, P pred) { } // FindIfPtr - return NULL if not found. Works for arrays, containers, iterators -template <class I, class P> -static inline auto FindIfPtr(I f, I l, P pred) -> decltype(&*f) { +template <class I, class P> +static inline auto FindIfPtr(I f, I l, P pred) -> decltype(&*f) { I found = FindIf(f, l, pred); return (found != l) ? &*found : nullptr; } -template <class C, class P> +template <class C, class P> static inline auto FindIfPtr(C&& c, P pred) { using std::begin; using std::end; @@ -208,13 +208,13 @@ static inline size_t FindIndexIf(C&& c, P p) { } //EqualToOneOf(x, "apple", "orange") means (x == "apple" || x == "orange") -template <typename T> -inline bool EqualToOneOf(const T&) { +template <typename T> +inline bool EqualToOneOf(const T&) { return false; } - -template <typename T, typename U, typename... Other> -inline bool EqualToOneOf(const T& x, const U& y, const Other&... other) { + +template <typename T, typename U, typename... Other> +inline bool EqualToOneOf(const T& x, const U& y, const Other&... other) { return x == y || EqualToOneOf(x, other...); } @@ -228,86 +228,86 @@ static inline size_t CountOf(const T& x, const U& y, const Other&... other) { return static_cast<size_t>(x == y) + CountOf(x, other...); } -template <class I> -static inline void PushHeap(I f, I l) { - std::push_heap(f, l); -} - -template <class I, class C> -static inline void PushHeap(I f, I l, C c) { - std::push_heap(f, l, c); -} - -template <class I> -static inline void PopHeap(I f, I l) { - std::pop_heap(f, l); -} - -template <class I, class C> -static inline void PopHeap(I f, I l, C c) { - std::pop_heap(f, l, c); -} - -template <class I> -static inline void MakeHeap(I f, I l) { - std::make_heap(f, l); -} - -template <class I, class C> -static inline void MakeHeap(I f, I l, C c) { - std::make_heap(f, l, c); -} - +template <class I> +static inline void PushHeap(I f, I l) { + std::push_heap(f, l); +} + +template <class I, class C> +static inline void PushHeap(I f, I l, C c) { + std::push_heap(f, l, c); +} + +template <class I> +static inline void PopHeap(I f, I l) { + std::pop_heap(f, l); +} + +template <class I, class C> +static inline void PopHeap(I f, I l, C c) { + std::pop_heap(f, l, c); +} + +template <class I> +static inline void MakeHeap(I f, I l) { + std::make_heap(f, l); +} + +template <class I, class C> +static inline void MakeHeap(I f, I l, C c) { + std::make_heap(f, l, c); +} + template <class I> static inline void SortHeap(I f, I l) { - std::sort_heap(f, l); + std::sort_heap(f, l); } template <class I, class C> static inline void SortHeap(I f, I l, C c) { - std::sort_heap(f, l, c); -} - -template <class I, class T> -static inline I LowerBound(I f, I l, const T& v) { - return std::lower_bound(f, l, v); -} - -template <class I, class T, class C> -static inline I LowerBound(I f, I l, const T& v, C c) { - return std::lower_bound(f, l, v, c); -} - + std::sort_heap(f, l, c); +} + +template <class I, class T> +static inline I LowerBound(I f, I l, const T& v) { + return std::lower_bound(f, l, v); +} + +template <class I, class T, class C> +static inline I LowerBound(I f, I l, const T& v, C c) { + return std::lower_bound(f, l, v, c); +} + template <class I, class T, class TGetKey> static inline I LowerBoundBy(I f, I l, const T& v, const TGetKey& getKey) { return std::lower_bound(f, l, v, [&](auto&& left, auto&& right) { return getKey(left) < right; }); } -template <class I, class T> -static inline I UpperBound(I f, I l, const T& v) { - return std::upper_bound(f, l, v); -} - -template <class I, class T, class C> -static inline I UpperBound(I f, I l, const T& v, C c) { - return std::upper_bound(f, l, v, c); -} - +template <class I, class T> +static inline I UpperBound(I f, I l, const T& v) { + return std::upper_bound(f, l, v); +} + +template <class I, class T, class C> +static inline I UpperBound(I f, I l, const T& v, C c) { + return std::upper_bound(f, l, v, c); +} + template <class I, class T, class TGetKey> static inline I UpperBoundBy(I f, I l, const T& v, const TGetKey& getKey) { return std::upper_bound(f, l, v, [&](auto&& left, auto&& right) { return left < getKey(right); }); } -template <class T> -static inline T Unique(T f, T l) { - return std::unique(f, l); -} - -template <class T, class P> -static inline T Unique(T f, T l, P p) { - return std::unique(f, l, p); -} - +template <class T> +static inline T Unique(T f, T l) { + return std::unique(f, l); +} + +template <class T, class P> +static inline T Unique(T f, T l, P p) { + return std::unique(f, l, p); +} + template <class T, class TGetKey> static inline T UniqueBy(T f, T l, const TGetKey& getKey) { return Unique(f, l, [&](auto&& left, auto&& right) { return getKey(left) == getKey(right); }); @@ -344,7 +344,7 @@ void Erase(C& c, const TValue& value) { template <class C, class P> void EraseIf(C& c, P p) { - c.erase(std::remove_if(c.begin(), c.end(), p), c.end()); + c.erase(std::remove_if(c.begin(), c.end(), p), c.end()); } template <class C, class P> @@ -360,82 +360,82 @@ void EraseNodesIf(C& c, P p) { template <class T1, class T2> static inline bool Equal(T1 f1, T1 l1, T2 f2) { - return std::equal(f1, l1, f2); + return std::equal(f1, l1, f2); } template <class T1, class T2, class P> static inline bool Equal(T1 f1, T1 l1, T2 f2, P p) { - return std::equal(f1, l1, f2, p); + return std::equal(f1, l1, f2, p); } template <class TI, class TO> static inline TO Copy(TI f, TI l, TO t) { - return std::copy(f, l, t); + return std::copy(f, l, t); } template <class TI, class TO> static inline TO UniqueCopy(TI f, TI l, TO t) { - return std::unique_copy(f, l, t); + return std::unique_copy(f, l, t); } template <class TI, class TO, class TP> static inline TO UniqueCopy(TI f, TI l, TO t, TP p) { - return std::unique_copy(f, l, t, p); + return std::unique_copy(f, l, t, p); } template <class TI, class TO, class TP> static inline TO RemoveCopyIf(TI f, TI l, TO t, TP p) { - return std::remove_copy_if(f, l, t, p); + return std::remove_copy_if(f, l, t, p); } template <class TI, class TO> static inline TO ReverseCopy(TI f, TI l, TO t) { - return std::reverse_copy(f, l, t); + return std::reverse_copy(f, l, t); } template <class TI1, class TI2, class TO> static inline TO SetUnion(TI1 f1, TI1 l1, TI2 f2, TI2 l2, TO p) { - return std::set_union(f1, l1, f2, l2, p); + return std::set_union(f1, l1, f2, l2, p); } template <class TI1, class TI2, class TO, class TC> static inline TO SetUnion(TI1 f1, TI1 l1, TI2 f2, TI2 l2, TO p, TC c) { - return std::set_union(f1, l1, f2, l2, p, c); + return std::set_union(f1, l1, f2, l2, p, c); } template <class TI1, class TI2, class TO> static inline TO SetDifference(TI1 f1, TI1 l1, TI2 f2, TI2 l2, TO p) { - return std::set_difference(f1, l1, f2, l2, p); + return std::set_difference(f1, l1, f2, l2, p); } template <class TI1, class TI2, class TO, class TC> static inline TO SetDifference(TI1 f1, TI1 l1, TI2 f2, TI2 l2, TO p, TC c) { - return std::set_difference(f1, l1, f2, l2, p, c); + return std::set_difference(f1, l1, f2, l2, p, c); } template <class TI1, class TI2, class TO> static inline TO SetSymmetricDifference(TI1 f1, TI1 l1, TI2 f2, TI2 l2, TO p) { - return std::set_symmetric_difference(f1, l1, f2, l2, p); + return std::set_symmetric_difference(f1, l1, f2, l2, p); } template <class TI1, class TI2, class TO, class TC> static inline TO SetSymmetricDifference(TI1 f1, TI1 l1, TI2 f2, TI2 l2, TO p, TC c) { - return std::set_symmetric_difference(f1, l1, f2, l2, p, c); + return std::set_symmetric_difference(f1, l1, f2, l2, p, c); } template <class TI1, class TI2, class TO> static inline TO SetIntersection(TI1 f1, TI1 l1, TI2 f2, TI2 l2, TO p) { - return std::set_intersection(f1, l1, f2, l2, p); + return std::set_intersection(f1, l1, f2, l2, p); } template <class TI1, class TI2, class TO, class TC> static inline TO SetIntersection(TI1 f1, TI1 l1, TI2 f2, TI2 l2, TO p, TC c) { - return std::set_intersection(f1, l1, f2, l2, p, c); + return std::set_intersection(f1, l1, f2, l2, p, c); } template <class I, class T> static inline void Fill(I f, I l, const T& v) { - std::fill(f, l, v); + std::fill(f, l, v); } template <typename I, typename S, typename T> @@ -443,23 +443,23 @@ static inline I FillN(I f, S n, const T& v) { return std::fill_n(f, n, v); } -template <class T> -static inline void Reverse(T f, T l) { - std::reverse(f, l); +template <class T> +static inline void Reverse(T f, T l) { + std::reverse(f, l); } -template <class T> -static inline void Rotate(T f, T m, T l) { - std::rotate(f, m, l); +template <class T> +static inline void Rotate(T f, T m, T l) { + std::rotate(f, m, l); } -template <typename It, typename Val> +template <typename It, typename Val> Val Accumulate(It begin, It end, Val val) { // std::move since C++20 return std::accumulate(begin, end, std::move(val)); } -template <typename It, typename Val, typename BinOp> +template <typename It, typename Val, typename BinOp> Val Accumulate(It begin, It end, Val val, BinOp binOp) { // std::move since C++20 return std::accumulate(begin, end, std::move(val), binOp); @@ -482,39 +482,39 @@ static inline Val InnerProduct(It1 begin1, It1 end1, It2 begin2, Val val) { return std::inner_product(begin1, end1, begin2, val); } -template <typename It1, typename It2, typename Val, typename BinOp1, typename BinOp2> +template <typename It1, typename It2, typename Val, typename BinOp1, typename BinOp2> static inline Val InnerProduct(It1 begin1, It1 end1, It2 begin2, Val val, BinOp1 binOp1, BinOp2 binOp2) { - return std::inner_product(begin1, end1, begin2, val, binOp1, binOp2); + return std::inner_product(begin1, end1, begin2, val, binOp1, binOp2); } template <typename TVectorType> static inline typename TVectorType::value_type InnerProduct(const TVectorType& lhs, const TVectorType& rhs, typename TVectorType::value_type val = typename TVectorType::value_type()) { - return std::inner_product(lhs.begin(), lhs.end(), rhs.begin(), val); + return std::inner_product(lhs.begin(), lhs.end(), rhs.begin(), val); } template <typename TVectorType, typename BinOp1, typename BinOp2> static inline typename TVectorType::value_type InnerProduct(const TVectorType& lhs, const TVectorType& rhs, typename TVectorType::value_type val, BinOp1 binOp1, BinOp2 binOp2) { - return std::inner_product(lhs.begin(), lhs.end(), rhs.begin(), val, binOp1, binOp2); + return std::inner_product(lhs.begin(), lhs.end(), rhs.begin(), val, binOp1, binOp2); } -template <class T> +template <class T> static inline T MinElement(T begin, T end) { - return std::min_element(begin, end); + return std::min_element(begin, end); } -template <class T, class C> +template <class T, class C> static inline T MinElement(T begin, T end, C comp) { - return std::min_element(begin, end, comp); + return std::min_element(begin, end, comp); } -template <class T> +template <class T> static inline T MaxElement(T begin, T end) { - return std::max_element(begin, end); + return std::max_element(begin, end); } -template <class T, class C> +template <class T, class C> static inline T MaxElement(T begin, T end, C comp) { - return std::max_element(begin, end, comp); + return std::max_element(begin, end, comp); } template <class I, class F> @@ -551,13 +551,13 @@ auto MinElementBy(const C& c, F&& func) { template <class TOp, class... TArgs> void ApplyToMany(TOp op, TArgs&&... args) { - int dummy[] = {((void)op(std::forward<TArgs>(args)), 0)...}; + int dummy[] = {((void)op(std::forward<TArgs>(args)), 0)...}; Y_UNUSED(dummy); } -template <class TI, class TOp> +template <class TI, class TOp> inline void ForEach(TI f, TI l, TOp op) { - std::for_each(f, l, op); + std::for_each(f, l, op); } namespace NPrivate { @@ -601,18 +601,18 @@ namespace NPrivate { template <class T, class TOp> constexpr ::TEnableIfTuple<T, bool> AllOf(T&& t, TOp&& op) { return ::NPrivate::AllOfImpl( - std::forward<T>(t), - std::forward<TOp>(op), - std::make_index_sequence<std::tuple_size<std::decay_t<T>>::value>{}); + std::forward<T>(t), + std::forward<TOp>(op), + std::make_index_sequence<std::tuple_size<std::decay_t<T>>::value>{}); } // check that TOp return true for at least one element from tuple T template <class T, class TOp> constexpr ::TEnableIfTuple<T, bool> AnyOf(T&& t, TOp&& op) { return ::NPrivate::AnyOfImpl( - std::forward<T>(t), - std::forward<TOp>(op), - std::make_index_sequence<std::tuple_size<std::decay_t<T>>::value>{}); + std::forward<T>(t), + std::forward<TOp>(op), + std::make_index_sequence<std::tuple_size<std::decay_t<T>>::value>{}); } template <class T, class TOp> @@ -623,19 +623,19 @@ constexpr ::TEnableIfTuple<T> ForEach(T&& t, TOp&& op) { std::make_index_sequence<std::tuple_size<std::decay_t<T>>::value>{}); } -template <class T1, class T2, class O> +template <class T1, class T2, class O> static inline void Transform(T1 b, T1 e, T2 o, O f) { - std::transform(b, e, o, f); + std::transform(b, e, o, f); } -template <class T1, class T2, class T3, class O> +template <class T1, class T2, class T3, class O> static inline void Transform(T1 b1, T1 e1, T2 b2, T3 o, O f) { - std::transform(b1, e1, b2, o, f); + std::transform(b1, e1, b2, o, f); } template <class T, class V> -inline typename std::iterator_traits<T>::difference_type Count(T first, T last, const V& value) { - return std::count(first, last, value); +inline typename std::iterator_traits<T>::difference_type Count(T first, T last, const V& value) { + return std::count(first, last, value); } template <class TContainer, class TValue> @@ -645,38 +645,38 @@ static inline auto Count(const TContainer& container, const TValue& value) { template <class It, class P> static inline auto CountIf(It first, It last, P p) { - return std::count_if(first, last, p); + return std::count_if(first, last, p); } -template <class C, class P> +template <class C, class P> static inline auto CountIf(const C& c, P pred) { using std::begin; using std::end; return CountIf(begin(c), end(c), pred); } -template <class I1, class I2> +template <class I1, class I2> static inline std::pair<I1, I2> Mismatch(I1 b1, I1 e1, I2 b2) { - return std::mismatch(b1, e1, b2); + return std::mismatch(b1, e1, b2); } -template <class I1, class I2, class P> +template <class I1, class I2, class P> static inline std::pair<I1, I2> Mismatch(I1 b1, I1 e1, I2 b2, P p) { - return std::mismatch(b1, e1, b2, p); + return std::mismatch(b1, e1, b2, p); } template <class RandomIterator> static inline void NthElement(RandomIterator begin, RandomIterator nth, RandomIterator end) { - std::nth_element(begin, nth, end); + std::nth_element(begin, nth, end); } template <class RandomIterator, class Compare> static inline void NthElement(RandomIterator begin, RandomIterator nth, RandomIterator end, Compare compare) { - std::nth_element(begin, nth, end, compare); + std::nth_element(begin, nth, end, compare); } // no standard implementation until C++14 -template <class I1, class I2> +template <class I1, class I2> static inline std::pair<I1, I2> Mismatch(I1 b1, I1 e1, I2 b2, I2 e2) { while (b1 != e1 && b2 != e2 && *b1 == *b2) { ++b1; @@ -685,7 +685,7 @@ static inline std::pair<I1, I2> Mismatch(I1 b1, I1 e1, I2 b2, I2 e2) { return std::make_pair(b1, b2); } -template <class I1, class I2, class P> +template <class I1, class I2, class P> static inline std::pair<I1, I2> Mismatch(I1 b1, I1 e1, I2 b2, I2 e2, P p) { while (b1 != e1 && b2 != e2 && p(*b1, *b2)) { ++b1; @@ -696,32 +696,32 @@ static inline std::pair<I1, I2> Mismatch(I1 b1, I1 e1, I2 b2, I2 e2, P p) { template <class It, class Val> static inline bool BinarySearch(It begin, It end, const Val& val) { - return std::binary_search(begin, end, val); + return std::binary_search(begin, end, val); } template <class It, class Val, class Comp> static inline bool BinarySearch(It begin, It end, const Val& val, Comp comp) { - return std::binary_search(begin, end, val, comp); + return std::binary_search(begin, end, val, comp); } template <class It, class Val> static inline std::pair<It, It> EqualRange(It begin, It end, const Val& val) { - return std::equal_range(begin, end, val); + return std::equal_range(begin, end, val); } template <class It, class Val, class Comp> static inline std::pair<It, It> EqualRange(It begin, It end, const Val& val, Comp comp) { - return std::equal_range(begin, end, val, comp); + return std::equal_range(begin, end, val, comp); } template <class ForwardIt> bool IsSorted(ForwardIt begin, ForwardIt end) { - return std::is_sorted(begin, end); + return std::is_sorted(begin, end); } template <class ForwardIt, class Compare> bool IsSorted(ForwardIt begin, ForwardIt end, Compare comp) { - return std::is_sorted(begin, end, comp); + return std::is_sorted(begin, end, comp); } template <class TIterator, typename TGetKey> @@ -731,7 +731,7 @@ bool IsSortedBy(TIterator begin, TIterator end, const TGetKey& getKey) { template <class It, class Val> void Iota(It begin, It end, Val val) { - std::iota(begin, end, val); + std::iota(begin, end, val); } template <class TI, class TO, class S> |