[ 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 acces 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> <<a href="navigator_8hxx-source.html">vigra/navigator.hxx</a>>
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}: interate 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  i_(i),
119  end_(i)
120  {
121  if(inner_dimension != level)
122  end_.template dim<level>() += shape[level];
123  }
124 
125  /** Advance to next starting location.
126  */
127  void operator++()
128  {
130  if(base_type::atEnd() && i_ < end_) // this tests implicitly inner_dimension_ != level
131  {
132  ++i_.template dim<level>();
133  if(i_ < end_)
134  base_type::reset(i_);
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->inner_dimension_ == level ?
151  i_ < end_;
152  }
153 
154  /** true if iterator is exhausted.
155  */
156  bool atEnd() const
157  {
158  return this->inner_dimension_ == level ?
159  base_type::atEnd() :
160  !( i_ < end_);
161  }
162 
163  protected:
164  void reset(MULTI_ITERATOR const & i)
165  {
166  end_ = i_ = i;
167  if(this->inner_dimension_ != level)
168  end_.template dim<level>() += this->shape_[level];
169  base_type::reset(i);
170  }
171 
172  MULTI_ITERATOR i_, end_;
173 };
174 
175 template <class MULTI_ITERATOR>
176 class MultiArrayNavigator<MULTI_ITERATOR, 1>
177 {
178  public:
179  enum { level = 0 };
180  typedef typename MULTI_ITERATOR::multi_difference_type shape_type;
181  typedef typename MULTI_ITERATOR::iterator iterator;
182 
183  MultiArrayNavigator(MULTI_ITERATOR const & i, shape_type const & shape, unsigned int inner_dimension)
184  : shape_(shape),
185  inner_dimension_(inner_dimension),
186  i_(i),
187  end_(i)
188  {
189  if(inner_dimension != level)
190  end_.template dim<level>() += shape[level];
191  }
192 
193  void operator++()
194  {
195  ++i_.template dim<level>();
196  }
197 
198  void operator++(int)
199  {
200  ++*this;
201  }
202 
203  iterator begin() const
204  {
205  return i_.iteratorForDimension(inner_dimension_);
206  }
207 
208  iterator end() const
209  {
210  return begin() + shape_[inner_dimension_];
211  }
212 
213  bool hasMore() const
214  {
215  return i_ < end_;
216  }
217 
218  bool atEnd() const
219  {
220  return !( i_ < end_);
221  }
222 
223  protected:
224  void reset(MULTI_ITERATOR const & i)
225  {
226  end_ = i_ = i;
227  if(inner_dimension_ != level)
228  end_.template dim<level>() += shape_[level];
229  }
230 
231  shape_type shape_;
232  unsigned int inner_dimension_;
233  MULTI_ITERATOR i_, end_;
234 };
235 
236 } // namespace vigra
237 
238 #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.7.1 (Tue Jul 10 2012)