001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math3.linear;
018
019 import java.io.Serializable;
020 import java.lang.reflect.Array;
021
022 import org.apache.commons.math3.Field;
023 import org.apache.commons.math3.FieldElement;
024 import org.apache.commons.math3.exception.MathArithmeticException;
025 import org.apache.commons.math3.exception.NotPositiveException;
026 import org.apache.commons.math3.exception.NullArgumentException;
027 import org.apache.commons.math3.exception.OutOfRangeException;
028 import org.apache.commons.math3.exception.DimensionMismatchException;
029 import org.apache.commons.math3.exception.util.LocalizedFormats;
030 import org.apache.commons.math3.util.OpenIntToFieldHashMap;
031
032 /**
033 * This class implements the {@link FieldVector} interface with a {@link OpenIntToFieldHashMap} backing store.
034 * @param <T> the type of the field elements
035 * @version $Id: SparseFieldVector.java 1416643 2012-12-03 19:37:14Z tn $
036 * @since 2.0
037 * @deprecated As of version 3.1, this class is deprecated, for reasons exposed
038 * in this JIRA
039 * <a href="https://issues.apache.org/jira/browse/MATH-870">ticket</a>. This
040 * class will be removed in version 4.0.
041 */
042 @Deprecated
043 public class SparseFieldVector<T extends FieldElement<T>> implements FieldVector<T>, Serializable {
044 /** Serialization identifier. */
045 private static final long serialVersionUID = 7841233292190413362L;
046 /** Field to which the elements belong. */
047 private final Field<T> field;
048 /** Entries of the vector. */
049 private final OpenIntToFieldHashMap<T> entries;
050 /** Dimension of the vector. */
051 private final int virtualSize;
052
053 /**
054 * Build a 0-length vector.
055 * Zero-length vectors may be used to initialize construction of vectors
056 * by data gathering. We start with zero-length and use either the {@link
057 * #SparseFieldVector(SparseFieldVector, int)} constructor
058 * or one of the {@code append} method ({@link #append(FieldVector)} or
059 * {@link #append(SparseFieldVector)}) to gather data into this vector.
060 *
061 * @param field Field to which the elements belong.
062 */
063 public SparseFieldVector(Field<T> field) {
064 this(field, 0);
065 }
066
067
068 /**
069 * Construct a vector of zeroes.
070 *
071 * @param field Field to which the elements belong.
072 * @param dimension Size of the vector.
073 */
074 public SparseFieldVector(Field<T> field, int dimension) {
075 this.field = field;
076 virtualSize = dimension;
077 entries = new OpenIntToFieldHashMap<T>(field);
078 }
079
080 /**
081 * Build a resized vector, for use with append.
082 *
083 * @param v Original vector
084 * @param resize Amount to add.
085 */
086 protected SparseFieldVector(SparseFieldVector<T> v, int resize) {
087 field = v.field;
088 virtualSize = v.getDimension() + resize;
089 entries = new OpenIntToFieldHashMap<T>(v.entries);
090 }
091
092
093 /**
094 * Build a vector with known the sparseness (for advanced use only).
095 *
096 * @param field Field to which the elements belong.
097 * @param dimension Size of the vector.
098 * @param expectedSize Expected number of non-zero entries.
099 */
100 public SparseFieldVector(Field<T> field, int dimension, int expectedSize) {
101 this.field = field;
102 virtualSize = dimension;
103 entries = new OpenIntToFieldHashMap<T>(field,expectedSize);
104 }
105
106 /**
107 * Create from a Field array.
108 * Only non-zero entries will be stored.
109 *
110 * @param field Field to which the elements belong.
111 * @param values Set of values to create from.
112 */
113 public SparseFieldVector(Field<T> field, T[] values) {
114 this.field = field;
115 virtualSize = values.length;
116 entries = new OpenIntToFieldHashMap<T>(field);
117 for (int key = 0; key < values.length; key++) {
118 T value = values[key];
119 entries.put(key, value);
120 }
121 }
122
123 /**
124 * Copy constructor.
125 *
126 * @param v Instance to copy.
127 */
128 public SparseFieldVector(SparseFieldVector<T> v) {
129 field = v.field;
130 virtualSize = v.getDimension();
131 entries = new OpenIntToFieldHashMap<T>(v.getEntries());
132 }
133
134 /**
135 * Get the entries of this instance.
136 *
137 * @return the entries of this instance
138 */
139 private OpenIntToFieldHashMap<T> getEntries() {
140 return entries;
141 }
142
143 /**
144 * Optimized method to add sparse vectors.
145 *
146 * @param v Vector to add.
147 * @return {@code this + v}.
148 * @throws DimensionMismatchException if {@code v} is not the same size as
149 * {@code this}.
150 */
151 public FieldVector<T> add(SparseFieldVector<T> v)
152 throws DimensionMismatchException {
153 checkVectorDimensions(v.getDimension());
154 SparseFieldVector<T> res = (SparseFieldVector<T>)copy();
155 OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator();
156 while (iter.hasNext()) {
157 iter.advance();
158 int key = iter.key();
159 T value = iter.value();
160 if (entries.containsKey(key)) {
161 res.setEntry(key, entries.get(key).add(value));
162 } else {
163 res.setEntry(key, value);
164 }
165 }
166 return res;
167
168 }
169
170 /**
171 * Construct a vector by appending a vector to this vector.
172 *
173 * @param v Vector to append to this one.
174 * @return a new vector.
175 */
176 public FieldVector<T> append(SparseFieldVector<T> v) {
177 SparseFieldVector<T> res = new SparseFieldVector<T>(this, v.getDimension());
178 OpenIntToFieldHashMap<T>.Iterator iter = v.entries.iterator();
179 while (iter.hasNext()) {
180 iter.advance();
181 res.setEntry(iter.key() + virtualSize, iter.value());
182 }
183 return res;
184 }
185
186 /** {@inheritDoc} */
187 public FieldVector<T> append(FieldVector<T> v) {
188 if (v instanceof SparseFieldVector<?>) {
189 return append((SparseFieldVector<T>) v);
190 } else {
191 final int n = v.getDimension();
192 FieldVector<T> res = new SparseFieldVector<T>(this, n);
193 for (int i = 0; i < n; i++) {
194 res.setEntry(i + virtualSize, v.getEntry(i));
195 }
196 return res;
197 }
198 }
199
200 /** {@inheritDoc} */
201 public FieldVector<T> append(T d) {
202 FieldVector<T> res = new SparseFieldVector<T>(this, 1);
203 res.setEntry(virtualSize, d);
204 return res;
205 }
206
207 /** {@inheritDoc} */
208 public FieldVector<T> copy() {
209 return new SparseFieldVector<T>(this);
210 }
211
212 /** {@inheritDoc} */
213 public T dotProduct(FieldVector<T> v) throws DimensionMismatchException {
214 checkVectorDimensions(v.getDimension());
215 T res = field.getZero();
216 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
217 while (iter.hasNext()) {
218 iter.advance();
219 res = res.add(v.getEntry(iter.key()).multiply(iter.value()));
220 }
221 return res;
222 }
223
224 /** {@inheritDoc} */
225 public FieldVector<T> ebeDivide(FieldVector<T> v)
226 throws DimensionMismatchException, MathArithmeticException {
227 checkVectorDimensions(v.getDimension());
228 SparseFieldVector<T> res = new SparseFieldVector<T>(this);
229 OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
230 while (iter.hasNext()) {
231 iter.advance();
232 res.setEntry(iter.key(), iter.value().divide(v.getEntry(iter.key())));
233 }
234 return res;
235 }
236
237 /** {@inheritDoc} */
238 public FieldVector<T> ebeMultiply(FieldVector<T> v)
239 throws DimensionMismatchException {
240 checkVectorDimensions(v.getDimension());
241 SparseFieldVector<T> res = new SparseFieldVector<T>(this);
242 OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
243 while (iter.hasNext()) {
244 iter.advance();
245 res.setEntry(iter.key(), iter.value().multiply(v.getEntry(iter.key())));
246 }
247 return res;
248 }
249
250 /**
251 * {@inheritDoc}
252 *
253 * @deprecated as of 3.1, to be removed in 4.0. Please use the {@link #toArray()} method instead.
254 */
255 @Deprecated
256 public T[] getData() {
257 return toArray();
258 }
259
260 /** {@inheritDoc} */
261 public int getDimension() {
262 return virtualSize;
263 }
264
265 /** {@inheritDoc} */
266 public T getEntry(int index) throws OutOfRangeException {
267 checkIndex(index);
268 return entries.get(index);
269 }
270
271 /** {@inheritDoc} */
272 public Field<T> getField() {
273 return field;
274 }
275
276 /** {@inheritDoc} */
277 public FieldVector<T> getSubVector(int index, int n)
278 throws OutOfRangeException, NotPositiveException {
279 if (n < 0) {
280 throw new NotPositiveException(LocalizedFormats.NUMBER_OF_ELEMENTS_SHOULD_BE_POSITIVE, n);
281 }
282 checkIndex(index);
283 checkIndex(index + n - 1);
284 SparseFieldVector<T> res = new SparseFieldVector<T>(field,n);
285 int end = index + n;
286 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
287 while (iter.hasNext()) {
288 iter.advance();
289 int key = iter.key();
290 if (key >= index && key < end) {
291 res.setEntry(key - index, iter.value());
292 }
293 }
294 return res;
295 }
296
297 /** {@inheritDoc} */
298 public FieldVector<T> mapAdd(T d) throws NullArgumentException {
299 return copy().mapAddToSelf(d);
300 }
301
302 /** {@inheritDoc} */
303 public FieldVector<T> mapAddToSelf(T d) throws NullArgumentException {
304 for (int i = 0; i < virtualSize; i++) {
305 setEntry(i, getEntry(i).add(d));
306 }
307 return this;
308 }
309
310 /** {@inheritDoc} */
311 public FieldVector<T> mapDivide(T d)
312 throws NullArgumentException, MathArithmeticException {
313 return copy().mapDivideToSelf(d);
314 }
315
316 /** {@inheritDoc} */
317 public FieldVector<T> mapDivideToSelf(T d)
318 throws NullArgumentException, MathArithmeticException {
319 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
320 while (iter.hasNext()) {
321 iter.advance();
322 entries.put(iter.key(), iter.value().divide(d));
323 }
324 return this;
325 }
326
327 /** {@inheritDoc} */
328 public FieldVector<T> mapInv() throws MathArithmeticException {
329 return copy().mapInvToSelf();
330 }
331
332 /** {@inheritDoc} */
333 public FieldVector<T> mapInvToSelf() throws MathArithmeticException {
334 for (int i = 0; i < virtualSize; i++) {
335 setEntry(i, field.getOne().divide(getEntry(i)));
336 }
337 return this;
338 }
339
340 /** {@inheritDoc} */
341 public FieldVector<T> mapMultiply(T d) throws NullArgumentException {
342 return copy().mapMultiplyToSelf(d);
343 }
344
345 /** {@inheritDoc} */
346 public FieldVector<T> mapMultiplyToSelf(T d) throws NullArgumentException {
347 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
348 while (iter.hasNext()) {
349 iter.advance();
350 entries.put(iter.key(), iter.value().multiply(d));
351 }
352 return this;
353 }
354
355 /** {@inheritDoc} */
356 public FieldVector<T> mapSubtract(T d) throws NullArgumentException {
357 return copy().mapSubtractToSelf(d);
358 }
359
360 /** {@inheritDoc} */
361 public FieldVector<T> mapSubtractToSelf(T d) throws NullArgumentException {
362 return mapAddToSelf(field.getZero().subtract(d));
363 }
364
365 /**
366 * Optimized method to compute outer product when both vectors are sparse.
367 * @param v vector with which outer product should be computed
368 * @return the matrix outer product between instance and v
369 */
370 public FieldMatrix<T> outerProduct(SparseFieldVector<T> v) {
371 final int n = v.getDimension();
372 SparseFieldMatrix<T> res = new SparseFieldMatrix<T>(field, virtualSize, n);
373 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
374 while (iter.hasNext()) {
375 iter.advance();
376 OpenIntToFieldHashMap<T>.Iterator iter2 = v.entries.iterator();
377 while (iter2.hasNext()) {
378 iter2.advance();
379 res.setEntry(iter.key(), iter2.key(), iter.value().multiply(iter2.value()));
380 }
381 }
382 return res;
383 }
384
385 /** {@inheritDoc} */
386 public FieldMatrix<T> outerProduct(FieldVector<T> v) {
387 if (v instanceof SparseFieldVector<?>) {
388 return outerProduct((SparseFieldVector<T>)v);
389 } else {
390 final int n = v.getDimension();
391 FieldMatrix<T> res = new SparseFieldMatrix<T>(field, virtualSize, n);
392 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
393 while (iter.hasNext()) {
394 iter.advance();
395 int row = iter.key();
396 FieldElement<T>value = iter.value();
397 for (int col = 0; col < n; col++) {
398 res.setEntry(row, col, value.multiply(v.getEntry(col)));
399 }
400 }
401 return res;
402 }
403 }
404
405 /** {@inheritDoc} */
406 public FieldVector<T> projection(FieldVector<T> v)
407 throws DimensionMismatchException, MathArithmeticException {
408 checkVectorDimensions(v.getDimension());
409 return v.mapMultiply(dotProduct(v).divide(v.dotProduct(v)));
410 }
411
412 /** {@inheritDoc} */
413 public void set(T value) {
414 for (int i = 0; i < virtualSize; i++) {
415 setEntry(i, value);
416 }
417 }
418
419 /** {@inheritDoc} */
420 public void setEntry(int index, T value) throws OutOfRangeException {
421 checkIndex(index);
422 entries.put(index, value);
423 }
424
425 /** {@inheritDoc} */
426 public void setSubVector(int index, FieldVector<T> v)
427 throws OutOfRangeException {
428 checkIndex(index);
429 checkIndex(index + v.getDimension() - 1);
430 final int n = v.getDimension();
431 for (int i = 0; i < n; i++) {
432 setEntry(i + index, v.getEntry(i));
433 }
434 }
435
436 /**
437 * Optimized method to compute {@code this} minus {@code v}.
438 * @param v vector to be subtracted
439 * @return {@code this - v}
440 * @throws DimensionMismatchException if {@code v} is not the same size as
441 * {@code this}.
442 */
443 public SparseFieldVector<T> subtract(SparseFieldVector<T> v)
444 throws DimensionMismatchException {
445 checkVectorDimensions(v.getDimension());
446 SparseFieldVector<T> res = (SparseFieldVector<T>)copy();
447 OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator();
448 while (iter.hasNext()) {
449 iter.advance();
450 int key = iter.key();
451 if (entries.containsKey(key)) {
452 res.setEntry(key, entries.get(key).subtract(iter.value()));
453 } else {
454 res.setEntry(key, field.getZero().subtract(iter.value()));
455 }
456 }
457 return res;
458 }
459
460 /** {@inheritDoc} */
461 public FieldVector<T> subtract(FieldVector<T> v)
462 throws DimensionMismatchException {
463 if (v instanceof SparseFieldVector<?>) {
464 return subtract((SparseFieldVector<T>)v);
465 } else {
466 final int n = v.getDimension();
467 checkVectorDimensions(n);
468 SparseFieldVector<T> res = new SparseFieldVector<T>(this);
469 for (int i = 0; i < n; i++) {
470 if (entries.containsKey(i)) {
471 res.setEntry(i, entries.get(i).subtract(v.getEntry(i)));
472 } else {
473 res.setEntry(i, field.getZero().subtract(v.getEntry(i)));
474 }
475 }
476 return res;
477 }
478 }
479
480 /** {@inheritDoc} */
481 public T[] toArray() {
482 T[] res = buildArray(virtualSize);
483 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
484 while (iter.hasNext()) {
485 iter.advance();
486 res[iter.key()] = iter.value();
487 }
488 return res;
489 }
490
491 /**
492 * Check whether an index is valid.
493 *
494 * @param index Index to check.
495 * @throws OutOfRangeException if the index is not valid.
496 */
497 private void checkIndex(final int index) throws OutOfRangeException {
498 if (index < 0 || index >= getDimension()) {
499 throw new OutOfRangeException(index, 0, getDimension() - 1);
500 }
501 }
502
503 /**
504 * Check if instance dimension is equal to some expected value.
505 *
506 * @param n Expected dimension.
507 * @throws DimensionMismatchException if the dimensions do not match.
508 */
509 protected void checkVectorDimensions(int n)
510 throws DimensionMismatchException {
511 if (getDimension() != n) {
512 throw new DimensionMismatchException(getDimension(), n);
513 }
514 }
515
516 /** {@inheritDoc} */
517 public FieldVector<T> add(FieldVector<T> v) throws DimensionMismatchException {
518 if (v instanceof SparseFieldVector<?>) {
519 return add((SparseFieldVector<T>) v);
520 } else {
521 final int n = v.getDimension();
522 checkVectorDimensions(n);
523 SparseFieldVector<T> res = new SparseFieldVector<T>(field,
524 getDimension());
525 for (int i = 0; i < n; i++) {
526 res.setEntry(i, v.getEntry(i).add(getEntry(i)));
527 }
528 return res;
529 }
530 }
531
532 /**
533 * Build an array of elements.
534 *
535 * @param length Size of the array to build.
536 * @return a new array.
537 */
538 @SuppressWarnings("unchecked") // field is type T
539 private T[] buildArray(final int length) {
540 return (T[]) Array.newInstance(field.getRuntimeClass(), length);
541 }
542
543
544 /** {@inheritDoc} */
545 @Override
546 public int hashCode() {
547 final int prime = 31;
548 int result = 1;
549 result = prime * result + ((field == null) ? 0 : field.hashCode());
550 result = prime * result + virtualSize;
551 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
552 while (iter.hasNext()) {
553 iter.advance();
554 int temp = iter.value().hashCode();
555 result = prime * result + temp;
556 }
557 return result;
558 }
559
560
561 /** {@inheritDoc} */
562 @Override
563 public boolean equals(Object obj) {
564
565 if (this == obj) {
566 return true;
567 }
568
569 if (!(obj instanceof SparseFieldVector<?>)) {
570 return false;
571 }
572
573 @SuppressWarnings("unchecked") // OK, because "else if" check below ensures that
574 // other must be the same type as this
575 SparseFieldVector<T> other = (SparseFieldVector<T>) obj;
576 if (field == null) {
577 if (other.field != null) {
578 return false;
579 }
580 } else if (!field.equals(other.field)) {
581 return false;
582 }
583 if (virtualSize != other.virtualSize) {
584 return false;
585 }
586
587 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
588 while (iter.hasNext()) {
589 iter.advance();
590 T test = other.getEntry(iter.key());
591 if (!test.equals(iter.value())) {
592 return false;
593 }
594 }
595 iter = other.getEntries().iterator();
596 while (iter.hasNext()) {
597 iter.advance();
598 T test = iter.value();
599 if (!test.equals(getEntry(iter.key()))) {
600 return false;
601 }
602 }
603 return true;
604 }
605 }