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
018package org.apache.commons.math4.linear;
019
020import java.io.Serializable;
021
022import org.apache.commons.math4.exception.DimensionMismatchException;
023import org.apache.commons.math4.exception.NotStrictlyPositiveException;
024import org.apache.commons.math4.exception.NumberIsTooLargeException;
025import org.apache.commons.math4.exception.OutOfRangeException;
026import org.apache.commons.math4.util.OpenIntToDoubleHashMap;
027
028/**
029 * Sparse matrix implementation based on an open addressed map.
030 *
031 * <p>
032 *  Caveat: This implementation assumes that, for any {@code x},
033 *  the equality {@code x * 0d == 0d} holds. But it is is not true for
034 *  {@code NaN}. Moreover, zero entries will lose their sign.
035 *  Some operations (that involve {@code NaN} and/or infinities) may
036 *  thus give incorrect results.
037 * </p>
038 * @since 2.0
039 */
040public class OpenMapRealMatrix extends AbstractRealMatrix
041    implements SparseRealMatrix, Serializable {
042    /** Serializable version identifier. */
043    private static final long serialVersionUID = -5962461716457143437L;
044    /** Number of rows of the matrix. */
045    private final int rows;
046    /** Number of columns of the matrix. */
047    private final int columns;
048    /** Storage for (sparse) matrix elements. */
049    private final OpenIntToDoubleHashMap entries;
050
051    /**
052     * Build a sparse matrix with the supplied row and column dimensions.
053     *
054     * @param rowDimension Number of rows of the matrix.
055     * @param columnDimension Number of columns of the matrix.
056     * @throws NotStrictlyPositiveException if row or column dimension is not
057     * positive.
058     * @throws NumberIsTooLargeException if the total number of entries of the
059     * matrix is larger than {@code Integer.MAX_VALUE}.
060     */
061    public OpenMapRealMatrix(int rowDimension, int columnDimension)
062        throws NotStrictlyPositiveException, NumberIsTooLargeException {
063        super(rowDimension, columnDimension);
064        long lRow = rowDimension;
065        long lCol = columnDimension;
066        if (lRow * lCol >= Integer.MAX_VALUE) {
067            throw new NumberIsTooLargeException(lRow * lCol, Integer.MAX_VALUE, false);
068        }
069        this.rows = rowDimension;
070        this.columns = columnDimension;
071        this.entries = new OpenIntToDoubleHashMap(0.0);
072    }
073
074    /**
075     * Build a matrix by copying another one.
076     *
077     * @param matrix matrix to copy.
078     */
079    public OpenMapRealMatrix(OpenMapRealMatrix matrix) {
080        this.rows = matrix.rows;
081        this.columns = matrix.columns;
082        this.entries = new OpenIntToDoubleHashMap(matrix.entries);
083    }
084
085    /** {@inheritDoc} */
086    @Override
087    public OpenMapRealMatrix copy() {
088        return new OpenMapRealMatrix(this);
089    }
090
091    /**
092     * {@inheritDoc}
093     *
094     * @throws NumberIsTooLargeException if the total number of entries of the
095     * matrix is larger than {@code Integer.MAX_VALUE}.
096     */
097    @Override
098    public OpenMapRealMatrix createMatrix(int rowDimension, int columnDimension)
099        throws NotStrictlyPositiveException, NumberIsTooLargeException {
100        return new OpenMapRealMatrix(rowDimension, columnDimension);
101    }
102
103    /** {@inheritDoc} */
104    @Override
105    public int getColumnDimension() {
106        return columns;
107    }
108
109    /**
110     * Compute the sum of this matrix and {@code m}.
111     *
112     * @param m Matrix to be added.
113     * @return {@code this} + {@code m}.
114     * @throws MatrixDimensionMismatchException if {@code m} is not the same
115     * size as {@code this}.
116     */
117    public OpenMapRealMatrix add(OpenMapRealMatrix m)
118        throws MatrixDimensionMismatchException {
119
120        MatrixUtils.checkAdditionCompatible(this, m);
121
122        final OpenMapRealMatrix out = new OpenMapRealMatrix(this);
123        for (OpenIntToDoubleHashMap.Iterator iterator = m.entries.iterator(); iterator.hasNext();) {
124            iterator.advance();
125            final int row = iterator.key() / columns;
126            final int col = iterator.key() - row * columns;
127            out.setEntry(row, col, getEntry(row, col) + iterator.value());
128        }
129
130        return out;
131
132    }
133
134    /** {@inheritDoc} */
135    @Override
136    public OpenMapRealMatrix subtract(final RealMatrix m)
137        throws MatrixDimensionMismatchException {
138        if (m instanceof OpenMapRealMatrix) {
139            return subtract((OpenMapRealMatrix) m);
140        }
141        return (OpenMapRealMatrix) super.subtract(m);
142    }
143
144    /**
145     * Subtract {@code m} from this matrix.
146     *
147     * @param m Matrix to be subtracted.
148     * @return {@code this} - {@code m}.
149     * @throws MatrixDimensionMismatchException if {@code m} is not the same
150     * size as {@code this}.
151     */
152    public OpenMapRealMatrix subtract(OpenMapRealMatrix m)
153        throws MatrixDimensionMismatchException {
154        MatrixUtils.checkAdditionCompatible(this, m);
155
156        final OpenMapRealMatrix out = new OpenMapRealMatrix(this);
157        for (OpenIntToDoubleHashMap.Iterator iterator = m.entries.iterator(); iterator.hasNext();) {
158            iterator.advance();
159            final int row = iterator.key() / columns;
160            final int col = iterator.key() - row * columns;
161            out.setEntry(row, col, getEntry(row, col) - iterator.value());
162        }
163
164        return out;
165    }
166
167    /**
168     * {@inheritDoc}
169     *
170     * @throws NumberIsTooLargeException if {@code m} is an
171     * {@code OpenMapRealMatrix}, and the total number of entries of the product
172     * is larger than {@code Integer.MAX_VALUE}.
173     */
174    @Override
175    public RealMatrix multiply(final RealMatrix m)
176        throws DimensionMismatchException, NumberIsTooLargeException {
177        if (m instanceof OpenMapRealMatrix) {
178            return multiply((OpenMapRealMatrix) m);
179        }
180
181        MatrixUtils.checkMultiplicationCompatible(this, m);
182
183        final int outCols = m.getColumnDimension();
184        final BlockRealMatrix out = new BlockRealMatrix(rows, outCols);
185        for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
186            iterator.advance();
187            final double value = iterator.value();
188            final int key      = iterator.key();
189            final int i        = key / columns;
190            final int k        = key % columns;
191            for (int j = 0; j < outCols; ++j) {
192                out.addToEntry(i, j, value * m.getEntry(k, j));
193            }
194        }
195
196        return out;
197    }
198
199    /**
200     * Postmultiply this matrix by {@code m}.
201     *
202     * @param m Matrix to postmultiply by.
203     * @return {@code this} * {@code m}.
204     * @throws DimensionMismatchException if the number of rows of {@code m}
205     * differ from the number of columns of {@code this} matrix.
206     * @throws NumberIsTooLargeException if the total number of entries of the
207     * product is larger than {@code Integer.MAX_VALUE}.
208     */
209    public OpenMapRealMatrix multiply(OpenMapRealMatrix m)
210        throws DimensionMismatchException, NumberIsTooLargeException {
211        // Safety check.
212        MatrixUtils.checkMultiplicationCompatible(this, m);
213
214        final int outCols = m.getColumnDimension();
215        OpenMapRealMatrix out = new OpenMapRealMatrix(rows, outCols);
216        for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
217            iterator.advance();
218            final double value = iterator.value();
219            final int key      = iterator.key();
220            final int i        = key / columns;
221            final int k        = key % columns;
222            for (int j = 0; j < outCols; ++j) {
223                final int rightKey = m.computeKey(k, j);
224                if (m.entries.containsKey(rightKey)) {
225                    final int outKey = out.computeKey(i, j);
226                    final double outValue =
227                        out.entries.get(outKey) + value * m.entries.get(rightKey);
228                    if (outValue == 0.0) {
229                        out.entries.remove(outKey);
230                    } else {
231                        out.entries.put(outKey, outValue);
232                    }
233                }
234            }
235        }
236
237        return out;
238    }
239
240    /** {@inheritDoc} */
241    @Override
242    public double getEntry(int row, int column) throws OutOfRangeException {
243        MatrixUtils.checkRowIndex(this, row);
244        MatrixUtils.checkColumnIndex(this, column);
245        return entries.get(computeKey(row, column));
246    }
247
248    /** {@inheritDoc} */
249    @Override
250    public int getRowDimension() {
251        return rows;
252    }
253
254    /** {@inheritDoc} */
255    @Override
256    public void setEntry(int row, int column, double value)
257        throws OutOfRangeException {
258        MatrixUtils.checkRowIndex(this, row);
259        MatrixUtils.checkColumnIndex(this, column);
260        if (value == 0.0) {
261            entries.remove(computeKey(row, column));
262        } else {
263            entries.put(computeKey(row, column), value);
264        }
265    }
266
267    /** {@inheritDoc} */
268    @Override
269    public void addToEntry(int row, int column, double increment)
270        throws OutOfRangeException {
271        MatrixUtils.checkRowIndex(this, row);
272        MatrixUtils.checkColumnIndex(this, column);
273        final int key = computeKey(row, column);
274        final double value = entries.get(key) + increment;
275        if (value == 0.0) {
276            entries.remove(key);
277        } else {
278            entries.put(key, value);
279        }
280    }
281
282    /** {@inheritDoc} */
283    @Override
284    public void multiplyEntry(int row, int column, double factor)
285        throws OutOfRangeException {
286        MatrixUtils.checkRowIndex(this, row);
287        MatrixUtils.checkColumnIndex(this, column);
288        final int key = computeKey(row, column);
289        final double value = entries.get(key) * factor;
290        if (value == 0.0) {
291            entries.remove(key);
292        } else {
293            entries.put(key, value);
294        }
295    }
296
297    /**
298     * Compute the key to access a matrix element
299     * @param row row index of the matrix element
300     * @param column column index of the matrix element
301     * @return key within the map to access the matrix element
302     */
303    private int computeKey(int row, int column) {
304        return row * columns + column;
305    }
306
307
308}