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     */
017    package org.apache.commons.math3.linear;
018    
019    import java.io.Serializable;
020    
021    import org.apache.commons.math3.exception.DimensionMismatchException;
022    import org.apache.commons.math3.exception.MathArithmeticException;
023    import org.apache.commons.math3.exception.NotPositiveException;
024    import org.apache.commons.math3.exception.OutOfRangeException;
025    import org.apache.commons.math3.exception.util.LocalizedFormats;
026    import org.apache.commons.math3.util.FastMath;
027    import org.apache.commons.math3.util.OpenIntToDoubleHashMap;
028    import org.apache.commons.math3.util.OpenIntToDoubleHashMap.Iterator;
029    
030    /**
031     * This class implements the {@link RealVector} interface with a
032     * {@link OpenIntToDoubleHashMap} backing store.
033     * @version $Id: OpenMapRealVector.java 1416643 2012-12-03 19:37:14Z tn $
034     * @since 2.0
035     * @deprecated As of version 3.1, this class is deprecated, for reasons exposed
036     * in this JIRA
037     * <a href="https://issues.apache.org/jira/browse/MATH-870">ticket</a>. This
038     * class will be removed in version 4.0.
039     */
040    @Deprecated
041    public class OpenMapRealVector extends SparseRealVector
042        implements Serializable {
043        /** Default Tolerance for having a value considered zero. */
044        public static final double DEFAULT_ZERO_TOLERANCE = 1.0e-12;
045        /** Serializable version identifier. */
046        private static final long serialVersionUID = 8772222695580707260L;
047        /** Entries of the vector. */
048        private final OpenIntToDoubleHashMap entries;
049        /** Dimension of the vector. */
050        private final int virtualSize;
051        /** Tolerance for having a value considered zero. */
052        private final double epsilon;
053    
054        /**
055         * Build a 0-length vector.
056         * Zero-length vectors may be used to initialized construction of vectors
057         * by data gathering. We start with zero-length and use either the {@link
058         * #OpenMapRealVector(OpenMapRealVector, int)} constructor
059         * or one of the {@code append} method ({@link #append(double)},
060         * {@link #append(RealVector)}) to gather data into this vector.
061         */
062        public OpenMapRealVector() {
063            this(0, DEFAULT_ZERO_TOLERANCE);
064        }
065    
066        /**
067         * Construct a vector of zeroes.
068         *
069         * @param dimension Size of the vector.
070         */
071        public OpenMapRealVector(int dimension) {
072            this(dimension, DEFAULT_ZERO_TOLERANCE);
073        }
074    
075        /**
076         * Construct a vector of zeroes, specifying zero tolerance.
077         *
078         * @param dimension Size of the vector.
079         * @param epsilon Tolerance below which a value considered zero.
080         */
081        public OpenMapRealVector(int dimension, double epsilon) {
082            virtualSize = dimension;
083            entries = new OpenIntToDoubleHashMap(0.0);
084            this.epsilon = epsilon;
085        }
086    
087        /**
088         * Build a resized vector, for use with append.
089         *
090         * @param v Original vector.
091         * @param resize Amount to add.
092         */
093        protected OpenMapRealVector(OpenMapRealVector v, int resize) {
094            virtualSize = v.getDimension() + resize;
095            entries = new OpenIntToDoubleHashMap(v.entries);
096            epsilon = v.epsilon;
097        }
098    
099        /**
100         * Build a vector with known the sparseness (for advanced use only).
101         *
102         * @param dimension Size of the vector.
103         * @param expectedSize The expected number of non-zero entries.
104         */
105        public OpenMapRealVector(int dimension, int expectedSize) {
106            this(dimension, expectedSize, DEFAULT_ZERO_TOLERANCE);
107        }
108    
109        /**
110         * Build a vector with known the sparseness and zero tolerance
111         * setting (for advanced use only).
112         *
113         * @param dimension Size of the vector.
114         * @param expectedSize Expected number of non-zero entries.
115         * @param epsilon Tolerance below which a value is considered zero.
116         */
117        public OpenMapRealVector(int dimension, int expectedSize, double epsilon) {
118            virtualSize = dimension;
119            entries = new OpenIntToDoubleHashMap(expectedSize, 0.0);
120            this.epsilon = epsilon;
121        }
122    
123        /**
124         * Create from an array.
125         * Only non-zero entries will be stored.
126         *
127         * @param values Set of values to create from.
128         */
129        public OpenMapRealVector(double[] values) {
130            this(values, DEFAULT_ZERO_TOLERANCE);
131        }
132    
133        /**
134         * Create from an array, specifying zero tolerance.
135         * Only non-zero entries will be stored.
136         *
137         * @param values Set of values to create from.
138         * @param epsilon Tolerance below which a value is considered zero.
139         */
140        public OpenMapRealVector(double[] values, double epsilon) {
141            virtualSize = values.length;
142            entries = new OpenIntToDoubleHashMap(0.0);
143            this.epsilon = epsilon;
144            for (int key = 0; key < values.length; key++) {
145                double value = values[key];
146                if (!isDefaultValue(value)) {
147                    entries.put(key, value);
148                }
149            }
150        }
151    
152        /**
153         * Create from an array.
154         * Only non-zero entries will be stored.
155         *
156         * @param values The set of values to create from
157         */
158        public OpenMapRealVector(Double[] values) {
159            this(values, DEFAULT_ZERO_TOLERANCE);
160        }
161    
162        /**
163         * Create from an array.
164         * Only non-zero entries will be stored.
165         *
166         * @param values Set of values to create from.
167         * @param epsilon Tolerance below which a value is considered zero.
168         */
169        public OpenMapRealVector(Double[] values, double epsilon) {
170            virtualSize = values.length;
171            entries = new OpenIntToDoubleHashMap(0.0);
172            this.epsilon = epsilon;
173            for (int key = 0; key < values.length; key++) {
174                double value = values[key].doubleValue();
175                if (!isDefaultValue(value)) {
176                    entries.put(key, value);
177                }
178            }
179        }
180    
181        /**
182         * Copy constructor.
183         *
184         * @param v Instance to copy from.
185         */
186        public OpenMapRealVector(OpenMapRealVector v) {
187            virtualSize = v.getDimension();
188            entries = new OpenIntToDoubleHashMap(v.getEntries());
189            epsilon = v.epsilon;
190        }
191    
192        /**
193         * Generic copy constructor.
194         *
195         * @param v Instance to copy from.
196         */
197        public OpenMapRealVector(RealVector v) {
198            virtualSize = v.getDimension();
199            entries = new OpenIntToDoubleHashMap(0.0);
200            epsilon = DEFAULT_ZERO_TOLERANCE;
201            for (int key = 0; key < virtualSize; key++) {
202                double value = v.getEntry(key);
203                if (!isDefaultValue(value)) {
204                    entries.put(key, value);
205                }
206            }
207        }
208    
209        /**
210         * Get the entries of this instance.
211         *
212         * @return the entries of this instance.
213         */
214        private OpenIntToDoubleHashMap getEntries() {
215            return entries;
216        }
217    
218        /**
219         * Determine if this value is within epsilon of zero.
220         *
221         * @param value Value to test
222         * @return {@code true} if this value is within epsilon to zero,
223         * {@code false} otherwise.
224         * @since 2.1
225         */
226        protected boolean isDefaultValue(double value) {
227            return FastMath.abs(value) < epsilon;
228        }
229    
230        /** {@inheritDoc} */
231        @Override
232        public RealVector add(RealVector v)
233            throws DimensionMismatchException {
234            checkVectorDimensions(v.getDimension());
235            if (v instanceof OpenMapRealVector) {
236                return add((OpenMapRealVector) v);
237            } else {
238                return super.add(v);
239            }
240        }
241    
242        /**
243         * Optimized method to add two OpenMapRealVectors.
244         * It copies the larger vector, then iterates over the smaller.
245         *
246         * @param v Vector to add.
247         * @return the sum of {@code this} and {@code v}.
248         * @throws DimensionMismatchException if the dimensions do not match.
249         */
250        public OpenMapRealVector add(OpenMapRealVector v)
251            throws DimensionMismatchException {
252            checkVectorDimensions(v.getDimension());
253            boolean copyThis = entries.size() > v.entries.size();
254            OpenMapRealVector res = copyThis ? this.copy() : v.copy();
255            Iterator iter = copyThis ? v.entries.iterator() : entries.iterator();
256            OpenIntToDoubleHashMap randomAccess = copyThis ? entries : v.entries;
257            while (iter.hasNext()) {
258                iter.advance();
259                int key = iter.key();
260                if (randomAccess.containsKey(key)) {
261                    res.setEntry(key, randomAccess.get(key) + iter.value());
262                } else {
263                    res.setEntry(key, iter.value());
264                }
265            }
266            return res;
267        }
268    
269        /**
270         * Optimized method to append a OpenMapRealVector.
271         * @param v vector to append
272         * @return The result of appending {@code v} to self
273         */
274        public OpenMapRealVector append(OpenMapRealVector v) {
275            OpenMapRealVector res = new OpenMapRealVector(this, v.getDimension());
276            Iterator iter = v.entries.iterator();
277            while (iter.hasNext()) {
278                iter.advance();
279                res.setEntry(iter.key() + virtualSize, iter.value());
280            }
281            return res;
282        }
283    
284        /** {@inheritDoc} */
285        @Override
286        public OpenMapRealVector append(RealVector v) {
287            if (v instanceof OpenMapRealVector) {
288                return append((OpenMapRealVector) v);
289            } else {
290                final OpenMapRealVector res = new OpenMapRealVector(this, v.getDimension());
291                for (int i = 0; i < v.getDimension(); i++) {
292                    res.setEntry(i + virtualSize, v.getEntry(i));
293                }
294                return res;
295            }
296        }
297    
298        /** {@inheritDoc} */
299        @Override
300        public OpenMapRealVector append(double d) {
301            OpenMapRealVector res = new OpenMapRealVector(this, 1);
302            res.setEntry(virtualSize, d);
303            return res;
304        }
305    
306        /**
307         * {@inheritDoc}
308         * @since 2.1
309         */
310        @Override
311        public OpenMapRealVector copy() {
312            return new OpenMapRealVector(this);
313        }
314    
315        /**
316         * Computes the dot product.
317         * Note that the computation is now performed in the parent class: no
318         * performance improvement is to be expected from this overloaded
319         * method.
320         * The previous implementation was buggy and cannot be easily fixed
321         * (see MATH-795).
322         *
323         * @param v Vector.
324         * @return the dot product of this vector with {@code v}.
325         * @throws DimensionMismatchException if {@code v} is not the same size as
326         * {@code this} vector.
327         *
328         * @deprecated as of 3.1 (to be removed in 4.0). The computation is
329         * performed by the parent class. The method must be kept to maintain
330         * backwards compatibility.
331         */
332        @Deprecated
333        public double dotProduct(OpenMapRealVector v)
334            throws DimensionMismatchException {
335            return dotProduct((RealVector) v);
336        }
337    
338        /** {@inheritDoc} */
339        @Override
340        public OpenMapRealVector ebeDivide(RealVector v)
341            throws DimensionMismatchException {
342            checkVectorDimensions(v.getDimension());
343            OpenMapRealVector res = new OpenMapRealVector(this);
344            /*
345             * MATH-803: it is not sufficient to loop through non zero entries of
346             * this only. Indeed, if this[i] = 0d and v[i] = 0d, then
347             * this[i] / v[i] = NaN, and not 0d.
348             */
349            final int n = getDimension();
350            for (int i = 0; i < n; i++) {
351                res.setEntry(i, this.getEntry(i) / v.getEntry(i));
352            }
353            return res;
354        }
355    
356        /** {@inheritDoc} */
357        @Override
358        public OpenMapRealVector ebeMultiply(RealVector v)
359            throws DimensionMismatchException {
360            checkVectorDimensions(v.getDimension());
361            OpenMapRealVector res = new OpenMapRealVector(this);
362            Iterator iter = entries.iterator();
363            while (iter.hasNext()) {
364                iter.advance();
365                res.setEntry(iter.key(), iter.value() * v.getEntry(iter.key()));
366            }
367            /*
368             * MATH-803: the above loop assumes that 0d * x  = 0d for any double x,
369             * which allows to consider only the non-zero entries of this. However,
370             * this fails if this[i] == 0d and (v[i] = NaN or v[i] = Infinity).
371             *
372             * These special cases are handled below.
373             */
374            if (v.isNaN() || v.isInfinite()) {
375                final int n = getDimension();
376                for (int i = 0; i < n; i++) {
377                    final double y = v.getEntry(i);
378                    if (Double.isNaN(y)) {
379                        res.setEntry(i, Double.NaN);
380                    } else if (Double.isInfinite(y)) {
381                        final double x = this.getEntry(i);
382                        res.setEntry(i, x * y);
383                    }
384                }
385            }
386            return res;
387        }
388    
389        /** {@inheritDoc} */
390        @Override
391        public OpenMapRealVector getSubVector(int index, int n)
392            throws NotPositiveException, OutOfRangeException {
393            checkIndex(index);
394            if (n < 0) {
395                throw new NotPositiveException(LocalizedFormats.NUMBER_OF_ELEMENTS_SHOULD_BE_POSITIVE, n);
396            }
397            checkIndex(index + n - 1);
398            OpenMapRealVector res = new OpenMapRealVector(n);
399            int end = index + n;
400            Iterator iter = entries.iterator();
401            while (iter.hasNext()) {
402                iter.advance();
403                int key = iter.key();
404                if (key >= index && key < end) {
405                    res.setEntry(key - index, iter.value());
406                }
407            }
408            return res;
409        }
410    
411        /** {@inheritDoc} */
412        @Override
413        public int getDimension() {
414            return virtualSize;
415        }
416    
417        /**
418         * Optimized method to compute distance.
419         *
420         * @param v Vector to compute distance to.
421         * @return the distance from {@code this} and {@code v}.
422         * @throws DimensionMismatchException if the dimensions do not match.
423         */
424        public double getDistance(OpenMapRealVector v)
425            throws DimensionMismatchException {
426            checkVectorDimensions(v.getDimension());
427            Iterator iter = entries.iterator();
428            double res = 0;
429            while (iter.hasNext()) {
430                iter.advance();
431                int key = iter.key();
432                double delta;
433                delta = iter.value() - v.getEntry(key);
434                res += delta * delta;
435            }
436            iter = v.getEntries().iterator();
437            while (iter.hasNext()) {
438                iter.advance();
439                int key = iter.key();
440                if (!entries.containsKey(key)) {
441                    final double value = iter.value();
442                    res += value * value;
443                }
444            }
445            return FastMath.sqrt(res);
446        }
447    
448        /** {@inheritDoc} */
449        @Override
450        public double getDistance(RealVector v) throws DimensionMismatchException {
451            checkVectorDimensions(v.getDimension());
452            if (v instanceof OpenMapRealVector) {
453                return getDistance((OpenMapRealVector) v);
454            } else {
455                return super.getDistance(v);
456            }
457        }
458    
459        /** {@inheritDoc} */
460        @Override
461        public double getEntry(int index) throws OutOfRangeException {
462            checkIndex(index);
463            return entries.get(index);
464        }
465    
466        /**
467         * Distance between two vectors.
468         * This method computes the distance consistent with
469         * L<sub>1</sub> norm, i.e. the sum of the absolute values of
470         * elements differences.
471         *
472         * @param v Vector to which distance is requested.
473         * @return distance between this vector and {@code v}.
474         * @throws DimensionMismatchException if the dimensions do not match.
475         */
476        public double getL1Distance(OpenMapRealVector v)
477            throws DimensionMismatchException {
478            checkVectorDimensions(v.getDimension());
479            double max = 0;
480            Iterator iter = entries.iterator();
481            while (iter.hasNext()) {
482                iter.advance();
483                double delta = FastMath.abs(iter.value() - v.getEntry(iter.key()));
484                max += delta;
485            }
486            iter = v.getEntries().iterator();
487            while (iter.hasNext()) {
488                iter.advance();
489                int key = iter.key();
490                if (!entries.containsKey(key)) {
491                    double delta = FastMath.abs(iter.value());
492                    max +=  FastMath.abs(delta);
493                }
494            }
495            return max;
496        }
497    
498        /** {@inheritDoc} */
499        @Override
500        public double getL1Distance(RealVector v)
501            throws DimensionMismatchException {
502            checkVectorDimensions(v.getDimension());
503            if (v instanceof OpenMapRealVector) {
504                return getL1Distance((OpenMapRealVector) v);
505            } else {
506                return super.getL1Distance(v);
507            }
508        }
509    
510        /**
511         * Optimized method to compute LInfDistance.
512         *
513         * @param v Vector to compute distance from.
514         * @return the LInfDistance.
515         * @throws DimensionMismatchException if the dimensions do not match.
516         */
517        private double getLInfDistance(OpenMapRealVector v)
518            throws DimensionMismatchException {
519            checkVectorDimensions(v.getDimension());
520            double max = 0;
521            Iterator iter = entries.iterator();
522            while (iter.hasNext()) {
523                iter.advance();
524                double delta = FastMath.abs(iter.value() - v.getEntry(iter.key()));
525                if (delta > max) {
526                    max = delta;
527                }
528            }
529            iter = v.getEntries().iterator();
530            while (iter.hasNext()) {
531                iter.advance();
532                int key = iter.key();
533                if (!entries.containsKey(key)) {
534                    if (iter.value() > max) {
535                        max = iter.value();
536                    }
537                }
538            }
539            return max;
540        }
541    
542        /** {@inheritDoc} */
543        @Override
544        public double getLInfDistance(RealVector v)
545            throws DimensionMismatchException {
546            checkVectorDimensions(v.getDimension());
547            if (v instanceof OpenMapRealVector) {
548                return getLInfDistance((OpenMapRealVector) v);
549            } else {
550                return super.getLInfDistance(v);
551            }
552        }
553    
554        /** {@inheritDoc} */
555        @Override
556        public boolean isInfinite() {
557            boolean infiniteFound = false;
558            Iterator iter = entries.iterator();
559            while (iter.hasNext()) {
560                iter.advance();
561                final double value = iter.value();
562                if (Double.isNaN(value)) {
563                    return false;
564                }
565                if (Double.isInfinite(value)) {
566                    infiniteFound = true;
567                }
568            }
569            return infiniteFound;
570        }
571    
572        /** {@inheritDoc} */
573        @Override
574        public boolean isNaN() {
575            Iterator iter = entries.iterator();
576            while (iter.hasNext()) {
577                iter.advance();
578                if (Double.isNaN(iter.value())) {
579                    return true;
580                }
581            }
582            return false;
583        }
584    
585        /** {@inheritDoc} */
586        @Override
587        public OpenMapRealVector mapAdd(double d) {
588            return copy().mapAddToSelf(d);
589        }
590    
591        /** {@inheritDoc} */
592        @Override
593        public OpenMapRealVector mapAddToSelf(double d) {
594            for (int i = 0; i < virtualSize; i++) {
595                setEntry(i, getEntry(i) + d);
596            }
597            return this;
598        }
599    
600        /** {@inheritDoc} */
601        @Override
602        public void setEntry(int index, double value)
603            throws OutOfRangeException {
604            checkIndex(index);
605            if (!isDefaultValue(value)) {
606                entries.put(index, value);
607            } else if (entries.containsKey(index)) {
608                entries.remove(index);
609            }
610        }
611    
612        /** {@inheritDoc} */
613        @Override
614        public void setSubVector(int index, RealVector v)
615            throws OutOfRangeException {
616            checkIndex(index);
617            checkIndex(index + v.getDimension() - 1);
618            for (int i = 0; i < v.getDimension(); i++) {
619                setEntry(i + index, v.getEntry(i));
620            }
621        }
622    
623        /** {@inheritDoc} */
624        @Override
625        public void set(double value) {
626            for (int i = 0; i < virtualSize; i++) {
627                setEntry(i, value);
628            }
629        }
630    
631        /**
632         * Optimized method to subtract OpenMapRealVectors.
633         *
634         * @param v Vector to subtract from {@code this}.
635         * @return the difference of {@code this} and {@code v}.
636         * @throws DimensionMismatchException if the dimensions do not match.
637         */
638        public OpenMapRealVector subtract(OpenMapRealVector v)
639            throws DimensionMismatchException {
640            checkVectorDimensions(v.getDimension());
641            OpenMapRealVector res = copy();
642            Iterator iter = v.getEntries().iterator();
643            while (iter.hasNext()) {
644                iter.advance();
645                int key = iter.key();
646                if (entries.containsKey(key)) {
647                    res.setEntry(key, entries.get(key) - iter.value());
648                } else {
649                    res.setEntry(key, -iter.value());
650                }
651            }
652            return res;
653        }
654    
655        /** {@inheritDoc} */
656        @Override
657        public RealVector subtract(RealVector v)
658            throws DimensionMismatchException {
659            checkVectorDimensions(v.getDimension());
660            if (v instanceof OpenMapRealVector) {
661                return subtract((OpenMapRealVector) v);
662            } else {
663                return super.subtract(v);
664            }
665        }
666    
667        /** {@inheritDoc} */
668        @Override
669        public OpenMapRealVector unitVector() throws MathArithmeticException {
670            OpenMapRealVector res = copy();
671            res.unitize();
672            return res;
673        }
674    
675        /** {@inheritDoc} */
676        @Override
677        public void unitize() throws MathArithmeticException {
678            double norm = getNorm();
679            if (isDefaultValue(norm)) {
680                throw new MathArithmeticException(LocalizedFormats.ZERO_NORM);
681            }
682            Iterator iter = entries.iterator();
683            while (iter.hasNext()) {
684                iter.advance();
685                entries.put(iter.key(), iter.value() / norm);
686            }
687        }
688    
689        /** {@inheritDoc} */
690        @Override
691        public double[] toArray() {
692            double[] res = new double[virtualSize];
693            Iterator iter = entries.iterator();
694            while (iter.hasNext()) {
695                iter.advance();
696                res[iter.key()] = iter.value();
697            }
698            return res;
699        }
700    
701        /**
702         * {@inheritDoc}
703         * Implementation Note: This works on exact values, and as a result
704         * it is possible for {@code a.subtract(b)} to be the zero vector, while
705         * {@code a.hashCode() != b.hashCode()}.
706         */
707        @Override
708        public int hashCode() {
709            final int prime = 31;
710            int result = 1;
711            long temp;
712            temp = Double.doubleToLongBits(epsilon);
713            result = prime * result + (int) (temp ^ (temp >>> 32));
714            result = prime * result + virtualSize;
715            Iterator iter = entries.iterator();
716            while (iter.hasNext()) {
717                iter.advance();
718                temp = Double.doubleToLongBits(iter.value());
719                result = prime * result + (int) (temp ^ (temp >>32));
720            }
721            return result;
722        }
723    
724        /**
725         * {@inheritDoc}
726         * Implementation Note: This performs an exact comparison, and as a result
727         * it is possible for {@code a.subtract(b}} to be the zero vector, while
728         * {@code  a.equals(b) == false}.
729         */
730        @Override
731        public boolean equals(Object obj) {
732            if (this == obj) {
733                return true;
734            }
735            if (!(obj instanceof OpenMapRealVector)) {
736                return false;
737            }
738            OpenMapRealVector other = (OpenMapRealVector) obj;
739            if (virtualSize != other.virtualSize) {
740                return false;
741            }
742            if (Double.doubleToLongBits(epsilon) !=
743                Double.doubleToLongBits(other.epsilon)) {
744                return false;
745            }
746            Iterator iter = entries.iterator();
747            while (iter.hasNext()) {
748                iter.advance();
749                double test = other.getEntry(iter.key());
750                if (Double.doubleToLongBits(test) != Double.doubleToLongBits(iter.value())) {
751                    return false;
752                }
753            }
754            iter = other.getEntries().iterator();
755            while (iter.hasNext()) {
756                iter.advance();
757                double test = iter.value();
758                if (Double.doubleToLongBits(test) != Double.doubleToLongBits(getEntry(iter.key()))) {
759                    return false;
760                }
761            }
762            return true;
763        }
764    
765        /**
766         *
767         * @return the percentage of none zero elements as a decimal percent.
768         * @since 2.2
769         */
770        public double getSparsity() {
771            return (double)entries.size()/(double)getDimension();
772        }
773    
774        /** {@inheritDoc} */
775        @Override
776        public java.util.Iterator<Entry> sparseIterator() {
777            return new OpenMapSparseIterator();
778        }
779    
780        /**
781         * Implementation of {@code Entry} optimized for OpenMap.
782         * This implementation does not allow arbitrary calls to {@code setIndex}
783         * since the order in which entries are returned is undefined.
784         */
785        protected class OpenMapEntry extends Entry {
786            /** Iterator pointing to the entry. */
787            private final Iterator iter;
788    
789            /**
790             * Build an entry from an iterator point to an element.
791             *
792             * @param iter Iterator pointing to the entry.
793             */
794            protected OpenMapEntry(Iterator iter) {
795                this.iter = iter;
796            }
797    
798            /** {@inheritDoc} */
799            @Override
800            public double getValue() {
801                return iter.value();
802            }
803    
804            /** {@inheritDoc} */
805            @Override
806            public void setValue(double value) {
807                entries.put(iter.key(), value);
808            }
809    
810            /** {@inheritDoc} */
811            @Override
812            public int getIndex() {
813                return iter.key();
814            }
815    
816        }
817    
818        /**
819         * Iterator class to do iteration over just the non-zero elements.
820         * This implementation is fail-fast, so cannot be used to modify
821         * any zero element.
822         */
823        protected class OpenMapSparseIterator implements java.util.Iterator<Entry> {
824            /** Underlying iterator. */
825            private final Iterator iter;
826            /** Current entry. */
827            private final Entry current;
828    
829            /** Simple constructor. */
830            protected OpenMapSparseIterator() {
831                iter = entries.iterator();
832                current = new OpenMapEntry(iter);
833            }
834    
835            /** {@inheritDoc} */
836            public boolean hasNext() {
837                return iter.hasNext();
838            }
839    
840            /** {@inheritDoc} */
841            public Entry next() {
842                iter.advance();
843                return current;
844            }
845    
846            /** {@inheritDoc} */
847            public void remove() {
848                throw new UnsupportedOperationException("Not supported");
849            }
850        }
851    }