range_algorithm.txt

                    
   RANGE_ALGORITHMS  
                    

VERSION ==>             #Avoir minimum la 1.43

CONSEILS ==>            #  - Essayer d'utiliser les ranges tant que possible,
                        #    plutôt que les itérators
                        #  - Essayer d'utiliser les algorithmes tant que
                        #    possible
                        #  - Les enchaîner, ce qui donne un effet comme si l'on
                        #    pipait des commandes en Bash.

HEADER ==>              #<boost/range.hpp>

NOTATION ==>            #RANGE_T et ITERATOR_T désignent des types, pas des
                        #objets.

RANGE ==>               #Un RANGE désigne ou bien :
                        #  - un container, dont STRING.
                        #    Son concept sera celui de son iterator.
                        #    Les array statiques (dont STR, et non dynamiques)
                        #    sont supportées, mais peu portables et
                        #    incompatibles avec :
                        #      - copy_range
                        #      - les adaptors copy, slice, indirect
                        #  - une std::pair <ITERATOR_T, ITERATOR_T> (std:pair
                        #    désignant deux ITERATOR de même ITERATOR_T pour le
                        #    begin() et le end() du RANGE)
                        #  - un ITERATOR_RANGE ou SUB_RANGE
                        #On peut aussi rajouter d'autres RANGE à condition que :
                        #  - ils modèlent au moins SinglePassRangeConcept
                        #  - ou qu'on implémente :
                        #    - typedef boost::range_mutable_iterator<RANG>::type
                        #      modelant SinglePassRangeConcept
                        #    - typedef boost::range_const_iterator<RANGE>::type
                        #      modelant SinglePassRangeConcept
                        #    - NAMESPACE::range_begin( RANGE& ), et
                        #      range_end( RANGE& ) renvoyant un TYPE tel que
                        #      dessus (mutable) ; puis les mêmes avec
                        #      ( const RANGE& ), renvoyant un TYPE tel que
                        #      dessus (const). NAMESPACE est celui de RANGE.
                        #    - range_calculate_size peut être défini pour
                        #      préciser une méthode efficiente de calculer la
                        #      taille de RANGE ( cf doc de Boost )
                        #Un algorithm prenant comme argument un RANGE ne devrait
                        #pas prendre un RANGE non-référence.

CONCEPTS ==>            #Les RANGE ont des traversal concepts, comme les
                        #iterators.
                        #Le concept du range est celui de l'iterator sous-
                        #jacent.
                        #Voici les CONCEPTS (cf la librarie Boost pour les
                        #iterators pour savoir comment les utiliser) (le concept
                        #Incrementable n'est pas checkable) (si pas "Writable",
                        #correspondant à "Writable ou non").
                        #Voir aussi les concepts comme Collection, etc.
WritableRangeConcept    #
<RANGE_T>               #Définit aussi le typedef iterator.

SinglePassRangeConcept  #Définit aussi les typedefs iterator et const_iterator,
<RANGE_T>               #et begin() et end() qui renvoient un [const_]iterator,
                        #selon la constness de RANGE_T.
                        #Même chose pour ceux du dessous.
ForwardRangeConcept     #
<RANGE_T>
WritableForwardRange    #
Concept<RANGE_T>
BidirectionalRange      #
Concept <RANGE_T>
WritableBidirectional   #
RangeConcept <RANGE_T>
RandomAccessRangeConcept#
<RANGE_T>
WritableRandomAccess    #
RangeConcept<RANGE_T>

OPERATIONS SUR LES      #Elles dépendent du concept du RANGE.
RANGE  ==>              #Incrémentable et supérieur :

