iter.h

Go to the documentation of this file.
00001 /** @file rutz/iter.h generic iterator classes */
00002 
00003 ///////////////////////////////////////////////////////////////////////
00004 //
00005 // Copyright (c) 2001-2004 California Institute of Technology
00006 // Copyright (c) 2004-2007 University of Southern California
00007 // Rob Peters <rjpeters at usc dot edu>
00008 //
00009 // created: Fri Aug 17 11:05:24 2001
00010 // commit: $Id: iter.h 8249 2007-04-12 06:03:40Z rjpeters $
00011 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/rutz/iter.h $
00012 //
00013 // --------------------------------------------------------------------
00014 //
00015 // This file is part of GroovX.
00016 //   [http://ilab.usc.edu/rjpeters/groovx/]
00017 //
00018 // GroovX is free software; you can redistribute it and/or modify it
00019 // under the terms of the GNU General Public License as published by
00020 // the Free Software Foundation; either version 2 of the License, or
00021 // (at your option) any later version.
00022 //
00023 // GroovX is distributed in the hope that it will be useful, but
00024 // WITHOUT ANY WARRANTY; without even the implied warranty of
00025 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00026 // General Public License for more details.
00027 //
00028 // You should have received a copy of the GNU General Public License
00029 // along with GroovX; if not, write to the Free Software Foundation,
00030 // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
00031 //
00032 ///////////////////////////////////////////////////////////////////////
00033 
00034 #ifndef GROOVX_RUTZ_ITER_H_UTC20050626084019_DEFINED
00035 #define GROOVX_RUTZ_ITER_H_UTC20050626084019_DEFINED
00036 
00037 #include "rutz/shared_ptr.h"
00038 
00039 #include <utility> // for std::pair
00040 
00041 namespace rutz
00042 {
00043   /// Symbol class for representing generic "end of iteration".
00044   struct iter_end_t {};
00045 
00046   extern const iter_end_t iter_end;
00047 
00048   template <class T> class fwd_iter;
00049   template <class T> class bidir_iter;
00050   template <class T> class rxs_iter;
00051 
00052   template <class T> class fwd_iter_ifx;
00053   template <class T> class bidir_iter_ifx;
00054   template <class T> class rxs_iter_ifx;
00055 
00056   template <class real_iter_t, class T> class fwd_iter_adapter;
00057   template <class real_iter_t, class T> class bidir_iter_adapter;
00058   template <class real_iter_t, class T> class rxs_iter_adapter;
00059 
00060   template <class T, class ifx_t> class concrete_iter;
00061 
00062   template <class T>
00063   inline T& getref(T& t) { return t; }
00064 
00065   template <class T1, class T2>
00066   inline T2& getref(std::pair<T1, T2>& p) { return p.second; }
00067 
00068   ///////////////////////////////////////////////////////////
00069   //
00070   // concrete_iter class
00071   //
00072   ///////////////////////////////////////////////////////////
00073 
00074   /// A template base class for all concrete iterator classes.
00075   /** concrete_iter provides a "fat" interface, but a compile-time
00076       error will be generated if part of the interface is used that is
00077       not supported by the implementation class. */
00078   template <class T, class ifx_t>
00079   class concrete_iter
00080   {
00081     shared_ptr<ifx_t> rep;
00082 
00083     void make_unique()
00084     {
00085       if ( !rep.unique() )
00086         {
00087           rep.reset( rep->clone() );
00088         }
00089     }
00090 
00091   public:
00092     concrete_iter(const concrete_iter& other) : rep(other.rep) {}
00093 
00094     concrete_iter(shared_ptr<ifx_t> impl)      : rep(impl) {}
00095 
00096     // Default assigment-oper OK
00097 
00098     void next()                     { make_unique(); rep->next(); }
00099     void prev()                     { make_unique(); rep->prev(); }
00100     void step(int n)                { make_unique(); rep->step(n); }
00101     concrete_iter& operator++()     { next(); return *this; }
00102     concrete_iter operator++(int)   { concrete_iter c(*this); next(); return c; }
00103     concrete_iter& operator--()     { prev(); return *this; }
00104     concrete_iter operator--(int)   { concrete_iter c(*this); prev(); return c; }
00105 
00106     concrete_iter operator+=(int n) { step(n); return *this; }
00107     concrete_iter operator-=(int n) { step(-n); return *this; }
00108 
00109     int operator-(const concrete_iter& other) const
00110     { return rep->minus(other.rep); }
00111 
00112     T*   operator->()                  const { return &(rep->get()); }
00113     T&   operator*()                   const { return rep->get(); }
00114 
00115     bool at_end()                      const { return rep->at_end(); }
00116     bool is_valid()                    const { return !at_end(); }
00117     int  from_end()                    const { return rep->from_end(); }
00118     bool operator==(const iter_end_t&) const { return at_end(); }
00119     bool operator!=(const iter_end_t&) const { return !at_end(); }
00120   };
00121 
00122 
00123   ///////////////////////////////////////////////////////////
00124   //
00125   // Forward iterators
00126   //
00127   ///////////////////////////////////////////////////////////
00128 
00129 
00130   /// Abstract interface class for forward iterators.
00131   template <class T>
00132   class fwd_iter_ifx
00133   {
00134   public:
00135     typedef T value_t;
00136     typedef fwd_iter_ifx<T> ifx_t;
00137 
00138     virtual        ~fwd_iter_ifx()  {}
00139     virtual ifx_t* clone()  const = 0;
00140     virtual void   next()         = 0;
00141     virtual T&     get()    const = 0;
00142     virtual bool   at_end() const = 0;
00143   };
00144 
00145 
00146   /// Adapts forward iterators to the fwd_iter_ifx interface.
00147   template <class real_iter_t, class T>
00148   class fwd_iter_adapter : public fwd_iter_ifx<T>
00149   {
00150     // assignment operator (not implemented; use clone() instead)
00151     fwd_iter_adapter<real_iter_t, T>&
00152     operator=(const fwd_iter_adapter<real_iter_t, T>&);
00153 
00154     typedef fwd_iter_ifx<T> base_t;
00155 
00156     real_iter_t m_iter;
00157     real_iter_t m_end;
00158 
00159     // copy constructor
00160     fwd_iter_adapter<real_iter_t, T>
00161     (const fwd_iter_adapter<real_iter_t, T>& that)
00162       :
00163       base_t(), m_iter(that.m_iter), m_end(that.m_end) {}
00164 
00165   public:
00166     /// Construct from a pair of "real" iterators.
00167     fwd_iter_adapter<real_iter_t, T>
00168     (real_iter_t iter, real_iter_t end)
00169       :
00170       base_t(), m_iter(iter), m_end(end) {}
00171 
00172     virtual base_t* clone() const { return new fwd_iter_adapter(*this); }
00173     virtual void     next()       { ++m_iter; }
00174     virtual T&        get() const { return getref(*m_iter); }
00175     virtual bool   at_end() const { return m_iter == m_end; }
00176   };
00177 
00178 
00179   /// Concrete forward iterator class.
00180   template <class T>
00181   class fwd_iter :
00182     public concrete_iter<T, fwd_iter_ifx<T> >
00183   {
00184     template <class It>
00185     shared_ptr<fwd_iter_ifx<T> >
00186     adapt(It iter, It end)
00187     {
00188       return shared_ptr<fwd_iter_ifx<T> >
00189         (new fwd_iter_adapter<It, T>(iter, end));
00190     }
00191 
00192   public:
00193     typedef fwd_iter_ifx<T> ifx_t;
00194     typedef concrete_iter<T, ifx_t> base_t;
00195 
00196     fwd_iter(const base_t& other) : base_t(other) {}
00197 
00198     fwd_iter(shared_ptr<ifx_t> impl) : base_t(impl) {}
00199 
00200     template <class It>
00201     fwd_iter(It iter, It end) : base_t(adapt(iter, end)) {}
00202   };
00203 
00204   ///////////////////////////////////////////////////////////
00205   //
00206   // Bidirectional iterators
00207   //
00208   ///////////////////////////////////////////////////////////
00209 
00210 
00211   /// Abstract interface class for bidirectional iterators.
00212   template <class T>
00213   class bidir_iter_ifx : public fwd_iter_ifx<T>
00214   {
00215   public:
00216     typedef bidir_iter_ifx<T> ifx_t;
00217 
00218     virtual ifx_t* clone() const = 0;
00219     virtual void   prev()        = 0;
00220   };
00221 
00222 
00223   /// Adapts bidirectional iterators to the bidir_iter_ifx interface.
00224   template <class real_iter_t, class T>
00225   class bidir_iter_adapter : public bidir_iter_ifx<T>
00226   {
00227     // assignment operator (not implemented; use clone() instead)
00228     bidir_iter_adapter<real_iter_t, T>&
00229     operator=(const bidir_iter_adapter<real_iter_t, T>&);
00230 
00231     typedef bidir_iter_ifx<T> base_t;
00232 
00233     real_iter_t m_iter;
00234     real_iter_t m_end;
00235 
00236     // copy constructor
00237     bidir_iter_adapter<real_iter_t, T>
00238     (const bidir_iter_adapter<real_iter_t, T>& that)
00239       :
00240       base_t(), m_iter(that.m_iter), m_end(that.m_end) {}
00241 
00242   public:
00243     /// Construct from a pair of "real" iterators.
00244     bidir_iter_adapter<real_iter_t, T>
00245     (real_iter_t iter, real_iter_t end)
00246       :
00247       base_t(), m_iter(iter), m_end(end) {}
00248 
00249     virtual base_t* clone() const { return new bidir_iter_adapter(*this); }
00250     virtual void     next()       { ++m_iter; }
00251     virtual void     prev()       { --m_iter; }
00252     virtual T&        get() const { return getref(*m_iter); }
00253     virtual bool   at_end() const { return m_iter == m_end; }
00254   };
00255 
00256 
00257   /// Concrete bidirectional iterator class.
00258   template <class T>
00259   class bidir_iter :
00260     public concrete_iter<T, bidir_iter_ifx<T> >
00261   {
00262     template <class It>
00263     shared_ptr<bidir_iter_ifx<T> >
00264     adapt(It iter, It end)
00265     {
00266       return shared_ptr<bidir_iter_ifx<T> >
00267         (new bidir_iter_adapter<It, T>(iter, end));
00268     }
00269 
00270   public:
00271     typedef bidir_iter_ifx<T> ifx_t;
00272     typedef concrete_iter<T, ifx_t> base_t;
00273 
00274     bidir_iter(const base_t& other) : base_t(other) {}
00275 
00276     bidir_iter(shared_ptr<ifx_t> impl) : base_t(impl) {}
00277 
00278     template <class It>
00279     bidir_iter(It iter, It end) : base_t(adapt(iter, end)) {}
00280   };
00281 
00282 
00283   ///////////////////////////////////////////////////////////
00284   //
00285   // Random Access iterators
00286   //
00287   ///////////////////////////////////////////////////////////
00288 
00289 
00290   /// Abstract interface class for random-access iterators.
00291   template <class T>
00292   class rxs_iter_ifx : public bidir_iter_ifx<T>
00293   {
00294   public:
00295     typedef rxs_iter_ifx<T> ifx_t;
00296 
00297     virtual ifx_t* clone()                   const = 0;
00298     virtual void   step(int n)                     = 0;
00299     virtual int    minus(const ifx_t& other) const = 0;
00300     virtual int    from_end()                const = 0;
00301   };
00302 
00303 
00304   /// Adapts random-access iterators to the rxs_iter_ifx interface.
00305   template <class real_iter_t, class T>
00306   class rxs_iter_adapter : public rxs_iter_ifx<T>
00307   {
00308     // assignment operator (not implemented; use clone() instead)
00309     rxs_iter_adapter<real_iter_t, T>&
00310     operator=(const rxs_iter_adapter<real_iter_t, T>&);
00311 
00312     typedef rxs_iter_ifx<T> base_t;
00313 
00314     real_iter_t m_iter;
00315     real_iter_t m_end;
00316 
00317     // copy constructor
00318     rxs_iter_adapter<real_iter_t, T>
00319     (const rxs_iter_adapter<real_iter_t, T>& that)
00320       :
00321       base_t(), m_iter(that.m_iter), m_end(that.m_end) {}
00322 
00323   public:
00324     /// Construct from a pair of "real" iterators.
00325     rxs_iter_adapter<real_iter_t, T>
00326     (real_iter_t iter, real_iter_t end)
00327       :
00328       base_t(), m_iter(iter), m_end(end) {}
00329 
00330     virtual base_t* clone()      const { return new rxs_iter_adapter(*this); }
00331     virtual void     next()            { ++m_iter; }
00332     virtual void     prev()            { --m_iter; }
00333     virtual void     step(int n)       { m_iter += n; }
00334     virtual T&        get()      const { return getref(*m_iter); }
00335     virtual bool   at_end()      const { return m_iter == m_end; }
00336     virtual int  from_end()      const { return m_end - m_iter; }
00337 
00338     virtual int minus(const rxs_iter_ifx<T>& other_) const
00339     {
00340       rxs_iter_adapter<real_iter_t, T>& other =
00341         dynamic_cast<const rxs_iter_adapter<real_iter_t, T>& >(other_);
00342 
00343       return m_iter - other.m_iter;
00344     }
00345   };
00346 
00347 
00348   /// Concrete random-access iterator class.
00349   template <class T>
00350   class rxs_iter :
00351     public concrete_iter<T, rxs_iter_ifx<T> >
00352   {
00353     template <class It>
00354     shared_ptr<rxs_iter_ifx<T> >
00355     adapt(It iter, It end)
00356     {
00357       return shared_ptr<rxs_iter_ifx<T> >
00358         (new rxs_iter_adapter<It, T>(iter, end));
00359     }
00360 
00361   public:
00362     typedef rxs_iter_ifx<T> ifx_t;
00363     typedef concrete_iter<T, ifx_t> base_t;
00364 
00365     rxs_iter(const base_t& other) : base_t(other) {}
00366 
00367     rxs_iter(shared_ptr<ifx_t> impl) : base_t(impl) {}
00368 
00369     template <class It>
00370     rxs_iter(It iter, It end) : base_t(adapt(iter, end)) {}
00371   };
00372 
00373 } // end namespace rutz
00374 
00375 static const char __attribute__((used)) vcid_groovx_rutz_iter_h_utc20050626084019[] = "$Id: iter.h 8249 2007-04-12 06:03:40Z rjpeters $ $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/rutz/iter.h $";
00376 #endif // !GROOVX_RUTZ_ITER_H_UTC20050626084019_DEFINED
Generated on Sun May 8 08:42:12 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3