kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

ranges.hh (20271B)


      1 #ifndef ranges_hh_INCLUDED
      2 #define ranges_hh_INCLUDED
      3 
      4 #include <algorithm>
      5 #include <utility>
      6 #include <iterator>
      7 #include <numeric>
      8 
      9 #include "array.hh"
     10 
     11 namespace Kakoune
     12 {
     13 
     14 template<typename Func> struct ViewFactory { Func func; };
     15 
     16 template<typename Func>
     17 ViewFactory(Func&&) -> ViewFactory<std::remove_cvref_t<Func>>;
     18 
     19 template<typename Range, typename Func>
     20 decltype(auto) operator| (Range&& range, ViewFactory<Func> factory)
     21 {
     22     return factory.func(std::forward<Range>(range));
     23 }
     24 
     25 template<typename Range>
     26 struct DecayRangeImpl { using type = std::remove_cvref_t<Range>; };
     27 
     28 template<typename Range>
     29 struct DecayRangeImpl<Range&> { using type = Range&; };
     30 
     31 template<typename Range>
     32 using DecayRange = typename DecayRangeImpl<Range>::type;
     33 
     34 template<typename Range>
     35 struct RangeHolderImpl { using type = std::remove_cvref_t<Range>; };
     36 
     37 template<typename Range>
     38 struct RangeHolderImpl<Range&> {
     39     struct type
     40     {
     41         Range* range{};
     42 
     43         decltype(auto) begin() { return std::begin(*range); }
     44         decltype(auto) end() { return std::end(*range); }
     45 
     46         type& operator=(Range& r) { range = &r; return *this; }
     47         operator Range&() { return *range; }
     48     };
     49 };
     50 
     51 template<typename Range>
     52 using RangeHolder = typename RangeHolderImpl<Range>::type;
     53 
     54 template<typename Range>
     55 struct ReverseView
     56 {
     57     decltype(auto) begin() { return m_range.rbegin(); }
     58     decltype(auto) end()   { return m_range.rend(); }
     59     decltype(auto) rbegin() { return m_range.begin(); }
     60     decltype(auto) rend()   { return m_range.end(); }
     61     decltype(auto) begin() const { return m_range.rbegin(); }
     62     decltype(auto) end() const  { return m_range.rend(); }
     63     decltype(auto) rbegin() const { return m_range.begin(); }
     64     decltype(auto) rend() const  { return m_range.end(); }
     65 
     66     Range m_range;
     67 };
     68 
     69 constexpr auto reverse()
     70 {
     71     return ViewFactory{[](auto&& range) {
     72         using Range = decltype(range);
     73         return ReverseView<DecayRange<Range>>{std::forward<Range>(range)};
     74     }};
     75 }
     76 
     77 template<typename Range>
     78 using IteratorOf = decltype(std::begin(std::declval<Range>()));
     79 
     80 template<typename Range>
     81 using ValueOf = decltype(*std::declval<IteratorOf<Range>>());
     82 
     83 template<typename Range>
     84 struct SkipView
     85 {
     86     auto begin() const { return std::next(std::begin(m_range), m_skip_count); }
     87     auto end()   const { return std::end(m_range); }
     88 
     89     Range m_range;
     90     size_t m_skip_count;
     91 };
     92 
     93 constexpr auto skip(size_t count)
     94 {
     95     return ViewFactory{[count](auto&& range) {
     96         using Range = decltype(range);
     97         return SkipView<DecayRange<Range>>{std::forward<Range>(range), count};
     98     }};
     99 }
    100 
    101 template<typename Range>
    102 struct DropView
    103 {
    104     auto begin() const { return std::begin(m_range); }
    105     auto end()   const { return std::end(m_range) - m_drop_count; }
    106 
    107     Range m_range;
    108     size_t m_drop_count;
    109 };
    110 
    111 constexpr auto drop(size_t count)
    112 {
    113     return ViewFactory{[count](auto&& range) {
    114         using Range = decltype(range);
    115         return DropView<DecayRange<Range>>{std::forward<Range>(range), count};
    116     }};
    117 }
    118 
    119 template<typename Range, typename Filter>
    120 struct FilterView
    121 {
    122     using RangeIt = IteratorOf<Range>;
    123 
    124     struct Iterator
    125     {
    126         using difference_type = ptrdiff_t;
    127         using value_type = typename std::iterator_traits<RangeIt>::value_type;
    128         using pointer = value_type*;
    129         using reference = value_type&;
    130         using iterator_category = std::forward_iterator_tag;
    131 
    132         Iterator(Filter& filter, RangeIt it, RangeIt end)
    133             : m_it{std::move(it)}, m_end{std::move(end)}, m_filter{&filter}
    134         {
    135             do_filter();
    136         }
    137 
    138         decltype(auto) operator*() { return *m_it; }
    139         Iterator& operator++() { ++m_it; do_filter(); return *this; }
    140         Iterator operator++(int) { auto copy = *this; ++(*this); return copy; }
    141 
    142         friend bool operator==(const Iterator& lhs, const Iterator& rhs)
    143         {
    144             return lhs.m_it == rhs.m_it;
    145         }
    146 
    147         const RangeIt& base() const { return m_it; }
    148 
    149     private:
    150         void do_filter()
    151         {
    152             while (m_it != m_end and not (*m_filter)(*m_it))
    153                 ++m_it;
    154         }
    155 
    156         RangeIt m_it;
    157         RangeIt m_end;
    158         Filter* m_filter;
    159     };
    160 
    161     Iterator begin() const { return {m_filter, std::begin(m_range), std::end(m_range)}; }
    162     Iterator end()   const { return {m_filter, std::end(m_range), std::end(m_range)}; }
    163 
    164     Range m_range;
    165     mutable Filter m_filter;
    166 };
    167 
    168 template<typename Filter>
    169 constexpr auto filter(Filter f)
    170 {
    171     return ViewFactory{[f = std::move(f)](auto&& range) {
    172         using Range = decltype(range);
    173         return FilterView<DecayRange<Range>, Filter>{std::forward<Range>(range), std::move(f)};
    174     }};
    175 }
    176 
    177 template<typename Range>
    178 struct EnumerateView
    179 {
    180     using RangeIt = IteratorOf<Range>;
    181 
    182     struct Iterator
    183     {
    184         using difference_type = ptrdiff_t;
    185         using value_type = typename std::iterator_traits<RangeIt>::value_type;
    186         using pointer = value_type*;
    187         using reference = value_type&;
    188         using iterator_category = std::forward_iterator_tag;
    189 
    190         Iterator(size_t index, RangeIt it)
    191             : m_index{index}, m_it{std::move(it)} {}
    192 
    193         struct ValueType
    194         {
    195             size_t index;
    196             decltype(*std::declval<RangeIt>()) element;
    197         };
    198 
    199         ValueType operator*() { return {m_index, *m_it}; }
    200         Iterator& operator++() { ++m_index; ++m_it; return *this; }
    201         Iterator operator++(int) { auto copy = *this; ++(*this); return copy; }
    202 
    203         friend bool operator==(const Iterator& lhs, const Iterator& rhs)
    204         {
    205             return lhs.m_it == rhs.m_it;
    206         }
    207 
    208         const RangeIt& base() const { return m_it; }
    209 
    210     private:
    211         size_t m_index;
    212         RangeIt m_it;
    213     };
    214 
    215     Iterator begin() const { return {0, std::begin(m_range)}; }
    216     Iterator end()   const { return {(size_t)-1, std::end(m_range)}; }
    217 
    218     Range m_range;
    219 };
    220 
    221 constexpr auto enumerate()
    222 {
    223     return ViewFactory{[](auto&& range) {
    224         using Range = decltype(range);
    225         return EnumerateView<DecayRange<Range>>{std::forward<Range>(range)};
    226     }};
    227 }
    228 
    229 template<typename Range, typename Transform>
    230 struct TransformView
    231 {
    232     using RangeIt = IteratorOf<Range>;
    233     using ResType = decltype(std::declval<Transform>()(*std::declval<RangeIt>()));
    234 
    235     struct Iterator
    236     {
    237         using iterator_category = typename std::iterator_traits<RangeIt>::iterator_category;
    238         using value_type = std::remove_reference_t<ResType>;
    239         using difference_type = typename std::iterator_traits<RangeIt>::difference_type;
    240         using pointer = value_type*;
    241         using reference = value_type&;
    242 
    243         Iterator(Transform& transform, RangeIt it)
    244             : m_it{std::move(it)}, m_transform{&transform} {}
    245 
    246         decltype(auto) operator*() { return (*m_transform)(*m_it); }
    247         decltype(auto) operator[](difference_type i) const { return (*m_transform)(m_it[i]); }
    248 
    249         Iterator& operator++() { ++m_it; return *this; }
    250         Iterator operator++(int) { auto copy = *this; ++m_it; return copy; }
    251 
    252         Iterator& operator--() { --m_it; return *this; }
    253         Iterator operator--(int) { auto copy = *this; --m_it; return copy; }
    254 
    255         Iterator& operator+=(difference_type diff) { m_it += diff; return *this; }
    256         Iterator& operator-=(difference_type diff) { m_it -= diff; return *this; }
    257 
    258         Iterator operator+(difference_type diff) const { return {*m_transform, m_it + diff}; }
    259         Iterator operator-(difference_type diff) const { return {*m_transform, m_it - diff}; }
    260 
    261         friend bool operator==(const Iterator& lhs, const Iterator& rhs) { return lhs.m_it == rhs.m_it; }
    262         friend difference_type operator-(const Iterator& lhs, const Iterator& rhs) { return lhs.m_it - rhs.m_it; }
    263 
    264         RangeIt base() const { return m_it; }
    265 
    266     private:
    267         RangeIt m_it;
    268         Transform* m_transform;
    269     };
    270 
    271     Iterator begin() const { return {m_transform, std::begin(m_range)}; }
    272     Iterator end()   const { return {m_transform, std::end(m_range)}; }
    273 
    274     Range m_range;
    275     mutable Transform m_transform;
    276 };
    277 
    278 template<typename Transform>
    279 constexpr auto transform(Transform t)
    280 {
    281     return ViewFactory{[t = std::move(t)](auto&& range) {
    282         using Range = decltype(range);
    283         return TransformView<DecayRange<Range>, Transform>{std::forward<Range>(range), std::move(t)};
    284     }};
    285 }
    286 
    287 template<typename T, typename U>
    288 struct is_pointer_like : std::false_type {};
    289 
    290 template<typename T, typename U> requires std::is_same_v<std::remove_cvref_t<decltype(*std::declval<U>())>, std::remove_cvref_t<T>>
    291 struct is_pointer_like<T, U> : std::true_type {};
    292 
    293 template<typename M, typename T>
    294 constexpr auto transform(M T::*member)
    295 {
    296     return transform([member](auto&& arg) -> decltype(auto) {
    297         using Arg = decltype(arg);
    298         using Member = decltype(member);
    299 
    300         auto get_object = [&] () mutable  -> decltype(auto) {
    301             if constexpr (is_pointer_like<T, Arg>::value)
    302                 return *std::forward<Arg>(arg);
    303             else
    304                 return std::forward<Arg>(arg);
    305         };
    306 
    307         if constexpr (std::is_member_function_pointer_v<Member>)
    308             return (get_object().*member)();
    309         else
    310             return get_object().*member;
    311     });
    312 }
    313 
    314 template<typename Range, bool escape, bool include_separator,
    315          typename Element = ValueOf<Range>,
    316          typename ValueTypeParam = void>
    317 struct SplitView
    318 {
    319     using RangeIt = IteratorOf<Range>;
    320     using ValueType = std::conditional_t<std::is_same<void, ValueTypeParam>::value,
    321                                          std::pair<IteratorOf<Range>, IteratorOf<Range>>,
    322                                          ValueTypeParam>;
    323 
    324     struct Iterator
    325     {
    326         using difference_type = ptrdiff_t;
    327         using value_type = ValueType;
    328         using pointer = ValueType*;
    329         using reference = ValueType&;
    330         using iterator_category = std::forward_iterator_tag;
    331 
    332         Iterator(RangeIt pos, const RangeIt& end, Element separator, Element escaper)
    333          : done{pos == end}, pos{pos}, sep{pos}, end(end), separator{std::move(separator)}, escaper{std::move(escaper)}
    334         {
    335             bool escaped = false;
    336             while (sep != end and (escaped or *sep != separator))
    337             {
    338                 escaped = escape and not escaped and *sep == escaper;
    339                 ++sep;
    340             }
    341         }
    342 
    343         Iterator& operator++() { advance(); return *this; }
    344         Iterator operator++(int) { auto copy = *this; advance(); return copy; }
    345 
    346         bool operator==(const Iterator& other) const { return pos == other.pos and done == other.done; }
    347 
    348         ValueType operator*() { return {pos, (not include_separator or sep == end) ? sep : sep + 1}; }
    349 
    350     private:
    351         void advance()
    352         {
    353             if (sep == end)
    354             {
    355                 pos = end;
    356                 done = true;
    357                 return;
    358             }
    359 
    360             pos = sep+1;
    361             if (include_separator and pos == end)
    362             {
    363                 done = true;
    364                 return;
    365             }
    366             bool escaped = escape and *sep == escaper;
    367             for (sep = pos; sep != end; ++sep)
    368             {
    369                 if (not escaped and *sep == separator)
    370                     break;
    371                 escaped = escape and not escaped and *sep == escaper;
    372             }
    373         }
    374 
    375         bool done;
    376         RangeIt pos;
    377         RangeIt sep;
    378         RangeIt end;
    379         Element separator;
    380         Element escaper;
    381     };
    382 
    383     Iterator begin() const { return {std::begin(m_range), std::end(m_range), m_separator, m_escaper}; }
    384     Iterator end()   const { return {std::end(m_range), std::end(m_range), m_separator, m_escaper}; }
    385 
    386     Range m_range;
    387     Element m_separator;
    388     Element m_escaper;
    389 };
    390 
    391 template<typename ValueType = void, typename Element>
    392 auto split(Element separator)
    393 {
    394     return ViewFactory{[s = std::move(separator)](auto&& range) {
    395         using Range = decltype(range);
    396         return SplitView<DecayRange<Range>, false, false, Element, ValueType>{std::forward<Range>(range), std::move(s), {}};
    397     }};
    398 }
    399 
    400 template<typename ValueType = void, typename Element>
    401 auto split_after(Element separator)
    402 {
    403     return ViewFactory{[s = std::move(separator)](auto&& range) {
    404         using Range = decltype(range);
    405         return SplitView<DecayRange<Range>, false, true, Element, ValueType>{std::forward<Range>(range), std::move(s), {}};
    406     }};
    407 }
    408 
    409 template<typename ValueType = void, typename Element>
    410 auto split(Element separator, Element escaper)
    411 {
    412     return ViewFactory{[s = std::move(separator), e = std::move(escaper)](auto&& range) {
    413         using Range = decltype(range);
    414         return SplitView<DecayRange<Range>, true, false, Element, ValueType>{std::forward<Range>(range), std::move(s), std::move(e)};
    415     }};
    416 }
    417 
    418 template<typename Range>
    419 struct FlattenedView
    420 {
    421     using OuterIt = IteratorOf<Range>;
    422     using InnerRange = ValueOf<Range>;
    423     using InnerIt = IteratorOf<InnerRange>;
    424 
    425     struct Iterator
    426     {
    427         using value_type = typename std::iterator_traits<InnerIt>::value_type;
    428         using iterator_category = std::forward_iterator_tag;
    429         using difference_type = std::size_t;
    430         using reference = value_type&;
    431         using pointer = value_type*;
    432 
    433         Iterator() = default;
    434         Iterator(OuterIt begin, OuterIt end) : m_outer_it{begin}, m_outer_end{end}
    435         {
    436             find_next_inner();
    437         }
    438 
    439         decltype(auto) operator*() {  return *m_inner_it; }
    440 
    441         Iterator& operator++()
    442         {
    443             if (++m_inner_it == std::end(m_inner_range))
    444             {
    445                 ++m_outer_it;
    446                 find_next_inner();
    447             }
    448             return *this;
    449         }
    450         Iterator operator++(int) { auto copy = *this; ++*this; return copy; }
    451 
    452         friend bool operator==(const Iterator& lhs, const Iterator& rhs)
    453         {
    454             return lhs.m_outer_it == rhs.m_outer_it and lhs.m_inner_it == rhs.m_inner_it;
    455         }
    456 
    457         void find_next_inner()
    458         {
    459             m_inner_it = InnerIt{};
    460             for (; m_outer_it != m_outer_end; ++m_outer_it)
    461             {
    462                 m_inner_range = *m_outer_it;
    463                 if (std::begin(m_inner_range) != std::end(m_inner_range))
    464                 {
    465                     m_inner_it = std::begin(m_inner_range);
    466                     return;
    467                 }
    468             }
    469         }
    470 
    471         OuterIt m_outer_it{};
    472         OuterIt m_outer_end{};
    473         InnerIt m_inner_it{};
    474         RangeHolder<InnerRange> m_inner_range;
    475     };
    476 
    477     Iterator begin() const { return {std::begin(m_range), std::end(m_range)}; }
    478     Iterator end()   const { return {std::end(m_range), std::end(m_range)}; }
    479 
    480     Range m_range;
    481 };
    482 
    483 constexpr auto flatten()
    484 {
    485     return ViewFactory{[](auto&& range){
    486         using Range = decltype(range);
    487         return FlattenedView<DecayRange<Range>>{std::forward<Range>(range)};
    488     }};
    489 }
    490 
    491 template<typename Range1, typename Range2>
    492 struct ConcatView
    493 {
    494     using RangeIt1 = decltype(std::declval<Range1>().begin());
    495     using RangeIt2 = decltype(std::declval<Range2>().begin());
    496     using ValueType = typename std::common_type_t<typename std::iterator_traits<RangeIt1>::value_type,
    497                                                   typename std::iterator_traits<RangeIt2>::value_type>;
    498 
    499     struct Iterator
    500     {
    501         using difference_type = ptrdiff_t;
    502         using value_type = ValueType;
    503         using pointer = ValueType*;
    504         using reference = ValueType&;
    505         using iterator_category = std::forward_iterator_tag;
    506 
    507         static_assert(std::is_convertible<typename std::iterator_traits<RangeIt1>::value_type, ValueType>::value, "");
    508         static_assert(std::is_convertible<typename std::iterator_traits<RangeIt2>::value_type, ValueType>::value, "");
    509 
    510         Iterator(RangeIt1 it1, RangeIt1 end1, RangeIt2 it2)
    511             : m_it1(std::move(it1)), m_end1(std::move(end1)),
    512               m_it2(std::move(it2)) {}
    513 
    514         decltype(auto) operator*() { return is2() ? *m_it2 : *m_it1; }
    515         Iterator& operator++() { if (is2()) ++m_it2; else ++m_it1; return *this; }
    516         Iterator operator++(int) { auto copy = *this; ++*this; return copy; }
    517 
    518         friend bool operator==(const Iterator& lhs, const Iterator& rhs) = default;
    519 
    520     private:
    521         bool is2() const { return m_it1 == m_end1; }
    522 
    523         RangeIt1 m_it1;
    524         RangeIt1 m_end1;
    525         RangeIt2 m_it2;
    526     };
    527 
    528     Iterator begin() const { return {m_range1.begin(), m_range1.end(), m_range2.begin()}; }
    529     Iterator end()   const { return {m_range1.end(), m_range1.end(), m_range2.end()}; }
    530 
    531     Range1 m_range1;
    532     Range2 m_range2;
    533 };
    534 
    535 template<typename Range1, typename Range2>
    536 ConcatView<DecayRange<Range1>, DecayRange<Range2>> concatenated(Range1&& range1, Range2&& range2)
    537 {
    538     return {range1, range2};
    539 }
    540 
    541 template<typename Range, typename T>
    542 auto find(Range&& range, const T& value)
    543 {
    544     using std::begin; using std::end;
    545     return std::find(begin(range), end(range), value);
    546 }
    547 
    548 template<typename Range, typename T>
    549 auto find_if(Range&& range, T&& op)
    550 {
    551     using std::begin; using std::end;
    552     return std::find_if(begin(range), end(range), std::forward<T>(op));
    553 }
    554 
    555 template<typename Range, typename T>
    556 bool contains(Range&& range, const T& value)
    557 {
    558     using std::end;
    559     return find(range, value) != end(range);
    560 }
    561 
    562 template<typename Range, typename T>
    563 bool all_of(Range&& range, T&& op)
    564 {
    565     using std::begin; using std::end;
    566     return std::all_of(begin(range), end(range), std::forward<T>(op));
    567 }
    568 
    569 template<typename Range, typename T>
    570 bool any_of(Range&& range, T&& op)
    571 {
    572     using std::begin; using std::end;
    573     return std::any_of(begin(range), end(range), std::forward<T>(op));
    574 }
    575 
    576 template<typename Range, typename T>
    577 auto remove_if(Range&& range, T&& op)
    578 {
    579     using std::begin; using std::end;
    580     return std::remove_if(begin(range), end(range), std::forward<T>(op));
    581 }
    582 
    583 template<typename Range, typename U>
    584 void unordered_erase(Range&& vec, U&& value)
    585 {
    586     auto it = find(vec, std::forward<U>(value));
    587     if (it != vec.end())
    588     {
    589         using std::swap;
    590         swap(vec.back(), *it);
    591         vec.pop_back();
    592     }
    593 }
    594 
    595 template<typename Range, typename Init, typename BinOp>
    596 Init accumulate(Range&& c, Init&& init, BinOp&& op)
    597 {
    598     using std::begin; using std::end;
    599     return std::accumulate(begin(c), end(c), init, std::forward<BinOp>(op));
    600 }
    601 
    602 template<typename Range, typename Compare, typename Func>
    603 void for_n_best(Range&& c, size_t count, Compare&& compare, Func&& func)
    604 {
    605     using std::begin; using std::end;
    606     auto b = begin(c), e = end(c);
    607     std::make_heap(b, e, compare);
    608     while (count > 0 and b != e)
    609     {
    610         if (func(*b))
    611             --count;
    612         std::pop_heap(b, e--, compare);
    613     }
    614 }
    615 
    616 template<typename Container>
    617 auto gather()
    618 {
    619     return ViewFactory{[](auto&& range) {
    620         using std::begin; using std::end;
    621         return Container(begin(range), end(range));
    622     }};
    623 }
    624 
    625 template<template <typename Element> class Container>
    626 auto gather()
    627 {
    628     return ViewFactory{[](auto&& range) {
    629         using std::begin; using std::end;
    630         using ValueType = std::remove_cv_t<std::remove_reference_t<decltype(*begin(range))>>;
    631         return Container<ValueType>(begin(range), end(range));
    632     }};
    633 }
    634 
    635 template<typename ExceptionType, size_t size, bool exact_size = true>
    636 auto static_gather()
    637 {
    638     return []<size_t... Indexes>(std::index_sequence<Indexes...>) {
    639         return ViewFactory{[] (auto&& range) {
    640             using std::begin; using std::end;
    641             auto it = begin(range), end_it = end(range);
    642             size_t i = 0;
    643             auto elem = [&](size_t index) {
    644                 for (; i < index; ++i)
    645                     if (++it == end_it) throw ExceptionType{i};
    646                 return *it;
    647             };
    648             // Note that initializer lists elements are guaranteed to be sequenced
    649             Array<std::remove_cvref_t<decltype(*begin(range))>, sizeof...(Indexes)> res{{elem(Indexes)...}};
    650             if (exact_size and ++it != end_it)
    651                 throw ExceptionType{++i};
    652             return res;
    653         }};
    654     }(std::make_index_sequence<size>());
    655 }
    656 
    657 }
    658 
    659 #endif // ranges_hh_INCLUDED