Range concepts
==============

.. contents:: Table of Contents
    :local:


.. _concept-Range:

Range
-----

See details here : 

Let `Rng` be a type that models :ref:`Range (details) <concept-details-Range>`.

Then `Rng` also models :ref:`Semiregular (fundamentals) <concept-fundamentals-object-Semiregular>`.

.. _concept-Range-expressions:
.. rubric:: Expressions

Let : 
    - ``rng`` be an instance of `Rng`.
    - ``rng_cpy`` be an instance of `Rng`.
    - ``crng`` be an instance of `const Rng`.

Then we have the following valid expressions :

+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
|       Expression        |           Return type            | Pre-condition | Post-condition |                      Description                      |
+=========================+==================================+===============+================+=======================================================+
| ``rng()``               | `Rng`                            | none          | none           | Constructs a range ``rng`` of type `Rng`              |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``crng()``              | `const Rng`                      | none          | none           | Constructs a range ``crng`` of type `Rng`             |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``rng_cpy(rng)``        | `Rng`                            | none          | none           | Copy-constructs a range ``rng_cpy`` from ``rng``      |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``rng_cpy(crng)``       | `Rng`                            | none          | none           | Copy-constructs a range ``rng_cpy`` from ``crng``     |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``rng_cpy(move(rng))``  | `Rng`                            | none          | none           | Move-constructs a range ``rng_cpy`` from ``rng``      |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``rng_cpy = rng``       | `Rng&`                           | none          | none           | Assign ``rng`` to ``rng_cpy``                         |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``rng_cpy = crng``      | `Rng&`                           | none          | none           | Assign ``crng`` to ``rng_cpy``                        |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``rng_cpy = move(rng)`` | `Rng&`                           | none          | none           | Move-assign ``rng`` to ``rng_cpy``                    |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``rng.begin()``         | ``/* implementation defined */`` | none          | none           | Return the begining of the range moving forward       |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``rng.end()``           | ``/* implementation defined */`` | none          | none           | Return the end of the range moving forward            |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``crng.cbegin()``       | ``/* implementation defined */`` | none          | none           | Return the const begining of the range moving forward |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+
| ``crng.cend()``         | ``/* implementation defined */`` | none          | none           | Return the const end of the range moving forward      |
+-------------------------+----------------------------------+---------------+----------------+-------------------------------------------------------+


.. _concept-SizedRange:

SizedRange
----------

See details here : 

Let `SRng` be a type that models :ref:`SizedRange (details) <concept-details-SizedRange>`.

Then `SRng` also models :ref:`Range <concept-Range>`.

.. _concept-SizedRange-types:
.. rubric:: Types

Then we can define :

+-----------------------+----------------------+----------------------------------------------------------------------------------------+
|      Definition       |     Description      |                                      Requirement                                       |
+=======================+======================+========================================================================================+
| `SRng::iterator_type` | type of the iterator | models :ref:`Iterator (fundamentals) <concept-fundamentals-iterator-Iterator>` concept |
+-----------------------+----------------------+----------------------------------------------------------------------------------------+

.. _concept-SizedRange-expressions:
.. rubric:: Expressions

Let `IRng` inherit all valid expressions defined for :ref:`Range <concept-Range-expressions>`.

Let : 
    - ``csrng`` be an instance of `const SRng`.

Then we have the following valid expressions :

+------------------+----------------------------------------+---------------+----------------+------------------------------+
|    Expression    |              Return type               | Pre-condition | Post-condition |         Description          |
+==================+========================================+===============+================+==============================+
| ``csrng.size()`` | `SRng::iterator_type::difference_type` | none          | none           | Return the size of the range |
+------------------+----------------------------------------+---------------+----------------+------------------------------+


.. _concept-InputRange:

InputRange
----------

See details here : 

Let `IRng` be a type that models :ref:`InputRange (details) <concept-details-InputRange>`.

Then `IRng` also models :ref:`Range <concept-Range>`.

.. _concept-InputRange-types:
.. rubric:: Types

Then we can define :

