1 /*
2
3 dsh-matrix long-addressable bit and typed object matrix implementations.
4 Copyright (c) 2004-2013 held jointly by the individual authors.
5
6 This library is free software; you can redistribute it and/or modify it
7 under the terms of the GNU Lesser General Public License as published
8 by the Free Software Foundation; either version 3 of the License, or (at
9 your option) any later version.
10
11 This library is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; with out even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
14 License for more details.
15
16 You should have received a copy of the GNU Lesser General Public License
17 along with this library; if not, write to the Free Software Foundation,
18 Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
19
20 > http://www.fsf.org/licensing/licenses/lgpl.html
21 > http://www.opensource.org/licenses/lgpl-license.php
22
23 */
24 package org.dishevelled.matrix.impl;
25
26 import java.io.IOException;
27 import java.io.Serializable;
28 import java.io.ObjectInputStream;
29 import java.io.ObjectOutputStream;
30
31 import java.util.Map;
32 import java.util.HashMap;
33
34 import org.dishevelled.functor.UnaryProcedure;
35
36 import org.dishevelled.matrix.Matrix1D;
37
38 /**
39 * Sparse implementation of Matrix2D based on
40 * a hash map whose keys are <code>Long</code>s.
41 *
42 * <p>The cardinality of this sparse object matrix is limited
43 * by the <code>HashMap</code> underlying this implementation
44 * to something less than <code>Integer.MAX_VALUE</code>. The
45 * addressable size, on the other hand, is limited to
46 * <code>(rows * columns) < Long.MAX_VALUE</code>.</p>
47 *
48 * @param <E> type of this sparse 2D matrix
49 * @author Michael Heuer
50 */
51 public class SparseMatrix2D<E>
52 extends AbstractMatrix2D<E>
53 implements Serializable
54 {
55 /** Map of elements keyed by a <code>Long</code> index. */
56 private Map<Long, E> elements;
57
58 /** Default load factor. */
59 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
60
61
62 /**
63 * Private no-arg constructor, to support serialization.
64 */
65 private SparseMatrix2D()
66 {
67 elements = null;
68 }
69
70 /**
71 * Create a new sparse 2D matrix with the specified number
72 * of rows and columns.
73 *
74 * @param rows rows, must be <code>>= 0</code>
75 * @param columns columns, must be <code>>= 0</code>
76 * @throws IllegalArgumentException if either <code>rows</code>
77 * or <code>columns</code> is negative
78 */
79 public SparseMatrix2D(final long rows, final long columns)
80 {
81 this(rows,
82 columns,
83 (int) Math.min(Integer.MAX_VALUE, ((rows * columns) * DEFAULT_LOAD_FACTOR)),
84 DEFAULT_LOAD_FACTOR);
85 }
86
87 /**
88 * Create a new sparse 2D matrix with the specified number
89 * of rows and columns, initial capacity, and load factor.
90 *
91 * @param rows rows, must be <code>>= 0</code>
92 * @param columns columns, must be <code>>= 0</code>
93 * @param initialCapacity initial capacity, must be <code>>= 0</code>
94 * @param loadFactor load factor, must be <code>> 0</code>
95 */
96 public SparseMatrix2D(final long rows, final long columns, final int initialCapacity, final float loadFactor)
97 {
98 super(rows, columns);
99 elements = new HashMap<Long, E>(initialCapacity, loadFactor);
100 }
101
102 /**
103 * Create a new instance of SparseMatrix2D with the specified
104 * parameters and map of elements. Used exclusively by the
105 * <code>clone()</code> method.
106 *
107 * @param rows rows, must be <code>>= 0</code>
108 * @param columns columns, must be <code>>= 0</code>
109 * @param rowZero row of the first element
110 * @param columnZero column of the first element
111 * @param rowStride number of rows between two elements
112 * @param columnStride number of columns between two elements
113 * @param isView true if this instance is a view
114 * @param elements map of elements
115 */
116 protected SparseMatrix2D(final long rows,
117 final long columns,
118 final long rowZero,
119 final long columnZero,
120 final long rowStride,
121 final long columnStride,
122 final boolean isView,
123 final Map<Long, E> elements)
124 {
125 super(rows, columns,
126 rowZero, columnZero,
127 rowStride, columnStride, isView);
128 this.elements = elements;
129 }
130
131
132 /** {@inheritDoc} */
133 public Object clone()
134 {
135 return new SparseMatrix2D<E>(rows, columns,
136 rowZero, columnZero,
137 rowStride, columnStride,
138 isView, elements);
139 }
140
141 /** {@inheritDoc} */
142 public E getQuick(final long row, final long column)
143 {
144 long index = rowZero + (row * rowStride) + columnZero + (column * columnStride);
145 return elements.get(index);
146 }
147
148 /** {@inheritDoc} */
149 public void setQuick(final long row, final long column, final E e)
150 {
151 long index = rowZero + (row * rowStride) + columnZero + (column * columnStride);
152 if (e == null)
153 {
154 elements.remove(index);
155 }
156 else
157 {
158 elements.put(index, e);
159 }
160 }
161
162 /**
163 * {@inheritDoc}
164 *
165 * Overridden for performance.
166 */
167 public void clear()
168 {
169 if (isView)
170 {
171 super.clear();
172 }
173 else
174 {
175 elements.clear();
176 }
177 }
178
179 /**
180 * {@inheritDoc}
181 *
182 * Overridden for performance.
183 */
184 public void forEachNonNull(final UnaryProcedure<? super E> procedure)
185 {
186 if (isView)
187 {
188 super.forEachNonNull(procedure);
189 }
190 else
191 {
192 if (procedure == null)
193 {
194 throw new IllegalArgumentException("procedure must not be null");
195 }
196
197 for (E e : elements.values())
198 {
199 procedure.run(e);
200 }
201 }
202 }
203
204 /** {@inheritDoc} */
205 public Matrix1D<E> viewRow(final long row)
206 {
207 if (row < 0)
208 {
209 throw new IndexOutOfBoundsException(row + " < 0");
210 }
211 if (row >= rows)
212 {
213 throw new IndexOutOfBoundsException(row + " >= " + rows);
214 }
215 return new RowView(row);
216 }
217
218 /** {@inheritDoc} */
219 public Matrix1D<E> viewColumn(final long column)
220 {
221 if (column < 0)
222 {
223 throw new IndexOutOfBoundsException(column + " < 0");
224 }
225 if (column >= columns)
226 {
227 throw new IndexOutOfBoundsException(column + " >= " + columns);
228 }
229 return new ColumnView(column);
230 }
231
232 /**
233 * Return a reference to the map backing this sparse 2D matrix.
234 *
235 * @return a reference to the map backing this sparse 2D matrix
236 */
237 protected Map<Long, E> elements()
238 {
239 return elements;
240 }
241
242 /**
243 * Write this 2D matrix to the specified object output stream.
244 *
245 * @see java.io.ObjectOutputStream
246 * @param out object output stream
247 * @throws IOException if an IO error occurs
248 */
249 private void writeObject(final ObjectOutputStream out)
250 throws IOException
251 {
252 out.writeLong(rows);
253 out.writeLong(columns);
254 out.writeLong(rowZero);
255 out.writeLong(columnZero);
256 out.writeLong(rowStride);
257 out.writeLong(columnStride);
258 out.writeBoolean(isView);
259 out.writeObject(elements);
260 }
261
262 /**
263 * Read this 2D matrix in from the specified object input stream.
264 *
265 * @see java.io.ObjectInputStream
266 * @param in object input stream
267 * @throws IOException if an IO error occurs
268 * @throws ClassNotFoundException if a classloading error occurs
269 */
270 private void readObject(final ObjectInputStream in)
271 throws IOException, ClassNotFoundException
272 {
273 super.rows = in.readLong();
274 super.columns = in.readLong();
275 super.rowZero = in.readLong();
276 super.columnZero = in.readLong();
277 super.rowStride = in.readLong();
278 super.columnStride = in.readLong();
279 super.isView = in.readBoolean();
280 this.elements = (Map<Long, E>) in.readObject();
281 }
282
283 /** {@inheritDoc} */
284 public String toString()
285 {
286 StringBuffer sb = new StringBuffer(super.toString());
287 sb.append("\n rows=");
288 sb.append(rows);
289 sb.append(" columns=");
290 sb.append(columns);
291 sb.append(" rowZero=");
292 sb.append(rowZero);
293 sb.append(" columnZero=");
294 sb.append(columnZero);
295 sb.append(" rowStride=");
296 sb.append(rowStride);
297 sb.append(" columnStride=");
298 sb.append(columnStride);
299 sb.append("\n elements=");
300 sb.append(elements.toString());
301 sb.append("\n");
302 return sb.toString();
303 }
304
305 /**
306 * Row view.
307 */
308 private class RowView
309 extends SparseMatrix1D<E>
310 {
311
312 /**
313 * Create a new row view for the specified row.
314 *
315 * @param row row
316 */
317 RowView(final long row)
318 {
319 super(SparseMatrix2D.this.columns,
320 SparseMatrix2D.this.rowZero
321 + (row * SparseMatrix2D.this.rowStride)
322 + SparseMatrix2D.this.columnZero,
323 SparseMatrix2D.this.columnStride,
324 true,
325 elements);
326 }
327 }
328
329 /**
330 * Column view.
331 */
332 private class ColumnView
333 extends SparseMatrix1D<E>
334 {
335
336 /**
337 * Create a new column view for the specified column.
338 *
339 * @param column column
340 */
341 ColumnView(final long column)
342 {
343 super(SparseMatrix2D.this.rows,
344 SparseMatrix2D.this.rowZero
345 + (column * SparseMatrix2D.this.columnStride)
346 + SparseMatrix2D.this.columnZero,
347 SparseMatrix2D.this.rowStride,
348 true,
349 elements);
350 }
351 }
352 }