1 ////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (C) 1998-2021 The Octave Project Developers
4 //
5 // See the file COPYRIGHT.md in the top-level directory of this
6 // distribution or <https://octave.org/copyright/>.
7 //
8 // This file is part of Octave.
9 //
10 // Octave is free software: you can redistribute it and/or modify it
11 // under the terms of the GNU General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // Octave is distributed in the hope that it will be useful, but
16 // WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU General Public License for more details.
19 //
20 // You should have received a copy of the GNU General Public License
21 // along with Octave; see the file COPYING. If not, see
22 // <https://www.gnu.org/licenses/>.
23 //
24 ////////////////////////////////////////////////////////////////////////
25
26 #if defined (HAVE_CONFIG_H)
27 # include "config.h"
28 #endif
29
30 #include <istream>
31 #include <ostream>
32 #include <vector>
33
34 #include "quit.h"
35 #include "lo-ieee.h"
36 #include "lo-mappers.h"
37
38 #include "boolSparse.h"
39 #include "dSparse.h"
40 #include "oct-locbuf.h"
41
42 #include "Sparse-op-defs.h"
43
44 // SparseBoolMatrix class.
45
46 bool
operator ==(const SparseBoolMatrix & a) const47 SparseBoolMatrix::operator == (const SparseBoolMatrix& a) const
48 {
49 octave_idx_type nr = rows ();
50 octave_idx_type nc = cols ();
51 octave_idx_type nz = nnz ();
52 octave_idx_type nr_a = a.rows ();
53 octave_idx_type nc_a = a.cols ();
54 octave_idx_type nz_a = a.nnz ();
55
56 if (nr != nr_a || nc != nc_a || nz != nz_a)
57 return false;
58
59 for (octave_idx_type i = 0; i < nc + 1; i++)
60 if (cidx (i) != a.cidx (i))
61 return false;
62
63 for (octave_idx_type i = 0; i < nz; i++)
64 if (data (i) != a.data (i) || ridx (i) != a.ridx (i))
65 return false;
66
67 return true;
68 }
69
70 bool
operator !=(const SparseBoolMatrix & a) const71 SparseBoolMatrix::operator != (const SparseBoolMatrix& a) const
72 {
73 return !(*this == a);
74 }
75
76 SparseBoolMatrix&
insert(const SparseBoolMatrix & a,octave_idx_type r,octave_idx_type c)77 SparseBoolMatrix::insert (const SparseBoolMatrix& a,
78 octave_idx_type r, octave_idx_type c)
79 {
80 Sparse<bool>::insert (a, r, c);
81 return *this;
82 }
83
84 SparseBoolMatrix&
insert(const SparseBoolMatrix & a,const Array<octave_idx_type> & indx)85 SparseBoolMatrix::insert (const SparseBoolMatrix& a,
86 const Array<octave_idx_type>& indx)
87 {
88 Sparse<bool>::insert (a, indx);
89 return *this;
90 }
91
92 SparseBoolMatrix
concat(const SparseBoolMatrix & rb,const Array<octave_idx_type> & ra_idx)93 SparseBoolMatrix::concat (const SparseBoolMatrix& rb,
94 const Array<octave_idx_type>& ra_idx)
95 {
96 // Don't use numel to avoid all possibility of an overflow
97 if (rb.rows () > 0 && rb.cols () > 0)
98 insert (rb, ra_idx(0), ra_idx(1));
99 return *this;
100 }
101
102 // unary operations
103
104 SparseBoolMatrix
operator !(void) const105 SparseBoolMatrix::operator ! (void) const
106 {
107 octave_idx_type nr = rows ();
108 octave_idx_type nc = cols ();
109 octave_idx_type nz1 = nnz ();
110 octave_idx_type nz2 = nr*nc - nz1;
111
112 SparseBoolMatrix r (nr, nc, nz2);
113
114 octave_idx_type ii = 0;
115 octave_idx_type jj = 0;
116 r.cidx (0) = 0;
117 for (octave_idx_type i = 0; i < nc; i++)
118 {
119 for (octave_idx_type j = 0; j < nr; j++)
120 {
121 if (jj < cidx (i+1) && ridx (jj) == j)
122 jj++;
123 else
124 {
125 r.data (ii) = true;
126 r.ridx (ii++) = j;
127 }
128 }
129 r.cidx (i+1) = ii;
130 }
131
132 return r;
133 }
134
135 // other operations
136
137 // FIXME: Do these really belong here? Maybe they should be in a base class?
138
139 SparseBoolMatrix
all(int dim) const140 SparseBoolMatrix::all (int dim) const
141 {
142 SPARSE_ALL_OP (dim);
143 }
144
145 SparseBoolMatrix
any(int dim) const146 SparseBoolMatrix::any (int dim) const
147 {
148 Sparse<bool> retval;
149 octave_idx_type nr = rows ();
150 octave_idx_type nc = cols ();
151 octave_idx_type nz = nnz ();
152 if (dim == -1)
153 dim = (nr == 1 && nc != 1) ? 1 : 0;
154
155 if (dim == 0)
156 {
157 // Result is a row vector.
158 retval = Sparse<bool> (1, nc);
159 retval.xcidx (0) = 0;
160 for (octave_idx_type i = 0; i < nc; i++)
161 retval.xcidx (i+1) = retval.xcidx (i) + (cidx (i+1) > cidx (i));
162 octave_idx_type new_nz = retval.xcidx (nc);
163 retval.change_capacity (new_nz);
164 std::fill_n (retval.ridx (), new_nz, static_cast<octave_idx_type> (0));
165 std::fill_n (retval.data (), new_nz, true);
166 }
167 else if (dim == 1)
168 {
169 // Result is a column vector.
170 if (nz > nr/4)
171 {
172 // We can use O(nr) memory.
173 Array<bool> tmp (dim_vector (nr, 1), false);
174 for (octave_idx_type i = 0; i < nz; i++)
175 tmp.xelem (ridx (i)) = true;
176 retval = tmp;
177 }
178 else
179 {
180 Array<octave_idx_type> tmp (dim_vector (nz, 1));
181 std::copy_n (ridx (), nz, tmp.fortran_vec ());
182 retval = Sparse<bool> (Array<bool> (dim_vector (1, 1), true),
183 idx_vector (tmp),
184 idx_vector (static_cast<octave_idx_type> (0)),
185 nr, 1, false);
186 }
187 }
188
189 return retval;
190 }
191
192 SparseMatrix
sum(int dim) const193 SparseBoolMatrix::sum (int dim) const
194 {
195 Sparse<double> retval;
196 octave_idx_type nr = rows ();
197 octave_idx_type nc = cols ();
198 octave_idx_type nz = nnz ();
199 if (dim == -1)
200 dim = (nr == 1 && nc != 1) ? 1 : 0;
201
202 if (dim == 0)
203 {
204 // Result is a row vector.
205 retval = Sparse<double> (1, nc);
206 for (octave_idx_type i = 0; i < nc; i++)
207 retval.xcidx (i+1) = retval.xcidx (i) + (cidx (i+1) > cidx (i));
208 octave_idx_type new_nz = retval.xcidx (nc);
209 retval.change_capacity (new_nz);
210 std::fill_n (retval.ridx (), new_nz, static_cast<octave_idx_type> (0));
211 for (octave_idx_type i = 0, k = 0; i < nc; i++)
212 {
213 octave_idx_type c = cidx (i+1) - cidx (i);
214 if (c > 0)
215 retval.xdata (k++) = c;
216 }
217 }
218 else if (dim == 1)
219 {
220 // Result is a column vector.
221 if (nz > nr)
222 {
223 // We can use O(nr) memory.
224 Array<double> tmp (dim_vector (nr, 1), 0);
225 for (octave_idx_type i = 0; i < nz; i++)
226 tmp.xelem (ridx (i)) += 1.0;
227 retval = tmp;
228 }
229 else
230 {
231 Array<octave_idx_type> tmp (dim_vector (nz, 1));
232 std::copy_n (ridx (), nz, tmp.fortran_vec ());
233 retval = Sparse<double> (Array<double> (dim_vector (1, 1), 1.0),
234 idx_vector (tmp),
235 idx_vector (static_cast<octave_idx_type> (0)),
236 nr, 1);
237 }
238 }
239
240 return retval;
241 }
242
243 SparseBoolMatrix
diag(octave_idx_type k) const244 SparseBoolMatrix::diag (octave_idx_type k) const
245 {
246 return Sparse<bool>::diag (k);
247 }
248
249 boolMatrix
matrix_value(void) const250 SparseBoolMatrix::matrix_value (void) const
251 {
252 octave_idx_type nr = rows ();
253 octave_idx_type nc = cols ();
254
255 boolMatrix retval (nr, nc, false);
256 for (octave_idx_type j = 0; j < nc; j++)
257 for (octave_idx_type i = cidx (j); i < cidx (j+1); i++)
258 retval.elem (ridx (i), j) = data (i);
259
260 return retval;
261 }
262
263 std::ostream&
operator <<(std::ostream & os,const SparseBoolMatrix & a)264 operator << (std::ostream& os, const SparseBoolMatrix& a)
265 {
266 octave_idx_type nc = a.cols ();
267
268 // add one to the printed indices to go from
269 // zero-based to one-based arrays
270 for (octave_idx_type j = 0; j < nc; j++)
271 {
272 octave_quit ();
273 for (octave_idx_type i = a.cidx (j); i < a.cidx (j+1); i++)
274 os << a.ridx (i) + 1 << ' ' << j + 1 << ' ' << a.data (i) << "\n";
275 }
276
277 return os;
278 }
279
280 std::istream&
operator >>(std::istream & is,SparseBoolMatrix & a)281 operator >> (std::istream& is, SparseBoolMatrix& a)
282 {
283 typedef SparseBoolMatrix::element_type elt_type;
284
285 return read_sparse_matrix<elt_type> (is, a, octave_read_value<bool>);
286 }
287
288 SparseBoolMatrix
squeeze(void) const289 SparseBoolMatrix::squeeze (void) const
290 {
291 return Sparse<bool>::squeeze ();
292 }
293
294 SparseBoolMatrix
index(const idx_vector & i,bool resize_ok) const295 SparseBoolMatrix::index (const idx_vector& i, bool resize_ok) const
296 {
297 return Sparse<bool>::index (i, resize_ok);
298 }
299
300 SparseBoolMatrix
index(const idx_vector & i,const idx_vector & j,bool resize_ok) const301 SparseBoolMatrix::index (const idx_vector& i, const idx_vector& j,
302 bool resize_ok) const
303 {
304 return Sparse<bool>::index (i, j, resize_ok);
305 }
306
307 SparseBoolMatrix
reshape(const dim_vector & new_dims) const308 SparseBoolMatrix::reshape (const dim_vector& new_dims) const
309 {
310 return Sparse<bool>::reshape (new_dims);
311 }
312
313 SparseBoolMatrix
permute(const Array<octave_idx_type> & vec,bool inv) const314 SparseBoolMatrix::permute (const Array<octave_idx_type>& vec, bool inv) const
315 {
316 return Sparse<bool>::permute (vec, inv);
317 }
318
319 SparseBoolMatrix
ipermute(const Array<octave_idx_type> & vec) const320 SparseBoolMatrix::ipermute (const Array<octave_idx_type>& vec) const
321 {
322 return Sparse<bool>::ipermute (vec);
323 }
324
325 SPARSE_SMS_EQNE_OPS (SparseBoolMatrix, bool)
326 SPARSE_SMS_BOOL_OPS (SparseBoolMatrix, bool)
327
328 SPARSE_SSM_EQNE_OPS (bool, SparseBoolMatrix)
329 SPARSE_SSM_BOOL_OPS (bool, SparseBoolMatrix)
330
331 SPARSE_SMSM_EQNE_OPS (SparseBoolMatrix, SparseBoolMatrix)
332 SPARSE_SMSM_BOOL_OPS (SparseBoolMatrix, SparseBoolMatrix)
333