SparseVector


1   /*
2    * JScience - Java(TM) Tools and Libraries for the Advancement of Sciences.
3    * Copyright (C) 2007 - JScience (http://jscience.org/)
4    * All rights reserved.
5    * 
6    * Permission to use, copy, modify, and distribute this software is
7    * freely granted, provided that this notice is preserved.
8    */
9   package org.jscience.mathematics.vectors;
10  
11  import java.util.Map  ;
12  
13  import javolution.util.FastComparator;
14  import javolution.util.FastMap;
15  import javolution.util.Index;
16  import javolution.xml.XMLFormat;
17  import javolution.xml.stream.XMLStreamException;
18  
19  import org.jscience.mathematics.structures.Field;
20  
21  /**
22   * <p> This class represents a sparse vector.</p>
23   * <p> Sparse vectors can be created using an index-to-element mapping or 
24   *     by adding single elements sparse vectors together. For example:[code]
25   *         // Creates a sparse vector of dimension 256 but with only 3 non-zero elements.
26   *         SparseVector<Float64> V = SparseVector.valueOf(256, Float64.ZERO, 127, Float64.valueOf(0.5));
27   *         V = V.plus(SparseVector.valueOf(256, Float64.ZERO, 128, Float64.valueOf(1.0)));
28   *         V = V.plus(SparseVector.valueOf(256, Float64.ZERO, 129, Float64.valueOf(2.0)));
29   *    [/code]</p>
30   *         
31   * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
32   * @version 3.3, January 2, 2007
33   */
34  public final class SparseVector<F extends Field<F>> extends Vector<F> {
35  
36      /**
37       * Holds the default XML representation for sparse vectors.
38       * For example:[code]
39       *    <SparseVector dimension="16">
40       *        <Zero class="Complex" real="0.0" imaginary="0.0" />
41       *        <Elements>
42       *            <Index value="4" />
43       *            <Complex real="1.0" imaginary="0.0" />
44       *            <Index value="6" />
45       *            <Complex real="0.0" imaginary="1.0" />
46       *        </Elements>
47       *    </SparseVector>[/code]
48       */
49      protected static final XMLFormat<SparseVector> XML = new XMLFormat<SparseVector>(
50              SparseVector.class) {
51  
52          @Override  
53          public SparseVector newInstance(Class  <SparseVector> cls, InputElement xml)
54                  throws XMLStreamException {
55              return FACTORY.object();
56          }
57  
58          @SuppressWarnings  ("unchecked")
59          @Override  
60          public void read(InputElement xml, SparseVector V)
61                  throws XMLStreamException {
62              V._dimension = xml.getAttribute("dimension", 0);
63              V._zero = xml.get("Zero");
64              V._elements.putAll(xml.get("Elements", FastMap.class));
65          }
66  
67          @Override  
68          public void write(SparseVector V, OutputElement xml)
69                  throws XMLStreamException {
70              xml.setAttribute("dimension", V._dimension);
71              xml.add(V._zero, "Zero");
72              xml.add(V._elements, "Elements", FastMap.class);
73          }
74      };
75      
76      /**
77       * Holds this vector dimension.
78       */
79      int _dimension;
80  
81      /**
82       * Holds zero.
83       */
84      F _zero;
85  
86      /**
87       * Holds the index to element mapping.
88       */
89      final FastMap<Index, F> _elements = new FastMap<Index, F>();
90  
91      /**
92       * Returns a sparse vector having a single element at the specified index.
93       *
94       * @param dimension this vector dimension.
95       * @param zero the element representing zero.
96       * @param i the index value of this vector single element.
97       * @param element the element at the specified index.
98       * @return the corresponding vector.
99       */
100     public static <F extends Field<F>> SparseVector<F> valueOf(int dimension,
101             F zero, int i, F element) {
102         SparseVector<F> V = SparseVector.newInstance(dimension, zero);
103         V._elements.put(Index.valueOf(i), element);
104         return V;
105     }
106 
107     /**
108      * Returns a sparse vector from the specified index to element mapping.
109      *
110      * @param dimension this vector dimension.
111      * @param zero the element representing zero.
112      * @param elements the index to element mapping.
113      * @return the corresponding vector.
114      */
115     public static <F extends Field<F>> SparseVector<F> valueOf(int dimension,
116             F zero, Map  <Index, F> elements) {
117         SparseVector<F> V = SparseVector.newInstance(dimension, zero);
118         V._elements.putAll(elements);
119         return V;
120     }
121 
122     /**
123      * Returns a sparse vector equivalent to the specified vector but with 
124      * the zero elements removed removed using a default object equality 
125      * comparator.
126      * 
127      * @param that the vector to convert.
128      * @param zero the zero element for the sparse vector to return.
129      * @return <code>SparseVector.valueOf(that, zero, FastComparator.DEFAULT)</code>
130      */
131     public static <F extends Field<F>> SparseVector<F> valueOf(
132             Vector<F> that, F zero) {
133         return SparseVector.valueOf(that, zero, FastComparator.DEFAULT);
134     }
135 
136     /**
137      * Returns a sparse vector equivalent to the specified vector but with 
138      * the zero elements removed using the specified object equality comparator.
139      * This method can be used to clean up sparse vectors (to remove elements
140      * close to zero).
141      * 
142      * @param that the vector to convert.
143      * @param zero the zero element for the sparse vector to return.
144      * @param comparator the comparator used to determinate zero equality. 
145      * @return a sparse vector with zero elements removed.
146      */
147     public static <F extends Field<F>> SparseVector<F> valueOf(
148             Vector<F> that, F zero, FastComparator<? super F> comparator) {
149         if (that instanceof SparseVector) 
150             return SparseVector.valueOf((SparseVector<F>) that, zero, comparator);
151         int n = that.getDimension();
152         SparseVector<F> V = SparseVector.newInstance(n, zero);
153         for (int i=0; i < n; i++) {
154             F element = that.get(i);
155             if (!comparator.areEqual(zero, element)) {
156                 V._elements.put(Index.valueOf(i), element);
157             }
158         }
159         return V;
160     }
161     private static <F extends Field<F>> SparseVector<F> valueOf(
162             SparseVector<F> that, F zero, FastComparator<? super F> comparator) {
163         SparseVector<F> V = SparseVector.newInstance(that._dimension, zero);
164         for (FastMap.Entry<Index, F> e = that._elements.head(), n = that._elements.tail(); (e = e
165                 .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.tail(); (e = e
199                 .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, FastComparator.DEFAULT));
210     }
211 
212     private SparseVector<F> plus(SparseVector<F> that) {
213         if (this._dimension != that._dimension) throw new DimensionException();
214         SparseVector<F> V = SparseVector.newInstance(_dimension, _zero);
215         V._elements.putAll(this._elements);
216         for (FastMap.Entry<Index, F> e = that._elements.head(), n = that._elements.tail();
217                 (e = e.getNext()) != n;) {
218             Index index = e.getKey();
219             FastMap.Entry<Index, F> entry = V._elements.getEntry(index);
220             if (entry == null) {
221                 V._elements.put(index, e.getValue());
222             } else {
223                 entry.setValue(entry.getValue().plus(e.getValue()));
224             }
225         }
226         return V;
227     }
228 
229     @Override  
230     public SparseVector<F> times(F k) {
231         SparseVector<F> V = SparseVector.newInstance(_dimension, _zero);
232         for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements.tail(); (e = e
233                 .getNext()) != n;) {
234             V._elements.put(e.getKey(), e.getValue().times(k));
235         }
236         return V;
237     }
238 
239     @Override  
240     public F times(Vector<F> that) {
241         if (that.getDimension() != _dimension)
242             throw new DimensionException();
243         F sum = null;
244         for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements.tail(); (e = e
245                 .getNext()) != n;) {
246             F f = e.getValue().times(that.get(e.getKey().intValue()));
247             sum = (sum == null) ? f : sum.plus(f);
248         }
249         return (sum != null) ? sum : _zero;
250     }
251 
252     @Override  
253     public boolean move(ObjectSpace os) {
254         if (super.move(os)) {
255             // The elements map itself is intrinsic (all final members are)
256             // and implicitely moves with this vector.
257             // But it may refer to locally/stack allocated elements which
258             // need to be moved along.
259             for (FastMap.Entry<Index, F> e = _elements.head(), n = _elements.tail(); (e = e
260                     .getNext()) != n;) {
261                 e.getValue().move(os);
262             }
263             _zero.move(os);
264             return true;
265         }
266         return false;
267     }
268     
269     ///////////////////////
270     // Factory creation. //
271     ///////////////////////
272 
273     @SuppressWarnings  ("unchecked")
274     static <F extends Field<F>> SparseVector<F> newInstance(int dimension, F zero) {
275         SparseVector<F> V = FACTORY.object();
276         V._dimension = dimension;
277         V._zero = zero;
278         return V;
279     }
280 
281     private static Factory<SparseVector> FACTORY = new Factory<SparseVector>() {
282         @Override  
283         protected SparseVector create() {
284             return new SparseVector();
285         }
286 
287         @Override  
288         protected void cleanup(SparseVector vector) {
289             vector._elements.reset();
290         }
291     };
292 
293     private SparseVector() {   
294     }
295     
296     private static final long serialVersionUID = 1L;
297 
298 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags