00001 // This is core/vnl/vnl_scalar_join_iterator.h 00002 #ifndef vnl_scalar_join_iterator_h_ 00003 #define vnl_scalar_join_iterator_h_ 00004 #ifdef VCL_NEEDS_PRAGMA_INTERFACE 00005 #pragma interface 00006 #endif 00007 //: 00008 // \file 00009 // \brief Database join on matrix columns 00010 // \author Andrew W. Fitzgibbon, Oxford RRG 00011 // \date 27 Dec 96 00012 // 00013 // vnl_scalar_join_iterator implements a fast database join on columns 00014 // of matrices of scalars. "Scalar" here really means that the 00015 // objects have comparison operators. The cost is O(n log n) where 00016 // n is the number of rows, all for the two sorts in the ctor. 00017 // 00018 // CAVEAT: The current implementation fudges multiple occurrences 00019 // of the same key in the source column. For example, 00020 // \verbatim 00021 // join 1 3 and 3 5 on columns 2 and 1 respectively 00022 // 2 3 3 6 00023 // \endverbatim 00024 // should give 00025 // \verbatim 00026 // 1 3 3 5 00027 // 1 3 3 6 00028 // 2 3 3 5 00029 // 2 3 3 6 00030 // \endverbatim 00031 // and it doesn't. Contact awf if you need this to work. 00032 // 00033 // \verbatim 00034 // Modifications 00035 // LSB (Manchester) Documentation Tidied 00036 // Feb.2002 - Peter Vanroose - brief doxygen comment placed on single line 00037 // \endverbatim 00038 // 00039 //----------------------------------------------------------------------------- 00040 00041 #include <vcl_list.h> 00042 #include <vnl/vnl_matrix.h> 00043 00044 template <class T> 00045 class vnl_scalar_join_iterator_indexed_pair; 00046 00047 //: Database join on matrix columns. 00048 // vnl_scalar_join_iterator implements a fast database join on columns 00049 // of matrices of scalars. "Scalar" here really means that the 00050 // objects have comparison operators. The cost is O(n log n) where 00051 // n is the number of rows, all for the two sorts in the ctor. 00052 // 00053 // CAVEAT: The current implementation fudges multiple occurrences 00054 // of the same key in the source column. For example, 00055 // \verbatim 00056 // join 1 3 and 3 5 on columns 2 and 1 respectively 00057 // 2 3 3 6 00058 // \endverbatim 00059 // should give 00060 // \verbatim 00061 // 1 3 3 5 00062 // 1 3 3 6 00063 // 2 3 3 5 00064 // 2 3 3 6 00065 // \endverbatim 00066 // and it doesn't. Contact awf if you need this to work. 00067 00068 template <class T> 00069 class vnl_scalar_join_iterator 00070 { 00071 VCL_SAFE_BOOL_DEFINE; 00072 protected: 00073 unsigned n1; 00074 unsigned n2; 00075 vcl_list<vnl_scalar_join_iterator_indexed_pair<T> >* pI1; 00076 vcl_list<vnl_scalar_join_iterator_indexed_pair<T> >* pI2; 00077 vcl_list<vnl_scalar_join_iterator_indexed_pair<T> >& I1; 00078 vcl_list<vnl_scalar_join_iterator_indexed_pair<T> >& I2; 00079 typename vcl_list<vnl_scalar_join_iterator_indexed_pair<T> >::iterator index1; 00080 typename vcl_list<vnl_scalar_join_iterator_indexed_pair<T> >::iterator index2; 00081 00082 public: 00083 00084 //: Initialize this iterator to the join of relation1(:,column1) and relation2(:,column2). 00085 // The algorithm sorts an array of pointers to each row and 00086 // traversal of the iterator runs through these to produce the join. 00087 // After construction the row1() and row2() methods indicate the first pair. 00088 vnl_scalar_join_iterator(const vnl_matrix<T>& relation1, unsigned column1, 00089 const vnl_matrix<T>& relation2, unsigned column2); 00090 00091 ~vnl_scalar_join_iterator(); 00092 00093 00094 //: Return true if all pairs have been seen. 00095 operator safe_bool () const 00096 { return (!done())? VCL_SAFE_BOOL_TRUE : 0; } 00097 00098 //: Return false if all pairs have been seen. 00099 bool operator!() const 00100 { return (!done())? false : true; } 00101 00102 //: Advance to the next pair. This is prefix ++. 00103 inline vnl_scalar_join_iterator<T>& operator ++ () { next(); return *this; } 00104 00105 bool done() const; 00106 void next(); 00107 00108 //: Return the index of the current row in the first relation. 00109 unsigned row1() const; 00110 //: Return the index of the current row in the second relation. 00111 unsigned row2() const; 00112 00113 private: 00114 // Postfix ++ is private as it would be costly to implement. 00115 vnl_scalar_join_iterator<T> operator++ (int); 00116 00117 #if 0 00118 T object1() const { return *I1[index1].object; } 00119 T object2() const { return *I2[index2].object; } 00120 #endif 00121 }; 00122 00123 //: Helper class to hold the sorted arrays of indices. 00124 template <class T> 00125 class vnl_scalar_join_iterator_indexed_pair 00126 { 00127 public: 00128 const T* object; 00129 int original_index; 00130 00131 vnl_scalar_join_iterator_indexed_pair() {} 00132 vnl_scalar_join_iterator_indexed_pair(const T* object_, int original_index_):object(object_), original_index(original_index_) {} 00133 00134 bool operator == (const vnl_scalar_join_iterator_indexed_pair<T>& that) const; 00135 bool operator < (const vnl_scalar_join_iterator_indexed_pair<T>& that) const; 00136 }; 00137 00138 #endif // vnl_scalar_join_iterator_h_