range_iterator          #Typedef depuis le type de l'iterator de RANGE_T :
<RANGE_T>::type         #RANGE_ITERATOR_T
range_value<RANGE_T>    #Typedef depuis
::type                  #std::iterator_traits<RANGE_ITERATOR_T>::value_type
range_reference<RANGE_T>#Typedef depuis
::type                  #std::iterator_traits<RANGE_ITERATOR_T>::reference
range_pointer<RANGE_T>  #Typedef depuis
::type                  #std::iterator_traits<RANGE_ITERATOR_T>::pointer
range_category<RANGE_T> #Typedef depuis
::type                  #std::iterator_traits<RANGE_ITERATOR_T>::
                        #iterator_category

has_range_iterator      #mpl::true_ si range_mutable_iterator<RANGE_T>::type
<RANGE_T>::type         #existe, mpl_false_ sinon
has_const_iterator      #mpl::true_ si range_const_iterator<RANGE_T>::type
<RANGE_T>::type         #existe, mpl_false_ sinon

                        #Single Pass et supérieur :

begin(RANGE)            #Renvoie un ITERATOR sur le début du RANGE, mais par
                        #value : il est donc non Assignable (notamment ++ et --)
                        #(mais son déréférencement est par référence)
                        #Utiliser un RANGE temporaire est peu portable.
end(RANGE)              #Même chose mais sur la fin du RANGE
const_begin(RANGE)      #Comme begin(), mais const : utiliser quand c'est
                        #possible au lieu de begin(), car plus portable
const_end(RANGE)        #Comme end(), mais const

empty(RANGE)            #Renvoie true si begin(RANGE) == end(RANGE)

                        #Forward et supérieur :

range_difference<RANG_T>#Typedef depuis
::type                  #std::iterator_traits<RANGE_ITERATOR_T>::difference
range_size<RANG_T>::type#Typedef vers un type utilisé pour la taille du range

distance(RANGE)         #Renvoie std::distance(begin(RANGE), end(RANGE)) (comme
                        #size(), mais plus lent.)

                        #Bidirectional et supérieur :

range_reverse_iterator  #
<RANGE_T>::type         #Typedef depuis reverse_iterator<ITERATOR_T>

rbegin(RANGE)           #Renvoie un ITERATOR du type précédent, sur end(RANGE).
                        #Cf begin().
rend(RANGE)             #Même chose pour begin(RANGE)
const_rbegin(RANGE)     #Comme rbegin(), mais const
const_rend(RANGE)       #Comme rend(), mais const

                        #Random Access et supérieur :

size(RANGE)             #renvoie le nombre d'éléments de RANGE

make_iterator_range     #Renvoie un ITERATOR_RANGE instantié avec RANGE.
(RANGE[, SIZE_T_VAL1,   #Si les SIZE_T_VAL sont précisés, et seulement si RANGE
SIZE_T_VAL2])           #est au moins Single Pass, ce n'est pas ITERATOR_RANGE
                        #qui est renvoyé, mais ITERATOR_RANGE.
                        #advance_begin(SIZE_T_VAL1).advance_end(SIZE_T_VAL2)
make_iterator_range     #Renvoie un ITERATOR_RANGE, instantié avec les
(WVAR_VAL1, WVAR_VAL2)  #deux ITERATOR en arguments.
as_literal(RANGE)       #Comme make_iterator_range(RANGE), sauf que si RANGE
                        #est une STR ou WSTR, le '\0' final n'est pas compris.

iterator_range<WVAR>    #Classe désignant un RANGE. Contrairement aux autres
                        #RANGE possibles, elle propose quelques CLASSFK en plus
                        #(par exemple begin(), etc. pour un array,
                        #advance_begin() pour un container, etc.).
                        #WVAR est le type d'iterator du RANGE.
                        #Les opérations disponibles, ainsi que le concept du
                        #RANGE dépendent du traversal concept de WVAR.
                        #ITERATOR_RANGE est toujours au moins ForwardTr.

                        #Pour tous :

ITERATOR_RANGE(WVAL,
WVAL2)                  #WVAL et WVAL2 sont donc deux ITERATOR.
ITERATOR_RANGE(RANGE)

ITERATOR_RANGE = RANGE

