View Javadoc
1   package org.djunits.value.vdouble.matrix.data;
2   
3   import java.util.Arrays;
4   import java.util.Collection;
5   import java.util.concurrent.atomic.AtomicInteger;
6   import java.util.stream.IntStream;
7   
8   import org.djunits.Throw;
9   import org.djunits.unit.Unit;
10  import org.djunits.unit.scale.Scale;
11  import org.djunits.value.ValueRuntimeException;
12  import org.djunits.value.storage.StorageType;
13  import org.djunits.value.vdouble.function.DoubleFunction;
14  import org.djunits.value.vdouble.function.DoubleFunction2;
15  import org.djunits.value.vdouble.matrix.base.DoubleSparseValue;
16  import org.djunits.value.vdouble.scalar.base.DoubleScalarInterface;
17  
18  /**
19   * Stores sparse data for a DoubleMatrix and carries out basic operations. The index in the sparse matrix data is calculated as
20   * <code>r * columns + c</code>, where r is the row number, cols is the total number of columns, and c is the column number.
21   * <p>
22   * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
23   * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
24   * </p>
25   * @author <a href="https://www.tudelft.nl/averbraeck">Alexander Verbraeck</a>
26   * @author <a href="https://www.tudelft.nl/staff/p.knoppers/">Peter Knoppers</a>
27   */
28  public class DoubleMatrixDataSparse extends DoubleMatrixData
29  {
30      /** */
31      private static final long serialVersionUID = 1L;
32  
33      /** the index values of the Matrix. The index is calculated as r * columns + c. */
34      private long[] indices;
35  
36      /**
37       * Create a matrix with sparse data.
38       * @param matrixSI double[]; the data to store
39       * @param indices long[]; the index values of the Matrix, with &lt;tt&gt;index = row * cols + col&lt;/tt&gt;
40       * @param rows int; the number of rows
41       * @param cols int; the number of columns
42       */
43      public DoubleMatrixDataSparse(final double[] matrixSI, final long[] indices, final int rows, final int cols)
44      {
45          super(StorageType.SPARSE);
46          this.matrixSI = matrixSI;
47          this.indices = indices;
48          this.rows = rows;
49          this.cols = cols;
50      }
51  
52      /**
53       * Create a matrix with sparse data.
54       * @param dataSI Collection&lt;DoubleSparseValue&lt;U, S&gt;&gt;; the sparse [X, Y, SI] values to store
55       * @param rows int; the number of rows of the matrix
56       * @param cols int; the number of columns of the matrix
57       * @throws NullPointerException when storageType is null or dataSI is null
58       * @param <U> the unit
59       * @param <S> the corresponding scalar type
60       */
61      public <U extends Unit<U>, S extends DoubleScalarInterface<U, S>> DoubleMatrixDataSparse(
62              final Collection<DoubleSparseValue<U, S>> dataSI, final int rows, final int cols) throws NullPointerException
63      {
64          super(StorageType.SPARSE);
65          Throw.whenNull(dataSI, "matrixSI is null");
66  
67          int length = (int) dataSI.stream().parallel().filter(d -> d.getValueSI() != 0.0).count();
68          this.rows = rows;
69          this.cols = cols;
70          this.matrixSI = new double[length];
71          this.indices = new long[length];
72          int index = 0;
73          for (DoubleSparseValue<U, S> data : dataSI)
74          {
75              if (data.getValueSI() != 0.0)
76              {
77                  this.indices[index] = data.getRow() * this.cols + data.getColumn();
78                  this.matrixSI[index] = data.getValueSI();
79                  index++;
80              }
81          }
82      }
83  
84      /** {@inheritDoc} */
85      @Override
86      public final int cardinality()
87      {
88          return this.indices.length;
89      }
90  
91      /**
92       * Fill the sparse data structures matrixSI[] and indices[]. Note: output vectors have to be initialized at the right size.
93       * Cannot be parallelized because of stateful and sequence-sensitive count.
94       * @param data double[][]; the input data
95       * @param matrixSI double[]; the matrix data to write
96       * @param indices long[]; the indices to write
97       * @throws ValueRuntimeException in case matrix is ragged
98       */
99      @SuppressWarnings("checkstyle:finalparameters")
100     private static void fill(final double[][] data, double[] matrixSI, long[] indices) throws ValueRuntimeException
101     {
102         int rows = data.length;
103         int cols = data[0].length;
104         int count = 0;
105         for (int r = 0; r < rows; r++)
106         {
107             double[] row = data[r];
108             // Row length check has been done by checkRectangularAndNonEmpty
109             for (int c = 0; c < cols; c++)
110             {
111                 int index = r * cols + c;
112                 if (row[c] != 0.0)
113                 {
114                     matrixSI[count] = row[c];
115                     indices[count] = index;
116                     count++;
117                 }
118             }
119         }
120     }
121 
122     /**
123      * Fill the sparse data structures matrixSI[] and indices[]. Note: output vectors have to be initialized at the right size.
124      * Cannot be parallelized because of stateful and sequence-sensitive count.
125      * @param data double[][]; the input data
126      * @param matrixSI double[]; the matrix data to write
127      * @param indices long[]; the indices to write
128      * @param scale Scale; Scale, the scale that will convert the data to SI
129      * @throws ValueRuntimeException in case matrix is ragged
130      */
131     @SuppressWarnings("checkstyle:finalparameters")
132     private static void fill(final double[][] data, double[] matrixSI, long[] indices, final Scale scale)
133             throws ValueRuntimeException
134     {
135         int rows = data.length;
136         int cols = data[0].length;
137         int count = 0;
138         for (int r = 0; r < rows; r++)
139         {
140             double[] row = data[r];
141             // Row length check has been done by checkRectangularAndNonEmpty
142             for (int c = 0; c < cols; c++)
143             {
144                 int index = r * cols + c;
145                 double value = scale.toStandardUnit(row[c]);
146                 if (value != 0.0)
147                 {
148                     matrixSI[count] = value;
149                     indices[count] = index;
150                     count++;
151                 }
152             }
153         }
154     }
155 
156     /** {@inheritDoc} */
157     @Override
158     public DoubleMatrixData assign(final DoubleFunction doubleFunction)
159     {
160         if (doubleFunction.apply(0d) != 0d)
161         {
162             // It is most unlikely that the result AND the left and right operands are efficiently stored in Sparse format
163             DoubleMatrixDataSparse result = toDense().assign(doubleFunction).toSparse();
164             this.indices = result.indices;
165             this.matrixSI = result.matrixSI;
166             return this;
167         }
168         // The code below relies on the fact that doubleFunction.apply(0d) yields 0d
169         int currentSize = rows() * cols();
170         if (currentSize > 16)
171         {
172             currentSize = 16;
173         }
174         long[] newIndices = new long[currentSize];
175         double[] newValues = new double[currentSize];
176         int nonZeroValues = 0;
177         int ownIndex = 0;
178         while (ownIndex < this.indices.length)
179         {
180             long index = this.indices[ownIndex];
181             double value = doubleFunction.apply(this.matrixSI[ownIndex]);
182             ownIndex++;
183             if (value != 0d)
184             {
185                 if (nonZeroValues >= currentSize)
186                 {
187                     // increase size of arrays
188                     currentSize *= 2;
189                     if (currentSize > rows() * cols())
190                     {
191                         currentSize = rows() * cols();
192                     }
193                     long[] newNewIndices = new long[currentSize];
194                     System.arraycopy(newIndices, 0, newNewIndices, 0, newIndices.length);
195                     newIndices = newNewIndices;
196                     double[] newNewValues = new double[currentSize];
197                     System.arraycopy(newValues, 0, newNewValues, 0, newValues.length);
198                     newValues = newNewValues;
199                 }
200                 newIndices[nonZeroValues] = index;
201                 newValues[nonZeroValues] = value;
202                 nonZeroValues++;
203             }
204         }
205         if (nonZeroValues < currentSize)
206         {
207             // reduce size of arrays
208             long[] newNewIndices = new long[nonZeroValues];
209             System.arraycopy(newIndices, 0, newNewIndices, 0, nonZeroValues);
210             newIndices = newNewIndices;
211             double[] newNewValues = new double[nonZeroValues];
212             System.arraycopy(newValues, 0, newNewValues, 0, nonZeroValues);
213             newValues = newNewValues;
214         }
215         this.indices = newIndices;
216         this.matrixSI = newValues;
217         return this;
218     }
219 
220     /** {@inheritDoc} */
221     @Override
222     public final DoubleMatrixDataSparse assign(final DoubleFunction2 doubleFunction, final DoubleMatrixData right)
223     {
224         if (doubleFunction.apply(0d, 0d) != 0d)
225         {
226             // It is most unlikely that the result AND the left and right operands are efficiently stored in Sparse format
227             DoubleMatrixDataSparse result = toDense().assign(doubleFunction, right).toSparse();
228             this.indices = result.indices;
229             this.matrixSI = result.matrixSI;
230             return this;
231         }
232         // The code below relies on the fact that doubleFunction.apply(0d, 0d) yields 0d
233         checkSizes(right);
234         int currentSize = rows() * cols();
235         if (currentSize > 16)
236         {
237             currentSize = 16;
238         }
239         long[] newIndices = new long[currentSize];
240         double[] newValues = new double[currentSize];
241         int nonZeroValues = 0;
242         int ownIndex = 0;
243         int otherIndex = 0;
244         if (right.isSparse())
245         { // both are sparse, result must be sparse
246             DoubleMatrixDataSparse../org/djunits/value/vdouble/matrix/data/DoubleMatrixDataSparse.html#DoubleMatrixDataSparse">DoubleMatrixDataSparse other = (DoubleMatrixDataSparse) right;
247             while (ownIndex < this.indices.length || otherIndex < other.indices.length)
248             {
249                 double value;
250                 long index;
251                 if (ownIndex < this.indices.length && otherIndex < other.indices.length)
252                 { // neither we nor right has run out of values
253                     if (this.indices[ownIndex] == other.indices[otherIndex])
254                     {
255                         value = doubleFunction.apply(this.matrixSI[ownIndex], other.matrixSI[otherIndex]);
256                         index = this.indices[ownIndex];
257                         ownIndex++;
258                         otherIndex++;
259                     }
260                     else if (this.indices[ownIndex] < other.indices[otherIndex])
261                     {
262                         // we have a non-zero; right has a zero
263                         value = doubleFunction.apply(this.matrixSI[ownIndex], 0d);
264                         index = this.indices[ownIndex];
265                         ownIndex++;
266                     }
267                     else
268                     {
269                         // we have a zero; right has a non-zero
270                         value = doubleFunction.apply(0d, other.matrixSI[otherIndex]);
271                         index = other.indices[otherIndex];
272                         otherIndex++;
273                     }
274                 }
275                 else if (ownIndex < this.indices.length)
276                 { // right has run out of values; we have not
277                     value = doubleFunction.apply(this.matrixSI[ownIndex], 0d);
278                     index = this.indices[ownIndex];
279                     ownIndex++;
280                 }
281                 else
282                 { // we have run out of values; right has not
283                     value = doubleFunction.apply(0d, other.matrixSI[otherIndex]);
284                     index = other.indices[otherIndex];
285                     otherIndex++;
286                 }
287                 if (value != 0d)
288                 {
289                     if (nonZeroValues >= currentSize)
290                     {
291                         // increase size of arrays
292                         currentSize *= 2;
293                         if (currentSize > rows() * cols())
294                         {
295                             currentSize = rows() * cols();
296                         }
297                         long[] newNewIndices = new long[currentSize];
298                         System.arraycopy(newIndices, 0, newNewIndices, 0, newIndices.length);
299                         newIndices = newNewIndices;
300                         double[] newNewValues = new double[currentSize];
301                         System.arraycopy(newValues, 0, newNewValues, 0, newValues.length);
302                         newValues = newNewValues;
303                     }
304                     newIndices[nonZeroValues] = index;
305                     newValues[nonZeroValues] = value;
306                     nonZeroValues++;
307                 }
308             }
309         }
310         else
311         { // we are sparse; other is dense, result must be sparse
312             DoubleMatrixDataDense/../org/djunits/value/vdouble/matrix/data/DoubleMatrixDataDense.html#DoubleMatrixDataDense">DoubleMatrixDataDense other = (DoubleMatrixDataDense) right;
313             while (otherIndex < right.matrixSI.length)
314             {
315                 double value;
316                 int index = otherIndex;
317                 if (ownIndex < this.indices.length)
318                 { // neither we nor right has run out of values
319                     if (this.indices[ownIndex] == otherIndex)
320                     {
321                         value = doubleFunction.apply(this.matrixSI[ownIndex], other.matrixSI[otherIndex]);
322                         ownIndex++;
323                     }
324                     else
325                     {
326                         // we have a zero; other has a value
327                         value = doubleFunction.apply(0d, other.matrixSI[otherIndex]);
328                     }
329                     otherIndex++;
330                 }
331                 else
332                 { // we have run out of values; right has not
333                     value = doubleFunction.apply(0d, other.matrixSI[otherIndex]);
334                     otherIndex++;
335                 }
336                 if (value != 0d)
337                 {
338                     if (nonZeroValues >= currentSize)
339                     {
340                         // increase size of arrays
341                         currentSize *= 2;
342                         if (currentSize > rows() * cols())
343                         {
344                             currentSize = rows() * cols();
345                         }
346                         long[] newNewIndices = new long[currentSize];
347                         System.arraycopy(newIndices, 0, newNewIndices, 0, newIndices.length);
348                         newIndices = newNewIndices;
349                         double[] newNewValues = new double[currentSize];
350                         System.arraycopy(newValues, 0, newNewValues, 0, newValues.length);
351                         newValues = newNewValues;
352                     }
353                     newIndices[nonZeroValues] = index;
354                     newValues[nonZeroValues] = value;
355                     nonZeroValues++;
356                 }
357             }
358         }
359         if (nonZeroValues < currentSize)
360         {
361             // reduce size of arrays
362             long[] newNewIndices = new long[nonZeroValues];
363             System.arraycopy(newIndices, 0, newNewIndices, 0, nonZeroValues);
364             newIndices = newNewIndices;
365             double[] newNewValues = new double[nonZeroValues];
366             System.arraycopy(newValues, 0, newNewValues, 0, nonZeroValues);
367             newValues = newNewValues;
368         }
369         this.indices = newIndices;
370         this.matrixSI = newValues;
371         return this;
372     }
373 
374     /** {@inheritDoc} */
375     @Override
376     public final DoubleMatrixDataDense toDense()
377     {
378         double[] denseSI = new double[this.rows * this.cols];
379         for (int index = 0; index < this.matrixSI.length; index++)
380         {
381             denseSI[(int) this.indices[index]] = this.matrixSI[index];
382         }
383         try
384         {
385             return new DoubleMatrixDataDense(denseSI, this.rows, this.cols);
386         }
387         catch (ValueRuntimeException exception)
388         {
389             throw new RuntimeException(exception); // cannot happen -- denseSI has the right size
390         }
391     }
392 
393     /** {@inheritDoc} */
394     @Override
395     public final DoubleMatrixDataSparse toSparse()
396     {
397         return this;
398     }
399 
400     /** {@inheritDoc} */
401     @Override
402     public final double getSI(final int row, final int col)
403     {
404         long index = row * this.cols + col;
405         int internalIndex = Arrays.binarySearch(this.indices, index);
406         return internalIndex < 0 ? 0.0 : this.matrixSI[internalIndex];
407     }
408 
409     /** {@inheritDoc} */
410     @Override
411     public final void setSI(final int row, final int col, final double valueSI)
412     {
413         long index = row * this.cols + col;
414         int internalIndex = Arrays.binarySearch(this.indices, index);
415         if (internalIndex >= 0)
416         {
417             this.matrixSI[internalIndex] = valueSI;
418             return;
419         }
420 
421         // make room. TODO increase size in chunks
422         internalIndex = -internalIndex - 1;
423         long[] indicesNew = new long[this.indices.length + 1];
424         double[] matrixSINew = new double[this.matrixSI.length + 1];
425         System.arraycopy(this.indices, 0, indicesNew, 0, internalIndex);
426         System.arraycopy(this.matrixSI, 0, matrixSINew, 0, internalIndex);
427         System.arraycopy(this.indices, internalIndex, indicesNew, internalIndex + 1, this.indices.length - internalIndex);
428         System.arraycopy(this.matrixSI, internalIndex, matrixSINew, internalIndex + 1, this.indices.length - internalIndex);
429         indicesNew[internalIndex] = index;
430         matrixSINew[internalIndex] = valueSI;
431         this.indices = indicesNew;
432         this.matrixSI = matrixSINew;
433     }
434 
435     /** {@inheritDoc} */
436     @Override
437     public final double[][] getDenseMatrixSI()
438     {
439         return toDense().getDenseMatrixSI();
440     }
441 
442     /** {@inheritDoc} */
443     @Override
444     public final DoubleMatrixDataSparse copy()
445     {
446         double[] vCopy = new double[this.matrixSI.length];
447         System.arraycopy(this.matrixSI, 0, vCopy, 0, this.matrixSI.length);
448         long[] iCopy = new long[this.indices.length];
449         System.arraycopy(this.indices, 0, iCopy, 0, this.indices.length);
450         return new DoubleMatrixDataSparse(vCopy, iCopy, this.rows, this.cols);
451     }
452 
453     /**
454      * Instantiate a DoubleMatrixDataSparse from an array.
455      * @param valuesSI double[][]; the (SI) values to store
456      * @return the DoubleMatrixDataSparse
457      * @throws ValueRuntimeException in case matrix is ragged
458      */
459     public static DoubleMatrixDataSparse instantiate(final double[][] valuesSI) throws ValueRuntimeException
460     {
461         checkRectangularAndNonEmpty(valuesSI);
462         int length = nonZero(valuesSI);
463         final int rows = valuesSI.length;
464         final int cols = valuesSI[0].length;
465         double[] sparseSI = new double[length];
466         long[] indices = new long[length];
467         fill(valuesSI, sparseSI, indices);
468         return new DoubleMatrixDataSparse(sparseSI, indices, rows, cols);
469     }
470 
471     /**
472      * Instantiate a DoubleMatrixDataSparse from an array.
473      * @param values double[][]; the values to store
474      * @param scale Scale; the scale that will convert values to SI
475      * @return the DoubleMatrixDataSparse
476      * @throws ValueRuntimeException in case matrix is ragged
477      */
478     public static DoubleMatrixDataSparse instantiate(final double[][] values, final Scale scale) throws ValueRuntimeException
479     {
480         checkRectangularAndNonEmpty(values);
481         int length = nonZero(values);
482         final int rows = values.length;
483         final int cols = values[0].length;
484         double[] sparseSI = new double[length];
485         long[] indices = new long[length];
486         fill(values, sparseSI, indices, scale);
487         return new DoubleMatrixDataSparse(sparseSI, indices, rows, cols);
488     }
489 
490     /**
491      * Calculate the number of non-zero values in a double[][] matrix.
492      * @param valuesSI double[][]; the double[][] matrix
493      * @return the number of non-zero values in the double[][] matrix
494      */
495     private static int nonZero(final double[][] valuesSI)
496     {
497         // determine number of non-null cells
498         AtomicInteger atomicLength = new AtomicInteger(0);
499         IntStream.range(0, valuesSI.length).parallel().forEach(r -> IntStream.range(0, valuesSI[0].length).forEach(c ->
500         {
501             if (valuesSI[r][c] != 0.0)
502             {
503                 atomicLength.incrementAndGet();
504             }
505         }));
506 
507         return atomicLength.get();
508     }
509 
510     /** {@inheritDoc} */
511     @Override
512     public DoubleMatrixDataix/data/DoubleMatrixData.html#DoubleMatrixData">DoubleMatrixData plus(final DoubleMatrixData right) throws ValueRuntimeException
513     {
514         if (right.isDense())
515         {
516             return right.copy().incrementBy(this);
517         }
518         return this.copy().incrementBy(right);
519     }
520 
521     /** {@inheritDoc} */
522     @Override
523     public final DoubleMatrixDatax/data/DoubleMatrixData.html#DoubleMatrixData">DoubleMatrixData minus(final DoubleMatrixData right)
524     {
525         if (right.isDense())
526         {
527             return this.toDense().decrementBy(right);
528         }
529         return this.copy().decrementBy(right);
530     }
531 
532     /** {@inheritDoc} */
533     @Override
534     public DoubleMatrixDataSparse times(final DoubleMatrixData right) throws ValueRuntimeException
535     {
536         checkSizes(right);
537         DoubleMatrixDataSparse result = this.copy();
538         result.multiplyBy(right);
539         return result;
540     }
541 
542     /** {@inheritDoc} */
543     @Override
544     public DoubleMatrixData/data/DoubleMatrixData.html#DoubleMatrixData">DoubleMatrixData divide(final DoubleMatrixData right) throws ValueRuntimeException
545     {
546         if (right.isSparse())
547         {
548             // Sparse divided by sparse makes a dense
549             return this.toDense().divide(right);
550         }
551         // Sparse divided by dense makes a sparse
552         checkSizes(right);
553         return this.copy().divideBy(right);
554     }
555 
556     /** {@inheritDoc} */
557     @Override
558     public int hashCode()
559     {
560         return super.hashCode();
561     }
562 
563     /** {@inheritDoc} */
564     @Override
565     @SuppressWarnings({"checkstyle:needbraces", "checkstyle:designforextension"})
566     public boolean equals(final Object obj)
567     {
568         if (this == obj)
569             return true;
570         if (obj == null)
571             return false;
572         if (!(obj instanceof DoubleMatrixData))
573             return false;
574         DoubleMatrixData../../../org/djunits/value/vdouble/matrix/data/DoubleMatrixData.html#DoubleMatrixData">DoubleMatrixData other = (DoubleMatrixData) obj;
575         if (this.rows != other.rows)
576             return false;
577         if (this.cols != other.cols)
578             return false;
579         if (other instanceof DoubleMatrixDataDense)
580             return super.equals(other);
581         if (getClass() != obj.getClass())
582             return false;
583         // Both are sparse
584         if (!Arrays.equals(this.indices, ((DoubleMatrixDataSparse) other).indices))
585             return false;
586         return Arrays.equals(this.matrixSI, ((DoubleMatrixDataSparse) other).matrixSI);
587     }
588 
589     /** {@inheritDoc} */
590     @Override
591     public String toString()
592     {
593         return "DoubleMatrixDataSparse [storageType=" + getStorageType() + ", indices=" + Arrays.toString(this.indices)
594                 + ", matrixSI=" + Arrays.toString(this.matrixSI) + "]";
595     }
596 
597 }