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 org.apache.commons.math.Field;
020 import org.apache.commons.math.FieldElement;
021 import org.apache.commons.math.util.OpenIntToFieldHashMap;
022
023 /**
024 * Sparse matrix implementation based on an open addressed map.
025 *
026 * @param <T> the type of the field elements
027 * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $
028 * @since 2.0
029 */
030 public class SparseFieldMatrix<T extends FieldElement<T>> extends AbstractFieldMatrix<T> {
031 /**
032 * Serial id
033 */
034 private static final long serialVersionUID = 9078068119297757342L;
035 /** Storage for (sparse) matrix elements. */
036 private final OpenIntToFieldHashMap<T> entries;
037 /**
038 * row dimension
039 */
040 private final int rows;
041 /**
042 * column dimension
043 */
044 private final int columns;
045
046
047 /**
048 * Creates a matrix with no data.
049 * @param field field to which the elements belong
050 */
051 public SparseFieldMatrix(final Field<T> field) {
052 super(field);
053 rows = 0;
054 columns= 0;
055 entries = new OpenIntToFieldHashMap<T>(field);
056 }
057
058 /**
059 * Create a new SparseFieldMatrix<T> with the supplied row and column dimensions.
060 *
061 * @param field field to which the elements belong
062 * @param rowDimension the number of rows in the new matrix
063 * @param columnDimension the number of columns in the new matrix
064 * @throws IllegalArgumentException if row or column dimension is not positive
065 */
066 public SparseFieldMatrix(final Field<T> field,
067 final int rowDimension, final int columnDimension)
068 throws IllegalArgumentException {
069 super(field, rowDimension, columnDimension);
070 this.rows = rowDimension;
071 this.columns = columnDimension;
072 entries = new OpenIntToFieldHashMap<T>(field);
073 }
074
075 /**
076 * Copy constructor.
077 * @param other The instance to copy
078 */
079 public SparseFieldMatrix(SparseFieldMatrix<T> other) {
080 super(other.getField(), other.getRowDimension(), other.getColumnDimension());
081 rows = other.getRowDimension();
082 columns = other.getColumnDimension();
083 entries = new OpenIntToFieldHashMap<T>(other.entries);
084 }
085
086 /**
087 * Generic copy constructor.
088 * @param other The instance to copy
089 */
090 public SparseFieldMatrix(FieldMatrix<T> other){
091 super(other.getField(), other.getRowDimension(), other.getColumnDimension());
092 rows = other.getRowDimension();
093 columns = other.getColumnDimension();
094 entries = new OpenIntToFieldHashMap<T>(getField());
095 for (int i = 0; i < rows; i++) {
096 for (int j = 0; j < columns; j++) {
097 setEntry(i, j, other.getEntry(i, j));
098 }
099 }
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 }