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