OKlibrary  0.2.1.6
IteratorHandling.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 10.11.2002 (Swansea)
00002 /* Copyright 2002 - 2007, 2008, 2009 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00014 #ifndef ITERATORHANDLINGWAECHTER_gdgsh4e3
00015 #define ITERATORHANDLINGWAECHTER_gdgsh4e3
00016 
00017 #include <algorithm>
00018 #include <iterator>
00019 #include <cstddef>
00020 
00021 #include <boost/iterator/transform_iterator.hpp>
00022 #include <boost/range/functions.hpp>
00023 #include <boost/range/metafunctions.hpp>
00024 #include <boost/range/iterator_range.hpp>
00025 
00026 #include <OKlib/Programming/Utilities/OrderRelations/DerivedRelations.hpp>
00027 
00028 #include <OKlib/General/FunctionHandling.hpp>
00029 
00030 namespace IteratorHandling {
00031 
00032   // ----------------------------------------
00033   // Counting
00034   // ----------------------------------------
00035 
00036   // Output iterator, which only counts how many time it has been advanced
00037   template <typename T>
00038   class Advance_Count : public std::iterator<std::output_iterator_tag, T> {
00039   public :
00040     Advance_Count() : c(0) {}
00041     Advance_Count(const Advance_Count& ac) : c(ac.c) {}
00042     Advance_Count& operator =(const Advance_Count& ac) {
00043       c = ac.c; return *this; }
00044     const Advance_Count& operator =(const T&) const { return *this; }
00045     const Advance_Count& operator *() const { return *this; }
00046     Advance_Count& operator ++() { ++c; return *this; }
00047     Advance_Count operator ++(int) {
00048       Advance_Count ac(*this);
00049       ++c;
00050       return ac;
00051     }
00052 
00053     std::ptrdiff_t count() const { return c; }
00054 
00055   private :
00056     std::ptrdiff_t c;
00057   };
00058 
00059   // Random access iterator for counting
00060   template <typename Int = std::ptrdiff_t>
00061   class Count_iterator : public std::iterator<std::random_access_iterator_tag, Int, Int> {
00062     Int c;
00063   public :
00064     Count_iterator() : c(0) {}
00065     Count_iterator(Int x) : c(x) {}
00066 
00067     friend inline bool operator ==(const Count_iterator lhs, const Count_iterator rhs) { return lhs.c == rhs.c; }
00068     friend inline bool operator <(Count_iterator lhs, Count_iterator rhs) { return lhs.c < rhs.c; }
00069 
00070     Int& operator *() { return c; }
00071 
00072     Count_iterator& operator ++() { ++c; return *this; }
00073     Count_iterator& operator --() { --c; return *this; }
00074     Count_iterator operator ++(int) { Count_iterator ci(*this); ++c; return ci; }
00075     Count_iterator operator --(int) { Count_iterator ci(*this); --c; return ci; }
00076     Count_iterator& operator +=(Int n) { c += n; return *this; }
00077     Count_iterator& operator -=(Int n) { c -= n; return *this; }
00078     friend inline Count_iterator operator + (Count_iterator ci, Int n) { ci += n; return ci; }
00079     friend inline Int operator - (Count_iterator lhs, Count_iterator rhs) { return lhs.c - rhs.c; }
00080   };
00081   
00082   OKLIB_DERIVED_UNEQUAL_TEMPLATE1(Count_iterator)
00083   OKLIB_DERIVED_ORDERRELATIONS_TEMPLATE1(Count_iterator)
00084   
00085   template <typename Int>
00086   Count_iterator<Int> count_iterator(Int x) { return Count_iterator<Int>(x); }
00087 
00088   // ----------------------------------------
00089   // Arithmetical progressions
00090   // ----------------------------------------
00091 
00092   // Arithmetical progressions (as a collection)
00093   // Collection a, a + d, a + 2d, ..., a + m * d
00094   // a, d numerical, m integral
00095 
00096   // ToDo: Integration with class in Combinatorics/Hypergraphs/Generators/plans/VanderWaerden.hpp
00097 
00098   template <typename Num, typename Int>
00099   class Arithmetical_progression {
00100     const Num a, d;
00101     const Int m;
00102 
00103   public :
00104     Arithmetical_progression(const Num a, const Num d, const Int m) : a(a), d(d), m(m) {}
00105     Int size() const { return m+1; }
00106     
00107     class iterator : public Count_iterator<Int> {
00108       const Arithmetical_progression* ap;
00109       iterator(const Arithmetical_progression* ap) : ap(ap) {}
00110       iterator(const Arithmetical_progression* ap, Int i) : Count_iterator<Int>(i), ap(ap) {}
00111       friend class Arithmetical_progression;
00112 
00113     public :
00114       typedef Num value_type;
00115       typedef const Num* pointer;
00116       typedef Num reference;
00117       iterator() : ap(0) {}
00118       reference operator *() {
00119   assert(ap);
00120   return ap -> eval(Count_iterator<Int>::operator *());
00121       }
00122       reference operator *() const {
00123   assert(ap);
00124   return ap -> eval(Count_iterator<Int>::operator *());
00125       }
00126 
00127       friend inline bool operator ==(const iterator lhs, const iterator rhs) {
00128   return static_cast<Count_iterator<Int> >(lhs) == static_cast<Count_iterator<Int> >(rhs) and lhs.ap == rhs.ap;
00129       }
00130       friend OKLIB_DERIVED_UNEQUAL(iterator); // needed inside this class for type deduction
00131 
00132       iterator& operator ++() {
00133   Count_iterator<Int>::operator ++();
00134   return *this;
00135       }
00136       iterator& operator --() {
00137   Count_iterator<Int>::operator --();
00138   return *this;
00139       }
00140       iterator operator ++(int) {
00141   iterator i(*this); operator ++();
00142   return i;
00143       }
00144       iterator operator --(int) {
00145   iterator i(*this); operator --();
00146   return i;
00147       }
00148       iterator& operator +=(Int n) {
00149   Count_iterator<Int>::operator +=(n);
00150   return *this;
00151       }
00152       iterator& operator -=(Int n) {
00153   Count_iterator<Int>::operator -=(n);
00154   return *this;
00155       }
00156       friend inline iterator operator + (iterator i, Int n) {
00157   i += n; return i;
00158       }
00159       friend inline Int operator - (iterator lhs, iterator rhs) {
00160   return static_cast<Count_iterator<Int> >(lhs) - static_cast<Count_iterator<Int> >(rhs);
00161       }
00162     };
00163     
00164     typedef iterator const_iterator;
00165     iterator begin() { return iterator(this); }
00166     iterator end() {
00167       assert(m >= 0);
00168       return iterator(this, m + 1);
00169     }
00170     
00171   private :
00172     Num eval(Int i) const { return a + i * d; }
00173   };
00174 
00175 
00176   // ----------------------------------------
00177   // Iterator adaptors for sequences
00178   // ----------------------------------------
00179 
00185   template <class Iterator>
00186   struct IteratorFirst {
00187     typedef typename Iterator::value_type value_type;
00188     typedef FunctionHandling::First<value_type> first;
00189     typedef boost::transform_iterator<first, Iterator> type;
00190   };
00191   template <class Iterator>
00192   struct IteratorFirstMutable {
00193     typedef typename Iterator::value_type value_type;
00194     typedef FunctionHandling::FirstMutable<value_type> first;
00195     typedef boost::transform_iterator<first, Iterator> type;
00196   };
00197 
00198 
00199   template <class Iterator>
00200   typename IteratorFirst<Iterator>::type iterator_first(const Iterator& it) {
00201     typedef typename IteratorFirst<Iterator>::type iterator;
00202     return iterator(it);
00203   }
00204   template <class Iterator>
00205   typename IteratorFirstMutable<Iterator>::type iterator_first(Iterator& it) {
00206     typedef typename IteratorFirst<Iterator>::type iterator;
00207     return iterator(it);
00208   }
00209 
00210 
00216   template <class Iterator>
00217   struct IteratorSecond {
00218     typedef typename Iterator::value_type value_type;
00219     typedef FunctionHandling::Second<value_type> second;
00220     typedef boost::transform_iterator<second, Iterator> type;
00221   };
00222   template <class Iterator>
00223   struct IteratorSecondMutable {
00224     typedef typename Iterator::value_type value_type;
00225     typedef FunctionHandling::SecondMutable<value_type> second;
00226     typedef boost::transform_iterator<second, Iterator> type;
00227   };
00228 
00229 
00230   template <class Iterator>
00231   typename IteratorSecond<Iterator>::type iterator_second(const Iterator& it) {
00232     typedef typename IteratorSecond<Iterator>::type iterator;
00233     return iterator(it);
00234   }
00235   template <class Iterator>
00236   typename IteratorSecondMutable<Iterator>::type iterator_second(Iterator& it) {
00237     typedef typename IteratorSecond<Iterator>::type iterator;
00238     return iterator(it);
00239   }
00240 
00241 
00242   template <class Range>
00243   struct RangeFirstConst {
00244     typedef typename boost::range_const_iterator<Range>::type iterator;
00245     typedef typename IteratorFirst<iterator>::type iterator_first;
00246     typedef boost::iterator_range<iterator_first> type;
00247   };
00248   template <class Range>
00249   struct RangeFirstMutable {
00250     typedef typename boost::range_iterator<Range>::type iterator;
00251     typedef typename IteratorFirstMutable<iterator>::type iterator_first;
00252     typedef boost::iterator_range<iterator_first> type;
00253   };
00254 
00255 
00256   template <class Range>
00257   typename RangeFirstConst<Range>::type range_first(const Range& r) {
00258     typedef RangeFirstConst<Range> range_first_const;
00259     typedef typename range_first_const::type range;
00260     typedef typename range_first_const::iterator_first iterator;
00261     using boost::begin;
00262     using boost::end;
00263     return range(iterator(begin(r)), iterator(end(r)));
00264   }
00265   template <class Range>
00266   typename RangeFirstMutable<Range>::type range_first(Range& r) {
00267     typedef RangeFirstMutable<Range> range_first_mutable;
00268     typedef typename range_first_mutable::type range;
00269     typedef typename range_first_mutable::iterator_first iterator;
00270     using boost::begin;
00271     using boost::end;
00272     return range(iterator(begin(r)), iterator(end(r)));
00273   }
00274 
00275 
00276   template <class Range>
00277   struct RangeSecondConst {
00278     typedef typename boost::range_const_iterator<Range>::type iterator;
00279     typedef typename IteratorSecond<iterator>::type iterator_second;
00280     typedef boost::iterator_range<iterator_second> type;
00281   };
00282   template <class Range>
00283   struct RangeSecondMutable {
00284     typedef typename boost::range_iterator<Range>::type iterator;
00285     typedef typename IteratorSecondMutable<iterator>::type iterator_second;
00286     typedef boost::iterator_range<iterator_second> type;
00287   };
00288 
00289 
00290   template <class Range>
00291   typename RangeSecondConst<Range>::type range_second(const Range& r) {
00292     typedef RangeSecondConst<Range> range_second_const;
00293     typedef typename range_second_const::type range;
00294     typedef typename range_second_const::iterator_second iterator;
00295     using boost::begin;
00296     using boost::end;
00297     return range(iterator(begin(r)), iterator(end(r)));
00298   }
00299   template <class Range>
00300   typename RangeSecondConst<Range>::type range_second(Range& r) {
00301     typedef RangeSecondMutable<Range> range_second_mutable;
00302     typedef typename range_second_mutable::type range;
00303     typedef typename range_second_mutable::iterator_second iterator;
00304     using boost::begin;
00305     using boost::end;
00306     return range(iterator(begin(r)), iterator(end(r)));
00307   }
00308 
00309 
00310 }
00311 
00312 #endif