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.math3.linear;
019
020import java.io.Serializable;
021
022import org.apache.commons.math3.exception.DimensionMismatchException;
023import org.apache.commons.math3.exception.NotStrictlyPositiveException;
024import org.apache.commons.math3.exception.NumberIsTooLargeException;
025import org.apache.commons.math3.exception.OutOfRangeException;
026import org.apache.commons.math3.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        try {
139            return subtract((OpenMapRealMatrix) m);
140        } catch (ClassCastException cce) {
141            return (OpenMapRealMatrix) super.subtract(m);
142        }
143    }
144
145    /**
146     * Subtract {@code m} from this matrix.
147     *
148     * @param m Matrix to be subtracted.
149     * @return {@code this} - {@code m}.
150     * @throws MatrixDimensionMismatchException if {@code m} is not the same
151     * size as {@code this}.
152     */
153    public OpenMapRealMatrix subtract(OpenMapRealMatrix m)
154        throws MatrixDimensionMismatchException {
155        MatrixUtils.checkAdditionCompatible(this, m);
156
157        final OpenMapRealMatrix out = new OpenMapRealMatrix(this);
158        for (OpenIntToDoubleHashMap.Iterator iterator = m.entries.iterator(); iterator.hasNext();) {
159            iterator.advance();
160            final int row = iterator.key() / columns;
161            final int col = iterator.key() - row * columns;
162            out.setEntry(row, col, getEntry(row, col) - iterator.value());
163        }
164
165        return out;
166    }
167
168    /**
169     * {@inheritDoc}
170     *
171     * @throws NumberIsTooLargeException if {@code m} is an
172     * {@code OpenMapRealMatrix}, and the total number of entries of the product
173     * is larger than {@code Integer.MAX_VALUE}.
174     */
175    @Override
176    public RealMatrix multiply(final RealMatrix m)
177        throws DimensionMismatchException, NumberIsTooLargeException {
178        try {
179            return multiply((OpenMapRealMatrix) m);
180        } catch (ClassCastException cce) {
181
182            MatrixUtils.checkMultiplicationCompatible(this, m);
183
184            final int outCols = m.getColumnDimension();
185            final BlockRealMatrix out = new BlockRealMatrix(rows, outCols);
186            for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
187                iterator.advance();
188                final double value = iterator.value();
189                final int key      = iterator.key();
190                final int i        = key / columns;
191                final int k        = key % columns;
192                for (int j = 0; j < outCols; ++j) {
193                    out.addToEntry(i, j, value * m.getEntry(k, j));
194                }
195            }
196
197            return out;
198        }
199    }
200
201    /**
202     * Postmultiply this matrix by {@code m}.
203     *
204     * @param m Matrix to postmultiply by.
205     * @return {@code this} * {@code m}.
206     * @throws DimensionMismatchException if the number of rows of {@code m}
207     * differ from the number of columns of {@code this} matrix.
208     * @throws NumberIsTooLargeException if the total number of entries of the
209     * product is larger than {@code Integer.MAX_VALUE}.
210     */
211    public OpenMapRealMatrix multiply(OpenMapRealMatrix m)
212        throws DimensionMismatchException, NumberIsTooLargeException {
213        // Safety check.
214        MatrixUtils.checkMultiplicationCompatible(this, m);
215
216        final int outCols = m.getColumnDimension();
217        OpenMapRealMatrix out = new OpenMapRealMatrix(rows, outCols);
218        for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
219            iterator.advance();
220            final double value = iterator.value();
221            final int key      = iterator.key();
222            final int i        = key / columns;
223            final int k        = key % columns;
224            for (int j = 0; j < outCols; ++j) {
225                final int rightKey = m.computeKey(k, j);
226                if (m.entries.containsKey(rightKey)) {
227                    final int outKey = out.computeKey(i, j);
228                    final double outValue =
229                        out.entries.get(outKey) + value * m.entries.get(rightKey);
230                    if (outValue == 0.0) {
231                        out.entries.remove(outKey);
232                    } else {
233                        out.entries.put(outKey, outValue);
234                    }
235                }
236            }
237        }
238
239        return out;
240    }
241
242    /** {@inheritDoc} */
243    @Override
244    public double getEntry(int row, int column) throws OutOfRangeException {
245        MatrixUtils.checkRowIndex(this, row);
246        MatrixUtils.checkColumnIndex(this, column);
247        return entries.get(computeKey(row, column));
248    }
249
250    /** {@inheritDoc} */
251    @Override
252    public int getRowDimension() {
253        return rows;
254    }
255
256    /** {@inheritDoc} */
257    @Override
258    public void setEntry(int row, int column, double value)
259        throws OutOfRangeException {
260        MatrixUtils.checkRowIndex(this, row);
261        MatrixUtils.checkColumnIndex(this, column);
262        if (value == 0.0) {
263            entries.remove(computeKey(row, column));
264        } else {
265            entries.put(computeKey(row, column), value);
266        }
267    }
268
269    /** {@inheritDoc} */
270    @Override
271    public void addToEntry(int row, int column, double increment)
272        throws OutOfRangeException {
273        MatrixUtils.checkRowIndex(this, row);
274        MatrixUtils.checkColumnIndex(this, column);
275        final int key = computeKey(row, column);
276        final double value = entries.get(key) + increment;
277        if (value == 0.0) {
278            entries.remove(key);
279        } else {
280            entries.put(key, value);
281        }
282    }
283
284    /** {@inheritDoc} */
285    @Override
286    public void multiplyEntry(int row, int column, double factor)
287        throws OutOfRangeException {
288        MatrixUtils.checkRowIndex(this, row);
289        MatrixUtils.checkColumnIndex(this, column);
290        final int key = computeKey(row, column);
291        final double value = entries.get(key) * factor;
292        if (value == 0.0) {
293            entries.remove(key);
294        } else {
295            entries.put(key, value);
296        }
297    }
298
299    /**
300     * Compute the key to access a matrix element
301     * @param row row index of the matrix element
302     * @param column column index of the matrix element
303     * @return key within the map to access the matrix element
304     */
305    private int computeKey(int row, int column) {
306        return row * columns + column;
307    }
308
309
310}