View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      https://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  /*
19   * This is not the original file distributed by the Apache Software Foundation
20   * It has been modified by the Hipparchus project
21   */
22  package org.hipparchus.linear;
23  
24  import java.io.Serializable;
25  
26  import org.hipparchus.Field;
27  import org.hipparchus.FieldElement;
28  import org.hipparchus.exception.LocalizedCoreFormats;
29  import org.hipparchus.exception.MathIllegalArgumentException;
30  import org.hipparchus.exception.MathRuntimeException;
31  import org.hipparchus.exception.NullArgumentException;
32  import org.hipparchus.util.MathArrays;
33  import org.hipparchus.util.MathUtils;
34  import org.hipparchus.util.OpenIntToFieldHashMap;
35  
36  /**
37   * This class implements the {@link FieldVector} interface with a {@link OpenIntToFieldHashMap} backing store.
38   * <p>
39   *  Caveat: This implementation assumes that, for any {@code x},
40   *  the equality {@code x * 0d == 0d} holds. But it is is not true for
41   *  {@code NaN}. Moreover, zero entries will lose their sign.
42   *  Some operations (that involve {@code NaN} and/or infinities) may
43   *  thus give incorrect results.
44   * </p>
45   * @param <T> the type of the field elements
46   */
47  public class SparseFieldVector<T extends FieldElement<T>> implements FieldVector<T>, Serializable {
48      /**  Serialization identifier. */
49      private static final long serialVersionUID = 7841233292190413362L;
50      /** Field to which the elements belong. */
51      private final Field<T> field;
52      /** Entries of the vector. */
53      private final OpenIntToFieldHashMap<T> entries;
54      /** Dimension of the vector. */
55      private final int virtualSize;
56  
57      /**
58       * Build a 0-length vector.
59       * Zero-length vectors may be used to initialize construction of vectors
60       * by data gathering. We start with zero-length and use either the {@link
61       * #SparseFieldVector(SparseFieldVector, int)} constructor
62       * or one of the {@code append} method ({@link #append(FieldVector)} or
63       * {@link #append(SparseFieldVector)}) to gather data into this vector.
64       *
65       * @param field Field to which the elements belong.
66       */
67      public SparseFieldVector(Field<T> field) {
68          this(field, 0);
69      }
70  
71  
72      /**
73       * Construct a vector of zeroes.
74       *
75       * @param field Field to which the elements belong.
76       * @param dimension Size of the vector.
77       */
78      public SparseFieldVector(Field<T> field, int dimension) {
79          this.field = field;
80          virtualSize = dimension;
81          entries = new OpenIntToFieldHashMap<>(field);
82      }
83  
84      /**
85       * Build a resized vector, for use with append.
86       *
87       * @param v Original vector
88       * @param resize Amount to add.
89       */
90      protected SparseFieldVector(SparseFieldVector<T> v, int resize) {
91          field = v.field;
92          virtualSize = v.getDimension() + resize;
93          entries = new OpenIntToFieldHashMap<>(v.entries);
94      }
95  
96  
97      /**
98       * Build a vector with known the sparseness (for advanced use only).
99       *
100      * @param field Field to which the elements belong.
101      * @param dimension Size of the vector.
102      * @param expectedSize Expected number of non-zero entries.
103      */
104     public SparseFieldVector(Field<T> field, int dimension, int expectedSize) {
105         this.field = field;
106         virtualSize = dimension;
107         entries = new OpenIntToFieldHashMap<>(field,expectedSize);
108     }
109 
110     /**
111      * Create from a Field array.
112      * Only non-zero entries will be stored.
113      *
114      * @param field Field to which the elements belong.
115      * @param values Set of values to create from.
116      * @exception NullArgumentException if values is null
117      */
118     public SparseFieldVector(Field<T> field, T[] values) throws NullArgumentException {
119         MathUtils.checkNotNull(values);
120         this.field = field;
121         virtualSize = values.length;
122         entries = new OpenIntToFieldHashMap<>(field);
123         for (int key = 0; key < values.length; key++) {
124             T value = values[key];
125             entries.put(key, value);
126         }
127     }
128 
129     /**
130      * Copy constructor.
131      *
132      * @param v Instance to copy.
133      */
134     public SparseFieldVector(SparseFieldVector<T> v) {
135         field = v.field;
136         virtualSize = v.getDimension();
137         entries = new OpenIntToFieldHashMap<>(v.getEntries());
138     }
139 
140     /**
141      * Get the entries of this instance.
142      *
143      * @return the entries of this instance
144      */
145     private OpenIntToFieldHashMap<T> getEntries() {
146         return entries;
147     }
148 
149     /**
150      * Optimized method to add sparse vectors.
151      *
152      * @param v Vector to add.
153      * @return {@code this + v}.
154      * @throws MathIllegalArgumentException if {@code v} is not the same size as
155      * {@code this}.
156      */
157     public FieldVector<T> add(SparseFieldVector<T> v)
158         throws MathIllegalArgumentException {
159         checkVectorDimensions(v.getDimension());
160         SparseFieldVector<T> res = (SparseFieldVector<T>)copy();
161         OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator();
162         while (iter.hasNext()) {
163             iter.advance();
164             int key = iter.key();
165             T value = iter.value();
166             if (entries.containsKey(key)) {
167                 res.setEntry(key, entries.get(key).add(value));
168             } else {
169                 res.setEntry(key, value);
170             }
171         }
172         return res;
173 
174     }
175 
176     /**
177      * Construct a vector by appending a vector to this vector.
178      *
179      * @param v Vector to append to this one.
180      * @return a new vector.
181      */
182     public FieldVector<T> append(SparseFieldVector<T> v) {
183         SparseFieldVector<T> res = new SparseFieldVector<>(this, v.getDimension());
184         OpenIntToFieldHashMap<T>.Iterator iter = v.entries.iterator();
185         while (iter.hasNext()) {
186             iter.advance();
187             res.setEntry(iter.key() + virtualSize, iter.value());
188         }
189         return res;
190     }
191 
192     /** {@inheritDoc} */
193     @Override
194     public FieldVector<T> append(FieldVector<T> v) {
195         if (v instanceof SparseFieldVector<?>) {
196             return append((SparseFieldVector<T>) v);
197         } else {
198             final int n = v.getDimension();
199             FieldVector<T> res = new SparseFieldVector<>(this, n);
200             for (int i = 0; i < n; i++) {
201                 res.setEntry(i + virtualSize, v.getEntry(i));
202             }
203             return res;
204         }
205     }
206 
207     /** {@inheritDoc}
208      * @exception NullArgumentException if d is null
209      */
210     @Override
211     public FieldVector<T> append(T d) throws NullArgumentException {
212         MathUtils.checkNotNull(d);
213         FieldVector<T> res = new SparseFieldVector<>(this, 1);
214         res.setEntry(virtualSize, d);
215         return res;
216      }
217 
218     /** {@inheritDoc} */
219     @Override
220     public FieldVector<T> copy() {
221         return new SparseFieldVector<T>(this);
222     }
223 
224     /** {@inheritDoc} */
225     @Override
226     public T dotProduct(FieldVector<T> v) throws MathIllegalArgumentException {
227         checkVectorDimensions(v.getDimension());
228         T res = field.getZero();
229         OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
230         while (iter.hasNext()) {
231             iter.advance();
232             res = res.add(v.getEntry(iter.key()).multiply(iter.value()));
233         }
234         return res;
235     }
236 
237     /** {@inheritDoc} */
238     @Override
239     public FieldVector<T> ebeDivide(FieldVector<T> v)
240         throws MathIllegalArgumentException, MathRuntimeException {
241         checkVectorDimensions(v.getDimension());
242         SparseFieldVector<T> res = new SparseFieldVector<>(this);
243         OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
244         while (iter.hasNext()) {
245             iter.advance();
246             res.setEntry(iter.key(), iter.value().divide(v.getEntry(iter.key())));
247         }
248         return res;
249     }
250 
251     /** {@inheritDoc} */
252     @Override
253     public FieldVector<T> ebeMultiply(FieldVector<T> v)
254         throws MathIllegalArgumentException {
255         checkVectorDimensions(v.getDimension());
256         SparseFieldVector<T> res = new SparseFieldVector<>(this);
257         OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
258         while (iter.hasNext()) {
259             iter.advance();
260             res.setEntry(iter.key(), iter.value().multiply(v.getEntry(iter.key())));
261         }
262         return res;
263     }
264 
265     /** {@inheritDoc} */
266     @Override
267     public int getDimension() {
268         return virtualSize;
269     }
270 
271     /** {@inheritDoc} */
272     @Override
273     public T getEntry(int index) throws MathIllegalArgumentException {
274         checkIndex(index);
275         return entries.get(index);
276    }
277 
278     /** {@inheritDoc} */
279     @Override
280     public Field<T> getField() {
281         return field;
282     }
283 
284     /** {@inheritDoc} */
285     @Override
286     public FieldVector<T> getSubVector(int index, int n)
287         throws MathIllegalArgumentException {
288         if (n < 0) {
289             throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_OF_ELEMENTS_SHOULD_BE_POSITIVE, n);
290         }
291         checkIndex(index);
292         checkIndex(index + n - 1);
293         SparseFieldVector<T> res = new SparseFieldVector<>(field,n);
294         int end = index + n;
295         OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
296         while (iter.hasNext()) {
297             iter.advance();
298             int key = iter.key();
299             if (key >= index && key < end) {
300                 res.setEntry(key - index, iter.value());
301             }
302         }
303         return res;
304     }
305 
306     /** {@inheritDoc} */
307     @Override
308     public FieldVector<T> mapAdd(T d) throws NullArgumentException {
309         return copy().mapAddToSelf(d);
310     }
311 
312     /** {@inheritDoc} */
313     @Override
314     public FieldVector<T> mapAddToSelf(T d) throws NullArgumentException {
315         for (int i = 0; i < virtualSize; i++) {
316             setEntry(i, getEntry(i).add(d));
317         }
318         return this;
319     }
320 
321     /** {@inheritDoc} */
322     @Override
323     public FieldVector<T> mapDivide(T d)
324         throws NullArgumentException, MathRuntimeException {
325         return copy().mapDivideToSelf(d);
326     }
327 
328     /** {@inheritDoc} */
329     @Override
330     public FieldVector<T> mapDivideToSelf(T d)
331         throws NullArgumentException, MathRuntimeException {
332         OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
333         while (iter.hasNext()) {
334             iter.advance();
335             entries.put(iter.key(), iter.value().divide(d));
336         }
337         return this;
338     }
339 
340     /** {@inheritDoc} */
341     @Override
342     public FieldVector<T> mapInv() throws MathRuntimeException {
343         return copy().mapInvToSelf();
344     }
345 
346     /** {@inheritDoc} */
347     @Override
348     public FieldVector<T> mapInvToSelf() throws MathRuntimeException {
349         for (int i = 0; i < virtualSize; i++) {
350             setEntry(i, field.getOne().divide(getEntry(i)));
351         }
352         return this;
353     }
354 
355     /** {@inheritDoc} */
356     @Override
357     public FieldVector<T> mapMultiply(T d) throws NullArgumentException {
358         return copy().mapMultiplyToSelf(d);
359     }
360 
361     /** {@inheritDoc} */
362     @Override
363     public FieldVector<T> mapMultiplyToSelf(T d) throws NullArgumentException {
364         OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
365         while (iter.hasNext()) {
366             iter.advance();
367             entries.put(iter.key(), iter.value().multiply(d));
368         }
369         return this;
370     }
371 
372     /** {@inheritDoc} */
373     @Override
374     public FieldVector<T> mapSubtract(T d) throws NullArgumentException {
375         return copy().mapSubtractToSelf(d);
376     }
377 
378     /** {@inheritDoc} */
379     @Override
380     public FieldVector<T> mapSubtractToSelf(T d) throws NullArgumentException {
381         return mapAddToSelf(field.getZero().subtract(d));
382     }
383 
384     /**
385      * Optimized method to compute outer product when both vectors are sparse.
386      * @param v vector with which outer product should be computed
387      * @return the matrix outer product between instance and v
388      */
389     public FieldMatrix<T> outerProduct(SparseFieldVector<T> v) {
390         final int n = v.getDimension();
391         SparseFieldMatrix<T> res = new SparseFieldMatrix<>(field, virtualSize, n);
392         OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
393         while (iter.hasNext()) {
394             iter.advance();
395             OpenIntToFieldHashMap<T>.Iterator iter2 = v.entries.iterator();
396             while (iter2.hasNext()) {
397                 iter2.advance();
398                 res.setEntry(iter.key(), iter2.key(), iter.value().multiply(iter2.value()));
399             }
400         }
401         return res;
402     }
403 
404     /** {@inheritDoc} */
405     @Override
406     public FieldMatrix<T> outerProduct(FieldVector<T> v) {
407         if (v instanceof SparseFieldVector<?>) {
408             return outerProduct((SparseFieldVector<T>)v);
409         } else {
410             final int n = v.getDimension();
411             FieldMatrix<T> res = new SparseFieldMatrix<>(field, virtualSize, n);
412             OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
413             while (iter.hasNext()) {
414                 iter.advance();
415                 int row = iter.key();
416                 FieldElement<T>value = iter.value();
417                 for (int col = 0; col < n; col++) {
418                     res.setEntry(row, col, value.multiply(v.getEntry(col)));
419                 }
420             }
421             return res;
422         }
423     }
424 
425     /** {@inheritDoc} */
426     @Override
427     public FieldVector<T> projection(FieldVector<T> v)
428         throws MathIllegalArgumentException, MathRuntimeException {
429         checkVectorDimensions(v.getDimension());
430         return v.mapMultiply(dotProduct(v).divide(v.dotProduct(v)));
431     }
432 
433     /** {@inheritDoc}
434      * @exception NullArgumentException if value is null
435      */
436     @Override
437     public void set(T value) {
438         MathUtils.checkNotNull(value);
439         for (int i = 0; i < virtualSize; i++) {
440             setEntry(i, value);
441         }
442     }
443 
444     /** {@inheritDoc}
445      * @exception NullArgumentException if value is null
446      */
447     @Override
448     public void setEntry(int index, T value) throws MathIllegalArgumentException, NullArgumentException {
449         MathUtils.checkNotNull(value);
450         checkIndex(index);
451         entries.put(index, value);
452     }
453 
454     /** {@inheritDoc} */
455     @Override
456     public void setSubVector(int index, FieldVector<T> v)
457         throws MathIllegalArgumentException {
458         checkIndex(index);
459         checkIndex(index + v.getDimension() - 1);
460         final int n = v.getDimension();
461         for (int i = 0; i < n; i++) {
462             setEntry(i + index, v.getEntry(i));
463         }
464     }
465 
466     /**
467      * Optimized method to compute {@code this} minus {@code v}.
468      * @param v vector to be subtracted
469      * @return {@code this - v}
470      * @throws MathIllegalArgumentException if {@code v} is not the same size as
471      * {@code this}.
472      */
473     public SparseFieldVector<T> subtract(SparseFieldVector<T> v)
474         throws MathIllegalArgumentException {
475         checkVectorDimensions(v.getDimension());
476         SparseFieldVector<T> res = (SparseFieldVector<T>)copy();
477         OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator();
478         while (iter.hasNext()) {
479             iter.advance();
480             int key = iter.key();
481             if (entries.containsKey(key)) {
482                 res.setEntry(key, entries.get(key).subtract(iter.value()));
483             } else {
484                 res.setEntry(key, field.getZero().subtract(iter.value()));
485             }
486         }
487         return res;
488     }
489 
490     /** {@inheritDoc} */
491     @Override
492     public FieldVector<T> subtract(FieldVector<T> v)
493         throws MathIllegalArgumentException {
494         if (v instanceof SparseFieldVector<?>) {
495             return subtract((SparseFieldVector<T>)v);
496         } else {
497             final int n = v.getDimension();
498             checkVectorDimensions(n);
499             SparseFieldVector<T> res = new SparseFieldVector<>(this);
500             for (int i = 0; i < n; i++) {
501                 if (entries.containsKey(i)) {
502                     res.setEntry(i, entries.get(i).subtract(v.getEntry(i)));
503                 } else {
504                     res.setEntry(i, field.getZero().subtract(v.getEntry(i)));
505                 }
506             }
507             return res;
508         }
509     }
510 
511     /** {@inheritDoc} */
512     @Override
513     public T[] toArray() {
514         T[] res = MathArrays.buildArray(field, virtualSize);
515         OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
516         while (iter.hasNext()) {
517             iter.advance();
518             res[iter.key()] = iter.value();
519         }
520         return res;
521     }
522 
523     /**
524      * Check whether an index is valid.
525      *
526      * @param index Index to check.
527      * @throws MathIllegalArgumentException if the index is not valid.
528      */
529     private void checkIndex(final int index) throws MathIllegalArgumentException {
530         MathUtils.checkRangeInclusive(index, 0, getDimension() - 1);
531     }
532 
533     /**
534      * Checks that the indices of a subvector are valid.
535      *
536      * @param start the index of the first entry of the subvector
537      * @param end the index of the last entry of the subvector (inclusive)
538      * @throws MathIllegalArgumentException if {@code start} of {@code end} are not valid
539      * @throws MathIllegalArgumentException if {@code end < start}
540      */
541     private void checkIndices(final int start, final int end)
542         throws MathIllegalArgumentException {
543         final int dim = getDimension();
544         if ((start < 0) || (start >= dim)) {
545             throw new MathIllegalArgumentException(LocalizedCoreFormats.INDEX, start, 0,
546                                           dim - 1);
547         }
548         if ((end < 0) || (end >= dim)) {
549             throw new MathIllegalArgumentException(LocalizedCoreFormats.INDEX, end, 0,
550                                           dim - 1);
551         }
552         if (end < start) {
553             throw new MathIllegalArgumentException(LocalizedCoreFormats.INITIAL_ROW_AFTER_FINAL_ROW,
554                                                 end, start, false);
555         }
556     }
557 
558     /**
559      * Check if instance dimension is equal to some expected value.
560      *
561      * @param n Expected dimension.
562      * @throws MathIllegalArgumentException if the dimensions do not match.
563      */
564     protected void checkVectorDimensions(int n)
565         throws MathIllegalArgumentException {
566         if (getDimension() != n) {
567             throw new MathIllegalArgumentException(LocalizedCoreFormats.DIMENSIONS_MISMATCH,
568                                                    getDimension(), n);
569         }
570     }
571 
572     /** {@inheritDoc} */
573     @Override
574     public FieldVector<T> add(FieldVector<T> v) throws MathIllegalArgumentException {
575         if (v instanceof SparseFieldVector<?>) {
576             return add((SparseFieldVector<T>) v);
577         } else {
578             final int n = v.getDimension();
579             checkVectorDimensions(n);
580             SparseFieldVector<T> res = new SparseFieldVector<>(field, getDimension());
581             for (int i = 0; i < n; i++) {
582                 res.setEntry(i, v.getEntry(i).add(getEntry(i)));
583             }
584             return res;
585         }
586     }
587 
588     /**
589      * Visits (but does not alter) all entries of this vector in default order
590      * (increasing index).
591      *
592      * @param visitor the visitor to be used to process the entries of this
593      * vector
594      * @return the value returned by {@link FieldVectorPreservingVisitor#end()}
595      * at the end of the walk
596      */
597     public T walkInDefaultOrder(final FieldVectorPreservingVisitor<T> visitor) {
598         final int dim = getDimension();
599         visitor.start(dim, 0, dim - 1);
600         for (int i = 0; i < dim; i++) {
601             visitor.visit(i, getEntry(i));
602         }
603         return visitor.end();
604     }
605 
606     /**
607      * Visits (but does not alter) some entries of this vector in default order
608      * (increasing index).
609      *
610      * @param visitor visitor to be used to process the entries of this vector
611      * @param start the index of the first entry to be visited
612      * @param end the index of the last entry to be visited (inclusive)
613      * @return the value returned by {@link FieldVectorPreservingVisitor#end()}
614      * at the end of the walk
615      * @throws MathIllegalArgumentException if {@code end < start}.
616      * @throws MathIllegalArgumentException if the indices are not valid.
617      */
618     public T walkInDefaultOrder(final FieldVectorPreservingVisitor<T> visitor,
619                                 final int start, final int end)
620         throws MathIllegalArgumentException {
621         checkIndices(start, end);
622         visitor.start(getDimension(), start, end);
623         for (int i = start; i <= end; i++) {
624             visitor.visit(i, getEntry(i));
625         }
626         return visitor.end();
627     }
628 
629     /**
630      * Visits (but does not alter) all entries of this vector in optimized
631      * order. The order in which the entries are visited is selected so as to
632      * lead to the most efficient implementation; it might depend on the
633      * concrete implementation of this abstract class.
634      *
635      * @param visitor the visitor to be used to process the entries of this
636      * vector
637      * @return the value returned by {@link FieldVectorPreservingVisitor#end()}
638      * at the end of the walk
639      */
640     public T walkInOptimizedOrder(final FieldVectorPreservingVisitor<T> visitor) {
641         return walkInDefaultOrder(visitor);
642     }
643 
644     /**
645      * Visits (but does not alter) some entries of this vector in optimized
646      * order. The order in which the entries are visited is selected so as to
647      * lead to the most efficient implementation; it might depend on the
648      * concrete implementation of this abstract class.
649      *
650      * @param visitor visitor to be used to process the entries of this vector
651      * @param start the index of the first entry to be visited
652      * @param end the index of the last entry to be visited (inclusive)
653      * @return the value returned by {@link FieldVectorPreservingVisitor#end()}
654      * at the end of the walk
655      * @throws MathIllegalArgumentException if {@code end < start}.
656      * @throws MathIllegalArgumentException if the indices are not valid.
657      */
658     public T walkInOptimizedOrder(final FieldVectorPreservingVisitor<T> visitor,
659                                   final int start, final int end)
660         throws MathIllegalArgumentException {
661         return walkInDefaultOrder(visitor, start, end);
662     }
663 
664     /**
665      * Visits (and possibly alters) all entries of this vector in default order
666      * (increasing index).
667      *
668      * @param visitor the visitor to be used to process and modify the entries
669      * of this vector
670      * @return the value returned by {@link FieldVectorChangingVisitor#end()}
671      * at the end of the walk
672      */
673     public T walkInDefaultOrder(final FieldVectorChangingVisitor<T> visitor) {
674         final int dim = getDimension();
675         visitor.start(dim, 0, dim - 1);
676         for (int i = 0; i < dim; i++) {
677             setEntry(i, visitor.visit(i, getEntry(i)));
678         }
679         return visitor.end();
680     }
681 
682     /**
683      * Visits (and possibly alters) some entries of this vector in default order
684      * (increasing index).
685      *
686      * @param visitor visitor to be used to process the entries of this vector
687      * @param start the index of the first entry to be visited
688      * @param end the index of the last entry to be visited (inclusive)
689      * @return the value returned by {@link FieldVectorChangingVisitor#end()}
690      * at the end of the walk
691      * @throws MathIllegalArgumentException if {@code end < start}.
692      * @throws MathIllegalArgumentException if the indices are not valid.
693      */
694     public T walkInDefaultOrder(final FieldVectorChangingVisitor<T> visitor,
695                                 final int start, final int end)
696         throws MathIllegalArgumentException {
697         checkIndices(start, end);
698         visitor.start(getDimension(), start, end);
699         for (int i = start; i <= end; i++) {
700             setEntry(i, visitor.visit(i, getEntry(i)));
701         }
702         return visitor.end();
703     }
704 
705     /**
706      * Visits (and possibly alters) all entries of this vector in optimized
707      * order. The order in which the entries are visited is selected so as to
708      * lead to the most efficient implementation; it might depend on the
709      * concrete implementation of this abstract class.
710      *
711      * @param visitor the visitor to be used to process the entries of this
712      * vector
713      * @return the value returned by {@link FieldVectorChangingVisitor#end()}
714      * at the end of the walk
715      */
716     public T walkInOptimizedOrder(final FieldVectorChangingVisitor<T> visitor) {
717         return walkInDefaultOrder(visitor);
718     }
719 
720     /**
721      * Visits (and possibly change) some entries of this vector in optimized
722      * order. The order in which the entries are visited is selected so as to
723      * lead to the most efficient implementation; it might depend on the
724      * concrete implementation of this abstract class.
725      *
726      * @param visitor visitor to be used to process the entries of this vector
727      * @param start the index of the first entry to be visited
728      * @param end the index of the last entry to be visited (inclusive)
729      * @return the value returned by {@link FieldVectorChangingVisitor#end()}
730      * at the end of the walk
731      * @throws MathIllegalArgumentException if {@code end < start}.
732      * @throws MathIllegalArgumentException if the indices are not valid.
733      */
734     public T walkInOptimizedOrder(final FieldVectorChangingVisitor<T> visitor,
735                                   final int start, final int end)
736         throws MathIllegalArgumentException {
737         return walkInDefaultOrder(visitor, start, end);
738     }
739 
740     /** {@inheritDoc} */
741     @Override
742     public int hashCode() {
743         final int prime = 31;
744         int result = 1;
745         result = prime * result + ((field == null) ? 0 : field.hashCode());
746         result = prime * result + virtualSize;
747         OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
748         while (iter.hasNext()) {
749             iter.advance();
750             int temp = iter.value().hashCode();
751             result = prime * result + temp;
752         }
753         return result;
754     }
755 
756 
757     /** {@inheritDoc} */
758     @Override
759     public boolean equals(Object obj) {
760 
761         if (this == obj) {
762             return true;
763         }
764 
765         if (!(obj instanceof SparseFieldVector<?>)) {
766             return false;
767         }
768 
769         @SuppressWarnings("unchecked") // OK, because "else if" check below ensures that
770                                        // other must be the same type as this
771         SparseFieldVector<T> other = (SparseFieldVector<T>) obj;
772         if (field == null) {
773             if (other.field != null) {
774                 return false;
775             }
776         } else if (!field.equals(other.field)) {
777             return false;
778         }
779         if (virtualSize != other.virtualSize) {
780             return false;
781         }
782 
783         OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
784         while (iter.hasNext()) {
785             iter.advance();
786             T test = other.getEntry(iter.key());
787             if (!test.equals(iter.value())) {
788                 return false;
789             }
790         }
791         iter = other.getEntries().iterator();
792         while (iter.hasNext()) {
793             iter.advance();
794             T test = iter.value();
795             if (!test.equals(getEntry(iter.key()))) {
796                 return false;
797             }
798         }
799         return true;
800     }
801 }