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