diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/stat/descriptive/rank/PSquarePercentile.java')
-rw-r--r-- | src/main/java/org/apache/commons/math3/stat/descriptive/rank/PSquarePercentile.java | 997 |
1 files changed, 997 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/stat/descriptive/rank/PSquarePercentile.java b/src/main/java/org/apache/commons/math3/stat/descriptive/rank/PSquarePercentile.java new file mode 100644 index 0000000..b8bc274 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/stat/descriptive/rank/PSquarePercentile.java @@ -0,0 +1,997 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.stat.descriptive.rank; + +import java.io.IOException; +import java.io.ObjectInputStream; +import java.io.Serializable; +import java.text.DecimalFormat; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.List; + +import org.apache.commons.math3.analysis.UnivariateFunction; +import org.apache.commons.math3.analysis.interpolation.LinearInterpolator; +import org.apache.commons.math3.analysis.interpolation.NevilleInterpolator; +import org.apache.commons.math3.analysis.interpolation.UnivariateInterpolator; +import org.apache.commons.math3.exception.InsufficientDataException; +import org.apache.commons.math3.exception.OutOfRangeException; +import org.apache.commons.math3.exception.util.LocalizedFormats; +import org.apache.commons.math3.stat.descriptive.AbstractStorelessUnivariateStatistic; +import org.apache.commons.math3.stat.descriptive.StorelessUnivariateStatistic; +import org.apache.commons.math3.util.MathArrays; +import org.apache.commons.math3.util.MathUtils; +import org.apache.commons.math3.util.Precision; + +/** + * A {@link StorelessUnivariateStatistic} estimating percentiles using the + * <ahref=http://www.cs.wustl.edu/~jain/papers/ftp/psqr.pdf>P<SUP>2</SUP></a> + * Algorithm as explained by <a href=http://www.cse.wustl.edu/~jain/>Raj + * Jain</a> and Imrich Chlamtac in + * <a href=http://www.cse.wustl.edu/~jain/papers/psqr.htm>P<SUP>2</SUP> Algorithm + * for Dynamic Calculation of Quantiles and Histogram Without Storing + * Observations</a>. + * <p> + * Note: This implementation is not synchronized and produces an approximate + * result. For small samples, where data can be stored and processed in memory, + * {@link Percentile} should be used.</p> + * + */ +public class PSquarePercentile extends AbstractStorelessUnivariateStatistic + implements StorelessUnivariateStatistic, Serializable { + + /** + * The maximum array size used for psquare algorithm + */ + private static final int PSQUARE_CONSTANT = 5; + + /** + * A Default quantile needed in case if user prefers to use default no + * argument constructor. + */ + private static final double DEFAULT_QUANTILE_DESIRED = 50d; + + /** + * Serial ID + */ + private static final long serialVersionUID = 2283912083175715479L; + + /** + * A decimal formatter for print convenience + */ + private static final DecimalFormat DECIMAL_FORMAT = new DecimalFormat( + "00.00"); + + /** + * Initial list of 5 numbers corresponding to 5 markers. <b>NOTE:</b>watch + * out for the add methods that are overloaded + */ + private final List<Double> initialFive = new FixedCapacityList<Double>( + PSQUARE_CONSTANT); + + /** + * The quantile needed should be in range of 0-1. The constructor + * {@link #PSquarePercentile(double)} ensures that passed in percentile is + * divided by 100. + */ + private final double quantile; + + /** + * lastObservation is the last observation value/input sample. No need to + * serialize + */ + private transient double lastObservation; + + /** + * Markers is the marker collection object which comes to effect + * only after 5 values are inserted + */ + private PSquareMarkers markers = null; + + /** + * Computed p value (i,e percentile value of data set hither to received) + */ + private double pValue = Double.NaN; + + /** + * Counter to count the values/observations accepted into this data set + */ + private long countOfObservations; + + /** + * Constructs a PSquarePercentile with the specific percentile value. + * @param p the percentile + * @throws OutOfRangeException if p is not greater than 0 and less + * than or equal to 100 + */ + public PSquarePercentile(final double p) { + if (p > 100 || p < 0) { + throw new OutOfRangeException(LocalizedFormats.OUT_OF_RANGE, + p, 0, 100); + } + this.quantile = p / 100d;// always set it within (0,1] + } + + /** + * Default constructor that assumes a {@link #DEFAULT_QUANTILE_DESIRED + * default quantile} needed + */ + PSquarePercentile() { + this(DEFAULT_QUANTILE_DESIRED); + } + + /** + * {@inheritDoc} + */ + @Override + public int hashCode() { + double result = getResult(); + result = Double.isNaN(result) ? 37 : result; + final double markersHash = markers == null ? 0 : markers.hashCode(); + final double[] toHash = {result, quantile, markersHash, countOfObservations}; + return Arrays.hashCode(toHash); + } + + /** + * Returns true iff {@code o} is a {@code PSquarePercentile} returning the + * same values as this for {@code getResult()} and {@code getN()} and also + * having equal markers + * + * @param o object to compare + * @return true if {@code o} is a {@code PSquarePercentile} with + * equivalent internal state + */ + @Override + public boolean equals(Object o) { + boolean result = false; + if (this == o) { + result = true; + } else if (o != null && o instanceof PSquarePercentile) { + PSquarePercentile that = (PSquarePercentile) o; + boolean isNotNull = markers != null && that.markers != null; + boolean isNull = markers == null && that.markers == null; + result = isNotNull ? markers.equals(that.markers) : isNull; + // markers as in the case of first + // five observations + result = result && getN() == that.getN(); + } + return result; + } + + /** + * {@inheritDoc}The internal state updated due to the new value in this + * context is basically of the marker positions and computation of the + * approximate quantile. + * + * @param observation the observation currently being added. + */ + @Override + public void increment(final double observation) { + // Increment counter + countOfObservations++; + + // Store last observation + this.lastObservation = observation; + + // 0. Use Brute force for <5 + if (markers == null) { + if (initialFive.add(observation)) { + Collections.sort(initialFive); + pValue = + initialFive + .get((int) (quantile * (initialFive.size() - 1))); + return; + } + // 1. Initialize once after 5th observation + markers = newMarkers(initialFive, quantile); + } + // 2. process a Data Point and return pValue + pValue = markers.processDataPoint(observation); + } + + /** + * Returns a string containing the last observation, the current estimate + * of the quantile and all markers. + * + * @return string representation of state data + */ + @Override + public String toString() { + + if (markers == null) { + return String.format("obs=%s pValue=%s", + DECIMAL_FORMAT.format(lastObservation), + DECIMAL_FORMAT.format(pValue)); + } else { + return String.format("obs=%s markers=%s", + DECIMAL_FORMAT.format(lastObservation), markers.toString()); + } + } + + /** + * {@inheritDoc} + */ + public long getN() { + return countOfObservations; + } + + /** + * {@inheritDoc} + */ + @Override + public StorelessUnivariateStatistic copy() { + // multiply quantile by 100 now as anyway constructor divides it by 100 + PSquarePercentile copy = new PSquarePercentile(100d * quantile); + + if (markers != null) { + copy.markers = (PSquareMarkers) markers.clone(); + } + copy.countOfObservations = countOfObservations; + copy.pValue = pValue; + copy.initialFive.clear(); + copy.initialFive.addAll(initialFive); + return copy; + } + + /** + * Returns the quantile estimated by this statistic in the range [0.0-1.0] + * + * @return quantile estimated by {@link #getResult()} + */ + public double quantile() { + return quantile; + } + + /** + * {@inheritDoc}. This basically clears all the markers, the + * initialFive list and sets countOfObservations to 0. + */ + @Override + public void clear() { + markers = null; + initialFive.clear(); + countOfObservations = 0L; + pValue = Double.NaN; + } + + /** + * {@inheritDoc} + */ + @Override + public double getResult() { + if (Double.compare(quantile, 1d) == 0) { + pValue = maximum(); + } else if (Double.compare(quantile, 0d) == 0) { + pValue = minimum(); + } + return pValue; + } + + /** + * @return maximum in the data set added to this statistic + */ + private double maximum() { + double val = Double.NaN; + if (markers != null) { + val = markers.height(PSQUARE_CONSTANT); + } else if (!initialFive.isEmpty()) { + val = initialFive.get(initialFive.size() - 1); + } + return val; + } + + /** + * @return minimum in the data set added to this statistic + */ + private double minimum() { + double val = Double.NaN; + if (markers != null) { + val = markers.height(1); + } else if (!initialFive.isEmpty()) { + val = initialFive.get(0); + } + return val; + } + + /** + * Markers is an encapsulation of the five markers/buckets as indicated in + * the original works. + */ + private static class Markers implements PSquareMarkers, Serializable { + /** + * Serial version id + */ + private static final long serialVersionUID = 1L; + + /** Low marker index */ + private static final int LOW = 2; + + /** High marker index */ + private static final int HIGH = 4; + + /** + * Array of 5+1 Markers (The first marker is dummy just so we + * can match the rest of indexes [1-5] indicated in the original works + * which follows unit based index) + */ + private final Marker[] markerArray; + + /** + * Kth cell belonging to [1-5] of the markerArray. No need for + * this to be serialized + */ + private transient int k = -1; + + /** + * Constructor + * + * @param theMarkerArray marker array to be used + */ + private Markers(final Marker[] theMarkerArray) { + MathUtils.checkNotNull(theMarkerArray); + markerArray = theMarkerArray; + for (int i = 1; i < PSQUARE_CONSTANT; i++) { + markerArray[i].previous(markerArray[i - 1]) + .next(markerArray[i + 1]).index(i); + } + markerArray[0].previous(markerArray[0]).next(markerArray[1]) + .index(0); + markerArray[5].previous(markerArray[4]).next(markerArray[5]) + .index(5); + } + + /** + * Constructor + * + * @param initialFive elements required to build Marker + * @param p quantile required to be computed + */ + private Markers(final List<Double> initialFive, final double p) { + this(createMarkerArray(initialFive, p)); + } + + /** + * Creates a marker array using initial five elements and a quantile + * + * @param initialFive list of initial five elements + * @param p the pth quantile + * @return Marker array + */ + private static Marker[] createMarkerArray( + final List<Double> initialFive, final double p) { + final int countObserved = + initialFive == null ? -1 : initialFive.size(); + if (countObserved < PSQUARE_CONSTANT) { + throw new InsufficientDataException( + LocalizedFormats.INSUFFICIENT_OBSERVED_POINTS_IN_SAMPLE, + countObserved, PSQUARE_CONSTANT); + } + Collections.sort(initialFive); + return new Marker[] { + new Marker(),// Null Marker + new Marker(initialFive.get(0), 1, 0, 1), + new Marker(initialFive.get(1), 1 + 2 * p, p / 2, 2), + new Marker(initialFive.get(2), 1 + 4 * p, p, 3), + new Marker(initialFive.get(3), 3 + 2 * p, (1 + p) / 2, 4), + new Marker(initialFive.get(4), 5, 1, 5) }; + } + + /** + * {@inheritDoc} + */ + @Override + public int hashCode() { + return Arrays.deepHashCode(markerArray); + } + + /** + * {@inheritDoc}.This equals method basically checks for marker array to + * be deep equals. + * + * @param o is the other object + * @return true if the object compares with this object are equivalent + */ + @Override + public boolean equals(Object o) { + boolean result = false; + if (this == o) { + result = true; + } else if (o != null && o instanceof Markers) { + Markers that = (Markers) o; + result = Arrays.deepEquals(markerArray, that.markerArray); + } + return result; + } + + /** + * Process a data point + * + * @param inputDataPoint is the data point passed + * @return computed percentile + */ + public double processDataPoint(final double inputDataPoint) { + + // 1. Find cell and update minima and maxima + final int kthCell = findCellAndUpdateMinMax(inputDataPoint); + + // 2. Increment positions + incrementPositions(1, kthCell + 1, 5); + + // 2a. Update desired position with increments + updateDesiredPositions(); + + // 3. Adjust heights of m[2-4] if necessary + adjustHeightsOfMarkers(); + + // 4. Return percentile + return getPercentileValue(); + } + + /** + * Returns the percentile computed thus far. + * + * @return height of mid point marker + */ + public double getPercentileValue() { + return height(3); + } + + /** + * Finds the cell where the input observation / value fits. + * + * @param observation the input value to be checked for + * @return kth cell (of the markers ranging from 1-5) where observed + * sample fits + */ + private int findCellAndUpdateMinMax(final double observation) { + k = -1; + if (observation < height(1)) { + markerArray[1].markerHeight = observation; + k = 1; + } else if (observation < height(2)) { + k = 1; + } else if (observation < height(3)) { + k = 2; + } else if (observation < height(4)) { + k = 3; + } else if (observation <= height(5)) { + k = 4; + } else { + markerArray[5].markerHeight = observation; + k = 4; + } + return k; + } + + /** + * Adjust marker heights by setting quantile estimates to middle markers. + */ + private void adjustHeightsOfMarkers() { + for (int i = LOW; i <= HIGH; i++) { + estimate(i); + } + } + + /** + * {@inheritDoc} + */ + public double estimate(final int index) { + if (index < LOW || index > HIGH) { + throw new OutOfRangeException(index, LOW, HIGH); + } + return markerArray[index].estimate(); + } + + /** + * Increment positions by d. Refer to algorithm paper for the + * definition of d. + * + * @param d The increment value for the position + * @param startIndex start index of the marker array + * @param endIndex end index of the marker array + */ + private void incrementPositions(final int d, final int startIndex, + final int endIndex) { + for (int i = startIndex; i <= endIndex; i++) { + markerArray[i].incrementPosition(d); + } + } + + /** + * Desired positions incremented by bucket width. The bucket width is + * basically the desired increments. + */ + private void updateDesiredPositions() { + for (int i = 1; i < markerArray.length; i++) { + markerArray[i].updateDesiredPosition(); + } + } + + /** + * Sets previous and next markers after default read is done. + * + * @param anInputStream the input stream to be deserialized + * @throws ClassNotFoundException thrown when a desired class not found + * @throws IOException thrown due to any io errors + */ + private void readObject(ObjectInputStream anInputStream) + throws ClassNotFoundException, IOException { + // always perform the default de-serialization first + anInputStream.defaultReadObject(); + // Build links + for (int i = 1; i < PSQUARE_CONSTANT; i++) { + markerArray[i].previous(markerArray[i - 1]) + .next(markerArray[i + 1]).index(i); + } + markerArray[0].previous(markerArray[0]).next(markerArray[1]) + .index(0); + markerArray[5].previous(markerArray[4]).next(markerArray[5]) + .index(5); + } + + /** + * Return marker height given index + * + * @param markerIndex index of marker within (1,6) + * @return marker height + */ + public double height(final int markerIndex) { + if (markerIndex >= markerArray.length || markerIndex <= 0) { + throw new OutOfRangeException(markerIndex, 1, + markerArray.length); + } + return markerArray[markerIndex].markerHeight; + } + + /** + * {@inheritDoc}.Clone Markers + * + * @return cloned object + */ + @Override + public Object clone() { + return new Markers(new Marker[] { new Marker(), + (Marker) markerArray[1].clone(), + (Marker) markerArray[2].clone(), + (Marker) markerArray[3].clone(), + (Marker) markerArray[4].clone(), + (Marker) markerArray[5].clone() }); + + } + + /** + * Returns string representation of the Marker array. + * + * @return Markers as a string + */ + @Override + public String toString() { + return String.format("m1=[%s],m2=[%s],m3=[%s],m4=[%s],m5=[%s]", + markerArray[1].toString(), markerArray[2].toString(), + markerArray[3].toString(), markerArray[4].toString(), + markerArray[5].toString()); + } + + } + + /** + * The class modeling the attributes of the marker of the P-square algorithm + */ + private static class Marker implements Serializable, Cloneable { + + /** + * Serial Version ID + */ + private static final long serialVersionUID = -3575879478288538431L; + + /** + * The marker index which is just a serial number for the marker in the + * marker array of 5+1. + */ + private int index; + + /** + * The integral marker position. Refer to the variable n in the original + * works. + */ + private double intMarkerPosition; + + /** + * Desired marker position. Refer to the variable n' in the original + * works. + */ + private double desiredMarkerPosition; + + /** + * Marker height or the quantile. Refer to the variable q in the + * original works. + */ + private double markerHeight; + + /** + * Desired marker increment. Refer to the variable dn' in the original + * works. + */ + private double desiredMarkerIncrement; + + /** + * Next and previous markers for easy linked navigation in loops. this + * is not serialized as they can be rebuilt during deserialization. + */ + private transient Marker next; + + /** + * The previous marker links + */ + private transient Marker previous; + + /** + * Nonlinear interpolator + */ + private final UnivariateInterpolator nonLinear = + new NevilleInterpolator(); + + /** + * Linear interpolator which is not serializable + */ + private transient UnivariateInterpolator linear = + new LinearInterpolator(); + + /** + * Default constructor + */ + private Marker() { + this.next = this.previous = this; + } + + /** + * Constructor of the marker with parameters + * + * @param heightOfMarker represent the quantile value + * @param makerPositionDesired represent the desired marker position + * @param markerPositionIncrement represent increments for position + * @param markerPositionNumber represent the position number of marker + */ + private Marker(double heightOfMarker, double makerPositionDesired, + double markerPositionIncrement, double markerPositionNumber) { + this(); + this.markerHeight = heightOfMarker; + this.desiredMarkerPosition = makerPositionDesired; + this.desiredMarkerIncrement = markerPositionIncrement; + this.intMarkerPosition = markerPositionNumber; + } + + /** + * Sets the previous marker. + * + * @param previousMarker the previous marker to the current marker in + * the array of markers + * @return this instance + */ + private Marker previous(final Marker previousMarker) { + MathUtils.checkNotNull(previousMarker); + this.previous = previousMarker; + return this; + } + + /** + * Sets the next marker. + * + * @param nextMarker the next marker to the current marker in the array + * of markers + * @return this instance + */ + private Marker next(final Marker nextMarker) { + MathUtils.checkNotNull(nextMarker); + this.next = nextMarker; + return this; + } + + /** + * Sets the index of the marker. + * + * @param indexOfMarker the array index of the marker in marker array + * @return this instance + */ + private Marker index(final int indexOfMarker) { + this.index = indexOfMarker; + return this; + } + + /** + * Update desired Position with increment. + */ + private void updateDesiredPosition() { + desiredMarkerPosition += desiredMarkerIncrement; + } + + /** + * Increment Position by d. + * + * @param d a delta value to increment + */ + private void incrementPosition(final int d) { + intMarkerPosition += d; + } + + /** + * Difference between desired and actual position + * + * @return difference between desired and actual position + */ + private double difference() { + return desiredMarkerPosition - intMarkerPosition; + } + + /** + * Estimate the quantile for the current marker. + * + * @return estimated quantile + */ + private double estimate() { + final double di = difference(); + final boolean isNextHigher = + next.intMarkerPosition - intMarkerPosition > 1; + final boolean isPreviousLower = + previous.intMarkerPosition - intMarkerPosition < -1; + + if (di >= 1 && isNextHigher || di <= -1 && isPreviousLower) { + final int d = di >= 0 ? 1 : -1; + final double[] xval = + new double[] { previous.intMarkerPosition, + intMarkerPosition, next.intMarkerPosition }; + final double[] yval = + new double[] { previous.markerHeight, markerHeight, + next.markerHeight }; + final double xD = intMarkerPosition + d; + + UnivariateFunction univariateFunction = + nonLinear.interpolate(xval, yval); + markerHeight = univariateFunction.value(xD); + + // If parabolic estimate is bad then turn linear + if (isEstimateBad(yval, markerHeight)) { + int delta = xD - xval[1] > 0 ? 1 : -1; + final double[] xBad = + new double[] { xval[1], xval[1 + delta] }; + final double[] yBad = + new double[] { yval[1], yval[1 + delta] }; + MathArrays.sortInPlace(xBad, yBad);// since d can be +/- 1 + univariateFunction = linear.interpolate(xBad, yBad); + markerHeight = univariateFunction.value(xD); + } + incrementPosition(d); + } + return markerHeight; + } + + /** + * Check if parabolic/nonlinear estimate is bad by checking if the + * ordinate found is beyond the y[0] and y[2]. + * + * @param y the array to get the bounds + * @param yD the estimate + * @return true if yD is a bad estimate + */ + private boolean isEstimateBad(final double[] y, final double yD) { + return yD <= y[0] || yD >= y[2]; + } + + /** + * {@inheritDoc}<i>This equals method checks for marker attributes and + * as well checks if navigation pointers (next and previous) are the same + * between this and passed in object</i> + * + * @param o Other object + * @return true if this equals passed in other object o + */ + @Override + public boolean equals(Object o) { + boolean result = false; + if (this == o) { + result = true; + } else if (o != null && o instanceof Marker) { + Marker that = (Marker) o; + + result = Double.compare(markerHeight, that.markerHeight) == 0; + result = + result && + Double.compare(intMarkerPosition, + that.intMarkerPosition) == 0; + result = + result && + Double.compare(desiredMarkerPosition, + that.desiredMarkerPosition) == 0; + result = + result && + Double.compare(desiredMarkerIncrement, + that.desiredMarkerIncrement) == 0; + + result = result && next.index == that.next.index; + result = result && previous.index == that.previous.index; + } + return result; + } + + /** {@inheritDoc} */ + @Override + public int hashCode() { + return Arrays.hashCode(new double[] {markerHeight, intMarkerPosition, + desiredMarkerIncrement, desiredMarkerPosition, previous.index, next.index}); + } + + /** + * Read Object to deserialize. + * + * @param anInstream Stream Object data + * @throws IOException thrown for IO Errors + * @throws ClassNotFoundException thrown for class not being found + */ + private void readObject(ObjectInputStream anInstream) + throws ClassNotFoundException, IOException { + anInstream.defaultReadObject(); + previous=next=this; + linear = new LinearInterpolator(); + } + + /** + * Clone this instance. + * + * @return cloned marker + */ + @Override + public Object clone() { + return new Marker(markerHeight, desiredMarkerPosition, + desiredMarkerIncrement, intMarkerPosition); + } + + /** + * {@inheritDoc} + */ + @Override + public String toString() { + return String.format( + "index=%.0f,n=%.0f,np=%.2f,q=%.2f,dn=%.2f,prev=%d,next=%d", + (double) index, Precision.round(intMarkerPosition, 0), + Precision.round(desiredMarkerPosition, 2), + Precision.round(markerHeight, 2), + Precision.round(desiredMarkerIncrement, 2), previous.index, + next.index); + } + } + + /** + * A simple fixed capacity list that has an upper bound to growth. + * Once its capacity is reached, {@code add} is a no-op, returning + * {@code false}. + * + * @param <E> + */ + private static class FixedCapacityList<E> extends ArrayList<E> implements + Serializable { + /** + * Serialization Version Id + */ + private static final long serialVersionUID = 2283952083075725479L; + /** + * Capacity of the list + */ + private final int capacity; + + /** + * This constructor constructs the list with given capacity and as well + * as stores the capacity + * + * @param fixedCapacity the capacity to be fixed for this list + */ + FixedCapacityList(final int fixedCapacity) { + super(fixedCapacity); + this.capacity = fixedCapacity; + } + + /** + * {@inheritDoc} In addition it checks if the {@link #size()} returns a + * size that is within capacity and if true it adds; otherwise the list + * contents are unchanged and {@code false} is returned. + * + * @return true if addition is successful and false otherwise + */ + @Override + public boolean add(final E e) { + return size() < capacity ? super.add(e) : false; + } + + /** + * {@inheritDoc} In addition it checks if the sum of Collection size and + * this instance's {@link #size()} returns a value that is within + * capacity and if true it adds the collection; otherwise the list + * contents are unchanged and {@code false} is returned. + * + * @return true if addition is successful and false otherwise + */ + @Override + public boolean addAll(Collection<? extends E> collection) { + boolean isCollectionLess = + collection != null && + collection.size() + size() <= capacity; + return isCollectionLess ? super.addAll(collection) : false; + } + } + + /** + * A creation method to build Markers + * + * @param initialFive list of initial five elements + * @param p the quantile desired + * @return an instance of PSquareMarkers + */ + public static PSquareMarkers newMarkers(final List<Double> initialFive, + final double p) { + return new Markers(initialFive, p); + } + + /** + * An interface that encapsulates abstractions of the + * P-square algorithm markers as is explained in the original works. This + * interface is exposed with protected access to help in testability. + */ + protected interface PSquareMarkers extends Cloneable { + /** + * Returns Percentile value computed thus far. + * + * @return percentile + */ + double getPercentileValue(); + + /** + * A clone function to clone the current instance. It's created as an + * interface method as well for convenience though Cloneable is just a + * marker interface. + * + * @return clone of this instance + */ + Object clone(); + + /** + * Returns the marker height (or percentile) of a given marker index. + * + * @param markerIndex is the index of marker in the marker array + * @return percentile value of the marker index passed + * @throws OutOfRangeException in case the index is not within [1-5] + */ + double height(final int markerIndex); + + /** + * Process a data point by moving the marker heights based on estimator. + * + * @param inputDataPoint is the data point passed + * @return computed percentile + */ + double processDataPoint(final double inputDataPoint); + + /** + * An Estimate of the percentile value of a given Marker + * + * @param index the marker's index in the array of markers + * @return percentile estimate + * @throws OutOfRangeException in case if index is not within [1-5] + */ + double estimate(final int index); + } +} |