View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math3.linear;
18  
19  import java.io.Serializable;
20  
21  import org.apache.commons.math3.exception.DimensionMismatchException;
22  import org.apache.commons.math3.exception.MathArithmeticException;
23  import org.apache.commons.math3.exception.NotPositiveException;
24  import org.apache.commons.math3.exception.OutOfRangeException;
25  import org.apache.commons.math3.exception.util.LocalizedFormats;
26  import org.apache.commons.math3.util.FastMath;
27  import org.apache.commons.math3.util.OpenIntToDoubleHashMap;
28  import org.apache.commons.math3.util.OpenIntToDoubleHashMap.Iterator;
29  
30  /**
31   * This class implements the {@link RealVector} interface with a
32   * {@link OpenIntToDoubleHashMap} backing store.
33   * <p>
34   *  Caveat: This implementation assumes that, for any {@code x},
35   *  the equality {@code x * 0d == 0d} holds. But it is is not true for
36   *  {@code NaN}. Moreover, zero entries will lose their sign.
37   *  Some operations (that involve {@code NaN} and/or infinities) may
38   *  thus give incorrect results, like multiplications, divisions or
39   *  functions mapping.
40   * </p>
41   * @version $Id: OpenMapRealVector.java 1570254 2014-02-20 16:16:19Z luc $
42   * @since 2.0
43   */
44  public class OpenMapRealVector extends SparseRealVector
45      implements Serializable {
46      /** Default Tolerance for having a value considered zero. */
47      public static final double DEFAULT_ZERO_TOLERANCE = 1.0e-12;
48      /** Serializable version identifier. */
49      private static final long serialVersionUID = 8772222695580707260L;
50      /** Entries of the vector. */
51      private final OpenIntToDoubleHashMap entries;
52      /** Dimension of the vector. */
53      private final int virtualSize;
54      /** Tolerance for having a value considered zero. */
55      private final double epsilon;
56  
57      /**
58       * Build a 0-length vector.
59       * Zero-length vectors may be used to initialized construction of vectors
60       * by data gathering. We start with zero-length and use either the {@link
61       * #OpenMapRealVector(OpenMapRealVector, int)} constructor
62       * or one of the {@code append} method ({@link #append(double)},
63       * {@link #append(RealVector)}) to gather data into this vector.
64       */
65      public OpenMapRealVector() {
66          this(0, DEFAULT_ZERO_TOLERANCE);
67      }
68  
69      /**
70       * Construct a vector of zeroes.
71       *
72       * @param dimension Size of the vector.
73       */
74      public OpenMapRealVector(int dimension) {
75          this(dimension, DEFAULT_ZERO_TOLERANCE);
76      }
77  
78      /**
79       * Construct a vector of zeroes, specifying zero tolerance.
80       *
81       * @param dimension Size of the vector.
82       * @param epsilon Tolerance below which a value considered zero.
83       */
84      public OpenMapRealVector(int dimension, double epsilon) {
85          virtualSize = dimension;
86          entries = new OpenIntToDoubleHashMap(0.0);
87          this.epsilon = epsilon;
88      }
89  
90      /**
91       * Build a resized vector, for use with append.
92       *
93       * @param v Original vector.
94       * @param resize Amount to add.
95       */
96      protected OpenMapRealVector(OpenMapRealVector v, int resize) {
97          virtualSize = v.getDimension() + resize;
98          entries = new OpenIntToDoubleHashMap(v.entries);
99          epsilon = v.epsilon;
100     }
101 
102     /**
103      * Build a vector with known the sparseness (for advanced use only).
104      *
105      * @param dimension Size of the vector.
106      * @param expectedSize The expected number of non-zero entries.
107      */
108     public OpenMapRealVector(int dimension, int expectedSize) {
109         this(dimension, expectedSize, DEFAULT_ZERO_TOLERANCE);
110     }
111 
112     /**
113      * Build a vector with known the sparseness and zero tolerance
114      * setting (for advanced use only).
115      *
116      * @param dimension Size of the vector.
117      * @param expectedSize Expected number of non-zero entries.
118      * @param epsilon Tolerance below which a value is considered zero.
119      */
120     public OpenMapRealVector(int dimension, int expectedSize, double epsilon) {
121         virtualSize = dimension;
122         entries = new OpenIntToDoubleHashMap(expectedSize, 0.0);
123         this.epsilon = epsilon;
124     }
125 
126     /**
127      * Create from an array.
128      * Only non-zero entries will be stored.
129      *
130      * @param values Set of values to create from.
131      */
132     public OpenMapRealVector(double[] values) {
133         this(values, DEFAULT_ZERO_TOLERANCE);
134     }
135 
136     /**
137      * Create from an array, specifying zero tolerance.
138      * Only non-zero entries will be stored.
139      *
140      * @param values Set of values to create from.
141      * @param epsilon Tolerance below which a value is considered zero.
142      */
143     public OpenMapRealVector(double[] values, double epsilon) {
144         virtualSize = values.length;
145         entries = new OpenIntToDoubleHashMap(0.0);
146         this.epsilon = epsilon;
147         for (int key = 0; key < values.length; key++) {
148             double value = values[key];
149             if (!isDefaultValue(value)) {
150                 entries.put(key, value);
151             }
152         }
153     }
154 
155     /**
156      * Create from an array.
157      * Only non-zero entries will be stored.
158      *
159      * @param values The set of values to create from
160      */
161     public OpenMapRealVector(Double[] values) {
162         this(values, DEFAULT_ZERO_TOLERANCE);
163     }
164 
165     /**
166      * Create from an array.
167      * Only non-zero entries will be stored.
168      *
169      * @param values Set of values to create from.
170      * @param epsilon Tolerance below which a value is considered zero.
171      */
172     public OpenMapRealVector(Double[] values, double epsilon) {
173         virtualSize = values.length;
174         entries = new OpenIntToDoubleHashMap(0.0);
175         this.epsilon = epsilon;
176         for (int key = 0; key < values.length; key++) {
177             double value = values[key].doubleValue();
178             if (!isDefaultValue(value)) {
179                 entries.put(key, value);
180             }
181         }
182     }
183 
184     /**
185      * Copy constructor.
186      *
187      * @param v Instance to copy from.
188      */
189     public OpenMapRealVector(OpenMapRealVector v) {
190         virtualSize = v.getDimension();
191         entries = new OpenIntToDoubleHashMap(v.getEntries());
192         epsilon = v.epsilon;
193     }
194 
195     /**
196      * Generic copy constructor.
197      *
198      * @param v Instance to copy from.
199      */
200     public OpenMapRealVector(RealVector v) {
201         virtualSize = v.getDimension();
202         entries = new OpenIntToDoubleHashMap(0.0);
203         epsilon = DEFAULT_ZERO_TOLERANCE;
204         for (int key = 0; key < virtualSize; key++) {
205             double value = v.getEntry(key);
206             if (!isDefaultValue(value)) {
207                 entries.put(key, value);
208             }
209         }
210     }
211 
212     /**
213      * Get the entries of this instance.
214      *
215      * @return the entries of this instance.
216      */
217     private OpenIntToDoubleHashMap getEntries() {
218         return entries;
219     }
220 
221     /**
222      * Determine if this value is within epsilon of zero.
223      *
224      * @param value Value to test
225      * @return {@code true} if this value is within epsilon to zero,
226      * {@code false} otherwise.
227      * @since 2.1
228      */
229     protected boolean isDefaultValue(double value) {
230         return FastMath.abs(value) < epsilon;
231     }
232 
233     /** {@inheritDoc} */
234     @Override
235     public RealVector add(RealVector v)
236         throws DimensionMismatchException {
237         checkVectorDimensions(v.getDimension());
238         if (v instanceof OpenMapRealVector) {
239             return add((OpenMapRealVector) v);
240         } else {
241             return super.add(v);
242         }
243     }
244 
245     /**
246      * Optimized method to add two OpenMapRealVectors.
247      * It copies the larger vector, then iterates over the smaller.
248      *
249      * @param v Vector to add.
250      * @return the sum of {@code this} and {@code v}.
251      * @throws DimensionMismatchException if the dimensions do not match.
252      */
253     public OpenMapRealVector add(OpenMapRealVector v)
254         throws DimensionMismatchException {
255         checkVectorDimensions(v.getDimension());
256         boolean copyThis = entries.size() > v.entries.size();
257         OpenMapRealVector res = copyThis ? this.copy() : v.copy();
258         Iterator iter = copyThis ? v.entries.iterator() : entries.iterator();
259         OpenIntToDoubleHashMap randomAccess = copyThis ? entries : v.entries;
260         while (iter.hasNext()) {
261             iter.advance();
262             int key = iter.key();
263             if (randomAccess.containsKey(key)) {
264                 res.setEntry(key, randomAccess.get(key) + iter.value());
265             } else {
266                 res.setEntry(key, iter.value());
267             }
268         }
269         return res;
270     }
271 
272     /**
273      * Optimized method to append a OpenMapRealVector.
274      * @param v vector to append
275      * @return The result of appending {@code v} to self
276      */
277     public OpenMapRealVector append(OpenMapRealVector v) {
278         OpenMapRealVector res = new OpenMapRealVector(this, v.getDimension());
279         Iterator iter = v.entries.iterator();
280         while (iter.hasNext()) {
281             iter.advance();
282             res.setEntry(iter.key() + virtualSize, iter.value());
283         }
284         return res;
285     }
286 
287     /** {@inheritDoc} */
288     @Override
289     public OpenMapRealVector append(RealVector v) {
290         if (v instanceof OpenMapRealVector) {
291             return append((OpenMapRealVector) v);
292         } else {
293             final OpenMapRealVector res = new OpenMapRealVector(this, v.getDimension());
294             for (int i = 0; i < v.getDimension(); i++) {
295                 res.setEntry(i + virtualSize, v.getEntry(i));
296             }
297             return res;
298         }
299     }
300 
301     /** {@inheritDoc} */
302     @Override
303     public OpenMapRealVector append(double d) {
304         OpenMapRealVector res = new OpenMapRealVector(this, 1);
305         res.setEntry(virtualSize, d);
306         return res;
307     }
308 
309     /**
310      * {@inheritDoc}
311      * @since 2.1
312      */
313     @Override
314     public OpenMapRealVector copy() {
315         return new OpenMapRealVector(this);
316     }
317 
318     /**
319      * Computes the dot product.
320      * Note that the computation is now performed in the parent class: no
321      * performance improvement is to be expected from this overloaded
322      * method.
323      * The previous implementation was buggy and cannot be easily fixed
324      * (see MATH-795).
325      *
326      * @param v Vector.
327      * @return the dot product of this vector with {@code v}.
328      * @throws DimensionMismatchException if {@code v} is not the same size as
329      * {@code this} vector.
330      *
331      * @deprecated as of 3.1 (to be removed in 4.0). The computation is
332      * performed by the parent class. The method must be kept to maintain
333      * backwards compatibility.
334      */
335     @Deprecated
336     public double dotProduct(OpenMapRealVector v)
337         throws DimensionMismatchException {
338         return dotProduct((RealVector) v);
339     }
340 
341     /** {@inheritDoc} */
342     @Override
343     public OpenMapRealVector ebeDivide(RealVector v)
344         throws DimensionMismatchException {
345         checkVectorDimensions(v.getDimension());
346         OpenMapRealVector res = new OpenMapRealVector(this);
347         /*
348          * MATH-803: it is not sufficient to loop through non zero entries of
349          * this only. Indeed, if this[i] = 0d and v[i] = 0d, then
350          * this[i] / v[i] = NaN, and not 0d.
351          */
352         final int n = getDimension();
353         for (int i = 0; i < n; i++) {
354             res.setEntry(i, this.getEntry(i) / v.getEntry(i));
355         }
356         return res;
357     }
358 
359     /** {@inheritDoc} */
360     @Override
361     public OpenMapRealVector ebeMultiply(RealVector v)
362         throws DimensionMismatchException {
363         checkVectorDimensions(v.getDimension());
364         OpenMapRealVector res = new OpenMapRealVector(this);
365         Iterator iter = entries.iterator();
366         while (iter.hasNext()) {
367             iter.advance();
368             res.setEntry(iter.key(), iter.value() * v.getEntry(iter.key()));
369         }
370         return res;
371     }
372 
373     /** {@inheritDoc} */
374     @Override
375     public OpenMapRealVector getSubVector(int index, int n)
376         throws NotPositiveException, OutOfRangeException {
377         checkIndex(index);
378         if (n < 0) {
379             throw new NotPositiveException(LocalizedFormats.NUMBER_OF_ELEMENTS_SHOULD_BE_POSITIVE, n);
380         }
381         checkIndex(index + n - 1);
382         OpenMapRealVector res = new OpenMapRealVector(n);
383         int end = index + n;
384         Iterator iter = entries.iterator();
385         while (iter.hasNext()) {
386             iter.advance();
387             int key = iter.key();
388             if (key >= index && key < end) {
389                 res.setEntry(key - index, iter.value());
390             }
391         }
392         return res;
393     }
394 
395     /** {@inheritDoc} */
396     @Override
397     public int getDimension() {
398         return virtualSize;
399     }
400 
401     /**
402      * Optimized method to compute distance.
403      *
404      * @param v Vector to compute distance to.
405      * @return the distance from {@code this} and {@code v}.
406      * @throws DimensionMismatchException if the dimensions do not match.
407      */
408     public double getDistance(OpenMapRealVector v)
409         throws DimensionMismatchException {
410         checkVectorDimensions(v.getDimension());
411         Iterator iter = entries.iterator();
412         double res = 0;
413         while (iter.hasNext()) {
414             iter.advance();
415             int key = iter.key();
416             double delta;
417             delta = iter.value() - v.getEntry(key);
418             res += delta * delta;
419         }
420         iter = v.getEntries().iterator();
421         while (iter.hasNext()) {
422             iter.advance();
423             int key = iter.key();
424             if (!entries.containsKey(key)) {
425                 final double value = iter.value();
426                 res += value * value;
427             }
428         }
429         return FastMath.sqrt(res);
430     }
431 
432     /** {@inheritDoc} */
433     @Override
434     public double getDistance(RealVector v) throws DimensionMismatchException {
435         checkVectorDimensions(v.getDimension());
436         if (v instanceof OpenMapRealVector) {
437             return getDistance((OpenMapRealVector) v);
438         } else {
439             return super.getDistance(v);
440         }
441     }
442 
443     /** {@inheritDoc} */
444     @Override
445     public double getEntry(int index) throws OutOfRangeException {
446         checkIndex(index);
447         return entries.get(index);
448     }
449 
450     /**
451      * Distance between two vectors.
452      * This method computes the distance consistent with
453      * L<sub>1</sub> norm, i.e. the sum of the absolute values of
454      * elements differences.
455      *
456      * @param v Vector to which distance is requested.
457      * @return distance between this vector and {@code v}.
458      * @throws DimensionMismatchException if the dimensions do not match.
459      */
460     public double getL1Distance(OpenMapRealVector v)
461         throws DimensionMismatchException {
462         checkVectorDimensions(v.getDimension());
463         double max = 0;
464         Iterator iter = entries.iterator();
465         while (iter.hasNext()) {
466             iter.advance();
467             double delta = FastMath.abs(iter.value() - v.getEntry(iter.key()));
468             max += delta;
469         }
470         iter = v.getEntries().iterator();
471         while (iter.hasNext()) {
472             iter.advance();
473             int key = iter.key();
474             if (!entries.containsKey(key)) {
475                 double delta = FastMath.abs(iter.value());
476                 max +=  FastMath.abs(delta);
477             }
478         }
479         return max;
480     }
481 
482     /** {@inheritDoc} */
483     @Override
484     public double getL1Distance(RealVector v)
485         throws DimensionMismatchException {
486         checkVectorDimensions(v.getDimension());
487         if (v instanceof OpenMapRealVector) {
488             return getL1Distance((OpenMapRealVector) v);
489         } else {
490             return super.getL1Distance(v);
491         }
492     }
493 
494     /**
495      * Optimized method to compute LInfDistance.
496      *
497      * @param v Vector to compute distance from.
498      * @return the LInfDistance.
499      * @throws DimensionMismatchException if the dimensions do not match.
500      */
501     private double getLInfDistance(OpenMapRealVector v)
502         throws DimensionMismatchException {
503         checkVectorDimensions(v.getDimension());
504         double max = 0;
505         Iterator iter = entries.iterator();
506         while (iter.hasNext()) {
507             iter.advance();
508             double delta = FastMath.abs(iter.value() - v.getEntry(iter.key()));
509             if (delta > max) {
510                 max = delta;
511             }
512         }
513         iter = v.getEntries().iterator();
514         while (iter.hasNext()) {
515             iter.advance();
516             int key = iter.key();
517             if (!entries.containsKey(key) && iter.value() > max) {
518                 max = iter.value();
519             }
520         }
521         return max;
522     }
523 
524     /** {@inheritDoc} */
525     @Override
526     public double getLInfDistance(RealVector v)
527         throws DimensionMismatchException {
528         checkVectorDimensions(v.getDimension());
529         if (v instanceof OpenMapRealVector) {
530             return getLInfDistance((OpenMapRealVector) v);
531         } else {
532             return super.getLInfDistance(v);
533         }
534     }
535 
536     /** {@inheritDoc} */
537     @Override
538     public boolean isInfinite() {
539         boolean infiniteFound = false;
540         Iterator iter = entries.iterator();
541         while (iter.hasNext()) {
542             iter.advance();
543             final double value = iter.value();
544             if (Double.isNaN(value)) {
545                 return false;
546             }
547             if (Double.isInfinite(value)) {
548                 infiniteFound = true;
549             }
550         }
551         return infiniteFound;
552     }
553 
554     /** {@inheritDoc} */
555     @Override
556     public boolean isNaN() {
557         Iterator iter = entries.iterator();
558         while (iter.hasNext()) {
559             iter.advance();
560             if (Double.isNaN(iter.value())) {
561                 return true;
562             }
563         }
564         return false;
565     }
566 
567     /** {@inheritDoc} */
568     @Override
569     public OpenMapRealVector mapAdd(double d) {
570         return copy().mapAddToSelf(d);
571     }
572 
573     /** {@inheritDoc} */
574     @Override
575     public OpenMapRealVector mapAddToSelf(double d) {
576         for (int i = 0; i < virtualSize; i++) {
577             setEntry(i, getEntry(i) + d);
578         }
579         return this;
580     }
581 
582     /** {@inheritDoc} */
583     @Override
584     public void setEntry(int index, double value)
585         throws OutOfRangeException {
586         checkIndex(index);
587         if (!isDefaultValue(value)) {
588             entries.put(index, value);
589         } else if (entries.containsKey(index)) {
590             entries.remove(index);
591         }
592     }
593 
594     /** {@inheritDoc} */
595     @Override
596     public void setSubVector(int index, RealVector v)
597         throws OutOfRangeException {
598         checkIndex(index);
599         checkIndex(index + v.getDimension() - 1);
600         for (int i = 0; i < v.getDimension(); i++) {
601             setEntry(i + index, v.getEntry(i));
602         }
603     }
604 
605     /** {@inheritDoc} */
606     @Override
607     public void set(double value) {
608         for (int i = 0; i < virtualSize; i++) {
609             setEntry(i, value);
610         }
611     }
612 
613     /**
614      * Optimized method to subtract OpenMapRealVectors.
615      *
616      * @param v Vector to subtract from {@code this}.
617      * @return the difference of {@code this} and {@code v}.
618      * @throws DimensionMismatchException if the dimensions do not match.
619      */
620     public OpenMapRealVector subtract(OpenMapRealVector v)
621         throws DimensionMismatchException {
622         checkVectorDimensions(v.getDimension());
623         OpenMapRealVector res = copy();
624         Iterator iter = v.getEntries().iterator();
625         while (iter.hasNext()) {
626             iter.advance();
627             int key = iter.key();
628             if (entries.containsKey(key)) {
629                 res.setEntry(key, entries.get(key) - iter.value());
630             } else {
631                 res.setEntry(key, -iter.value());
632             }
633         }
634         return res;
635     }
636 
637     /** {@inheritDoc} */
638     @Override
639     public RealVector subtract(RealVector v)
640         throws DimensionMismatchException {
641         checkVectorDimensions(v.getDimension());
642         if (v instanceof OpenMapRealVector) {
643             return subtract((OpenMapRealVector) v);
644         } else {
645             return super.subtract(v);
646         }
647     }
648 
649     /** {@inheritDoc} */
650     @Override
651     public OpenMapRealVector unitVector() throws MathArithmeticException {
652         OpenMapRealVector res = copy();
653         res.unitize();
654         return res;
655     }
656 
657     /** {@inheritDoc} */
658     @Override
659     public void unitize() throws MathArithmeticException {
660         double norm = getNorm();
661         if (isDefaultValue(norm)) {
662             throw new MathArithmeticException(LocalizedFormats.ZERO_NORM);
663         }
664         Iterator iter = entries.iterator();
665         while (iter.hasNext()) {
666             iter.advance();
667             entries.put(iter.key(), iter.value() / norm);
668         }
669     }
670 
671     /** {@inheritDoc} */
672     @Override
673     public double[] toArray() {
674         double[] res = new double[virtualSize];
675         Iterator iter = entries.iterator();
676         while (iter.hasNext()) {
677             iter.advance();
678             res[iter.key()] = iter.value();
679         }
680         return res;
681     }
682 
683     /**
684      * {@inheritDoc}
685      * Implementation Note: This works on exact values, and as a result
686      * it is possible for {@code a.subtract(b)} to be the zero vector, while
687      * {@code a.hashCode() != b.hashCode()}.
688      */
689     @Override
690     public int hashCode() {
691         final int prime = 31;
692         int result = 1;
693         long temp;
694         temp = Double.doubleToLongBits(epsilon);
695         result = prime * result + (int) (temp ^ (temp >>> 32));
696         result = prime * result + virtualSize;
697         Iterator iter = entries.iterator();
698         while (iter.hasNext()) {
699             iter.advance();
700             temp = Double.doubleToLongBits(iter.value());
701             result = prime * result + (int) (temp ^ (temp >>32));
702         }
703         return result;
704     }
705 
706     /**
707      * {@inheritDoc}
708      * Implementation Note: This performs an exact comparison, and as a result
709      * it is possible for {@code a.subtract(b}} to be the zero vector, while
710      * {@code  a.equals(b) == false}.
711      */
712     @Override
713     public boolean equals(Object obj) {
714         if (this == obj) {
715             return true;
716         }
717         if (!(obj instanceof OpenMapRealVector)) {
718             return false;
719         }
720         OpenMapRealVector other = (OpenMapRealVector) obj;
721         if (virtualSize != other.virtualSize) {
722             return false;
723         }
724         if (Double.doubleToLongBits(epsilon) !=
725             Double.doubleToLongBits(other.epsilon)) {
726             return false;
727         }
728         Iterator iter = entries.iterator();
729         while (iter.hasNext()) {
730             iter.advance();
731             double test = other.getEntry(iter.key());
732             if (Double.doubleToLongBits(test) != Double.doubleToLongBits(iter.value())) {
733                 return false;
734             }
735         }
736         iter = other.getEntries().iterator();
737         while (iter.hasNext()) {
738             iter.advance();
739             double test = iter.value();
740             if (Double.doubleToLongBits(test) != Double.doubleToLongBits(getEntry(iter.key()))) {
741                 return false;
742             }
743         }
744         return true;
745     }
746 
747     /**
748      *
749      * @return the percentage of none zero elements as a decimal percent.
750      * @since 2.2
751      */
752     public double getSparsity() {
753         return (double)entries.size()/(double)getDimension();
754     }
755 
756     /** {@inheritDoc} */
757     @Override
758     public java.util.Iterator<Entry> sparseIterator() {
759         return new OpenMapSparseIterator();
760     }
761 
762     /**
763      * Implementation of {@code Entry} optimized for OpenMap.
764      * This implementation does not allow arbitrary calls to {@code setIndex}
765      * since the order in which entries are returned is undefined.
766      */
767     protected class OpenMapEntry extends Entry {
768         /** Iterator pointing to the entry. */
769         private final Iterator iter;
770 
771         /**
772          * Build an entry from an iterator point to an element.
773          *
774          * @param iter Iterator pointing to the entry.
775          */
776         protected OpenMapEntry(Iterator iter) {
777             this.iter = iter;
778         }
779 
780         /** {@inheritDoc} */
781         @Override
782         public double getValue() {
783             return iter.value();
784         }
785 
786         /** {@inheritDoc} */
787         @Override
788         public void setValue(double value) {
789             entries.put(iter.key(), value);
790         }
791 
792         /** {@inheritDoc} */
793         @Override
794         public int getIndex() {
795             return iter.key();
796         }
797 
798     }
799 
800     /**
801      * Iterator class to do iteration over just the non-zero elements.
802      * This implementation is fail-fast, so cannot be used to modify
803      * any zero element.
804      */
805     protected class OpenMapSparseIterator implements java.util.Iterator<Entry> {
806         /** Underlying iterator. */
807         private final Iterator iter;
808         /** Current entry. */
809         private final Entry current;
810 
811         /** Simple constructor. */
812         protected OpenMapSparseIterator() {
813             iter = entries.iterator();
814             current = new OpenMapEntry(iter);
815         }
816 
817         /** {@inheritDoc} */
818         public boolean hasNext() {
819             return iter.hasNext();
820         }
821 
822         /** {@inheritDoc} */
823         public Entry next() {
824             iter.advance();
825             return current;
826         }
827 
828         /** {@inheritDoc} */
829         public void remove() {
830             throw new UnsupportedOperationException("Not supported");
831         }
832     }
833 }