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   * @version $Id: OpenMapRealVector.java 1462503 2013-03-29 15:48:27Z luc $
34   * @since 2.0
35   * @deprecated As of version 3.1, this class is deprecated, for reasons exposed
36   * in this JIRA
37   * <a href="https://issues.apache.org/jira/browse/MATH-870">ticket</a>. This
38   * class will be removed in version 4.0.
39   */
40  @Deprecated
41  public class OpenMapRealVector extends SparseRealVector
42      implements Serializable {
43      /** Default Tolerance for having a value considered zero. */
44      public static final double DEFAULT_ZERO_TOLERANCE = 1.0e-12;
45      /** Serializable version identifier. */
46      private static final long serialVersionUID = 8772222695580707260L;
47      /** Entries of the vector. */
48      private final OpenIntToDoubleHashMap entries;
49      /** Dimension of the vector. */
50      private final int virtualSize;
51      /** Tolerance for having a value considered zero. */
52      private final double epsilon;
53  
54      /**
55       * Build a 0-length vector.
56       * Zero-length vectors may be used to initialized construction of vectors
57       * by data gathering. We start with zero-length and use either the {@link
58       * #OpenMapRealVector(OpenMapRealVector, int)} constructor
59       * or one of the {@code append} method ({@link #append(double)},
60       * {@link #append(RealVector)}) to gather data into this vector.
61       */
62      public OpenMapRealVector() {
63          this(0, DEFAULT_ZERO_TOLERANCE);
64      }
65  
66      /**
67       * Construct a vector of zeroes.
68       *
69       * @param dimension Size of the vector.
70       */
71      public OpenMapRealVector(int dimension) {
72          this(dimension, DEFAULT_ZERO_TOLERANCE);
73      }
74  
75      /**
76       * Construct a vector of zeroes, specifying zero tolerance.
77       *
78       * @param dimension Size of the vector.
79       * @param epsilon Tolerance below which a value considered zero.
80       */
81      public OpenMapRealVector(int dimension, double epsilon) {
82          virtualSize = dimension;
83          entries = new OpenIntToDoubleHashMap(0.0);
84          this.epsilon = epsilon;
85      }
86  
87      /**
88       * Build a resized vector, for use with append.
89       *
90       * @param v Original vector.
91       * @param resize Amount to add.
92       */
93      protected OpenMapRealVector(OpenMapRealVector v, int resize) {
94          virtualSize = v.getDimension() + resize;
95          entries = new OpenIntToDoubleHashMap(v.entries);
96          epsilon = v.epsilon;
97      }
98  
99      /**
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) && iter.value() > max) {
534                 max = iter.value();
535             }
536         }
537         return max;
538     }
539 
540     /** {@inheritDoc} */
541     @Override
542     public double getLInfDistance(RealVector v)
543         throws DimensionMismatchException {
544         checkVectorDimensions(v.getDimension());
545         if (v instanceof OpenMapRealVector) {
546             return getLInfDistance((OpenMapRealVector) v);
547         } else {
548             return super.getLInfDistance(v);
549         }
550     }
551 
552     /** {@inheritDoc} */
553     @Override
554     public boolean isInfinite() {
555         boolean infiniteFound = false;
556         Iterator iter = entries.iterator();
557         while (iter.hasNext()) {
558             iter.advance();
559             final double value = iter.value();
560             if (Double.isNaN(value)) {
561                 return false;
562             }
563             if (Double.isInfinite(value)) {
564                 infiniteFound = true;
565             }
566         }
567         return infiniteFound;
568     }
569 
570     /** {@inheritDoc} */
571     @Override
572     public boolean isNaN() {
573         Iterator iter = entries.iterator();
574         while (iter.hasNext()) {
575             iter.advance();
576             if (Double.isNaN(iter.value())) {
577                 return true;
578             }
579         }
580         return false;
581     }
582 
583     /** {@inheritDoc} */
584     @Override
585     public OpenMapRealVector mapAdd(double d) {
586         return copy().mapAddToSelf(d);
587     }
588 
589     /** {@inheritDoc} */
590     @Override
591     public OpenMapRealVector mapAddToSelf(double d) {
592         for (int i = 0; i < virtualSize; i++) {
593             setEntry(i, getEntry(i) + d);
594         }
595         return this;
596     }
597 
598     /** {@inheritDoc} */
599     @Override
600     public void setEntry(int index, double value)
601         throws OutOfRangeException {
602         checkIndex(index);
603         if (!isDefaultValue(value)) {
604             entries.put(index, value);
605         } else if (entries.containsKey(index)) {
606             entries.remove(index);
607         }
608     }
609 
610     /** {@inheritDoc} */
611     @Override
612     public void setSubVector(int index, RealVector v)
613         throws OutOfRangeException {
614         checkIndex(index);
615         checkIndex(index + v.getDimension() - 1);
616         for (int i = 0; i < v.getDimension(); i++) {
617             setEntry(i + index, v.getEntry(i));
618         }
619     }
620 
621     /** {@inheritDoc} */
622     @Override
623     public void set(double value) {
624         for (int i = 0; i < virtualSize; i++) {
625             setEntry(i, value);
626         }
627     }
628 
629     /**
630      * Optimized method to subtract OpenMapRealVectors.
631      *
632      * @param v Vector to subtract from {@code this}.
633      * @return the difference of {@code this} and {@code v}.
634      * @throws DimensionMismatchException if the dimensions do not match.
635      */
636     public OpenMapRealVector subtract(OpenMapRealVector v)
637         throws DimensionMismatchException {
638         checkVectorDimensions(v.getDimension());
639         OpenMapRealVector res = copy();
640         Iterator iter = v.getEntries().iterator();
641         while (iter.hasNext()) {
642             iter.advance();
643             int key = iter.key();
644             if (entries.containsKey(key)) {
645                 res.setEntry(key, entries.get(key) - iter.value());
646             } else {
647                 res.setEntry(key, -iter.value());
648             }
649         }
650         return res;
651     }
652 
653     /** {@inheritDoc} */
654     @Override
655     public RealVector subtract(RealVector v)
656         throws DimensionMismatchException {
657         checkVectorDimensions(v.getDimension());
658         if (v instanceof OpenMapRealVector) {
659             return subtract((OpenMapRealVector) v);
660         } else {
661             return super.subtract(v);
662         }
663     }
664 
665     /** {@inheritDoc} */
666     @Override
667     public OpenMapRealVector unitVector() throws MathArithmeticException {
668         OpenMapRealVector res = copy();
669         res.unitize();
670         return res;
671     }
672 
673     /** {@inheritDoc} */
674     @Override
675     public void unitize() throws MathArithmeticException {
676         double norm = getNorm();
677         if (isDefaultValue(norm)) {
678             throw new MathArithmeticException(LocalizedFormats.ZERO_NORM);
679         }
680         Iterator iter = entries.iterator();
681         while (iter.hasNext()) {
682             iter.advance();
683             entries.put(iter.key(), iter.value() / norm);
684         }
685     }
686 
687     /** {@inheritDoc} */
688     @Override
689     public double[] toArray() {
690         double[] res = new double[virtualSize];
691         Iterator iter = entries.iterator();
692         while (iter.hasNext()) {
693             iter.advance();
694             res[iter.key()] = iter.value();
695         }
696         return res;
697     }
698 
699     /**
700      * {@inheritDoc}
701      * Implementation Note: This works on exact values, and as a result
702      * it is possible for {@code a.subtract(b)} to be the zero vector, while
703      * {@code a.hashCode() != b.hashCode()}.
704      */
705     @Override
706     public int hashCode() {
707         final int prime = 31;
708         int result = 1;
709         long temp;
710         temp = Double.doubleToLongBits(epsilon);
711         result = prime * result + (int) (temp ^ (temp >>> 32));
712         result = prime * result + virtualSize;
713         Iterator iter = entries.iterator();
714         while (iter.hasNext()) {
715             iter.advance();
716             temp = Double.doubleToLongBits(iter.value());
717             result = prime * result + (int) (temp ^ (temp >>32));
718         }
719         return result;
720     }
721 
722     /**
723      * {@inheritDoc}
724      * Implementation Note: This performs an exact comparison, and as a result
725      * it is possible for {@code a.subtract(b}} to be the zero vector, while
726      * {@code  a.equals(b) == false}.
727      */
728     @Override
729     public boolean equals(Object obj) {
730         if (this == obj) {
731             return true;
732         }
733         if (!(obj instanceof OpenMapRealVector)) {
734             return false;
735         }
736         OpenMapRealVector other = (OpenMapRealVector) obj;
737         if (virtualSize != other.virtualSize) {
738             return false;
739         }
740         if (Double.doubleToLongBits(epsilon) !=
741             Double.doubleToLongBits(other.epsilon)) {
742             return false;
743         }
744         Iterator iter = entries.iterator();
745         while (iter.hasNext()) {
746             iter.advance();
747             double test = other.getEntry(iter.key());
748             if (Double.doubleToLongBits(test) != Double.doubleToLongBits(iter.value())) {
749                 return false;
750             }
751         }
752         iter = other.getEntries().iterator();
753         while (iter.hasNext()) {
754             iter.advance();
755             double test = iter.value();
756             if (Double.doubleToLongBits(test) != Double.doubleToLongBits(getEntry(iter.key()))) {
757                 return false;
758             }
759         }
760         return true;
761     }
762 
763     /**
764      *
765      * @return the percentage of none zero elements as a decimal percent.
766      * @since 2.2
767      */
768     public double getSparsity() {
769         return (double)entries.size()/(double)getDimension();
770     }
771 
772     /** {@inheritDoc} */
773     @Override
774     public java.util.Iterator<Entry> sparseIterator() {
775         return new OpenMapSparseIterator();
776     }
777 
778     /**
779      * Implementation of {@code Entry} optimized for OpenMap.
780      * This implementation does not allow arbitrary calls to {@code setIndex}
781      * since the order in which entries are returned is undefined.
782      */
783     protected class OpenMapEntry extends Entry {
784         /** Iterator pointing to the entry. */
785         private final Iterator iter;
786 
787         /**
788          * Build an entry from an iterator point to an element.
789          *
790          * @param iter Iterator pointing to the entry.
791          */
792         protected OpenMapEntry(Iterator iter) {
793             this.iter = iter;
794         }
795 
796         /** {@inheritDoc} */
797         @Override
798         public double getValue() {
799             return iter.value();
800         }
801 
802         /** {@inheritDoc} */
803         @Override
804         public void setValue(double value) {
805             entries.put(iter.key(), value);
806         }
807 
808         /** {@inheritDoc} */
809         @Override
810         public int getIndex() {
811             return iter.key();
812         }
813 
814     }
815 
816     /**
817      * Iterator class to do iteration over just the non-zero elements.
818      * This implementation is fail-fast, so cannot be used to modify
819      * any zero element.
820      */
821     protected class OpenMapSparseIterator implements java.util.Iterator<Entry> {
822         /** Underlying iterator. */
823         private final Iterator iter;
824         /** Current entry. */
825         private final Entry current;
826 
827         /** Simple constructor. */
828         protected OpenMapSparseIterator() {
829             iter = entries.iterator();
830             current = new OpenMapEntry(iter);
831         }
832 
833         /** {@inheritDoc} */
834         public boolean hasNext() {
835             return iter.hasNext();
836         }
837 
838         /** {@inheritDoc} */
839         public Entry next() {
840             iter.advance();
841             return current;
842         }
843 
844         /** {@inheritDoc} */
845         public void remove() {
846             throw new UnsupportedOperationException("Not supported");
847         }
848     }
849 }