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