content: /* ===========================================================
   * JFreeChart : a free chart library for the Java(tm) platform
   * ===========================================================
   *
   * (C) Copyright 2000-2013, by Object Refinery Limited and Contributors.
   *
   * Project Info:  http://www.jfree.org/jfreechart/index.html
   *
   * This library is free software; you can redistribute it and/or modify it
   * under the terms of the GNU Lesser General Public License as published by
   * the Free Software Foundation; either version 2.1 of the License, or
   * (at your option) any later version.
   *
   * This library is distributed in the hope that it will be useful, but
   * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
   * License for more details.
   *
   * You should have received a copy of the GNU Lesser General Public
   * License along with this library; if not, write to the Free Software
   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
   * USA.
   *
   * [Oracle and Java are registered trademarks of Oracle and/or its affiliates.
   * Other names may be trademarks of their respective owners.]
   *
   * ---------------------
   * XYSplineRenderer.java
   * ---------------------
   * (C) Copyright 2007-2013, by Klaus Rheinwald and Contributors.
   *
   * Original Author:  Klaus Rheinwald;
   * Contributor(s):   Tobias von Petersdorff (tvp@math.umd.edu,
   *                       http://www.wam.umd.edu/~petersd/);
   *                   David Gilbert (for Object Refinery Limited);
   *
   * Changes:
   * --------
   * 25-Jul-2007 : Version 1, contributed by Klaus Rheinwald (DG);
   * 03-Aug-2007 : Added new constructor (KR);
   * 25-Oct-2007 : Prevent duplicate control points (KR);
   * 19-May-2009 : Fixed FindBugs warnings, patch by Michal Wozniak (DG);
   * 17-Jun-2012 : Removed JCommon dependencies (DG);
   *
   */
  
  package org.jfree.chart.renderer.xy;
  
  import java.awt.GradientPaint;
  import java.awt.Graphics2D;
  import java.awt.Paint;
  import java.awt.geom.GeneralPath;
  import java.awt.geom.Point2D;
  import java.awt.geom.Rectangle2D;
  import java.util.ArrayList;
  import java.util.List;
  
  import org.jfree.chart.axis.ValueAxis;
  import org.jfree.chart.ui.RectangleEdge;
  import org.jfree.chart.event.RendererChangeEvent;
  import org.jfree.chart.plot.PlotOrientation;
  import org.jfree.chart.plot.PlotRenderingInfo;
  import org.jfree.chart.plot.XYPlot;
  import org.jfree.chart.ui.GradientPaintTransformer;
  import org.jfree.chart.ui.StandardGradientPaintTransformer;
  import org.jfree.chart.util.ObjectUtilities;
  import org.jfree.chart.util.ParamChecks;
  import org.jfree.data.xy.XYDataset;
  
  /**
   * A renderer that connects data points with natural cubic splines and/or
   * draws shapes at each data point.  This renderer is designed for use with
   * the {@link XYPlot} class. The example shown here is generated by the
   * <code>XYSplineRendererDemo1.java</code> program included in the JFreeChart
   * demo collection:
   * <br><br>
   * <img src="../../../../../images/XYSplineRendererSample.png"
   * alt="XYSplineRendererSample.png" />
   *
   * @since 1.0.7
   */
  public class XYSplineRenderer extends XYLineAndShapeRenderer {
  
      /**
       * An enumeration of the fill types for the renderer.
       * 
       * @since 1.0.17
       */
      public static enum FillType {
          NONE,
          TO_ZERO,
          TO_LOWER_BOUND,
          TO_UPPER_BOUND
      }
  
      /**
       * Represents state information that applies to a single rendering of
       * a chart.
       */
      public static class XYSplineState extends State {
          
          /** The area to fill under the curve. */
          public GeneralPath fillArea;
          
          /** The points. */
          public List<Point2D> points;
          
          /**
           * Creates a new state instance.
           * 
           * @param info  the plot rendering info. 
           */
          public XYSplineState(PlotRenderingInfo info) {
              super(info);
              this.fillArea = new GeneralPath();
              this.points = new ArrayList<Point2D>();
          }
      }
      
      /**
       * Resolution of splines (number of line segments between points)
       */
      private int precision;
  
      /**
       * A flag that can be set to specify 
       * to fill the area under the spline.
       */
      private FillType fillType;
  
      private GradientPaintTransformer gradientPaintTransformer;
      
      /**
       * Creates a new instance with the precision attribute defaulting to 5 
       * and no fill of the area 'under' the spline.
       */
      public XYSplineRenderer() {
          this(5, FillType.NONE);
      }
  
      /**
       * Creates a new renderer with the specified precision 
       * and no fill of the area 'under' (between '0' and) the spline.
       *
       * @param precision  the number of points between data items.
       */
      public XYSplineRenderer(int precision) {
          this(precision, FillType.NONE);
      }
  
      /**
       * Creates a new renderer with the specified precision
       * and specified fill of the area 'under' (between '0' and) the spline.
       *
       * @param precision  the number of points between data items.
       * @param fillType  the type of fill beneath the curve (<code>null</code> 
       *     not permitted).
       * 
       * @since 1.0.17
       */
      public XYSplineRenderer(int precision, FillType fillType) {
          super();
          if (precision <= 0) {
              throw new IllegalArgumentException("Requires precision > 0.");
          }
          ParamChecks.nullNotPermitted(fillType, "fillType");
          this.precision = precision;
          this.fillType = fillType;
          this.gradientPaintTransformer = new StandardGradientPaintTransformer();
      }
  
      /**
       * Returns the resolution of splines.
       *
       * @return Number of line segments between points.
       *
       * @see #setPrecision(int)
       */
      public int getPrecision() {
          return this.precision;
      }
  
      /**
       * Set the resolution of splines and sends a {@link RendererChangeEvent}
       * to all registered listeners.
       *
       * @param p  number of line segments between points (must be > 0).
       *
       * @see #getPrecision()
       */
      public void setPrecision(int p) {
          if (p <= 0) {
              throw new IllegalArgumentException("Requires p > 0.");
          }
          this.precision = p;
          fireChangeEvent();
      }
  
      /**
       * Returns the type of fill that the renderer draws beneath the curve.
       *
       * @return The type of fill (never <code>null</code>).
       *
       * @see #setFillMode(FillType)
       * 
       * @since 1.0.17
       */
      public FillType getFillType() {
          return this.fillType;
      }
  
      /**
       * Set the fill type and sends a {@link RendererChangeEvent}
       * to all registered listeners.
       *
       * @param fillType   the fill type (<code>null</code> not permitted).
       *
       * @see #getFillType()
       * 
       * @since 1.0.17
       */
      public void setFillType(FillType fillType) {
          this.fillType = fillType;
          fireChangeEvent();
      }
  
      /**
       * Returns the gradient paint transformer, or <code>null</code>.
       * 
       * @return The gradient paint transformer (possibly <code>null</code>).
       * 
       * @since 1.0.17
       */
      public GradientPaintTransformer getGradientPaintTransformer() {
          return this.gradientPaintTransformer;
      }
      
      /**
       * Sets the gradient paint transformer and sends a 
       * {@link RendererChangeEvent} to all registered listeners.
       * 
       * @param gpt  the transformer (<code>null</code> permitted).
       * 
       * @since 1.0.17
       */
      public void setGradientPaintTransformer(GradientPaintTransformer gpt) {
          this.gradientPaintTransformer = gpt;
          fireChangeEvent();
      }
      
      /**
       * Initialises the renderer.
       * <P>
       * This method will be called before the first item is rendered, giving the
       * renderer an opportunity to initialise any state information it wants to
       * maintain.  The renderer can do nothing if it chooses.
       *
       * @param g2  the graphics device.
       * @param dataArea  the area inside the axes.
       * @param plot  the plot.
       * @param data  the data.
       * @param info  an optional info collection object to return data back to
       *              the caller.
       *
       * @return The renderer state.
       */
      @Override
      public XYItemRendererState initialise(Graphics2D g2, Rectangle2D dataArea,
              XYPlot plot, XYDataset data, PlotRenderingInfo info) {
  
          setDrawSeriesLineAsPath(true);
          XYSplineState state = new XYSplineState(info);
          state.setProcessVisibleItemsOnly(false);
          return state;
      }
  
      /**
       * Draws the item (first pass). This method draws the lines
       * connecting the items. Instead of drawing separate lines,
       * a GeneralPath is constructed and drawn at the end of
       * the series painting.
       *
       * @param g2  the graphics device.
       * @param state  the renderer state.
       * @param plot  the plot (can be used to obtain standard color information
       *              etc).
       * @param dataset  the dataset.
       * @param pass  the pass.
       * @param series  the series index (zero-based).
       * @param item  the item index (zero-based).
       * @param xAxis  the domain axis.
       * @param yAxis  the range axis.
       * @param dataArea  the area within which the data is being drawn.
       */
      @Override
      protected void drawPrimaryLineAsPath(XYItemRendererState state,
              Graphics2D g2, XYPlot plot, XYDataset dataset, int pass,
              int series, int item, ValueAxis xAxis, ValueAxis yAxis,
              Rectangle2D dataArea) {
  
          XYSplineState s = (XYSplineState) state;
          RectangleEdge xAxisLocation = plot.getDomainAxisEdge();
          RectangleEdge yAxisLocation = plot.getRangeAxisEdge();
  
          // get the data points
          double x1 = dataset.getXValue(series, item);
          double y1 = dataset.getYValue(series, item);
          double transX1 = xAxis.valueToJava2D(x1, dataArea, xAxisLocation);
          double transY1 = yAxis.valueToJava2D(y1, dataArea, yAxisLocation);
  
          // collect points
          if (!Double.isNaN(transX1) && !Double.isNaN(transY1)) {
              Point2D p = plot.getOrientation() == PlotOrientation.HORIZONTAL 
                  ? new Point2D.Float((float) transY1, (float) transX1) 
                  : new Point2D.Float((float) transX1, (float) transY1);
              if (!s.points.contains(p))
                  s.points.add(p);
              }
          
          if (item == dataset.getItemCount(series) - 1) {     // construct path
              if (s.points.size() > 1) {
                  Point2D origin;
                  if (this.fillType == FillType.TO_ZERO) {
                      float xz = (float) xAxis.valueToJava2D(0, dataArea, 
                              yAxisLocation);
                      float yz = (float) yAxis.valueToJava2D(0, dataArea, 
                              yAxisLocation);
                      origin = plot.getOrientation() == PlotOrientation.HORIZONTAL
                              ? new Point2D.Float(yz, xz) 
                              : new Point2D.Float(xz, yz);
                  } else if (this.fillType == FillType.TO_LOWER_BOUND) {
                      float xlb = (float) xAxis.valueToJava2D(
                              xAxis.getLowerBound(), dataArea, xAxisLocation);
                      float ylb = (float) yAxis.valueToJava2D(
                              yAxis.getLowerBound(), dataArea, yAxisLocation);
                      origin = plot.getOrientation() == PlotOrientation.HORIZONTAL
                              ? new Point2D.Float(ylb, xlb) 
                              : new Point2D.Float(xlb, ylb);
                  } else {// fillType == TO_UPPER_BOUND
                      float xub = (float) xAxis.valueToJava2D(
                              xAxis.getUpperBound(), dataArea, xAxisLocation);
                      float yub = (float) yAxis.valueToJava2D(
                              yAxis.getUpperBound(), dataArea, yAxisLocation);
                      origin = plot.getOrientation() == PlotOrientation.HORIZONTAL
                              ? new Point2D.Float(yub, xub)
                              : new Point2D.Float(xub, yub);
          }
                  
                  // we need at least two points to draw something
                  Point2D cp0 = s.points.get(0);
                  s.seriesPath.moveTo(cp0.getX(), cp0.getY());
                  if (this.fillType != FillType.NONE) {
                      if (plot.getOrientation() == PlotOrientation.HORIZONTAL) {
                          s.fillArea.moveTo(origin.getX(), cp0.getY());
                      } else {
                          s.fillArea.moveTo(cp0.getX(), origin.getY());
                      }
                      s.fillArea.lineTo(cp0.getX(), cp0.getY());
                  }
                  if (s.points.size() == 2) {
                      // we need at least 3 points to spline. Draw simple line
                      // for two points
                      Point2D cp1 = s.points.get(1);
                      if (this.fillType != FillType.NONE) {
                          s.fillArea.lineTo(cp1.getX(), cp1.getY());
                          s.fillArea.lineTo(cp1.getX(), origin.getY());
                          s.fillArea.closePath();
                      }
                      s.seriesPath.lineTo(cp1.getX(), cp1.getY());
                  } else {
                      // construct spline
                      int np = s.points.size(); // number of points
                      float[] d = new float[np]; // Newton form coefficients
                      float[] x = new float[np]; // x-coordinates of nodes
                      float y, oldy;
                      float t, oldt;
  
                      float[] a = new float[np];
                      float t1;
                      float t2;
                      float[] h = new float[np];
  
                      for (int i = 0; i < np; i++) {
                          Point2D.Float cpi = (Point2D.Float) s.points.get(i);
                          x[i] = cpi.x;
                          d[i] = cpi.y;
                      }
  
                      for (int i = 1; i <= np - 1; i++)
                          h[i] = x[i] - x[i - 1];
  
                      float[] sub = new float[np - 1];
                      float[] diag = new float[np - 1];
                      float[] sup = new float[np - 1];
  
                      for (int i = 1; i <= np - 2; i++) {
                          diag[i] = (h[i] + h[i + 1]) / 3;
                          sup[i] = h[i + 1] / 6;
                          sub[i] = h[i] / 6;
                          a[i] = (d[i + 1] - d[i]) / h[i + 1]
                                     - (d[i] - d[i - 1]) / h[i];
                      }
                      solveTridiag(sub, diag, sup, a, np - 2);
  
                      // note that a[0]=a[np-1]=0
                      oldt = x[0];
                      oldy = d[0];
                      for (int i = 1; i <= np - 1; i++) {
                          // loop over intervals between nodes
                          for (int j = 1; j <= this.precision; j++) {
                              t1 = (h[i] * j) / this.precision;
                              t2 = h[i] - t1;
                              y = ((-a[i - 1] / 6 * (t2 + h[i]) * t1 + d[i - 1])
                                      * t2 + (-a[i] / 6 * (t1 + h[i]) * t2
                                      + d[i]) * t1) / h[i];
                              t = x[i - 1] + t1;
                              s.seriesPath.lineTo(t, y);
                              if (this.fillType != FillType.NONE) {
                                  s.fillArea.lineTo(t, y);
                              }
                          }
                      }
                  }
                  // Add last point @ y=0 for fillPath and close path
                  if (this.fillType != FillType.NONE) {
                      if (plot.getOrientation() == PlotOrientation.HORIZONTAL) {
                          s.fillArea.lineTo(origin.getX(), s.points.get(
                                  s.points.size() - 1).getY());
                      } else {
                          s.fillArea.lineTo(s.points.get(
                                  s.points.size() - 1).getX(), origin.getY());
                      }
                      s.fillArea.closePath();
                  }
  
                  // fill under the curve...
                  if (this.fillType != FillType.NONE) {
                      Paint fp = getSeriesFillPaint(series);
                      if (this.gradientPaintTransformer != null 
                              && fp instanceof GradientPaint) {
                          GradientPaint gp = this.gradientPaintTransformer
                                  .transform((GradientPaint) fp, s.fillArea);
                          g2.setPaint(gp);
                      } else {
                          g2.setPaint(fp);                        
                      }
                      g2.fill(s.fillArea);
                      s.fillArea.reset();
                  }
                  // then draw the line...
                  drawFirstPassShape(g2, pass, series, item, s.seriesPath);
              }
              // reset points vector
              s.points = new ArrayList<Point2D>();
          }
      }
  
      private void solveTridiag(float[] sub, float[] diag, float[] sup,
              float[] b, int n) {
  /*      solve linear system with tridiagonal n by n matrix a
          using Gaussian elimination *without* pivoting
          where   a(i,i-1) = sub[i]  for 2<=i<=n
          a(i,i)   = diag[i] for 1<=i<=n
          a(i,i+1) = sup[i]  for 1<=i<=n-1
          (the values sub[1], sup[n] are ignored)
          right hand side vector b[1:n] is overwritten with solution
          NOTE: 1...n is used in all arrays, 0 is unused */
          int i;
  /*      factorization and forward substitution */
          for (i = 2; i <= n; i++) {
              sub[i] /= diag[i - 1];
              diag[i] -= sub[i] * sup[i - 1];
              b[i] -= sub[i] * b[i - 1];
          }
          b[n] /= diag[n];
          for (i = n - 1; i >= 1; i--)
              b[i] = (b[i] - sup[i] * b[i + 1]) / diag[i];
      }
  
      /**
       * Tests this renderer for equality with an arbitrary object.
       *
       * @param obj  the object (<code>null</code> permitted).
       *
       * @return A boolean.
       */
      @Override
      public boolean equals(Object obj) {
          if (obj == this) {
              return true;
          }
          if (!(obj instanceof XYSplineRenderer)) {
              return false;
          }
          XYSplineRenderer that = (XYSplineRenderer) obj;
          if (this.precision != that.precision) {
              return false;
          }
          if (this.fillType != that.fillType) {
              return false;
          }
          if (!ObjectUtilities.equal(this.gradientPaintTransformer, 
                  that.gradientPaintTransformer)) {
              return false;
          }
          return super.equals(obj);
      }
  }
  