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