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
9
* http://www.apache.org/licenses/LICENSE-2.0
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.
17
package org.apache.commons.math.linear;
19
import java.io.Serializable;
20
import java.lang.reflect.Array;
22
import org.apache.commons.math.Field;
23
import org.apache.commons.math.FieldElement;
24
import org.apache.commons.math.MathRuntimeException;
25
import org.apache.commons.math.util.OpenIntToFieldHashMap;
28
* This class implements the {@link FieldVector} interface with a {@link OpenIntToFieldHashMap} backing store.
29
* @param <T> the type of the field elements
30
* @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
33
public class SparseFieldVector<T extends FieldElement<T>> implements FieldVector<T>, Serializable {
38
private static final long serialVersionUID = 7841233292190413362L;
39
/** Field to which the elements belong. */
40
private final Field<T> field;
41
/** Entries of the vector. */
42
private final OpenIntToFieldHashMap<T> entries;
43
/** Dimension of the vector. */
44
private final int virtualSize;
47
* Build a 0-length vector.
48
* <p>Zero-length vectors may be used to initialize construction of vectors
49
* by data gathering. We start with zero-length and use either the {@link
50
* #SparseFieldVector(SparseFieldVector, int)} constructor
51
* or one of the <code>append</code> method ({@link #append(FieldElement)},
52
* {@link #append(FieldElement[])}, {@link #append(FieldVector)},
53
* {@link #append(SparseFieldVector)}) to gather data into this vector.</p>
54
* @param field field to which the elements belong
56
public SparseFieldVector(Field<T> field) {
62
* Construct a (dimension)-length vector of zeros.
63
* @param field field to which the elements belong
64
* @param dimension Size of the vector
66
public SparseFieldVector(Field<T> field, int dimension) {
68
virtualSize = dimension;
69
entries = new OpenIntToFieldHashMap<T>(field);
73
* Build a resized vector, for use with append.
74
* @param v The original vector
75
* @param resize The amount to resize it
77
protected SparseFieldVector(SparseFieldVector<T> v, int resize) {
79
virtualSize = v.getDimension() + resize;
80
entries = new OpenIntToFieldHashMap<T>(v.entries);
85
* Build a vector with known the sparseness (for advanced use only).
86
* @param field field to which the elements belong
87
* @param dimension The size of the vector
88
* @param expectedSize The expected number of non-zero entries
90
public SparseFieldVector(Field<T> field, int dimension, int expectedSize) {
92
virtualSize = dimension;
93
entries = new OpenIntToFieldHashMap<T>(field,expectedSize);
97
* Create from a Field array.
98
* Only non-zero entries will be stored
99
* @param field field to which the elements belong
100
* @param values The set of values to create from
102
public SparseFieldVector(Field<T> field, T[] values) {
104
virtualSize = values.length;
105
entries = new OpenIntToFieldHashMap<T>(field);
106
for (int key = 0; key < values.length; key++) {
107
T value = values[key];
108
entries.put(key, value);
116
* @param v The instance to copy from
118
public SparseFieldVector(SparseFieldVector<T> v) {
120
virtualSize = v.getDimension();
121
entries = new OpenIntToFieldHashMap<T>(v.getEntries());
125
* Get the entries of this instance.
126
* @return entries of this instance
128
private OpenIntToFieldHashMap<T> getEntries() {
133
* Optimized method to add sparse vectors.
134
* @param v vector to add
135
* @return The sum of <code>this</code> and <code>v</code>
136
* @throws IllegalArgumentException If the dimensions don't match
138
public FieldVector<T> add(SparseFieldVector<T> v) throws IllegalArgumentException {
139
checkVectorDimensions(v.getDimension());
140
SparseFieldVector<T> res = (SparseFieldVector<T>)copy();
141
OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator();
142
while (iter.hasNext()) {
144
int key = iter.key();
145
T value = iter.value();
146
if (entries.containsKey(key)) {
147
res.setEntry(key, entries.get(key).add(value));
149
res.setEntry(key, value);
158
public FieldVector<T> add(T[] v) throws IllegalArgumentException {
159
checkVectorDimensions(v.length);
160
SparseFieldVector<T> res = new SparseFieldVector<T>(field,getDimension());
161
for (int i = 0; i < v.length; i++) {
162
res.setEntry(i, v[i].add(getEntry(i)));
168
* Construct a vector by appending a vector to this vector.
169
* @param v vector to append to this one.
170
* @return a new vector
172
public FieldVector<T> append(SparseFieldVector<T> v) {
173
SparseFieldVector<T> res = new SparseFieldVector<T>(this, v.getDimension());
174
OpenIntToFieldHashMap<T>.Iterator iter = v.entries.iterator();
175
while (iter.hasNext()) {
177
res.setEntry(iter.key() + virtualSize, iter.value());
183
public FieldVector<T> append(FieldVector<T> v) {
184
if (v instanceof SparseFieldVector<?>) {
185
return append((SparseFieldVector<T>) v);
187
return append(v.toArray());
192
public FieldVector<T> append(T d) {
193
FieldVector<T> res = new SparseFieldVector<T>(this, 1);
194
res.setEntry(virtualSize, d);
199
public FieldVector<T> append(T[] a) {
200
FieldVector<T> res = new SparseFieldVector<T>(this, a.length);
201
for (int i = 0; i < a.length; i++) {
202
res.setEntry(i + virtualSize, a[i]);
208
public FieldVector<T> copy() {
209
return new SparseFieldVector<T>(this);
213
public T dotProduct(FieldVector<T> v) throws IllegalArgumentException {
214
checkVectorDimensions(v.getDimension());
215
T res = field.getZero();
216
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
217
while (iter.hasNext()) {
219
res = res.add(v.getEntry(iter.key()).multiply(iter.value()));
225
public T dotProduct(T[] v) throws IllegalArgumentException {
226
checkVectorDimensions(v.length);
227
T res = field.getZero();
228
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
229
while (iter.hasNext()) {
230
int idx = iter.key();
231
T value = field.getZero();
232
if (idx < v.length) {
235
res = res.add(value.multiply(iter.value()));
241
public FieldVector<T> ebeDivide(FieldVector<T> v)
242
throws IllegalArgumentException {
243
checkVectorDimensions(v.getDimension());
244
SparseFieldVector<T> res = new SparseFieldVector<T>(this);
245
OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
246
while (iter.hasNext()) {
248
res.setEntry(iter.key(), iter.value().divide(v.getEntry(iter.key())));
254
public FieldVector<T> ebeDivide(T[] v) throws IllegalArgumentException {
255
checkVectorDimensions(v.length);
256
SparseFieldVector<T> res = new SparseFieldVector<T>(this);
257
OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
258
while (iter.hasNext()) {
260
res.setEntry(iter.key(), iter.value().divide(v[iter.key()]));
266
public FieldVector<T> ebeMultiply(FieldVector<T> v)throws IllegalArgumentException {
267
checkVectorDimensions(v.getDimension());
268
SparseFieldVector<T> res = new SparseFieldVector<T>(this);
269
OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
270
while (iter.hasNext()) {
272
res.setEntry(iter.key(), iter.value().multiply(v.getEntry(iter.key())));
278
public FieldVector<T> ebeMultiply(T[] v) throws IllegalArgumentException {
279
checkVectorDimensions(v.length);
280
SparseFieldVector<T> res = new SparseFieldVector<T>(this);
281
OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
282
while (iter.hasNext()) {
284
res.setEntry(iter.key(), iter.value().multiply(v[iter.key()]));
290
public T[] getData() {
291
T[] res = buildArray(virtualSize);
292
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
293
while (iter.hasNext()) {
295
res[iter.key()] = iter.value();
301
public int getDimension() {
306
public T getEntry(int index) throws MatrixIndexException {
308
return entries.get(index);
312
public Field<T> getField() {
317
public FieldVector<T> getSubVector(int index, int n)
318
throws MatrixIndexException {
320
checkIndex(index + n - 1);
321
SparseFieldVector<T> res = new SparseFieldVector<T>(field,n);
323
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
324
while (iter.hasNext()) {
326
int key = iter.key();
327
if (key >= index && key < end) {
328
res.setEntry(key - index, iter.value());
335
public FieldVector<T> mapAdd(T d) {
336
return copy().mapAddToSelf(d);
340
public FieldVector<T> mapAddToSelf(T d) {
341
for (int i = 0; i < virtualSize; i++) {
342
setEntry(i, getEntry(i).add(d));
348
public FieldVector<T> mapDivide(T d) {
349
return copy().mapDivideToSelf(d);
353
public FieldVector<T> mapDivideToSelf(T d) {
354
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
355
while (iter.hasNext()) {
357
entries.put(iter.key(), iter.value().divide(d));
363
public FieldVector<T> mapInv() {
364
return copy().mapInvToSelf();
368
public FieldVector<T> mapInvToSelf() {
369
for (int i = 0; i < virtualSize; i++) {
370
setEntry(i, field.getOne().divide(getEntry(i)));
376
public FieldVector<T> mapMultiply(T d) {
377
return copy().mapMultiplyToSelf(d);
381
public FieldVector<T> mapMultiplyToSelf(T d) {
382
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
383
while (iter.hasNext()) {
385
entries.put(iter.key(), iter.value().multiply(d));
391
public FieldVector<T> mapSubtract(T d) {
392
return copy().mapSubtractToSelf(d);
396
public FieldVector<T> mapSubtractToSelf(T d) {
397
return mapAddToSelf(field.getZero().subtract(d));
401
* Optimized method to compute outer product when both vectors are sparse.
402
* @param v vector with which outer product should be computed
403
* @return the square matrix outer product between instance and v
404
* @throws IllegalArgumentException if v is not the same size as {@code this}
406
public FieldMatrix<T> outerProduct(SparseFieldVector<T> v)
407
throws IllegalArgumentException {
408
checkVectorDimensions(v.getDimension());
409
SparseFieldMatrix<T> res = new SparseFieldMatrix<T>(field, virtualSize, virtualSize);
410
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
411
while (iter.hasNext()) {
413
OpenIntToFieldHashMap<T>.Iterator iter2 = v.entries.iterator();
414
while (iter2.hasNext()) {
416
res.setEntry(iter.key(), iter2.key(), iter.value().multiply(iter2.value()));
423
public FieldMatrix<T> outerProduct(T[] v) throws IllegalArgumentException {
424
checkVectorDimensions(v.length);
425
FieldMatrix<T> res = new SparseFieldMatrix<T>(field, virtualSize, virtualSize);
426
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
427
while (iter.hasNext()) {
429
int row = iter.key();
430
FieldElement<T>value = iter.value();
431
for (int col = 0; col < virtualSize; col++) {
432
res.setEntry(row, col, value.multiply(v[col]));
439
public FieldMatrix<T> outerProduct(FieldVector<T> v)
440
throws IllegalArgumentException {
441
if(v instanceof SparseFieldVector<?>)
442
return outerProduct((SparseFieldVector<T>)v);
444
return outerProduct(v.toArray());
448
public FieldVector<T> projection(FieldVector<T> v)
449
throws IllegalArgumentException {
450
checkVectorDimensions(v.getDimension());
451
return v.mapMultiply(dotProduct(v).divide(v.dotProduct(v)));
455
public FieldVector<T> projection(T[] v) throws IllegalArgumentException {
456
checkVectorDimensions(v.length);
457
return projection(new SparseFieldVector<T>(field,v));
461
public void set(T value) {
462
for (int i = 0; i < virtualSize; i++) {
468
public void setEntry(int index, T value) throws MatrixIndexException {
470
entries.put(index, value);
474
public void setSubVector(int index, FieldVector<T> v)
475
throws MatrixIndexException {
477
checkIndex(index + v.getDimension() - 1);
478
setSubVector(index, v.getData());
482
public void setSubVector(int index, T[] v) throws MatrixIndexException {
484
checkIndex(index + v.length - 1);
485
for (int i = 0; i < v.length; i++) {
486
setEntry(i + index, v[i]);
492
* Optimized method to subtract SparseRealVectors.
493
* @param v The vector to subtract from <code>this</code>
494
* @return The difference of <code>this</code> and <code>v</code>
495
* @throws IllegalArgumentException If the dimensions don't match
497
public SparseFieldVector<T> subtract(SparseFieldVector<T> v) throws IllegalArgumentException{
498
checkVectorDimensions(v.getDimension());
499
SparseFieldVector<T> res = (SparseFieldVector<T>)copy();
500
OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator();
501
while (iter.hasNext()) {
503
int key = iter.key();
504
if (entries.containsKey(key)) {
505
res.setEntry(key, entries.get(key).subtract(iter.value()));
507
res.setEntry(key, field.getZero().subtract(iter.value()));
514
public FieldVector<T> subtract(FieldVector<T> v)
515
throws IllegalArgumentException {
516
if(v instanceof SparseFieldVector<?>)
517
return subtract((SparseFieldVector<T>)v);
519
return subtract(v.toArray());
523
public FieldVector<T> subtract(T[] v) throws IllegalArgumentException {
524
checkVectorDimensions(v.length);
525
SparseFieldVector<T> res = new SparseFieldVector<T>(this);
526
for (int i = 0; i < v.length; i++) {
527
if (entries.containsKey(i)) {
528
res.setEntry(i, entries.get(i).subtract(v[i]));
530
res.setEntry(i, field.getZero().subtract(v[i]));
537
public T[] toArray() {
542
* Check if an index is valid.
546
* @exception MatrixIndexException
547
* if index is not valid
549
private void checkIndex(final int index) throws MatrixIndexException {
550
if (index < 0 || index >= getDimension()) {
551
throw new MatrixIndexException(
552
"index {0} out of allowed range [{1}, {2}]",
553
index, 0, getDimension() - 1);
558
* Check if instance dimension is equal to some expected value.
561
* expected dimension.
562
* @exception IllegalArgumentException
563
* if the dimension is inconsistent with vector size
565
protected void checkVectorDimensions(int n) throws IllegalArgumentException {
566
if (getDimension() != n) {
567
throw MathRuntimeException.createIllegalArgumentException(
568
"vector length mismatch: got {0} but expected {1}",
575
public FieldVector<T> add(FieldVector<T> v) throws IllegalArgumentException {
576
if (v instanceof SparseFieldVector<?>) {
577
return add((SparseFieldVector<T>)v);
579
return add(v.toArray());
583
/** Build an array of elements.
584
* @param length size of the array to build
585
* @return a new array
587
@SuppressWarnings("unchecked")
588
private T[] buildArray(final int length) {
589
return (T[]) Array.newInstance(field.getZero().getClass(), length);
595
public int hashCode() {
596
final int prime = 31;
598
result = prime * result + ((field == null) ? 0 : field.hashCode());
599
result = prime * result + virtualSize;
600
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
601
while (iter.hasNext()) {
603
int temp = iter.value().hashCode();
604
result = prime * result + temp;
611
@SuppressWarnings("unchecked")
613
public boolean equals(Object obj) {
623
if (!(obj instanceof SparseFieldVector)) {
627
SparseFieldVector<T> other = (SparseFieldVector<T>) obj;
629
if (other.field != null) {
632
} else if (!field.equals(other.field)) {
635
if (virtualSize != other.virtualSize) {
639
OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
640
while (iter.hasNext()) {
642
T test = other.getEntry(iter.key());
643
if (!test.equals(iter.value())) {
647
iter = other.getEntries().iterator();
648
while (iter.hasNext()) {
650
T test = iter.value();
651
if (!test.equals(getEntry(iter.key()))) {