LinearInterpolator


1   /* ============================================================
2    * JRobin : Pure java implementation of RRDTool's functionality
3    * ============================================================
4    *
5    * Project Info:  http://www.jrobin.org
6    * Project Lead:  Sasa Markovic (saxon@jrobin.org)
7    *
8    * Developers:    Sasa Markovic (saxon@jrobin.org)
9    *                Arne Vandamme (cobralord@jrobin.org)
10   *
11   * (C) Copyright 2003, by Sasa Markovic.
12   *
13   * This library is free software; you can redistribute it and/or modify it under the terms
14   * of the GNU Lesser General Public License as published by the Free Software Foundation;
15   * either version 2.1 of the License, or (at your option) any later version.
16   *
17   * This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
18   * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
19   * See the GNU Lesser General Public License for more details.
20   *
21   * You should have received a copy of the GNU Lesser General Public License along with this
22   * library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
23   * Boston, MA 02111-1307, USA.
24   */
25  package org.jrobin.graph;
26  
27  import org.jrobin.core.RrdException;
28  import org.jrobin.core.Util;
29  import java.util.Date  ;
30  import java.util.GregorianCalendar  ;
31  
32  /**
33   * Class used to interpolate datasource values from the collection of (timestamp, values)
34   * points. This class is suitable for linear interpolation only. <p>
35   *
36   * Interpolation algorithm returns different values based on the value passed to
37   * {@link #setInterpolationMethod(int) setInterpolationMethod()}. If not set, interpolation
38   * method defaults to standard linear interpolation ({@link #INTERPOLATE_LINEAR}).
39   * Interpolation method handles NaN datasource
40   * values gracefully.<p>
41   *
42   * Pass instances of this class to {@link RrdGraphDef#datasource(String, Plottable)
43   * RrdGraphDef.datasource()} to provide interpolated datasource values to JRobin grapher.<p>
44   */
45  public class LinearInterpolator extends Plottable {
46      /** constant used to specify LEFT interpolation.
47       * See {@link #setInterpolationMethod(int) setInterpolationMethod()} for explanation. */
48      public static final int INTERPOLATE_LEFT = 0;
49      /** constant used to specify RIGHT interpolation.
50       * See {@link #setInterpolationMethod(int) setInterpolationMethod()} for explanation. */
51      public static final int INTERPOLATE_RIGHT = 1;
52      /** constant used to specify LINEAR interpolation (default interpolation method).
53       * See {@link #setInterpolationMethod(int) setInterpolationMethod()} for explanation. */
54      public static final int INTERPOLATE_LINEAR = 2;
55      /** constant used to specify LINEAR REGRESSION as interpolation method.
56       * See {@link #setInterpolationMethod(int) setInterpolationMethod()} for explanation. */
57      public static final int INTERPOLATE_REGRESSION = 3;
58  
59      private int lastIndexUsed = 0;
60      private int interpolationMethod = INTERPOLATE_LINEAR;
61  
62      private long[] timestamps;
63      private double[] values;
64  
65      // used only if INTERPOLATE_BESTFIT is specified
66      double b0 = Double.NaN, b1 = Double.NaN;
67  
68      /**
69       * Creates LinearInterpolator from arrays of timestamps and corresponding datasource values.
70       * @param timestamps timestamps in seconds
71       * @param values corresponding datasource values
72       * @throws RrdException Thrown if supplied arrays do not contain at least two values, or if
73       * timestamps are not ordered, or array lengths are not equal.
74       */
75      public LinearInterpolator(long[] timestamps, double[] values) throws RrdException {
76          this.timestamps = timestamps;
77          this.values = values;
78          validate();
79      }
80  
81      /**
82       * Creates LinearInterpolator from arrays of timestamps and corresponding datasource values.
83       * @param dates Array of Date objects
84       * @param values corresponding datasource values
85       * @throws RrdException Thrown if supplied arrays do not contain at least two values, or if
86       * timestamps are not ordered, or array lengths are not equal.
87       */
88      public LinearInterpolator(Date  [] dates, double[] values) throws RrdException {
89          this.values = values;
90          timestamps = new long[dates.length];
91          for(int i = 0; i < dates.length; i++) {
92              timestamps[i] = Util.getTimestamp(dates[i]);
93          }
94          validate();
95      }
96  
97      /**
98       * Creates LinearInterpolator from arrays of timestamps and corresponding datasource values.
99       * @param dates array of GregorianCalendar objects
100      * @param values corresponding datasource values
101      * @throws RrdException Thrown if supplied arrays do not contain at least two values, or if
102      * timestamps are not ordered, or array lengths are not equal.
103      */
104     public LinearInterpolator(GregorianCalendar  [] dates, double[] values) throws RrdException {
105         this.values = values;
106         timestamps = new long[dates.length];
107         for(int i = 0; i < dates.length; i++) {
108             timestamps[i] = Util.getTimestamp(dates[i]);
109         }
110         validate();
111     }
112 
113     private void validate() throws RrdException {
114         boolean ok = true;
115         if(timestamps.length != values.length || timestamps.length < 2) {
116             ok = false;
117         }
118         for(int i = 0; i < timestamps.length - 1 && ok; i++) {
119             if(timestamps[i] >= timestamps[i + 1]) {
120                 ok = false;
121             }
122         }
123         if(!ok) {
124             throw new RrdException("Invalid plottable data supplied");
125         }
126     }
127 
128     /**
129      * Sets interpolation method to be used. Suppose that we have two timestamp/value pairs:<br>
130      * <code>(t, 100)</code> and <code>(t + 100, 300)</code>. Here are the results interpolator
131      * returns for t + 50 seconds, for various <code>interpolationMethods</code>:<p>
132      * <ul>
133      * <li><code>INTERPOLATE_LEFT:   100</code>
134      * <li><code>INTERPOLATE_RIGHT:  300</code>
135      * <li><code>INTERPOLATE_LINEAR: 200</code>
136      * </ul>
137      * If not set, interpolation method defaults to <code>INTERPOLATE_LINEAR</code>.<p>
138      *
139      * The fourth available interpolation method is INTERPOLATE_REGRESSION. This method uses
140      * simple linear regression to interpolate supplied data with a simple straight line which does not
141      * necessarily pass through all data points. The slope of the best-fit line will be chosen so that the
142      * total square distance of real data points from from the best-fit line is at minimum.<p>
143      *
144      * The full explanation of this inteprolation method can be found
145      * <a HREF="http://www.tufts.edu/~gdallal/slr.htm">here</a>.<p>
146      *
147      * @param interpolationMethod Should be <code>INTERPOLATE_LEFT</code>,
148      * <code>INTERPOLATE_RIGHT</code>, <code>INTERPOLATE_LINEAR</code> or
149      * <code>INTERPOLATE_REGRESSION</code>. Any other value will be interpreted as
150      * INTERPOLATE_LINEAR (default).
151      */
152     public void setInterpolationMethod(int interpolationMethod) {
153         switch(interpolationMethod) {
154             case INTERPOLATE_REGRESSION:
155                 calculateBestFitLine();
156             case INTERPOLATE_LEFT:
157             case INTERPOLATE_RIGHT:
158             case INTERPOLATE_LINEAR:
159                 this.interpolationMethod = interpolationMethod;
160                 break;
161             default:
162                 this.interpolationMethod = INTERPOLATE_LINEAR;
163         }
164     }
165 
166     private void calculateBestFitLine() {
167         int count = timestamps.length, validCount = 0;
168         double ts = 0.0, vs = 0.0;
169         for(int i = 0; i < count; i++) {
170             if(!Double.isNaN(values[i])) {
171                 ts += timestamps[i];
172                 vs += values[i];
173                 validCount++;
174             }
175         }
176         if(validCount <= 1) {
177             // just one not-NaN point
178             b0 = b1 = Double.NaN;
179             return;
180         }
181         ts /= validCount;
182         vs /= validCount;
183         double s1 = 0, s2 = 0;
184         for(int i = 0; i < count; i++) {
185             if(!Double.isNaN(values[i])) {
186                 double dt = timestamps[i] - ts;
187                 double dv = values[i] - vs;
188                 s1 += dt * dv;
189                 s2 += dt * dt;
190             }
191         }
192         b1 = s1 / s2;
193         b0 = vs - b1 * ts;
194     }
195 
196     /**
197      * Method overriden from the base class. This method will be called by the framework. Call
198      * this method only if you need interpolated values in your code.
199      * @param timestamp timestamp in seconds
200      * @return inteprolated datasource value
201      */
202     public double getValue(long timestamp) {
203         if(interpolationMethod == INTERPOLATE_REGRESSION) {
204             return b0 + b1 * timestamp;
205         }
206         int count = timestamps.length;
207         // check if out of range
208         if(timestamp < timestamps[0] || timestamp > timestamps[count - 1]) {
209             return Double.NaN;
210         }
211         // find matching segment
212         int startIndex = lastIndexUsed;
213         if(timestamp < timestamps[lastIndexUsed]) {
214             // backward reading, shift to the first timestamp
215             startIndex = 0;
216         }
217         for(int i = startIndex; i < count; i++) {
218             if(timestamps[i] == timestamp) {
219                 return values[i];
220             }
221             if(i < count - 1 && timestamps[i] < timestamp && timestamp < timestamps[i + 1]) {
222                 // matching segment found
223                 lastIndexUsed = i;
224                 switch(interpolationMethod) {
225                     case INTERPOLATE_LEFT:
226                         return values[i];
227                     case INTERPOLATE_RIGHT:
228                         return values[i + 1];
229                     case INTERPOLATE_LINEAR:
230                         double slope = (values[i + 1] - values[i]) /
231                             (timestamps[i + 1] - timestamps[i]);
232                         return values[i] + slope * (timestamp - timestamps[i]);
233                     default:
234                         return Double.NaN;
235                 }
236             }
237         }
238         // should not be here ever, but let's satisfy the compiler
239         return Double.NaN;
240     }
241 }
242
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags