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    
043    package org.jfree.chart.renderer;
044    
045    import org.jfree.data.DomainOrder;
046    import org.jfree.data.xy.XYDataset;
047    
048    /**
049     * Utility methods related to the rendering process.
050     *
051     * @since 1.0.6
052     */
053    public 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    }