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.math.linear; 18 19 import java.io.Serializable; 20 import java.lang.reflect.Array; 21 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.exception.util.LocalizedFormats; 26 import org.apache.commons.math.util.OpenIntToFieldHashMap; 27 28 /** 29 * This class implements the {@link FieldVector} interface with a {@link OpenIntToFieldHashMap} backing store. 30 * @param <T> the type of the field elements 31 * @version $Revision: 983921 $ $Date: 2010-08-10 12:46:06 +0200 (mar. 10 aot 2010) $ 32 * @since 2.0 33 */ 34 public class SparseFieldVector<T extends FieldElement<T>> implements FieldVector<T>, Serializable { 35 36 /** 37 * Serial version id 38 */ 39 private static final long serialVersionUID = 7841233292190413362L; 40 /** Field to which the elements belong. */ 41 private final Field<T> field; 42 /** Entries of the vector. */ 43 private final OpenIntToFieldHashMap<T> entries; 44 /** Dimension of the vector. */ 45 private final int virtualSize; 46 47 /** 48 * Build a 0-length vector. 49 * <p>Zero-length vectors may be used to initialize construction of vectors 50 * by data gathering. We start with zero-length and use either the {@link 51 * #SparseFieldVector(SparseFieldVector, int)} constructor 52 * or one of the <code>append</code> method ({@link #append(FieldElement)}, 53 * {@link #append(FieldElement[])}, {@link #append(FieldVector)}, 54 * {@link #append(SparseFieldVector)}) to gather data into this vector.</p> 55 * @param field field to which the elements belong 56 */ 57 public SparseFieldVector(Field<T> field) { 58 this(field, 0); 59 } 60 61 62 /** 63 * Construct a (dimension)-length vector of zeros. 64 * @param field field to which the elements belong 65 * @param dimension Size of the vector 66 */ 67 public SparseFieldVector(Field<T> field, int dimension) { 68 this.field = field; 69 virtualSize = dimension; 70 entries = new OpenIntToFieldHashMap<T>(field); 71 } 72 73 /** 74 * Build a resized vector, for use with append. 75 * @param v The original vector 76 * @param resize The amount to resize it 77 */ 78 protected SparseFieldVector(SparseFieldVector<T> v, int resize) { 79 field = v.field; 80 virtualSize = v.getDimension() + resize; 81 entries = new OpenIntToFieldHashMap<T>(v.entries); 82 } 83 84 85 /** 86 * Build a vector with known the sparseness (for advanced use only). 87 * @param field field to which the elements belong 88 * @param dimension The size of the vector 89 * @param expectedSize The expected number of non-zero entries 90 */ 91 public SparseFieldVector(Field<T> field, int dimension, int expectedSize) { 92 this.field = field; 93 virtualSize = dimension; 94 entries = new OpenIntToFieldHashMap<T>(field,expectedSize); 95 } 96 97 /** 98 * Create from a Field array. 99 * Only non-zero entries will be stored 100 * @param field field to which the elements belong 101 * @param values The set of values to create from 102 */ 103 public SparseFieldVector(Field<T> field, T[] values) { 104 this.field = field; 105 virtualSize = values.length; 106 entries = new OpenIntToFieldHashMap<T>(field); 107 for (int key = 0; key < values.length; key++) { 108 T value = values[key]; 109 entries.put(key, value); 110 } 111 } 112 113 114 115 /** 116 * Copy constructor. 117 * @param v The instance to copy from 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 * @return entries of this instance 128 */ 129 private OpenIntToFieldHashMap<T> getEntries() { 130 return entries; 131 } 132 133 /** 134 * Optimized method to add sparse vectors. 135 * @param v vector to add 136 * @return The sum of <code>this</code> and <code>v</code> 137 * @throws IllegalArgumentException If the dimensions don't match 138 */ 139 public FieldVector<T> add(SparseFieldVector<T> v) throws IllegalArgumentException { 140 checkVectorDimensions(v.getDimension()); 141 SparseFieldVector<T> res = (SparseFieldVector<T>)copy(); 142 OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator(); 143 while (iter.hasNext()) { 144 iter.advance(); 145 int key = iter.key(); 146 T value = iter.value(); 147 if (entries.containsKey(key)) { 148 res.setEntry(key, entries.get(key).add(value)); 149 } else { 150 res.setEntry(key, value); 151 } 152 } 153 return res; 154 155 } 156 157 158 /** {@inheritDoc} */ 159 public FieldVector<T> add(T[] v) throws IllegalArgumentException { 160 checkVectorDimensions(v.length); 161 SparseFieldVector<T> res = new SparseFieldVector<T>(field,getDimension()); 162 for (int i = 0; i < v.length; i++) { 163 res.setEntry(i, v[i].add(getEntry(i))); 164 } 165 return res; 166 } 167 168 /** 169 * Construct a vector by appending a vector to this vector. 170 * @param v vector to append to this one. 171 * @return a new vector 172 */ 173 public FieldVector<T> append(SparseFieldVector<T> v) { 174 SparseFieldVector<T> res = new SparseFieldVector<T>(this, v.getDimension()); 175 OpenIntToFieldHashMap<T>.Iterator iter = v.entries.iterator(); 176 while (iter.hasNext()) { 177 iter.advance(); 178 res.setEntry(iter.key() + virtualSize, iter.value()); 179 } 180 return res; 181 } 182 183 /** {@inheritDoc} */ 184 public FieldVector<T> append(FieldVector<T> v) { 185 if (v instanceof SparseFieldVector<?>) { 186 return append((SparseFieldVector<T>) v); 187 } else { 188 return append(v.toArray()); 189 } 190 } 191 192 /** {@inheritDoc} */ 193 public FieldVector<T> append(T d) { 194 FieldVector<T> res = new SparseFieldVector<T>(this, 1); 195 res.setEntry(virtualSize, d); 196 return res; 197 } 198 199 /** {@inheritDoc} */ 200 public FieldVector<T> append(T[] a) { 201 FieldVector<T> res = new SparseFieldVector<T>(this, a.length); 202 for (int i = 0; i < a.length; i++) { 203 res.setEntry(i + virtualSize, a[i]); 204 } 205 return res; 206 } 207 208 /** {@inheritDoc} */ 209 public FieldVector<T> copy() { 210 return new SparseFieldVector<T>(this); 211 } 212 213 /** {@inheritDoc} */ 214 public T dotProduct(FieldVector<T> v) throws IllegalArgumentException { 215 checkVectorDimensions(v.getDimension()); 216 T res = field.getZero(); 217 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 218 while (iter.hasNext()) { 219 iter.advance(); 220 res = res.add(v.getEntry(iter.key()).multiply(iter.value())); 221 } 222 return res; 223 } 224 225 /** {@inheritDoc} */ 226 public T dotProduct(T[] v) throws IllegalArgumentException { 227 checkVectorDimensions(v.length); 228 T res = field.getZero(); 229 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 230 while (iter.hasNext()) { 231 int idx = iter.key(); 232 T value = field.getZero(); 233 if (idx < v.length) { 234 value = v[idx]; 235 } 236 res = res.add(value.multiply(iter.value())); 237 } 238 return res; 239 } 240 241 /** {@inheritDoc} */ 242 public FieldVector<T> ebeDivide(FieldVector<T> v) 243 throws IllegalArgumentException { 244 checkVectorDimensions(v.getDimension()); 245 SparseFieldVector<T> res = new SparseFieldVector<T>(this); 246 OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator(); 247 while (iter.hasNext()) { 248 iter.advance(); 249 res.setEntry(iter.key(), iter.value().divide(v.getEntry(iter.key()))); 250 } 251 return res; 252 } 253 254 /** {@inheritDoc} */ 255 public FieldVector<T> ebeDivide(T[] v) throws IllegalArgumentException { 256 checkVectorDimensions(v.length); 257 SparseFieldVector<T> res = new SparseFieldVector<T>(this); 258 OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator(); 259 while (iter.hasNext()) { 260 iter.advance(); 261 res.setEntry(iter.key(), iter.value().divide(v[iter.key()])); 262 } 263 return res; 264 } 265 266 /** {@inheritDoc} */ 267 public FieldVector<T> ebeMultiply(FieldVector<T> v)throws IllegalArgumentException { 268 checkVectorDimensions(v.getDimension()); 269 SparseFieldVector<T> res = new SparseFieldVector<T>(this); 270 OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator(); 271 while (iter.hasNext()) { 272 iter.advance(); 273 res.setEntry(iter.key(), iter.value().multiply(v.getEntry(iter.key()))); 274 } 275 return res; 276 } 277 278 /** {@inheritDoc} */ 279 public FieldVector<T> ebeMultiply(T[] v) throws IllegalArgumentException { 280 checkVectorDimensions(v.length); 281 SparseFieldVector<T> res = new SparseFieldVector<T>(this); 282 OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator(); 283 while (iter.hasNext()) { 284 iter.advance(); 285 res.setEntry(iter.key(), iter.value().multiply(v[iter.key()])); 286 } 287 return res; 288 } 289 290 /** {@inheritDoc} */ 291 public T[] getData() { 292 T[] res = buildArray(virtualSize); 293 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 294 while (iter.hasNext()) { 295 iter.advance(); 296 res[iter.key()] = iter.value(); 297 } 298 return res; 299 } 300 301 /** {@inheritDoc} */ 302 public int getDimension() { 303 return virtualSize; 304 } 305 306 /** {@inheritDoc} */ 307 public T getEntry(int index) throws MatrixIndexException { 308 checkIndex(index); 309 return entries.get(index); 310 } 311 312 /** {@inheritDoc} */ 313 public Field<T> getField() { 314 return field; 315 } 316 317 /** {@inheritDoc} */ 318 public FieldVector<T> getSubVector(int index, int n) 319 throws MatrixIndexException { 320 checkIndex(index); 321 checkIndex(index + n - 1); 322 SparseFieldVector<T> res = new SparseFieldVector<T>(field,n); 323 int end = index + n; 324 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 325 while (iter.hasNext()) { 326 iter.advance(); 327 int key = iter.key(); 328 if (key >= index && key < end) { 329 res.setEntry(key - index, iter.value()); 330 } 331 } 332 return res; 333 } 334 335 /** {@inheritDoc} */ 336 public FieldVector<T> mapAdd(T d) { 337 return copy().mapAddToSelf(d); 338 } 339 340 /** {@inheritDoc} */ 341 public FieldVector<T> mapAddToSelf(T d) { 342 for (int i = 0; i < virtualSize; i++) { 343 setEntry(i, getEntry(i).add(d)); 344 } 345 return this; 346 } 347 348 /** {@inheritDoc} */ 349 public FieldVector<T> mapDivide(T d) { 350 return copy().mapDivideToSelf(d); 351 } 352 353 /** {@inheritDoc} */ 354 public FieldVector<T> mapDivideToSelf(T d) { 355 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 356 while (iter.hasNext()) { 357 iter.advance(); 358 entries.put(iter.key(), iter.value().divide(d)); 359 } 360 return this; 361 } 362 363 /** {@inheritDoc} */ 364 public FieldVector<T> mapInv() { 365 return copy().mapInvToSelf(); 366 } 367 368 /** {@inheritDoc} */ 369 public FieldVector<T> mapInvToSelf() { 370 for (int i = 0; i < virtualSize; i++) { 371 setEntry(i, field.getOne().divide(getEntry(i))); 372 } 373 return this; 374 } 375 376 /** {@inheritDoc} */ 377 public FieldVector<T> mapMultiply(T d) { 378 return copy().mapMultiplyToSelf(d); 379 } 380 381 /** {@inheritDoc} */ 382 public FieldVector<T> mapMultiplyToSelf(T d) { 383 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 384 while (iter.hasNext()) { 385 iter.advance(); 386 entries.put(iter.key(), iter.value().multiply(d)); 387 } 388 return this; 389 } 390 391 /** {@inheritDoc} */ 392 public FieldVector<T> mapSubtract(T d) { 393 return copy().mapSubtractToSelf(d); 394 } 395 396 /** {@inheritDoc} */ 397 public FieldVector<T> mapSubtractToSelf(T d) { 398 return mapAddToSelf(field.getZero().subtract(d)); 399 } 400 401 /** 402 * Optimized method to compute outer product when both vectors are sparse. 403 * @param v vector with which outer product should be computed 404 * @return the square matrix outer product between instance and v 405 * @throws IllegalArgumentException if v is not the same size as {@code this} 406 */ 407 public FieldMatrix<T> outerProduct(SparseFieldVector<T> v) 408 throws IllegalArgumentException { 409 checkVectorDimensions(v.getDimension()); 410 SparseFieldMatrix<T> res = new SparseFieldMatrix<T>(field, virtualSize, virtualSize); 411 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 412 while (iter.hasNext()) { 413 iter.advance(); 414 OpenIntToFieldHashMap<T>.Iterator iter2 = v.entries.iterator(); 415 while (iter2.hasNext()) { 416 iter2.advance(); 417 res.setEntry(iter.key(), iter2.key(), iter.value().multiply(iter2.value())); 418 } 419 } 420 return res; 421 } 422 423 /** {@inheritDoc} */ 424 public FieldMatrix<T> outerProduct(T[] v) throws IllegalArgumentException { 425 checkVectorDimensions(v.length); 426 FieldMatrix<T> res = new SparseFieldMatrix<T>(field, virtualSize, virtualSize); 427 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 428 while (iter.hasNext()) { 429 iter.advance(); 430 int row = iter.key(); 431 FieldElement<T>value = iter.value(); 432 for (int col = 0; col < virtualSize; col++) { 433 res.setEntry(row, col, value.multiply(v[col])); 434 } 435 } 436 return res; 437 } 438 439 /** {@inheritDoc} */ 440 public FieldMatrix<T> outerProduct(FieldVector<T> v) 441 throws IllegalArgumentException { 442 if(v instanceof SparseFieldVector<?>) 443 return outerProduct((SparseFieldVector<T>)v); 444 else 445 return outerProduct(v.toArray()); 446 } 447 448 /** {@inheritDoc} */ 449 public FieldVector<T> projection(FieldVector<T> v) 450 throws IllegalArgumentException { 451 checkVectorDimensions(v.getDimension()); 452 return v.mapMultiply(dotProduct(v).divide(v.dotProduct(v))); 453 } 454 455 /** {@inheritDoc} */ 456 public FieldVector<T> projection(T[] v) throws IllegalArgumentException { 457 checkVectorDimensions(v.length); 458 return projection(new SparseFieldVector<T>(field,v)); 459 } 460 461 /** {@inheritDoc} */ 462 public void set(T value) { 463 for (int i = 0; i < virtualSize; i++) { 464 setEntry(i, value); 465 } 466 } 467 468 /** {@inheritDoc} */ 469 public void setEntry(int index, T value) throws MatrixIndexException { 470 checkIndex(index); 471 entries.put(index, value); 472 } 473 474 /** {@inheritDoc} */ 475 public void setSubVector(int index, FieldVector<T> v) 476 throws MatrixIndexException { 477 checkIndex(index); 478 checkIndex(index + v.getDimension() - 1); 479 setSubVector(index, v.getData()); 480 } 481 482 /** {@inheritDoc} */ 483 public void setSubVector(int index, T[] v) throws MatrixIndexException { 484 checkIndex(index); 485 checkIndex(index + v.length - 1); 486 for (int i = 0; i < v.length; i++) { 487 setEntry(i + index, v[i]); 488 } 489 490 } 491 492 /** 493 * Optimized method to subtract SparseRealVectors. 494 * @param v The vector to subtract from <code>this</code> 495 * @return The difference of <code>this</code> and <code>v</code> 496 * @throws IllegalArgumentException If the dimensions don't match 497 */ 498 public SparseFieldVector<T> subtract(SparseFieldVector<T> v) throws IllegalArgumentException{ 499 checkVectorDimensions(v.getDimension()); 500 SparseFieldVector<T> res = (SparseFieldVector<T>)copy(); 501 OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator(); 502 while (iter.hasNext()) { 503 iter.advance(); 504 int key = iter.key(); 505 if (entries.containsKey(key)) { 506 res.setEntry(key, entries.get(key).subtract(iter.value())); 507 } else { 508 res.setEntry(key, field.getZero().subtract(iter.value())); 509 } 510 } 511 return res; 512 } 513 514 /** {@inheritDoc} */ 515 public FieldVector<T> subtract(FieldVector<T> v) 516 throws IllegalArgumentException { 517 if(v instanceof SparseFieldVector<?>) 518 return subtract((SparseFieldVector<T>)v); 519 else 520 return subtract(v.toArray()); 521 } 522 523 /** {@inheritDoc} */ 524 public FieldVector<T> subtract(T[] v) throws IllegalArgumentException { 525 checkVectorDimensions(v.length); 526 SparseFieldVector<T> res = new SparseFieldVector<T>(this); 527 for (int i = 0; i < v.length; i++) { 528 if (entries.containsKey(i)) { 529 res.setEntry(i, entries.get(i).subtract(v[i])); 530 } else { 531 res.setEntry(i, field.getZero().subtract(v[i])); 532 } 533 } 534 return res; 535 } 536 537 /** {@inheritDoc} */ 538 public T[] toArray() { 539 return getData(); 540 } 541 542 /** 543 * Check if an index is valid. 544 * 545 * @param index 546 * index to check 547 * @exception MatrixIndexException 548 * if index is not valid 549 */ 550 private void checkIndex(final int index) throws MatrixIndexException { 551 if (index < 0 || index >= getDimension()) { 552 throw new MatrixIndexException(LocalizedFormats.INDEX_OUT_OF_RANGE, 553 index, 0, getDimension() - 1); 554 } 555 } 556 557 /** 558 * Check if instance dimension is equal to some expected value. 559 * 560 * @param n 561 * expected dimension. 562 * @exception IllegalArgumentException 563 * if the dimension is inconsistent with vector size 564 */ 565 protected void checkVectorDimensions(int n) throws IllegalArgumentException { 566 if (getDimension() != n) { 567 throw MathRuntimeException.createIllegalArgumentException( 568 LocalizedFormats.VECTOR_LENGTH_MISMATCH, 569 getDimension(), n); 570 } 571 } 572 573 574 /** {@inheritDoc} */ 575 public FieldVector<T> add(FieldVector<T> v) throws IllegalArgumentException { 576 if (v instanceof SparseFieldVector<?>) { 577 return add((SparseFieldVector<T>)v); 578 } else { 579 return add(v.toArray()); 580 } 581 } 582 583 /** Build an array of elements. 584 * @param length size of the array to build 585 * @return a new array 586 */ 587 @SuppressWarnings("unchecked") // field is type T 588 private T[] buildArray(final int length) { 589 return (T[]) Array.newInstance(field.getZero().getClass(), length); 590 } 591 592 593 /** {@inheritDoc} */ 594 @Override 595 public int hashCode() { 596 final int prime = 31; 597 int result = 1; 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()) { 602 iter.advance(); 603 int temp = iter.value().hashCode(); 604 result = prime * result + temp; 605 } 606 return result; 607 } 608 609 610 /** {@inheritDoc} */ 611 @Override 612 public boolean equals(Object obj) { 613 614 if (this == obj) { 615 return true; 616 } 617 618 if (!(obj instanceof SparseFieldVector<?>)) { 619 return false; 620 } 621 622 @SuppressWarnings("unchecked") // OK, because "else if" check below ensures that 623 // other must be the same type as this 624 SparseFieldVector<T> other = (SparseFieldVector<T>) obj; 625 if (field == null) { 626 if (other.field != null) { 627 return false; 628 } 629 } else if (!field.equals(other.field)) { 630 return false; 631 } 632 if (virtualSize != other.virtualSize) { 633 return false; 634 } 635 636 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 637 while (iter.hasNext()) { 638 iter.advance(); 639 T test = other.getEntry(iter.key()); 640 if (!test.equals(iter.value())) { 641 return false; 642 } 643 } 644 iter = other.getEntries().iterator(); 645 while (iter.hasNext()) { 646 iter.advance(); 647 T test = iter.value(); 648 if (!test.equals(getEntry(iter.key()))) { 649 return false; 650 } 651 } 652 return true; 653 } 654 655 656 657 } 658