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