+-----------------------+----------------------+--------------------------------------------------------------------------------------------------+
|      Definition       |     Description      |                                           Requirement                                            |
+=======================+======================+==================================================================================================+
| `IRng::iterator_type` | type of the iterator | models :ref:`InputIterator (fundamentals) <concept-fundamentals-iterator-InputIterator>` concept |
+-----------------------+----------------------+--------------------------------------------------------------------------------------------------+

.. _concept-InputRange-expressions:
.. rubric:: Expressions

Let `IRng` inherit all valid expressions defined for :ref:`Range <concept-Range-expressions>`.

Let : 
    - ``it`` be an instance of `IRng::iterator_type`.
    - ``cit`` be an instance of `const IRng::iterator_type`.

Then we have the following valid expressions :

+------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| Expression |          Return type          | Pre-condition |             Post-condition             |         Description         |
+============+===============================+===============+========================================+=============================+
| ``++it``   | `iterator_type&`              | none          | none                                   | Pre-increment the iterator  |
+------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``it++``   | `/* implementation defined*/` | none          | not required to be equality preserving | Post-increment the iterator |
+------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``*cit``   | `auto&&`                      | none          | none                                   | Dereference the iterator    |
+------------+-------------------------------+---------------+----------------------------------------+-----------------------------+


.. _concept-OutputRange:

OutputRange
-----------

See details here : 

Let `(ORng, T)` be a the pair of type that models :ref:`OutputRange (details) <concept-details-OutputRange>`.

Then `ORng` also models :ref:`Range <concept-Range>`.

.. _concept-OutputRange-types:
.. rubric:: Types

Then we can define :

+-----------------------+----------------------+----------------------------------------------------------------------------------------------------+
|      Definition       |     Description      |                                            Requirement                                             |
+=======================+======================+====================================================================================================+
| `IRng::iterator_type` | type of the iterator | models :ref:`OutputIterator (fundamentals) <concept-fundamentals-iterator-OutputIterator>` concept |
+-----------------------+----------------------+----------------------------------------------------------------------------------------------------+

.. _concept-OutputRange-expressions:
.. rubric:: Expressions

Let `ORng` inherit all valid expressions defined for :ref:`Range <concept-Range-expressions>`.

Let : 
    - ``o`` be an instance of `ORng::iterator_type`.
    - ``co`` be an instance of `const ORng::iterator_type`.
    - ``t`` be an instance of `T`.

Then we have the following valid expressions :

+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
|                                          Expression                                          |          Return type          | Pre-condition |             Post-condition             |         Description         |
+==============================================================================================+===============================+===============+========================================+=============================+
| ``++o``                                                                                      | `iterator_type&`              | none          | none                                   | Pre-increment the iterator  |
+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``o++``                                                                                      | `/* implementation defined*/` | none          | not required to be equality preserving | Post-increment the iterator |
+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``*co``                                                                                      | `auto&&`                      | none          | none                                   | Dereference the iterator    |
+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``*o++ = forward<T>(t)``                                                                     | `/* implementation defined*/` | none          | not required to be equality preserving |                             |
+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``*o = forward<T>(t)``                                                                       | `/* implementation defined*/` | none          | not required to be equality preserving |                             |
+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``*forward<iterator_type>(o) = forward<T>(t)``                                               | `/* implementation defined*/` | none          | not required to be equality preserving |                             |
+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``const_cast<const iterator_type::reference&&>(*o) = forward<T>(t)``                         | `/* implementation defined*/` | none          | not required to be equality preserving |                             |
+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+
| ``const_cast<const iterator_type::reference&&>(*forward<iterator_type>(o)) = forward<T>(t)`` | `/* implementation defined*/` | none          | not required to be equality preserving |                             |
+----------------------------------------------------------------------------------------------+-------------------------------+---------------+----------------------------------------+-----------------------------+


.. _concept-ForwardRange:

ForwardRange
------------

See details here : 

Let `FwdRng` be a type that models :ref:`ForwardRange (details) <concept-details-ForwardRange>`.

