001/* ===========================================================
002 * JFreeChart : a free chart library for the Java(tm) platform
003 * ===========================================================
004 *
005 * (C) Copyright 2000-2009, 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 * [Java is a trademark or registered trademark of Sun Microsystems, Inc.
025 * in the United States and other countries.]
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 *
040 */
041
042package org.jfree.chart.renderer;
043
044import org.jfree.data.DomainOrder;
045import org.jfree.data.xy.XYDataset;
046
047/**
048 * Utility methods related to the rendering process.
049 *
050 * @since 1.0.6
051 */
052public class RendererUtilities {
053
054    /**
055     * Finds the lower index of the range of live items in the specified data
056     * series.
057     *
058     * @param dataset  the dataset (<code>null</code> not permitted).
059     * @param series  the series index.
060     * @param xLow  the lowest x-value in the live range.
061     * @param xHigh  the highest x-value in the live range.
062     *
063     * @return The index of the required item.
064     *
065     * @since 1.0.6
066     *
067     * @see #findLiveItemsUpperBound(XYDataset, int, double, double)
068     */
069    public static int findLiveItemsLowerBound(XYDataset dataset, int series,
070            double xLow, double xHigh) {
071        if (dataset == null) {
072            throw new IllegalArgumentException("Null 'dataset' argument.");
073        }
074        if (xLow >= xHigh) {
075            throw new IllegalArgumentException("Requires xLow < xHigh.");
076        }
077        int itemCount = dataset.getItemCount(series);
078        if (itemCount <= 1) {
079            return 0;
080        }
081        if (dataset.getDomainOrder() == DomainOrder.ASCENDING) {
082            // for data in ascending order by x-value, we are (broadly) looking
083            // for the index of the highest x-value that is less than xLow
084            int low = 0;
085            int high = itemCount - 1;
086            double lowValue = dataset.getXValue(series, low);
087            if (lowValue >= xLow) {
088                // special case where the lowest x-value is >= xLow
089                return low;
090            }
091            double highValue = dataset.getXValue(series, high);
092            if (highValue < xLow) {
093                // special case where the highest x-value is < xLow
094                return high;
095            }
096            while (high - low > 1) {
097                int mid = (low + high) / 2;
098                double midV = dataset.getXValue(series, mid);
099                if (midV >= xLow) {
100                    high = mid;
101                }
102                else {
103                    low = mid;
104                }
105            }
106            return high;
107        }
108        else if (dataset.getDomainOrder() == DomainOrder.DESCENDING) {
109            // when the x-values are sorted in descending order, the lower
110            // bound is found by calculating relative to the xHigh value
111            int low = 0;
112            int high = itemCount - 1;
113            double lowValue = dataset.getXValue(series, low);
114            if (lowValue <= xHigh) {
115                return low;
116            }
117            double highValue = dataset.getXValue(series, high);
118            if (highValue > xHigh) {
119                return high;
120            }
121            while (high - low > 1) {
122                int mid = (low + high) / 2;
123                double midV = dataset.getXValue(series, mid);
124                if (midV > xHigh) {
125                    low = mid;
126                }
127                else {
128                    high = mid;
129                }
130                mid = (low + high) / 2;
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}