octave_packages/m/general/sortrows.m

   1 ## Copyright (C) 2000-2012 Daniel Calvelo
   2 ## Copyright (C) 2009 Jaroslav Hajek
   3 ##
   4 ## This file is part of Octave.
   5 ##
   6 ## Octave is free software; you can redistribute it and/or modify it
   7 ## under the terms of the GNU General Public License as published by
   8 ## the Free Software Foundation; either version 3 of the License, or (at
   9 ## your option) any later version.
  10 ##
  11 ## Octave is distributed in the hope that it will be useful, but
  12 ## WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 ## General Public License for more details.
  15 ##
  16 ## You should have received a copy of the GNU General Public License
  17 ## along with Octave; see the file COPYING.  If not, see
  18 ## <http://www.gnu.org/licenses/>.
  19
  20 ## -*- texinfo -*-
  21 ## @deftypefn  {Function File} {[@var{s}, @var{i}] =} sortrows (@var{A})
  22 ## @deftypefnx {Function File} {[@var{s}, @var{i}] =} sortrows (@var{A}, @var{c})
  23 ## Sort the rows of the matrix @var{A} according to the order of the
  24 ## columns specified in @var{c}.  If @var{c} is omitted, a
  25 ## lexicographical sort is used.  By default ascending order is used
  26 ## however if elements of @var{c} are negative then the corresponding
  27 ## column is sorted in descending order.
  28 ## @seealso{sort}
  29 ## @end deftypefn
  30
  31 ## Author: Daniel Calvelo, Paul Kienzle
  32 ## Adapted-by: jwe
  33
  34 function [s, i] = sortrows (A, c)
  35
  36   if (nargin < 1 || nargin > 2)
  37     print_usage ();
  38   endif
  39
  40   if (nargin == 2)
  41     if (! (isnumeric (c) && isvector (c)))
  42       error ("sortrows: C must be a numeric vector");
  43     elseif (any (c == 0) || any (abs (c) > columns (A)))
  44       error ("sortrows: all elements of C must be in the range [1, columns (A)]");
  45     endif
  46   endif
  47
  48   default_mode = "ascend";
  49   reverse_mode = "descend";
  50
  51   if (issparse (A))
  52     ## FIXME: Eliminate this case once __sort_rows_idx__ is fixed to
  53     ##        handle sparse matrices.
  54     if (nargin == 1)
  55       i = sort_rows_idx_generic (default_mode, reverse_mode, A);
  56     else
  57       i = sort_rows_idx_generic (default_mode, reverse_mode, A, c);
  58     endif
  59   elseif (nargin == 1)
  60     i = __sort_rows_idx__ (A, default_mode);
  61   elseif (all (c > 0))
  62     i = __sort_rows_idx__ (A(:,c), default_mode);
  63   elseif (all (c < 0))
  64     i = __sort_rows_idx__ (A(:,-c), reverse_mode);
  65   else
  66     ## Otherwise, fall back to the old algorithm.
  67     i = sort_rows_idx_generic (default_mode, reverse_mode, A, c);
  68   endif
  69
  70   ## Only bother to compute s if needed.
  71   if (isargout (1))
  72     s = A(i,:);
  73   endif
  74
  75 endfunction
  76
  77 function i = sort_rows_idx_generic (default_mode, reverse_mode, m, c)
  78
  79   if (nargin == 3)
  80     indices = [1:columns(m)]';
  81     mode(1:columns(m)) = {default_mode};
  82   else
  83     for j = 1:length (c);
  84       if (c(j) < 0)
  85         mode{j} = reverse_mode;
  86       else
  87         mode{j} = default_mode;
  88       endif
  89     endfor
  90     indices = abs (c(:));
  91   endif
  92
  93   ## Since sort is 'stable' the order of identical elements will be
  94   ## preserved, so by traversing the sort indices in reverse order we
  95   ## will make sure that identical elements in index i are subsorted by
  96   ## index j.
  97   indices = flipud (indices);
  98   mode = flipud (mode');
  99   i = [1:rows(m)]';
 100   for j = 1:length (indices);
 101     [~, idx] = sort (m(i, indices(j)), mode{j});
 102     i = i(idx);
 103   endfor
 104
 105 endfunction
 106
 107
 108 %!test
 109 %! m = [1, 1; 1, 2; 3, 6; 2, 7];
 110 %! c = [1, -2];
 111 %! [x, idx] = sortrows (m, c);
 112 %! [sx, sidx] = sortrows (sparse (m), c);
 113 %! assert (x, [1, 2; 1, 1; 2, 7; 3, 6]);
 114 %! assert (idx, [2; 1; 4; 3]);
 115 %! assert (issparse (sx));
 116 %! assert (x, full (sx));
 117 %! assert (idx, sidx);
 118
 119 %!test
 120 %! m = [1, 0, 0, 4];
 121 %! c = 1;
 122 %! [x, idx] = sortrows (m, c);
 123 %! [sx, sidx] = sortrows (sparse (m), c);
 124 %! assert (x, m);
 125 %! assert (idx, 1);
 126 %! assert (issparse (sx));
 127 %! assert (x, full (sx));
 128 %! assert (idx, sidx);
 129
 130 %% Test input validation
 131 %!error sortrows ()
 132 %!error sortrows (1, 2, 3)
 133 %!error sortrows (1, "ascend")
 134 %!error sortrows (1, ones (2,2))
 135 %!error sortrows (1, 0)
 136 %!error sortrows (1, 2)
 137