Then `FwdRng` also models :ref:`InputRange <concept-InputRange>`.

.. _concept-ForwardRange-types:
.. rubric:: Types

Let `FwdRng` inherit all types defined for :ref:`InputRange <concept-InputRange-types>`.

Then we can define :

+-------------------------+----------------------+------------------------------------------------------------------------------------------------------+
|       Definition        |     Description      |                                             Requirement                                              |
+=========================+======================+======================================================================================================+
| `FwdRng::iterator_type` | type of the iterator | models :ref:`ForwardIterator (fundamentals) <concept-fundamentals-iterator-ForwardIterator>` concept |
+-------------------------+----------------------+------------------------------------------------------------------------------------------------------+
| `FwdRng::value_type`    | type of the value    | models :ref:`concept-Value` concept                                                                  |
+-------------------------+----------------------+------------------------------------------------------------------------------------------------------+

.. _concept-ForwardRange-expressions:
.. rubric:: Expressions

Let `FwdRng` inherit all valid expressions defined for :ref:`InputRange <concept-InputRange-expressions>`.

Let : 
    - ``it`` be an instance of `FwdRng::iterator_type`.
    - ``lhs`` be an instance of `const FwdRng::iterator_type`.
    - ``rhs`` be an instance of `const FwdRng::iterator_type`.

Then we have the following valid expressions :

+----------------+-------------------+---------------+----------------+--------------------------------------------+
|   Expression   |    Return type    | Pre-condition | Post-condition |                Description                 |
+================+===================+===============+================+============================================+
| ``lhs == rhs`` | `bool`            | none          | none           | Compare wether two iterators are equals    |
+----------------+-------------------+---------------+----------------+--------------------------------------------+
| ``lhs != rhs`` | `bool`            | none          | none           | Compare wether two iterators are different |
+----------------+-------------------+---------------+----------------+--------------------------------------------+
| ``rhs == lhs`` | `bool`            | none          | none           | Compare wether two iterators are equal     |
+----------------+-------------------+---------------+----------------+--------------------------------------------+
| ``rhs != lhs`` | `bool`            | none          | none           | Compare wether two iterators are different |
+----------------+-------------------+---------------+----------------+--------------------------------------------+
| ``it++``       | `iterator_type&&` | none          | none           | Go to the next element by post-increment   |
+----------------+-------------------+---------------+----------------+--------------------------------------------+


.. _concept-BidirectionalRange:

BidirectionalRange
------------------

Let `BidirRng` be a type that models :ref:`BidirectionalRange (details) <concept-details-BidirectionalRange>`.

Then `BidirRng` also models : :ref:`ForwardRange <concept-ForwardRange>`.

.. _concept-BidirectionalRange-types:
.. rubric:: Types

Let `BidirRng` inherit all types defined for :ref:`ForwardRange <concept-ForwardRange-types>`.

Then we can define :

+-------------------------+----------------------+------------------------------------------------------------------------------------------------------------------+
|       Definition        |     Description      |                                                   Requirement                                                    |
+=========================+======================+==================================================================================================================+
| `FwdRng::iterator_type` | type of the iterator | models :ref:`BidirectionalIterator (fundamentals) <concept-fundamentals-iterator-BidirectionalIterator>` concept |
+-------------------------+----------------------+------------------------------------------------------------------------------------------------------------------+

.. _concept-BidirectionalRange-expressions:
.. rubric:: Expressions

Let `BidirRng` inherit all valid expressions defined for :ref:`ForwardRange <concept-ForwardRange-expressions>`.

Let :
    - ``it`` be an instance of `BidirRng::iterator_type`.
    - ``bidirrng`` be an instance of `BidirRng`.
    - ``cbidirrng`` be an instance of `const BidirRng`.

Then we have the following valid expressions :

