Source code

001/*
+002 * Licensed to the Apache Software Foundation (ASF) under one or more
+003 * contributor license agreements.  See the NOTICE file distributed with
+004 * this work for additional information regarding copyright ownership.
+005 * The ASF licenses this file to You under the Apache License, Version 2.0
+006 * (the "License"); you may not use this file except in compliance with
+007 * the License.  You may obtain a copy of the License at
+008 *
+009 *      http://www.apache.org/licenses/LICENSE-2.0
+010 *
+011 * Unless required by applicable law or agreed to in writing, software
+012 * distributed under the License is distributed on an "AS IS" BASIS,
+013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+014 * See the License for the specific language governing permissions and
+015 * limitations under the License.
+016 */
+017package org.apache.commons.math3.stat.descriptive.rank;
+018
+019import java.io.IOException;
+020import java.io.ObjectInputStream;
+021import java.io.Serializable;
+022import java.text.DecimalFormat;
+023import java.util.ArrayList;
+024import java.util.Arrays;
+025import java.util.Collection;
+026import java.util.Collections;
+027import java.util.List;
+028
+029import org.apache.commons.math3.analysis.UnivariateFunction;
+030import org.apache.commons.math3.analysis.interpolation.LinearInterpolator;
+031import org.apache.commons.math3.analysis.interpolation.NevilleInterpolator;
+032import org.apache.commons.math3.analysis.interpolation.UnivariateInterpolator;
+033import org.apache.commons.math3.exception.InsufficientDataException;
+034import org.apache.commons.math3.exception.OutOfRangeException;
+035import org.apache.commons.math3.exception.util.LocalizedFormats;
+036import org.apache.commons.math3.stat.descriptive.AbstractStorelessUnivariateStatistic;
+037import org.apache.commons.math3.stat.descriptive.StorelessUnivariateStatistic;
+038import org.apache.commons.math3.util.MathArrays;
+039import org.apache.commons.math3.util.MathUtils;
+040import org.apache.commons.math3.util.Precision;
+041
+042/**
+043 * A {@link StorelessUnivariateStatistic} estimating percentiles using the
+044 * <ahref=http://www.cs.wustl.edu/~jain/papers/ftp/psqr.pdf>P<SUP>2</SUP></a>
+045 * Algorithm as explained by <a href=http://www.cse.wustl.edu/~jain/>Raj
+046 * Jain</a> and Imrich Chlamtac in
+047 * <a href=http://www.cse.wustl.edu/~jain/papers/psqr.htm>P<SUP>2</SUP> Algorithm
+048 * for Dynamic Calculation of Quantiles and Histogram Without Storing
+049 * Observations</a>.
+050 * <p>
+051 * Note: This implementation is not synchronized and produces an approximate
+052 * result. For small samples, where data can be stored and processed in memory,
+053 * {@link Percentile} should be used.</p>
+054 *
+055 */
+056public class PSquarePercentile extends AbstractStorelessUnivariateStatistic
+057        implements StorelessUnivariateStatistic, Serializable {
+058
+059    /**
+060     * The maximum array size used for psquare algorithm
+061     */
+062    private static final int PSQUARE_CONSTANT = 5;
+063
+064    /**
+065     * A Default quantile needed in case if user prefers to use default no
+066     * argument constructor.
+067     */
+068    private static final double DEFAULT_QUANTILE_DESIRED = 50d;
+069
+070    /**
+071     * Serial ID
+072     */
+073    private static final long serialVersionUID = 2283912083175715479L;
+074
+075    /**
+076     * A decimal formatter for print convenience
+077     */
+078    private static final DecimalFormat DECIMAL_FORMAT = new DecimalFormat(
+079            "00.00");
+080
+081    /**
+082     * Initial list of 5 numbers corresponding to 5 markers. <b>NOTE:</b>watch
+083     * out for the add methods that are overloaded
+084     */
+085    private final List<Double> initialFive = new FixedCapacityList<Double>(
+086            PSQUARE_CONSTANT);
+087
+088    /**
+089     * The quantile needed should be in range of 0-1. The constructor
+090     * {@link #PSquarePercentile(double)} ensures that passed in percentile is
+091     * divided by 100.
+092     */
+093    private final double quantile;
+094
+095    /**
+096     * lastObservation is the last observation value/input sample. No need to
+097     * serialize
+098     */
+099    private transient double lastObservation;
+100
+101    /**
+102     * Markers is the marker collection object which comes to effect
+103     * only after 5 values are inserted
+104     */
+105    private PSquareMarkers markers = null;
+106
+107    /**
+108     * Computed p value (i,e percentile value of data set hither to received)
+109     */
+110    private double pValue = Double.NaN;
+111
+112    /**
+113     * Counter to count the values/observations accepted into this data set
+114     */
+115    private long countOfObservations;
+116
+117    /**
+118     * Constructs a PSquarePercentile with the specific percentile value.
+119     * @param p the percentile
+120     * @throws OutOfRangeException  if p is not greater than 0 and less
+121     * than or equal to 100
+122     */
+123    public PSquarePercentile(final double p) {
+124        if (p > 100 || p < 0) {
+125            throw new OutOfRangeException(LocalizedFormats.OUT_OF_RANGE,
+126                    p, 0, 100);
+127        }
+128        this.quantile = p / 100d;// always set it within (0,1]
+129    }
+130
+131    /**
+132     * Default constructor that assumes a {@link #DEFAULT_QUANTILE_DESIRED
+133     * default quantile} needed
+134     */
+135    PSquarePercentile() {
+136        this(DEFAULT_QUANTILE_DESIRED);
+137    }
+138
+139    /**
+140     * {@inheritDoc}
+141     */
+142    @Override
+143    public int hashCode() {
+144        double result = getResult();
+145        result = Double.isNaN(result) ? 37 : result;
+146        final double markersHash = markers == null ? 0 : markers.hashCode();
+147        final double[] toHash = {result, quantile, markersHash, countOfObservations};
+148        return Arrays.hashCode(toHash);
+149    }
+150
+151    /**
+152     * Returns true iff {@code o} is a {@code PSquarePercentile} returning the
+153     * same values as this for {@code getResult()} and {@code getN()} and also
+154     * having equal markers
+155     *
+156     * @param o object to compare
+157     * @return true if {@code o} is a {@code PSquarePercentile} with
+158     * equivalent internal state
+159     */
+160    @Override
+161    public boolean equals(Object o) {
+162        boolean result = false;
+163        if (this == o) {
+164            result = true;
+165        } else if (o != null && o instanceof PSquarePercentile) {
+166            PSquarePercentile that = (PSquarePercentile) o;
+167            boolean isNotNull = markers != null && that.markers != null;
+168            boolean isNull = markers == null && that.markers == null;
+169            result = isNotNull ? markers.equals(that.markers) : isNull;
+170            // markers as in the case of first
+171            // five observations
+172            result = result && getN() == that.getN();
+173        }
+174        return result;
+175    }
+176
+177    /**
+178     * {@inheritDoc}The internal state updated due to the new value in this
+179     * context is basically of the marker positions and computation of the
+180     * approximate quantile.
+181     *
+182     * @param observation the observation currently being added.
+183     */
+184    @Override
+185    public void increment(final double observation) {
+186        // Increment counter
+187        countOfObservations++;
+188
+189        // Store last observation
+190        this.lastObservation = observation;
+191
+192        // 0. Use Brute force for <5
+193        if (markers == null) {
+194            if (initialFive.add(observation)) {
+195                Collections.sort(initialFive);
+196                pValue =
+197                        initialFive
+198                                .get((int) (quantile * (initialFive.size() - 1)));
+199                return;
+200            }
+201            // 1. Initialize once after 5th observation
+202            markers = newMarkers(initialFive, quantile);
+203        }
+204        // 2. process a Data Point and return pValue
+205        pValue = markers.processDataPoint(observation);
+206    }
+207
+208    /**
+209     * Returns a string containing the last observation, the current estimate
+210     * of the quantile and all markers.
+211     *
+212     * @return string representation of state data
+213     */
+214    @Override
+215    public String toString() {
+216
+217        if (markers == null) {
+218            return String.format("obs=%s pValue=%s",
+219                    DECIMAL_FORMAT.format(lastObservation),
+220                    DECIMAL_FORMAT.format(pValue));
+221        } else {
+222            return String.format("obs=%s markers=%s",
+223                    DECIMAL_FORMAT.format(lastObservation), markers.toString());
+224        }
+225    }
+226
+227    /**
+228     * {@inheritDoc}
+229     */
+230    public long getN() {
+231        return countOfObservations;
+232    }
+233
+234    /**
+235     * {@inheritDoc}
+236     */
+237    @Override
+238    public StorelessUnivariateStatistic copy() {
+239        // multiply quantile by 100 now as anyway constructor divides it by 100
+240        PSquarePercentile copy = new PSquarePercentile(100d * quantile);
+241
+242        if (markers != null) {
+243            copy.markers = (PSquareMarkers) markers.clone();
+244        }
+245        copy.countOfObservations = countOfObservations;
+246        copy.pValue = pValue;
+247        copy.initialFive.clear();
+248        copy.initialFive.addAll(initialFive);
+249        return copy;
+250    }
+251
+252    /**
+253     * Returns the quantile estimated by this statistic in the range [0.0-1.0]
+254     *
+255     * @return quantile estimated by {@link #getResult()}
+256     */
+257    public double quantile() {
+258        return quantile;
+259    }
+260
+261    /**
+262     * {@inheritDoc}. This basically clears all the markers, the
+263     * initialFive list and sets countOfObservations to 0.
+264     */
+265    @Override
+266    public void clear() {
+267        markers = null;
+268        initialFive.clear();
+269        countOfObservations = 0L;
+270        pValue = Double.NaN;
+271    }
+272
+273    /**
+274     * {@inheritDoc}
+275     */
+276    @Override
+277    public double getResult() {
+278        if (Double.compare(quantile, 1d) == 0) {
+279            pValue = maximum();
+280        } else if (Double.compare(quantile, 0d) == 0) {
+281            pValue = minimum();
+282        }
+283        return pValue;
+284    }
+285
+286    /**
+287     * @return maximum in the data set added to this statistic
+288     */
+289    private double maximum() {
+290        double val = Double.NaN;
+291        if (markers != null) {
+292            val = markers.height(PSQUARE_CONSTANT);
+293        } else if (!initialFive.isEmpty()) {
+294            val = initialFive.get(initialFive.size() - 1);
+295        }
+296        return val;
+297    }
+298
+299    /**
+300     * @return minimum in the data set added to this statistic
+301     */
+302    private double minimum() {
+303        double val = Double.NaN;
+304        if (markers != null) {
+305            val = markers.height(1);
+306        } else if (!initialFive.isEmpty()) {
+307            val = initialFive.get(0);
+308        }
+309        return val;
+310    }
+311
+312    /**
+313     * Markers is an encapsulation of the five markers/buckets as indicated in
+314     * the original works.
+315     */
+316    private static class Markers implements PSquareMarkers, Serializable {
+317        /**
+318         * Serial version id
+319         */
+320        private static final long serialVersionUID = 1L;
+321
+322        /** Low marker index */
+323        private static final int LOW = 2;
+324
+325        /** High marker index */
+326        private static final int HIGH = 4;
+327
+328        /**
+329         * Array of 5+1 Markers (The first marker is dummy just so we
+330         * can match the rest of indexes [1-5] indicated in the original works
+331         * which follows unit based index)
+332         */
+333        private final Marker[] markerArray;
+334
+335        /**
+336         * Kth cell belonging to [1-5] of the markerArray. No need for
+337         * this to be serialized
+338         */
+339        private transient int k = -1;
+340
+341        /**
+342         * Constructor
+343         *
+344         * @param theMarkerArray marker array to be used
+345         */
+346        private Markers(final Marker[] theMarkerArray) {
+347            MathUtils.checkNotNull(theMarkerArray);
+348            markerArray = theMarkerArray;
+349            for (int i = 1; i < PSQUARE_CONSTANT; i++) {
+350                markerArray[i].previous(markerArray[i - 1])
+351                        .next(markerArray[i + 1]).index(i);
+352            }
+353            markerArray[0].previous(markerArray[0]).next(markerArray[1])
+354                    .index(0);
+355            markerArray[5].previous(markerArray[4]).next(markerArray[5])
+356                    .index(5);
+357        }
+358
+359        /**
+360         * Constructor
+361         *
+362         * @param initialFive elements required to build Marker
+363         * @param p quantile required to be computed
+364         */
+365        private Markers(final List<Double> initialFive, final double p) {
+366            this(createMarkerArray(initialFive, p));
+367        }
+368
+369        /**
+370         * Creates a marker array using initial five elements and a quantile
+371         *
+372         * @param initialFive list of initial five elements
+373         * @param p the pth quantile
+374         * @return Marker array
+375         */
+376        private static Marker[] createMarkerArray(
+377                final List<Double> initialFive, final double p) {
+378            final int countObserved =
+379                    initialFive == null ? -1 : initialFive.size();
+380            if (countObserved < PSQUARE_CONSTANT) {
+381                throw new InsufficientDataException(
+382                        LocalizedFormats.INSUFFICIENT_OBSERVED_POINTS_IN_SAMPLE,
+383                        countObserved, PSQUARE_CONSTANT);
+384            }
+385            Collections.sort(initialFive);
+386            return new Marker[] {
+387                    new Marker(),// Null Marker
+388                    new Marker(initialFive.get(0), 1, 0, 1),
+389                    new Marker(initialFive.get(1), 1 + 2 * p, p / 2, 2),
+390                    new Marker(initialFive.get(2), 1 + 4 * p, p, 3),
+391                    new Marker(initialFive.get(3), 3 + 2 * p, (1 + p) / 2, 4),
+392                    new Marker(initialFive.get(4), 5, 1, 5) };
+393        }
+394
+395        /**
+396         * {@inheritDoc}
+397         */
+398        @Override
+399        public int hashCode() {
+400            return Arrays.deepHashCode(markerArray);
+401        }
+402
+403        /**
+404         * {@inheritDoc}.This equals method basically checks for marker array to
+405         * be deep equals.
+406         *
+407         * @param o is the other object
+408         * @return true if the object compares with this object are equivalent
+409         */
+410        @Override
+411        public boolean equals(Object o) {
+412            boolean result = false;
+413            if (this == o) {
+414                result = true;
+415            } else if (o != null && o instanceof Markers) {
+416                Markers that = (Markers) o;
+417                result = Arrays.deepEquals(markerArray, that.markerArray);
+418            }
+419            return result;
+420        }
+421
+422        /**
+423         * Process a data point
+424         *
+425         * @param inputDataPoint is the data point passed
+426         * @return computed percentile
+427         */
+428        public double processDataPoint(final double inputDataPoint) {
+429
+430            // 1. Find cell and update minima and maxima
+431            final int kthCell = findCellAndUpdateMinMax(inputDataPoint);
+432
+433            // 2. Increment positions
+434            incrementPositions(1, kthCell + 1, 5);
+435
+436            // 2a. Update desired position with increments
+437            updateDesiredPositions();
+438
+439            // 3. Adjust heights of m[2-4] if necessary
+440            adjustHeightsOfMarkers();
+441
+442            // 4. Return percentile
+443            return getPercentileValue();
+444        }
+445
+446        /**
+447         * Returns the percentile computed thus far.
+448         *
+449         * @return height of mid point marker
+450         */
+451        public double getPercentileValue() {
+452            return height(3);
+453        }
+454
+455        /**
+456         * Finds the cell where the input observation / value fits.
+457         *
+458         * @param observation the input value to be checked for
+459         * @return kth cell (of the markers ranging from 1-5) where observed
+460         *         sample fits
+461         */
+462        private int findCellAndUpdateMinMax(final double observation) {
+463            k = -1;
+464            if (observation < height(1)) {
+465                markerArray[1].markerHeight = observation;
+466                k = 1;
+467            } else if (observation < height(2)) {
+468                k = 1;
+469            } else if (observation < height(3)) {
+470                k = 2;
+471            } else if (observation < height(4)) {
+472                k = 3;
+473            } else if (observation <= height(5)) {
+474                k = 4;
+475            } else {
+476                markerArray[5].markerHeight = observation;
+477                k = 4;
+478            }
+479            return k;
+480        }
+481
+482        /**
+483         * Adjust marker heights by setting quantile estimates to middle markers.
+484         */
+485        private void adjustHeightsOfMarkers() {
+486            for (int i = LOW; i <= HIGH; i++) {
+487                estimate(i);
+488            }
+489        }
+490
+491        /**
+492         * {@inheritDoc}
+493         */
+494        public double estimate(final int index) {
+495            if (index < LOW || index > HIGH) {
+496                throw new OutOfRangeException(index, LOW, HIGH);
+497            }
+498            return markerArray[index].estimate();
+499        }
+500
+501        /**
+502         * Increment positions by d. Refer to algorithm paper for the
+503         * definition of d.
+504         *
+505         * @param d The increment value for the position
+506         * @param startIndex start index of the marker array
+507         * @param endIndex end index of the marker array
+508         */
+509        private void incrementPositions(final int d, final int startIndex,
+510                final int endIndex) {
+511            for (int i = startIndex; i <= endIndex; i++) {
+512                markerArray[i].incrementPosition(d);
+513            }
+514        }
+515
+516        /**
+517         * Desired positions incremented by bucket width. The bucket width is
+518         * basically the desired increments.
+519         */
+520        private void updateDesiredPositions() {
+521            for (int i = 1; i < markerArray.length; i++) {
+522                markerArray[i].updateDesiredPosition();
+523            }
+524        }
+525
+526        /**
+527         * Sets previous and next markers after default read is done.
+528         *
+529         * @param anInputStream the input stream to be deserialized
+530         * @throws ClassNotFoundException thrown when a desired class not found
+531         * @throws IOException thrown due to any io errors
+532         */
+533        private void readObject(ObjectInputStream anInputStream)
+534                throws ClassNotFoundException, IOException {
+535            // always perform the default de-serialization first
+536            anInputStream.defaultReadObject();
+537            // Build links
+538            for (int i = 1; i < PSQUARE_CONSTANT; i++) {
+539                markerArray[i].previous(markerArray[i - 1])
+540                        .next(markerArray[i + 1]).index(i);
+541            }
+542            markerArray[0].previous(markerArray[0]).next(markerArray[1])
+543                    .index(0);
+544            markerArray[5].previous(markerArray[4]).next(markerArray[5])
+545                    .index(5);
+546        }
+547
+548        /**
+549         * Return marker height given index
+550         *
+551         * @param markerIndex index of marker within (1,6)
+552         * @return marker height
+553         */
+554        public double height(final int markerIndex) {
+555            if (markerIndex >= markerArray.length || markerIndex <= 0) {
+556                throw new OutOfRangeException(markerIndex, 1,
+557                        markerArray.length);
+558            }
+559            return markerArray[markerIndex].markerHeight;
+560        }
+561
+562        /**
+563         * {@inheritDoc}.Clone Markers
+564         *
+565         * @return cloned object
+566         */
+567        @Override
+568        public Object clone() {
+569            return new Markers(new Marker[] { new Marker(),
+570                    (Marker) markerArray[1].clone(),
+571                    (Marker) markerArray[2].clone(),
+572                    (Marker) markerArray[3].clone(),
+573                    (Marker) markerArray[4].clone(),
+574                    (Marker) markerArray[5].clone() });
+575
+576        }
+577
+578        /**
+579         * Returns string representation of the Marker array.
+580         *
+581         * @return Markers as a string
+582         */
+583        @Override
+584        public String toString() {
+585            return String.format("m1=[%s],m2=[%s],m3=[%s],m4=[%s],m5=[%s]",
+586                    markerArray[1].toString(), markerArray[2].toString(),
+587                    markerArray[3].toString(), markerArray[4].toString(),
+588                    markerArray[5].toString());
+589        }
+590
+591    }
+592
+593    /**
+594     * The class modeling the attributes of the marker of the P-square algorithm
+595     */
+596    private static class Marker implements Serializable, Cloneable {
+597
+598        /**
+599         * Serial Version ID
+600         */
+601        private static final long serialVersionUID = -3575879478288538431L;
+602
+603        /**
+604         * The marker index which is just a serial number for the marker in the
+605         * marker array of 5+1.
+606         */
+607        private int index;
+608
+609        /**
+610         * The integral marker position. Refer to the variable n in the original
+611         * works.
+612         */
+613        private double intMarkerPosition;
+614
+615        /**
+616         * Desired marker position. Refer to the variable n' in the original
+617         * works.
+618         */
+619        private double desiredMarkerPosition;
+620
+621        /**
+622         * Marker height or the quantile. Refer to the variable q in the
+623         * original works.
+624         */
+625        private double markerHeight;
+626
+627        /**
+628         * Desired marker increment. Refer to the variable dn' in the original
+629         * works.
+630         */
+631        private double desiredMarkerIncrement;
+632
+633        /**
+634         * Next and previous markers for easy linked navigation in loops. this
+635         * is not serialized as they can be rebuilt during deserialization.
+636         */
+637        private transient Marker next;
+638
+639        /**
+640         * The previous marker links
+641         */
+642        private transient Marker previous;
+643
+644        /**
+645         * Nonlinear interpolator
+646         */
+647        private final UnivariateInterpolator nonLinear =
+648                new NevilleInterpolator();
+649
+650        /**
+651         * Linear interpolator which is not serializable
+652         */
+653        private transient UnivariateInterpolator linear =
+654                new LinearInterpolator();
+655
+656        /**
+657         * Default constructor
+658         */
+659        private Marker() {
+660            this.next = this.previous = this;
+661        }
+662
+663        /**
+664         * Constructor of the marker with parameters
+665         *
+666         * @param heightOfMarker represent the quantile value
+667         * @param makerPositionDesired represent the desired marker position
+668         * @param markerPositionIncrement represent increments for position
+669         * @param markerPositionNumber represent the position number of marker
+670         */
+671        private Marker(double heightOfMarker, double makerPositionDesired,
+672                double markerPositionIncrement, double markerPositionNumber) {
+673            this();
+674            this.markerHeight = heightOfMarker;
+675            this.desiredMarkerPosition = makerPositionDesired;
+676            this.desiredMarkerIncrement = markerPositionIncrement;
+677            this.intMarkerPosition = markerPositionNumber;
+678        }
+679
+680        /**
+681         * Sets the previous marker.
+682         *
+683         * @param previousMarker the previous marker to the current marker in
+684         *            the array of markers
+685         * @return this instance
+686         */
+687        private Marker previous(final Marker previousMarker) {
+688            MathUtils.checkNotNull(previousMarker);
+689            this.previous = previousMarker;
+690            return this;
+691        }
+692
+693        /**
+694         * Sets the next marker.
+695         *
+696         * @param nextMarker the next marker to the current marker in the array
+697         *            of markers
+698         * @return this instance
+699         */
+700        private Marker next(final Marker nextMarker) {
+701            MathUtils.checkNotNull(nextMarker);
+702            this.next = nextMarker;
+703            return this;
+704        }
+705
+706        /**
+707         * Sets the index of the marker.
+708         *
+709         * @param indexOfMarker the array index of the marker in marker array
+710         * @return this instance
+711         */
+712        private Marker index(final int indexOfMarker) {
+713            this.index = indexOfMarker;
+714            return this;
+715        }
+716
+717        /**
+718         * Update desired Position with increment.
+719         */
+720        private void updateDesiredPosition() {
+721            desiredMarkerPosition += desiredMarkerIncrement;
+722        }
+723
+724        /**
+725         * Increment Position by d.
+726         *
+727         * @param d a delta value to increment
+728         */
+729        private void incrementPosition(final int d) {
+730            intMarkerPosition += d;
+731        }
+732
+733        /**
+734         * Difference between desired and actual position
+735         *
+736         * @return difference between desired and actual position
+737         */
+738        private double difference() {
+739            return desiredMarkerPosition - intMarkerPosition;
+740        }
+741
+742        /**
+743         * Estimate the quantile for the current marker.
+744         *
+745         * @return estimated quantile
+746         */
+747        private double estimate() {
+748            final double di = difference();
+749            final boolean isNextHigher =
+750                    next.intMarkerPosition - intMarkerPosition > 1;
+751            final boolean isPreviousLower =
+752                    previous.intMarkerPosition - intMarkerPosition < -1;
+753
+754            if (di >= 1 && isNextHigher || di <= -1 && isPreviousLower) {
+755                final int d = di >= 0 ? 1 : -1;
+756                final double[] xval =
+757                        new double[] { previous.intMarkerPosition,
+758                                intMarkerPosition, next.intMarkerPosition };
+759                final double[] yval =
+760                        new double[] { previous.markerHeight, markerHeight,
+761                                next.markerHeight };
+762                final double xD = intMarkerPosition + d;
+763
+764                UnivariateFunction univariateFunction =
+765                        nonLinear.interpolate(xval, yval);
+766                markerHeight = univariateFunction.value(xD);
+767
+768                // If parabolic estimate is bad then turn linear
+769                if (isEstimateBad(yval, markerHeight)) {
+770                    int delta = xD - xval[1] > 0 ? 1 : -1;
+771                    final double[] xBad =
+772                            new double[] { xval[1], xval[1 + delta] };
+773                    final double[] yBad =
+774                            new double[] { yval[1], yval[1 + delta] };
+775                    MathArrays.sortInPlace(xBad, yBad);// since d can be +/- 1
+776                    univariateFunction = linear.interpolate(xBad, yBad);
+777                    markerHeight = univariateFunction.value(xD);
+778                }
+779                incrementPosition(d);
+780            }
+781            return markerHeight;
+782        }
+783
+784        /**
+785         * Check if parabolic/nonlinear estimate is bad by checking if the
+786         * ordinate found is beyond the y[0] and y[2].
+787         *
+788         * @param y the array to get the bounds
+789         * @param yD the estimate
+790         * @return true if yD is a bad estimate
+791         */
+792        private boolean isEstimateBad(final double[] y, final double yD) {
+793            return yD <= y[0] || yD >= y[2];
+794        }
+795
+796        /**
+797         * {@inheritDoc}<i>This equals method checks for marker attributes and
+798         * as well checks if navigation pointers (next and previous) are the same
+799         * between this and passed in object</i>
+800         *
+801         * @param o Other object
+802         * @return true if this equals passed in other object o
+803         */
+804        @Override
+805        public boolean equals(Object o) {
+806            boolean result = false;
+807            if (this == o) {
+808                result = true;
+809            } else if (o != null && o instanceof Marker) {
+810                Marker that = (Marker) o;
+811
+812                result = Double.compare(markerHeight, that.markerHeight) == 0;
+813                result =
+814                        result &&
+815                                Double.compare(intMarkerPosition,
+816                                        that.intMarkerPosition) == 0;
+817                result =
+818                        result &&
+819                                Double.compare(desiredMarkerPosition,
+820                                        that.desiredMarkerPosition) == 0;
+821                result =
+822                        result &&
+823                                Double.compare(desiredMarkerIncrement,
+824                                        that.desiredMarkerIncrement) == 0;
+825
+826                result = result && next.index == that.next.index;
+827                result = result && previous.index == that.previous.index;
+828            }
+829            return result;
+830        }
+831
+832        @Override
+833        public int hashCode() {
+834            return Arrays.hashCode(new double[] {markerHeight, intMarkerPosition,
+835                desiredMarkerIncrement, desiredMarkerPosition, previous.index, next.index});
+836        }
+837
+838        /**
+839         * Read Object to deserialize.
+840         *
+841         * @param anInstream Stream Object data
+842         * @throws IOException thrown for IO Errors
+843         * @throws ClassNotFoundException thrown for class not being found
+844         */
+845        private void readObject(ObjectInputStream anInstream)
+846                throws ClassNotFoundException, IOException {
+847            anInstream.defaultReadObject();
+848            previous=next=this;
+849            linear = new LinearInterpolator();
+850        }
+851
+852        /**
+853         * Clone this instance.
+854         *
+855         * @return cloned marker
+856         */
+857        @Override
+858        public Object clone() {
+859            return new Marker(markerHeight, desiredMarkerPosition,
+860                    desiredMarkerIncrement, intMarkerPosition);
+861        }
+862
+863        /**
+864         * {@inheritDoc}
+865         */
+866        @Override
+867        public String toString() {
+868            return String.format(
+869                    "index=%.0f,n=%.0f,np=%.2f,q=%.2f,dn=%.2f,prev=%d,next=%d",
+870                    (double) index, Precision.round(intMarkerPosition, 0),
+871                    Precision.round(desiredMarkerPosition, 2),
+872                    Precision.round(markerHeight, 2),
+873                    Precision.round(desiredMarkerIncrement, 2), previous.index,
+874                    next.index);
+875        }
+876    }
+877
+878    /**
+879     * A simple fixed capacity list that has an upper bound to growth.
+880     * Once its capacity is reached, {@code add} is a no-op, returning
+881     * {@code false}.
+882     *
+883     * @param <E>
+884     */
+885    private static class FixedCapacityList<E> extends ArrayList<E> implements
+886            Serializable {
+887        /**
+888         * Serialization Version Id
+889         */
+890        private static final long serialVersionUID = 2283952083075725479L;
+891        /**
+892         * Capacity of the list
+893         */
+894        private final int capacity;
+895
+896        /**
+897         * This constructor constructs the list with given capacity and as well
+898         * as stores the capacity
+899         *
+900         * @param fixedCapacity the capacity to be fixed for this list
+901         */
+902        public FixedCapacityList(final int fixedCapacity) {
+903            super(fixedCapacity);
+904            this.capacity = fixedCapacity;
+905        }
+906
+907        /**
+908         * {@inheritDoc} In addition it checks if the {@link #size()} returns a
+909         * size that is within capacity and if true it adds; otherwise the list
+910         * contents are unchanged and {@code false} is returned.
+911         *
+912         * @return true if addition is successful and false otherwise
+913         */
+914        @Override
+915        public boolean add(final E e) {
+916            return size() < capacity ? super.add(e) : false;
+917        }
+918
+919        /**
+920         * {@inheritDoc} In addition it checks if the sum of Collection size and
+921         * this instance's {@link #size()} returns a value that is within
+922         * capacity and if true it adds the collection; otherwise the list
+923         * contents are unchanged and {@code false} is returned.
+924         *
+925         * @return true if addition is successful and false otherwise
+926         */
+927        @Override
+928        public boolean addAll(Collection<? extends E> collection) {
+929            boolean isCollectionLess =
+930                    collection != null &&
+931                            collection.size() + size() <= capacity;
+932            return isCollectionLess ? super.addAll(collection) : false;
+933        }
+934    }

[... 127 lines stripped ...]