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