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 *
10 *
11 * (C) Copyright 2003-2005, 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.data;
26
27 import org.jrobin.core.RrdException;
28 import org.jrobin.core.Util;
29
30 import java.util.Calendar;
31 import java.util.Date;
32
33 /**
34 * Class used to interpolate datasource values from the collection of (timestamp, values)
35 * points using natural cubic spline interpolation.<p>
36 * <p/>
37 * <b>WARNING</b>: So far, this class cannot handle NaN datasource values
38 * (an exception will be thrown by the constructor). Future releases might change this.
39 */
40 public class CubicSplineInterpolator extends Plottable {
41 private double[] x;
42 private double[] y;
43
44 // second derivates come here
45 private double[] y2;
46
47 // internal spline variables
48 private int n, klo, khi;
49
50 /**
51 * Creates cubic spline interpolator from arrays of timestamps and corresponding
52 * datasource values.
53 *
54 * @param timestamps timestamps in seconds
55 * @param values corresponding datasource values
56 * @throws RrdException Thrown if supplied arrays do not contain at least 3 values, or if
57 * timestamps are not ordered, or array lengths are not equal, or some datasource value is NaN.
58 */
59 public CubicSplineInterpolator(long[] timestamps, double[] values) throws RrdException {
60 this.x = new double[timestamps.length];
61 for (int i = 0; i < timestamps.length; i++) {
62 this.x[i] = timestamps[i];
63 }
64 this.y = values;
65 validate();
66 spline();
67 }
68
69 /**
70 * Creates cubic spline interpolator from arrays of Date objects and corresponding
71 * datasource values.
72 *
73 * @param dates Array of Date objects
74 * @param values corresponding datasource values
75 * @throws RrdException Thrown if supplied arrays do not contain at least 3 values, or if
76 * timestamps are not ordered, or array lengths are not equal, or some datasource value is NaN.
77 */
78 public CubicSplineInterpolator(Date[] dates, double[] values) throws RrdException {
79 this.x = new double[dates.length];
80 for (int i = 0; i < dates.length; i++) {
81 this.x[i] = Util.getTimestamp(dates[i]);
82 }
83 this.y = values;
84 validate();
85 spline();
86 }
87
88 /**
89 * Creates cubic spline interpolator from arrays of GregorianCalendar objects and corresponding
90 * datasource values.
91 *
92 * @param dates Array of GregorianCalendar objects
93 * @param values corresponding datasource values
94 * @throws RrdException Thrown if supplied arrays do not contain at least 3 values, or if
95 * timestamps are not ordered, or array lengths are not equal, or some datasource value is NaN.
96 */
97 public CubicSplineInterpolator(Calendar[] dates, double[] values) throws RrdException {
98 this.x = new double[dates.length];
99 for (int i = 0; i < dates.length; i++) {
100 this.x[i] = Util.getTimestamp(dates[i]);
101 }
102 this.y = values;
103 validate();
104 spline();
105 }
106
107 /**
108 * Creates cubic spline interpolator for an array of 2D-points.
109 *
110 * @param x x-axis point coordinates
111 * @param y y-axis point coordinates
112 * @throws RrdException Thrown if supplied arrays do not contain at least 3 values, or if
113 * timestamps are not ordered, or array lengths are not equal, or some datasource value is NaN.
114 */
115 public CubicSplineInterpolator(double[] x, double[] y) throws RrdException {
116 this.x = x;
117 this.y = y;
118 validate();
119 spline();
120 }
121
122 private void validate() throws RrdException {
123 boolean ok = true;
124 if (x.length != y.length || x.length < 3) {
125 ok = false;
126 }
127 for (int i = 0; i < x.length - 1 && ok; i++) {
128 if (x[i] >= x[i + 1] || Double.isNaN(y[i])) {
129 ok = false;
130 }
131 }
132 if (!ok) {
133 throw new RrdException("Invalid plottable data supplied");
134 }
135 }
136
137 private void spline() {
138 n = x.length;
139 y2 = new double[n];
140 double[] u = new double[n - 1];
141 y2[0] = y2[n - 1] = 0.0;
142 u[0] = 0.0; // natural spline
143 for (int i = 1; i <= n - 2; i++) {
144 double sig = (x[i] - x[i - 1]) / (x[i + 1] - x[i - 1]);
145 double p = sig * y2[i - 1] + 2.0;
146 y2[i] = (sig - 1.0) / p;
147 u[i] = (y[i + 1] - y[i]) / (x[i + 1] - x[i]) - (y[i] - y[i - 1]) / (x[i] - x[i - 1]);
148 u[i] = (6.0 * u[i] / (x[i + 1] - x[i - 1]) - sig * u[i - 1]) / p;
149 }
150 for (int k = n - 2; k >= 0; k--) {
151 y2[k] = y2[k] * y2[k + 1] + u[k];
152 }
153 // prepare everything for getValue()
154 klo = 0;
155 khi = n - 1;
156 }
157
158 /**
159 * Calculates spline-interpolated y-value for the corresponding x-value. Call
160 * this if you need spline-interpolated values in your code.
161 *
162 * @param xval x-value
163 * @return inteprolated y-value
164 */
165 public double getValue(double xval) {
166 if (xval < x[0] || xval > x[n - 1]) {
167 return Double.NaN;
168 }
169 if (xval < x[klo] || xval > x[khi]) {
170 // out of bounds
171 klo = 0;
172 khi = n - 1;
173 }
174 while (khi - klo > 1) {
175 // find bounding interval using bisection method
176 int k = (khi + klo) / 2;
177 if (x[k] > xval) {
178 khi = k;
179 }
180 else {
181 klo = k;
182 }
183 }
184 double h = x[khi] - x[klo];
185 double a = (x[khi] - xval) / h;
186 double b = (xval - x[klo]) / h;
187 return a * y[klo] + b * y[khi] +
188 ((a * a * a - a) * y2[klo] + (b * b * b - b) * y2[khi]) * (h * h) / 6.0;
189 }
190
191 /**
192 * Method overriden from the base class. This method will be called by the framework. Call
193 * this method only if you need spline-interpolated values in your code.
194 *
195 * @param timestamp timestamp in seconds
196 * @return inteprolated datasource value
197 */
198 public double getValue(long timestamp) {
199 return getValue((double) timestamp);
200 }
201
202 }