001/* ===========================================================
002 * JFreeChart : a free chart library for the Java(tm) platform
003 * ===========================================================
004 *
005 * (C) Copyright 2000-2011, 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-2009, 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 *
041 */
042
043package org.jfree.chart.renderer;
044
045import org.jfree.data.DomainOrder;
046import org.jfree.data.xy.XYDataset;
047
048/**
049 * Utility methods related to the rendering process.
050 *
051 * @since 1.0.6
052 */
053public class RendererUtilities {
054
055    /**
056     * Finds the lower index of the range of live items in the specified data
057     * series.
058     *
059     * @param dataset  the dataset (<code>null</code> not permitted).
060     * @param series  the series index.
061     * @param xLow  the lowest x-value in the live range.
062     * @param xHigh  the highest x-value in the live range.
063     *
064     * @return The index of the required item.
065     *
066     * @since 1.0.6
067     *
068     * @see #findLiveItemsUpperBound(XYDataset, int, double, double)
069     */
070    public static int findLiveItemsLowerBound(XYDataset dataset, int series,
071            double xLow, double xHigh) {
072        if (dataset == null) {
073            throw new IllegalArgumentException("Null 'dataset' argument.");
074        }
075        if (xLow >= xHigh) {
076            throw new IllegalArgumentException("Requires xLow < xHigh.");
077        }
078        int itemCount = dataset.getItemCount(series);
079        if (itemCount <= 1) {
080            return 0;
081        }
082        if (dataset.getDomainOrder() == DomainOrder.ASCENDING) {
083            // for data in ascending order by x-value, we are (broadly) looking
084            // for the index of the highest x-value that is less than xLow
085            int low = 0;
086            int high = itemCount - 1;
087            double lowValue = dataset.getXValue(series, low);
088            if (lowValue >= xLow) {
089                // special case where the lowest x-value is >= xLow
090                return low;
091            }
092            double highValue = dataset.getXValue(series, high);
093            if (highValue < xLow) {
094                // special case where the highest x-value is < xLow
095                return high;
096            }
097            while (high - low > 1) {
098                int mid = (low + high) / 2;
099                double midV = dataset.getXValue(series, mid);
100                if (midV >= xLow) {
101                    high = mid;
102                }
103                else {
104                    low = mid;
105                }
106            }
107            return high;
108        }
109        else if (dataset.getDomainOrder() == DomainOrder.DESCENDING) {
110            // when the x-values are sorted in descending order, the lower
111            // bound is found by calculating relative to the xHigh value
112            int low = 0;
113            int high = itemCount - 1;
114            double lowValue = dataset.getXValue(series, low);
115            if (lowValue <= xHigh) {
116                return low;
117            }
118            double highValue = dataset.getXValue(series, high);
119            if (highValue > xHigh) {
120                return high;
121            }
122            while (high - low > 1) {
123                int mid = (low + high) / 2;
124                double midV = dataset.getXValue(series, mid);
125                if (midV > xHigh) {
126                    low = mid;
127                }
128                else {
129                    high = mid;
130                }
131            }
132            return high;
133        }
134        else {
135            // we don't know anything about the ordering of the x-values,
136            // but we can still skip any initial values that fall outside the
137            // range...
138            int index = 0;
139            // skip any items that don't need including...
140            double x = dataset.getXValue(series, index);
141            while (index < itemCount && (x < xLow || x > xHigh)) {
142                index++;
143                if (index < itemCount) {
144                    x = dataset.getXValue(series, index);
145                }
146            }
147            return Math.min(Math.max(0, index), itemCount - 1);
148        }
149    }
150
151    /**
152     * Finds the upper index of the range of live items in the specified data
153     * series.
154     *
155     * @param dataset  the dataset (<code>null</code> not permitted).
156     * @param series  the series index.
157     * @param xLow  the lowest x-value in the live range.
158     * @param xHigh  the highest x-value in the live range.
159     *
160     * @return The index of the required item.
161     *
162     * @since 1.0.6
163     *
164     * @see #findLiveItemsLowerBound(XYDataset, int, double, double)
165     */
166    public static int findLiveItemsUpperBound(XYDataset dataset, int series,
167            double xLow, double xHigh) {
168        if (dataset == null) {
169            throw new IllegalArgumentException("Null 'dataset' argument.");
170        }
171        if (xLow >= xHigh) {
172            throw new IllegalArgumentException("Requires xLow < xHigh.");
173        }
174        int itemCount = dataset.getItemCount(series);
175        if (itemCount <= 1) {
176            return 0;
177        }
178        if (dataset.getDomainOrder() == DomainOrder.ASCENDING) {
179            int low = 0;
180            int high = itemCount - 1;
181            double lowValue = dataset.getXValue(series, low);
182            if (lowValue > xHigh) {
183                return low;
184            }
185            double highValue = dataset.getXValue(series, high);
186            if (highValue <= xHigh) {
187                return high;
188            }
189            int mid = (low + high) / 2;
190            while (high - low > 1) {
191                double midV = dataset.getXValue(series, mid);
192                if (midV <= xHigh) {
193                    low = mid;
194                }
195                else {
196                    high = mid;
197                }
198                mid = (low + high) / 2;
199            }
200            return mid;
201        }
202        else if (dataset.getDomainOrder() == DomainOrder.DESCENDING) {
203            // when the x-values are descending, the upper bound is found by
204            // comparing against xLow
205            int low = 0;
206            int high = itemCount - 1;
207            int mid = (low + high) / 2;
208            double lowValue = dataset.getXValue(series, low);
209            if (lowValue < xLow) {
210                return low;
211            }
212            double highValue = dataset.getXValue(series, high);
213            if (highValue >= xLow) {
214                return high;
215            }
216            while (high - low > 1) {
217                double midV = dataset.getXValue(series, mid);
218                if (midV >= xLow) {
219                    low = mid;
220                }
221                else {
222                    high = mid;
223                }
224                mid = (low + high) / 2;
225            }
226            return mid;
227        }
228        else {
229            // we don't know anything about the ordering of the x-values,
230            // but we can still skip any trailing values that fall outside the
231            // range...
232            int index = itemCount - 1;
233            // skip any items that don't need including...
234            double x = dataset.getXValue(series, index);
235            while (index >= 0 && (x < xLow || x > xHigh)) {
236                index--;
237                if (index >= 0) {
238                    x = dataset.getXValue(series, index);
239                }
240            }
241            return Math.max(index, 0);
242        }
243    }
244
245    /**
246     * Finds a range of item indices that is guaranteed to contain all the
247     * x-values from x0 to x1 (inclusive).
248     *
249     * @param dataset  the dataset (<code>null</code> not permitted).
250     * @param series  the series index.
251     * @param xLow  the lower bound of the x-value range.
252     * @param xHigh  the upper bound of the x-value range.
253     *
254     * @return The indices of the boundary items.
255     */
256    public static int[] findLiveItems(XYDataset dataset, int series,
257            double xLow, double xHigh) {
258        // here we could probably be a little faster by searching for both
259        // indices simultaneously, but I'll look at that later if it seems
260        // like it matters...
261        int i0 = findLiveItemsLowerBound(dataset, series, xLow, xHigh);
262        int i1 = findLiveItemsUpperBound(dataset, series, xLow, xHigh);
263        if (i0 > i1) {
264            i0 = i1;
265        }
266        return new int[] {i0, i1};
267    }
268
269}