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: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 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 rowDimension; 041 /** 042 * column dimension 043 */ 044 private final int columnDimension; 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 rowDimension = 0; 054 columnDimension= 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.rowDimension = rowDimension; 071 this.columnDimension = 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 rowDimension = other.getRowDimension(); 082 columnDimension = 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 rowDimension = other.getRowDimension(); 093 columnDimension = other.getColumnDimension(); 094 entries = new OpenIntToFieldHashMap<T>(getField()); 095 for (int i = 0; i < rowDimension; i++) { 096 for (int j = 0; j < columnDimension; 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 columnDimension; 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 rowDimension; 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 * columnDimension + column; 188 } 189 190 }