zypp/base/Iterator.h

   1 /*---------------------------------------------------------------------\
   2 |                          ____ _   __ __ ___                          |
   3 |                         |__  / \ / / . \ . \                         |
   4 |                           / / \ V /|  _/  _/                         |
   5 |                          / /__ | | | | | |                           |
   6 |                         /_____||_| |_| |_|                           |
   7 |                                                                      |
   8 \---------------------------------------------------------------------*/
   9 /** \file       zypp/base/Iterator.h
  10  *
  11 */
  12 #ifndef ZYPP_BASE_ITERATOR_H
  13 #define ZYPP_BASE_ITERATOR_H
  14
  15 #include <iterator>
  16 #include <utility>
  17
  18 #include <boost/functional.hpp>
  19 #include <boost/iterator/filter_iterator.hpp>
  20 #include <boost/iterator/transform_iterator.hpp>
  21 #include <boost/function_output_iterator.hpp>
  22
  23 #include "zypp/base/Iterable.h"
  24
  25 ///////////////////////////////////////////////////////////////////
  26 namespace zypp
  27 { /////////////////////////////////////////////////////////////////
  28
  29   /** \defgroup ITERATOR Boost.Iterator Library
  30    *
  31    * \see http://www.boost.org/libs/iterator/doc/index.html
  32    *
  33    * \li \b counting_iterator: an iterator over a sequence of
  34    *        consecutive values. Implements a "lazy sequence"
  35    * \li \b filter_iterator: an iterator over the subset of elements
  36    *        of some sequence which satisfy a given predicate
  37    * \li \b function_output_iterator: an output iterator wrapping a
  38    *        unary function object; each time an element is written into
  39    *        the dereferenced iterator, it is passed as a parameter to
  40    *        the function object.
  41    * \li \b indirect_iterator: an iterator over the objects pointed-to
  42    *        by the elements of some sequence.
  43    * \li \b permutation_iterator: an iterator over the elements of
  44    *        some random-access sequence, rearranged according to some
  45    *        sequence of integer indices.
  46    * \li \b reverse_iterator: an iterator which traverses the elements
  47    *        of some bidirectional sequence in reverse. Corrects many of the shortcomings of C++98's std::reverse_iterator.
  48    * \li \b shared_container_iterator: an iterator over elements of
  49    *        a container whose lifetime is maintained by a shared_ptr
  50    *        stored in the iterator.
  51    * \li \b transform_iterator: an iterator over elements which are
  52    *        the result of applying some functional transformation to
  53    *        the elements of an underlying sequence. This component
  54    *        also replaces the old projection_iterator_adaptor.
  55    * \li \b zip_iterator: an iterator over tuples of the elements
  56    *        at corresponding positions of heterogeneous underlying
  57    *        iterators.
  58    *
  59    * There are in fact more interesting iterator concepts
  60    * available than the ones listed above. Have a look at them.
  61    *
  62    * Some of the iterator types are already dragged into namespace
  63    * zypp. Feel free to add what's missing.
  64    *
  65    * \todo Separate them into individual zypp header files.
  66   */
  67   //@{
  68
  69   /** \class filter_iterator
  70    * An iterator over the subset of elements of some sequence
  71    * which satisfy a given predicate.
  72    *
  73    * Provides boost::filter_iterator and boost::make_filter_iterator
  74    * convenience function.
  75    * \see http://www.boost.org/libs/iterator/doc/filter_iterator.html
  76    * \code
  77    * template <class Predicate, class Iterator>
  78    *   filter_iterator<Predicate,Iterator>
  79    *   make_filter_iterator(Predicate f, Iterator x, Iterator end = Iterator());
  80    *
  81    * template <class Predicate, class Iterator>
  82    *   filter_iterator<Predicate,Iterator>
  83    *   make_filter_iterator(Iterator x, Iterator end = Iterator());
  84    * \endcode
  85    * Remember the deduction rules for template arguments.
  86    * \code
  87    * struct MyDefaultConstructibleFilter;
  88    * make_filter_iterator<MyDefaultConstructibleFilter>( c.begin(), c.end() );
  89    * make_filter_iterator( MyDefaultConstructibleFilter(), c.begin(), c.end() );
  90    * ...
  91    * make_filter_iterator( resfilter::ByName("foo"), c.begin(), c.end() );
  92    *
  93    * \endcode
  94   */
  95   using boost::filter_iterator;
  96   using boost::make_filter_iterator;
  97
  98   /** Convenience to create filter_iterator from container::begin(). */
  99   template<class TFilter, class TContainer>
 100     filter_iterator<TFilter, typename TContainer::const_iterator>
 101     make_filter_begin( TFilter f, const TContainer & c )
 102     {
 103       return make_filter_iterator( f, c.begin(), c.end() );
 104     }
 105
 106   /** Convenience to create filter_iterator from container::begin(). */
 107   template<class TFilter, class TContainer>
 108     filter_iterator<TFilter, typename TContainer::const_iterator>
 109     make_filter_begin( const TContainer & c )
 110     {
 111       return make_filter_iterator( TFilter(), c.begin(), c.end() );
 112     }
 113
 114   /** Convenience to create filter_iterator from container::end(). */
 115   template<class TFilter, class TContainer>
 116     filter_iterator<TFilter, typename TContainer::const_iterator>
 117     make_filter_end( TFilter f, const TContainer & c )
 118     {
 119       return make_filter_iterator( f, c.end(), c.end() );
 120     }
 121
 122   /** Convenience to create filter_iterator from container::end(). */
 123   template<class TFilter, class TContainer>
 124     filter_iterator<TFilter, typename TContainer::const_iterator>
 125     make_filter_end( const TContainer & c )
 126     {
 127       return make_filter_iterator( TFilter(), c.end(), c.end() );
 128     }
 129
 130   /** \class transform_iterator
 131    * An iterator over elements which are the result of applying
 132    * some functional transformation to the elements of an underlying
 133    * sequence.
 134    *
 135    * Provides boost::transform_iterator and boost::make_transform_iterator
 136    * convenience function.
 137    * \see http://www.boost.org/libs/iterator/doc/transform_iterator.html
 138    * \code
 139    * template <class UnaryFunction, class Iterator>
 140    *   transform_iterator<UnaryFunction, Iterator>
 141    *   make_transform_iterator(Iterator it, UnaryFunction fun);
 142    *
 143    * template <class UnaryFunction, class Iterator>
 144    *   transform_iterator<UnaryFunction, Iterator>
 145    *   make_transform_iterator(Iterator it);
 146    * \endcode
 147   */
 148   using boost::transform_iterator;
 149   using boost::make_transform_iterator;
 150
 151   /** Functor taking a \c std::pair returning \c std::pair.first.
 152    * \see MapKVIteratorTraits
 153   */
 154   template<class TPair>
 155     struct GetPairFirst : public std::unary_function<TPair, const typename TPair::first_type &>
 156     {
 157       const typename TPair::first_type & operator()( const TPair & pair_r ) const
 158       { return pair_r.first; }
 159     };
 160
 161   /** Functor taking a \c std::pair returning \c std::pair.second .
 162    * \see MapKVIteratorTraits
 163   */
 164   template<class TPair>
 165     struct GetPairSecond : public std::unary_function<TPair, const typename TPair::second_type &>
 166     {
 167       const typename TPair::second_type & operator()( const TPair & pair_r ) const
 168       { return pair_r.second; }
 169     };
 170
 171   /** Traits for std::map key and value iterators.
 172    *
 173    * \ref GetPairFirst and \ref GetPairSecond help building a transform_iterator
 174    * that iterates over keys or values of a std::map. Class MapKVIteratorTraits
 175    * provides some typedefs, you usg. do not want to write explicitly.
 176    *
 177    * \code
 178    * // typedefs
 179    * typedef std::map<K,V> MapType;
 180    *
 181    * // transform_iterator<GetPairFirst<MapType::value_type>,  MapType::const_iterator>
 182    * typedef MapKVIteratorTraits<MapType>::Key_const_iterator MapTypeKey_iterator;
 183    * // transform_iterator<GetPairSecond<MapType::value_type>, MapType::const_iterator>
 184    * typedef MapKVIteratorTraits<MapType>::Value_const_iterator  MapTypeValue_iterator;
 185    *
 186    * // usage
 187    * MapType mymap;
 188    *
 189    * MapTypeKey_const_iterator keyBegin( make_map_key_begin( mymap ) );
 190    * MapTypeKey_const_iterator keyEnd  ( make_map_key_end( mymap ) );
 191    *
 192    * MapTypeValue_const_iterator valBegin( make_map_value_begin( mymap ) );
 193    * MapTypeValue_const_iterator valEnd  ( make_map_value_end( mymap ) );
 194    *
 195    * std::for_each( keyBegin, keyEnd, DoSomething() );
 196    * std::for_each( valBegin, valEnd, DoSomething() );
 197    * \endcode
 198    *
 199    * Or short:
 200    *
 201    * \code
 202    * typedef std::map<K,V> MapType;
 203    * MapType mymap;
 204    *
 205    * std::for_each( make_map_key_begin( mymap ),   make_map_key_end( mymap ),   DoSomething() );
 206    * std::for_each( make_map_value_begin( mymap ), make_map_value_end( mymap ), DoSomething() );
 207    * \endcode
 208    */
 209   template<class TMap>
 210     struct MapKVIteratorTraits
 211     {
 212       /** The map type */
 213       typedef TMap                       MapType;
 214       /** The maps key type */
 215       typedef typename TMap::key_type    KeyType;
 216       /** The key iterator type */
 217       typedef transform_iterator<GetPairFirst<typename MapType::value_type>,
 218                                  typename MapType::const_iterator> Key_const_iterator;
 219       /** The maps value (mapped) type */
 220       typedef typename TMap::mapped_type ValueType;
 221       /** The value iterator type */
 222       typedef transform_iterator<GetPairSecond<typename MapType::value_type>,
 223                                  typename MapType::const_iterator> Value_const_iterator;
 224     };
 225
 226   /** Convenience to create the key iterator from container::begin() */
 227   template<class TMap>
 228     inline typename MapKVIteratorTraits<TMap>::Key_const_iterator make_map_key_begin( const TMap & map_r )
 229     { return make_transform_iterator( map_r.begin(), GetPairFirst<typename TMap::value_type>() ); }
 230
 231   /** Convenience to create the key iterator from container::end() */
 232   template<class TMap>
 233     inline typename MapKVIteratorTraits<TMap>::Key_const_iterator make_map_key_end( const TMap & map_r )
 234     { return make_transform_iterator( map_r.end(), GetPairFirst<typename TMap::value_type>() ); }
 235
 236   /** Convenience to create the value iterator from container::begin() */
 237   template<class TMap>
 238     inline typename MapKVIteratorTraits<TMap>::Value_const_iterator make_map_value_begin( const TMap & map_r )
 239     { return make_transform_iterator( map_r.begin(), GetPairSecond<typename TMap::value_type>() ); }
 240
 241   /** Convenience to create the value iterator from container::end() */
 242   template<class TMap>
 243     inline typename MapKVIteratorTraits<TMap>::Value_const_iterator make_map_value_end( const TMap & map_r )
 244     { return make_transform_iterator( map_r.end(), GetPairSecond<typename TMap::value_type>() ); }
 245
 246   /** Convenience to create the key iterator from container::lower_bound() */
 247   template<class TMap>
 248     inline typename MapKVIteratorTraits<TMap>::Key_const_iterator make_map_key_lower_bound( const TMap & map_r, const typename TMap::key_type & key_r )
 249     { return make_transform_iterator( map_r.lower_bound( key_r ), GetPairFirst<typename TMap::value_type>() ); }
 250
 251   /** Convenience to create the key iterator from container::upper_bound() */
 252   template<class TMap>
 253     inline typename MapKVIteratorTraits<TMap>::Key_const_iterator make_map_key_upper_bound( const TMap & map_r, const typename TMap::key_type & key_r )
 254     { return make_transform_iterator( map_r.upper_bound( key_r ), GetPairFirst<typename TMap::value_type>() ); }
 255
 256   /** Convenience to create the value iterator from container::lower_bound() */
 257   template<class TMap>
 258     inline typename MapKVIteratorTraits<TMap>::Value_const_iterator make_map_value_lower_bound( const TMap & map_r, const typename TMap::key_type & key_r )
 259     { return make_transform_iterator( map_r.lower_bound( key_r ), GetPairSecond<typename TMap::value_type>() ); }
 260
 261   /** Convenience to create the value iterator from container::upper_bound() */
 262   template<class TMap>
 263     inline typename MapKVIteratorTraits<TMap>::Value_const_iterator make_map_value_upper_bound( const TMap & map_r, const typename TMap::key_type & key_r )
 264     { return make_transform_iterator( map_r.upper_bound( key_r ), GetPairSecond<typename TMap::value_type>() ); }
 265
 266   /** \class function_output_iterator
 267    * An output iterator wrapping a unary function object; each time an
 268    * element is written into the dereferenced iterator, it is passed as
 269    * a parameter to the function object.
 270    *
 271    * Provides boost::function_output_iterator and boost::make_function_output_iterator
 272    * convenience function.
 273    * \see http://www.boost.org/libs/iterator/doc/function_output_iterator.html
 274    * \code
 275    * template <class UnaryFunction>
 276    *   function_output_iterator<UnaryFunction>
 277    *   make_function_output_iterator(const UnaryFunction& f = UnaryFunction());
 278    * \endcode
 279   */
 280   using boost::function_output_iterator;
 281   using boost::make_function_output_iterator;
 282
 283   //@}
 284   /////////////////////////////////////////////////////////////////
 285 } // namespace zypp
 286 ///////////////////////////////////////////////////////////////////
 287 #endif // ZYPP_BASE_ITERATOR_H