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 // 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 {
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  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).
264  ColumnsIndex (const ColumnsIndex& that);
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>
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>
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 
342 protected:
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 
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<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 }
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
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.
Vector< String > columnNames() const
Return the names of the columns forming the index.
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
ColumnsIndex & operator=(const ColumnsIndex &that)
Assignment (copy semantics).
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
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