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