1function [I, J, X] = find (G, k, search)
2%FIND extract entries from a matrix.
3% [I, J, X] = find (G) extracts the nonzeros from a matrix G.
4% X has the same type as G ('double', 'single', 'int8', ...).
5%
6% Linear 1D indexing (I = find (S) for the MATLAB matrix S) is not yet
7% supported.
8%
9% A GraphBLAS matrix G may contain explicit zero entries, and by default
10% these are excluded from the result.  Use GrB.extracttuples (G) to return
11% these explicit zero entries.
12%
13% For a column vector, I = find (G) returns I as a list of the row indices
14% of nonzeros in G.  For a row vector, I = find (G) returns I as a list of
15% the column indices of nonzeros in G.
16%
17% [...] = find (G, k, 'first') returns the first k nonozeros of G.
18% [...] = find (G, k, 'last')  returns the last k nonozeros of G.
19% For this usage, the first and last k are in terms of nonzeros in the
20% column-major order.
21%
22% See also sparse, GrB.build, GrB.extracttuples.
23
24% SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
25% SPDX-License-Identifier: GPL-3.0-or-later
26
27% FUTURE: add linear indexing
28
29% FUTURE: find (G,k,'first') and find (G,k,'last') are slow, since as
30% they are currently implemented, all entries are extracted and then the
31% first or last k are selected from the extracted tuples.  It would be
32% faster to use a mexFunction that directly accesses the opaque content
33% of G, instead of using GrB_Matrix_extractTuples_*, which always extracts
34% the entire matrix.
35
36if (isobject (G))
37    G = G.opaque ;
38end
39
40if (nargin > 1)
41    k = ceil (double (gb_get_scalar (k))) ;
42    if (k < 1)
43        error ('k must be positive') ;
44    end
45    if (~isequal (gbformat (G), 'by col'))
46        % find (G, k) assumes the matrix is stored by column, so reformat G
47        % if it is stored by row.
48        G = gbnew (G, 'by col') ;
49    end
50end
51
52% prune explicit zeros
53G = gbselect (G, 'nonzero') ;
54
55[m, n] = gbsize (G) ;
56
57if (nargout == 3)
58    [I, J, X] = gbextracttuples (G) ;
59    if (m == 1)
60        I = I' ;
61        J = J' ;
62        X = X' ;
63    end
64elseif (nargout == 2)
65    [I, J] = gbextracttuples (G) ;
66    if (m == 1)
67        I = I' ;
68        J = J' ;
69    end
70else
71    if (m == 1)
72        % extract indices from a row vector
73        [~, I] = gbextracttuples (G) ;
74        I = I' ;
75    elseif (n == 1)
76        % extract indices from a column vector
77        I = gbextracttuples (G) ;
78    else
79        % FUTURE: this does not return the same thing as I = find (G)
80        % in MATLAB. (need to add 1D linear indexing)
81        error ('Linear indexing not yet supported') ;
82        % I = gbextracttuples (G) ;
83    end
84end
85
86if (nargin > 1)
87    % find (G, k, ...): get the first or last k entries
88    if (nargin < 3)
89        search = 'first' ;
90    end
91    n = length (I) ;
92    if (k >= n)
93        % output already has all k first or last entries;
94        % nothing more to do
95    elseif (isequal (search, 'first'))
96        % find (G, k, 'first'): get the first k entries
97        I = I (1:k) ;
98        if (nargout > 1)
99            J = J (1:k) ;
100        end
101        if (nargout > 2)
102            X = X (1:k) ;
103        end
104    elseif (isequal (search, 'last'))
105        % find (G, k, 'last'): get the last k entries
106        I = I (n-k+1:n) ;
107        if (nargout > 1)
108            J = J (n-k+1:n) ;
109        end
110        if (nargout > 2)
111            X = X (n-k+1:n) ;
112        end
113    else
114        error ('invalid search option; must be ''first'' or ''last''') ;
115    end
116end
117
118