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