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