Source code

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 */
009package org.jscience.mathematics.vector;
010
011import java.util.Map;
012
013import javolution.context.ObjectFactory;
014import javolution.util.FastComparator;
015import javolution.util.FastMap;
016import javolution.util.Index;
017import javolution.xml.XMLFormat;
018import javolution.xml.stream.XMLStreamException;
019
020import 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 */
030public 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, InputElement xml)
050                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(int dimension,
097            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(int dimension,
112            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, comparator);
147        int n = that.getDimension();
148        SparseVector<F> V = SparseVector.newInstance(n, zero);
149        for (int i=0; i < n; i++) {
150            F element = that.get(i);
151            if (!comparator.areEqual(zero, element)) {
152                V._elements.put(Index.valueOf(i), element);
153            }
154        }
155        return V;
156    }
157    private static <F extends Field<F>> SparseVector<F> valueOf(
158            SparseVector<F> that, F zero, FastComparator<? super F> comparator) {
159        SparseVector<F> V = SparseVector.newInstance(that._dimension, zero);
160        for (FastMap.Entry<Index, F> e = that._elements.head(), n = that._elements.tail(); (e = e
161                .getNext()) != n;) {
162            if (!comparator.areEqual(e.getValue(), zero)) {
163                V._elements.put(e.getKey(), e.getValue());
164            }
165        }
166        return V;
167    } 
168
169    /**
170     * Returns the value of the non-set elements for this sparse vector.
171     * 
172     * @return the element corresponding to zero.
173     */
174    public F getZero() {
175        return _zero;
176    }
177
178    @Override
179    public int getDimension() {
180        return _dimension;
181    }
182
183    @Override
184    public F get(int i) {
185        if ((i < 0) || (i >= _dimension))
186            throw new IndexOutOfBoundsException();
187        F element = _elements.get(Index.valueOf(i));
188        return (element == null) ? _zero : element;
189    }
190
191    @Override
192    public SparseVector<F> opposite() {
193        SparseVector<F> V = SparseVector.newInstance(_dimension, _zero);
194        for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements.tail(); (e = e
195                .getNext()) != n;) {
196            V._elements.put(e.getKey(), e.getValue().opposite());
197        }
198        return V;
199    }
200
201    @Override
202    public SparseVector<F> plus(Vector<F> that) {
203        if (that instanceof SparseVector) 
204            return plus((SparseVector<F>) that);
205        return plus(SparseVector.valueOf(that, _zero, FastComparator.DEFAULT));
206    }
207
208    private SparseVector<F> plus(SparseVector<F> that) {
209        if (this._dimension != that._dimension) throw new DimensionException();
210        SparseVector<F> V = SparseVector.newInstance(_dimension, _zero);
211        V._elements.putAll(this._elements);
212        for (FastMap.Entry<Index, F> e = that._elements.head(), n = that._elements.tail();
213                (e = e.getNext()) != n;) {
214            Index index = e.getKey();
215            FastMap.Entry<Index, F> entry = V._elements.getEntry(index);
216            if (entry == null) {
217                V._elements.put(index, e.getValue());
218            } else {
219                entry.setValue(entry.getValue().plus(e.getValue()));
220            }
221        }
222        return V;
223    }
224
225    @Override
226    public SparseVector<F> times(F k) {
227        SparseVector<F> V = SparseVector.newInstance(_dimension, _zero);
228        for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements.tail(); (e = e
229                .getNext()) != n;) {
230            V._elements.put(e.getKey(), e.getValue().times(k));
231        }
232        return V;
233    }
234
235    @Override
236    public F times(Vector<F> that) {
237        if (that.getDimension() != _dimension)
238            throw new DimensionException();
239        F sum = null;
240        for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements.tail(); (e = e
241                .getNext()) != n;) {
242            F f = e.getValue().times(that.get(e.getKey().intValue()));
243            sum = (sum == null) ? f : sum.plus(f);
244        }
245        return (sum != null) ? sum : _zero;
246    }
247
248    @SuppressWarnings("unchecked")
249    @Override
250    public SparseVector<F> copy() {
251        SparseVector<F> V = SparseVector.newInstance(_dimension, (F)_zero.copy());
252        for (Map.Entry<Index, F> e : _elements.entrySet()) {
253            V._elements.put(e.getKey(), (F) e.getValue().copy());            
254        }
255        return V;
256    }
257    
258    ///////////////////////
259    // Factory creation. //
260    ///////////////////////
261
262    @SuppressWarnings("unchecked")
263    static <F extends Field<F>> SparseVector<F> newInstance(int dimension, F zero) {
264        SparseVector<F> V = FACTORY.object();
265        V._dimension = dimension;
266        V._zero = zero;
267        return V;
268    }
269
270    private static final ObjectFactory<SparseVector> FACTORY = new ObjectFactory<SparseVector>() {
271        @Override
272        protected SparseVector create() {
273            return new SparseVector();
274        }
275
276        @Override
277        protected void cleanup(SparseVector vector) {
278            vector._elements.reset();
279        }
280    };
281
282    private SparseVector() {   
283    }
284    
285    private static final long serialVersionUID = 1L;
286
287}