Source code

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