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