View Javadoc
1   package org.djunits.value.vdouble.vector.data;
2   
3   import java.util.Arrays;
4   
5   import org.djunits.value.ValueRuntimeException;
6   import org.djunits.value.storage.StorageType;
7   import org.djunits.value.vdouble.function.DoubleFunction;
8   import org.djunits.value.vdouble.function.DoubleFunction2;
9   
10  /**
11   * Stores sparse data for a DoubleVector and carries out basic operations.
12   * <p>
13   * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
14   * BSD-style license. See <a href="https://djunits.org/docs/license.html">DJUNITS License</a>.
15   * </p>
16   * @author <a href="https://www.tudelft.nl/averbraeck">Alexander Verbraeck</a>
17   * @author <a href="https://www.tudelft.nl/staff/p.knoppers/">Peter Knoppers</a>
18   */
19  public class DoubleVectorDataSparse extends DoubleVectorData
20  {
21      /** */
22      private static final long serialVersionUID = 1L;
23  
24      /** The index values of the Vector. */
25      private int[] indices;
26  
27      /** The length of the vector (padded with 0 after highest index in indices). */
28      private final int size;
29  
30      /**
31       * Create a vector with sparse data.
32       * @param vectorSI double[]; the data to store
33       * @param indices int[]; the index values of the Vector
34       * @param size int; the length of the vector (padded with 0 after highest index in indices)
35       */
36      public DoubleVectorDataSparse(final double[] vectorSI, final int[] indices, final int size)
37      {
38          super(StorageType.SPARSE);
39          this.vectorSI = vectorSI;
40          this.indices = indices;
41          this.size = size;
42      }
43  
44      @Override
45      public final int cardinality()
46      {
47          return this.indices.length;
48      }
49  
50      @Override
51      public DoubleVectorData assign(final DoubleFunction doubleFunction)
52      {
53          if (doubleFunction.apply(0d) != 0d)
54          {
55              // It is most unlikely that the result AND the left and right operands are efficiently stored in Sparse format
56              DoubleVectorDataSparse result = toDense().assign(doubleFunction).toSparse();
57              this.indices = result.indices;
58              this.vectorSI = result.vectorSI;
59              return this;
60          }
61          // The code below relies on the fact that doubleFunction.apply(0d) yields 0d
62          int currentSize = size();
63          if (currentSize > 16)
64          {
65              currentSize = 16;
66          }
67          int[] newIndices = new int[currentSize];
68          double[] newValues = new double[currentSize];
69          int nonZeroValues = 0;
70          int ownIndex = 0;
71          while (ownIndex < this.indices.length)
72          {
73              int index = this.indices[ownIndex];
74              double value = doubleFunction.apply(this.vectorSI[ownIndex]);
75              ownIndex++;
76              if (value != 0d)
77              {
78                  if (nonZeroValues >= currentSize)
79                  {
80                      // increase size of arrays
81                      currentSize *= 2;
82                      if (currentSize > size())
83                      {
84                          currentSize = size();
85                      }
86                      int[] newNewIndices = new int[currentSize];
87                      System.arraycopy(newIndices, 0, newNewIndices, 0, newIndices.length);
88                      newIndices = newNewIndices;
89                      double[] newNewValues = new double[currentSize];
90                      System.arraycopy(newValues, 0, newNewValues, 0, newValues.length);
91                      newValues = newNewValues;
92                  }
93                  newIndices[nonZeroValues] = index;
94                  newValues[nonZeroValues] = value;
95                  nonZeroValues++;
96              }
97          }
98          if (nonZeroValues < currentSize)
99          {
100             // reduce size of arrays
101             int[] newNewIndices = new int[nonZeroValues];
102             System.arraycopy(newIndices, 0, newNewIndices, 0, nonZeroValues);
103             newIndices = newNewIndices;
104             double[] newNewValues = new double[nonZeroValues];
105             System.arraycopy(newValues, 0, newNewValues, 0, nonZeroValues);
106             newValues = newNewValues;
107         }
108         this.indices = newIndices;
109         this.vectorSI = newValues;
110         return this;
111     }
112 
113     @Override
114     public final DoubleVectorDataSparse assign(final DoubleFunction2 doubleFunction, final DoubleVectorData right)
115     {
116         if (doubleFunction.apply(0d, 0d) != 0d)
117         {
118             // It is most unlikely that the result AND the left and right operands are efficiently stored in Sparse format
119             DoubleVectorDataSparse result = toDense().assign(doubleFunction, right).toSparse();
120             this.indices = result.indices;
121             this.vectorSI = result.vectorSI;
122             return this;
123         }
124         // The code below relies on the fact that doubleFunction.apply(0d, 0d) yields 0d
125         checkSizes(right);
126         int currentSize = size();
127         if (currentSize > 16)
128         {
129             currentSize = 16;
130         }
131         int[] newIndices = new int[currentSize];
132         double[] newValues = new double[currentSize];
133         int nonZeroValues = 0;
134         int ownIndex = 0;
135         int otherIndex = 0;
136         if (right.isSparse())
137         { // both are sparse, result must be sparse
138             DoubleVectorDataSparse other = (DoubleVectorDataSparse) right;
139             while (ownIndex < this.indices.length || otherIndex < other.indices.length)
140             {
141                 double value;
142                 int index;
143                 if (ownIndex < this.indices.length && otherIndex < other.indices.length)
144                 { // neither we nor right has run out of values
145                     if (this.indices[ownIndex] == other.indices[otherIndex])
146                     {
147                         value = doubleFunction.apply(this.vectorSI[ownIndex], other.vectorSI[otherIndex]);
148                         index = this.indices[ownIndex];
149                         ownIndex++;
150                         otherIndex++;
151                     }
152                     else if (this.indices[ownIndex] < other.indices[otherIndex])
153                     {
154                         // we have a non-zero; right has a zero
155                         value = doubleFunction.apply(this.vectorSI[ownIndex], 0d);
156                         index = this.indices[ownIndex];
157                         ownIndex++;
158                     }
159                     else
160                     {
161                         // we have a zero; right has a non-zero
162                         value = doubleFunction.apply(0d, other.vectorSI[otherIndex]);
163                         index = other.indices[otherIndex];
164                         otherIndex++;
165                     }
166                 }
167                 else if (ownIndex < this.indices.length)
168                 { // right has run out of values; we have not
169                     value = doubleFunction.apply(this.vectorSI[ownIndex], 0d);
170                     index = this.indices[ownIndex];
171                     ownIndex++;
172                 }
173                 else
174                 { // we have run out of values; right has not
175                     value = doubleFunction.apply(0d, other.vectorSI[otherIndex]);
176                     index = other.indices[otherIndex];
177                     otherIndex++;
178                 }
179                 if (value != 0d)
180                 {
181                     if (nonZeroValues >= currentSize)
182                     {
183                         // increase size of arrays
184                         currentSize *= 2;
185                         if (currentSize > size())
186                         {
187                             currentSize = size();
188                         }
189                         int[] newNewIndices = new int[currentSize];
190                         System.arraycopy(newIndices, 0, newNewIndices, 0, newIndices.length);
191                         newIndices = newNewIndices;
192                         double[] newNewValues = new double[currentSize];
193                         System.arraycopy(newValues, 0, newNewValues, 0, newValues.length);
194                         newValues = newNewValues;
195                     }
196                     newIndices[nonZeroValues] = index;
197                     newValues[nonZeroValues] = value;
198                     nonZeroValues++;
199                 }
200             }
201         }
202         else
203         { // we are sparse; other is dense, result must be sparse
204             DoubleVectorDataDense other = (DoubleVectorDataDense) right;
205             while (otherIndex < right.vectorSI.length)
206             {
207                 double value;
208                 int index = otherIndex;
209                 if (ownIndex < this.indices.length)
210                 { // neither we nor right has run out of values
211                     if (this.indices[ownIndex] == otherIndex)
212                     {
213                         value = doubleFunction.apply(this.vectorSI[ownIndex], other.vectorSI[otherIndex]);
214                         ownIndex++;
215                     }
216                     else
217                     {
218                         // we have a zero; other has a value
219                         value = doubleFunction.apply(0d, other.vectorSI[otherIndex]);
220                     }
221                     otherIndex++;
222                 }
223                 else
224                 { // we have run out of values; right has not
225                     value = doubleFunction.apply(0d, other.vectorSI[otherIndex]);
226                     otherIndex++;
227                 }
228                 if (value != 0d)
229                 {
230                     if (nonZeroValues >= currentSize)
231                     {
232                         // increase size of arrays
233                         currentSize *= 2;
234                         if (currentSize > size())
235                         {
236                             currentSize = size();
237                         }
238                         int[] newNewIndices = new int[currentSize];
239                         System.arraycopy(newIndices, 0, newNewIndices, 0, newIndices.length);
240                         newIndices = newNewIndices;
241                         double[] newNewValues = new double[currentSize];
242                         System.arraycopy(newValues, 0, newNewValues, 0, newValues.length);
243                         newValues = newNewValues;
244                     }
245                     newIndices[nonZeroValues] = index;
246                     newValues[nonZeroValues] = value;
247                     nonZeroValues++;
248                 }
249             }
250         }
251         if (nonZeroValues < currentSize)
252         {
253             // reduce size of arrays
254             int[] newNewIndices = new int[nonZeroValues];
255             System.arraycopy(newIndices, 0, newNewIndices, 0, nonZeroValues);
256             newIndices = newNewIndices;
257             double[] newNewValues = new double[nonZeroValues];
258             System.arraycopy(newValues, 0, newNewValues, 0, nonZeroValues);
259             newValues = newNewValues;
260         }
261         this.indices = newIndices;
262         this.vectorSI = newValues;
263         return this;
264     }
265 
266     @Override
267     public final DoubleVectorDataDense toDense()
268     {
269         double[] denseSI = new double[this.size];
270         for (int index = 0; index < this.vectorSI.length; index++)
271         {
272             denseSI[this.indices[index]] = this.vectorSI[index];
273         }
274         return new DoubleVectorDataDense(denseSI);
275     }
276 
277     @Override
278     public final DoubleVectorDataSparse toSparse()
279     {
280         return this;
281     }
282 
283     @Override
284     public final int size()
285     {
286         return this.size;
287     }
288 
289     @Override
290     public final double getSI(final int index)
291     {
292         int internalIndex = Arrays.binarySearch(this.indices, index);
293         return internalIndex < 0 ? 0.0 : this.vectorSI[internalIndex];
294     }
295 
296     @Override
297     public final void setSI(final int index, final double valueSI)
298     {
299         int internalIndex = Arrays.binarySearch(this.indices, index);
300         if (internalIndex >= 0)
301         {
302             if (valueSI == 0f)
303             {
304                 // remove room
305                 int[] indicesNew = new int[this.indices.length - 1];
306                 double[] vectorSINew = new double[this.vectorSI.length - 1];
307                 System.arraycopy(this.indices, 0, indicesNew, 0, internalIndex);
308                 System.arraycopy(this.vectorSI, 0, vectorSINew, 0, internalIndex);
309                 System.arraycopy(this.indices, internalIndex + 1, indicesNew, internalIndex,
310                         this.indices.length - internalIndex - 1);
311                 System.arraycopy(this.vectorSI, internalIndex + 1, vectorSINew, internalIndex,
312                         this.indices.length - internalIndex - 1);
313                 this.indices = indicesNew;
314                 this.vectorSI = vectorSINew;
315             }
316             else
317             {
318                 this.vectorSI[internalIndex] = valueSI;
319             }
320             return;
321         }
322 
323         // make room. TODO increase size in chunks
324         internalIndex = -internalIndex - 1;
325         int[] indicesNew = new int[this.indices.length + 1];
326         double[] vectorSINew = new double[this.vectorSI.length + 1];
327         System.arraycopy(this.indices, 0, indicesNew, 0, internalIndex);
328         System.arraycopy(this.vectorSI, 0, vectorSINew, 0, internalIndex);
329         // System.out.println("arraycopy1 current size is " + this.indices.length + " srcPos=" + internalIndex +
330         // ", new size is "
331         // + indicesNew.length + " dstPos=" + (internalIndex + 1) + " length=" + (this.indices.length - internalIndex));
332         System.arraycopy(this.indices, internalIndex, indicesNew, internalIndex + 1, this.indices.length - internalIndex);
333         System.arraycopy(this.vectorSI, internalIndex, vectorSINew, internalIndex + 1, this.indices.length - internalIndex);
334         // System.arraycopy(this.indices, internalIndex, indicesNew, internalIndex - 1, this.indices.length - internalIndex);
335         // System.arraycopy(this.vectorSI, internalIndex, vectorSINew, internalIndex - 1, this.indices.length - internalIndex);
336         indicesNew[internalIndex] = index;
337         vectorSINew[internalIndex] = valueSI;
338         this.indices = indicesNew;
339         this.vectorSI = vectorSINew;
340     }
341 
342     @Override
343     public final double[] getDenseVectorSI()
344     {
345         return toDense().vectorSI;
346     }
347 
348     @Override
349     public final DoubleVectorDataSparse copy()
350     {
351         double[] vCopy = new double[this.vectorSI.length];
352         System.arraycopy(this.vectorSI, 0, vCopy, 0, this.vectorSI.length);
353         int[] iCopy = new int[this.indices.length];
354         System.arraycopy(this.indices, 0, iCopy, 0, this.indices.length);
355         return new DoubleVectorDataSparse(vCopy, iCopy, this.size);
356     }
357 
358     /**
359      * Instantiate a DoubleVectorDataSparse from an array.
360      * @param valuesSI double[]; the (SI) values to store
361      * @return the DoubleVectorDataSparse
362      */
363     public static DoubleVectorDataSparse instantiate(final double[] valuesSI)
364     {
365         // determine number of non-null cells
366         int length = (int) Arrays.stream(valuesSI).parallel().filter(d -> d != 0.0).count();
367         double[] sparseSI = new double[length];
368         int[] indices = new int[length];
369 
370         // fill the sparse data structures. Cannot be parallelized because of stateful and sequence-sensitive count
371         int count = 0;
372         for (int i = 0; i < valuesSI.length; i++)
373         {
374             if (valuesSI[i] != 0.0)
375             {
376                 sparseSI[count] = valuesSI[i];
377                 indices[count] = i;
378                 count++;
379             }
380         }
381         return new DoubleVectorDataSparse(sparseSI, indices, valuesSI.length);
382     }
383 
384     @Override
385     public final DoubleVectorData plus(final DoubleVectorData right)
386     {
387         if (right.isDense())
388         {
389             DoubleVectorData result = right.plus(this);
390             return result;
391         }
392         checkSizes(right);
393         return this.copy().incrementBy(right);
394     }
395 
396     @Override
397     public final DoubleVectorData minus(final DoubleVectorData right)
398     {
399         return this.copy().decrementBy(right);
400     }
401 
402     @Override
403     public final DoubleVectorData times(final DoubleVectorData right)
404     {
405         return this.copy().multiplyBy(right);
406     }
407 
408     @Override
409     public final DoubleVectorData divide(final DoubleVectorData right) throws ValueRuntimeException
410     {
411         if (right.isSparse())
412         {
413             // Sparse divided by sparse makes a dense
414             return this.toDense().divideBy(right);
415         }
416         // Sparse divided by dense makes a sparse
417         return this.copy().divideBy(right);
418     }
419 
420     @Override
421     public int hashCode()
422     {
423         return super.hashCode();
424     }
425 
426     @Override
427     @SuppressWarnings({"checkstyle:needbraces", "checkstyle:designforextension"})
428     public boolean equals(final Object obj)
429     {
430         if (this == obj)
431             return true;
432         if (obj == null)
433             return false;
434         if (!(obj instanceof DoubleVectorData))
435             return false;
436         DoubleVectorData other = (DoubleVectorData) obj;
437         if (this.size() != other.size())
438             return false;
439         if (other instanceof DoubleVectorDataDense)
440             return super.equals(other);
441         if (getClass() != obj.getClass())
442             return false;
443         // Both are sparse
444         if (!Arrays.equals(this.indices, ((DoubleVectorDataSparse) other).indices))
445             return false;
446         return Arrays.equals(this.vectorSI, ((DoubleVectorDataSparse) other).vectorSI);
447     }
448 
449 }