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 }