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