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        /** {@inheritDoc} */
833        @Override
834        public int hashCode() {
835            return Arrays.hashCode(new double[] {markerHeight, intMarkerPosition,
836                desiredMarkerIncrement, desiredMarkerPosition, previous.index, next.index});
837        }
838
839        /**
840         * Read Object to deserialize.
841         *
842         * @param anInstream Stream Object data
843         * @throws IOException thrown for IO Errors
844         * @throws ClassNotFoundException thrown for class not being found
845         */
846        private void readObject(ObjectInputStream anInstream)
847                throws ClassNotFoundException, IOException {
848            anInstream.defaultReadObject();
849            previous=next=this;
850            linear = new LinearInterpolator();
851        }
852
853        /**
854         * Clone this instance.
855         *
856         * @return cloned marker
857         */
858        @Override
859        public Object clone() {
860            return new Marker(markerHeight, desiredMarkerPosition,
861                    desiredMarkerIncrement, intMarkerPosition);
862        }
863
864        /**
865         * {@inheritDoc}
866         */
867        @Override
868        public String toString() {
869            return String.format(
870                    "index=%.0f,n=%.0f,np=%.2f,q=%.2f,dn=%.2f,prev=%d,next=%d",
871                    (double) index, Precision.round(intMarkerPosition, 0),
872                    Precision.round(desiredMarkerPosition, 2),
873                    Precision.round(markerHeight, 2),
874                    Precision.round(desiredMarkerIncrement, 2), previous.index,
875                    next.index);
876        }
877    }
878
879    /**
880     * A simple fixed capacity list that has an upper bound to growth.
881     * Once its capacity is reached, {@code add} is a no-op, returning
882     * {@code false}.
883     *
884     * @param <E>
885     */
886    private static class FixedCapacityList<E> extends ArrayList<E> implements
887            Serializable {
888        /**
889         * Serialization Version Id
890         */
891        private static final long serialVersionUID = 2283952083075725479L;
892        /**
893         * Capacity of the list
894         */
895        private final int capacity;
896
897        /**
898         * This constructor constructs the list with given capacity and as well
899         * as stores the capacity
900         *
901         * @param fixedCapacity the capacity to be fixed for this list
902         */
903        FixedCapacityList(final int fixedCapacity) {
904            super(fixedCapacity);
905            this.capacity = fixedCapacity;
906        }
907
908        /**
909         * {@inheritDoc} In addition it checks if the {@link #size()} returns a
910         * size that is within capacity and if true it adds; otherwise the list
911         * contents are unchanged and {@code false} is returned.
912         *
913         * @return true if addition is successful and false otherwise
914         */
915        @Override
916        public boolean add(final E e) {
917            return size() < capacity ? super.add(e) : false;
918        }
919
920        /**
921         * {@inheritDoc} In addition it checks if the sum of Collection size and
922         * this instance's {@link #size()} returns a value that is within
923         * capacity and if true it adds the collection; otherwise the list
924         * contents are unchanged and {@code false} is returned.
925         *
926         * @return true if addition is successful and false otherwise
927         */
928        @Override
929        public boolean addAll(Collection<? extends E> collection) {
930            boolean isCollectionLess =
931                    collection != null &&
932                            collection.size() + size() <= capacity;
933            return isCollectionLess ? super.addAll(collection) : false;
934        }
935    }
936
937    /**
938     * A creation method to build Markers
939     *
940     * @param initialFive list of initial five elements
941     * @param p the quantile desired
942     * @return an instance of PSquareMarkers
943     */
944    public static PSquareMarkers newMarkers(final List<Double> initialFive,
945            final double p) {
946        return new Markers(initialFive, p);
947    }
948
949    /**
950     * An interface that encapsulates abstractions of the
951     * P-square algorithm markers as is explained in the original works. This
952     * interface is exposed with protected access to help in testability.
953     */
954    protected interface PSquareMarkers extends Cloneable {
955        /**
956         * Returns Percentile value computed thus far.
957         *
958         * @return percentile
959         */
960        double getPercentileValue();
961
962        /**
963         * A clone function to clone the current instance. It's created as an
964         * interface method as well for convenience though Cloneable is just a
965         * marker interface.
966         *
967         * @return clone of this instance
968         */
969        Object clone();
970
971        /**
972         * Returns the marker height (or percentile) of a given marker index.
973         *
974         * @param markerIndex is the index of marker in the marker array
975         * @return percentile value of the marker index passed
976         * @throws OutOfRangeException in case the index is not within [1-5]
977         */
978        double height(final int markerIndex);
979
980        /**
981         * Process a data point by moving the marker heights based on estimator.
982         *
983         * @param inputDataPoint is the data point passed
984         * @return computed percentile
985         */
986        double processDataPoint(final double inputDataPoint);
987
988        /**
989         * An Estimate of the percentile value of a given Marker
990         *
991         * @param index the marker's index in the array of markers
992         * @return percentile estimate
993         * @throws OutOfRangeException in case if index is not within [1-5]
994         */
995        double estimate(final int index);
996    }
997}