    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
    018    package org.apache.commons.math3.linear;
    019
    020    import java.io.Serializable;
    021
    022    import org.apache.commons.math3.exception.DimensionMismatchException;
    023    import org.apache.commons.math3.exception.NotStrictlyPositiveException;
    024    import org.apache.commons.math3.exception.NumberIsTooLargeException;
    025    import org.apache.commons.math3.exception.OutOfRangeException;
    026    import org.apache.commons.math3.util.OpenIntToDoubleHashMap;
    027
    028    /**
    029     * Sparse matrix implementation based on an open addressed map.
    030     *
    031     * @version $Id: OpenMapRealMatrix.java 1416643 2012-12-03 19:37:14Z tn $
    032     * @since 2.0
    033     * @deprecated As of version 3.1, this class is deprecated, for reasons exposed
    034     * in this JIRA
    035     * <a href="https://issues.apache.org/jira/browse/MATH-870">ticket</a>. This
    036     * class will be removed in version 4.0.
    037     *
    038     */
    039    @Deprecated
    040    public 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    }