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