Repository: josdejong/mathjs
Pull request #803 (2017-02-28 04:00:46)

SparseMatrix.reshape
Here is an implementation of reshape for the SparseMatrix.

`math.reshape` has also been changed to use each matrix type's implementation of `reshape`, if it exists, or the `array.reshape` function otherwise (which was the original behavior).


Patch:
diff --git a/lib/function/matrix/reshape.js b/lib/function/matrix/reshape.js
index 87d37503f..8d7ae23e9 100644
--- a/lib/function/matrix/reshape.js
+++ b/lib/function/matrix/reshape.js
@@ -47,7 +47,11 @@ function factory (type, config, load, typed) {
   var reshape = typed('reshape', {
 
     'Matrix, Array': function (x, sizes) {
-      return matrix(array.reshape(x.valueOf(), sizes));
+      if(x.reshape) {
+        return x.reshape(sizes);
+      } else {
+        return matrix(array.reshape(x.valueOf(), sizes));
+      }
     },
 
     'Array, Array': function (x, sizes) {
diff --git a/lib/type/matrix/SparseMatrix.js b/lib/type/matrix/SparseMatrix.js
index 9bfb4ecaf..ef8bfe19f 100644
--- a/lib/type/matrix/SparseMatrix.js
+++ b/lib/type/matrix/SparseMatrix.js
@@ -705,6 +705,102 @@ function factory (type, config, load, typed) {
     // return matrix
     return matrix;
   };
+
+  /**
+   * Reshape the matrix to the given size. Returns a copy of the matrix when
+   * `copy=true`, otherwise return the matrix itself (reshape in place).
+   *
+   * NOTE: This might be better suited to copy by default, instead of modifying
+   *       in place. For now, it operates in place to remain consistent with
+   *       resize().
+   *
+   * @memberof SparseMatrix
+   * @param {number[]} size           The new size the matrix should have.
+   * @param {boolean} [copy]          Return a reshaped copy of the matrix
+   *
+   * @return {Matrix}                 The reshaped matrix
+   */
+  SparseMatrix.prototype.reshape = function (size, copy) {
+
+    // validate arguments
+    if (!isArray(size))
+      throw new TypeError('Array expected');
+    if (size.length !== 2)
+      throw new Error('Sparse matrices can only be reshaped in two dimensions');
+
+    // check sizes
+    size.forEach(function (value) {
+      if (!number.isNumber(value) || !number.isInteger(value) || value < 0) {
+        throw new TypeError('Invalid size, must contain positive integers ' +
+                            '(size: ' + string.format(size) + ')');
+      }
+    });
+
+    // m * n must not change
+    if(this._size[0] * this._size[1] !== size[0] * size[1]) {
+      throw new Error('Reshaping sparse matrix will result in the wrong number of elements');
+    }
+
+    // matrix to reshape
+    var m = copy ? this.clone() : this;
+
+    // return unchanged if the same shape
+    if(this._size[0] === size[0] && this._size[1] === size[1]) {
+      return m;
+    }
+
+    // Convert to COO format (generate a column index)
+    var colIndex = [];
+    for(var i=0; i<m._ptr.length; i++) {
+      for(var j=0; j<m._ptr[i+1]-m._ptr[i]; j++) {
+        colIndex.push(i);
+      }
+    }
+
+    // Clone the values array
+    var values = m._values.slice();
+
+    // Clone the row index array
+    var rowIndex = m._index.slice();
+
+    // Transform the (row, column) indices
+    for(var i=0; i<m._index.length; i++) {
+      var r1 = rowIndex[i];
+      var c1 = colIndex[i];
+      var flat = r1 * m._size[1] + c1;
+      colIndex[i] = flat % size[1];
+      rowIndex[i] = Math.floor(flat / size[1]);
+    }
+
+    // Now reshaping is supposed to preserve the row-major order, BUT these sparse matrices are stored
+    // in column-major order, so we have to reorder the value array now. One option is to use a multisort,
+    // sorting several arrays based on some other array.
+
+    // OR, we could easily just:
+
+    // 1. Remove all values from the matrix
+    m._values.length = 0;
+    m._index.length = 0;
+    m._ptr.length = size[1] + 1;
+    m._size = size.slice();
+    for(var i=0; i<m._ptr.length; i++) {
+      m._ptr[i] = 0;
+    }
+
+    // 2. Re-insert all elements in the proper order (simplified code from SparseMatrix.prototype.set)
+    // This step is probably the most time-consuming
+    for(var h=0; h<values.length; h++) {
+      var i = rowIndex[h];
+      var j = colIndex[h];
+      var v = values[h];
+      var k = _getValueIndex(i, m._ptr[j], m._ptr[j + 1], m._index);
+      _insert(k, i, j, v, m._values, m._index, m._ptr);
+    }
+
+    // The value indices are inserted out of order, but apparently that's... still OK?
+
+    return m;
+  }
   
   /**
    * Create a clone of the matrix


Test patch:
diff --git a/test/function/matrix/reshape.test.js b/test/function/matrix/reshape.test.js
index a02e8f1cb..cc6d9cf43 100644
--- a/test/function/matrix/reshape.test.js
+++ b/test/function/matrix/reshape.test.js
@@ -64,5 +64,45 @@ describe('reshape', function() {
     var expression = math.parse('reshape([1,2],1)');
     assert.equal(expression.toTex(), '\\mathrm{reshape}\\left(\\begin{bmatrix}1\\\\2\\\\\\end{bmatrix},1\\right)');
   });
+
+  it('should reshape a SparseMatrix', function() {
+
+    /*
+     * Must use toArray because SparseMatrix.reshape currently does not preserve
+     * the order of the _index and _values arrays (this does not matter?)
+     */
+
+    var matrix = math.matrix([[0,1,2],[3,4,5]], 'sparse');
+    assert.deepEqual(math.reshape(matrix, [3, 2]).toArray(),
+        [[0,1], [2,3], [4,5]]);
+
+    assert.deepEqual(math.reshape(matrix, [6, 1]).toArray(),
+        [[0],[1],[2],[3],[4],[5]]);
+
+    assert.deepEqual(math.reshape(matrix, [1, 6]).toArray(),
+        [[0,1,2,3,4,5]]);
+
+    matrix = math.matrix([[0,1,2,3,4,5]], 'sparse');
+    assert.deepEqual(math.reshape(matrix, [3, 2]).toArray(),
+        [[0,1], [2,3], [4,5]]);
+
+    matrix = math.matrix([[0],[1],[2],[3],[4],[5]], 'sparse');
+    assert.deepEqual(math.reshape(matrix, [3, 2]).toArray(),
+        [[0,1], [2,3], [4,5]]);
+
+  });
+
+  it('should throw on attempting to reshape an ImmutableDenseMatrix', function() {
+    var immutableMatrix = new math.type.ImmutableDenseMatrix([[1,2],[3,4]]);
+    assert.throws(function() { math.reshape(immutableMatrix, [1, 4]); },
+        /Cannot invoke reshape on an Immutable Matrix instance/);
+  });
+
+  it('should throw on attempting to reshape a Matrix (abstract type)', function() {
+    var matrix = new math.type.Matrix([[1,2],[3,4]]);
+    assert.throws(function() { math.reshape(matrix, [1, 4]); },
+        /Cannot invoke reshape on a Matrix interface/);
+  });
+
 });
 
