001: /*
002: * JScience - Java(TM) Tools and Libraries for the Advancement of Sciences.
003: * Copyright (C) 2007 - JScience (http://jscience.org/)
004: * All rights reserved.
005: *
006: * Permission to use, copy, modify, and distribute this software is
007: * freely granted, provided that this notice is preserved.
008: */
009: package org.jscience.mathematics.vector;
010:
011: import java.util.Map;
012:
013: import javolution.context.ObjectFactory;
014: import javolution.util.FastComparator;
015: import javolution.util.FastMap;
016: import javolution.util.Index;
017: import javolution.xml.XMLFormat;
018: import javolution.xml.stream.XMLStreamException;
019:
020: import org.jscience.mathematics.structure.Field;
021:
022: /**
023: * <p> This class represents a sparse vector.</p>
024: * <p> Sparse vectors can be created using an index-to-element mapping or
025: * by adding single elements sparse vectors together.</p>
026: *
027: * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
028: * @version 3.3, January 2, 2007
029: */
030: public final class SparseVector<F extends Field<F>> extends Vector<F> {
031:
032: /**
033: * Holds the default XML representation for sparse vectors.
034: * For example:[code]
035: * <SparseVector dimension="16">
036: * <Zero class="Complex" real="0.0" imaginary="0.0" />
037: * <Elements>
038: * <Index value="4" />
039: * <Complex real="1.0" imaginary="0.0" />
040: * <Index value="6" />
041: * <Complex real="0.0" imaginary="1.0" />
042: * </Elements>
043: * </SparseVector>[/code]
044: */
045: protected static final XMLFormat<SparseVector> XML = new XMLFormat<SparseVector>(
046: SparseVector.class) {
047:
048: @Override
049: public SparseVector newInstance(Class<SparseVector> cls,
050: InputElement xml) throws XMLStreamException {
051: return FACTORY.object();
052: }
053:
054: @SuppressWarnings("unchecked")
055: @Override
056: public void read(InputElement xml, SparseVector V)
057: throws XMLStreamException {
058: V._dimension = xml.getAttribute("dimension", 0);
059: V._zero = xml.get("Zero");
060: V._elements.putAll(xml.get("Elements", FastMap.class));
061: }
062:
063: @Override
064: public void write(SparseVector V, OutputElement xml)
065: throws XMLStreamException {
066: xml.setAttribute("dimension", V._dimension);
067: xml.add(V._zero, "Zero");
068: xml.add(V._elements, "Elements", FastMap.class);
069: }
070: };
071:
072: /**
073: * Holds this vector dimension.
074: */
075: int _dimension;
076:
077: /**
078: * Holds zero.
079: */
080: F _zero;
081:
082: /**
083: * Holds the index to element mapping.
084: */
085: final FastMap<Index, F> _elements = new FastMap<Index, F>();
086:
087: /**
088: * Returns a sparse vector having a single element at the specified index.
089: *
090: * @param dimension this vector dimension.
091: * @param zero the element representing zero.
092: * @param i the index value of this vector single element.
093: * @param element the element at the specified index.
094: * @return the corresponding vector.
095: */
096: public static <F extends Field<F>> SparseVector<F> valueOf(
097: int dimension, F zero, int i, F element) {
098: SparseVector<F> V = SparseVector.newInstance(dimension, zero);
099: V._elements.put(Index.valueOf(i), element);
100: return V;
101: }
102:
103: /**
104: * Returns a sparse vector from the specified index to element mapping.
105: *
106: * @param dimension this vector dimension.
107: * @param zero the element representing zero.
108: * @param elements the index to element mapping.
109: * @return the corresponding vector.
110: */
111: public static <F extends Field<F>> SparseVector<F> valueOf(
112: int dimension, F zero, Map<Index, F> elements) {
113: SparseVector<F> V = SparseVector.newInstance(dimension, zero);
114: V._elements.putAll(elements);
115: return V;
116: }
117:
118: /**
119: * Returns a sparse vector equivalent to the specified vector but with
120: * the zero elements removed removed using a default object equality
121: * comparator.
122: *
123: * @param that the vector to convert.
124: * @param zero the zero element for the sparse vector to return.
125: * @return <code>SparseVector.valueOf(that, zero, FastComparator.DEFAULT)</code>
126: */
127: public static <F extends Field<F>> SparseVector<F> valueOf(
128: Vector<F> that, F zero) {
129: return SparseVector.valueOf(that, zero, FastComparator.DEFAULT);
130: }
131:
132: /**
133: * Returns a sparse vector equivalent to the specified vector but with
134: * the zero elements removed using the specified object equality comparator.
135: * This method can be used to clean up sparse vectors (to remove elements
136: * close to zero).
137: *
138: * @param that the vector to convert.
139: * @param zero the zero element for the sparse vector to return.
140: * @param comparator the comparator used to determinate zero equality.
141: * @return a sparse vector with zero elements removed.
142: */
143: public static <F extends Field<F>> SparseVector<F> valueOf(
144: Vector<F> that, F zero, FastComparator<? super F> comparator) {
145: if (that instanceof SparseVector)
146: return SparseVector.valueOf((SparseVector<F>) that, zero,
147: comparator);
148: int n = that.getDimension();
149: SparseVector<F> V = SparseVector.newInstance(n, zero);
150: for (int i = 0; i < n; i++) {
151: F element = that.get(i);
152: if (!comparator.areEqual(zero, element)) {
153: V._elements.put(Index.valueOf(i), element);
154: }
155: }
156: return V;
157: }
158:
159: private static <F extends Field<F>> SparseVector<F> valueOf(
160: SparseVector<F> that, F zero,
161: FastComparator<? super F> comparator) {
162: SparseVector<F> V = SparseVector.newInstance(that._dimension,
163: zero);
164: for (FastMap.Entry<Index, F> e = that._elements.head(), n = that._elements
165: .tail(); (e = e.getNext()) != n;) {
166: if (!comparator.areEqual(e.getValue(), zero)) {
167: V._elements.put(e.getKey(), e.getValue());
168: }
169: }
170: return V;
171: }
172:
173: /**
174: * Returns the value of the non-set elements for this sparse vector.
175: *
176: * @return the element corresponding to zero.
177: */
178: public F getZero() {
179: return _zero;
180: }
181:
182: @Override
183: public int getDimension() {
184: return _dimension;
185: }
186:
187: @Override
188: public F get(int i) {
189: if ((i < 0) || (i >= _dimension))
190: throw new IndexOutOfBoundsException();
191: F element = _elements.get(Index.valueOf(i));
192: return (element == null) ? _zero : element;
193: }
194:
195: @Override
196: public SparseVector<F> opposite() {
197: SparseVector<F> V = SparseVector.newInstance(_dimension, _zero);
198: for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements
199: .tail(); (e = e.getNext()) != n;) {
200: V._elements.put(e.getKey(), e.getValue().opposite());
201: }
202: return V;
203: }
204:
205: @Override
206: public SparseVector<F> plus(Vector<F> that) {
207: if (that instanceof SparseVector)
208: return plus((SparseVector<F>) that);
209: return plus(SparseVector.valueOf(that, _zero,
210: FastComparator.DEFAULT));
211: }
212:
213: private SparseVector<F> plus(SparseVector<F> that) {
214: if (this ._dimension != that._dimension)
215: throw new DimensionException();
216: SparseVector<F> V = SparseVector.newInstance(_dimension, _zero);
217: V._elements.putAll(this ._elements);
218: for (FastMap.Entry<Index, F> e = that._elements.head(), n = that._elements
219: .tail(); (e = e.getNext()) != n;) {
220: Index index = e.getKey();
221: FastMap.Entry<Index, F> entry = V._elements.getEntry(index);
222: if (entry == null) {
223: V._elements.put(index, e.getValue());
224: } else {
225: entry.setValue(entry.getValue().plus(e.getValue()));
226: }
227: }
228: return V;
229: }
230:
231: @Override
232: public SparseVector<F> times(F k) {
233: SparseVector<F> V = SparseVector.newInstance(_dimension, _zero);
234: for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements
235: .tail(); (e = e.getNext()) != n;) {
236: V._elements.put(e.getKey(), e.getValue().times(k));
237: }
238: return V;
239: }
240:
241: @Override
242: public F times(Vector<F> that) {
243: if (that.getDimension() != _dimension)
244: throw new DimensionException();
245: F sum = null;
246: for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements
247: .tail(); (e = e.getNext()) != n;) {
248: F f = e.getValue().times(that.get(e.getKey().intValue()));
249: sum = (sum == null) ? f : sum.plus(f);
250: }
251: return (sum != null) ? sum : _zero;
252: }
253:
254: @SuppressWarnings("unchecked")
255: @Override
256: public SparseVector<F> copy() {
257: SparseVector<F> V = SparseVector.newInstance(_dimension,
258: (F) _zero.copy());
259: for (Map.Entry<Index, F> e : _elements.entrySet()) {
260: V._elements.put(e.getKey(), (F) e.getValue().copy());
261: }
262: return V;
263: }
264:
265: ///////////////////////
266: // Factory creation. //
267: ///////////////////////
268:
269: @SuppressWarnings("unchecked")
270: static <F extends Field<F>> SparseVector<F> newInstance(
271: int dimension, F zero) {
272: SparseVector<F> V = FACTORY.object();
273: V._dimension = dimension;
274: V._zero = zero;
275: return V;
276: }
277:
278: private static final ObjectFactory<SparseVector> FACTORY = new ObjectFactory<SparseVector>() {
279: @Override
280: protected SparseVector create() {
281: return new SparseVector();
282: }
283:
284: @Override
285: protected void cleanup(SparseVector vector) {
286: vector._elements.reset();
287: }
288: };
289:
290: private SparseVector() {
291: }
292:
293: private static final long serialVersionUID = 1L;
294:
295: }
|