casacore
ColumnsIndex.h
Go to the documentation of this file.
1//# ColumnsIndex.h: Index to one or more columns in a table
2//# Copyright (C) 1998,1999,2001,2002
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 TABLES_COLUMNSINDEX_H
29#define TABLES_COLUMNSINDEX_H
30
31
32//# Includes
33#include <casacore/casa/aips.h>
34#include <casacore/tables/Tables/Table.h>
35#include <casacore/casa/Arrays/Vector.h>
36#include <casacore/casa/Containers/Block.h>
37#include <casacore/casa/Containers/Record.h>
38
39namespace casacore { //# NAMESPACE CASACORE - BEGIN
40
41//# Forward Declarations
42class String;
43class TableColumn;
44template<typename T> class RecordFieldPtr;
45
46// <summary>
47// Index to one or more columns in a table.
48// </summary>
49
50// <use visibility=export>
51
52// <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="tColumnsIndex.cc" demos="">
53// </reviewed>
54
55// <prerequisite>
56// <li> <linkto class=Table>Table</linkto>
57// <li> <linkto class=Record>Record</linkto>
58// <li> <linkto class=RecordFieldPtr>RecordFieldPtr</linkto>
59// </prerequisite>
60
61// <synopsis>
62// This class makes it possible to use transient indices on top
63// of tables in order to speed up the process of finding rows
64// based on a given key or key range.
65// When constructing a <src>ColumnsIndex</src> object, one has to define
66// which columns form the key for this index on the given
67// <src>table</src> object.
68// Only scalar columns are supported. The data in the given columns
69// will be read, sorted (if needed), and stored in memory.
70// When looking up a key or key range, the class will use a fast binary
71// search on the data held in memory.
72// <p>
73// The <src>ColumnsIndex</src> object contains a
74// <linkto class=Record>Record</linkto> object which can be used
75// to define the key to be looked up. The record contains a field for
76// each column in the index (with the same name and data type).
77// The fastest way to fill the key is by creating a
78// <linkto class=RecordFieldPtr>RecordFieldPtr</linkto> object for
79// each field in the record (see the example) and fill it as needed.
80// However, one can also use the <src>Record::define</src> function,
81// but that is slower.
82// <br>
83// A second record is available to define the upper key
84// when a key range has to be looked up. The keys can be accessed
85// using the various <src>accessKey</src> functions.
86// <p>
87// When a key is defined, the <src>getRowNumbers</src> function can be
88// used to find the table rows containing the given key (range).
89// Function <src>getRowNumber</src> can be used if all keys in the index
90// are unique (which can be tested with the <src>isUnique</src> function).
91// <p>
92// Instead of using the internal records holding the keys, one can also
93// pass its own Record object to <src>getRowNumbers</src>.
94// However, it will be slower.
95// <p>
96// When constructing the object, the user can supply his own compare
97// function. The default compare function compares each field of the
98// key in the normal way. A user's compare function makes it possible
99// to compare in a special way. E.g. one could use near instead of ==
100// on floating point fields. Another example (which is shown in one
101// of the examples below) makes it possible to find a key in an
102// index consisting of a time and width.
103// <p>
104// After an index is created, it is possible to change the data
105// in the underlying columns. However, the <src>ColumnsIndex</src> can
106// not detect if the column data have changed. It can only detect if
107// the number of rows has changed. If the column data have changed,
108// the user has to use the <src>setChanged</src> function to indicate
109// that all columns or a particular column has changed.
110// <br>If data have changed, the entire index will be recreated by
111// rereading and optionally resorting the data. This will be deferred
112// until the next key lookup.
113// </synopsis>
114
115// <example>
116// Suppose one has an antenna table with key ANTENNA.
117// <srcblock>
118// // Open the table and make an index for column ANTENNA.
119// Table tab("antenna.tab")
120// ColumnsIndex colInx(tab, "ANTENNA");
121// // Make a RecordFieldPtr for the ANTENNA field in the index key record.
122// // Its data type has to match the data type of the column.
123// RecordFieldPtr<Int> antFld(colInx.accessKey(), "ANTENNA");
124// // Now loop in some way and find the row for the antenna
125// // involved in that loop.
126// Bool found;
127// while (...) {
128// // Fill the key field and get the row number.
129// // ANTENNA is a unique key, so only one row number matches.
130// // Otherwise function getRowNumbers had to be used.
131// *antFld = antenna;
132// rownr_t antRownr = colInx.getRowNumber (found);
133// if (!found) {
134// cout << "Antenna " << antenna << " is unknown" << endl;
135// } else {
136// // antRownr can now be used to get data from that row in
137// // the antenna table.
138// }
139// }
140// </srcblock>
141//
142// The following example shows how multiple keys can be used and how
143// a search on a range can be done.
144// <srcblock>
145// Table tab("sometable")
146// // Note that TIME is the main key.
147// // Also note that stringToVector (in ArrayUtil.h) is a handy
148// // way to convert a String to a Vector<String>.
149// ColumnsIndex colInx(tab, stringToVector("TIME,ANTENNA"));
150// // Make a RecordFieldPtr for the fields in lower and upper key records.
151// RecordFieldPtr<Double> timeLow(colInx.accessLowerKey(), "TIME");
152// RecordFieldPtr<Int> antLow(colInx.accessLowerKey(), "ANTENNA");
153// RecordFieldPtr<Double> timeUpp(colInx.accessUpperKey(), "TIME");
154// RecordFieldPtr<Int> antUpp(colInx.accessUpperKey(), "ANTENNA");
155// while (...) {
156// // Fill the key fields.
157// *timeLow = ...;
158// *antLow = ...;
159// *timeUpp = ...;
160// *antUpp = ...;
161// // Find the row numbers for keys between low and upp (inclusive).
162// RowNumbers rows = colInx.getRowNumbers (True, True);
163// }
164// </srcblock>
165//
166// The following example shows how a specific compare function
167// could look like. A function like this will actually be used in the
168// calibration software.
169// <br>
170// The table for which the index is built, has rows with the TIME as its key.
171// However, each row is valid for a given interval, where TIME gives
172// the middle of the interval and WIDTH the length of the interval.
173// This means that the compare function has to test whether the key
174// is part of the interval.
175// <srcblock>
176// Int myCompare (const Block<void*>& fieldPtrs,
177// const Block<void*>& dataPtrs,
178// const Block<Int>& dataTypes,
179// rownr_t index)
180// {
181// // Assert (for performance only in debug mode) that the correct
182// // fields are used.
183// DebugAssert (dataTypes.nelements() == 2, AipsError);
184// DebugAssert (dataTypes[0] == TpDouble && dataTypes[1] == TpDouble,
185// AipsError);
186// // Now get the key to be looked up
187// // (an awfully looking cast has to be used).
188// const Double key = *(*(const RecordFieldPtr<Double>*)(fieldPtrs[0]));
189// // Get the time and width of the entry to be compared.
190// const Double time = ((const Double*)(dataPtrs[0]))[index];
191// const Double width = ((const Double*)(dataPtrs[1]))[index];
192// const Double start = time - width/2;
193// const Double end = time + width/2;
194// // Test if the key is before, after, or in the interval
195// // (representing less, greater, equal).
196// if (key < start) {
197// return -1;
198// } else if (key > end) {
199// return 1;
200// }
201// return 0;
202// }
203//
204// // Now use this compare function in an actual index.
205// Table tab("sometable")
206// ColumnsIndex colInx(tab, stringToVector("TIME,WIDTH"), myCompare);
207// // Make a RecordFieldPtr for the TIME field in the key record.
208// // Note that although the WIDTH is part of the index, it is
209// // not an actual key. So it does not need to be filled in.
210// RecordFieldPtr<Double> time(colInx.accessLowerKey(), "TIME");
211// Bool found;
212// while (...) {
213// // Fill the key field.
214// *time = ...;
215// // Find the row number for this time.
216// rownr_t rownr = colInx.getRowNumber (found);
217// }
218// </srcblock>
219// </example>
220
221// <motivation>
222// The calibration software needs to lookup keys in calibration tables
223// very frequently. This class makes that process much easier and faster.
224// </motivation>
225
226
228{
229public:
230 // Define the signature of a comparison function.
231 // The first block contains pointers to <src>RecordFieldPtr<T></src>
232 // objects holding the key to be looked up.
233 // The second block contains pointers to the column data.
234 // The <src>index</src> argument gives the index in the column data.
235 // The third block contains data types of those blocks (TpBool, etc.).
236 // The function should return -1 if key is less than data,
237 // 0 if equal, 1 if greater.
238 // <br>An example above shows how a compare function can be used.
239 typedef Int Compare (const Block<void*>& fieldPtrs,
240 const Block<void*>& dataPtrs,
241 const Block<Int>& dataTypes,
242 rownr_t index);
243
244 // Create an index on the given table for the given column.
245 // The column has to be a scalar column.
246 // If <src>noSort==True</src>, the table is already in order of that
247 // column and the sort step will not be done.
248 // The default compare function is provided by this class. It simply
249 // compares each field in the key.
250 ColumnsIndex (const Table&, const String& columnName,
251 Compare* compareFunction = 0, Bool noSort = False);
252
253 // Create an index on the given table for the given columns, thus
254 // the key is formed by multiple columns.
255 // The columns have to be scalar columns.
256 // If <src>noSort==True</src>, the table is already in order of those
257 // columns and the sort step will not be done.
258 // The default compare function is provided by this class. It simply
259 // compares each field in the key.
261 Compare* compareFunction = 0, Bool noSort = False);
262
263 // Copy constructor (copy semantics).
265
267
268 // Assignment (copy semantics).
270
271 // Are all keys in the index unique?
272 Bool isUnique() const;
273
274 // Return the names of the columns forming the index.
276
277 // Get the table for which this index is created.
278 const Table& table() const;
279
280 // Something has changed in the table, so the index has to be recreated.
281 // The 2nd version indicates that a specific column has changed,
282 // so only that column is reread. If that column is not part of the
283 // index, nothing will be done.
284 // <br>Note that the class itself is keeping track if the number of
285 // rows in the table changes.
286 // <group>
288 void setChanged (const String& columnName);
289 // </group>
290
291 // Access the key values.
292 // These functions allow you to create RecordFieldPtr<T> objects
293 // for each field in the key. In this way you can quickly fill in
294 // the key.
295 // <br>The records have a fixed type, so you cannot add or delete fields.
296 // <group>
297 Record& accessKey();
300 // </group>
301
302 // Find the row number matching the key. All keys have to be unique,
303 // otherwise an exception is thrown.
304 // If no match is found, <src>found</src> is set to False.
305 // The 2nd version makes it possible to pass in your own Record
306 // instead of using the internal record via the <src>accessKey</src>
307 // functions. Note that the given Record will be copied to the internal
308 // record, thus overwrites it.
309 // <group>
311 rownr_t getRowNumber (Bool& found, const Record& key);
312 // </group>
313
314 // Find the row numbers matching the key. It should be used instead
315 // of <src>getRowNumber</src> if the same key can exist multiple times.
316 // The 2nd version makes it possible to pass in your own Record
317 // instead of using the internal record via the <src>accessKey</src>
318 // functions. Note that the given Record will be copied to the internal
319 // record, thus overwrites it.
320 // <group>
323 // </group>
324
325 // Find the row numbers matching the key range. The boolean arguments
326 // tell if the lower and upper key are part of the range.
327 // The 2nd version makes it possible to pass in your own Records
328 // instead of using the internal records via the
329 // <src>accessLower/UpperKey</src> functions.
330 // Note that the given Records will be copied to the internal
331 // records, thus overwrite them.
332 // <group>
333 RowNumbers getRowNumbers (Bool lowerInclusive, Bool upperInclusive);
334 RowNumbers getRowNumbers (const Record& lower, const Record& upper,
335 Bool lowerInclusive, Bool upperInclusive);
336 // </group>
337
338 // Fill the internal key field from the corresponding external key.
339 // The data type may differ.
340 static void copyKeyField (void* field, int dtype, const Record& key);
341
342protected:
343 // Copy that object to this.
344 void copy (const ColumnsIndex& that);
345
346 // Delete all data in the object.
348
349 // Add a column to the record description for the keys.
350 void addColumnToDesc (RecordDesc& description,
351 const TableColumn& column);
352
353 // Create the various members in the object.
355 Compare* compareFunction, Bool noSort);
356
357 // Make the various internal <src>RecordFieldPtr</src> objects.
358 void makeObjects (const RecordDesc& description);
359
360 // Read the data of the columns forming the index, sort them and
361 // form the index.
362 void readData();
363
364 // Do a binary search on <src>itsUniqueIndex</src> for the key in
365 // <src>fieldPtrs</src>.
366 // If the key is found, <src>found</src> is set to True and the index
367 // in <src>itsUniqueIndex</src> is returned.
368 // If not found, <src>found</src> is set to False and the index
369 // of the next higher key is returned.
370 rownr_t bsearch (Bool& found, const Block<void*>& fieldPtrs) const;
371
372 // Compare the key in <src>fieldPtrs</src> with the given index entry.
373 // -1 is returned when less, 0 when equal, 1 when greater.
374 static Int compare (const Block<void*>& fieldPtrs,
375 const Block<void*>& dataPtrs,
376 const Block<Int>& dataTypes,
377 rownr_t index);
378
379 // Fill the row numbers vector for the given start till end in the
380 // <src>itsUniqueIndex</src> vector (end is not inclusive).
381 void fillRowNumbers (Vector<rownr_t>& rows, rownr_t start, rownr_t end) const;
382
383private:
384 // Fill the internal key fields from the corresponding external key.
385 void copyKey (Block<void*> fields, const Record& key);
386
387 // Fill the internal key field from the corresponding external key.
388 // The data type may differ.
389 template <typename T>
390 static void copyKeyField (RecordFieldPtr<T>& field, const Record& key)
391 {
392 key.get (field.name(), *field);
393 }
394
401 Block<void*> itsData; //# pointer to data in itsDataVectors
402 //# The following 2 blocks are actually blocks of RecordFieldPtr<T>*.
403 //# They are used for fast access to the records.
408 Bool itsNoSort; //# True = sort is not needed
409 Compare* itsCompare; //# Compare function
410 Vector<rownr_t> itsDataIndex; //# Row numbers of all keys
411 //# Indices in itsDataIndex for each unique key
413 rownr_t* itsDataInx; //# pointer to data in itsDataIndex
414 rownr_t* itsUniqueInx; //# pointer to data in itsUniqueIndex
415};
416
417
419{
421}
422inline const Table& ColumnsIndex::table() const
423{
424 return itsTable;
425}
427{
428 return *itsLowerKeyPtr;
429}
431{
432 return *itsLowerKeyPtr;
433}
435{
436 return *itsUpperKeyPtr;
437}
438
439
440} //# NAMESPACE CASACORE - END
441
442#endif
size_t nelements() const
How many elements does this array have? Product of all axis lengths.
Definition: ArrayBase.h:103
const Table & table() const
Get the table for which this index is created.
Definition: ColumnsIndex.h:422
RowNumbers getRowNumbers()
Find the row numbers matching the key.
RowNumbers getRowNumbers(const Record &key)
RowNumbers getRowNumbers(Bool lowerInclusive, Bool upperInclusive)
Find the row numbers matching the key range.
void copy(const ColumnsIndex &that)
Copy that object to this.
void fillRowNumbers(Vector< rownr_t > &rows, rownr_t start, rownr_t end) const
Fill the row numbers vector for the given start till end in the itsUniqueIndex vector (end is not inc...
void setChanged(const String &columnName)
ColumnsIndex(const Table &, const String &columnName, Compare *compareFunction=0, Bool noSort=False)
Create an index on the given table for the given column.
Vector< rownr_t > itsDataIndex
Definition: ColumnsIndex.h:410
void setChanged()
Something has changed in the table, so the index has to be recreated.
Block< void * > itsUpperFields
Definition: ColumnsIndex.h:405
Block< void * > itsDataVectors
Definition: ColumnsIndex.h:400
void create(const Table &table, const Vector< String > &columnNames, Compare *compareFunction, Bool noSort)
Create the various members in the object.
void readData()
Read the data of the columns forming the index, sort them and form the index.
ColumnsIndex & operator=(const ColumnsIndex &that)
Assignment (copy semantics).
ColumnsIndex(const Table &, const Vector< String > &columnNames, Compare *compareFunction=0, Bool noSort=False)
Create an index on the given table for the given columns, thus the key is formed by multiple columns.
void addColumnToDesc(RecordDesc &description, const TableColumn &column)
Add a column to the record description for the keys.
ColumnsIndex(const ColumnsIndex &that)
Copy constructor (copy semantics).
Block< Bool > itsColumnChanged
Definition: ColumnsIndex.h:406
rownr_t bsearch(Bool &found, const Block< void * > &fieldPtrs) const
Do a binary search on itsUniqueIndex for the key in fieldPtrs.
Block< void * > itsLowerFields
Definition: ColumnsIndex.h:404
static void copyKeyField(void *field, int dtype, const Record &key)
Fill the internal key field from the corresponding external key.
Int Compare(const Block< void * > &fieldPtrs, const Block< void * > &dataPtrs, const Block< Int > &dataTypes, rownr_t index)
Define the signature of a comparison function.
Definition: ColumnsIndex.h:239
Bool isUnique() const
Are all keys in the index unique?
Definition: ColumnsIndex.h:418
void deleteObjects()
Delete all data in the object.
static Int compare(const Block< void * > &fieldPtrs, const Block< void * > &dataPtrs, const Block< Int > &dataTypes, rownr_t index)
Compare the key in fieldPtrs with the given index entry.
static void copyKeyField(RecordFieldPtr< T > &field, const Record &key)
Fill the internal key field from the corresponding external key.
Definition: ColumnsIndex.h:390
Record & accessKey()
Access the key values.
Definition: ColumnsIndex.h:426
Vector< String > columnNames() const
Return the names of the columns forming the index.
void copyKey(Block< void * > fields, const Record &key)
Fill the internal key fields from the corresponding external key.
Block< Int > itsDataTypes
Definition: ColumnsIndex.h:399
Block< void * > itsData
Definition: ColumnsIndex.h:401
Vector< rownr_t > itsUniqueIndex
Definition: ColumnsIndex.h:412
rownr_t getRowNumber(Bool &found, const Record &key)
rownr_t getRowNumber(Bool &found)
Find the row number matching the key.
void makeObjects(const RecordDesc &description)
Make the various internal RecordFieldPtr objects.
RowNumbers getRowNumbers(const Record &lower, const Record &upper, Bool lowerInclusive, Bool upperInclusive)
String name() const
Return the name of the field.
Definition: RecordField.h:180
void get(const RecordFieldId &, Bool &value) const
Get the value of the given field.
String: the storage and methods of handling collections of characters.
Definition: String.h:225
this file contains all the compiler specific defines
Definition: mainpage.dox:28
const Bool False
Definition: aipstype.h:44
int Int
Definition: aipstype.h:50
bool Bool
Define the standard types used by Casacore.
Definition: aipstype.h:42
uInt64 rownr_t
Define the type of a row number in a table.
Definition: aipsxtype.h:46