iterator_range<WVAR>::
iterator                #Typedef depuis WVAR.
iterator_range<WVAR>::  #Typedef depuis WVAR pour ITERATOR_RANGE et depuis
const_iterator          #const WVAR pour SUB_RANGE.
iterator_range<WVAR>::
difference_type         #Typedef depuis std::iterator_traits<WVAR>::difference

ITERATOR_RANGE.begin()  #Equivaut à begin( ITERATOR_RANGE )
ITERATOR_RANGE.end()    #Même chose pour end()

                        #Pour les single pass ITERATOR_RANGE, et supérieur :

ITERATOR_RANGE.empty()  #Renvoie true si ITERATOR_RANGE a une taille == 0.
( ITERATOR_RANGE )      #Contraire.

ITERATOR_RANGE.equal    #Renvoie true si ITERATOR_RANG.begin() == begin(SP_RANG)
(SP_RANG)               # && ITERATOR_RANGE.end() == end(SP_RANG)
ITERATOR_RANG == SP_RANG#Renvoie true ou false si ITERATOR_RANG et SP_RANG ont
ITERATOR_RANG != SP_RANG#la même taille et les même valeurs, mais pas par
                        #référence comme equal()
ITERATOR_RANG < SP_RANG
ITERATOR_RANG > SP_RANG
ITERATOR_RANG <= SP_RANG
ITERATOR_RANG >= SP_RANG#Equivaut à boost::lexicographical_compare()

ITERATOR_RANG.front()   #Renvoie *ITERATOR_RANGE.begin()

                        #Pour les bidirectional pass ITERATOR_RANGE, et
                        #supérieur :

ITERATOR_RANG.back()    #Renvoie *(ITERATOR_RANG.end() - 1)

ITERATOR_RANG.          #Renvoie ITERATOR_RANG, par référence, mais sans ses
advance_begin(SIZ_T_VAL)#SIZE_T_VAL premiers éléments
ITERATOR_RANG.          #Renvoie ITERATOR_RANG, par référence, mais sans ses
advance_end(SIZE_T_VAL) #-SIZE_T_VAL derniers éléments

OSTREAM << ITERATOR_RANG#Ecrit la concaténation de tous les éléments
                        #d'ITERATOR_RANGE sur OSTREAM.

                        #Pour les random access pass ITERATOR_RANGE, et
                        #supérieur :

ITERATOR_RANG[SIZ_T_VAL]#Renvoie l'élément numéro SIZE_T_VAL d'ITERATOR_RANG,
                        #par référence.
ITERATOR_RANG(SIZ_T_VAL)#Même chose, mais par value et const.

ITERATOR_RANG.size()    #Renvoie size(ITERATOR_RANG)

sub_range<WVAR>         #A exactement les mêmes membres que iterator_range,
                        #sauf que l'arguement du template est le type du RANGE
                        #pas de l'iterator.
                        #Est donc plus simple à utiliser.
                        #A aussi un const_iterator plus correct.
                        #Préférer à iterator_range.

copy_range<WVAR>(RANGE) #Renvoie RANGE, sous forme de WVAR_VAL, qui doit être
                        #un type de RANGE convertible depuis RANGE.

HEADER ==>              #<boost/range/irange.hpp>
irange(INTEGER1,        #Renvoie un ITERATOR_RANGE composé d'INTEGER allant
INTEGER2[, S_INTEGER])  #d'INTEGER1 à INTEGER2, avec un pas de S_INTEGER
                        #(par défaut 1), en excluant le dernier nombre en
                        #fonction de ce pas.
                        #Modèle RandomAccessTr. et ReadableIt.
HEADER ==>              #<boost/range/counting_range.hpp>
counting_range(WVAL,    #Equivaut à make_iterator_range(counting_iterator<WVAR>
WVAL2)                  #(WVAL), counting_iterator<WVAR2>(WVAL2)).
counting_range(SP_RANG) #Equivaut à counting_range( SP_RANGE.front(),
                        #SP_RANG.back() )
