00001 #ifndef vnl_index_sort_h_
00002 #define vnl_index_sort_h_
00003
00004
00005
00006
00007
00008 #include <vnl/vnl_vector.h>
00009 #include <vcl_algorithm.h>
00010 #include <vcl_utility.h>
00011 #include <vcl_vector.h>
00012
00013
00014 template <class TValue, class TIndex>
00015 class vnl_index_sort
00016 {
00017 public:
00018
00019
00020 typedef vnl_vector<TValue> SortVectorType;
00021 typedef vnl_vector<TIndex> SortVectorIndexType;
00022
00023
00024 typedef vnl_matrix<TValue> SortMatrixType;
00025 typedef vnl_matrix<TIndex> SortMatrixIndexType;
00026
00027
00028 enum DirectionType {ByRow, ByColumn} Direction;
00029
00030
00031 void vector_sort(
00032 const SortVectorType& values,
00033 SortVectorIndexType& indices)
00034 {
00035 sortIndices(values, indices);
00036 }
00037
00038
00039 void vector_sort(
00040 const SortVectorType& values,
00041 SortVectorType& sorted_values,
00042 SortVectorIndexType& indices)
00043 {
00044 vector_sort(values, indices);
00045
00046
00047 reindexValues(values, indices, sorted_values);
00048 }
00049
00050
00051 void vector_sort_in_place(
00052 SortVectorType& values,
00053 SortVectorIndexType& indices)
00054 {
00055 vector_sort(values, indices);
00056 SortVectorType tmpValues(values);
00057
00058
00059 reindexValues(tmpValues, indices, values);
00060 }
00061
00062
00063
00064 void matrix_sort(
00065 DirectionType direction,
00066 const SortMatrixType& values,
00067 SortMatrixType& sorted_values,
00068 SortMatrixIndexType& indices)
00069 {
00070 sorted_values.set_size(values.rows(), values.cols());
00071 indices.set_size(values.rows(), values.cols());
00072
00073 SortVectorType valVect;
00074 SortVectorType sortedValVect;
00075 SortVectorIndexType indVect;
00076 for (unsigned int vIx = 0;
00077 vIx < (direction == ByRow ? values.rows() : values.cols()); vIx++)
00078 {
00079 getVector(values, direction, vIx, valVect);
00080 vector_sort(valVect, sortedValVect, indVect);
00081 putVector(sortedValVect, direction, vIx, sorted_values);
00082 putVector(indVect, direction, vIx, indices);
00083 }
00084 }
00085
00086 private:
00087
00088
00089 template <class T, class I>
00090 struct sort_index_compare_functor
00091 {
00092 const T *data;
00093 bool operator () (const I &a, const I &b)
00094 {
00095 return data[a] < data[b];
00096 }
00097 };
00098
00099
00100
00101 void sortIndices(const SortVectorType& v, SortVectorIndexType& s)
00102 {
00103 sort_index_compare_functor<TValue, TIndex> c;
00104 c.data = v.data_block();
00105 s.set_size(v.size());
00106
00107 for (TIndex ix = 0; ix < (TIndex) v.size(); ix++) s[ix] = ix;
00108
00109 vcl_sort(s.begin(), s.end(), c);
00110 }
00111
00112
00113 void reindexValues(
00114 const SortVectorType& values,
00115 const SortVectorIndexType& indices,
00116 SortVectorType& sorted_values)
00117 {
00118 sorted_values.set_size(values.size());
00119 for (TIndex ix = 0; ix < (TIndex) values.size(); ix++)
00120 sorted_values[ix] = values[indices[ix]];
00121 }
00122
00123
00124 template<class T>
00125 void getVector(
00126 const vnl_matrix<T>& fromMat,
00127 DirectionType direction,
00128 int whichVect,
00129 vnl_vector<T>& toVect)
00130 {
00131 switch (direction)
00132 {
00133 case ByRow:
00134 toVect = fromMat.get_row(whichVect);
00135 break;
00136 case ByColumn:
00137 toVect = fromMat.get_column(whichVect);
00138 break;
00139 default:
00140 toVect.clear();
00141 break;
00142 }
00143 }
00144
00145
00146 template<class T>
00147 void putVector(
00148 const vnl_vector<T>& fromVect,
00149 DirectionType direction,
00150 int whichVect,
00151 vnl_matrix<T>& toMat)
00152 {
00153 switch (direction)
00154 {
00155 case ByRow:
00156 toMat.set_row(whichVect, fromVect);
00157 break;
00158 case ByColumn:
00159 toMat.set_column(whichVect, fromVect);
00160 break;
00161 default:
00162 break;
00163 }
00164 }
00165 };
00166
00167 #endif