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.
207  TiledLineStepper (const TiledLineStepper& other);
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.
279  IPosition tileShape() const;
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
casacore::TiledLineStepper::itsTiler
LatticeIndexer itsTiler
Definition: TiledLineStepper.h:338
casacore::IPosition
A Vector of integers, for indexing into Array<T> objects.
Definition: IPosition.h:119
casacore::TiledLineStepper::hangOver
virtual Bool hangOver() const
Function which returns "True" if the increment/decrement operators have moved the cursor position suc...
casacore::TiledLineStepper::subLatticeShape
virtual IPosition subLatticeShape() const
casacore::TiledLineStepper::itsBlc
IPosition itsBlc
Definition: TiledLineStepper.h:333
casacore::TiledLineStepper::reset
virtual void reset()
Function to move the cursor to the beginning of the Lattice.
casacore::TiledLineStepper::cursorShape
virtual IPosition cursorShape() const
Function which returns the shape of the cursor.
casacore::TiledLineStepper::TiledLineStepper
TiledLineStepper()
Prevent the default constructor from being used.
casacore::TiledLineStepper::itsAxisPath
IPosition itsAxisPath
Definition: TiledLineStepper.h:343
casacore::TiledLineStepper
Step a Vector cursor optimally through a tiled Lattice.
Definition: TiledLineStepper.h:192
casacore::TiledLineStepper::itsAxis
uInt itsAxis
Definition: TiledLineStepper.h:345
casacore::TiledLineStepper::atEnd
virtual Bool atEnd() const
Function which returns "True" if an attempt has been made to increment the cursor beyond the end of t...
casacore::TiledLineStepper::blc
virtual IPosition blc() const
Return the bottom left hand corner (blc), top right corner (trc) or step size (increment) used by the...
casacore::TiledLineStepper::itsNsteps
uInt itsNsteps
Definition: TiledLineStepper.h:344
casacore::LatticeNavigator
Abstract base class to steer lattice iterators.
Definition: LatticeNavigator.h:182
casacore::uInt
unsigned int uInt
Definition: aipstype.h:51
casacore::TiledLineStepper::clone
virtual LatticeNavigator * clone() const
Function which returns a pointer to dynamic memory of an exact copy of this instance.
casacore::TiledLineStepper::itsTrc
IPosition itsTrc
Definition: TiledLineStepper.h:334
casacore::TiledLineStepper::ok
virtual Bool ok() const
Function which checks the internal data of this class for correct dimensionality and consistant value...
casacore::TiledLineStepper::~TiledLineStepper
~TiledLineStepper()
casacore::TiledLineStepper::itsTileShape
IPosition itsTileShape
Definition: TiledLineStepper.h:342
casacore::TiledLineStepper::tileShape
IPosition tileShape() const
Function which returns the shape of the "tile" the cursor will iterate through before moving onto the...
casacore::TiledLineStepper::itsStart
Bool itsStart
Definition: TiledLineStepper.h:347
casacore
this file contains all the compiler specific defines
Definition: mainpage.dox:28
casacore::LatticeNavigator::operator--
Bool operator--()
Definition: LatticeNavigator.h:358
casacore::TiledLineStepper::latticeShape
virtual IPosition latticeShape() const
Functions which returns the shape of the Lattice being iterated through.
casacore::LatticeNavigator::operator++
Bool operator++()
Definition: LatticeNavigator.h:354
casacore::TiledLineStepper::cursorAxes
virtual IPosition cursorAxes() const
Function which returns the axes of the cursor.
casacore::TiledLineStepper::itsIndexer
LatticeIndexer itsIndexer
Definition: TiledLineStepper.h:337
casacore::LatticeIndexer
A helper class for stepping through Lattices.
Definition: LatticeIndexer.h:108
casacore::TiledLineStepper::axisPath
virtual const IPosition & axisPath() const
Return the axis path.
casacore::TiledLineStepper::position
virtual IPosition position() const
Function which returns the current position of the beginning of the cursor.
casacore::TiledLineStepper::itsInc
IPosition itsInc
Definition: TiledLineStepper.h:335
casacore::TiledLineStepper::atStart
virtual Bool atStart() const
Function which returns "True" if the cursor is at the beginning of the Lattice, otherwise,...
casacore::TiledLineStepper::endPosition
virtual IPosition endPosition() const
Function which returns the current position of the end of the cursor.
casacore::Bool
bool Bool
Define the standard types used by Casacore.
Definition: aipstype.h:42
casacore::TiledLineStepper::subSection
virtual void subSection(const IPosition &blc, const IPosition &trc)
Functions to specify a "section" of the Lattice to step over.
casacore::TiledLineStepper::itsIndexerCursorPos
IPosition itsIndexerCursorPos
Definition: TiledLineStepper.h:339
casacore::TiledLineStepper::calcCacheSize
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...
casacore::TiledLineStepper::trc
virtual IPosition trc() const
casacore::TiledLineStepper::itsCursorShape
IPosition itsCursorShape
Definition: TiledLineStepper.h:341
casacore::TiledLineStepper::itsTilerCursorPos
IPosition itsTilerCursorPos
Definition: TiledLineStepper.h:340
casacore::TiledLineStepper::operator=
TiledLineStepper & operator=(const TiledLineStepper &other)
The assignment operator uses copy semantics.
casacore::TiledLineStepper::itsEnd
Bool itsEnd
Definition: TiledLineStepper.h:346
casacore::TiledLineStepper::nsteps
virtual uInt nsteps() const
Function to return the number of steps (increments & decrements) taken since construction (or since l...
casacore::TiledLineStepper::increment
virtual IPosition increment() const
casacore::TiledLineStepper::itsSubSection
LatticeIndexer itsSubSection
Definition: TiledLineStepper.h:336