+-------------------------+----------------------------------+---------------+----------------+--------------------------------------------------------+
|       Expression        |           Return type            | Pre-condition | Post-condition |                      Description                       |
+=========================+==================================+===============+================+========================================================+
| ``--it``                | `iterator_type&`                 | none          | none           | Pre-decrement the iterator                             |
+-------------------------+----------------------------------+---------------+----------------+--------------------------------------------------------+
| ``it--``                | `iterator_type&&`                | none          | none           | Post-decrement the iterator                            |
+-------------------------+----------------------------------+---------------+----------------+--------------------------------------------------------+
| ``cbidirrng.rbegin()``  | ``/* implementation defined */`` | none          | none           | Return the begining of the range moving backward       |
+-------------------------+----------------------------------+---------------+----------------+--------------------------------------------------------+
| ``cbidirrng.rend()``    | ``/* implementation defined */`` | none          | none           | Return the end of the range moving backward            |
+-------------------------+----------------------------------+---------------+----------------+--------------------------------------------------------+
| ``cbidirrng.crbegin()`` | ``/* implementation defined */`` | none          | none           | Return the const begining of the range moving backward |
+-------------------------+----------------------------------+---------------+----------------+--------------------------------------------------------+
| ``cbidirrng.crend()``   | ``/* implementation defined */`` | none          | none           | Return the const end of the range moving backward      |
+-------------------------+----------------------------------+---------------+----------------+--------------------------------------------------------+


.. _concept-RandomAccessRange:

RandomAccessRange
-----------------

Let `RndAccRng` be a type that models :ref:`RandomAccessRange (details) <concept-details-RandomAccessRange>`.

Then `RndAccRng` also models :ref:`BidirectionalRange <concept-BidirectionalRange>`.

.. _concept-RandomAccessRange-types:
.. rubric:: Types

Let `RndAccRng` inherit all types defined for :ref:`BidirectionalRange <concept-ForwardRange-types>`.

Then we can define :

+----------------------------+----------------------+----------------------------------------------------------------------------------------------------------------+
|         Definition         |     Description      |                                                  Requirement                                                   |
+============================+======================+================================================================================================================+
| `RndAccRng::iterator_type` | type of the iterator | models :ref:`RandomAccessIterator (fundamentals) <concept-fundamentals-iterator-RandomAccessIterator>` concept |
+----------------------------+----------------------+----------------------------------------------------------------------------------------------------------------+

.. _concept-RandomAccessRange-expressions:
.. rubric:: Expressions

Let `RndAccRng` inherit all valid expressions defined for :ref:`BidirectionalRange <concept-ForwardRange-expressions>`.

Let :
    - ``it`` be an instance of `RndAccRng::iterator_type`.
    - ``cit`` be an instance of `const RndAccRng::iterator_type`.
    - ``lhs`` be an instance of `const RndAccRng::iterator_type`.
    - ``rhs`` be an instance of `const RndAccRng::iterator_type`.
    - ``n`` be an instance of `RndAccRng::iterator_type::difference_type`. 

Then we have the following valid expressions :

+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
|   Expression   |        Return type         | Pre-condition | Post-condition |                      Description                      |
+================+============================+===============+================+=======================================================+
| ``lhs < rhs``  | `bool`                     | none          | none           | Compare order of the two ranges                       |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
| ``lhs > rhs``  | `bool`                     | none          | none           | Compare order of the two ranges                       |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
| ``lhs <= rhs`` | `bool`                     | none          | none           | Compare order of the two ranges                       |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
| ``lhs >= rhs`` | `bool`                     | none          | none           | Compare order of the two ranges                       |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
| ``it += n``    | `iterator_type&`           | none          | none           | Jump forward of ``n`` elements                        |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
| - ``cit + n``  | `iterator_type&&`          | none          | none           | Return a range that jumped forward of ``n`` elements  |
| - ``n + cit``  |                            |               |                |                                                       |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
| ``it -= n``    | `iterator_type&`           | none          | none           | Jump backward of ``n`` elements                       |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
| - ``cit - n``  | `iterator_type&&`          | none          | none           | Return a range that jumped backward of ``n`` elements |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+
| ``cit[n]``     | `iterator_type::reference` | none          | none           | Return a range at the index ``n``                     |
+----------------+----------------------------+---------------+----------------+-------------------------------------------------------+