Line data    Source code

       1           0 : // Distributed under the MIT License.
       2             : // See LICENSE.txt for details.
       3             : 
       4             : #pragma once
       5             : 
       6             : #include <algorithm>
       7             : #include <cstddef>
       8             : #include <iterator>
       9             : #include <limits>
      10             : #include <stdexcept>
      11             : #include <type_traits>
      12             : 
      13             : #include "Utilities/ErrorHandling/Assert.hpp"
      14             : #include "Utilities/Gsl.hpp"
      15             : #include "Utilities/MakeString.hpp"
      16             : 
      17             : /// Classes to generate repetitive code needed for STL compatibility.
      18           1 : namespace stl_boilerplate {
      19             : /// Base class to generate methods for a random-access iterator.  This
      20             : /// class takes the derived class and the (optionally `const`)
      21             : /// `value_type` of the iterator.  The exposed `value_type` alias will
      22             : /// always be non-const, as required by the standard, but the template
      23             : /// parameter's constness will affect the `reference` and `pointer`
      24             : /// aliases.
      25             : ///
      26             : /// The derived class must implement `operator*`, `operator+=`,
      27             : /// `operator-` (of two iterators), and `operator==`.
      28             : ///
      29             : /// \snippet Test_StlBoilerplate.cpp RandomAccessIterator
      30             : ///
      31             : /// This class is inspired by Boost's `iterator_facade`, except that
      32             : /// that has a lot of special cases, some of which work poorly because
      33             : /// they predate C++11.
      34             : template <typename Iter, typename ValueType>
      35           1 : class RandomAccessIterator {
      36             :  protected:
      37           0 :   RandomAccessIterator() = default;
      38           0 :   RandomAccessIterator(const RandomAccessIterator&) = default;
      39           0 :   RandomAccessIterator(RandomAccessIterator&&) = default;
      40           0 :   RandomAccessIterator& operator=(const RandomAccessIterator&) = default;
      41           0 :   RandomAccessIterator& operator=(RandomAccessIterator&&) = default;
      42           0 :   ~RandomAccessIterator() = default;
      43             : 
      44             :  public:
      45           0 :   using iterator_category = std::random_access_iterator_tag;
      46           0 :   using value_type = std::remove_const_t<ValueType>;
      47           0 :   using reference = ValueType&;
      48           0 :   using pointer = ValueType*;
      49           0 :   using difference_type = std::ptrdiff_t;
      50             : 
      51           0 :   pointer operator->() const { return &**dthis(); }
      52             : 
      53           0 :   Iter& operator++() { return *dthis() += 1; }
      54           0 :   Iter operator++(int) {
      55             :     const auto ret = *dthis();
      56             :     ++*dthis();
      57             :     return ret;
      58             :   }
      59           0 :   Iter& operator--() { return *dthis() += -1; }
      60           0 :   Iter operator--(int) {
      61             :     const auto ret = *dthis();
      62             :     --*dthis();
      63             :     return ret;
      64             :   }
      65             : 
      66           0 :   Iter& operator-=(const difference_type n) { return *dthis() += -n; }
      67             : 
      68           0 :   reference operator[](const difference_type n) const {
      69             :     auto temp = *dthis();
      70             :     temp += n;
      71             :     return *temp;
      72             :   }
      73             : 
      74             :  private:
      75             :   // derived this
      76           0 :   Iter* dthis() { return static_cast<Iter*>(this); }
      77           0 :   const Iter* dthis() const { return static_cast<const Iter*>(this); }
      78             : };
      79             : 
      80             : template <typename Iter, typename ValueType>
      81           0 : bool operator!=(const RandomAccessIterator<Iter, ValueType>& a,
      82             :                 const RandomAccessIterator<Iter, ValueType>& b) {
      83             :   return not(static_cast<const Iter&>(a) == static_cast<const Iter&>(b));
      84             : }
      85             : 
      86             : template <typename Iter, typename ValueType>
      87           0 : bool operator<(const RandomAccessIterator<Iter, ValueType>& a,
      88             :                const RandomAccessIterator<Iter, ValueType>& b) {
      89             :   return static_cast<const Iter&>(b) - static_cast<const Iter&>(a) > 0;
      90             : }
      91             : 
      92             : template <typename Iter, typename ValueType>
      93           0 : bool operator>(const RandomAccessIterator<Iter, ValueType>& a,
      94             :                const RandomAccessIterator<Iter, ValueType>& b) {
      95             :   return b < a;
      96             : }
      97             : 
      98             : template <typename Iter, typename ValueType>
      99           0 : bool operator<=(const RandomAccessIterator<Iter, ValueType>& a,
     100             :                 const RandomAccessIterator<Iter, ValueType>& b) {
     101             :   return not(a > b);
     102             : }
     103             : 
     104             : template <typename Iter, typename ValueType>
     105           0 : bool operator>=(const RandomAccessIterator<Iter, ValueType>& a,
     106             :                 const RandomAccessIterator<Iter, ValueType>& b) {
     107             :   return not(a < b);
     108             : }
     109             : 
     110             : template <typename Iter, typename ValueType>
     111           0 : Iter operator+(
     112             :     const RandomAccessIterator<Iter, ValueType>& a,
     113             :     const typename RandomAccessIterator<Iter, ValueType>::difference_type& n) {
     114             :   auto result = static_cast<const Iter&>(a);
     115             :   result += n;
     116             :   return result;
     117             : }
     118             : 
     119             : template <typename Iter, typename ValueType>
     120           0 : Iter operator+(
     121             :     const typename RandomAccessIterator<Iter, ValueType>::difference_type& n,
     122             :     const RandomAccessIterator<Iter, ValueType>& a) {
     123             :   return a + n;
     124             : }
     125             : 
     126             : template <typename Iter, typename ValueType>
     127           0 : Iter operator-(
     128             :     const RandomAccessIterator<Iter, ValueType>& a,
     129             :     const typename RandomAccessIterator<Iter, ValueType>::difference_type& n) {
     130             :   auto result = static_cast<const Iter&>(a);
     131             :   result -= n;
     132             :   return result;
     133             : }
     134             : 
     135             : /// Base class to generate methods for a random-access sequence,
     136             : /// similar to a `std::array`.
     137             : ///
     138             : /// This class takes the derived class and the `value_type` of the
     139             : /// sequence as template parameters.  The third template parameter
     140             : /// specifies whether to define comparison operators.  Comparisons are
     141             : /// required by the standard, but for derived classes with additional
     142             : /// functionality the autogenerated ones can give incorrect results.
     143             : ///
     144             : /// The derived class must implement `size` and `operator[]`.
     145             : ///
     146             : /// \snippet Test_StlBoilerplate.cpp RandomAccessSequence
     147             : ///
     148             : /// This class provides methods for accessing and modifying elements
     149             : /// of the sequence, such as `front` and `begin`, as well as iterators
     150             : /// and reverse iterators.  Methods modifying the sequence itself,
     151             : /// such as `insert`, require explicit implementations.
     152             : template <typename Sequence, typename ValueType, bool DefineComparisons>
     153           1 : class RandomAccessSequence {
     154             :  protected:
     155           0 :   RandomAccessSequence() = default;
     156           0 :   RandomAccessSequence(const RandomAccessSequence&) = default;
     157           0 :   RandomAccessSequence(RandomAccessSequence&&) = default;
     158           0 :   RandomAccessSequence& operator=(const RandomAccessSequence&) = default;
     159           0 :   RandomAccessSequence& operator=(RandomAccessSequence&&) = default;
     160           0 :   ~RandomAccessSequence() = default;
     161             : 
     162             :  public:
     163           0 :   using value_type = ValueType;
     164           0 :   using reference = value_type&;
     165           0 :   using const_reference = const value_type&;
     166           0 :   using pointer = ValueType*;
     167           0 :   using const_pointer = const ValueType*;
     168             : 
     169           0 :   class const_iterator
     170             :       : public RandomAccessIterator<const_iterator, const value_type> {
     171             :    public:
     172           0 :     const_iterator() = default;
     173             : 
     174           0 :     const value_type& operator*() const { return (*container_)[offset_]; }
     175           0 :     const_iterator& operator+=(const std::ptrdiff_t n) {
     176             :       offset_ += static_cast<size_t>(n);
     177             :       return *this;
     178             :     }
     179             : 
     180             :    private:
     181           0 :     friend bool operator==(const const_iterator& a, const const_iterator& b) {
     182             :       return a.container_ == b.container_ and a.offset_ == b.offset_;
     183             :     }
     184             : 
     185           0 :     friend std::ptrdiff_t operator-(const const_iterator& a,
     186             :                                     const const_iterator& b) {
     187             :       ASSERT(a.container_ == b.container_, "Subtracting unrelated iterators");
     188             :       return static_cast<std::ptrdiff_t>(a.offset_) -
     189             :              static_cast<std::ptrdiff_t>(b.offset_);
     190             :     }
     191             : 
     192           0 :     friend RandomAccessSequence;
     193           0 :     const_iterator(const gsl::not_null<const Sequence*> container,
     194             :                    const size_t offset)
     195             :         : container_(container), offset_(offset) {}
     196             : 
     197           0 :     const Sequence* container_{nullptr};
     198           0 :     size_t offset_{0};
     199             :   };
     200             : 
     201           0 :   class iterator : public RandomAccessIterator<iterator, value_type> {
     202             :    public:
     203           0 :     iterator() = default;
     204             : 
     205           0 :     value_type& operator*() const { return (*container_)[offset_]; }
     206           0 :     iterator& operator+=(const std::ptrdiff_t n) {
     207             :       offset_ += static_cast<size_t>(n);
     208             :       return *this;
     209             :     }
     210             : 
     211           0 :     operator const_iterator() const {
     212             :       return container_->cbegin() + static_cast<std::ptrdiff_t>(offset_);
     213             :     }
     214             : 
     215             :    private:
     216           0 :     friend bool operator==(const iterator& a, const iterator& b) {
     217             :       return a.container_ == b.container_ and a.offset_ == b.offset_;
     218             :     }
     219             : 
     220           0 :     friend std::ptrdiff_t operator-(const iterator& a, const iterator& b) {
     221             :       ASSERT(a.container_ == b.container_, "Subtracting unrelated iterators");
     222             :       return static_cast<std::ptrdiff_t>(a.offset_) -
     223             :              static_cast<std::ptrdiff_t>(b.offset_);
     224             :     }
     225             : 
     226           0 :     friend RandomAccessSequence;
     227           0 :     iterator(const gsl::not_null<Sequence*> container, const size_t offset)
     228             :         : container_(container), offset_(offset) {}
     229             : 
     230           0 :     Sequence* container_{nullptr};
     231           0 :     size_t offset_{0};
     232             :   };
     233             : 
     234           0 :   using reverse_iterator = std::reverse_iterator<iterator>;
     235           0 :   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     236           0 :   using difference_type =
     237             :       typename std::iterator_traits<const_iterator>::difference_type;
     238           0 :   using size_type = size_t;
     239             : 
     240           0 :   iterator begin() & { return {dthis(), 0}; }
     241           0 :   const_iterator begin() const& { return {dthis(), 0}; }
     242           0 :   const_iterator cbegin() const& { return begin(); }
     243           0 :   iterator end() & { return {dthis(), dthis()->size()}; }
     244           0 :   const_iterator end() const& { return {dthis(), dthis()->size()}; }
     245           0 :   const_iterator cend() const& { return end(); }
     246             : 
     247           0 :   reverse_iterator rbegin() & { return reverse_iterator(end()); }
     248           0 :   const_reverse_iterator rbegin() const& {
     249             :     return const_reverse_iterator(end());
     250             :   }
     251           0 :   const_reverse_iterator crbegin() const& { return rbegin(); }
     252           0 :   reverse_iterator rend() & { return reverse_iterator(begin()); }
     253           0 :   const_reverse_iterator rend() const& {
     254             :     return const_reverse_iterator(begin());
     255             :   }
     256           0 :   const_reverse_iterator crend() const& { return rend(); }
     257             : 
     258             :   /// Not part of the standard, but any attempt to store the results
     259             :   /// of a call that would match one of these would be undefined
     260             :   /// behavior.  Valid uses would be: use as temporaries, but that can
     261             :   /// usually be better done through the normal container access; and
     262             :   /// use in unevaluated contexts, but those should really be
     263             :   /// explicitly requesting lvalue references if that's what they're
     264             :   /// checking.  Either of these can be easily worked around.  If
     265             :   /// these things happen in code outside our control we may have to
     266             :   /// reconsider.
     267             :   /// @{
     268           1 :   void begin() && = delete;
     269           1 :   void begin() const&& = delete;
     270           1 :   void cbegin() && = delete;
     271           1 :   void cbegin() const&& = delete;
     272           1 :   void end() && = delete;
     273           1 :   void end() const&& = delete;
     274           1 :   void cend() && = delete;
     275           1 :   void cend() const&& = delete;
     276           1 :   void rbegin() && = delete;
     277           1 :   void rbegin() const&& = delete;
     278           1 :   void crbegin() && = delete;
     279           1 :   void crbegin() const&& = delete;
     280           1 :   void rend() && = delete;
     281           1 :   void rend() const&& = delete;
     282           1 :   void crend() && = delete;
     283           1 :   void crend() const&& = delete;
     284             :   /// @}
     285             : 
     286           0 :   size_type max_size() const { return std::numeric_limits<size_type>::max(); }
     287           0 :   bool empty() const { return begin() == end(); }
     288             : 
     289           0 :   reference front() { return *begin(); }
     290           0 :   const_reference front() const { return *begin(); }
     291           0 :   reference back() { return *(end() - 1); }
     292           0 :   const_reference back() const { return *(end() - 1); }
     293             : 
     294           0 :   reference at(const size_type n) {
     295             :     if (n >= dthis()->size()) {
     296             :       throw std::out_of_range(MakeString{} << "RandomAccessSequence::at " << n
     297             :                                            << " >= " << dthis()->size());
     298             :     }
     299             :     return (*dthis())[n];
     300             :   }
     301           0 :   const_reference at(const size_type n) const {
     302             :     if (n >= dthis()->size()) {
     303             :       throw std::out_of_range(MakeString{} << "RandomAccessSequence::at " << n
     304             :                                            << " >= " << dthis()->size());
     305             :     }
     306             :     return (*dthis())[n];
     307             :   }
     308             : 
     309             :  private:
     310             :   // derived this
     311           0 :   Sequence* dthis() { return static_cast<Sequence*>(this); }
     312           0 :   const Sequence* dthis() const { return static_cast<const Sequence*>(this); }
     313             : };
     314             : 
     315             : template <typename Sequence, typename ValueType>
     316           0 : bool operator==(const RandomAccessSequence<Sequence, ValueType, true>& a,
     317             :                 const RandomAccessSequence<Sequence, ValueType, true>& b) {
     318             :   return static_cast<const Sequence&>(a).size() ==
     319             :              static_cast<const Sequence&>(b).size() and
     320             :          std::equal(a.begin(), a.end(), b.begin());
     321             : }
     322             : 
     323             : template <typename Sequence, typename ValueType>
     324           0 : bool operator!=(const RandomAccessSequence<Sequence, ValueType, true>& a,
     325             :                 const RandomAccessSequence<Sequence, ValueType, true>& b) {
     326             :   return not(a == b);
     327             : }
     328             : 
     329             : template <typename Sequence, typename ValueType>
     330           0 : bool operator<(const RandomAccessSequence<Sequence, ValueType, true>& a,
     331             :                const RandomAccessSequence<Sequence, ValueType, true>& b) {
     332             :   return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
     333             : }
     334             : 
     335             : template <typename Sequence, typename ValueType>
     336           0 : bool operator>(const RandomAccessSequence<Sequence, ValueType, true>& a,
     337             :                const RandomAccessSequence<Sequence, ValueType, true>& b) {
     338             :   return b < a;
     339             : }
     340             : 
     341             : template <typename Sequence, typename ValueType>
     342           0 : bool operator<=(const RandomAccessSequence<Sequence, ValueType, true>& a,
     343             :                 const RandomAccessSequence<Sequence, ValueType, true>& b) {
     344             :   return not(a > b);
     345             : }
     346             : 
     347             : template <typename Sequence, typename ValueType>
     348           0 : bool operator>=(const RandomAccessSequence<Sequence, ValueType, true>& a,
     349             :                 const RandomAccessSequence<Sequence, ValueType, true>& b) {
     350             :   return not(a < b);
     351             : }
     352             : }  // namespace stl_boilerplate