1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.math4.legacy.stat.descriptive.rank;
18
19 import java.text.DecimalFormat;
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Collection;
23 import java.util.Collections;
24 import java.util.List;
25
26 import org.apache.commons.numbers.core.Precision;
27 import org.apache.commons.numbers.arrays.SortInPlace;
28 import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
29 import org.apache.commons.math4.legacy.analysis.interpolation.LinearInterpolator;
30 import org.apache.commons.math4.legacy.analysis.interpolation.NevilleInterpolator;
31 import org.apache.commons.math4.legacy.analysis.interpolation.UnivariateInterpolator;
32 import org.apache.commons.math4.legacy.exception.InsufficientDataException;
33 import org.apache.commons.math4.legacy.exception.OutOfRangeException;
34 import org.apache.commons.math4.legacy.exception.NullArgumentException;
35 import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
36 import org.apache.commons.math4.legacy.stat.descriptive.AbstractStorelessUnivariateStatistic;
37 import org.apache.commons.math4.legacy.stat.descriptive.StorelessUnivariateStatistic;
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 public class PSquarePercentile extends AbstractStorelessUnivariateStatistic
53 implements StorelessUnivariateStatistic {
54
55
56
57
58 private static final int PSQUARE_CONSTANT = 5;
59
60
61
62
63
64 private static final double DEFAULT_QUANTILE_DESIRED = 50d;
65
66
67
68
69 private static final DecimalFormat DECIMAL_FORMAT = new DecimalFormat("00.00");
70
71
72
73
74
75 private final List<Double> initialFive = new FixedCapacityList<>(PSQUARE_CONSTANT);
76
77
78
79
80
81
82 private final double quantile;
83
84
85
86
87
88 private transient double lastObservation;
89
90
91
92
93
94 private PSquareMarkers markers;
95
96
97
98
99 private double pValue = Double.NaN;
100
101
102
103
104 private long countOfObservations;
105
106
107
108
109
110
111
112 public PSquarePercentile(final double p) {
113 if (p > 100 || p < 0) {
114 throw new OutOfRangeException(LocalizedFormats.OUT_OF_RANGE, p, 0, 100);
115 }
116 this.quantile = p / 100d;
117 }
118
119
120
121
122
123 PSquarePercentile() {
124 this(DEFAULT_QUANTILE_DESIRED);
125 }
126
127
128
129
130 @Override
131 public int hashCode() {
132 double result = getResult();
133 result = Double.isNaN(result) ? 37 : result;
134 final double markersHash = markers == null ? 0 : markers.hashCode();
135 final double[] toHash = {result, quantile, markersHash, countOfObservations};
136 return Arrays.hashCode(toHash);
137 }
138
139
140
141
142
143
144
145
146
147
148 @Override
149 public boolean equals(Object o) {
150 boolean result = false;
151 if (this == o) {
152 result = true;
153 } else if (o instanceof PSquarePercentile) {
154 PSquarePercentile that = (PSquarePercentile) o;
155 boolean isNotNull = markers != null && that.markers != null;
156 boolean isNull = markers == null && that.markers == null;
157 result = isNotNull ? markers.equals(that.markers) : isNull;
158
159
160 result = result && getN() == that.getN();
161 }
162 return result;
163 }
164
165
166
167
168
169
170
171
172 @Override
173 public void increment(final double observation) {
174
175 countOfObservations++;
176
177
178 this.lastObservation = observation;
179
180
181 if (markers == null) {
182 if (initialFive.add(observation)) {
183 Collections.sort(initialFive);
184 pValue =
185 initialFive
186 .get((int) (quantile * (initialFive.size() - 1)));
187 return;
188 }
189
190 markers = newMarkers(initialFive, quantile);
191 }
192
193 pValue = markers.processDataPoint(observation);
194 }
195
196
197
198
199
200
201
202 @Override
203 public String toString() {
204
205 if (markers == null) {
206 return String.format("obs=%s pValue=%s",
207 DECIMAL_FORMAT.format(lastObservation),
208 DECIMAL_FORMAT.format(pValue));
209 } else {
210 return String.format("obs=%s markers=%s",
211 DECIMAL_FORMAT.format(lastObservation), markers.toString());
212 }
213 }
214
215
216
217
218 @Override
219 public long getN() {
220 return countOfObservations;
221 }
222
223
224
225
226 @Override
227 public StorelessUnivariateStatistic copy() {
228
229 PSquarePercentile copy = new PSquarePercentile(100d * quantile);
230
231 if (markers != null) {
232 copy.markers = markers.copy();
233 }
234 copy.countOfObservations = countOfObservations;
235 copy.pValue = pValue;
236 copy.initialFive.clear();
237 copy.initialFive.addAll(initialFive);
238
239 return copy;
240 }
241
242
243
244
245
246
247 public double quantile() {
248 return quantile;
249 }
250
251
252
253
254
255 @Override
256 public void clear() {
257 markers = null;
258 initialFive.clear();
259 countOfObservations = 0L;
260 pValue = Double.NaN;
261 }
262
263
264
265
266 @Override
267 public double getResult() {
268 if (Double.compare(quantile, 1d) == 0) {
269 pValue = maximum();
270 } else if (Double.compare(quantile, 0d) == 0) {
271 pValue = minimum();
272 }
273 return pValue;
274 }
275
276
277
278
279 private double maximum() {
280 double val = Double.NaN;
281 if (markers != null) {
282 val = markers.height(PSQUARE_CONSTANT);
283 } else if (!initialFive.isEmpty()) {
284 val = initialFive.get(initialFive.size() - 1);
285 }
286 return val;
287 }
288
289
290
291
292 private double minimum() {
293 double val = Double.NaN;
294 if (markers != null) {
295 val = markers.height(1);
296 } else if (!initialFive.isEmpty()) {
297 val = initialFive.get(0);
298 }
299 return val;
300 }
301
302
303
304
305
306 private static final class Markers implements PSquareMarkers {
307
308 private static final int LOW = 2;
309
310
311 private static final int HIGH = 4;
312
313
314
315
316
317
318 private final Marker[] markerArray;
319
320
321
322
323
324 private transient int k = -1;
325
326
327
328
329
330
331 private Markers(final Marker[] theMarkerArray) {
332 NullArgumentException.check(theMarkerArray);
333 markerArray = theMarkerArray;
334 for (int i = 1; i < PSQUARE_CONSTANT; i++) {
335 markerArray[i].previous(markerArray[i - 1])
336 .next(markerArray[i + 1]).index(i);
337 }
338 markerArray[0].previous(markerArray[0]).next(markerArray[1])
339 .index(0);
340 markerArray[5].previous(markerArray[4]).next(markerArray[5])
341 .index(5);
342 }
343
344
345
346
347
348
349
350 private Markers(final List<Double> initialFive, final double p) {
351 this(createMarkerArray(initialFive, p));
352 }
353
354
355
356
357
358
359
360
361 private static Marker[] createMarkerArray(
362 final List<Double> initialFive, final double p) {
363 final int countObserved =
364 initialFive == null ? -1 : initialFive.size();
365 if (countObserved < PSQUARE_CONSTANT) {
366 throw new InsufficientDataException(
367 LocalizedFormats.INSUFFICIENT_OBSERVED_POINTS_IN_SAMPLE,
368 countObserved, PSQUARE_CONSTANT);
369 }
370 Collections.sort(initialFive);
371 return new Marker[] {
372 new Marker(),
373 new Marker(initialFive.get(0), 1, 0, 1),
374 new Marker(initialFive.get(1), 1 + 2 * p, p / 2, 2),
375 new Marker(initialFive.get(2), 1 + 4 * p, p, 3),
376 new Marker(initialFive.get(3), 3 + 2 * p, (1 + p) / 2, 4),
377 new Marker(initialFive.get(4), 5, 1, 5) };
378 }
379
380
381
382
383 @Override
384 public int hashCode() {
385 return Arrays.deepHashCode(markerArray);
386 }
387
388
389
390
391
392
393
394
395 @Override
396 public boolean equals(Object o) {
397 boolean result = false;
398 if (this == o) {
399 result = true;
400 } else if (o instanceof Markers) {
401 Markers that = (Markers) o;
402 result = Arrays.deepEquals(markerArray, that.markerArray);
403 }
404 return result;
405 }
406
407
408
409
410
411
412
413 @Override
414 public double processDataPoint(final double inputDataPoint) {
415
416
417 final int kthCell = findCellAndUpdateMinMax(inputDataPoint);
418
419
420 incrementPositions(1, kthCell + 1, 5);
421
422
423 updateDesiredPositions();
424
425
426 adjustHeightsOfMarkers();
427
428
429 return getPercentileValue();
430 }
431
432
433
434
435
436
437 @Override
438 public double getPercentileValue() {
439 return height(3);
440 }
441
442
443
444
445
446
447
448
449 private int findCellAndUpdateMinMax(final double observation) {
450 k = -1;
451 if (observation < height(1)) {
452 markerArray[1].markerHeight = observation;
453 k = 1;
454 } else if (observation < height(2)) {
455 k = 1;
456 } else if (observation < height(3)) {
457 k = 2;
458 } else if (observation < height(4)) {
459 k = 3;
460 } else if (observation <= height(5)) {
461 k = 4;
462 } else {
463 markerArray[5].markerHeight = observation;
464 k = 4;
465 }
466 return k;
467 }
468
469
470
471
472 private void adjustHeightsOfMarkers() {
473 for (int i = LOW; i <= HIGH; i++) {
474 estimate(i);
475 }
476 }
477
478
479
480
481 @Override
482 public double estimate(final int index) {
483 if (index < LOW || index > HIGH) {
484 throw new OutOfRangeException(index, LOW, HIGH);
485 }
486 return markerArray[index].estimate();
487 }
488
489
490
491
492
493
494
495
496
497 private void incrementPositions(final int d, final int startIndex,
498 final int endIndex) {
499 for (int i = startIndex; i <= endIndex; i++) {
500 markerArray[i].incrementPosition(d);
501 }
502 }
503
504
505
506
507
508 private void updateDesiredPositions() {
509 for (int i = 1; i < markerArray.length; i++) {
510 markerArray[i].updateDesiredPosition();
511 }
512 }
513
514
515
516
517
518
519
520 @Override
521 public double height(final int markerIndex) {
522 if (markerIndex >= markerArray.length || markerIndex <= 0) {
523 throw new OutOfRangeException(markerIndex, 1, markerArray.length);
524 }
525 return markerArray[markerIndex].markerHeight;
526 }
527
528
529
530
531
532
533 public Markers copy() {
534 return new Markers(new Marker[] {
535 new Marker(),
536 markerArray[1].copy(),
537 markerArray[2].copy(),
538 markerArray[3].copy(),
539 markerArray[4].copy(),
540 markerArray[5].copy()
541 });
542 }
543
544
545
546
547
548
549 @Override
550 public String toString() {
551 return String.format("m1=[%s],m2=[%s],m3=[%s],m4=[%s],m5=[%s]",
552 markerArray[1].toString(), markerArray[2].toString(),
553 markerArray[3].toString(), markerArray[4].toString(),
554 markerArray[5].toString());
555 }
556 }
557
558
559
560
561 private static final class Marker {
562
563
564
565
566 private int index;
567
568
569
570
571
572 private double intMarkerPosition;
573
574
575
576
577
578 private double desiredMarkerPosition;
579
580
581
582
583
584 private double markerHeight;
585
586
587
588
589
590 private double desiredMarkerIncrement;
591
592
593
594
595
596 private transient Marker next;
597
598
599
600
601 private transient Marker previous;
602
603
604
605
606 private final UnivariateInterpolator nonLinear = new NevilleInterpolator();
607
608
609
610
611 private transient UnivariateInterpolator linear = new LinearInterpolator();
612
613
614
615
616 private Marker() {
617 this.next = this.previous = this;
618 }
619
620
621
622
623
624
625
626
627
628 private Marker(double heightOfMarker, double makerPositionDesired,
629 double markerPositionIncrement, double markerPositionNumber) {
630 this();
631 this.markerHeight = heightOfMarker;
632 this.desiredMarkerPosition = makerPositionDesired;
633 this.desiredMarkerIncrement = markerPositionIncrement;
634 this.intMarkerPosition = markerPositionNumber;
635 }
636
637
638
639
640
641
642
643
644 private Marker previous(final Marker previousMarker) {
645 NullArgumentException.check(previousMarker);
646 this.previous = previousMarker;
647 return this;
648 }
649
650
651
652
653
654
655
656
657 private Marker next(final Marker nextMarker) {
658 NullArgumentException.check(nextMarker);
659 this.next = nextMarker;
660 return this;
661 }
662
663
664
665
666
667
668
669 private Marker index(final int indexOfMarker) {
670 this.index = indexOfMarker;
671 return this;
672 }
673
674
675
676
677 private void updateDesiredPosition() {
678 desiredMarkerPosition += desiredMarkerIncrement;
679 }
680
681
682
683
684
685
686 private void incrementPosition(final int d) {
687 intMarkerPosition += d;
688 }
689
690
691
692
693
694
695 private double difference() {
696 return desiredMarkerPosition - intMarkerPosition;
697 }
698
699
700
701
702
703
704 private double estimate() {
705 final double di = difference();
706 final boolean isNextHigher =
707 next.intMarkerPosition - intMarkerPosition > 1;
708 final boolean isPreviousLower =
709 previous.intMarkerPosition - intMarkerPosition < -1;
710
711 if (di >= 1 && isNextHigher || di <= -1 && isPreviousLower) {
712 final int d = di >= 0 ? 1 : -1;
713 final double[] xval =
714 new double[] { previous.intMarkerPosition,
715 intMarkerPosition, next.intMarkerPosition };
716 final double[] yval =
717 new double[] { previous.markerHeight, markerHeight,
718 next.markerHeight };
719 final double xD = intMarkerPosition + d;
720
721 UnivariateFunction univariateFunction =
722 nonLinear.interpolate(xval, yval);
723 markerHeight = univariateFunction.value(xD);
724
725
726 if (isEstimateBad(yval, markerHeight)) {
727 int delta = xD - xval[1] > 0 ? 1 : -1;
728 final double[] xBad =
729 new double[] { xval[1], xval[1 + delta] };
730 final double[] yBad =
731 new double[] { yval[1], yval[1 + delta] };
732 SortInPlace.ASCENDING.apply(xBad, yBad);
733 univariateFunction = linear.interpolate(xBad, yBad);
734 markerHeight = univariateFunction.value(xD);
735 }
736 incrementPosition(d);
737 }
738 return markerHeight;
739 }
740
741
742
743
744
745
746
747
748
749 private boolean isEstimateBad(final double[] y, final double yD) {
750 return yD <= y[0] || yD >= y[2];
751 }
752
753
754
755
756
757
758
759
760
761 @Override
762 public boolean equals(Object o) {
763 boolean result = false;
764 if (this == o) {
765 result = true;
766 } else if (o instanceof Marker) {
767 Marker that = (Marker) o;
768
769 result = Double.compare(markerHeight, that.markerHeight) == 0;
770 result =
771 result &&
772 Double.compare(intMarkerPosition,
773 that.intMarkerPosition) == 0;
774 result =
775 result &&
776 Double.compare(desiredMarkerPosition,
777 that.desiredMarkerPosition) == 0;
778 result =
779 result &&
780 Double.compare(desiredMarkerIncrement,
781 that.desiredMarkerIncrement) == 0;
782
783 result = result && next.index == that.next.index;
784 result = result && previous.index == that.previous.index;
785 }
786 return result;
787 }
788
789
790 @Override
791 public int hashCode() {
792 return Arrays.hashCode(new double[] {markerHeight, intMarkerPosition,
793 desiredMarkerIncrement, desiredMarkerPosition, previous.index, next.index});
794 }
795
796
797
798
799
800
801 public Marker copy() {
802 return new Marker(markerHeight, desiredMarkerPosition, desiredMarkerIncrement, intMarkerPosition);
803 }
804
805
806
807
808 @Override
809 public String toString() {
810 return String.format(
811 "index=%.0f,n=%.0f,np=%.2f,q=%.2f,dn=%.2f,prev=%d,next=%d",
812 (double) index, Precision.round(intMarkerPosition, 0),
813 Precision.round(desiredMarkerPosition, 2),
814 Precision.round(markerHeight, 2),
815 Precision.round(desiredMarkerIncrement, 2), previous.index,
816 next.index);
817 }
818 }
819
820
821
822
823
824
825
826
827 private static final class FixedCapacityList<E> extends ArrayList<E> {
828
829
830
831 private final int capacity;
832
833
834
835
836
837
838
839 FixedCapacityList(final int fixedCapacity) {
840 super(fixedCapacity);
841 this.capacity = fixedCapacity;
842 }
843
844
845
846
847
848
849
850
851 @Override
852 public boolean add(final E e) {
853 return size() < capacity && super.add(e);
854 }
855
856
857
858
859
860
861
862
863
864 @Override
865 public boolean addAll(Collection<? extends E> collection) {
866 boolean isCollectionLess =
867 collection != null &&
868 collection.size() + size() <= capacity;
869 return isCollectionLess && super.addAll(collection);
870 }
871 }
872
873
874
875
876
877
878
879
880 public static PSquareMarkers newMarkers(final List<Double> initialFive, final double p) {
881 return new Markers(initialFive, p);
882 }
883
884
885
886
887
888 interface PSquareMarkers {
889
890
891
892
893
894 double getPercentileValue();
895
896
897
898
899
900
901
902
903 double height(int markerIndex);
904
905
906
907
908
909
910 PSquareMarkers copy();
911
912
913
914
915
916
917
918 double processDataPoint(double inputDataPoint);
919
920
921
922
923
924
925
926
927 double estimate(int index);
928 }
929 }