View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.linear;
18  
19  import org.apache.commons.math.Field;
20  import org.apache.commons.math.FieldElement;
21  import org.apache.commons.math.util.OpenIntToFieldHashMap;
22  
23  /**
24   * Sparse matrix implementation based on an open addressed map.
25   * 
26   * @param <T> the type of the field elements
27   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
28   * @since 2.0
29   */
30  public class SparseFieldMatrix<T extends FieldElement<T>> extends AbstractFieldMatrix<T> {
31      /**
32       *  Serial id
33       */
34      private static final long serialVersionUID = 9078068119297757342L;
35      /** Storage for (sparse) matrix elements. */
36      private final OpenIntToFieldHashMap<T> entries;
37      /**
38       * row dimension
39       */
40      private final int rowDimension;
41      /**
42       * column dimension
43       */
44      private final int columnDimension;
45      
46  
47      /**
48       * Creates a matrix with no data.
49       * @param field field to which the elements belong
50       */
51      public SparseFieldMatrix(final Field<T> field) {
52          super(field);
53          rowDimension = 0;
54          columnDimension= 0;
55          entries = new OpenIntToFieldHashMap<T>(field);
56      }
57  
58      /**
59       * Create a new SparseFieldMatrix<T> with the supplied row and column dimensions.
60       *
61       * @param field field to which the elements belong
62       * @param rowDimension  the number of rows in the new matrix
63       * @param columnDimension  the number of columns in the new matrix
64       * @throws IllegalArgumentException if row or column dimension is not positive
65       */
66      public SparseFieldMatrix(final Field<T> field,
67                               final int rowDimension, final int columnDimension)
68          throws IllegalArgumentException {
69          super(field, rowDimension, columnDimension);
70          this.rowDimension = rowDimension;
71          this.columnDimension = columnDimension;
72          entries = new OpenIntToFieldHashMap<T>(field);
73      }
74      
75      /**
76       * Copy constructor.
77       * @param other The instance to copy
78       */
79      public SparseFieldMatrix(SparseFieldMatrix<T> other) {
80          super(other.getField(), other.getRowDimension(), other.getColumnDimension());
81          rowDimension = other.getRowDimension();
82          columnDimension = other.getColumnDimension();
83          entries = new OpenIntToFieldHashMap<T>(other.entries);
84      }
85  
86      /**
87       * Generic copy constructor.
88       * @param other The instance to copy
89       */
90      public SparseFieldMatrix(FieldMatrix<T> other){
91          super(other.getField(), other.getRowDimension(), other.getColumnDimension());
92          rowDimension = other.getRowDimension();
93          columnDimension = other.getColumnDimension();
94          entries = new OpenIntToFieldHashMap<T>(getField());
95          for (int i = 0; i < rowDimension; i++) {
96              for (int j = 0; j < columnDimension; j++) {
97                  setEntry(i, j, other.getEntry(i, j));
98              }
99          }
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 }