casacore
TiledLineStepper.h
Go to the documentation of this file.
1 //# TiledLineStepper.h: Step a Vector cursor optimally through a tiled Lattice
2 //# Copyright (C) 1997,1998,1999,2000
3 //# Associated Universities, Inc. Washington DC, USA.
4 //#
5 //# This library is free software; you can redistribute it and/or modify it
6 //# under the terms of the GNU Library General Public License as published by
7 //# the Free Software Foundation; either version 2 of the License, or (at your
8 //# option) any later version.
9 //#
10 //# This library is distributed in the hope that it will be useful, but WITHOUT
11 //# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 //# FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
13 //# License for more details.
14 //#
15 //# You should have received a copy of the GNU Library General Public License
16 //# along with this library; if not, write to the Free Software Foundation,
17 //# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA.
18 //#
19 //# Correspondence concerning AIPS++ should be addressed as follows:
20 //# Internet email: aips2-request@nrao.edu.
21 //# Postal address: AIPS++ Project Office
22 //# National Radio Astronomy Observatory
23 //# 520 Edgemont Road
24 //# Charlottesville, VA 22903-2475 USA
25 //#
26 //# $Id$
27 
28 #ifndef LATTICES_TILEDLINESTEPPER_H
29 #define LATTICES_TILEDLINESTEPPER_H
30 
31 //# Includes
32 #include <casacore/casa/aips.h>
33 #include <casacore/lattices/Lattices/LatticeNavigator.h>
34 #include <casacore/lattices/Lattices/LatticeIndexer.h>
35 #include <casacore/casa/Arrays/IPosition.h>
36 
37 
38 namespace casacore { //# NAMESPACE CASACORE - BEGIN
39 
40 // <summary>
41 // Step a Vector cursor optimally through a tiled Lattice.
42 // </summary>
43 // <use visibility=export>
44 
45 // <reviewed reviewer="Peter Barnes" date="1999/10/30" tests="tTiledLineStepper.cc">
46 // </reviewed>
47 
48 // <prerequisite>
49 // <li> <linkto class=LatticeNavigator> LatticeNavigator </linkto>
50 // </prerequisite>
51 
52 // <etymology>
53 // TiledLineStepper is used to step a Vector cursor optimally through
54 // a Lattice that is tiled.
55 // </etymology>
56 
57 // <synopsis>
58 // When you wish to traverse a Lattice (say, a PagedArray or an Image) you
59 // will usually create a LatticeIterator. Once created, you may attach a
60 // LatticeNavigator to the iterator. A TiledLineStepper, is a concrete class
61 // derived from the abstract LatticeNavigator that allows you to move
62 // a Vector cursor through the Lattice in a way that will minimize the
63 // amount of cache memory consumed.
64 // <p>
65 // Some Lattices (in particular PagedArrays) are stored (on disk) in
66 // tiles. For an N-dimensional Lattice a tile is an N-dimensional
67 // subsection with fewer elements along each axis. For example a Lattice of
68 // shape [512,512,4,32] may have a tile shape of [32,16,4,16], and there
69 // will be 16*32*1*2 (=1024) tiles in the entire Lattice. To allow efficient
70 // access of the data in a Lattice some tiles are cached in memory. As each
71 // tile may consume a fair bit of memory (in this example 128kBytes,
72 // assuming each element consumes 4 bytes), it is desirable to minimise the
73 // number of tiles held in the cache. But it is also desirable to minimise
74 // the number of times a tiles must be read into or written from the
75 // cache as this may require a time consuming operation like disk I/O.
76 // <p>
77 // Now suppose you wanted to traverse a Lattice with a Vector cursor of
78 // length 512 pixel aligned along the x-axis. Using a
79 // <linkto class=LatticeStepper>LatticeStepper</linkto>, each Vector is
80 // retrieved from the Lattice sequentially and without any consideration of
81 // the underlying tile shape. What is the optimal cache size for the above
82 // example?
83 // <p>
84 // Suppose we have a cache size of 16 ie., the number of tiles along the
85 // x-axis. Then Vectors beginning at positions [0,0,0,0] to [0,15,0,0] will
86 // be stored in the cache. But the next Vector beginning at position
87 // [0,16,0,0] will flush the cache and read in another 16 tiles. This I/O
88 // takes time and will occur 16 times for each plane in the four dimensional
89 // Lattice. Further when the cursor moves to position [0,0,1,0] the 16 tiles
90 // that where initially in the cache will need to be read again. To avoid
91 // all this cache I/O it is better to have a bigger cache.
92 // <p>
93 // Suppose the cache size is 16*32 (=512) ie., enough tiles to contain an
94 // (x,y)-plane. Then the cache size will not be flushed until the cursor is
95 // moved to position [0,0,0,16]. Further the cache will never need to read
96 // back into memory tiles that had previously been stored in there. The
97 // cache is big enough to store tiles until they have been completely
98 // used. But this cache is 64MBytes in size, and consumes too much memory
99 // for many computers.
100 // <p>
101 // This where a TiledLineStepper is useful. Because it knows the shape of the
102 // tiles in the underlying Lattice it moves the cursor to return all the
103 // Vectors in the smallest possible cache of tiles before moving on to the
104 // next set of tiles. Using the above example again, the TiledLineStepper will
105 // move the beginning of the Vector cursor in the following pattern.
106 // <srcblock>
107 // [0,0,0,0], [0,1,0,0], [0,2,0,0], ... [0,15,0,0]
108 // [0,0,1,0], [0,1,1,0], ... [0,15,1,0],
109 // ... [0,15,3,0],
110 // [0,0,0,1], ... [0,15,3,15]
111 // </srcblock>
112 // Moving the Vector cursor through all 16*4*16 (=1024 positions) can be
113 // done by caching only 16 tiles in memory (those along the x-axis). Hence
114 // the cache size need only be 2MBytes in size. Further once all 1024
115 // vectors have been returned it is not necessary to read these 16 tiles
116 // back into memory. All the data in those tiles has already been
117 // accessed. Using a TiledLineStepper rather than a LatticeStepper has,
118 // in this example, resulted in a drop in the required cache size from
119 // 64MBytes down to 2MBytes.
120 // <p>
121 // In constructing a TiledLineStepper, you specify the Lattice shape, the
122 // tile shape and the axis the Vector cursor will be aligned with. Specifying
123 // an axis=0 will align the cursor with the x-axis and axis=2 will produce a
124 // cursor that is along the z-axis. The length of the cursor is always the
125 // same as the number of elements in the Lattice along the axis the cursor
126 // is aligned with.
127 // <br>It is possible to use the function <src>subSection</src> to
128 // traverse only a subsection of the lattice.
129 // <p>
130 // The cursor position can be incremented or decremented to retrieve the next
131 // or previous Vector in the Lattice. The position of the next Vector in the
132 // Lattice will depend on the tile shape, and is described above. Within a tile
133 // the Vector cursor will move first through the x-axis and then the y-axis
134 // (assuming we have a cursor oriented along the z-axis). In general the lower
135 // dimensions will be exhausted (within a tile) before moving the cursor
136 // through higher dimensions. This intra-tile behaviour for cursor movement
137 // extends to the inter-tile movement of the cursor between tiles.
138 // </synopsis>
139 
140 // <example>
141 // This example is of a global function that will do a 2-D inplace
142 // complex Fourier transform of an arbitrary large Lattice (which
143 // must have at least two dimensions).
144 //
145 // A two dimensional transform is done by successive one dimensional
146 // transforms along all the rows and then all the columns in the
147 // lattice. Scoping is used to destroy iterators once they have been
148 // used. This frees up the cache memory associated with the cursor in each
149 // iterator.
150 //
151 // <srcblock>
152 // void FFT2DComplex (Lattice<Complex>& cArray,
153 // const Bool direction)
154 // {
155 // const uInt ndim = cArray.ndim();
156 // AlwaysAssert(ndim > 1, AipsError);
157 // const IPosition latticeShape = cArray.shape();
158 // const uInt nx=latticeShape(0);
159 // const uInt ny=latticeShape(1);
160 // const IPosition tileShape = cArray.niceCursorShape();
161 //
162 // {
163 // TiledLineStepper tsx(latticeShape, tileShape, 0);
164 // LatticeIterator<Complex> lix(cArray, tsx);
165 // FFTServer<Float,Complex> fftx(IPosition(1, nx));
166 // for (lix.reset();!lix.atEnd();lix++) {
167 // fftx.fft(lix.rwVectorCursor(), direction);
168 // }
169 // }
170 // {
171 // TiledLineStepper tsy(latticeShape, tileShape, 1);
172 // LatticeIterator<Complex> liy(cArray, tsy);
173 // FFTServer<Float,Complex> ffty(IPosition(1, ny));
174 // for (liy.reset();!liy.atEnd();liy++) {
175 // ffty.fft(liy.rwVectorCursor(), direction);
176 // }
177 // }
178 // }
179 // </srcblock>
180 // </example>
181 
182 // <motivation>
183 // Moving through a Lattice by equal sized chunks, and without regard
184 // to the nature of the data, is a basic and common procedure.
185 // </motivation>
186 
187 // <todo asof="1997/03/28">
188 // <li> Support for Matrix and higher dimensional cursors can be used.
189 // </todo>
190 
191 
193 {
194 public:
195 
196  // Construct a TiledLineStepper by specifying the Lattice shape,
197  // a tile shape and the axis along which the Vector cursor will lie
198  // (0 means the x-axis). Is is nearly always advisable to make the
199  // tileShape identical to the Lattice tileShape. This can be obtained by
200  // <src>lat.niceCursorShape(lat.advisedMaxPixels())</src>
201  // where <src>lat</src> is a Lattice object.
203  const IPosition& tileShape,
204  const uInt axis);
205 
206  // The copy constructor uses copy semantics.
208 
210 
211  // The assignment operator uses copy semantics.
213 
214  // Increment operator (postfix or prefix version) - move the cursor
215  // forward one step. Returns True if the cursor was moved.
216  virtual Bool operator++(int);
217 
218  // Decrement operator (postfix or prefix version) - move the cursor
219  // backwards one step. Returns True if the cursor was moved.
220  virtual Bool operator--(int);
221 
222  // Function to move the cursor to the beginning of the Lattice. Also
223  // resets the number of steps (<src>nsteps</src> function) to zero.
224  virtual void reset();
225 
226  // Function which returns "True" if the cursor is at the beginning of the
227  // Lattice, otherwise, returns "False"
228  virtual Bool atStart() const;
229 
230  // Function which returns "True" if an attempt has been made to increment
231  // the cursor beyond the end of the Lattice.
232  virtual Bool atEnd() const;
233 
234  // Function to return the number of steps (increments & decrements) taken
235  // since construction (or since last reset). This is a running count of
236  // all cursor movement (operator++ or operator--), even though
237  // N-increments followed by N-decrements will always leave the cursor in
238  // the original position.
239  virtual uInt nsteps() const;
240 
241  // Function which returns the current position of the beginning of the
242  // cursor. The <src>position</src> function is relative to the origin
243  // in the main Lattice.
244  // <group>
245  virtual IPosition position() const;
246  // </group>
247 
248  // Function which returns the current position of the end of the
249  // cursor. The <src>endPosition</src> function is relative to the origin
250  // in the main Lattice.
251  // <group>
252  virtual IPosition endPosition() const;
253  // </group>
254 
255  // Functions which returns the shape of the Lattice being iterated
256  // through. <src>latticeShape</src> always returns the shape of the main
257  // Lattice while <src>subLatticeShape</src> returns the shape of any
258  // sub-Lattice defined using the <src>subSection</src> function.
259  // <group>
260  virtual IPosition latticeShape() const;
261  virtual IPosition subLatticeShape() const;
262  // </group>
263 
264  // Function which returns the shape of the cursor. This always includes
265  // all axes (ie. it includes degenerates axes)
266  virtual IPosition cursorShape() const;
267 
268  // Function which returns the axes of the cursor.
269  virtual IPosition cursorAxes() const;
270 
271  // Function which returns the shape of the "tile" the cursor will iterate
272  // through before moving onto the next tile. THIS IS NOT THE SAME AS THE
273  // TILE SHAPE USED BY THE LATTICE. It is nearly the same except that the
274  // axis the cursor is aligned with is replaced by the shape of the Lattice
275  // on that axis. eg., If a Lattice has a shape of [512,512,4,32] and a
276  // tile shape of [32,16,4,16] then <src>tileShape()</src> will return
277  // [512,16,4,16] if the cursor is along the x-axis and [32,512,4,16] if the
278  // cursor is along the y-axis.
280 
281  // Function which returns "True" if the increment/decrement operators have
282  // moved the cursor position such that part of the cursor beginning or end
283  // is hanging over the edge of the Lattice. This always returns False.
284  virtual Bool hangOver() const;
285 
286  // Functions to specify a "section" of the Lattice to step over. A section
287  // is defined in terms of the Bottom Left Corner (blc), Top Right Corner
288  // (trc), and step size (inc), on ALL of its axes, including degenerate
289  // axes. The step size defaults to one if not specified.
290  // <group>
291  virtual void subSection (const IPosition& blc, const IPosition& trc);
292  virtual void subSection (const IPosition& blc, const IPosition& trc,
293  const IPosition& inc);
294  // </group>
295 
296  // Return the bottom left hand corner (blc), top right corner (trc) or
297  // step size (increment) used by the current sub-Lattice. If no
298  // sub-Lattice has been defined (with the <src>subSection</src> function)
299  // these functions return blc=0, trc=latticeShape-1, increment=1, ie. the
300  // entire Lattice.
301  // <group>
302  virtual IPosition blc() const;
303  virtual IPosition trc() const;
304  virtual IPosition increment() const;
305  // </group>
306 
307  // Return the axis path.
308  // See <linkto class=LatticeStepper>LatticeStepper</linkto> for a
309  // description and examples.
310  virtual const IPosition& axisPath() const;
311 
312  // Function which returns a pointer to dynamic memory of an exact copy
313  // of this instance. The pointer returned by this function must
314  // be deleted externally.
315  virtual LatticeNavigator* clone() const;
316 
317  // Function which checks the internal data of this class for correct
318  // dimensionality and consistant values.
319  // Returns True if everything is fine otherwise returns False
320  virtual Bool ok() const;
321 
322  // Calculate the cache size (in tiles) for this type of access to a lattice
323  // in the given row of the tiled hypercube.
324  virtual uInt calcCacheSize (const IPosition& cubeShape,
325  const IPosition& tileShape,
326  uInt maxCacheSize, uInt bucketSize) const;
327 
328 private:
329  // Prevent the default constructor from being used.
331 
332 
333  IPosition itsBlc; //# Bottom Left Corner
334  IPosition itsTrc; //# Top Right Corner
335  IPosition itsInc; //# Increment
336  LatticeIndexer itsSubSection; //# The current subsection
337  LatticeIndexer itsIndexer; //# For moving within a tile
338  LatticeIndexer itsTiler; //# For moving between tiles
339  IPosition itsIndexerCursorPos; //# The current position of the iterator.
340  IPosition itsTilerCursorPos; //# The current position of the iterator.
341  IPosition itsCursorShape; //# The shape of the cursor for itsIndexer
342  IPosition itsTileShape; //# The tile shape (= itsTiler cursor shape)
343  IPosition itsAxisPath; //# Path for traversing
344  uInt itsNsteps; //# The number of iterator steps taken so far;
345  uInt itsAxis; //# The axis containing the data vector
346  Bool itsEnd; //# Is the cursor beyond the end?
347  Bool itsStart; //# Is the cursor at the beginning?
348 };
349 
350 
351 
352 } //# NAMESPACE CASACORE - END
353 
354 #endif
virtual Bool atEnd() const
Function which returns "True" if an attempt has been made to increment the cursor beyond the end of t...
virtual Bool operator++(int)
Increment operator (postfix or prefix version) - move the cursor forward one step.
virtual IPosition blc() const
Return the bottom left hand corner (blc), top right corner (trc) or step size (increment) used by the...
virtual Bool atStart() const
Function which returns "True" if the cursor is at the beginning of the Lattice, otherwise,...
TiledLineStepper(const TiledLineStepper &other)
The copy constructor uses copy semantics.
TiledLineStepper(const IPosition &latticeShape, const IPosition &tileShape, const uInt axis)
Construct a TiledLineStepper by specifying the Lattice shape, a tile shape and the axis along which t...
TiledLineStepper()
Prevent the default constructor from being used.
virtual const IPosition & axisPath() const
Return the axis path.
virtual Bool ok() const
Function which checks the internal data of this class for correct dimensionality and consistant value...
virtual Bool hangOver() const
Function which returns "True" if the increment/decrement operators have moved the cursor position suc...
virtual void subSection(const IPosition &blc, const IPosition &trc, const IPosition &inc)
virtual uInt calcCacheSize(const IPosition &cubeShape, const IPosition &tileShape, uInt maxCacheSize, uInt bucketSize) const
Calculate the cache size (in tiles) for this type of access to a lattice in the given row of the tile...
virtual IPosition trc() const
virtual IPosition position() const
Function which returns the current position of the beginning of the cursor.
virtual IPosition subLatticeShape() const
virtual IPosition cursorAxes() const
Function which returns the axes of the cursor.
virtual IPosition latticeShape() const
Functions which returns the shape of the Lattice being iterated through.
virtual uInt nsteps() const
Function to return the number of steps (increments & decrements) taken since construction (or since l...
virtual void subSection(const IPosition &blc, const IPosition &trc)
Functions to specify a "section" of the Lattice to step over.
virtual Bool operator--(int)
Decrement operator (postfix or prefix version) - move the cursor backwards one step.
IPosition tileShape() const
Function which returns the shape of the "tile" the cursor will iterate through before moving onto the...
TiledLineStepper & operator=(const TiledLineStepper &other)
The assignment operator uses copy semantics.
virtual LatticeNavigator * clone() const
Function which returns a pointer to dynamic memory of an exact copy of this instance.
virtual void reset()
Function to move the cursor to the beginning of the Lattice.
virtual IPosition cursorShape() const
Function which returns the shape of the cursor.
virtual IPosition increment() const
virtual IPosition endPosition() const
Function which returns the current position of the end of the cursor.
this file contains all the compiler specific defines
Definition: mainpage.dox:28
unsigned int uInt
Definition: aipstype.h:51
bool Bool
Define the standard types used by Casacore.
Definition: aipstype.h:42