001/* ===========================================================
002 * JFreeChart : a free chart library for the Java(tm) platform
003 * ===========================================================
004 *
005 * (C) Copyright 2000-2013, by Object Refinery Limited and Contributors.
006 *
007 * Project Info:  http://www.jfree.org/jfreechart/index.html
008 *
009 * This library is free software; you can redistribute it and/or modify it
010 * under the terms of the GNU Lesser General Public License as published by
011 * the Free Software Foundation; either version 2.1 of the License, or
012 * (at your option) any later version.
013 *
014 * This library is distributed in the hope that it will be useful, but
015 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
016 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
017 * License for more details.
018 *
019 * You should have received a copy of the GNU Lesser General Public
020 * License along with this library; if not, write to the Free Software
021 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
022 * USA.
023 *
024 * [Oracle and Java are registered trademarks of Oracle and/or its affiliates. 
025 * Other names may be trademarks of their respective owners.]
026 *
027 * ----------------------
028 * RendererUtilities.java
029 * ----------------------
030 * (C) Copyright 2007-2013, by Object Refinery Limited.
031 *
032 * Original Author:  David Gilbert (for Object Refinery Limited);
033 * Contributor(s):   -;
034 *
035 * Changes
036 * -------
037 * 19-Apr-2007 : Version 1 (DG);
038 * 27-Mar-2009 : Fixed results for unsorted datasets (DG);
039 * 19-May-2009 : Fixed FindBugs warnings, patch by Michal Wozniak (DG);
040 * 23-Aug-2012 : Fixed rendering anomaly bug 3561093 (DG);
041 * 03-Jul-2013 : Use ParamChecks (DG);
042 *
043 */
044
045package org.jfree.chart.renderer;
046
047import org.jfree.chart.util.ParamChecks;
048import org.jfree.data.DomainOrder;
049import org.jfree.data.xy.XYDataset;
050
051/**
052 * Utility methods related to the rendering process.
053 *
054 * @since 1.0.6
055 */
056public class RendererUtilities {
057
058    /**
059     * Finds the lower index of the range of live items in the specified data
060     * series.
061     *
062     * @param dataset  the dataset (<code>null</code> not permitted).
063     * @param series  the series index.
064     * @param xLow  the lowest x-value in the live range.
065     * @param xHigh  the highest x-value in the live range.
066     *
067     * @return The index of the required item.
068     *
069     * @since 1.0.6
070     *
071     * @see #findLiveItemsUpperBound(XYDataset, int, double, double)
072     */
073    public static int findLiveItemsLowerBound(XYDataset dataset, int series,
074            double xLow, double xHigh) {
075        ParamChecks.nullNotPermitted(dataset, "dataset");
076        if (xLow >= xHigh) {
077            throw new IllegalArgumentException("Requires xLow < xHigh.");
078        }
079        int itemCount = dataset.getItemCount(series);
080        if (itemCount <= 1) {
081            return 0;
082        }
083        if (dataset.getDomainOrder() == DomainOrder.ASCENDING) {
084            // for data in ascending order by x-value, we are (broadly) looking
085            // for the index of the highest x-value that is less than xLow
086            int low = 0;
087            int high = itemCount - 1;
088            double lowValue = dataset.getXValue(series, low);
089            if (lowValue >= xLow) {
090                // special case where the lowest x-value is >= xLow
091                return low;
092            }
093            double highValue = dataset.getXValue(series, high);
094            if (highValue < xLow) {
095                // special case where the highest x-value is < xLow
096                return high;
097            }
098            while (high - low > 1) {
099                int mid = (low + high) / 2;
100                double midV = dataset.getXValue(series, mid);
101                if (midV >= xLow) {
102                    high = mid;
103                }
104                else {
105                    low = mid;
106                }
107            }
108            return high;
109        }
110        else if (dataset.getDomainOrder() == DomainOrder.DESCENDING) {
111            // when the x-values are sorted in descending order, the lower
112            // bound is found by calculating relative to the xHigh value
113            int low = 0;
114            int high = itemCount - 1;
115            double lowValue = dataset.getXValue(series, low);
116            if (lowValue <= xHigh) {
117                return low;
118            }
119            double highValue = dataset.getXValue(series, high);
120            if (highValue > xHigh) {
121                return high;
122            }
123            while (high - low > 1) {
124                int mid = (low + high) / 2;
125                double midV = dataset.getXValue(series, mid);
126                if (midV > xHigh) {
127                    low = mid;
128                }
129                else {
130                    high = mid;
131                }
132            }
133            return high;
134        }
135        else {
136            // we don't know anything about the ordering of the x-values,
137            // but we can still skip any initial values that fall outside the
138            // range...
139            int index = 0;
140            // skip any items that don't need including...
141            double x = dataset.getXValue(series, index);
142            while (index < itemCount && x < xLow) {
143                index++;
144                if (index < itemCount) {
145                    x = dataset.getXValue(series, index);
146                }
147            }
148            return Math.min(Math.max(0, index), itemCount - 1);
149        }
150    }
151
152    /**
153     * Finds the upper index of the range of live items in the specified data
154     * series.
155     *
156     * @param dataset  the dataset (<code>null</code> not permitted).
157     * @param series  the series index.
158     * @param xLow  the lowest x-value in the live range.
159     * @param xHigh  the highest x-value in the live range.
160     *
161     * @return The index of the required item.
162     *
163     * @since 1.0.6
164     *
165     * @see #findLiveItemsLowerBound(XYDataset, int, double, double)
166     */
167    public static int findLiveItemsUpperBound(XYDataset dataset, int series,
168            double xLow, double xHigh) {
169        ParamChecks.nullNotPermitted(dataset, "dataset");
170        if (xLow >= xHigh) {
171            throw new IllegalArgumentException("Requires xLow < xHigh.");
172        }
173        int itemCount = dataset.getItemCount(series);
174        if (itemCount <= 1) {
175            return 0;
176        }
177        if (dataset.getDomainOrder() == DomainOrder.ASCENDING) {
178            int low = 0;
179            int high = itemCount - 1;
180            double lowValue = dataset.getXValue(series, low);
181            if (lowValue > xHigh) {
182                return low;
183            }
184            double highValue = dataset.getXValue(series, high);
185            if (highValue <= xHigh) {
186                return high;
187            }
188            int mid = (low + high) / 2;
189            while (high - low > 1) {
190                double midV = dataset.getXValue(series, mid);
191                if (midV <= xHigh) {
192                    low = mid;
193                }
194                else {
195                    high = mid;
196                }
197                mid = (low + high) / 2;
198            }
199            return mid;
200        }
201        else if (dataset.getDomainOrder() == DomainOrder.DESCENDING) {
202            // when the x-values are descending, the upper bound is found by
203            // comparing against xLow
204            int low = 0;
205            int high = itemCount - 1;
206            int mid = (low + high) / 2;
207            double lowValue = dataset.getXValue(series, low);
208            if (lowValue < xLow) {
209                return low;
210            }
211            double highValue = dataset.getXValue(series, high);
212            if (highValue >= xLow) {
213                return high;
214            }
215            while (high - low > 1) {
216                double midV = dataset.getXValue(series, mid);
217                if (midV >= xLow) {
218                    low = mid;
219                }
220                else {
221                    high = mid;
222                }
223                mid = (low + high) / 2;
224            }
225            return mid;
226        }
227        else {
228            // we don't know anything about the ordering of the x-values,
229            // but we can still skip any trailing values that fall outside the
230            // range...
231            int index = itemCount - 1;
232            // skip any items that don't need including...
233            double x = dataset.getXValue(series, index);
234            while (index >= 0 && x > xHigh) {
235                index--;
236                if (index >= 0) {
237                    x = dataset.getXValue(series, index);
238                }
239            }
240            return Math.max(index, 0);
241        }
242    }
243
244    /**
245     * Finds a range of item indices that is guaranteed to contain all the
246     * x-values from x0 to x1 (inclusive).
247     *
248     * @param dataset  the dataset (<code>null</code> not permitted).
249     * @param series  the series index.
250     * @param xLow  the lower bound of the x-value range.
251     * @param xHigh  the upper bound of the x-value range.
252     *
253     * @return The indices of the boundary items.
254     */
255    public static int[] findLiveItems(XYDataset dataset, int series,
256            double xLow, double xHigh) {
257        // here we could probably be a little faster by searching for both
258        // indices simultaneously, but I'll look at that later if it seems
259        // like it matters...
260        int i0 = findLiveItemsLowerBound(dataset, series, xLow, xHigh);
261        int i1 = findLiveItemsUpperBound(dataset, series, xLow, xHigh);
262        if (i0 > i1) {
263            i0 = i1;
264        }
265        return new int[] {i0, i1};
266    }
267
268}