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