PLearn 0.1
TMat_sort.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // PLearn (A C++ Machine Learning Library)
00004 // Copyright (C) 1998 Pascal Vincent
00005 // Copyright (C) 1999-2002 Pascal Vincent, Yoshua Bengio and University of Montreal
00006 //
00007 
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions are met:
00010 // 
00011 //  1. Redistributions of source code must retain the above copyright
00012 //     notice, this list of conditions and the following disclaimer.
00013 // 
00014 //  2. Redistributions in binary form must reproduce the above copyright
00015 //     notice, this list of conditions and the following disclaimer in the
00016 //     documentation and/or other materials provided with the distribution.
00017 // 
00018 //  3. The name of the authors may not be used to endorse or promote
00019 //     products derived from this software without specific prior written
00020 //     permission.
00021 // 
00022 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00023 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00024 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00025 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00026 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00027 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00028 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00029 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00030 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00031 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00032 // 
00033 // This file is part of the PLearn library. For more information on the PLearn
00034 // library, go to the PLearn Web site at www.plearn.org
00035 
00036 
00037  
00038 
00039 /* *******************************************************      
00040  * $Id: TMat_sort.h 9649 2008-11-06 16:07:34Z ducharme $
00041  * AUTHORS: Pascal Vincent & Yoshua Bengio & Rejean Ducharme
00042  * This file is part of the PLearn library.
00043  ******************************************************* */
00044 
00047 #ifndef TMat_sort_INC
00048 #define TMat_sort_INC
00049 
00050 #include <algorithm>
00051 #include "TVec_impl.h"
00052 #include "TMat_impl.h"
00053 
00054 namespace PLearn {
00055 using namespace std;
00056 
00057 
00058 template<class T> class SelectedIndicesCmp
00059 {
00060 private:
00061     TVec<int> indices;
00062     bool use_less_than; 
00063 
00064 public:
00065     typedef T first_argument_type;
00066     typedef T second_argument_type;
00067     typedef bool result_type;
00068 
00069     SelectedIndicesCmp(TVec<int> the_indices, bool use_lexical_less_than=true)
00070         :indices(the_indices), use_less_than(use_lexical_less_than)
00071     {}
00072 
00073     bool operator()(const T& x, const T& y)
00074     {
00075         int n = indices.length();
00076         if(use_less_than) // lexical <
00077         {
00078             for(int k=0; k<n; k++)
00079             {
00080                 int i = indices[k];
00081                 if(x[i]<y[i])
00082                     return true;
00083                 else if(x[i]>y[i])
00084                     return false;
00085             }
00086             return false;
00087         }
00088         else // lexical >
00089         {
00090             for(int k=0; k<n; k++)
00091             {
00092                 int i = indices[k];
00093                 if(x[i]>y[i])
00094                     return true;
00095                 else if(x[i]<y[i])
00096                     return false;
00097             }
00098             return false;
00099         }
00100     }
00101 };
00102 
00103 template<class T>
00104 void sortRows(TMat<T>& mat, const TVec<int>& key_columns, bool increasing_order=true)
00105 {
00106     SelectedIndicesCmp< Array<T> > cmp(key_columns,increasing_order);
00107     sort(mat.rows_as_arrays_begin(), mat.rows_as_arrays_end(), cmp);
00108 }
00109 
00110 
00112 template<class T>
00113 inline void sortElements(const TVec<T>& vec, bool reverse_elems=false)
00114 {
00115     sort(vec.begin(), vec.end());
00116     if (reverse_elems)
00117         reverse(vec.begin(), vec.end());
00118 }
00119 
00120 
00129 template<class T>
00130 void partialSortRows(const TMat<T>& mat, int k, int sortk=1, int col=0)
00131 {
00132     if (k > mat.length())
00133         PLERROR("In partialSortRows - The number of rows to sort (%d) must "
00134                 "be less than the length of the matrix (%d)",
00135                 k, mat.length());
00136     vector< pair<T,int> > order(mat.length());
00137     typename vector< pair<T,int> >::iterator it = order.begin();
00138     T* ptr = mat.data()+col;
00139     for(int i=0; i<mat.length(); ++i, ptr+=mat.mod(), ++it)
00140     {
00141         it->first = *ptr;
00142         it->second = i;
00143     }
00144 
00145     typename vector< pair<T,int> >::iterator middle = order.begin();
00146     for(int i=0; i<k; ++i, ++middle);
00147 
00148     partial_sort(order.begin(),middle,order.end());
00149     
00150     // Build the new destination position array
00151     // (destpos is the inverse map of order.second)
00152     vector<int> destpos(mat.length());  
00153     for(int i=0; i<mat.length(); ++i)
00154         destpos[order[i].second] = i;
00155 
00156     // Put elements wich are in the rows k to mat.length()-1 at their place if
00157     // their destpos is in the range 0 to k-1. If not, we leave them there.
00158     for(int startpos = mat.length()-1; startpos>=k; startpos--)
00159     {
00160         int dest = destpos[startpos];
00161         if(dest!=-1)
00162         {
00163             while(dest<k)
00164             {
00165                 mat.swapRows(startpos,dest);
00166                 int newdest = destpos[dest];
00167                 destpos[dest] = -1;
00168                 dest = newdest;
00169             }
00170             destpos[startpos] = -1;
00171         }
00172     }
00173 
00174     if(sortk) {
00175         // Put the k firsts rows in the right order
00176         for(int startpos = 0; startpos<k; startpos++)
00177         {
00178             int dest = destpos[startpos];      
00179             if(dest!=-1)
00180             {
00181                 while(dest!=startpos)
00182                 {
00183                     mat.swapRows(startpos,dest);
00184                     int newdest = destpos[dest];
00185                     destpos[dest] = -1;
00186                     dest = newdest;
00187                 }
00188                 destpos[startpos] = -1;
00189             }
00190         }
00191     }
00192 }
00193 
00201 template<class T>
00202 void sortRows(const TMat<T>& mat, int col=0, bool increasing_order=true)
00203 {
00204     vector< pair<T,int> > order(mat.length());
00205     typename vector< pair<T,int> >::iterator it = order.begin();
00206     T* ptr = mat.data()+col;
00207     for(int i=0; i<mat.length(); ++i, ptr+=mat.mod(), ++it)
00208     {
00209         it->first = *ptr;
00210         it->second = i;
00211     }
00212 
00213     if(increasing_order)
00214         sort(order.begin(),order.end());
00215     else 
00216         sort(order.begin(), order.end(), greater< pair<T,int> >() );
00217 
00218     // Build the new destination position array
00219     // (destpos is the inverse map of order.second)
00220     vector<int> destpos(mat.length());  
00221     for(int i=0; i<mat.length(); ++i)
00222         destpos[order[i].second] = i;
00223 
00224     // Now put the full rows in order...
00225     for(int startpos = 0; startpos<mat.length(); startpos++)
00226     {
00227         int dest = destpos[startpos];      
00228         if(dest!=-1)
00229         {
00230             while(dest!=startpos)
00231             {
00232                 mat.swapRows(startpos,dest);
00233                 int newdest = destpos[dest];
00234                 destpos[dest] = -1;
00235                 dest = newdest;
00236             }
00237             destpos[startpos] = -1;
00238         }
00239     }
00240 }
00241 
00242 
00243 
00244 /*   Not taken from Numerical Recipies: This is a quickly written and hihghly unefficient algorithm!   */
00245 /*   Sorts the columns of the given matrix, in ascending order of its rownum row's elements   */
00246 template<class T>
00247 void sortColumns(const TMat<T>& mat, int rownum)
00248 {
00249     int j,jj,i;
00250     T min;
00251     T tmp;
00252     int mincol;
00253   
00254     if(rownum>=mat.length())
00255         PLERROR("In sortColumns: no rownumumn %d in matrix (%dx%d)",rownum,mat.width(),mat.length());
00256 
00257     for(j=0; j<mat.width(); j++)
00258     {
00259         // look, starting from col j, for the col with the minimum rownum element
00260         mincol = j;
00261         min = mat(rownum,j);
00262         for(jj=j; jj<mat.width(); jj++)
00263         {
00264             if(mat(rownum,jj)<min)
00265             {
00266                 min = mat(rownum,jj);
00267                 mincol = jj;
00268             }
00269         }
00270         if(mincol>j) /*   Found a col with inferior value   */
00271         {
00272             /*   So let's exchange cols j and mincol   */
00273             for(i=0; i<mat.length(); i++)
00274             {
00275                 tmp = mat(i,j);
00276                 mat(i,j) = mat(i,mincol);
00277                 mat(i,mincol) = tmp;
00278             }
00279         }
00280     }
00281 }
00282 
00283 
00284 
00285 // returns the position k of x in src such that src[k] <= x < src[k+1]
00286 // (returns -1 if x < src[0]  or  N-1 if x >= src[N-1])
00287 // BE CAREFULL: src must be sort BEFORE the fonction binary_search is called
00288 template<class T>
00289 int binary_search(const TVec<T>& src, T x)
00290 {
00291     const int len = src.length();
00292 
00293     if (x < src[0]) return -1;
00294     else if (x >= src[len-1]) return len-1;
00295 
00296     int start = 0;
00297     int end = len-1;
00298     for (;;) {
00299         int k = (start+end)/2;
00300         if (x >= src[k]  &&  x < src[k+1]) {
00301             if (src[k] == src[k+1]) {
00302                 start = k;
00303                 end = k+1;
00304                 while (start>0  &&  src[start-1]==src[start]) start--;
00305                 while (end<len-1  &&  src[end]==src[end+1]) end++;
00306                 k = (start+end)/2;
00307             }
00308             return k;
00309         }
00310         else if (x > src[k])
00311             start = k+1;
00312         else
00313             end = k;
00314     }
00315 }
00316 
00317 // Binary search according to the given column c of a matrix.  The column
00318 // MUST BE SORTED.  Return the row k such that src(k,c) <= x < src(k+1).
00319 // Returns -1 if x < src(0,c) or N-1 if x >= src(N-1,c).
00320 template <class T>
00321 int binary_search(const TMat<T>& src, int c, T x)
00322 {
00323     const int len = src.length();
00324 
00325     if (x < src(0,c))
00326         return -1;
00327     else if (x >= src(len-1,c))
00328         return len-1;
00329 
00330     int start = 0, end = len-1;
00331     for (;;) {
00332         int k = (start+end)/2;
00333         if (x >= src(k,c) && x < src(k+1,c)) {
00334             if (src(k,c) == src(k+1,c)) {
00335                 start = k;
00336                 end = k+1;
00337                 while (start > 0 && src(start-1,c) == src(start,c))
00338                     --start;
00339                 while (end < len-1 && src(end,c) == src(end+1,c))
00340                     ++end;
00341                 k = (start+end)/2;
00342             }
00343             return k;
00344         }
00345         else if (x > src(k,c))
00346             start = k+1;
00347         else
00348             end = k;
00349     }
00350 }
00351 
00352 
00353 } // end of namespace PLearn
00354  
00355 #endif // TMat_sort_INC
00356 
00357 
00358 /*
00359   Local Variables:
00360   mode:c++
00361   c-basic-offset:4
00362   c-file-style:"stroustrup"
00363   c-file-offsets:((innamespace . 0)(inline-open . 0))
00364   indent-tabs-mode:nil
00365   fill-column:79
00366   End:
00367 */
00368 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines