1 | import { isArray, isBigNumber, isIndex, isMatrix, isNumber, isString, typeOf } from '../../utils/is'
|
2 | import { isInteger } from '../../utils/number'
|
3 | import { format } from '../../utils/string'
|
4 | import { clone, deepStrictEqual } from '../../utils/object'
|
5 | import { arraySize, getArrayDataType, unsqueeze, validateIndex } from '../../utils/array'
|
6 | import { factory } from '../../utils/factory'
|
7 | import { DimensionError } from '../../error/DimensionError'
|
8 |
|
9 | const name = 'SparseMatrix'
|
10 | const dependencies = [
|
11 | 'typed',
|
12 | 'equalScalar',
|
13 | 'Matrix'
|
14 | ]
|
15 |
|
16 | export const createSparseMatrixClass = factory(name, dependencies, ({ typed, equalScalar, Matrix }) => {
|
17 | |
18 |
|
19 |
|
20 |
|
21 |
|
22 | function SparseMatrix (data, datatype) {
|
23 | if (!(this instanceof SparseMatrix)) { throw new SyntaxError('Constructor must be called with the new operator') }
|
24 | if (datatype && !isString(datatype)) { throw new Error('Invalid datatype: ' + datatype) }
|
25 |
|
26 | if (isMatrix(data)) {
|
27 |
|
28 | _createFromMatrix(this, data, datatype)
|
29 | } else if (data && isArray(data.index) && isArray(data.ptr) && isArray(data.size)) {
|
30 |
|
31 | this._values = data.values
|
32 | this._index = data.index
|
33 | this._ptr = data.ptr
|
34 | this._size = data.size
|
35 | this._datatype = datatype || data.datatype
|
36 | } else if (isArray(data)) {
|
37 |
|
38 | _createFromArray(this, data, datatype)
|
39 | } else if (data) {
|
40 |
|
41 | throw new TypeError('Unsupported type of data (' + typeOf(data) + ')')
|
42 | } else {
|
43 |
|
44 | this._values = []
|
45 | this._index = []
|
46 | this._ptr = [0]
|
47 | this._size = [0, 0]
|
48 | this._datatype = datatype
|
49 | }
|
50 | }
|
51 |
|
52 | function _createFromMatrix (matrix, source, datatype) {
|
53 |
|
54 | if (source.type === 'SparseMatrix') {
|
55 |
|
56 | matrix._values = source._values ? clone(source._values) : undefined
|
57 | matrix._index = clone(source._index)
|
58 | matrix._ptr = clone(source._ptr)
|
59 | matrix._size = clone(source._size)
|
60 | matrix._datatype = datatype || source._datatype
|
61 | } else {
|
62 |
|
63 | _createFromArray(matrix, source.valueOf(), datatype || source._datatype)
|
64 | }
|
65 | }
|
66 |
|
67 | function _createFromArray (matrix, data, datatype) {
|
68 |
|
69 | matrix._values = []
|
70 | matrix._index = []
|
71 | matrix._ptr = []
|
72 | matrix._datatype = datatype
|
73 |
|
74 | const rows = data.length
|
75 | let columns = 0
|
76 |
|
77 |
|
78 | let eq = equalScalar
|
79 |
|
80 | let zero = 0
|
81 |
|
82 | if (isString(datatype)) {
|
83 |
|
84 | eq = typed.find(equalScalar, [datatype, datatype]) || equalScalar
|
85 |
|
86 | zero = typed.convert(0, datatype)
|
87 | }
|
88 |
|
89 |
|
90 | if (rows > 0) {
|
91 |
|
92 | let j = 0
|
93 | do {
|
94 |
|
95 | matrix._ptr.push(matrix._index.length)
|
96 |
|
97 | for (let i = 0; i < rows; i++) {
|
98 |
|
99 | const row = data[i]
|
100 |
|
101 | if (isArray(row)) {
|
102 |
|
103 | if (j === 0 && columns < row.length) { columns = row.length }
|
104 |
|
105 | if (j < row.length) {
|
106 |
|
107 | const v = row[j]
|
108 |
|
109 | if (!eq(v, zero)) {
|
110 |
|
111 | matrix._values.push(v)
|
112 |
|
113 | matrix._index.push(i)
|
114 | }
|
115 | }
|
116 | } else {
|
117 |
|
118 | if (j === 0 && columns < 1) { columns = 1 }
|
119 |
|
120 | if (!eq(row, zero)) {
|
121 |
|
122 | matrix._values.push(row)
|
123 |
|
124 | matrix._index.push(i)
|
125 | }
|
126 | }
|
127 | }
|
128 |
|
129 | j++
|
130 | }
|
131 | while (j < columns)
|
132 | }
|
133 |
|
134 | matrix._ptr.push(matrix._index.length)
|
135 |
|
136 | matrix._size = [rows, columns]
|
137 | }
|
138 |
|
139 | SparseMatrix.prototype = new Matrix()
|
140 |
|
141 | |
142 |
|
143 |
|
144 | SparseMatrix.prototype.createSparseMatrix = function (data, datatype) {
|
145 | return new SparseMatrix(data, datatype)
|
146 | }
|
147 |
|
148 | |
149 |
|
150 |
|
151 | SparseMatrix.prototype.type = 'SparseMatrix'
|
152 | SparseMatrix.prototype.isSparseMatrix = true
|
153 |
|
154 | |
155 |
|
156 |
|
157 |
|
158 |
|
159 |
|
160 |
|
161 |
|
162 |
|
163 | SparseMatrix.prototype.getDataType = function () {
|
164 | return getArrayDataType(this._values, typeOf)
|
165 | }
|
166 |
|
167 | |
168 |
|
169 |
|
170 |
|
171 |
|
172 |
|
173 |
|
174 |
|
175 |
|
176 | SparseMatrix.prototype.storage = function () {
|
177 | return 'sparse'
|
178 | }
|
179 |
|
180 | |
181 |
|
182 |
|
183 |
|
184 |
|
185 |
|
186 |
|
187 |
|
188 |
|
189 | SparseMatrix.prototype.datatype = function () {
|
190 | return this._datatype
|
191 | }
|
192 |
|
193 | |
194 |
|
195 |
|
196 |
|
197 |
|
198 |
|
199 | SparseMatrix.prototype.create = function (data, datatype) {
|
200 | return new SparseMatrix(data, datatype)
|
201 | }
|
202 |
|
203 | |
204 |
|
205 |
|
206 |
|
207 |
|
208 |
|
209 |
|
210 |
|
211 |
|
212 | SparseMatrix.prototype.density = function () {
|
213 |
|
214 | const rows = this._size[0]
|
215 | const columns = this._size[1]
|
216 |
|
217 | return rows !== 0 && columns !== 0 ? (this._index.length / (rows * columns)) : 0
|
218 | }
|
219 |
|
220 | |
221 |
|
222 |
|
223 |
|
224 |
|
225 |
|
226 |
|
227 |
|
228 |
|
229 |
|
230 |
|
231 |
|
232 |
|
233 |
|
234 | SparseMatrix.prototype.subset = function (index, replacement, defaultValue) {
|
235 | if (!this._values) { throw new Error('Cannot invoke subset on a Pattern only matrix') }
|
236 |
|
237 |
|
238 | switch (arguments.length) {
|
239 | case 1:
|
240 | return _getsubset(this, index)
|
241 |
|
242 |
|
243 | case 2:
|
244 | case 3:
|
245 | return _setsubset(this, index, replacement, defaultValue)
|
246 |
|
247 | default:
|
248 | throw new SyntaxError('Wrong number of arguments')
|
249 | }
|
250 | }
|
251 |
|
252 | function _getsubset (matrix, idx) {
|
253 |
|
254 | if (!isIndex(idx)) {
|
255 | throw new TypeError('Invalid index')
|
256 | }
|
257 |
|
258 | const isScalar = idx.isScalar()
|
259 | if (isScalar) {
|
260 |
|
261 | return matrix.get(idx.min())
|
262 | }
|
263 |
|
264 | const size = idx.size()
|
265 | if (size.length !== matrix._size.length) {
|
266 | throw new DimensionError(size.length, matrix._size.length)
|
267 | }
|
268 |
|
269 |
|
270 | let i, ii, k, kk
|
271 |
|
272 |
|
273 | const min = idx.min()
|
274 | const max = idx.max()
|
275 | for (i = 0, ii = matrix._size.length; i < ii; i++) {
|
276 | validateIndex(min[i], matrix._size[i])
|
277 | validateIndex(max[i], matrix._size[i])
|
278 | }
|
279 |
|
280 |
|
281 | const mvalues = matrix._values
|
282 | const mindex = matrix._index
|
283 | const mptr = matrix._ptr
|
284 |
|
285 |
|
286 | const rows = idx.dimension(0)
|
287 | const columns = idx.dimension(1)
|
288 |
|
289 |
|
290 | const w = []
|
291 | const pv = []
|
292 |
|
293 |
|
294 | rows.forEach(function (i, r) {
|
295 |
|
296 | pv[i] = r[0]
|
297 |
|
298 | w[i] = true
|
299 | })
|
300 |
|
301 |
|
302 | const values = mvalues ? [] : undefined
|
303 | const index = []
|
304 | const ptr = []
|
305 |
|
306 |
|
307 | columns.forEach(function (j) {
|
308 |
|
309 | ptr.push(index.length)
|
310 |
|
311 | for (k = mptr[j], kk = mptr[j + 1]; k < kk; k++) {
|
312 |
|
313 | i = mindex[k]
|
314 |
|
315 | if (w[i] === true) {
|
316 |
|
317 | index.push(pv[i])
|
318 |
|
319 | if (values) { values.push(mvalues[k]) }
|
320 | }
|
321 | }
|
322 | })
|
323 |
|
324 | ptr.push(index.length)
|
325 |
|
326 |
|
327 | return new SparseMatrix({
|
328 | values: values,
|
329 | index: index,
|
330 | ptr: ptr,
|
331 | size: size,
|
332 | datatype: matrix._datatype
|
333 | })
|
334 | }
|
335 |
|
336 | function _setsubset (matrix, index, submatrix, defaultValue) {
|
337 |
|
338 | if (!index || index.isIndex !== true) {
|
339 | throw new TypeError('Invalid index')
|
340 | }
|
341 |
|
342 |
|
343 | const iSize = index.size()
|
344 | const isScalar = index.isScalar()
|
345 |
|
346 |
|
347 | let sSize
|
348 | if (isMatrix(submatrix)) {
|
349 |
|
350 | sSize = submatrix.size()
|
351 |
|
352 | submatrix = submatrix.toArray()
|
353 | } else {
|
354 |
|
355 | sSize = arraySize(submatrix)
|
356 | }
|
357 |
|
358 |
|
359 | if (isScalar) {
|
360 |
|
361 | if (sSize.length !== 0) {
|
362 | throw new TypeError('Scalar expected')
|
363 | }
|
364 |
|
365 | matrix.set(index.min(), submatrix, defaultValue)
|
366 | } else {
|
367 |
|
368 | if (iSize.length !== 1 && iSize.length !== 2) {
|
369 | throw new DimensionError(iSize.length, matrix._size.length, '<')
|
370 | }
|
371 |
|
372 |
|
373 | if (sSize.length < iSize.length) {
|
374 |
|
375 | let i = 0
|
376 | let outer = 0
|
377 | while (iSize[i] === 1 && sSize[i] === 1) {
|
378 | i++
|
379 | }
|
380 | while (iSize[i] === 1) {
|
381 | outer++
|
382 | i++
|
383 | }
|
384 |
|
385 | submatrix = unsqueeze(submatrix, iSize.length, outer, sSize)
|
386 | }
|
387 |
|
388 |
|
389 | if (!deepStrictEqual(iSize, sSize)) {
|
390 | throw new DimensionError(iSize, sSize, '>')
|
391 | }
|
392 |
|
393 |
|
394 | const x0 = index.min()[0]
|
395 | const y0 = index.min()[1]
|
396 |
|
397 |
|
398 | const m = sSize[0]
|
399 | const n = sSize[1]
|
400 |
|
401 |
|
402 | for (let x = 0; x < m; x++) {
|
403 |
|
404 | for (let y = 0; y < n; y++) {
|
405 |
|
406 | const v = submatrix[x][y]
|
407 |
|
408 | matrix.set([x + x0, y + y0], v, defaultValue)
|
409 | }
|
410 | }
|
411 | }
|
412 | return matrix
|
413 | }
|
414 |
|
415 | |
416 |
|
417 |
|
418 |
|
419 |
|
420 |
|
421 | SparseMatrix.prototype.get = function (index) {
|
422 | if (!isArray(index)) { throw new TypeError('Array expected') }
|
423 | if (index.length !== this._size.length) { throw new DimensionError(index.length, this._size.length) }
|
424 |
|
425 |
|
426 | if (!this._values) { throw new Error('Cannot invoke get on a Pattern only matrix') }
|
427 |
|
428 |
|
429 | const i = index[0]
|
430 | const j = index[1]
|
431 |
|
432 |
|
433 | validateIndex(i, this._size[0])
|
434 | validateIndex(j, this._size[1])
|
435 |
|
436 |
|
437 | const k = _getValueIndex(i, this._ptr[j], this._ptr[j + 1], this._index)
|
438 |
|
439 | if (k < this._ptr[j + 1] && this._index[k] === i) { return this._values[k] }
|
440 |
|
441 | return 0
|
442 | }
|
443 |
|
444 | |
445 |
|
446 |
|
447 |
|
448 |
|
449 |
|
450 |
|
451 |
|
452 |
|
453 |
|
454 | SparseMatrix.prototype.set = function (index, v, defaultValue) {
|
455 | if (!isArray(index)) { throw new TypeError('Array expected') }
|
456 | if (index.length !== this._size.length) { throw new DimensionError(index.length, this._size.length) }
|
457 |
|
458 |
|
459 | if (!this._values) { throw new Error('Cannot invoke set on a Pattern only matrix') }
|
460 |
|
461 |
|
462 | const i = index[0]
|
463 | const j = index[1]
|
464 |
|
465 |
|
466 | let rows = this._size[0]
|
467 | let columns = this._size[1]
|
468 |
|
469 |
|
470 | let eq = equalScalar
|
471 |
|
472 | let zero = 0
|
473 |
|
474 | if (isString(this._datatype)) {
|
475 |
|
476 | eq = typed.find(equalScalar, [this._datatype, this._datatype]) || equalScalar
|
477 |
|
478 | zero = typed.convert(0, this._datatype)
|
479 | }
|
480 |
|
481 |
|
482 | if (i > rows - 1 || j > columns - 1) {
|
483 |
|
484 | _resize(this, Math.max(i + 1, rows), Math.max(j + 1, columns), defaultValue)
|
485 |
|
486 | rows = this._size[0]
|
487 | columns = this._size[1]
|
488 | }
|
489 |
|
490 |
|
491 | validateIndex(i, rows)
|
492 | validateIndex(j, columns)
|
493 |
|
494 |
|
495 | const k = _getValueIndex(i, this._ptr[j], this._ptr[j + 1], this._index)
|
496 |
|
497 | if (k < this._ptr[j + 1] && this._index[k] === i) {
|
498 |
|
499 | if (!eq(v, zero)) {
|
500 |
|
501 | this._values[k] = v
|
502 | } else {
|
503 |
|
504 | _remove(k, j, this._values, this._index, this._ptr)
|
505 | }
|
506 | } else {
|
507 |
|
508 | _insert(k, i, j, v, this._values, this._index, this._ptr)
|
509 | }
|
510 |
|
511 | return this
|
512 | }
|
513 |
|
514 | function _getValueIndex (i, top, bottom, index) {
|
515 |
|
516 | if (bottom - top === 0) { return bottom }
|
517 |
|
518 | for (let r = top; r < bottom; r++) {
|
519 |
|
520 | if (index[r] === i) { return r }
|
521 | }
|
522 |
|
523 | return top
|
524 | }
|
525 |
|
526 | function _remove (k, j, values, index, ptr) {
|
527 |
|
528 | values.splice(k, 1)
|
529 | index.splice(k, 1)
|
530 |
|
531 | for (let x = j + 1; x < ptr.length; x++) { ptr[x]-- }
|
532 | }
|
533 |
|
534 | function _insert (k, i, j, v, values, index, ptr) {
|
535 |
|
536 | values.splice(k, 0, v)
|
537 |
|
538 | index.splice(k, 0, i)
|
539 |
|
540 | for (let x = j + 1; x < ptr.length; x++) { ptr[x]++ }
|
541 | }
|
542 |
|
543 | |
544 |
|
545 |
|
546 |
|
547 |
|
548 |
|
549 |
|
550 |
|
551 |
|
552 |
|
553 |
|
554 |
|
555 |
|
556 | SparseMatrix.prototype.resize = function (size, defaultValue, copy) {
|
557 |
|
558 | if (!isArray(size)) { throw new TypeError('Array expected') }
|
559 | if (size.length !== 2) { throw new Error('Only two dimensions matrix are supported') }
|
560 |
|
561 |
|
562 | size.forEach(function (value) {
|
563 | if (!isNumber(value) || !isInteger(value) || value < 0) {
|
564 | throw new TypeError('Invalid size, must contain positive integers ' +
|
565 | '(size: ' + format(size) + ')')
|
566 | }
|
567 | })
|
568 |
|
569 |
|
570 | const m = copy ? this.clone() : this
|
571 |
|
572 | return _resize(m, size[0], size[1], defaultValue)
|
573 | }
|
574 |
|
575 | function _resize (matrix, rows, columns, defaultValue) {
|
576 |
|
577 | let value = defaultValue || 0
|
578 |
|
579 |
|
580 | let eq = equalScalar
|
581 |
|
582 | let zero = 0
|
583 |
|
584 | if (isString(matrix._datatype)) {
|
585 |
|
586 | eq = typed.find(equalScalar, [matrix._datatype, matrix._datatype]) || equalScalar
|
587 |
|
588 | zero = typed.convert(0, matrix._datatype)
|
589 |
|
590 | value = typed.convert(value, matrix._datatype)
|
591 | }
|
592 |
|
593 |
|
594 | const ins = !eq(value, zero)
|
595 |
|
596 |
|
597 | const r = matrix._size[0]
|
598 | let c = matrix._size[1]
|
599 |
|
600 | let i, j, k
|
601 |
|
602 |
|
603 | if (columns > c) {
|
604 |
|
605 | for (j = c; j < columns; j++) {
|
606 |
|
607 | matrix._ptr[j] = matrix._values.length
|
608 |
|
609 | if (ins) {
|
610 |
|
611 | for (i = 0; i < r; i++) {
|
612 |
|
613 | matrix._values.push(value)
|
614 |
|
615 | matrix._index.push(i)
|
616 | }
|
617 | }
|
618 | }
|
619 |
|
620 | matrix._ptr[columns] = matrix._values.length
|
621 | } else if (columns < c) {
|
622 |
|
623 | matrix._ptr.splice(columns + 1, c - columns)
|
624 |
|
625 | matrix._values.splice(matrix._ptr[columns], matrix._values.length)
|
626 | matrix._index.splice(matrix._ptr[columns], matrix._index.length)
|
627 | }
|
628 |
|
629 | c = columns
|
630 |
|
631 |
|
632 | if (rows > r) {
|
633 |
|
634 | if (ins) {
|
635 |
|
636 | let n = 0
|
637 |
|
638 | for (j = 0; j < c; j++) {
|
639 |
|
640 | matrix._ptr[j] = matrix._ptr[j] + n
|
641 |
|
642 | k = matrix._ptr[j + 1] + n
|
643 |
|
644 | let p = 0
|
645 |
|
646 | for (i = r; i < rows; i++, p++) {
|
647 |
|
648 | matrix._values.splice(k + p, 0, value)
|
649 |
|
650 | matrix._index.splice(k + p, 0, i)
|
651 |
|
652 | n++
|
653 | }
|
654 | }
|
655 |
|
656 | matrix._ptr[c] = matrix._values.length
|
657 | }
|
658 | } else if (rows < r) {
|
659 |
|
660 | let d = 0
|
661 |
|
662 | for (j = 0; j < c; j++) {
|
663 |
|
664 | matrix._ptr[j] = matrix._ptr[j] - d
|
665 |
|
666 | const k0 = matrix._ptr[j]
|
667 | const k1 = matrix._ptr[j + 1] - d
|
668 |
|
669 | for (k = k0; k < k1; k++) {
|
670 |
|
671 | i = matrix._index[k]
|
672 |
|
673 | if (i > rows - 1) {
|
674 |
|
675 | matrix._values.splice(k, 1)
|
676 |
|
677 | matrix._index.splice(k, 1)
|
678 |
|
679 | d++
|
680 | }
|
681 | }
|
682 | }
|
683 |
|
684 | matrix._ptr[j] = matrix._values.length
|
685 | }
|
686 |
|
687 | matrix._size[0] = rows
|
688 | matrix._size[1] = columns
|
689 |
|
690 | return matrix
|
691 | }
|
692 |
|
693 | |
694 |
|
695 |
|
696 |
|
697 |
|
698 |
|
699 |
|
700 |
|
701 |
|
702 |
|
703 |
|
704 |
|
705 |
|
706 |
|
707 | SparseMatrix.prototype.reshape = function (size, copy) {
|
708 |
|
709 | if (!isArray(size)) { throw new TypeError('Array expected') }
|
710 | if (size.length !== 2) { throw new Error('Sparse matrices can only be reshaped in two dimensions') }
|
711 |
|
712 |
|
713 | size.forEach(function (value) {
|
714 | if (!isNumber(value) || !isInteger(value) || value < 0) {
|
715 | throw new TypeError('Invalid size, must contain positive integers ' +
|
716 | '(size: ' + format(size) + ')')
|
717 | }
|
718 | })
|
719 |
|
720 |
|
721 | if (this._size[0] * this._size[1] !== size[0] * size[1]) {
|
722 | throw new Error('Reshaping sparse matrix will result in the wrong number of elements')
|
723 | }
|
724 |
|
725 |
|
726 | const m = copy ? this.clone() : this
|
727 |
|
728 |
|
729 | if (this._size[0] === size[0] && this._size[1] === size[1]) {
|
730 | return m
|
731 | }
|
732 |
|
733 |
|
734 | const colIndex = []
|
735 | for (let i = 0; i < m._ptr.length; i++) {
|
736 | for (let j = 0; j < m._ptr[i + 1] - m._ptr[i]; j++) {
|
737 | colIndex.push(i)
|
738 | }
|
739 | }
|
740 |
|
741 |
|
742 | const values = m._values.slice()
|
743 |
|
744 |
|
745 | const rowIndex = m._index.slice()
|
746 |
|
747 |
|
748 | for (let i = 0; i < m._index.length; i++) {
|
749 | const r1 = rowIndex[i]
|
750 | const c1 = colIndex[i]
|
751 | const flat = r1 * m._size[1] + c1
|
752 | colIndex[i] = flat % size[1]
|
753 | rowIndex[i] = Math.floor(flat / size[1])
|
754 | }
|
755 |
|
756 |
|
757 |
|
758 |
|
759 |
|
760 |
|
761 |
|
762 |
|
763 | m._values.length = 0
|
764 | m._index.length = 0
|
765 | m._ptr.length = size[1] + 1
|
766 | m._size = size.slice()
|
767 | for (let i = 0; i < m._ptr.length; i++) {
|
768 | m._ptr[i] = 0
|
769 | }
|
770 |
|
771 |
|
772 |
|
773 | for (let h = 0; h < values.length; h++) {
|
774 | const i = rowIndex[h]
|
775 | const j = colIndex[h]
|
776 | const v = values[h]
|
777 | const k = _getValueIndex(i, m._ptr[j], m._ptr[j + 1], m._index)
|
778 | _insert(k, i, j, v, m._values, m._index, m._ptr)
|
779 | }
|
780 |
|
781 |
|
782 |
|
783 | return m
|
784 | }
|
785 |
|
786 | |
787 |
|
788 |
|
789 |
|
790 |
|
791 | SparseMatrix.prototype.clone = function () {
|
792 | const m = new SparseMatrix({
|
793 | values: this._values ? clone(this._values) : undefined,
|
794 | index: clone(this._index),
|
795 | ptr: clone(this._ptr),
|
796 | size: clone(this._size),
|
797 | datatype: this._datatype
|
798 | })
|
799 | return m
|
800 | }
|
801 |
|
802 | |
803 |
|
804 |
|
805 |
|
806 |
|
807 | SparseMatrix.prototype.size = function () {
|
808 | return this._size.slice(0)
|
809 | }
|
810 |
|
811 | |
812 |
|
813 |
|
814 |
|
815 |
|
816 |
|
817 |
|
818 |
|
819 |
|
820 |
|
821 |
|
822 | SparseMatrix.prototype.map = function (callback, skipZeros) {
|
823 |
|
824 | if (!this._values) { throw new Error('Cannot invoke map on a Pattern only matrix') }
|
825 |
|
826 | const me = this
|
827 |
|
828 | const rows = this._size[0]
|
829 | const columns = this._size[1]
|
830 |
|
831 | const invoke = function (v, i, j) {
|
832 |
|
833 | return callback(v, [i, j], me)
|
834 | }
|
835 |
|
836 | return _map(this, 0, rows - 1, 0, columns - 1, invoke, skipZeros)
|
837 | }
|
838 |
|
839 | |
840 |
|
841 |
|
842 |
|
843 | function _map (matrix, minRow, maxRow, minColumn, maxColumn, callback, skipZeros) {
|
844 |
|
845 | const values = []
|
846 | const index = []
|
847 | const ptr = []
|
848 |
|
849 |
|
850 | let eq = equalScalar
|
851 |
|
852 | let zero = 0
|
853 |
|
854 | if (isString(matrix._datatype)) {
|
855 |
|
856 | eq = typed.find(equalScalar, [matrix._datatype, matrix._datatype]) || equalScalar
|
857 |
|
858 | zero = typed.convert(0, matrix._datatype)
|
859 | }
|
860 |
|
861 |
|
862 | const invoke = function (v, x, y) {
|
863 |
|
864 | v = callback(v, x, y)
|
865 |
|
866 | if (!eq(v, zero)) {
|
867 |
|
868 | values.push(v)
|
869 |
|
870 | index.push(x)
|
871 | }
|
872 | }
|
873 |
|
874 | for (let j = minColumn; j <= maxColumn; j++) {
|
875 |
|
876 | ptr.push(values.length)
|
877 |
|
878 | const k0 = matrix._ptr[j]
|
879 | const k1 = matrix._ptr[j + 1]
|
880 |
|
881 | if (skipZeros) {
|
882 |
|
883 | for (let k = k0; k < k1; k++) {
|
884 |
|
885 | const i = matrix._index[k]
|
886 |
|
887 | if (i >= minRow && i <= maxRow) {
|
888 |
|
889 | invoke(matrix._values[k], i - minRow, j - minColumn)
|
890 | }
|
891 | }
|
892 | } else {
|
893 |
|
894 | const values = {}
|
895 | for (let k = k0; k < k1; k++) {
|
896 | const i = matrix._index[k]
|
897 | values[i] = matrix._values[k]
|
898 | }
|
899 |
|
900 |
|
901 |
|
902 | for (let i = minRow; i <= maxRow; i++) {
|
903 | const value = (i in values) ? values[i] : 0
|
904 | invoke(value, i - minRow, j - minColumn)
|
905 | }
|
906 | }
|
907 | }
|
908 |
|
909 |
|
910 | ptr.push(values.length)
|
911 |
|
912 | return new SparseMatrix({
|
913 | values: values,
|
914 | index: index,
|
915 | ptr: ptr,
|
916 | size: [maxRow - minRow + 1, maxColumn - minColumn + 1]
|
917 | })
|
918 | }
|
919 |
|
920 | |
921 |
|
922 |
|
923 |
|
924 |
|
925 |
|
926 |
|
927 |
|
928 | SparseMatrix.prototype.forEach = function (callback, skipZeros) {
|
929 |
|
930 | if (!this._values) { throw new Error('Cannot invoke forEach on a Pattern only matrix') }
|
931 |
|
932 | const me = this
|
933 |
|
934 | const rows = this._size[0]
|
935 | const columns = this._size[1]
|
936 |
|
937 | for (let j = 0; j < columns; j++) {
|
938 |
|
939 | const k0 = this._ptr[j]
|
940 | const k1 = this._ptr[j + 1]
|
941 |
|
942 | if (skipZeros) {
|
943 |
|
944 | for (let k = k0; k < k1; k++) {
|
945 |
|
946 | const i = this._index[k]
|
947 |
|
948 |
|
949 | callback(this._values[k], [i, j], me)
|
950 | }
|
951 | } else {
|
952 |
|
953 | const values = {}
|
954 | for (let k = k0; k < k1; k++) {
|
955 | const i = this._index[k]
|
956 | values[i] = this._values[k]
|
957 | }
|
958 |
|
959 |
|
960 |
|
961 | for (let i = 0; i < rows; i++) {
|
962 | const value = (i in values) ? values[i] : 0
|
963 | callback(value, [i, j], me)
|
964 | }
|
965 | }
|
966 | }
|
967 | }
|
968 |
|
969 | |
970 |
|
971 |
|
972 |
|
973 |
|
974 | SparseMatrix.prototype.toArray = function () {
|
975 | return _toArray(this._values, this._index, this._ptr, this._size, true)
|
976 | }
|
977 |
|
978 | |
979 |
|
980 |
|
981 |
|
982 |
|
983 | SparseMatrix.prototype.valueOf = function () {
|
984 | return _toArray(this._values, this._index, this._ptr, this._size, false)
|
985 | }
|
986 |
|
987 | function _toArray (values, index, ptr, size, copy) {
|
988 |
|
989 | const rows = size[0]
|
990 | const columns = size[1]
|
991 |
|
992 | const a = []
|
993 |
|
994 | let i, j
|
995 |
|
996 | for (i = 0; i < rows; i++) {
|
997 | a[i] = []
|
998 | for (j = 0; j < columns; j++) { a[i][j] = 0 }
|
999 | }
|
1000 |
|
1001 |
|
1002 | for (j = 0; j < columns; j++) {
|
1003 |
|
1004 | const k0 = ptr[j]
|
1005 | const k1 = ptr[j + 1]
|
1006 |
|
1007 | for (let k = k0; k < k1; k++) {
|
1008 |
|
1009 | i = index[k]
|
1010 |
|
1011 | a[i][j] = values ? (copy ? clone(values[k]) : values[k]) : 1
|
1012 | }
|
1013 | }
|
1014 | return a
|
1015 | }
|
1016 |
|
1017 | |
1018 |
|
1019 |
|
1020 |
|
1021 |
|
1022 |
|
1023 |
|
1024 |
|
1025 |
|
1026 | SparseMatrix.prototype.format = function (options) {
|
1027 |
|
1028 | const rows = this._size[0]
|
1029 | const columns = this._size[1]
|
1030 |
|
1031 | const density = this.density()
|
1032 |
|
1033 | let str = 'Sparse Matrix [' + format(rows, options) + ' x ' + format(columns, options) + '] density: ' + format(density, options) + '\n'
|
1034 |
|
1035 | for (let j = 0; j < columns; j++) {
|
1036 |
|
1037 | const k0 = this._ptr[j]
|
1038 | const k1 = this._ptr[j + 1]
|
1039 |
|
1040 | for (let k = k0; k < k1; k++) {
|
1041 |
|
1042 | const i = this._index[k]
|
1043 |
|
1044 | str += '\n (' + format(i, options) + ', ' + format(j, options) + ') ==> ' + (this._values ? format(this._values[k], options) : 'X')
|
1045 | }
|
1046 | }
|
1047 | return str
|
1048 | }
|
1049 |
|
1050 | |
1051 |
|
1052 |
|
1053 |
|
1054 |
|
1055 | SparseMatrix.prototype.toString = function () {
|
1056 | return format(this.toArray())
|
1057 | }
|
1058 |
|
1059 | |
1060 |
|
1061 |
|
1062 |
|
1063 |
|
1064 | SparseMatrix.prototype.toJSON = function () {
|
1065 | return {
|
1066 | mathjs: 'SparseMatrix',
|
1067 | values: this._values,
|
1068 | index: this._index,
|
1069 | ptr: this._ptr,
|
1070 | size: this._size,
|
1071 | datatype: this._datatype
|
1072 | }
|
1073 | }
|
1074 |
|
1075 | |
1076 |
|
1077 |
|
1078 |
|
1079 |
|
1080 |
|
1081 |
|
1082 |
|
1083 | SparseMatrix.prototype.diagonal = function (k) {
|
1084 |
|
1085 | if (k) {
|
1086 |
|
1087 | if (isBigNumber(k)) { k = k.toNumber() }
|
1088 |
|
1089 | if (!isNumber(k) || !isInteger(k)) {
|
1090 | throw new TypeError('The parameter k must be an integer number')
|
1091 | }
|
1092 | } else {
|
1093 |
|
1094 | k = 0
|
1095 | }
|
1096 |
|
1097 | const kSuper = k > 0 ? k : 0
|
1098 | const kSub = k < 0 ? -k : 0
|
1099 |
|
1100 |
|
1101 | const rows = this._size[0]
|
1102 | const columns = this._size[1]
|
1103 |
|
1104 |
|
1105 | const n = Math.min(rows - kSub, columns - kSuper)
|
1106 |
|
1107 |
|
1108 | const values = []
|
1109 | const index = []
|
1110 | const ptr = []
|
1111 |
|
1112 | ptr[0] = 0
|
1113 |
|
1114 | for (let j = kSuper; j < columns && values.length < n; j++) {
|
1115 |
|
1116 | const k0 = this._ptr[j]
|
1117 | const k1 = this._ptr[j + 1]
|
1118 |
|
1119 | for (let x = k0; x < k1; x++) {
|
1120 |
|
1121 | const i = this._index[x]
|
1122 |
|
1123 | if (i === j - kSuper + kSub) {
|
1124 |
|
1125 | values.push(this._values[x])
|
1126 |
|
1127 | index[values.length - 1] = i - kSub
|
1128 |
|
1129 | break
|
1130 | }
|
1131 | }
|
1132 | }
|
1133 |
|
1134 | ptr.push(values.length)
|
1135 |
|
1136 | return new SparseMatrix({
|
1137 | values: values,
|
1138 | index: index,
|
1139 | ptr: ptr,
|
1140 | size: [n, 1]
|
1141 | })
|
1142 | }
|
1143 |
|
1144 | |
1145 |
|
1146 |
|
1147 |
|
1148 |
|
1149 |
|
1150 |
|
1151 |
|
1152 | SparseMatrix.fromJSON = function (json) {
|
1153 | return new SparseMatrix(json)
|
1154 | }
|
1155 |
|
1156 | |
1157 |
|
1158 |
|
1159 |
|
1160 |
|
1161 |
|
1162 |
|
1163 |
|
1164 |
|
1165 |
|
1166 |
|
1167 |
|
1168 | SparseMatrix.diagonal = function (size, value, k, defaultValue, datatype) {
|
1169 | if (!isArray(size)) { throw new TypeError('Array expected, size parameter') }
|
1170 | if (size.length !== 2) { throw new Error('Only two dimensions matrix are supported') }
|
1171 |
|
1172 |
|
1173 | size = size.map(function (s) {
|
1174 |
|
1175 | if (isBigNumber(s)) {
|
1176 |
|
1177 | s = s.toNumber()
|
1178 | }
|
1179 |
|
1180 | if (!isNumber(s) || !isInteger(s) || s < 1) {
|
1181 | throw new Error('Size values must be positive integers')
|
1182 | }
|
1183 | return s
|
1184 | })
|
1185 |
|
1186 |
|
1187 | if (k) {
|
1188 |
|
1189 | if (isBigNumber(k)) { k = k.toNumber() }
|
1190 |
|
1191 | if (!isNumber(k) || !isInteger(k)) {
|
1192 | throw new TypeError('The parameter k must be an integer number')
|
1193 | }
|
1194 | } else {
|
1195 |
|
1196 | k = 0
|
1197 | }
|
1198 |
|
1199 |
|
1200 | let eq = equalScalar
|
1201 |
|
1202 | let zero = 0
|
1203 |
|
1204 | if (isString(datatype)) {
|
1205 |
|
1206 | eq = typed.find(equalScalar, [datatype, datatype]) || equalScalar
|
1207 |
|
1208 | zero = typed.convert(0, datatype)
|
1209 | }
|
1210 |
|
1211 | const kSuper = k > 0 ? k : 0
|
1212 | const kSub = k < 0 ? -k : 0
|
1213 |
|
1214 |
|
1215 | const rows = size[0]
|
1216 | const columns = size[1]
|
1217 |
|
1218 |
|
1219 | const n = Math.min(rows - kSub, columns - kSuper)
|
1220 |
|
1221 |
|
1222 | let _value
|
1223 |
|
1224 |
|
1225 | if (isArray(value)) {
|
1226 |
|
1227 | if (value.length !== n) {
|
1228 |
|
1229 | throw new Error('Invalid value array length')
|
1230 | }
|
1231 |
|
1232 | _value = function (i) {
|
1233 |
|
1234 | return value[i]
|
1235 | }
|
1236 | } else if (isMatrix(value)) {
|
1237 |
|
1238 | const ms = value.size()
|
1239 |
|
1240 | if (ms.length !== 1 || ms[0] !== n) {
|
1241 |
|
1242 | throw new Error('Invalid matrix length')
|
1243 | }
|
1244 |
|
1245 | _value = function (i) {
|
1246 |
|
1247 | return value.get([i])
|
1248 | }
|
1249 | } else {
|
1250 |
|
1251 | _value = function () {
|
1252 |
|
1253 | return value
|
1254 | }
|
1255 | }
|
1256 |
|
1257 |
|
1258 | const values = []
|
1259 | const index = []
|
1260 | const ptr = []
|
1261 |
|
1262 |
|
1263 | for (let j = 0; j < columns; j++) {
|
1264 |
|
1265 | ptr.push(values.length)
|
1266 |
|
1267 | const i = j - kSuper
|
1268 |
|
1269 | if (i >= 0 && i < n) {
|
1270 |
|
1271 | const v = _value(i)
|
1272 |
|
1273 | if (!eq(v, zero)) {
|
1274 |
|
1275 | index.push(i + kSub)
|
1276 |
|
1277 | values.push(v)
|
1278 | }
|
1279 | }
|
1280 | }
|
1281 |
|
1282 | ptr.push(values.length)
|
1283 |
|
1284 | return new SparseMatrix({
|
1285 | values: values,
|
1286 | index: index,
|
1287 | ptr: ptr,
|
1288 | size: [rows, columns]
|
1289 | })
|
1290 | }
|
1291 |
|
1292 | |
1293 |
|
1294 |
|
1295 |
|
1296 |
|
1297 |
|
1298 |
|
1299 |
|
1300 |
|
1301 | SparseMatrix.prototype.swapRows = function (i, j) {
|
1302 |
|
1303 | if (!isNumber(i) || !isInteger(i) || !isNumber(j) || !isInteger(j)) {
|
1304 | throw new Error('Row index must be positive integers')
|
1305 | }
|
1306 |
|
1307 | if (this._size.length !== 2) {
|
1308 | throw new Error('Only two dimensional matrix is supported')
|
1309 | }
|
1310 |
|
1311 | validateIndex(i, this._size[0])
|
1312 | validateIndex(j, this._size[0])
|
1313 |
|
1314 |
|
1315 | SparseMatrix._swapRows(i, j, this._size[1], this._values, this._index, this._ptr)
|
1316 |
|
1317 | return this
|
1318 | }
|
1319 |
|
1320 | |
1321 |
|
1322 |
|
1323 |
|
1324 |
|
1325 |
|
1326 |
|
1327 |
|
1328 |
|
1329 | SparseMatrix._forEachRow = function (j, values, index, ptr, callback) {
|
1330 |
|
1331 | const k0 = ptr[j]
|
1332 | const k1 = ptr[j + 1]
|
1333 |
|
1334 | for (let k = k0; k < k1; k++) {
|
1335 |
|
1336 | callback(index[k], values[k])
|
1337 | }
|
1338 | }
|
1339 |
|
1340 | |
1341 |
|
1342 |
|
1343 |
|
1344 |
|
1345 |
|
1346 |
|
1347 |
|
1348 |
|
1349 |
|
1350 | SparseMatrix._swapRows = function (x, y, columns, values, index, ptr) {
|
1351 |
|
1352 | for (let j = 0; j < columns; j++) {
|
1353 |
|
1354 | const k0 = ptr[j]
|
1355 | const k1 = ptr[j + 1]
|
1356 |
|
1357 | const kx = _getValueIndex(x, k0, k1, index)
|
1358 |
|
1359 | const ky = _getValueIndex(y, k0, k1, index)
|
1360 |
|
1361 | if (kx < k1 && ky < k1 && index[kx] === x && index[ky] === y) {
|
1362 |
|
1363 | if (values) {
|
1364 | const v = values[kx]
|
1365 | values[kx] = values[ky]
|
1366 | values[ky] = v
|
1367 | }
|
1368 |
|
1369 | continue
|
1370 | }
|
1371 |
|
1372 | if (kx < k1 && index[kx] === x && (ky >= k1 || index[ky] !== y)) {
|
1373 |
|
1374 | const vx = values ? values[kx] : undefined
|
1375 |
|
1376 | index.splice(ky, 0, y)
|
1377 | if (values) { values.splice(ky, 0, vx) }
|
1378 |
|
1379 | index.splice(ky <= kx ? kx + 1 : kx, 1)
|
1380 | if (values) { values.splice(ky <= kx ? kx + 1 : kx, 1) }
|
1381 |
|
1382 | continue
|
1383 | }
|
1384 |
|
1385 | if (ky < k1 && index[ky] === y && (kx >= k1 || index[kx] !== x)) {
|
1386 |
|
1387 | const vy = values ? values[ky] : undefined
|
1388 |
|
1389 | index.splice(kx, 0, x)
|
1390 | if (values) { values.splice(kx, 0, vy) }
|
1391 |
|
1392 | index.splice(kx <= ky ? ky + 1 : ky, 1)
|
1393 | if (values) { values.splice(kx <= ky ? ky + 1 : ky, 1) }
|
1394 | }
|
1395 | }
|
1396 | }
|
1397 |
|
1398 | return SparseMatrix
|
1399 | }, { isClass: true })
|