Mercurial > octave-dspies

comparison liboctave/util/min-with-nnz.h @ 19006:2e0613dadfee draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
All calls to "find" use the same generic implementation (bug #42408, 42421) * find.cc: Rewrite. Move generic "find" logic to find.h (Ffind) : Changed calls to find_nonzero_elem_idx to find_templated Added unit test for bug #42421 * Array.cc (and .h) (Array::find): Deleted function. Replaced with find::find(Array) from find.h * Array.h: Added typedef for array_iterator (in nz-iterators.h) as Array::iter_type * DiagArray2.h: Added typedef for diag_iterator (in nz-iterators.h) as DiagArray2::iter_type * PermMatrix.h: Added typedef for perm_iterator (in nz-iterators.h) as PermMatrix::iter_type Also added typedef for bool as PermMatrix::element_type (not octave_idx_type) Added an nnz() function (which is an alias for perm_length) and a perm_elem(i) function for retrieving the ith element of the permutation * Sparse.h: Added typedef for sparse_iterator (in nz-iterators.h) as Sparse::iter_type Added a short comment documenting the the argument to the numel function * idx-vector.cc (idx_vector::idx_mask_rep::as_array): Changed Array.find to find::find(Array) (in find.h) * (new file) find.h * (new file) interp-idx.h: Simple methods for converting between interpreter index type and internal octave_idx_type/row-col pair * (new file) min-with-nnz.h: Fast methods for taking an arbitrary matrix M and an octave_idx_type n and finding min(M.nnz(), n) * (new file) nz-iterators.h: Iterators for traversing (in column-major order) the nonzero elements of any array or matrix backwards or forwards * (new file) direction.h: Generic methods for simplifying code has to deal with a "backwards or forwards" template argument * build-sparse-tests.sh: Removed 5-return-value calls to "find" in unit-tests; Admittedly this commit breaks this "feature" which was undocumented and only partially supported to begin with (ie never worked for full matrices, permutation matrices, or diagonal matrices)
author David Spies <dnspies@gmail.com>
date Tue, 17 Jun 2014 16:41:11 -0600
parents
children
comparison
equal deleted inserted replaced
19003:d00f6b09258f 19006:2e0613dadfee
1 /*
2
3 Copyright (C) 2014 David Spies
4
5 This file is part of Octave.
6
7 Octave is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 Octave is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Octave; see the file COPYING. If not, see
19 <http://www.gnu.org/licenses/>.
20
21 */
22 #if !defined (octave_min_with_nnz_h)
23 #define octave_min_with_nnz_h 1
24
25 #include "Sparse.h"
26 #include "direction.h"
27
28 // Generic efficient methods for finding the equivalent of
29 // min(arr.nnz(), minwith). In case arr.nnz() happens to run
30 // in O(arr.numel()) time, this operation will short-circuit and return
31 // as soon as it counts minwith nonzero elements.
32 // But if arr has a constant-time nnz() operation, then this will use
33 // that instead and run in constant-time.
34
35 template<typename M>
36 octave_idx_type
37 min_with_nnz (M arr, octave_idx_type minwith)
38 {
39 octave_idx_type count;
40 typename M::iter_type iter (arr);
41 dir_handler<FORWARD> dirc;
42 for (iter.begin (dirc), count = 0; !iter.finished (dirc) && count < minwith;
43 iter.step (dirc), ++count);
44 return count;
45 }
46
47 template<typename T>
48 octave_idx_type
49 min_with_nnz (Sparse<T> arr, octave_idx_type minwith)
50 {
51 return std::min (arr.nnz (), minwith);
52 }
53
54 // FIXME: I want to add one for PermMatrix, but for some reason C++ doesn't
55 // like it when you overload templated functions with non-templated ones.
56 // Except that PermMatrix is not templated. Anyone know how to handle that?
57 // Should I add a dummy template parameter? (that seems like quite an ugly hack)
58
59 #endif