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.MathRuntimeException; 025 import org.apache.commons.math.util.OpenIntToFieldHashMap; 026 027 /** 028 * This class implements the {@link FieldVector} interface with a {@link OpenIntToFieldHashMap} backing store. 029 * @param <T> the type of the field elements 030 * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $ 031 * @since 2.0 032 */ 033 public class SparseFieldVector<T extends FieldElement<T>> implements FieldVector<T>, Serializable { 034 035 /** 036 * Serial version id 037 */ 038 private static final long serialVersionUID = 7841233292190413362L; 039 /** Field to which the elements belong. */ 040 private final Field<T> field; 041 /** Entries of the vector. */ 042 private final OpenIntToFieldHashMap<T> entries; 043 /** Dimension of the vector. */ 044 private final int virtualSize; 045 046 /** 047 * Build a 0-length vector. 048 * <p>Zero-length vectors may be used to initialize construction of vectors 049 * by data gathering. We start with zero-length and use either the {@link 050 * #SparseFieldVector(SparseFieldVector, int)} constructor 051 * or one of the <code>append</code> method ({@link #append(FieldElement)}, 052 * {@link #append(FieldElement[])}, {@link #append(FieldVector)}, 053 * {@link #append(SparseFieldVector)}) to gather data into this vector.</p> 054 * @param field field to which the elements belong 055 */ 056 public SparseFieldVector(Field<T> field) { 057 this(field, 0); 058 } 059 060 061 /** 062 * Construct a (dimension)-length vector of zeros. 063 * @param field field to which the elements belong 064 * @param dimension Size of the vector 065 */ 066 public SparseFieldVector(Field<T> field, int dimension) { 067 this.field = field; 068 virtualSize = dimension; 069 entries = new OpenIntToFieldHashMap<T>(field); 070 } 071 072 /** 073 * Build a resized vector, for use with append. 074 * @param v The original vector 075 * @param resize The amount to resize it 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 * @param field field to which the elements belong 087 * @param dimension The size of the vector 088 * @param expectedSize The expected number of non-zero entries 089 */ 090 public SparseFieldVector(Field<T> field, int dimension, int expectedSize) { 091 this.field = field; 092 virtualSize = dimension; 093 entries = new OpenIntToFieldHashMap<T>(field,expectedSize); 094 } 095 096 /** 097 * Create from a Field array. 098 * Only non-zero entries will be stored 099 * @param field field to which the elements belong 100 * @param values The set of values to create from 101 */ 102 public SparseFieldVector(Field<T> field, T[] values) { 103 this.field = field; 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); 109 } 110 } 111 112 113 114 /** 115 * Copy constructor. 116 * @param v The instance to copy from 117 */ 118 public SparseFieldVector(SparseFieldVector<T> v) { 119 field = v.field; 120 virtualSize = v.getDimension(); 121 entries = new OpenIntToFieldHashMap<T>(v.getEntries()); 122 } 123 124 /** 125 * Get the entries of this instance. 126 * @return entries of this instance 127 */ 128 private OpenIntToFieldHashMap<T> getEntries() { 129 return entries; 130 } 131 132 /** 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 137 */ 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()) { 143 iter.advance(); 144 int key = iter.key(); 145 T value = iter.value(); 146 if (entries.containsKey(key)) { 147 res.setEntry(key, entries.get(key).add(value)); 148 } else { 149 res.setEntry(key, value); 150 } 151 } 152 return res; 153 154 } 155 156 157 /** {@inheritDoc} */ 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))); 163 } 164 return res; 165 } 166 167 /** 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 171 */ 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()) { 176 iter.advance(); 177 res.setEntry(iter.key() + virtualSize, iter.value()); 178 } 179 return res; 180 } 181 182 /** {@inheritDoc} */ 183 public FieldVector<T> append(FieldVector<T> v) { 184 if (v instanceof SparseFieldVector<?>) { 185 return append((SparseFieldVector<T>) v); 186 } else { 187 return append(v.toArray()); 188 } 189 } 190 191 /** {@inheritDoc} */ 192 public FieldVector<T> append(T d) { 193 FieldVector<T> res = new SparseFieldVector<T>(this, 1); 194 res.setEntry(virtualSize, d); 195 return res; 196 } 197 198 /** {@inheritDoc} */ 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]); 203 } 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 IllegalArgumentException { 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 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) { 233 value = v[idx]; 234 } 235 res = res.add(value.multiply(iter.value())); 236 } 237 return res; 238 } 239 240 /** {@inheritDoc} */ 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()) { 247 iter.advance(); 248 res.setEntry(iter.key(), iter.value().divide(v.getEntry(iter.key()))); 249 } 250 return res; 251 } 252 253 /** {@inheritDoc} */ 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()) { 259 iter.advance(); 260 res.setEntry(iter.key(), iter.value().divide(v[iter.key()])); 261 } 262 return res; 263 } 264 265 /** {@inheritDoc} */ 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()) { 271 iter.advance(); 272 res.setEntry(iter.key(), iter.value().multiply(v.getEntry(iter.key()))); 273 } 274 return res; 275 } 276 277 /** {@inheritDoc} */ 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()) { 283 iter.advance(); 284 res.setEntry(iter.key(), iter.value().multiply(v[iter.key()])); 285 } 286 return res; 287 } 288 289 /** {@inheritDoc} */ 290 public T[] getData() { 291 T[] res = buildArray(virtualSize); 292 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 293 while (iter.hasNext()) { 294 iter.advance(); 295 res[iter.key()] = iter.value(); 296 } 297 return res; 298 } 299 300 /** {@inheritDoc} */ 301 public int getDimension() { 302 return virtualSize; 303 } 304 305 /** {@inheritDoc} */ 306 public T getEntry(int index) throws MatrixIndexException { 307 checkIndex(index); 308 return entries.get(index); 309 } 310 311 /** {@inheritDoc} */ 312 public Field<T> getField() { 313 return field; 314 } 315 316 /** {@inheritDoc} */ 317 public FieldVector<T> getSubVector(int index, int n) 318 throws MatrixIndexException { 319 checkIndex(index); 320 checkIndex(index + n - 1); 321 SparseFieldVector<T> res = new SparseFieldVector<T>(field,n); 322 int end = index + n; 323 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 324 while (iter.hasNext()) { 325 iter.advance(); 326 int key = iter.key(); 327 if (key >= index && key < end) { 328 res.setEntry(key - index, iter.value()); 329 } 330 } 331 return res; 332 } 333 334 /** {@inheritDoc} */ 335 public FieldVector<T> mapAdd(T d) { 336 return copy().mapAddToSelf(d); 337 } 338 339 /** {@inheritDoc} */ 340 public FieldVector<T> mapAddToSelf(T d) { 341 for (int i = 0; i < virtualSize; i++) { 342 setEntry(i, getEntry(i).add(d)); 343 } 344 return this; 345 } 346 347 /** {@inheritDoc} */ 348 public FieldVector<T> mapDivide(T d) { 349 return copy().mapDivideToSelf(d); 350 } 351 352 /** {@inheritDoc} */ 353 public FieldVector<T> mapDivideToSelf(T d) { 354 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 355 while (iter.hasNext()) { 356 iter.advance(); 357 entries.put(iter.key(), iter.value().divide(d)); 358 } 359 return this; 360 } 361 362 /** {@inheritDoc} */ 363 public FieldVector<T> mapInv() { 364 return copy().mapInvToSelf(); 365 } 366 367 /** {@inheritDoc} */ 368 public FieldVector<T> mapInvToSelf() { 369 for (int i = 0; i < virtualSize; i++) { 370 setEntry(i, field.getOne().divide(getEntry(i))); 371 } 372 return this; 373 } 374 375 /** {@inheritDoc} */ 376 public FieldVector<T> mapMultiply(T d) { 377 return copy().mapMultiplyToSelf(d); 378 } 379 380 /** {@inheritDoc} */ 381 public FieldVector<T> mapMultiplyToSelf(T d) { 382 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 383 while (iter.hasNext()) { 384 iter.advance(); 385 entries.put(iter.key(), iter.value().multiply(d)); 386 } 387 return this; 388 } 389 390 /** {@inheritDoc} */ 391 public FieldVector<T> mapSubtract(T d) { 392 return copy().mapSubtractToSelf(d); 393 } 394 395 /** {@inheritDoc} */ 396 public FieldVector<T> mapSubtractToSelf(T d) { 397 return mapAddToSelf(field.getZero().subtract(d)); 398 } 399 400 /** 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} 405 */ 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()) { 412 iter.advance(); 413 OpenIntToFieldHashMap<T>.Iterator iter2 = v.entries.iterator(); 414 while (iter2.hasNext()) { 415 iter2.advance(); 416 res.setEntry(iter.key(), iter2.key(), iter.value().multiply(iter2.value())); 417 } 418 } 419 return res; 420 } 421 422 /** {@inheritDoc} */ 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()) { 428 iter.advance(); 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])); 433 } 434 } 435 return res; 436 } 437 438 /** {@inheritDoc} */ 439 public FieldMatrix<T> outerProduct(FieldVector<T> v) 440 throws IllegalArgumentException { 441 if(v instanceof SparseFieldVector<?>) 442 return outerProduct((SparseFieldVector<T>)v); 443 else 444 return outerProduct(v.toArray()); 445 } 446 447 /** {@inheritDoc} */ 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))); 452 } 453 454 /** {@inheritDoc} */ 455 public FieldVector<T> projection(T[] v) throws IllegalArgumentException { 456 checkVectorDimensions(v.length); 457 return projection(new SparseFieldVector<T>(field,v)); 458 } 459 460 /** {@inheritDoc} */ 461 public void set(T value) { 462 for (int i = 0; i < virtualSize; i++) { 463 setEntry(i, value); 464 } 465 } 466 467 /** {@inheritDoc} */ 468 public void setEntry(int index, T value) throws MatrixIndexException { 469 checkIndex(index); 470 entries.put(index, value); 471 } 472 473 /** {@inheritDoc} */ 474 public void setSubVector(int index, FieldVector<T> v) 475 throws MatrixIndexException { 476 checkIndex(index); 477 checkIndex(index + v.getDimension() - 1); 478 setSubVector(index, v.getData()); 479 } 480 481 /** {@inheritDoc} */ 482 public void setSubVector(int index, T[] v) throws MatrixIndexException { 483 checkIndex(index); 484 checkIndex(index + v.length - 1); 485 for (int i = 0; i < v.length; i++) { 486 setEntry(i + index, v[i]); 487 } 488 489 } 490 491 /** 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 496 */ 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()) { 502 iter.advance(); 503 int key = iter.key(); 504 if (entries.containsKey(key)) { 505 res.setEntry(key, entries.get(key).subtract(iter.value())); 506 } else { 507 res.setEntry(key, field.getZero().subtract(iter.value())); 508 } 509 } 510 return res; 511 } 512 513 /** {@inheritDoc} */ 514 public FieldVector<T> subtract(FieldVector<T> v) 515 throws IllegalArgumentException { 516 if(v instanceof SparseFieldVector<?>) 517 return subtract((SparseFieldVector<T>)v); 518 else 519 return subtract(v.toArray()); 520 } 521 522 /** {@inheritDoc} */ 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])); 529 } else { 530 res.setEntry(i, field.getZero().subtract(v[i])); 531 } 532 } 533 return res; 534 } 535 536 /** {@inheritDoc} */ 537 public T[] toArray() { 538 return getData(); 539 } 540 541 /** 542 * Check if an index is valid. 543 * 544 * @param index 545 * index to check 546 * @exception MatrixIndexException 547 * if index is not valid 548 */ 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); 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 "vector length mismatch: got {0} but expected {1}", 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") 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 @SuppressWarnings("unchecked") 612 @Override 613 public boolean equals(Object obj) { 614 615 if (this == obj) { 616 return true; 617 } 618 619 if (obj == null) { 620 return false; 621 } 622 623 if (!(obj instanceof SparseFieldVector)) { 624 return false; 625 } 626 627 SparseFieldVector<T> other = (SparseFieldVector<T>) obj; 628 if (field == null) { 629 if (other.field != null) { 630 return false; 631 } 632 } else if (!field.equals(other.field)) { 633 return false; 634 } 635 if (virtualSize != other.virtualSize) { 636 return false; 637 } 638 639 OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator(); 640 while (iter.hasNext()) { 641 iter.advance(); 642 T test = other.getEntry(iter.key()); 643 if (!test.equals(iter.value())) { 644 return false; 645 } 646 } 647 iter = other.getEntries().iterator(); 648 while (iter.hasNext()) { 649 iter.advance(); 650 T test = iter.value(); 651 if (!test.equals(getEntry(iter.key()))) { 652 return false; 653 } 654 } 655 return true; 656 } 657 658 659 660 }