diff --git a/test/type/matrix/SparseMatrix.test.js b/test/type/matrix/SparseMatrix.test.js
index ad8e17f14..e5849f156 100644
--- a/test/type/matrix/SparseMatrix.test.js
+++ b/test/type/matrix/SparseMatrix.test.js
@@ -592,6 +592,64 @@ describe('SparseMatrix', function() {
           [0, 0]
         ]);
     });
+  });
+  
+   describe('reshape', function () {
+
+    it('should reshape the matrix properly', function () {
+      var m = new SparseMatrix([[1,2,3],[4,5,6]]);
+      m.reshape([3,2]);
+      assert.deepEqual(m.valueOf(), [[1,2], [3,4], [5,6]]);
+      m.reshape([6,1]);
+      assert.deepEqual(m.valueOf(), [[1],[2],[3],[4],[5],[6]]);
+    });
+
+    it('should return a copy only when specified', function () {
+      var m1 = new SparseMatrix([[1, 2], [3, 4]]);
+      var m2 = m1.reshape([4, 1]);
+      var m3 = m2.reshape([1, 4], true);
+
+      assert.strictEqual(m2, m1);
+      assert.deepEqual(m2.valueOf(), [[1], [2], [3], [4]]);
+      assert.deepEqual(m2.valueOf(), m1.valueOf());
+
+      assert.notStrictEqual(m3, m2);
+      assert.deepEqual(m3.valueOf(), [[1, 2, 3, 4]]);
+      assert.notDeepEqual(m3.valueOf(), m2.valueOf());
+    });
+
+    it('should update the size of the reshaped matrix', function () {
+      var m1 = new SparseMatrix([[1, 2], [3, 4]]);
+      var m2 = m1.reshape([4, 1], true);
+
+      assert.deepEqual(m1.size(), [2, 2]);
+
+      m1.reshape([1, 4]);
+
+      assert.deepEqual(m1.size(), [1, 4]);
+      assert.deepEqual(m2.size(), [4, 1]);
+    });
+    
+    it('should throw on attempting to reshape to != 2 dimensions', function() {
+      var m1 = new SparseMatrix([[1, 2], [3, 4]]);
+      assert.throws(function() { m1.reshape([4]); }, /Sparse matrices can only be reshaped in two dimensions/);
+      assert.throws(function() { m1.reshape([2, 2, 1]); }, /Sparse matrices can only be reshaped in two dimensions/);
+    });
+    
+    it('should throw when reshaping will change the number of elements', function() {
+      var m1 = new SparseMatrix([[1, 2], [3, 4]]);
+      assert.throws(function() { m1.reshape([2, 5]); }, /Reshaping sparse matrix will result in the wrong number of elements/);
+    });
+    
+    it('should throw for invalid arguments', function() {
+      var m1 = new SparseMatrix([[1, 2], [3, 4]]);
+      assert.throws(function() { m1.reshape(); }, /Array expected/);
+      assert.throws(function() { m1.reshape(42); }, /Array expected/);
+      assert.throws(function() { m1.reshape(["hello", "world"]); }, /Invalid size, must contain positive integers/);
+      assert.throws(function() { m1.reshape([-2, -2]); }, /Invalid size, must contain positive integers/);
+    });
+
+
   });
   
   describe('get', function () {