PLearn 0.1
SortRowsVMatrix.cc
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-2001 Pascal Vincent, Yoshua Bengio, Rejean Ducharme and University of Montreal
00006 // Copyright (C) 2002 Pascal Vincent, Julien Keable, Xavier Saint-Mleux
00007 // Copyright (C) 2003 Olivier Delalleau
00008 //
00009 // Redistribution and use in source and binary forms, with or without
00010 // modification, are permitted provided that the following conditions are met:
00011 //
00012 //  1. Redistributions of source code must retain the above copyright
00013 //     notice, this list of conditions and the following disclaimer.
00014 //
00015 //  2. Redistributions in binary form must reproduce the above copyright
00016 //     notice, this list of conditions and the following disclaimer in the
00017 //     documentation and/or other materials provided with the distribution.
00018 //
00019 //  3. The name of the authors may not be used to endorse or promote
00020 //     products derived from this software without specific prior written
00021 //     permission.
00022 //
00023 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00024 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00025 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00026 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00027 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00028 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00029 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00030 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00031 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00032 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00033 //
00034 // This file is part of the PLearn library. For more information on the PLearn
00035 // library, go to the PLearn Web site at www.plearn.org
00036 
00037 
00038 /* *******************************************************
00039  * $Id: SortRowsVMatrix.cc 9408 2008-08-27 17:47:25Z nouiz $
00040  ******************************************************* */
00041 
00042 #include "SortRowsVMatrix.h"
00043 #include "SubVMatrix.h"
00044 #include <plearn/math/TMat_sort.h>    
00045 
00046 namespace PLearn {
00047 using namespace std;
00048 
00051 PLEARN_IMPLEMENT_OBJECT(
00052     SortRowsVMatrix,
00053     "Sort the samples of a VMatrix according to one (or more) given columns.",
00054     "The implementation is not efficient at all, feel free to improve it !"
00055 );
00056 
00058 // SortRowsVMatrix //
00060 SortRowsVMatrix::SortRowsVMatrix():
00061     ignore_missing_fields(false),
00062     increasing_order(true)
00063 {
00064     warn_if_all_rows_selected = false;
00065 }
00066 
00068 // declareOptions //
00070 void SortRowsVMatrix::declareOptions(OptionList &ol)
00071 {
00072     declareOption(ol, "sort_columns", &SortRowsVMatrix::sort_columns,
00073                                       OptionBase::buildoption,
00074         "Indices of the column(s) that must be sorted (the first one is the\n"
00075         "first criterion).");
00076 
00077     declareOption(ol, "sort_columns_by_name",
00078                   &SortRowsVMatrix::sort_columns_by_name,
00079                   OptionBase::buildoption,
00080         "Names of the column(s) that must be sorted (the first one is the\n"
00081         "first criterion). This option is optional and, if provided, the\n"
00082         "'sort_columns' option will be ignored.");
00083 
00084     declareOption(ol, "ignore_missing_fields",
00085                   &SortRowsVMatrix::ignore_missing_fields,
00086                   OptionBase::buildoption,
00087         "If true, then no error will be thrown when a column given in\n"
00088         "sort_columns or sort_columns_by_name is missing.");
00089 
00090     declareOption(ol, "increasing_order", &SortRowsVMatrix::increasing_order, OptionBase::buildoption,
00091                   "    if set to 1, the data will be sorted in increasing order");
00092 
00093     inherited::declareOptions(ol);
00094 
00095     // Hide unused options.
00096 
00097     redeclareOption(ol, "indices", &SortRowsVMatrix::indices, OptionBase::nosave,
00098                     "The indices are computed at build time.");
00099     redeclareOption(ol, "indices_vmat", &SortRowsVMatrix::indices_vmat, OptionBase::nosave,
00100                     "Unused.");
00101 }
00102 
00104 // makeDeepCopyFromShallowCopy //
00106 void SortRowsVMatrix::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00107 {
00108     deepCopyField(sort_columns,         copies);
00109     deepCopyField(sort_columns_by_name, copies);
00110     inherited::makeDeepCopyFromShallowCopy(copies);
00111 }
00112 
00114 // build //
00116 void SortRowsVMatrix::build()
00117 {
00118     inherited::build();
00119     build_();
00120 }
00121 
00123 // build_ //
00125 void SortRowsVMatrix::build_()
00126 {
00127     if (sort_columns_by_name.isNotEmpty() && source) {
00128         // Convert column names into column indices.
00129         sort_columns.resize(0);
00130         for (int i = 0; i < sort_columns_by_name.length(); i++) {
00131             int idx = source->getFieldIndex(sort_columns_by_name[i],
00132                                             !ignore_missing_fields);
00133             if (idx >= 0)
00134                 sort_columns.append(idx);
00135         }
00136     }
00137     // Check we don't try to sort twice by the same column (this can be confusing).
00138     // Also verify fields do exist, just in case.
00139     if (sort_columns.isNotEmpty()) {
00140         for (int i = 0; i < sort_columns.length(); i++) {
00141             if (!ignore_missing_fields &&
00142                     (sort_columns[i] < 0 || sort_columns[i] >= source->width()))
00143                 PLERROR("In SortRowsVMatrix::build_ - Field with index %d "
00144                         "cannot exist in the source VMatrix, whose width is "
00145                         "%d", sort_columns[i], source->width());
00146             for (int j = i + 1; j < sort_columns.length(); j++) {
00147                 if (sort_columns[j] == sort_columns[i]) {
00148                     PLERROR("In SortRowsVMatrix::build_ - You have a duplicated index in the 'sort_columns' vector");
00149                 }
00150             }
00151         }
00152     }
00153     // Construct the indices vector.
00154     if (source) {
00155         updateMtime(source);
00156         indices = TVec<int>(0, source.length()-1, 1);
00157         if (sort_columns.length() > 1) {
00158             // We need to sort many columns: we use the unefficient method.
00159             sortRows(source, indices, sort_columns, 0, source->length()-1, 0, increasing_order);
00160         } else if (sort_columns.length() > 0) {
00161             // Only sorting one column: we can do this more efficiently.
00162             Mat to_sort(source->length(), 2);
00163             // Fill first column with the column to sort.
00164             to_sort.column(0) << source.subMatColumns(sort_columns[0], 1);
00165             // Fill 2nd column with indices.
00166             to_sort.column(1) << Vec(0, to_sort.length() - 1, 1);
00167 
00168             if (to_sort.column(0).hasMissing()) {
00169                 // We have missing values, so we use the unefficient method
00170                 sortRows(source, indices, sort_columns, 0, source->length()-1,
00171                          0, increasing_order);
00172             } else {
00173                 // Perform the sort.
00174                 PLearn::sortRows(to_sort, 0, increasing_order);
00175                 // Get the indices.
00176                 indices << to_sort.column(1);
00177             }
00178         }
00179         inherited::build(); // Since we have just changed the indices.
00180     }
00181     updateMtime(indices_vmat);
00182 }
00183 
00185 // sortRows //
00187 void SortRowsVMatrix::sortRows(VMat& m, TVec<int>& indices, TVec<int>& sort_columns, int istart, int iend, int colstart, bool increasing_order) {
00188     real best = 0; // Initialization only to prevent compiler warning.
00189     real jval;
00190     int tmp;
00191     bool better;
00192     if (sort_columns.size() > colstart) {
00193         int col = sort_columns[colstart]; // The current column used to perform sorting.
00194         for (int i = istart; i <= iend-1; i++) {
00195             // Let's look for the i-th element of our result.
00196             int i_nan = i;
00197             // Find first non-missing.
00198             while (i_nan <= iend && is_missing(best = m(indices[i_nan],col))) i_nan++;
00199             if (i_nan > iend)
00200                 // All nan !
00201                 break;
00202             else if (i_nan > i) {
00203                 // There were some nans. We swap i_nan and i.
00204                 tmp = indices[i];
00205                 indices[i] = indices[i_nan];
00206                 indices[i_nan] = tmp;
00207             }
00208             for (int j = i+1; j <= iend; j++) {
00209                 better = false;
00210                 jval = m(indices[j],col);
00211                 if (increasing_order && jval < best)
00212                     better = true;
00213                 else if (!increasing_order && jval > best)
00214                     better = true;
00215                 if (better) {
00216                     // Swap i and j.
00217                     tmp = indices[j];
00218                     indices[j] = indices[i];
00219                     indices[i] = tmp;
00220                     best = jval;
00221                 }
00222             }
00223         }
00224         // At this point, we have only sorted according to one column.
00225         if (sort_columns.length() > colstart + 1) {
00226             // There are other sorting criteria.
00227             // Let's find where we need to apply them.
00228             int i = istart;
00229             real val;
00230             while (i <= iend - 1) {
00231                 val = m(indices[i],col);
00232                 int j = i+1;
00233                 while (   j <= iend
00234                           && ( is_equal(m(indices[j],col), val, 1.0)))
00235                     j++;
00236                 j--;
00237                 if (j > i) {
00238                     // There are consecutive elements with the same value for the sorting
00239                     // criterion, thus we must use the other criteria to sort them correctly.
00240                     sortRows(m, indices, sort_columns, i, j, colstart + 1, increasing_order);
00241                 }
00242                 i = j+1;
00243             }
00244         }
00245     }
00246 }
00247 
00248 } // end of namespace PLearn
00249 
00250 
00251 /*
00252   Local Variables:
00253   mode:c++
00254   c-basic-offset:4
00255   c-file-style:"stroustrup"
00256   c-file-offsets:((innamespace . 0)(inline-open . 0))
00257   indent-tabs-mode:nil
00258   fill-column:79
00259   End:
00260 */
00261 // 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