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.legacy.stat.descriptive.rank; 018 019import java.text.DecimalFormat; 020import java.util.ArrayList; 021import java.util.Arrays; 022import java.util.Collection; 023import java.util.Collections; 024import java.util.List; 025 026import org.apache.commons.numbers.core.Precision; 027import org.apache.commons.numbers.arrays.SortInPlace; 028import org.apache.commons.math4.legacy.analysis.UnivariateFunction; 029import org.apache.commons.math4.legacy.analysis.interpolation.LinearInterpolator; 030import org.apache.commons.math4.legacy.analysis.interpolation.NevilleInterpolator; 031import org.apache.commons.math4.legacy.analysis.interpolation.UnivariateInterpolator; 032import org.apache.commons.math4.legacy.exception.InsufficientDataException; 033import org.apache.commons.math4.legacy.exception.OutOfRangeException; 034import org.apache.commons.math4.legacy.exception.NullArgumentException; 035import org.apache.commons.math4.legacy.exception.util.LocalizedFormats; 036import org.apache.commons.math4.legacy.stat.descriptive.AbstractStorelessUnivariateStatistic; 037import org.apache.commons.math4.legacy.stat.descriptive.StorelessUnivariateStatistic; 038 039/** 040 * A {@link StorelessUnivariateStatistic} estimating percentiles using the 041 * <a href="http://www.cs.wustl.edu/~jain/papers/ftp/psqr.pdf">P<SUP>2</SUP></a> 042 * Algorithm as explained by <a href="http://www.cse.wustl.edu/~jain/">Raj 043 * Jain</a> and Imrich Chlamtac in 044 * <a href="http://www.cse.wustl.edu/~jain/papers/psqr.htm">P<SUP>2</SUP> Algorithm 045 * for Dynamic Calculation of Quantiles and Histogram Without Storing 046 * Observations</a>. 047 * <p> 048 * Note: This implementation is not synchronized and produces an approximate 049 * result. For small samples, where data can be stored and processed in memory, 050 * {@link Percentile} should be used.</p> 051 */ 052public class PSquarePercentile extends AbstractStorelessUnivariateStatistic 053 implements StorelessUnivariateStatistic { 054 055 /** 056 * The maximum array size used for psquare algorithm. 057 */ 058 private static final int PSQUARE_CONSTANT = 5; 059 060 /** 061 * A Default quantile needed in case if user prefers to use default no 062 * argument constructor. 063 */ 064 private static final double DEFAULT_QUANTILE_DESIRED = 50d; 065 066 /** 067 * A decimal formatter for print convenience. 068 */ 069 private static final DecimalFormat DECIMAL_FORMAT = new DecimalFormat("00.00"); 070 071 /** 072 * Initial list of 5 numbers corresponding to 5 markers. <b>NOTE:</b>watch 073 * out for the add methods that are overloaded. 074 */ 075 private final List<Double> initialFive = new FixedCapacityList<>(PSQUARE_CONSTANT); 076 077 /** 078 * The quantile needed should be in range of 0-1. The constructor 079 * {@link #PSquarePercentile(double)} ensures that passed in percentile is 080 * divided by 100. 081 */ 082 private final double quantile; 083 084 /** 085 * lastObservation is the last observation value/input sample. No need to 086 * serialize 087 */ 088 private transient double lastObservation; 089 090 /** 091 * Markers is the marker collection object which comes to effect. 092 * only after 5 values are inserted 093 */ 094 private PSquareMarkers markers; 095 096 /** 097 * Computed p value (i,e percentile value of data set hither to received). 098 */ 099 private double pValue = Double.NaN; 100 101 /** 102 * Counter to count the values/observations accepted into this data set. 103 */ 104 private long countOfObservations; 105 106 /** 107 * Constructs a PSquarePercentile with the specific percentile value. 108 * @param p the percentile 109 * @throws OutOfRangeException if p is not greater than 0 and less 110 * than or equal to 100 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;// always set it within (0,1] 117 } 118 119 /** 120 * Default constructor that assumes a {@link #DEFAULT_QUANTILE_DESIRED 121 * default quantile} needed. 122 */ 123 PSquarePercentile() { 124 this(DEFAULT_QUANTILE_DESIRED); 125 } 126 127 /** 128 * {@inheritDoc} 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 * Returns true iff {@code o} is a {@code PSquarePercentile} returning the. 141 * same values as this for {@code getResult()} and {@code getN()} and also 142 * having equal markers 143 * 144 * @param o object to compare 145 * @return true if {@code o} is a {@code PSquarePercentile} with 146 * equivalent internal state 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 // markers as in the case of first 159 // five observations 160 result = result && getN() == that.getN(); 161 } 162 return result; 163 } 164 165 /** 166 * {@inheritDoc}The internal state updated due to the new value in this 167 * context is basically of the marker positions and computation of the 168 * approximate quantile. 169 * 170 * @param observation the observation currently being added. 171 */ 172 @Override 173 public void increment(final double observation) { 174 // Increment counter 175 countOfObservations++; 176 177 // Store last observation 178 this.lastObservation = observation; 179 180 // 0. Use Brute force for <5 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 // 1. Initialize once after 5th observation 190 markers = newMarkers(initialFive, quantile); 191 } 192 // 2. process a Data Point and return pValue 193 pValue = markers.processDataPoint(observation); 194 } 195 196 /** 197 * Returns a string containing the last observation, the current estimate 198 * of the quantile and all markers. 199 * 200 * @return string representation of state data 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 * {@inheritDoc} 217 */ 218 @Override 219 public long getN() { 220 return countOfObservations; 221 } 222 223 /** 224 * {@inheritDoc} 225 */ 226 @Override 227 public StorelessUnivariateStatistic copy() { 228 // multiply quantile by 100 now as anyway constructor divides it by 100 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 * Returns the quantile estimated by this statistic in the range [0.0-1.0]. 244 * 245 * @return quantile estimated by {@link #getResult()} 246 */ 247 public double quantile() { 248 return quantile; 249 } 250 251 /** 252 * {@inheritDoc}. This basically clears all the markers, the 253 * initialFive list and sets countOfObservations to 0. 254 */ 255 @Override 256 public void clear() { 257 markers = null; 258 initialFive.clear(); 259 countOfObservations = 0L; 260 pValue = Double.NaN; 261 } 262 263 /** 264 * {@inheritDoc} 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 * @return maximum in the data set added to this statistic 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 * @return minimum in the data set added to this statistic 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 * Markers is an encapsulation of the five markers/buckets as indicated in 304 * the original works. 305 */ 306 private static final class Markers implements PSquareMarkers { 307 /** Low marker index. */ 308 private static final int LOW = 2; 309 310 /** High marker index. */ 311 private static final int HIGH = 4; 312 313 /** 314 * Array of 5+1 Markers (The first marker is dummy just so we. 315 * can match the rest of indexes [1-5] indicated in the original works 316 * which follows unit based index) 317 */ 318 private final Marker[] markerArray; 319 320 /** 321 * Kth cell belonging to [1-5] of the markerArray. No need for 322 * this to be serialized 323 */ 324 private transient int k = -1; 325 326 /** 327 * Constructor. 328 * 329 * @param theMarkerArray marker array to be used 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 * Constructor. 346 * 347 * @param initialFive elements required to build Marker 348 * @param p quantile required to be computed 349 */ 350 private Markers(final List<Double> initialFive, final double p) { 351 this(createMarkerArray(initialFive, p)); 352 } 353 354 /** 355 * Creates a marker array using initial five elements and a quantile. 356 * 357 * @param initialFive list of initial five elements 358 * @param p the pth quantile 359 * @return Marker array 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(),// Null 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 * {@inheritDoc} 382 */ 383 @Override 384 public int hashCode() { 385 return Arrays.deepHashCode(markerArray); 386 } 387 388 /** 389 * {@inheritDoc}.This equals method basically checks for marker array to 390 * be deep equals. 391 * 392 * @param o is the other object 393 * @return true if the object compares with this object are equivalent 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 * Process a data point. 409 * 410 * @param inputDataPoint is the data point passed 411 * @return computed percentile 412 */ 413 @Override 414 public double processDataPoint(final double inputDataPoint) { 415 416 // 1. Find cell and update minima and maxima 417 final int kthCell = findCellAndUpdateMinMax(inputDataPoint); 418 419 // 2. Increment positions 420 incrementPositions(1, kthCell + 1, 5); 421 422 // 2a. Update desired position with increments 423 updateDesiredPositions(); 424 425 // 3. Adjust heights of m[2-4] if necessary 426 adjustHeightsOfMarkers(); 427 428 // 4. Return percentile 429 return getPercentileValue(); 430 } 431 432 /** 433 * Returns the percentile computed thus far. 434 * 435 * @return height of mid point marker 436 */ 437 @Override 438 public double getPercentileValue() { 439 return height(3); 440 } 441 442 /** 443 * Finds the cell where the input observation / value fits. 444 * 445 * @param observation the input value to be checked for 446 * @return kth cell (of the markers ranging from 1-5) where observed 447 * sample fits 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 * Adjust marker heights by setting quantile estimates to middle markers. 471 */ 472 private void adjustHeightsOfMarkers() { 473 for (int i = LOW; i <= HIGH; i++) { 474 estimate(i); 475 } 476 } 477 478 /** 479 * {@inheritDoc} 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 * Increment positions by d. Refer to algorithm paper for the 491 * definition of d. 492 * 493 * @param d The increment value for the position 494 * @param startIndex start index of the marker array 495 * @param endIndex end index of the marker array 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 * Desired positions incremented by bucket width. The bucket width is 506 * basically the desired increments. 507 */ 508 private void updateDesiredPositions() { 509 for (int i = 1; i < markerArray.length; i++) { 510 markerArray[i].updateDesiredPosition(); 511 } 512 } 513 514 /** 515 * Return marker height given index. 516 * 517 * @param markerIndex index of marker within (1,6) 518 * @return marker height 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 * Copy markers. 530 * 531 * @return a new instance. 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 * Returns string representation of the Marker array. 546 * 547 * @return Markers as a string 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 * The class modeling the attributes of the marker of the P-square algorithm. 560 */ 561 private static final class Marker { 562 /** 563 * The marker index which is just a serial number for the marker in the 564 * marker array of 5+1. 565 */ 566 private int index; 567 568 /** 569 * The integral marker position. Refer to the variable n in the original 570 * works. 571 */ 572 private double intMarkerPosition; 573 574 /** 575 * Desired marker position. Refer to the variable n' in the original 576 * works. 577 */ 578 private double desiredMarkerPosition; 579 580 /** 581 * Marker height or the quantile. Refer to the variable q in the 582 * original works. 583 */ 584 private double markerHeight; 585 586 /** 587 * Desired marker increment. Refer to the variable dn' in the original 588 * works. 589 */ 590 private double desiredMarkerIncrement; 591 592 /** 593 * Next and previous markers for easy linked navigation in loops. this 594 * is not serialized as they can be rebuilt during deserialization. 595 */ 596 private transient Marker next; 597 598 /** 599 * The previous marker links. 600 */ 601 private transient Marker previous; 602 603 /** 604 * Nonlinear interpolator. 605 */ 606 private final UnivariateInterpolator nonLinear = new NevilleInterpolator(); 607 608 /** 609 * Linear interpolator which is not serializable. 610 */ 611 private transient UnivariateInterpolator linear = new LinearInterpolator(); 612 613 /** 614 * Default constructor. 615 */ 616 private Marker() { 617 this.next = this.previous = this; 618 } 619 620 /** 621 * Constructor of the marker with parameters. 622 * 623 * @param heightOfMarker represent the quantile value 624 * @param makerPositionDesired represent the desired marker position 625 * @param markerPositionIncrement represent increments for position 626 * @param markerPositionNumber represent the position number of marker 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 * Sets the previous marker. 639 * 640 * @param previousMarker the previous marker to the current marker in 641 * the array of markers 642 * @return this instance 643 */ 644 private Marker previous(final Marker previousMarker) { 645 NullArgumentException.check(previousMarker); 646 this.previous = previousMarker; 647 return this; 648 } 649 650 /** 651 * Sets the next marker. 652 * 653 * @param nextMarker the next marker to the current marker in the array 654 * of markers 655 * @return this instance 656 */ 657 private Marker next(final Marker nextMarker) { 658 NullArgumentException.check(nextMarker); 659 this.next = nextMarker; 660 return this; 661 } 662 663 /** 664 * Sets the index of the marker. 665 * 666 * @param indexOfMarker the array index of the marker in marker array 667 * @return this instance 668 */ 669 private Marker index(final int indexOfMarker) { 670 this.index = indexOfMarker; 671 return this; 672 } 673 674 /** 675 * Update desired Position with increment. 676 */ 677 private void updateDesiredPosition() { 678 desiredMarkerPosition += desiredMarkerIncrement; 679 } 680 681 /** 682 * Increment Position by d. 683 * 684 * @param d a delta value to increment 685 */ 686 private void incrementPosition(final int d) { 687 intMarkerPosition += d; 688 } 689 690 /** 691 * Difference between desired and actual position. 692 * 693 * @return difference between desired and actual position 694 */ 695 private double difference() { 696 return desiredMarkerPosition - intMarkerPosition; 697 } 698 699 /** 700 * Estimate the quantile for the current marker. 701 * 702 * @return estimated quantile 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 // If parabolic estimate is bad then turn linear 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);// since d can be +/- 1 733 univariateFunction = linear.interpolate(xBad, yBad); 734 markerHeight = univariateFunction.value(xD); 735 } 736 incrementPosition(d); 737 } 738 return markerHeight; 739 } 740 741 /** 742 * Check if parabolic/nonlinear estimate is bad by checking if the 743 * ordinate found is beyond the y[0] and y[2]. 744 * 745 * @param y the array to get the bounds 746 * @param yD the estimate 747 * @return true if yD is a bad estimate 748 */ 749 private boolean isEstimateBad(final double[] y, final double yD) { 750 return yD <= y[0] || yD >= y[2]; 751 } 752 753 /** 754 * {@inheritDoc}<i>This equals method checks for marker attributes and 755 * as well checks if navigation pointers (next and previous) are the same 756 * between this and passed in object</i> 757 * 758 * @param o Other object 759 * @return true if this equals passed in other object o 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 /** {@inheritDoc} */ 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 * Copy this instance. 798 * 799 * @return a new instance. 800 */ 801 public Marker copy() { 802 return new Marker(markerHeight, desiredMarkerPosition, desiredMarkerIncrement, intMarkerPosition); 803 } 804 805 /** 806 * {@inheritDoc} 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 * A simple fixed capacity list that has an upper bound to growth. 822 * Once its capacity is reached, {@code add} is a no-op, returning 823 * {@code false}. 824 * 825 * @param <E> type for fixed capacity list 826 */ 827 private static class FixedCapacityList<E> extends ArrayList<E> { 828 /** 829 * Capacity of the list. 830 */ 831 private final int capacity; 832 833 /** 834 * This constructor constructs the list with given capacity and as well. 835 * as stores the capacity 836 * 837 * @param fixedCapacity the capacity to be fixed for this list 838 */ 839 FixedCapacityList(final int fixedCapacity) { 840 super(fixedCapacity); 841 this.capacity = fixedCapacity; 842 } 843 844 /** 845 * {@inheritDoc} In addition it checks if the {@link #size()} returns a 846 * size that is within capacity and if true it adds; otherwise the list 847 * contents are unchanged and {@code false} is returned. 848 * 849 * @return true if addition is successful and false otherwise 850 */ 851 @Override 852 public boolean add(final E e) { 853 return size() < capacity && super.add(e); 854 } 855 856 /** 857 * {@inheritDoc} In addition it checks if the sum of Collection size and 858 * this instance's {@link #size()} returns a value that is within 859 * capacity and if true it adds the collection; otherwise the list 860 * contents are unchanged and {@code false} is returned. 861 * 862 * @return true if addition is successful and false otherwise 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 * A creation method to build Markers. 875 * 876 * @param initialFive list of initial five elements 877 * @param p the quantile desired 878 * @return an instance of PSquareMarkers 879 */ 880 public static PSquareMarkers newMarkers(final List<Double> initialFive, final double p) { 881 return new Markers(initialFive, p); 882 } 883 884 /** 885 * An interface that encapsulates abstractions of the 886 * P-square algorithm markers as is explained in the original works. 887 */ 888 interface PSquareMarkers { // Package-private for unit testing. 889 /** 890 * Returns Percentile value computed thus far. 891 * 892 * @return percentile 893 */ 894 double getPercentileValue(); 895 896 /** 897 * Returns the marker height (or percentile) of a given marker index. 898 * 899 * @param markerIndex is the index of marker in the marker array 900 * @return percentile value of the marker index passed 901 * @throws OutOfRangeException in case the index is not within [1-5] 902 */ 903 double height(int markerIndex); 904 905 /** 906 * Copy factory. 907 * 908 * @return a new instance 909 */ 910 PSquareMarkers copy(); 911 912 /** 913 * Process a data point by moving the marker heights based on estimator. 914 * 915 * @param inputDataPoint is the data point passed 916 * @return computed percentile 917 */ 918 double processDataPoint(double inputDataPoint); 919 920 /** 921 * An Estimate of the percentile value of a given Marker. 922 * 923 * @param index the marker's index in the array of markers 924 * @return percentile estimate 925 * @throws OutOfRangeException in case if index is not within [1-5] 926 */ 927 double estimate(int index); 928 } 929}