[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

vigra/navigator.hxx

00001 /************************************************************************/
00002 /*                                                                      */
00003 /*                Copyright 2004 by Ullrich Koethe                      */
00004 /*       Cognitive Systems Group, University of Hamburg, Germany        */
00005 /*                                                                      */
00006 /*    This file is part of the VIGRA computer vision library.           */
00007 /*    The VIGRA Website is                                              */
00008 /*        http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/      */
00009 /*    Please direct questions, bug reports, and contributions to        */
00010 /*        ullrich.koethe@iwr.uni-heidelberg.de    or                    */
00011 /*        vigra@informatik.uni-hamburg.de                               */
00012 /*                                                                      */
00013 /*    Permission is hereby granted, free of charge, to any person       */
00014 /*    obtaining a copy of this software and associated documentation    */
00015 /*    files (the "Software"), to deal in the Software without           */
00016 /*    restriction, including without limitation the rights to use,      */
00017 /*    copy, modify, merge, publish, distribute, sublicense, and/or      */
00018 /*    sell copies of the Software, and to permit persons to whom the    */
00019 /*    Software is furnished to do so, subject to the following          */
00020 /*    conditions:                                                       */
00021 /*                                                                      */
00022 /*    The above copyright notice and this permission notice shall be    */
00023 /*    included in all copies or substantial portions of the             */
00024 /*    Software.                                                         */
00025 /*                                                                      */
00026 /*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND    */
00027 /*    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES   */
00028 /*    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND          */
00029 /*    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT       */
00030 /*    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,      */
00031 /*    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      */
00032 /*    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR     */
00033 /*    OTHER DEALINGS IN THE SOFTWARE.                                   */                
00034 /*                                                                      */
00035 /************************************************************************/
00036 
00037 #ifndef VIGRA_NAVIGATOR_HXX
00038 #define VIGRA_NAVIGATOR_HXX
00039 
00040 namespace vigra {
00041 
00042 /********************************************************/
00043 /*                                                      */
00044 /*                MultiArrayNavigator                   */
00045 /*                                                      */
00046 /********************************************************/
00047 
00048 /** \brief A navigator that provides acces to the 1D subranges of an
00049     n-dimensional range given by a \ref vigra::MultiIterator and an nD shape.
00050 
00051     Normally, the innermost loop of an iteration extends over the innermost
00052     dimension of a given array. Sometimes, however, it is necessary to have
00053     some other dimension in the inner loop. For example, instead of iterating over
00054     the rows, the inner loop should extend over the columns. The class MultiArrayNavigator
00055     encapsulates the necessary functionality. Given an arbitrary dimensional
00056     array (represented by a vigra::MultiIterator/shape pair), and the desired
00057     inner loop dimension <TT>d</TT>, it moves the encapsulated iterator to all possible
00058     starting points of 1D subsets along the given dimension (e.g. all columns). By calling
00059     <TT>begin()</TT> and <TT>end()</TT>, one can then obtain an STL-compatible 1-dimensional
00060     iterator for the current subset.
00061 
00062     The template parameters specify the embedded iterator type and its dimension.
00063 
00064     <b>Usage:</b>
00065 
00066     <b>\#include</b> <<a href="navigator_8hxx-source.html">vigra/navigator.hxx</a>>
00067 
00068     Namespace: vigra
00069 
00070     \code
00071     typedef vigra::MultiArray<3, int>  Array;
00072 
00073     Array a(Array::size_type(X, Y, Z));
00074 
00075     typedef vigra::MultiArrayNavigator<Array::traverser, 3> Navigator;
00076 
00077     for(int d=0; d<3; ++d)
00078     {
00079         // create Navigator for dimension d
00080         Navigator nav(a.traverser_begin(), a.shape(), d);
00081 
00082         // outer loop: move navigator to all starting points
00083         // of 1D subsets that run parallel to coordinate axis d
00084         for(; nav.hasMore(); ++nav)
00085         {
00086             // inner loop: linear iteration over current subset
00087             //             d == {0, 1, 2}: interate along {x, y, z}-axis respectively
00088              Navigator::iterator i = nav.begin(), end = nav.end();
00089             for(; i != end; ++i)
00090                 // do something
00091         }
00092     }
00093     \endcode
00094 */
00095 template <class MULTI_ITERATOR, unsigned int N>
00096 class MultiArrayNavigator
00097 #ifndef DOXYGEN  // doxygen doesn't understand this inheritance
00098 : public MultiArrayNavigator<MULTI_ITERATOR, N-1>
00099 #endif
00100 {
00101     typedef MultiArrayNavigator<MULTI_ITERATOR, N-1> base_type;
00102 
00103   public:
00104     enum { level = N-1 };
00105 
00106         /** The required shape type for the given iterator type.
00107          */
00108     typedef typename MULTI_ITERATOR::multi_difference_type shape_type;
00109 
00110         /** The iterator type for the inner loop (result of begin() and end()).
00111          */
00112     typedef typename MULTI_ITERATOR::iterator iterator;
00113 
00114         /** Construct navigator for multi-dimensional iterator <TT>i</TT>, array shape <TT>shape</TT>
00115             and inner loop dimension <TT>inner_dimension</TT>.
00116          */
00117     MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & shape, unsigned int inner_dimension)
00118     : base_type(i, shape, inner_dimension),
00119       i_(i),
00120       end_(i)
00121     {
00122         if(inner_dimension != level)
00123             end_.template dim<level>() += shape[level];
00124     }
00125 
00126         /** Advance to next starting location.
00127          */
00128     void operator++()
00129     {
00130         base_type::operator++();
00131         if(base_type::atEnd() && i_ < end_) // this tests implicitly inner_dimension_ != level
00132         {
00133             ++i_.template dim<level>();
00134             if(i_ < end_)
00135                 base_type::reset(i_);
00136         }
00137     }
00138 
00139         /** Advance to next starting location.
00140          */
00141     void operator++(int)
00142     {
00143         ++*this;
00144     }
00145 
00146         /** true if there are more elements.
00147          */
00148     bool hasMore() const
00149     {
00150         return this->inner_dimension_ == level ?
00151                     base_type::hasMore() :
00152                     i_ < end_;
00153     }
00154 
00155         /** true if iterator is exhausted.
00156          */
00157     bool atEnd() const
00158     {
00159         return this->inner_dimension_ == level ?
00160                     base_type::atEnd() :
00161                 !( i_ < end_);
00162     }
00163 
00164   protected:
00165     void reset(MULTI_ITERATOR const & i)
00166     {
00167         end_ = i_ = i;
00168         if(this->inner_dimension_ != level)
00169             end_.template dim<level>() += this->shape_[level];
00170         base_type::reset(i);
00171     }
00172 
00173     MULTI_ITERATOR i_, end_;
00174 };
00175 
00176 template <class MULTI_ITERATOR>
00177 class MultiArrayNavigator<MULTI_ITERATOR, 1>
00178 {
00179   public:
00180     enum { level = 0 };
00181     typedef typename MULTI_ITERATOR::multi_difference_type shape_type;
00182     typedef typename MULTI_ITERATOR::iterator iterator;
00183 
00184     MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & shape, unsigned int inner_dimension)
00185     : shape_(shape),
00186       inner_dimension_(inner_dimension),
00187       i_(i),
00188       end_(i)
00189     {
00190         if(inner_dimension != level)
00191             end_.template dim<level>() += shape[level];
00192     }
00193 
00194     void operator++()
00195     {
00196         ++i_.template dim<level>();
00197     }
00198 
00199     void operator++(int)
00200     {
00201         ++*this;
00202     }
00203 
00204     iterator begin() const
00205     {
00206         return i_.iteratorForDimension(inner_dimension_);
00207     }
00208 
00209     iterator end() const
00210     {
00211         return begin() + shape_[inner_dimension_];
00212     }
00213 
00214     bool hasMore() const
00215     {
00216         return i_ < end_;
00217     }
00218 
00219     bool atEnd() const
00220     {
00221       return !( i_ < end_);
00222     }
00223 
00224   protected:
00225     void reset(MULTI_ITERATOR const & i)
00226     {
00227         end_ = i_ = i;
00228         if(inner_dimension_ != level)
00229             end_.template dim<level>() += shape_[level];
00230     }
00231 
00232     shape_type shape_;
00233     unsigned int inner_dimension_;
00234     MULTI_ITERATOR i_, end_;
00235 };
00236 
00237 } // namespace vigra
00238 
00239 #endif /* VIGRA_NAVIGATOR_HXX */

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
VIGRA 1.6.0 (5 Nov 2009)