octave_packages/m/set/unique.m

   1 ## Copyright (C) 2000-2012 Paul Kienzle
   2 ## Copyright (C) 2008-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} {} unique (@var{x})
  22 ## @deftypefnx {Function File} {} unique (@var{x}, "rows")
  23 ## @deftypefnx {Function File} {} unique (@dots{}, "first")
  24 ## @deftypefnx {Function File} {} unique (@dots{}, "last")
  25 ## @deftypefnx {Function File} {[@var{y}, @var{i}, @var{j}] =} unique (@dots{})
  26 ## Return the unique elements of @var{x}, sorted in ascending order.
  27 ## If the input @var{x} is a vector then the output is also a vector with the
  28 ## same orientation (row or column) as the input.  For a matrix input the
  29 ## output is always a column vector.  @var{x} may also be a cell array of
  30 ## strings.
  31 ##
  32 ## If the optional argument @code{"rows"} is supplied, return the unique
  33 ## rows of @var{x}, sorted in ascending order.
  34 ##
  35 ## If requested, return index vectors @var{i} and @var{j} such that
  36 ## @code{x(i)==y} and @code{y(j)==x}.
  37 ##
  38 ## Additionally, if @var{i} is a requested output then one of @code{"first"} or
  39 ## @code{"last"} may be given as an input.  If @code{"last"} is specified,
  40 ## return the highest possible indices in @var{i}, otherwise, if @code{"first"}
  41 ## is specified, return the lowest.  The default is @code{"last"}.
  42 ## @seealso{union, intersect, setdiff, setxor, ismember}
  43 ## @end deftypefn
  44
  45 function [y, i, j] = unique (x, varargin)
  46
  47   if (nargin < 1)
  48     print_usage ();
  49   endif
  50
  51   if (nargin > 1)
  52     ## parse options
  53     if (iscellstr (varargin))
  54       varargin = unique (varargin);
  55       optfirst = strmatch ("first", varargin, "exact") > 0;
  56       optlast = strmatch ("last", varargin, "exact") > 0;
  57       optrows = strmatch ("rows", varargin, "exact") > 0;
  58       if (optfirst && optlast)
  59         error ('unique: cannot specify both "last" and "first"');
  60       elseif (optfirst + optlast + optrows != nargin-1)
  61         error ("unique: invalid option");
  62       endif
  63     else
  64       error ("unique: options must be strings");
  65     endif
  66
  67     if (optrows && iscell (x))
  68       warning ('unique: "rows" is ignored for cell arrays');
  69       optrows = false;
  70     endif
  71   else
  72     optfirst = false;
  73     optrows = false;
  74   endif
  75
  76   ## FIXME -- the operations
  77   ##
  78   ##   match = (y(1:n-1) == y(2:n));
  79   ##   y(idx) = [];
  80   ##
  81   ## are very slow on sparse matrices.  Until they are fixed to be as
  82   ## fast as for full matrices, operate on the nonzero elements of the
  83   ## sparse array as long as we are not operating on rows.
  84
  85   if (issparse (x) && ! optrows && nargout <= 1)
  86     if (nnz (x) < numel (x))
  87       y = unique ([0; (full (nonzeros (x)))], varargin{:});
  88     else
  89       ## Corner case where sparse matrix is actually full
  90       y = unique (full (x), varargin{:});
  91     endif
  92     return;
  93   endif
  94
  95   if (optrows)
  96     n = rows (x);
  97     dim = 1;
  98   else
  99     n = numel (x);
 100     dim = (rows (x) == 1) + 1;
 101   endif
 102
 103   y = x;
 104   ## Special cases 0 and 1
 105   if (n == 0)
 106     if (! optrows && isempty (x) && any (size (x)))
 107       if (iscell (y))
 108         y = cell (0, 1);
 109       else
 110         y = zeros (0, 1, class (y));
 111       endif
 112     endif
 113     i = j = [];
 114     return;
 115   elseif (n == 1)
 116     i = j = 1;
 117     return;
 118   endif
 119
 120   if (optrows)
 121     if (nargout > 1)
 122       [y, i] = sortrows (y);
 123     else
 124       y = sortrows (y);
 125     endif
 126     match = all (y(1:n-1,:) == y(2:n,:), 2);
 127     idx = find (match);
 128     y(idx,:) = [];
 129   else
 130     if (! isvector (y))
 131       y = y(:);
 132     endif
 133     if (nargout > 1)
 134       [y, i] = sort (y);
 135     else
 136       y = sort (y);
 137     endif
 138     if (iscell (y))
 139       match = strcmp (y(1:n-1), y(2:n));
 140     else
 141       match = (y(1:n-1) == y(2:n));
 142     endif
 143     idx = find (match);
 144     y(idx) = [];
 145   endif
 146
 147   if (isargout (3))
 148     j = i;
 149     if (dim == 1)
 150       j(i) = cumsum ([1; !match]);
 151     else
 152       j(i) = cumsum ([1, !match]);
 153     endif
 154   endif
 155
 156   if (isargout (2))
 157     if (optfirst)
 158       i(idx+1) = [];
 159     else
 160       i(idx) = [];
 161     endif
 162   endif
 163
 164 endfunction
 165
 166 %!assert(unique([1 1 2; 1 2 1; 1 1 2]),[1;2])
 167 %!assert(unique([1 1 2; 1 0 1; 1 1 2],'rows'),[1 0 1; 1 1 2])
 168 %!assert(unique([]),[])
 169 %!assert(unique([1]),[1])
 170 %!assert(unique([1 2]),[1 2])
 171 %!assert(unique([1;2]),[1;2])
 172 %!assert(unique([1,NaN,Inf,NaN,Inf]),[1,Inf,NaN,NaN])
 173 %!assert(unique({'Foo','Bar','Foo'}),{'Bar','Foo'})
 174 %!assert(unique({'Foo','Bar','FooBar'}'),{'Bar','Foo','FooBar'}')
 175 %!assert(unique(zeros(1,0)), zeros(0,1))
 176 %!assert(unique(zeros(1,0), 'rows'), zeros(1,0))
 177 %!assert(unique(cell(1,0)), cell(0,1))
 178 %!assert(unique({}), {})
 179 %!assert(unique([1,2,2,3,2,4], 'rows'), [1,2,2,3,2,4])
 180 %!assert(unique([1,2,2,3,2,4]), [1,2,3,4])
 181 %!assert(unique([1,2,2,3,2,4]', 'rows'), [1,2,3,4]')
 182 %!assert(unique(sparse([2,0;2,0])), [0,2]')
 183 %!assert(unique(sparse([1,2;2,3])), [1,2,3]')
 184 %!assert(unique([1,2,2,3,2,4]', 'rows'), [1,2,3,4]')
 185 %!assert(unique(single([1,2,2,3,2,4]), 'rows'), single([1,2,2,3,2,4]))
 186 %!assert(unique(single([1,2,2,3,2,4])), single([1,2,3,4]))
 187 %!assert(unique(single([1,2,2,3,2,4]'), 'rows'), single([1,2,3,4]'))
 188 %!assert(unique(uint8([1,2,2,3,2,4]), 'rows'), uint8([1,2,2,3,2,4]))
 189 %!assert(unique(uint8([1,2,2,3,2,4])), uint8([1,2,3,4]))
 190 %!assert(unique(uint8([1,2,2,3,2,4]'), 'rows'), uint8([1,2,3,4]'))
 191 %!test
 192 %! [a,i,j] = unique([1,1,2,3,3,3,4]);
 193 %! assert(a,[1,2,3,4])
 194 %! assert(i,[2,3,6,7])
 195 %! assert(j,[1,1,2,3,3,3,4])
 196 %!
 197 %!test
 198 %! [a,i,j] = unique([1,1,2,3,3,3,4]','first');
 199 %! assert(a,[1,2,3,4]')
 200 %! assert(i,[1,3,4,7]')
 201 %! assert(j,[1,1,2,3,3,3,4]')
 202 %!
 203 %!test
 204 %! [a,i,j] = unique({'z'; 'z'; 'z'});
 205 %! assert(a,{'z'})
 206 %! assert(i,[3]')
 207 %! assert(j,[1,1,1]')
 208 %!
 209 %!test
 210 %! A=[1,2,3;1,2,3];
 211 %! [a,i,j] = unique(A,'rows');
 212 %! assert(a,[1,2,3])
 213 %! assert(A(i,:),a)
 214 %! assert(a(j,:),A)