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 
39 namespace casacore { //# NAMESPACE CASACORE - BEGIN
40 
41 //# Forward Declarations
42 class String;
43 class TableColumn;
44 template<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 // uInt 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 // Vector<uInt> 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 // Int 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 // uInt 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 {
229 public:
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  Int 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).
264  ColumnsIndex (const ColumnsIndex& that);
265 
266  ~ColumnsIndex();
267 
268  // Assignment (copy semantics).
269  ColumnsIndex& operator= (const ColumnsIndex& that);
270 
271  // Are all keys in the index unique?
272  Bool isUnique() const;
273 
274  // Return the names of the columns forming the index.
275  Vector<String> columnNames() const;
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>
287  void setChanged();
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>
310  uInt getRowNumber (Bool& found);
311  uInt 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>
322  Vector<uInt> getRowNumbers (const Record& key);
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  Vector<uInt> getRowNumbers (Bool lowerInclusive, Bool upperInclusive);
334  Vector<uInt> 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 
342 protected:
343  // Copy that object to this.
344  void copy (const ColumnsIndex& that);
345 
346  // Delete all data in the object.
347  void deleteObjects();
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.
354  void create (const Table& table, const Vector<String>& columnNames,
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  uInt 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  Int 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<uInt>& rows, uInt start, uInt end) const;
382 
383 private:
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<uInt> itsDataIndex; //# Row numbers of all keys
411  //# Indices in itsDataIndex for each unique key
413  uInt* itsDataInx; //# pointer to data in itsDataIndex
414  uInt* itsUniqueInx; //# pointer to data in itsUniqueIndex
415 };
416 
417 
419 {
421 }
422 inline 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
const Table & table() const
Get the table for which this index is created.
Definition: ColumnsIndex.h:422
void copy(const ColumnsIndex &that)
Copy that object to this.
Index to one or more columns in a table.
Definition: ColumnsIndex.h:227
Block< Int > itsDataTypes
Definition: ColumnsIndex.h:399
A 1-D Specialization of the Array class.
Definition: ArrayIO.h:45
void readData()
Read the data of the columns forming the index, sort them and form the index.
int Int
Definition: aipstype.h:50
static void copyKeyField(void *field, int dtype, const Record &key)
Fill the internal key field from the corresponding external key.
Main interface class to a read/write table.
Definition: Table.h:149
Block< void * > itsLowerFields
Definition: ColumnsIndex.h:404
uInt getRowNumber(Bool &found)
Find the row number matching the key.
Block< void * > itsUpperFields
Definition: ColumnsIndex.h:405
void deleteObjects()
Delete all data in the object.
Vector< uInt > itsDataIndex
Definition: ColumnsIndex.h:410
String name() const
Return the name of the field.
Definition: RecordField.h:180
Vector< uInt > getRowNumbers()
Find the row numbers matching the key.
Block< void * > itsData
Definition: ColumnsIndex.h:401
Block< Bool > itsColumnChanged
Definition: ColumnsIndex.h:406
Access to an individual field in a record.
Definition: RecordField.h:118
size_t nelements() const
How many elements does this array have? Product of all axis lengths.
Definition: ArrayBase.h:99
Record & accessKey()
Access the key values.
Definition: ColumnsIndex.h:426
void copyKey(Block< void *> fields, const Record &key)
Fill the internal key fields from the corresponding external key.
ColumnsIndex(const Table &, const String &columnName, Compare *compareFunction=0, Bool noSort=False)
Create an index on the given table for the given column.
Description of the fields in a record object.
Definition: RecordDesc.h:105
Int Compare(const Block< void *> &fieldPtrs, const Block< void *> &dataPtrs, const Block< Int > &dataTypes, Int index)
Define the signature of a comparison function.
Definition: ColumnsIndex.h:239
A hierarchical collection of named fields of various types.
Definition: Record.h:180
bool Bool
Define the standard types used by Casacore.
Definition: aipstype.h:42
void makeObjects(const RecordDesc &description)
Make the various internal RecordFieldPtr objects.
void addColumnToDesc(RecordDesc &description, const TableColumn &column)
Add a column to the record description for the keys.
Read/write access to a table column.
Definition: TableColumn.h:98
Bool isUnique() const
Are all keys in the index unique?
Definition: ColumnsIndex.h:418
const Bool False
Definition: aipstype.h:44
Vector< uInt > itsUniqueIndex
Definition: ColumnsIndex.h:412
simple 1-D array
Definition: ArrayIO.h:47
ColumnsIndex & operator=(const ColumnsIndex &that)
Assignment (copy semantics).
void create(const Table &table, const Vector< String > &columnNames, Compare *compareFunction, Bool noSort)
Create the various members in the object.
Vector< String > columnNames() const
Return the names of the columns forming the index.
static Int compare(const Block< void *> &fieldPtrs, const Block< void *> &dataPtrs, const Block< Int > &dataTypes, Int index)
Compare the key in fieldPtrs with the given index entry.
String: the storage and methods of handling collections of characters.
Definition: String.h:223
Block< void * > itsDataVectors
Definition: ColumnsIndex.h:400
uInt bsearch(Bool &found, const Block< void *> &fieldPtrs) const
Do a binary search on itsUniqueIndex for the key in fieldPtrs.
void get(const RecordFieldId &, Bool &value) const
Get the value of the given field.
void fillRowNumbers(Vector< uInt > &rows, uInt start, uInt end) const
Fill the row numbers vector for the given start till end in the itsUniqueIndex vector (end is not inc...
this file contains all the compiler specific defines
Definition: mainpage.dox:28
void setChanged()
Something has changed in the table, so the index has to be recreated.
unsigned int uInt
Definition: aipstype.h:51
static void copyKeyField(RecordFieldPtr< T > &field, const Record &key)
Fill the internal key field from the corresponding external key.
Definition: ColumnsIndex.h:390