[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
vigra/navigator.hxx | ![]() |
00001 /************************************************************************/ 00002 /* */ 00003 /* Copyright 2004 by Ullrich Koethe */ 00004 /* */ 00005 /* This file is part of the VIGRA computer vision library. */ 00006 /* The VIGRA Website is */ 00007 /* http://hci.iwr.uni-heidelberg.de/vigra/ */ 00008 /* Please direct questions, bug reports, and contributions to */ 00009 /* ullrich.koethe@iwr.uni-heidelberg.de or */ 00010 /* vigra@informatik.uni-hamburg.de */ 00011 /* */ 00012 /* Permission is hereby granted, free of charge, to any person */ 00013 /* obtaining a copy of this software and associated documentation */ 00014 /* files (the "Software"), to deal in the Software without */ 00015 /* restriction, including without limitation the rights to use, */ 00016 /* copy, modify, merge, publish, distribute, sublicense, and/or */ 00017 /* sell copies of the Software, and to permit persons to whom the */ 00018 /* Software is furnished to do so, subject to the following */ 00019 /* conditions: */ 00020 /* */ 00021 /* The above copyright notice and this permission notice shall be */ 00022 /* included in all copies or substantial portions of the */ 00023 /* Software. */ 00024 /* */ 00025 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */ 00026 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */ 00027 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */ 00028 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */ 00029 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */ 00030 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ 00031 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */ 00032 /* OTHER DEALINGS IN THE SOFTWARE. */ 00033 /* */ 00034 /************************************************************************/ 00035 00036 #ifndef VIGRA_NAVIGATOR_HXX 00037 #define VIGRA_NAVIGATOR_HXX 00038 00039 namespace vigra { 00040 00041 /********************************************************/ 00042 /* */ 00043 /* MultiArrayNavigator */ 00044 /* */ 00045 /********************************************************/ 00046 00047 /** \brief A navigator that provides access to the 1D subranges of an 00048 n-dimensional range given by a \ref vigra::MultiIterator and an nD shape. 00049 00050 Normally, the innermost loop of an iteration extends over the innermost 00051 dimension of a given array. Sometimes, however, it is necessary to have 00052 some other dimension in the inner loop. For example, instead of iterating over 00053 the rows, the inner loop should extend over the columns. The class MultiArrayNavigator 00054 encapsulates the necessary functionality. Given an arbitrary dimensional 00055 array (represented by a vigra::MultiIterator/shape pair), and the desired 00056 inner loop dimension <TT>d</TT>, it moves the encapsulated iterator to all possible 00057 starting points of 1D subsets along the given dimension (e.g. all columns). By calling 00058 <TT>begin()</TT> and <TT>end()</TT>, one can then obtain an STL-compatible 1-dimensional 00059 iterator for the current subset. 00060 00061 The template parameters specify the embedded iterator type and its dimension. 00062 00063 <b>Usage:</b> 00064 00065 <b>\#include</b> <vigra/navigator.hxx> 00066 00067 Namespace: vigra 00068 00069 \code 00070 typedef vigra::MultiArray<3, int> Array; 00071 00072 Array a(Array::size_type(X, Y, Z)); 00073 00074 typedef vigra::MultiArrayNavigator<Array::traverser, 3> Navigator; 00075 00076 for(int d=0; d<3; ++d) 00077 { 00078 // create Navigator for dimension d 00079 Navigator nav(a.traverser_begin(), a.shape(), d); 00080 00081 // outer loop: move navigator to all starting points 00082 // of 1D subsets that run parallel to coordinate axis d 00083 for(; nav.hasMore(); ++nav) 00084 { 00085 // inner loop: linear iteration over current subset 00086 // d == {0, 1, 2}: iterate along {x, y, z}-axis respectively 00087 Navigator::iterator i = nav.begin(), end = nav.end(); 00088 for(; i != end; ++i) 00089 // do something 00090 } 00091 } 00092 \endcode 00093 */ 00094 template <class MULTI_ITERATOR, unsigned int N> 00095 class MultiArrayNavigator 00096 #ifndef DOXYGEN // doxygen doesn't understand this inheritance 00097 : public MultiArrayNavigator<MULTI_ITERATOR, N-1> 00098 #endif 00099 { 00100 typedef MultiArrayNavigator<MULTI_ITERATOR, N-1> base_type; 00101 00102 public: 00103 enum { level = N-1 }; 00104 00105 /** The required shape type for the given iterator type. 00106 */ 00107 typedef typename MULTI_ITERATOR::multi_difference_type shape_type; 00108 00109 /** The iterator type for the inner loop (result of begin() and end()). 00110 */ 00111 typedef typename MULTI_ITERATOR::iterator iterator; 00112 00113 /** Construct navigator for multi-dimensional iterator <TT>i</TT>, array shape <TT>shape</TT> 00114 and inner loop dimension <TT>inner_dimension</TT>. 00115 */ 00116 MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & shape, unsigned int inner_dimension) 00117 : base_type(i, shape, inner_dimension) 00118 {} 00119 00120 MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & start, shape_type const & stop, 00121 unsigned int inner_dimension) 00122 : base_type(i, start, stop, inner_dimension) 00123 {} 00124 00125 /** Advance to next starting location. 00126 */ 00127 void operator++() 00128 { 00129 base_type::operator++(); 00130 if(this->point_[level-1] == this->stop_[level-1]) 00131 { 00132 base_type::reset(); 00133 ++this->point_[level]; 00134 ++this->i_.template dim<level>(); 00135 } 00136 } 00137 00138 /** Advance to next starting location. 00139 */ 00140 void operator++(int) 00141 { 00142 ++*this; 00143 } 00144 00145 /** true if there are more elements. 00146 */ 00147 bool hasMore() const 00148 { 00149 return this->point_[level] < this->stop_[level]; 00150 } 00151 00152 /** true if iterator is exhausted. 00153 */ 00154 bool atEnd() const 00155 { 00156 return this->point_[level] >= this->stop_[level]; 00157 } 00158 00159 protected: 00160 void reset() 00161 { 00162 this->point_[level] = this->start_[level]; 00163 this->i_.template dim<level>() -= (this->stop_[level] - this->start_[level]); 00164 } 00165 }; 00166 00167 template <class MULTI_ITERATOR> 00168 class MultiArrayNavigator<MULTI_ITERATOR, 1> 00169 { 00170 public: 00171 enum { level = 0 }; 00172 typedef typename MULTI_ITERATOR::multi_difference_type shape_type; 00173 typedef typename MULTI_ITERATOR::iterator iterator; 00174 00175 MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & shape, unsigned int inner_dimension) 00176 : start_(), stop_(shape), point_(start_), 00177 inner_dimension_(inner_dimension), 00178 inner_shape_(stop_[inner_dimension] - start_[inner_dimension]), 00179 i_(i + start_) 00180 { 00181 stop_[inner_dimension] = start_[inner_dimension] + 1; 00182 } 00183 00184 MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & start, shape_type const & stop, 00185 unsigned int inner_dimension) 00186 : start_(start), stop_(stop), point_(start_), 00187 inner_dimension_(inner_dimension), 00188 inner_shape_(stop_[inner_dimension] - start_[inner_dimension]), 00189 i_(i + start_) 00190 { 00191 stop_[inner_dimension] = start_[inner_dimension] + 1; 00192 } 00193 00194 void operator++() 00195 { 00196 ++point_[level]; 00197 ++i_.template dim<level>(); 00198 } 00199 00200 void operator++(int) 00201 { 00202 ++*this; 00203 } 00204 00205 iterator begin() const 00206 { 00207 return i_.iteratorForDimension(inner_dimension_); 00208 } 00209 00210 iterator end() const 00211 { 00212 return begin() + inner_shape_; 00213 } 00214 00215 bool hasMore() const 00216 { 00217 return point_[level] < stop_[level]; 00218 } 00219 00220 bool atEnd() const 00221 { 00222 return point_[level] >= stop_[level]; 00223 } 00224 00225 shape_type const & point() const 00226 { 00227 return point_; 00228 } 00229 00230 protected: 00231 void reset() 00232 { 00233 point_[level] = start_[level]; 00234 i_.template dim<level>() -= (stop_[level] - start_[level]); 00235 } 00236 00237 shape_type start_, stop_, point_; 00238 unsigned int inner_dimension_, inner_shape_; 00239 MULTI_ITERATOR i_; 00240 }; 00241 00242 /********************************************************/ 00243 /* */ 00244 /* MultiCoordinateNavigator */ 00245 /* */ 00246 /********************************************************/ 00247 00248 /** \brief A navigator that provides access to the 1D subranges of an 00249 n-dimensional range given by an nD shape. 00250 00251 This class works similarly to \ref MultiArrayNavigator, but instead of a 00252 1-dimensional iterator pair, it returns a pair of shapes whose difference 00253 specifies a 1-dimensional range along the desired dimension. That is, when 00254 the navigator refers to dimension <tt>d</tt>, the difference between 00255 <tt>end()</tt> and <tt>begin()</tt> is <tt>1</tt> along all dimensions 00256 except <tt>d</tt>. 00257 00258 The template parameters specifies the dimension of the shape. 00259 00260 <b>Usage:</b> 00261 00262 <b>\#include</b> <vigra/navigator.hxx> 00263 00264 Namespace: vigra 00265 00266 \code 00267 typedef vigra::MultiArrayShape<3>::type Shape; 00268 typedef vigra::MultiArray<3, int> Array; 00269 typedef vigra::MultiCoordinateNavigator<3> Navigator; 00270 00271 Array a(Shape(X, Y, Z)); 00272 00273 for(int d=0; d<3; ++d) 00274 { 00275 // create Navigator for dimension d 00276 Navigator nav(a.shape(), d); 00277 00278 // outer loop: move navigator to all starting points 00279 // of 1D subsets that run parallel to coordinate axis d 00280 for(; nav.hasMore(); ++nav) 00281 { 00282 // inner loop: linear iteration over current subset 00283 // d == {0, 1, 2}: iterate along {x, y, z}-axis respectively 00284 Shape point = nav.begin(), end = nav.end(); 00285 for(; point[d] != end[d]; ++point[d]) 00286 a[point] = 5; 00287 } 00288 } 00289 \endcode 00290 */ 00291 template <unsigned int Dimensions, unsigned int N = Dimensions> 00292 class MultiCoordinateNavigator 00293 #ifndef DOXYGEN // doxygen doesn't understand this inheritance 00294 : public MultiCoordinateNavigator<Dimensions, N-1> 00295 #endif 00296 { 00297 typedef MultiCoordinateNavigator<Dimensions, N-1> base_type; 00298 00299 public: 00300 enum { level = N-1 }; 00301 00302 /** The shape type for the given iterator type. 00303 */ 00304 typedef typename MultiArrayShape<Dimensions>::type value_type; 00305 00306 00307 /** Construct navigator for multi-dimensional iterator <TT>i</TT>, array shape <TT>shape</TT> 00308 and inner loop dimension <TT>inner_dimension</TT>. 00309 */ 00310 MultiCoordinateNavigator(value_type const & shape, unsigned int inner_dimension) 00311 : base_type(shape, inner_dimension) 00312 { 00313 this->end_[level] = (this->inner_dimension_ == level) 00314 ? 1 00315 : this->shape_[level]; 00316 } 00317 00318 /** Advance to next starting location. 00319 */ 00320 void operator++() 00321 { 00322 base_type::operator++(); 00323 if(base_type::atEnd() && this->i_[level] < this->end_[level]) 00324 { 00325 ++this->i_[level]; 00326 if(this->i_[level] < this->end_[level]) 00327 base_type::reset(); 00328 } 00329 } 00330 00331 /** Advance to next starting location. 00332 */ 00333 void operator++(int) 00334 { 00335 ++*this; 00336 } 00337 00338 /** true if there are more elements. 00339 */ 00340 bool hasMore() const 00341 { 00342 return this->inner_dimension_ == level 00343 ? base_type::hasMore() 00344 : this->i_[level] < this->end_[level]; 00345 } 00346 00347 /** true if iterator is exhausted. 00348 */ 00349 bool atEnd() const 00350 { 00351 return !hasMore(); 00352 // return this->inner_dimension_ == level 00353 // ? base_type::atEnd() 00354 // : !(this->i_[level] < this->end_[level]); 00355 } 00356 00357 protected: 00358 void reset() 00359 { 00360 this->i_[level] = 0; 00361 this->end_[level] = (this->inner_dimension_ == level) 00362 ? 1 00363 : this->shape_[level]; 00364 base_type::reset(); 00365 } 00366 }; 00367 00368 template <unsigned int Dimensions> 00369 class MultiCoordinateNavigator<Dimensions, 1> 00370 { 00371 public: 00372 enum { level = 0 }; 00373 typedef typename MultiArrayShape<Dimensions>::type value_type; 00374 00375 MultiCoordinateNavigator(value_type const & shape, unsigned int inner_dimension) 00376 : shape_(shape), 00377 inner_dimension_(inner_dimension) 00378 { 00379 end_[level] = (inner_dimension_ == level) 00380 ? 1 00381 : shape_[level]; 00382 } 00383 00384 void operator++() 00385 { 00386 ++i_[level]; 00387 } 00388 00389 void operator++(int) 00390 { 00391 ++*this; 00392 } 00393 00394 value_type const & begin() const 00395 { 00396 return i_; 00397 } 00398 00399 value_type end() const 00400 { 00401 value_type res = i_ + value_type(MultiArrayIndex(1)); 00402 res[inner_dimension_] = shape_[inner_dimension_]; 00403 return res; 00404 } 00405 00406 bool hasMore() const 00407 { 00408 return i_[level] < end_[level]; 00409 } 00410 00411 bool atEnd() const 00412 { 00413 return !hasMore(); 00414 } 00415 00416 protected: 00417 void reset() 00418 { 00419 i_[level] = 0; 00420 end_[level] = (inner_dimension_ == level) 00421 ? 1 00422 : shape_[level]; 00423 } 00424 00425 value_type shape_, i_, end_; 00426 unsigned int inner_dimension_; 00427 }; 00428 00429 } // namespace vigra 00430 00431 #endif /* VIGRA_NAVIGATOR_HXX */
© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) |
html generated using doxygen and Python
|