GNU Octave  4.0.0
A high-level interpreted language, primarily intended for numerical computations, mostly compatible with Matlab
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Pages
boolSparse.cc
Go to the documentation of this file.
1 /*
2 
3 Copyright (C) 2004-2015 David Bateman
4 Copyright (C) 1998-2004 Andy Adler
5 Copyright (C) 2010 VZLU Prague
6 
7 This file is part of Octave.
8 
9 Octave is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3 of the License, or (at your
12 option) any later version.
13 
14 Octave is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with Octave; see the file COPYING. If not, see
21 <http://www.gnu.org/licenses/>.
22 
23 */
24 
25 #ifdef HAVE_CONFIG_H
26 #include <config.h>
27 #endif
28 
29 #include <iostream>
30 #include <vector>
31 
32 #include "quit.h"
33 #include "lo-ieee.h"
34 #include "lo-mappers.h"
35 
36 #include "boolSparse.h"
37 #include "dSparse.h"
38 #include "oct-locbuf.h"
39 
40 #include "Sparse-op-defs.h"
41 
42 // SparseBoolMatrix class.
43 
44 bool
46 {
47  octave_idx_type nr = rows ();
48  octave_idx_type nc = cols ();
49  octave_idx_type nz = nnz ();
50  octave_idx_type nr_a = a.rows ();
51  octave_idx_type nc_a = a.cols ();
52  octave_idx_type nz_a = a.nnz ();
53 
54  if (nr != nr_a || nc != nc_a || nz != nz_a)
55  return false;
56 
57  for (octave_idx_type i = 0; i < nc + 1; i++)
58  if (cidx (i) != a.cidx (i))
59  return false;
60 
61  for (octave_idx_type i = 0; i < nz; i++)
62  if (data (i) != a.data (i) || ridx (i) != a.ridx (i))
63  return false;
64 
65  return true;
66 }
67 
68 bool
70 {
71  return !(*this == a);
72 }
73 
77 {
78  Sparse<bool>::insert (a, r, c);
79  return *this;
80 }
81 
84  const Array<octave_idx_type>& indx)
85 {
86  Sparse<bool>::insert (a, indx);
87  return *this;
88 }
89 
93 {
94  // Don't use numel to avoid all possiblity of an overflow
95  if (rb.rows () > 0 && rb.cols () > 0)
96  insert (rb, ra_idx(0), ra_idx(1));
97  return *this;
98 }
99 
100 // unary operations
101 
104 {
105  octave_idx_type nr = rows ();
106  octave_idx_type nc = cols ();
107  octave_idx_type nz1 = nnz ();
108  octave_idx_type nz2 = nr*nc - nz1;
109 
110  SparseBoolMatrix r (nr, nc, nz2);
111 
112  octave_idx_type ii = 0;
113  octave_idx_type jj = 0;
114  r.cidx (0) = 0;
115  for (octave_idx_type i = 0; i < nc; i++)
116  {
117  for (octave_idx_type j = 0; j < nr; j++)
118  {
119  if (jj < cidx (i+1) && ridx (jj) == j)
120  jj++;
121  else
122  {
123  r.data (ii) = true;
124  r.ridx (ii++) = j;
125  }
126  }
127  r.cidx (i+1) = ii;
128  }
129 
130  return r;
131 }
132 
133 // other operations
134 
135 // FIXME: Do these really belong here? Maybe they should be in a base class?
136 
138 SparseBoolMatrix::all (int dim) const
139 {
140  SPARSE_ALL_OP (dim);
141 }
142 
144 SparseBoolMatrix::any (int dim) const
145 {
146  Sparse<bool> retval;
147  octave_idx_type nr = rows ();
148  octave_idx_type nc = cols ();
149  octave_idx_type nz = nnz ();
150  if (dim == -1)
151  dim = (nr == 1 && nc != 1) ? 1 : 0;
152 
153  if (dim == 0)
154  {
155  // Result is a row vector.
156  retval = Sparse<bool> (1, nc);
157  retval.xcidx (0) = 0;
158  for (octave_idx_type i = 0; i < nc; i++)
159  retval.xcidx (i+1) = retval.xcidx (i) + (cidx (i+1) > cidx (i));
160  octave_idx_type new_nz = retval.xcidx (nc);
161  retval.change_capacity (new_nz);
162  std::fill_n (retval.ridx (), new_nz, static_cast<octave_idx_type> (0));
163  std::fill_n (retval.data (), new_nz, true);
164  }
165  else if (dim == 1)
166  {
167  // Result is a column vector.
168  if (nz > nr/4)
169  {
170  // We can use O(nr) memory.
171  Array<bool> tmp (dim_vector (nr, 1), false);
172  for (octave_idx_type i = 0; i < nz; i++)
173  tmp.xelem (ridx (i)) = true;
174  retval = tmp;
175  }
176  else
177  {
178  Array<octave_idx_type> tmp (dim_vector (nz, 1));
179  std::copy (ridx (), ridx () + nz, tmp.fortran_vec ());
180  retval = Sparse<bool> (Array<bool> (dim_vector (1, 1), true),
181  idx_vector (tmp),
182  idx_vector (static_cast<octave_idx_type> (0)),
183  nr, 1, false);
184  }
185  }
186 
187  return retval;
188 }
189 
191 SparseBoolMatrix::sum (int dim) const
192 {
193  Sparse<double> retval;
194  octave_idx_type nr = rows ();
195  octave_idx_type nc = cols ();
196  octave_idx_type nz = nnz ();
197  if (dim == -1)
198  dim = (nr == 1 && nc != 1) ? 1 : 0;
199 
200  if (dim == 0)
201  {
202  // Result is a row vector.
203  retval = Sparse<double> (1, nc);
204  for (octave_idx_type i = 0; i < nc; i++)
205  retval.xcidx (i+1) = retval.xcidx (i) + (cidx (i+1) > cidx (i));
206  octave_idx_type new_nz = retval.xcidx (nc);
207  retval.change_capacity (new_nz);
208  std::fill_n (retval.ridx (), new_nz, static_cast<octave_idx_type> (0));
209  for (octave_idx_type i = 0, k = 0; i < nc; i++)
210  {
211  octave_idx_type c = cidx (i+1) - cidx (i);
212  if (c > 0)
213  retval.xdata (k++) = c;
214  }
215  }
216  else if (dim == 1)
217  {
218  // Result is a column vector.
219  if (nz > nr)
220  {
221  // We can use O(nr) memory.
222  Array<double> tmp (dim_vector (nr, 1), 0);
223  for (octave_idx_type i = 0; i < nz; i++)
224  tmp.xelem (ridx (i)) += 1.0;
225  retval = tmp;
226  }
227  else
228  {
229  Array<octave_idx_type> tmp (dim_vector (nz, 1));
230  std::copy (ridx (), ridx () + nz, tmp.fortran_vec ());
231  retval = Sparse<double> (Array<double> (dim_vector (1, 1), 1.0),
232  idx_vector (tmp),
233  idx_vector (static_cast<octave_idx_type> (0)),
234  nr, 1);
235  }
236  }
237 
238  return retval;
239 }
240 
243 {
244  return Sparse<bool>::diag (k);
245 }
246 
249 {
250  octave_idx_type nr = rows ();
251  octave_idx_type nc = cols ();
252 
253  boolMatrix retval (nr, nc, false);
254  for (octave_idx_type j = 0; j < nc; j++)
255  for (octave_idx_type i = cidx (j); i < cidx (j+1); i++)
256  retval.elem (ridx (i), j) = data (i);
257 
258  return retval;
259 }
260 
261 std::ostream&
262 operator << (std::ostream& os, const SparseBoolMatrix& a)
263 {
264  octave_idx_type nc = a.cols ();
265 
266  // add one to the printed indices to go from
267  // zero-based to one-based arrays
268  for (octave_idx_type j = 0; j < nc; j++)
269  {
270  octave_quit ();
271  for (octave_idx_type i = a.cidx (j); i < a.cidx (j+1); i++)
272  os << a.ridx (i) + 1 << " " << j + 1 << " " << a.data (i) << "\n";
273  }
274 
275  return os;
276 }
277 
278 std::istream&
279 operator >> (std::istream& is, SparseBoolMatrix& a)
280 {
281  typedef SparseBoolMatrix::element_type elt_type;
282 
283  return read_sparse_matrix<elt_type> (is, a, octave_read_value<bool>);
284 }
285 
288 {
289  return Sparse<bool>::squeeze ();
290 }
291 
293 SparseBoolMatrix::index (const idx_vector& i, bool resize_ok) const
294 {
295  return Sparse<bool>::index (i, resize_ok);
296 }
297 
300  bool resize_ok) const
301 {
302  return Sparse<bool>::index (i, j, resize_ok);
303 }
304 
306 SparseBoolMatrix::reshape (const dim_vector& new_dims) const
307 {
308  return Sparse<bool>::reshape (new_dims);
309 }
310 
313 {
314  return Sparse<bool>::permute (vec, inv);
315 }
316 
319 {
320  return Sparse<bool>::ipermute (vec);
321 }
322 
323 SPARSE_SMS_EQNE_OPS (SparseBoolMatrix, false, , bool, false, )
325 
326 SPARSE_SSM_EQNE_OPS (bool, false, , SparseBoolMatrix, false, )
327 SPARSE_SSM_BOOL_OPS (bool, SparseBoolMatrix, false)
328 
329 SPARSE_SMSM_EQNE_OPS (SparseBoolMatrix, false, , SparseBoolMatrix, false, )
330 SPARSE_SMSM_BOOL_OPS (SparseBoolMatrix, SparseBoolMatrix, false)
#define SPARSE_SMS_EQNE_OPS(M, MZ, CM, S, SZ, CS)
Sparse< T > ipermute(const Array< octave_idx_type > &vec) const
Definition: Sparse.h:482
octave_idx_type cols(void) const
Definition: Sparse.h:264
boolMatrix matrix_value(void) const
Definition: boolSparse.cc:248
bool * data(void)
Definition: Sparse.h:509
octave_idx_type rows(void) const
Definition: Sparse.h:263
const octave_base_value const Array< octave_idx_type > & ra_idx
std::istream & operator>>(std::istream &is, SparseBoolMatrix &a)
Definition: boolSparse.cc:279
SparseBoolMatrix ipermute(const Array< octave_idx_type > &vec) const
Definition: boolSparse.cc:318
#define SPARSE_SMSM_EQNE_OPS(M1, Z1, C1, M2, Z2, C2)
#define SPARSE_SMSM_BOOL_OPS(M1, M2, ZERO)
octave_idx_type * xcidx(void)
Definition: Sparse.h:537
Sparse< T > index(const idx_vector &i, bool resize_ok=false) const
Definition: Sparse.cc:1387
SparseBoolMatrix permute(const Array< octave_idx_type > &vec, bool inv=false) const
Definition: boolSparse.cc:312
Sparse< T > permute(const Array< octave_idx_type > &vec, bool inv=false) const
Definition: Sparse.cc:882
Sparse< T > & insert(const Sparse< T > &a, octave_idx_type r, octave_idx_type c)
Definition: Sparse.cc:998
octave_idx_type * cidx(void)
Definition: Sparse.h:531
T & elem(octave_idx_type n)
Definition: Array.h:380
bool operator==(const SparseBoolMatrix &a) const
Definition: boolSparse.cc:45
SparseBoolMatrix index(const idx_vector &i, bool resize_ok) const
Definition: boolSparse.cc:293
SparseBoolMatrix reshape(const dim_vector &new_dims) const
Definition: boolSparse.cc:306
octave_idx_type nnz(void) const
Definition: Sparse.h:248
Sparse< T > squeeze(void) const
Definition: Sparse.h:285
SparseMatrix sum(int dim=-1) const
Definition: boolSparse.cc:191
#define SPARSE_ALL_OP(DIM)
#define SPARSE_SSM_EQNE_OPS(S, SZ, SC, M, MZ, MC)
SparseBoolMatrix all(int dim=-1) const
Definition: boolSparse.cc:138
void change_capacity(octave_idx_type nz)
Definition: Sparse.h:493
SparseBoolMatrix operator!(void) const
Definition: boolSparse.cc:103
Sparse< T > reshape(const dim_vector &new_dims) const
Definition: Sparse.cc:815
SparseBoolMatrix concat(const SparseBoolMatrix &rb, const Array< octave_idx_type > &ra_idx)
Definition: boolSparse.cc:91
SparseBoolMatrix & insert(const SparseBoolMatrix &a, octave_idx_type r, octave_idx_type c)
Definition: boolSparse.cc:75
SparseBoolMatrix any(int dim=-1) const
Definition: boolSparse.cc:144
SparseBoolMatrix squeeze(void) const
Definition: boolSparse.cc:287
T & xelem(octave_idx_type n)
Definition: Array.h:353
octave_idx_type * ridx(void)
Definition: Sparse.h:518
T * xdata(void)
Definition: Sparse.h:511
#define SPARSE_SMS_BOOL_OPS(M, S, ZERO)
SparseBoolMatrix diag(octave_idx_type k=0) const
Definition: boolSparse.cc:242
const T * fortran_vec(void) const
Definition: Array.h:481
#define SPARSE_SSM_BOOL_OPS(S, M, ZERO)
std::ostream & operator<<(std::ostream &os, const SparseBoolMatrix &a)
Definition: boolSparse.cc:262
Sparse< T > diag(octave_idx_type k=0) const
Definition: Sparse.cc:2411
bool operator!=(const SparseBoolMatrix &a) const
Definition: boolSparse.cc:69