HEADER ==>              #<boost/range/istream_range.hpp>
istream_range<WVAR>     #Renvoie un ITERATOR_RANGE composés de deux
(BASIC_ISTREAM_VAR)     #ISTREAM_ITERATOR <WVAR> placés sur le début et la fin
                        #de BASIC_ISTREAM_VAR
                        #Modèle InputIt.

HEADER ==>              #<boost/range/any_range.hpp>
any_range<T,U,V,W>      #Désigne un ITERATOR_RANG<any_range<...>::iterator> >,
                        #...::iterator étant n'importe quel iterator prenant en
                        #template <T,U,V,W> (value, category, reference,
                        #difference). Category doit être une boost:: category.
                        #Type erasure, comme boost::any, pas besoin de connaître
                        #type compile-time.
                        #S'instantie avec deux ITERATOR ou un RANGE, n'importe
                        #lesquels, du moment qu'ils respectent template
                        #d'any_range.
                        #...::const_iterator est aussi disponible.

HEADER ==>              #<boost/range/adaptors.hpp>

ADAPTORS ==>            #Ces derniers renvoient une copie d'un RANGE avec des
                        #ITERATOR sous-jacents différents, par value.
                        #Sauf précisé, le traversal concept est conservé.
                        #"Minimum résultant" signifie que le traversal concept
                        #du RANGE renvoyé est le minimum de celui de départ et
                        #de celui indiqué.
                        #Les PREDIC prennent toujours un ou deux arguments du
                        #même type que la value_type du RANGE, et renvoie un
                        #élément de ce même type (ou BOOL_VAL quand c'est
                        #précisé)
                        #ITO représente un itérateur pour le RANGE.
                        #Les voici :

adaptors::copy(RA_RANG, #Tous les éléments antérieur à l'élément numéro
SIZ_T_VAL1, SIZ_T_VAL2) #SIZE_T_VAL1 et postérieur à l'élément SIZ_T_VAL2 + 1
adaptors::slice(RA_RANG,#sont supprimés.
SIZ_T_VAL1, SIZ_T_VAL2) #SIZ_T_VAL1 et 2 doivent être positifs. SIZE_T_VAL1 doit
                        #être <= SIZ_T_VAL2 < RA_RANG.size()

adaptors::unique        #Tous les doublons adjacents de FW_RANG sont supprimés.
(FW_RANG)               #La value_type de FW_RANG doit être EqualityComparable.
                        #Minimum résultant : forward_traversal
adaptors::              #Tous les éléments de SP_RANG renvoyant false via
adjacent_filter(SP_RANG,#PREDIC avec l'élément suivant sont supprimés. Minimum
PREDIC)                 #résultant : forward_traversal. PREDIC doit être un
                        #fonctor.
adaptors::filter        #Tous les éléments de FW_RANG renvoyant false via
(FW_RANG, PREDIC)       #PREDIC sont supprimés. Minimum résultant :
                        #bidirectional.
adaptors::stride        #Tous les éléments dont le numéro - 1 n'est pas multiple
(RA_RANG, SIZE_T_VAL)   #de SIZE_T_VAL (positif) sont supprimés.
adaptors::reverse       #
(BD_RANG)               #Retourne FW_RANG.
adaptors::indirect      #
(SP_RANG)               #Tous les éléments de SP_RANG deviennent *ITO.
adaptors::replace       #
(FW_RANG, WVAL, WVAL2)  #Remplace tous les éléments == WVAL par WVAL2
adaptors::replace_if    #Remplace tous les éléments renvoyant true via PREDIC
(FW_RANG, PREDIC, WVAL) #par WVAL. Si PREDIC est une class, son operator() doit
                        #être const, et ne pas prendre de référence non-const.
adaptors::transform     #Applique PREDIC à tous les éléments de SP_RANG.
(SP_RANG, PREDIC)       #PREDIC doit être une classe et avoir un operator()
                        #const renvoyant PREDIC::result_type.
