    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    package org.apache.commons.math.linear;
    018
    019    import org.apache.commons.math.Field;
    020    import org.apache.commons.math.FieldElement;
    021    import org.apache.commons.math.util.OpenIntToFieldHashMap;
    022
    023    /**
    024     * Sparse matrix implementation based on an open addressed map.
    025     *
    026     * @param <T> the type of the field elements
    027     * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $
    028     * @since 2.0
    029     */
    030    public class SparseFieldMatrix<T extends FieldElement<T>> extends AbstractFieldMatrix<T> {
    031        /**
    032         *  Serial id
    033         */
    034        private static final long serialVersionUID = 9078068119297757342L;
    035        /** Storage for (sparse) matrix elements. */
    036        private final OpenIntToFieldHashMap<T> entries;
    037        /**
    038         * row dimension
    039         */
    040        private final int rows;
    041        /**
    042         * column dimension
    043         */
    044        private final int columns;
    045
    046
    047        /**
    048         * Creates a matrix with no data.
    049         * @param field field to which the elements belong
    050         */
    051        public SparseFieldMatrix(final Field<T> field) {
    052            super(field);
    053            rows = 0;
    054            columns= 0;
    055            entries = new OpenIntToFieldHashMap<T>(field);
    056        }
    057
    058        /**
    059         * Create a new SparseFieldMatrix<T> with the supplied row and column dimensions.
    060         *
    061         * @param field field to which the elements belong
    062         * @param rowDimension  the number of rows in the new matrix
    063         * @param columnDimension  the number of columns in the new matrix
    064         * @throws IllegalArgumentException if row or column dimension is not positive
    065         */
    066        public SparseFieldMatrix(final Field<T> field,
    067                                 final int rowDimension, final int columnDimension)
    068            throws IllegalArgumentException {
    069            super(field, rowDimension, columnDimension);
    070            this.rows = rowDimension;
    071            this.columns = columnDimension;
    072            entries = new OpenIntToFieldHashMap<T>(field);
    073        }
    074
    075        /**
    076         * Copy constructor.
    077         * @param other The instance to copy
    078         */
    079        public SparseFieldMatrix(SparseFieldMatrix<T> other) {
    080            super(other.getField(), other.getRowDimension(), other.getColumnDimension());
    081            rows = other.getRowDimension();
    082            columns = other.getColumnDimension();
    083            entries = new OpenIntToFieldHashMap<T>(other.entries);
    084        }
    085
    086        /**
    087         * Generic copy constructor.
    088         * @param other The instance to copy
    089         */
    090        public SparseFieldMatrix(FieldMatrix<T> other){
    091            super(other.getField(), other.getRowDimension(), other.getColumnDimension());
    092            rows = other.getRowDimension();
    093            columns = other.getColumnDimension();
    094            entries = new OpenIntToFieldHashMap<T>(getField());
    095            for (int i = 0; i < rows; i++) {
    096                for (int j = 0; j < columns; j++) {
    097                    setEntry(i, j, other.getEntry(i, j));
    098                }
    099            }
    100        }
    101
    102        /** {@inheritDoc} */
    103        @Override
    104        public void addToEntry(int row, int column, T increment)
    105                throws MatrixIndexException {
    106            checkRowIndex(row);
    107            checkColumnIndex(column);
    108            final int key = computeKey(row, column);
    109            final T value = entries.get(key).add(increment);
    110            if (getField().getZero().equals(value)) {
    111                entries.remove(key);
    112            } else {
    113                entries.put(key, value);
    114            }
    115
    116        }
    117
    118        /** {@inheritDoc} */
    119        @Override
    120        public FieldMatrix<T> copy() {
    121            return new SparseFieldMatrix<T>(this);
    122        }
    123
    124        /** {@inheritDoc} */
    125        @Override
    126        public FieldMatrix<T> createMatrix(int rowDimension, int columnDimension)
    127                throws IllegalArgumentException {
    128            return new SparseFieldMatrix<T>(getField(), rowDimension, columnDimension);
    129        }
    130
    131        /** {@inheritDoc} */
    132        @Override
    133        public int getColumnDimension() {
    134            return columns;
    135        }
    136
    137        /** {@inheritDoc} */
    138        @Override
    139        public T getEntry(int row, int column) throws MatrixIndexException {
    140            checkRowIndex(row);
    141            checkColumnIndex(column);
    142            return entries.get(computeKey(row, column));
    143        }
    144
    145        /** {@inheritDoc} */
    146        @Override
    147        public int getRowDimension() {
    148            return rows;
    149        }
    150
    151        /** {@inheritDoc} */
    152        @Override
    153        public void multiplyEntry(int row, int column, T factor)
    154                throws MatrixIndexException {
    155            checkRowIndex(row);
    156            checkColumnIndex(column);
    157            final int key = computeKey(row, column);
    158            final T value = entries.get(key).multiply(factor);
    159            if (getField().getZero().equals(value)) {
    160                entries.remove(key);
    161            } else {
    162                entries.put(key, value);
    163            }
    164
    165        }
    166
    167        /** {@inheritDoc} */
    168        @Override
    169        public void setEntry(int row, int column, T value)
    170                throws MatrixIndexException {
    171            checkRowIndex(row);
    172            checkColumnIndex(column);
    173            if (getField().getZero().equals(value)) {
    174                entries.remove(computeKey(row, column));
    175            } else {
    176                entries.put(computeKey(row, column), value);
    177            }
    178
    179        }
    180        /**
    181         * Compute the key to access a matrix element
    182         * @param row row index of the matrix element
    183         * @param column column index of the matrix element
    184         * @return key within the map to access the matrix element
    185         */
    186        private int computeKey(int row, int column) {
    187            return row * columns + column;
    188        }
    189
    190    }