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

navigator.hxx
1 /************************************************************************/
2 /* */
3 /* Copyright 2004 by Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35 
36 #ifndef VIGRA_NAVIGATOR_HXX
37 #define VIGRA_NAVIGATOR_HXX
38 
39 namespace vigra {
40 
41 /********************************************************/
42 /* */
43 /* MultiArrayNavigator */
44 /* */
45 /********************************************************/
46 
47 /** \brief A navigator that provides access to the 1D subranges of an
48  n-dimensional range given by a \ref vigra::MultiIterator and an nD shape.
49 
50  Normally, the innermost loop of an iteration extends over the innermost
51  dimension of a given array. Sometimes, however, it is necessary to have
52  some other dimension in the inner loop. For example, instead of iterating over
53  the rows, the inner loop should extend over the columns. The class MultiArrayNavigator
54  encapsulates the necessary functionality. Given an arbitrary dimensional
55  array (represented by a vigra::MultiIterator/shape pair), and the desired
56  inner loop dimension <TT>d</TT>, it moves the encapsulated iterator to all possible
57  starting points of 1D subsets along the given dimension (e.g. all columns). By calling
58  <TT>begin()</TT> and <TT>end()</TT>, one can then obtain an STL-compatible 1-dimensional
59  iterator for the current subset.
60 
61  The template parameters specify the embedded iterator type and its dimension.
62 
63  <b>Usage:</b>
64 
65  <b>\#include</b> <vigra/navigator.hxx>
66 
67  Namespace: vigra
68 
69  \code
70  typedef vigra::MultiArray<3, int> Array;
71 
72  Array a(Array::size_type(X, Y, Z));
73 
74  typedef vigra::MultiArrayNavigator<Array::traverser, 3> Navigator;
75 
76  for(int d=0; d<3; ++d)
77  {
78  // create Navigator for dimension d
79  Navigator nav(a.traverser_begin(), a.shape(), d);
80 
81  // outer loop: move navigator to all starting points
82  // of 1D subsets that run parallel to coordinate axis d
83  for(; nav.hasMore(); ++nav)
84  {
85  // inner loop: linear iteration over current subset
86  // d == {0, 1, 2}: iterate along {x, y, z}-axis respectively
87  Navigator::iterator i = nav.begin(), end = nav.end();
88  for(; i != end; ++i)
89  // do something
90  }
91  }
92  \endcode
93 */
94 template <class MULTI_ITERATOR, unsigned int N>
96 #ifndef DOXYGEN // doxygen doesn't understand this inheritance
97 : public MultiArrayNavigator<MULTI_ITERATOR, N-1>
98 #endif
99 {
100  typedef MultiArrayNavigator<MULTI_ITERATOR, N-1> base_type;
101 
102  public:
103  enum { level = N-1 };
104 
105  /** The required shape type for the given iterator type.
106  */
107  typedef typename MULTI_ITERATOR::multi_difference_type shape_type;
108 
109  /** The iterator type for the inner loop (result of begin() and end()).
110  */
111  typedef typename MULTI_ITERATOR::iterator iterator;
112 
113  /** Construct navigator for multi-dimensional iterator <TT>i</TT>, array shape <TT>shape</TT>
114  and inner loop dimension <TT>inner_dimension</TT>.
115  */
116  MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & shape, unsigned int inner_dimension)
117  : base_type(i, shape, inner_dimension)
118  {}
119 
120  MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & start, shape_type const & stop,
121  unsigned int inner_dimension)
122  : base_type(i, start, stop, inner_dimension)
123  {}
124 
125  /** Advance to next starting location.
126  */
127  void operator++()
128  {
130  if(this->point_[level-1] == this->stop_[level-1])
131  {
132  base_type::reset();
133  ++this->point_[level];
134  ++this->i_.template dim<level>();
135  }
136  }
137 
138  /** Advance to next starting location.
139  */
140  void operator++(int)
141  {
142  ++*this;
143  }
144 
145  /** true if there are more elements.
146  */
147  bool hasMore() const
148  {
149  return this->point_[level] < this->stop_[level];
150  }
151 
152  /** true if iterator is exhausted.
153  */
154  bool atEnd() const
155  {
156  return this->point_[level] >= this->stop_[level];
157  }
158 
159  protected:
160  void reset()
161  {
162  this->point_[level] = this->start_[level];
163  this->i_.template dim<level>() -= (this->stop_[level] - this->start_[level]);
164  }
165 };
166 
167 template <class MULTI_ITERATOR>
168 class MultiArrayNavigator<MULTI_ITERATOR, 1>
169 {
170  public:
171  enum { level = 0 };
172  typedef typename MULTI_ITERATOR::multi_difference_type shape_type;
173  typedef typename MULTI_ITERATOR::iterator iterator;
174 
175  MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & shape, unsigned int inner_dimension)
176  : start_(), stop_(shape), point_(start_),
177  inner_dimension_(inner_dimension),
178  inner_shape_(stop_[inner_dimension] - start_[inner_dimension]),
179  i_(i + start_)
180  {
181  stop_[inner_dimension] = start_[inner_dimension] + 1;
182  }
183 
184  MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & start, shape_type const & stop,
185  unsigned int inner_dimension)
186  : start_(start), stop_(stop), point_(start_),
187  inner_dimension_(inner_dimension),
188  inner_shape_(stop_[inner_dimension] - start_[inner_dimension]),
189  i_(i + start_)
190  {
191  stop_[inner_dimension] = start_[inner_dimension] + 1;
192  }
193 
194  void operator++()
195  {
196  ++point_[level];
197  ++i_.template dim<level>();
198  }
199 
200  void operator++(int)
201  {
202  ++*this;
203  }
204 
205  iterator begin() const
206  {
207  return i_.iteratorForDimension(inner_dimension_);
208  }
209 
210  iterator end() const
211  {
212  return begin() + inner_shape_;
213  }
214 
215  bool hasMore() const
216  {
217  return point_[level] < stop_[level];
218  }
219 
220  bool atEnd() const
221  {
222  return point_[level] >= stop_[level];
223  }
224 
225  shape_type const & point() const
226  {
227  return point_;
228  }
229 
230  protected:
231  void reset()
232  {
233  point_[level] = start_[level];
234  i_.template dim<level>() -= (stop_[level] - start_[level]);
235  }
236 
237  shape_type start_, stop_, point_;
238  unsigned int inner_dimension_, inner_shape_;
239  MULTI_ITERATOR i_;
240 };
241 
242 /********************************************************/
243 /* */
244 /* MultiCoordinateNavigator */
245 /* */
246 /********************************************************/
247 
248 /** \brief A navigator that provides access to the 1D subranges of an
249  n-dimensional range given by an nD shape.
250 
251  This class works similarly to \ref MultiArrayNavigator, but instead of a
252  1-dimensional iterator pair, it returns a pair of shapes whose difference
253  specifies a 1-dimensional range along the desired dimension. That is, when
254  the navigator refers to dimension <tt>d</tt>, the difference between
255  <tt>end()</tt> and <tt>begin()</tt> is <tt>1</tt> along all dimensions
256  except <tt>d</tt>.
257 
258  The template parameters specifies the dimension of the shape.
259 
260  <b>Usage:</b>
261 
262  <b>\#include</b> <vigra/navigator.hxx>
263 
264  Namespace: vigra
265 
266  \code
267  typedef vigra::MultiArrayShape<3>::type Shape;
268  typedef vigra::MultiArray<3, int> Array;
269  typedef vigra::MultiCoordinateNavigator<3> Navigator;
270 
271  Array a(Shape(X, Y, Z));
272 
273  for(int d=0; d<3; ++d)
274  {
275  // create Navigator for dimension d
276  Navigator nav(a.shape(), d);
277 
278  // outer loop: move navigator to all starting points
279  // of 1D subsets that run parallel to coordinate axis d
280  for(; nav.hasMore(); ++nav)
281  {
282  // inner loop: linear iteration over current subset
283  // d == {0, 1, 2}: iterate along {x, y, z}-axis respectively
284  Shape point = nav.begin(), end = nav.end();
285  for(; point[d] != end[d]; ++point[d])
286  a[point] = 5;
287  }
288  }
289  \endcode
290 */
291 template <unsigned int Dimensions, unsigned int N = Dimensions>
293 #ifndef DOXYGEN // doxygen doesn't understand this inheritance
294 : public MultiCoordinateNavigator<Dimensions, N-1>
295 #endif
296 {
297  typedef MultiCoordinateNavigator<Dimensions, N-1> base_type;
298 
299  public:
300  enum { level = N-1 };
301 
302  /** The shape type for the given iterator type.
303  */
305 
306 
307  /** Construct navigator for multi-dimensional iterator <TT>i</TT>, array shape <TT>shape</TT>
308  and inner loop dimension <TT>inner_dimension</TT>.
309  */
310  MultiCoordinateNavigator(value_type const & shape, unsigned int inner_dimension)
311  : base_type(shape, inner_dimension)
312  {
313  this->end_[level] = (this->inner_dimension_ == level)
314  ? 1
315  : this->shape_[level];
316  }
317 
318  /** Advance to next starting location.
319  */
320  void operator++()
321  {
323  if(base_type::atEnd() && this->i_[level] < this->end_[level])
324  {
325  ++this->i_[level];
326  if(this->i_[level] < this->end_[level])
327  base_type::reset();
328  }
329  }
330 
331  /** Advance to next starting location.
332  */
333  void operator++(int)
334  {
335  ++*this;
336  }
337 
338  /** true if there are more elements.
339  */
340  bool hasMore() const
341  {
342  return this->inner_dimension_ == level
343  ? base_type::hasMore()
344  : this->i_[level] < this->end_[level];
345  }
346 
347  /** true if iterator is exhausted.
348  */
349  bool atEnd() const
350  {
351  return !hasMore();
352  // return this->inner_dimension_ == level
353  // ? base_type::atEnd()
354  // : !(this->i_[level] < this->end_[level]);
355  }
356 
357  protected:
358  void reset()
359  {
360  this->i_[level] = 0;
361  this->end_[level] = (this->inner_dimension_ == level)
362  ? 1
363  : this->shape_[level];
364  base_type::reset();
365  }
366 };
367 
368 template <unsigned int Dimensions>
369 class MultiCoordinateNavigator<Dimensions, 1>
370 {
371  public:
372  enum { level = 0 };
374 
375  MultiCoordinateNavigator(value_type const & shape, unsigned int inner_dimension)
376  : shape_(shape),
377  inner_dimension_(inner_dimension)
378  {
379  end_[level] = (inner_dimension_ == level)
380  ? 1
381  : shape_[level];
382  }
383 
384  void operator++()
385  {
386  ++i_[level];
387  }
388 
389  void operator++(int)
390  {
391  ++*this;
392  }
393 
394  value_type const & begin() const
395  {
396  return i_;
397  }
398 
399  value_type end() const
400  {
401  value_type res = i_ + value_type(MultiArrayIndex(1));
402  res[inner_dimension_] = shape_[inner_dimension_];
403  return res;
404  }
405 
406  bool hasMore() const
407  {
408  return i_[level] < end_[level];
409  }
410 
411  bool atEnd() const
412  {
413  return !hasMore();
414  }
415 
416  protected:
417  void reset()
418  {
419  i_[level] = 0;
420  end_[level] = (inner_dimension_ == level)
421  ? 1
422  : shape_[level];
423  }
424 
425  value_type shape_, i_, end_;
426  unsigned int inner_dimension_;
427 };
428 
429 } // namespace vigra
430 
431 #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.9.0 (Wed Feb 27 2013)