adaptors::index(SP_RANG,#Ajoute aux itérators sous-jacents une CLASSFK index()
SIZ_T_VAL)              #qui renvoie la difference entre la position de départ
                        #(typiquement begin() ou end()) et le déplacement
                        #(par exemple effectué via + ou - SIZ_T_VAL2), et
                        #ajoute SIZ_T_VAL.

adaptors::map_keys      #Tous les élements de SP_RANG deviennent ITO.first.
(SP_RANG)               #SP_RANG doit contenir des STD::PAIR, comme c'est le
                        #cas pour les [multi]map et [multi]set.
adaptors::map_values    #Tous les élements de SP_RANG deviennent ITO.second.
(SP_RANG)               #SP_RANG doit contenir des STD::PAIR, comme c'est le
                        #cas pour les [multi]map et [multi]set.

adaptors::type_erase    #Convertit RANGE en any_range<...>. En général inutile
(RANGE, adaptors::      #car RANGE convertit implicitement à son instantiation.
type_erased<...>())     #Avec |, s'écrit seulement :
                        #   RANGE | adaptors::type_erased<...>()

NOTATION AVEC | ==>     #Tous les range adaptors sont disponibles avec un "d",
                        #"ed" ou "ied" (ou pareil pour map_keys et map_values),
                        #sous la forme :
                        #  - RANGE | ADAPTOR[(...)]
                        #au lieu de :
                        #  - ADAPTOR(RANGE[, ...])

ALGORITHMES ==>         #Cf doc. pour voir tableau regroupant les algorithmes.

HEADER ==>              #<boost/foreach.hpp>

BOOST_FOREACH(WVAR_VAL, #Exécute ... pour chaque élément WVAR_VAL contenus dans
SP_RANG) { ... }        #SP_RANG, comme le ferait par exemple :
                        #  - for ( SP_ITO(begin(SP_RANG)) ; SP_ITO !=
                        #    end(SP_RANG) ; SP_ITO++ ) { ... }
                        #(utilisant *SP_ITO au lieu de WVAR_VAL)
                        #return, continue et break fonctionnent.
                        #WVAR_VAL peut être une WVAR_VAL&
                        #Peuvent être nested.
                        #Peut enlever les { } si une seule ligne suit, comme pour une boucle normale.
                        #WVAR_VAL et SP_RANG ne doivent pas contenir de virgule, c'est-à-dire utiliser un type avec un template
                        #<T,U>. Dans ce cas, faire un typedef ou déclarer type avant pour ne pas mettre de virgule dans la
                        #macro.
                        #Si SP_RANG n'est pas Assignable ni CopyConstructible, il faut redéfinir boost::foreach::
                        #is_noncopyable, sous la forme :
                        #  template <>
                        #  struct boost::foreach::is_noncopyable<SP_RANG_TYPE> : mpl_true_ {};
                        #Ou (plus portable) :
                        #  inline boost::mpl::true_* boost_foreach_is_noncopyable( SP_RANG_TYPE*&, boost::foreach::tag )
                        #  { return 0; }
                        #Si SP_RANG ou WVAR_VAL est une VAL temporaire (rvalue) :
                        #  - si const : avec Intel 8.0-, Metrowerks 9.5-, ne marche pas, et macro
                        #    BOOST_FOREACH_NO_CONST_RVALUE_DETECTION defined
                        #  - si non-const ou const : avec VC++7.0-, Intel 7.0-, Borland 5.6.4-, Sunpro 5.8-, tru64cxx 71, ne
                        #    marche pas et BOOST_FOREACH_NO_RVALUE_DETECTION defined
BOOST_REVERSE_FOREACH   #
(...)                   #Même chose, mais à l'envers.


                                             /=+===============================+=\
                                            /  :                               :  \
                                            )==:            A FAIRE            :==(
                                            \  :_______________________________:  /
                                             \=+===============================+=/


    - tokenize (range adaptor) : besoin des boost::regex
    - créer ses propres range adaptors (extending the library)