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