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 org.apache.commons.math.Field; 20 import org.apache.commons.math.FieldElement; 21 import org.apache.commons.math.util.OpenIntToFieldHashMap; 22 23 /** 24 * Sparse matrix implementation based on an open addressed map. 25 * 26 * @param <T> the type of the field elements 27 * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ 28 * @since 2.0 29 */ 30 public class SparseFieldMatrix<T extends FieldElement<T>> extends AbstractFieldMatrix<T> { 31 /** 32 * Serial id 33 */ 34 private static final long serialVersionUID = 9078068119297757342L; 35 /** Storage for (sparse) matrix elements. */ 36 private final OpenIntToFieldHashMap<T> entries; 37 /** 38 * row dimension 39 */ 40 private final int rows; 41 /** 42 * column dimension 43 */ 44 private final int columns; 45 46 47 /** 48 * Creates a matrix with no data. 49 * @param field field to which the elements belong 50 */ 51 public SparseFieldMatrix(final Field<T> field) { 52 super(field); 53 rows = 0; 54 columns= 0; 55 entries = new OpenIntToFieldHashMap<T>(field); 56 } 57 58 /** 59 * Create a new SparseFieldMatrix<T> with the supplied row and column dimensions. 60 * 61 * @param field field to which the elements belong 62 * @param rowDimension the number of rows in the new matrix 63 * @param columnDimension the number of columns in the new matrix 64 * @throws IllegalArgumentException if row or column dimension is not positive 65 */ 66 public SparseFieldMatrix(final Field<T> field, 67 final int rowDimension, final int columnDimension) 68 throws IllegalArgumentException { 69 super(field, rowDimension, columnDimension); 70 this.rows = rowDimension; 71 this.columns = columnDimension; 72 entries = new OpenIntToFieldHashMap<T>(field); 73 } 74 75 /** 76 * Copy constructor. 77 * @param other The instance to copy 78 */ 79 public SparseFieldMatrix(SparseFieldMatrix<T> other) { 80 super(other.getField(), other.getRowDimension(), other.getColumnDimension()); 81 rows = other.getRowDimension(); 82 columns = other.getColumnDimension(); 83 entries = new OpenIntToFieldHashMap<T>(other.entries); 84 } 85 86 /** 87 * Generic copy constructor. 88 * @param other The instance to copy 89 */ 90 public SparseFieldMatrix(FieldMatrix<T> other){ 91 super(other.getField(), other.getRowDimension(), other.getColumnDimension()); 92 rows = other.getRowDimension(); 93 columns = other.getColumnDimension(); 94 entries = new OpenIntToFieldHashMap<T>(getField()); 95 for (int i = 0; i < rows; i++) { 96 for (int j = 0; j < columns; j++) { 97 setEntry(i, j, other.getEntry(i, j)); 98 } 99 } 100 } 101 102 /** {@inheritDoc} */ 103 @Override 104 public void addToEntry(int row, int column, T increment) 105 throws MatrixIndexException { 106 checkRowIndex(row); 107 checkColumnIndex(column); 108 final int key = computeKey(row, column); 109 final T value = entries.get(key).add(increment); 110 if (getField().getZero().equals(value)) { 111 entries.remove(key); 112 } else { 113 entries.put(key, value); 114 } 115 116 } 117 118 /** {@inheritDoc} */ 119 @Override 120 public FieldMatrix<T> copy() { 121 return new SparseFieldMatrix<T>(this); 122 } 123 124 /** {@inheritDoc} */ 125 @Override 126 public FieldMatrix<T> createMatrix(int rowDimension, int columnDimension) 127 throws IllegalArgumentException { 128 return new SparseFieldMatrix<T>(getField(), rowDimension, columnDimension); 129 } 130 131 /** {@inheritDoc} */ 132 @Override 133 public int getColumnDimension() { 134 return columns; 135 } 136 137 /** {@inheritDoc} */ 138 @Override 139 public T getEntry(int row, int column) throws MatrixIndexException { 140 checkRowIndex(row); 141 checkColumnIndex(column); 142 return entries.get(computeKey(row, column)); 143 } 144 145 /** {@inheritDoc} */ 146 @Override 147 public int getRowDimension() { 148 return rows; 149 } 150 151 /** {@inheritDoc} */ 152 @Override 153 public void multiplyEntry(int row, int column, T factor) 154 throws MatrixIndexException { 155 checkRowIndex(row); 156 checkColumnIndex(column); 157 final int key = computeKey(row, column); 158 final T value = entries.get(key).multiply(factor); 159 if (getField().getZero().equals(value)) { 160 entries.remove(key); 161 } else { 162 entries.put(key, value); 163 } 164 165 } 166 167 /** {@inheritDoc} */ 168 @Override 169 public void setEntry(int row, int column, T value) 170 throws MatrixIndexException { 171 checkRowIndex(row); 172 checkColumnIndex(column); 173 if (getField().getZero().equals(value)) { 174 entries.remove(computeKey(row, column)); 175 } else { 176 entries.put(computeKey(row, column), value); 177 } 178 179 } 180 /** 181 * Compute the key to access a matrix element 182 * @param row row index of the matrix element 183 * @param column column index of the matrix element 184 * @return key within the map to access the matrix element 185 */ 186 private int computeKey(int row, int column) { 187 return row * columns + column; 188 } 189 190 } 191