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