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